lemon-project-template-glpk
view deps/glpk/src/glpapi06.c @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 /* glpapi06.c (simplex method routines) */
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 *
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
9 * E-mail: <mao@gnu.org>.
10 *
11 * GLPK is free software: you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation, either version 3 of the License, or
14 * (at your option) any later version.
15 *
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
19 * License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
23 ***********************************************************************/
25 #include "glpios.h"
26 #include "glpnpp.h"
27 #include "glpspx.h"
29 /***********************************************************************
30 * NAME
31 *
32 * glp_simplex - solve LP problem with the simplex method
33 *
34 * SYNOPSIS
35 *
36 * int glp_simplex(glp_prob *P, const glp_smcp *parm);
37 *
38 * DESCRIPTION
39 *
40 * The routine glp_simplex is a driver to the LP solver based on the
41 * simplex method. This routine retrieves problem data from the
42 * specified problem object, calls the solver to solve the problem
43 * instance, and stores results of computations back into the problem
44 * object.
45 *
46 * The simplex solver has a set of control parameters. Values of the
47 * control parameters can be passed in a structure glp_smcp, which the
48 * parameter parm points to.
49 *
50 * The parameter parm can be specified as NULL, in which case the LP
51 * solver uses default settings.
52 *
53 * RETURNS
54 *
55 * 0 The LP problem instance has been successfully solved. This code
56 * does not necessarily mean that the solver has found optimal
57 * solution. It only means that the solution process was successful.
58 *
59 * GLP_EBADB
60 * Unable to start the search, because the initial basis specified
61 * in the problem object is invalid--the number of basic (auxiliary
62 * and structural) variables is not the same as the number of rows in
63 * the problem object.
64 *
65 * GLP_ESING
66 * Unable to start the search, because the basis matrix correspodning
67 * to the initial basis is singular within the working precision.
68 *
69 * GLP_ECOND
70 * Unable to start the search, because the basis matrix correspodning
71 * to the initial basis is ill-conditioned, i.e. its condition number
72 * is too large.
73 *
74 * GLP_EBOUND
75 * Unable to start the search, because some double-bounded variables
76 * have incorrect bounds.
77 *
78 * GLP_EFAIL
79 * The search was prematurely terminated due to the solver failure.
80 *
81 * GLP_EOBJLL
82 * The search was prematurely terminated, because the objective
83 * function being maximized has reached its lower limit and continues
84 * decreasing (dual simplex only).
85 *
86 * GLP_EOBJUL
87 * The search was prematurely terminated, because the objective
88 * function being minimized has reached its upper limit and continues
89 * increasing (dual simplex only).
90 *
91 * GLP_EITLIM
92 * The search was prematurely terminated, because the simplex
93 * iteration limit has been exceeded.
94 *
95 * GLP_ETMLIM
96 * The search was prematurely terminated, because the time limit has
97 * been exceeded.
98 *
99 * GLP_ENOPFS
100 * The LP problem instance has no primal feasible solution (only if
101 * the LP presolver is used).
102 *
103 * GLP_ENODFS
104 * The LP problem instance has no dual feasible solution (only if the
105 * LP presolver is used). */
107 static void trivial_lp(glp_prob *P, const glp_smcp *parm)
108 { /* solve trivial LP which has empty constraint matrix */
109 GLPROW *row;
110 GLPCOL *col;
111 int i, j;
112 double p_infeas, d_infeas, zeta;
113 P->valid = 0;
114 P->pbs_stat = P->dbs_stat = GLP_FEAS;
115 P->obj_val = P->c0;
116 P->some = 0;
117 p_infeas = d_infeas = 0.0;
118 /* make all auxiliary variables basic */
119 for (i = 1; i <= P->m; i++)
120 { row = P->row[i];
121 row->stat = GLP_BS;
122 row->prim = row->dual = 0.0;
123 /* check primal feasibility */
124 if (row->type == GLP_LO || row->type == GLP_DB ||
125 row->type == GLP_FX)
126 { /* row has lower bound */
127 if (row->lb > + parm->tol_bnd)
128 { P->pbs_stat = GLP_NOFEAS;
129 if (P->some == 0 && parm->meth != GLP_PRIMAL)
130 P->some = i;
131 }
132 if (p_infeas < + row->lb)
133 p_infeas = + row->lb;
134 }
135 if (row->type == GLP_UP || row->type == GLP_DB ||
136 row->type == GLP_FX)
137 { /* row has upper bound */
138 if (row->ub < - parm->tol_bnd)
139 { P->pbs_stat = GLP_NOFEAS;
140 if (P->some == 0 && parm->meth != GLP_PRIMAL)
141 P->some = i;
142 }
143 if (p_infeas < - row->ub)
144 p_infeas = - row->ub;
145 }
146 }
147 /* determine scale factor for the objective row */
148 zeta = 1.0;
149 for (j = 1; j <= P->n; j++)
150 { col = P->col[j];
151 if (zeta < fabs(col->coef)) zeta = fabs(col->coef);
152 }
153 zeta = (P->dir == GLP_MIN ? +1.0 : -1.0) / zeta;
154 /* make all structural variables non-basic */
155 for (j = 1; j <= P->n; j++)
156 { col = P->col[j];
157 if (col->type == GLP_FR)
158 col->stat = GLP_NF, col->prim = 0.0;
159 else if (col->type == GLP_LO)
160 lo: col->stat = GLP_NL, col->prim = col->lb;
161 else if (col->type == GLP_UP)
162 up: col->stat = GLP_NU, col->prim = col->ub;
163 else if (col->type == GLP_DB)
164 { if (zeta * col->coef > 0.0)
165 goto lo;
166 else if (zeta * col->coef < 0.0)
167 goto up;
168 else if (fabs(col->lb) <= fabs(col->ub))
169 goto lo;
170 else
171 goto up;
172 }
173 else if (col->type == GLP_FX)
174 col->stat = GLP_NS, col->prim = col->lb;
175 col->dual = col->coef;
176 P->obj_val += col->coef * col->prim;
177 /* check dual feasibility */
178 if (col->type == GLP_FR || col->type == GLP_LO)
179 { /* column has no upper bound */
180 if (zeta * col->dual < - parm->tol_dj)
181 { P->dbs_stat = GLP_NOFEAS;
182 if (P->some == 0 && parm->meth == GLP_PRIMAL)
183 P->some = P->m + j;
184 }
185 if (d_infeas < - zeta * col->dual)
186 d_infeas = - zeta * col->dual;
187 }
188 if (col->type == GLP_FR || col->type == GLP_UP)
189 { /* column has no lower bound */
190 if (zeta * col->dual > + parm->tol_dj)
191 { P->dbs_stat = GLP_NOFEAS;
192 if (P->some == 0 && parm->meth == GLP_PRIMAL)
193 P->some = P->m + j;
194 }
195 if (d_infeas < + zeta * col->dual)
196 d_infeas = + zeta * col->dual;
197 }
198 }
199 /* simulate the simplex solver output */
200 if (parm->msg_lev >= GLP_MSG_ON && parm->out_dly == 0)
201 { xprintf("~%6d: obj = %17.9e infeas = %10.3e\n", P->it_cnt,
202 P->obj_val, parm->meth == GLP_PRIMAL ? p_infeas : d_infeas);
203 }
204 if (parm->msg_lev >= GLP_MSG_ALL && parm->out_dly == 0)
205 { if (P->pbs_stat == GLP_FEAS && P->dbs_stat == GLP_FEAS)
206 xprintf("OPTIMAL SOLUTION FOUND\n");
207 else if (P->pbs_stat == GLP_NOFEAS)
208 xprintf("PROBLEM HAS NO FEASIBLE SOLUTION\n");
209 else if (parm->meth == GLP_PRIMAL)
210 xprintf("PROBLEM HAS UNBOUNDED SOLUTION\n");
211 else
212 xprintf("PROBLEM HAS NO DUAL FEASIBLE SOLUTION\n");
213 }
214 return;
215 }
217 static int solve_lp(glp_prob *P, const glp_smcp *parm)
218 { /* solve LP directly without using the preprocessor */
219 int ret;
220 if (!glp_bf_exists(P))
221 { ret = glp_factorize(P);
222 if (ret == 0)
223 ;
224 else if (ret == GLP_EBADB)
225 { if (parm->msg_lev >= GLP_MSG_ERR)
226 xprintf("glp_simplex: initial basis is invalid\n");
227 }
228 else if (ret == GLP_ESING)
229 { if (parm->msg_lev >= GLP_MSG_ERR)
230 xprintf("glp_simplex: initial basis is singular\n");
231 }
232 else if (ret == GLP_ECOND)
233 { if (parm->msg_lev >= GLP_MSG_ERR)
234 xprintf(
235 "glp_simplex: initial basis is ill-conditioned\n");
236 }
237 else
238 xassert(ret != ret);
239 if (ret != 0) goto done;
240 }
241 if (parm->meth == GLP_PRIMAL)
242 ret = spx_primal(P, parm);
243 else if (parm->meth == GLP_DUALP)
244 { ret = spx_dual(P, parm);
245 if (ret == GLP_EFAIL && P->valid)
246 ret = spx_primal(P, parm);
247 }
248 else if (parm->meth == GLP_DUAL)
249 ret = spx_dual(P, parm);
250 else
251 xassert(parm != parm);
252 done: return ret;
253 }
255 static int preprocess_and_solve_lp(glp_prob *P, const glp_smcp *parm)
256 { /* solve LP using the preprocessor */
257 NPP *npp;
258 glp_prob *lp = NULL;
259 glp_bfcp bfcp;
260 int ret;
261 if (parm->msg_lev >= GLP_MSG_ALL)
262 xprintf("Preprocessing...\n");
263 /* create preprocessor workspace */
264 npp = npp_create_wksp();
265 /* load original problem into the preprocessor workspace */
266 npp_load_prob(npp, P, GLP_OFF, GLP_SOL, GLP_OFF);
267 /* process LP prior to applying primal/dual simplex method */
268 ret = npp_simplex(npp, parm);
269 if (ret == 0)
270 ;
271 else if (ret == GLP_ENOPFS)
272 { if (parm->msg_lev >= GLP_MSG_ALL)
273 xprintf("PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION\n");
274 }
275 else if (ret == GLP_ENODFS)
276 { if (parm->msg_lev >= GLP_MSG_ALL)
277 xprintf("PROBLEM HAS NO DUAL FEASIBLE SOLUTION\n");
278 }
279 else
280 xassert(ret != ret);
281 if (ret != 0) goto done;
282 /* build transformed LP */
283 lp = glp_create_prob();
284 npp_build_prob(npp, lp);
285 /* if the transformed LP is empty, it has empty solution, which
286 is optimal */
287 if (lp->m == 0 && lp->n == 0)
288 { lp->pbs_stat = lp->dbs_stat = GLP_FEAS;
289 lp->obj_val = lp->c0;
290 if (parm->msg_lev >= GLP_MSG_ON && parm->out_dly == 0)
291 { xprintf("~%6d: obj = %17.9e infeas = %10.3e\n", P->it_cnt,
292 lp->obj_val, 0.0);
293 }
294 if (parm->msg_lev >= GLP_MSG_ALL)
295 xprintf("OPTIMAL SOLUTION FOUND BY LP PREPROCESSOR\n");
296 goto post;
297 }
298 if (parm->msg_lev >= GLP_MSG_ALL)
299 { xprintf("%d row%s, %d column%s, %d non-zero%s\n",
300 lp->m, lp->m == 1 ? "" : "s", lp->n, lp->n == 1 ? "" : "s",
301 lp->nnz, lp->nnz == 1 ? "" : "s");
302 }
303 /* inherit basis factorization control parameters */
304 glp_get_bfcp(P, &bfcp);
305 glp_set_bfcp(lp, &bfcp);
306 /* scale the transformed problem */
307 { ENV *env = get_env_ptr();
308 int term_out = env->term_out;
309 if (!term_out || parm->msg_lev < GLP_MSG_ALL)
310 env->term_out = GLP_OFF;
311 else
312 env->term_out = GLP_ON;
313 glp_scale_prob(lp, GLP_SF_AUTO);
314 env->term_out = term_out;
315 }
316 /* build advanced initial basis */
317 { ENV *env = get_env_ptr();
318 int term_out = env->term_out;
319 if (!term_out || parm->msg_lev < GLP_MSG_ALL)
320 env->term_out = GLP_OFF;
321 else
322 env->term_out = GLP_ON;
323 glp_adv_basis(lp, 0);
324 env->term_out = term_out;
325 }
326 /* solve the transformed LP */
327 lp->it_cnt = P->it_cnt;
328 ret = solve_lp(lp, parm);
329 P->it_cnt = lp->it_cnt;
330 /* only optimal solution can be postprocessed */
331 if (!(ret == 0 && lp->pbs_stat == GLP_FEAS && lp->dbs_stat ==
332 GLP_FEAS))
333 { if (parm->msg_lev >= GLP_MSG_ERR)
334 xprintf("glp_simplex: unable to recover undefined or non-op"
335 "timal solution\n");
336 if (ret == 0)
337 { if (lp->pbs_stat == GLP_NOFEAS)
338 ret = GLP_ENOPFS;
339 else if (lp->dbs_stat == GLP_NOFEAS)
340 ret = GLP_ENODFS;
341 else
342 xassert(lp != lp);
343 }
344 goto done;
345 }
346 post: /* postprocess solution from the transformed LP */
347 npp_postprocess(npp, lp);
348 /* the transformed LP is no longer needed */
349 glp_delete_prob(lp), lp = NULL;
350 /* store solution to the original problem */
351 npp_unload_sol(npp, P);
352 /* the original LP has been successfully solved */
353 ret = 0;
354 done: /* delete the transformed LP, if it exists */
355 if (lp != NULL) glp_delete_prob(lp);
356 /* delete preprocessor workspace */
357 npp_delete_wksp(npp);
358 return ret;
359 }
361 int glp_simplex(glp_prob *P, const glp_smcp *parm)
362 { /* solve LP problem with the simplex method */
363 glp_smcp _parm;
364 int i, j, ret;
365 /* check problem object */
366 if (P == NULL || P->magic != GLP_PROB_MAGIC)
367 xerror("glp_simplex: P = %p; invalid problem object\n", P);
368 if (P->tree != NULL && P->tree->reason != 0)
369 xerror("glp_simplex: operation not allowed\n");
370 /* check control parameters */
371 if (parm == NULL)
372 parm = &_parm, glp_init_smcp((glp_smcp *)parm);
373 if (!(parm->msg_lev == GLP_MSG_OFF ||
374 parm->msg_lev == GLP_MSG_ERR ||
375 parm->msg_lev == GLP_MSG_ON ||
376 parm->msg_lev == GLP_MSG_ALL ||
377 parm->msg_lev == GLP_MSG_DBG))
378 xerror("glp_simplex: msg_lev = %d; invalid parameter\n",
379 parm->msg_lev);
380 if (!(parm->meth == GLP_PRIMAL ||
381 parm->meth == GLP_DUALP ||
382 parm->meth == GLP_DUAL))
383 xerror("glp_simplex: meth = %d; invalid parameter\n",
384 parm->meth);
385 if (!(parm->pricing == GLP_PT_STD ||
386 parm->pricing == GLP_PT_PSE))
387 xerror("glp_simplex: pricing = %d; invalid parameter\n",
388 parm->pricing);
389 if (!(parm->r_test == GLP_RT_STD ||
390 parm->r_test == GLP_RT_HAR))
391 xerror("glp_simplex: r_test = %d; invalid parameter\n",
392 parm->r_test);
393 if (!(0.0 < parm->tol_bnd && parm->tol_bnd < 1.0))
394 xerror("glp_simplex: tol_bnd = %g; invalid parameter\n",
395 parm->tol_bnd);
396 if (!(0.0 < parm->tol_dj && parm->tol_dj < 1.0))
397 xerror("glp_simplex: tol_dj = %g; invalid parameter\n",
398 parm->tol_dj);
399 if (!(0.0 < parm->tol_piv && parm->tol_piv < 1.0))
400 xerror("glp_simplex: tol_piv = %g; invalid parameter\n",
401 parm->tol_piv);
402 if (parm->it_lim < 0)
403 xerror("glp_simplex: it_lim = %d; invalid parameter\n",
404 parm->it_lim);
405 if (parm->tm_lim < 0)
406 xerror("glp_simplex: tm_lim = %d; invalid parameter\n",
407 parm->tm_lim);
408 if (parm->out_frq < 1)
409 xerror("glp_simplex: out_frq = %d; invalid parameter\n",
410 parm->out_frq);
411 if (parm->out_dly < 0)
412 xerror("glp_simplex: out_dly = %d; invalid parameter\n",
413 parm->out_dly);
414 if (!(parm->presolve == GLP_ON || parm->presolve == GLP_OFF))
415 xerror("glp_simplex: presolve = %d; invalid parameter\n",
416 parm->presolve);
417 /* basic solution is currently undefined */
418 P->pbs_stat = P->dbs_stat = GLP_UNDEF;
419 P->obj_val = 0.0;
420 P->some = 0;
421 /* check bounds of double-bounded variables */
422 for (i = 1; i <= P->m; i++)
423 { GLPROW *row = P->row[i];
424 if (row->type == GLP_DB && row->lb >= row->ub)
425 { if (parm->msg_lev >= GLP_MSG_ERR)
426 xprintf("glp_simplex: row %d: lb = %g, ub = %g; incorrec"
427 "t bounds\n", i, row->lb, row->ub);
428 ret = GLP_EBOUND;
429 goto done;
430 }
431 }
432 for (j = 1; j <= P->n; j++)
433 { GLPCOL *col = P->col[j];
434 if (col->type == GLP_DB && col->lb >= col->ub)
435 { if (parm->msg_lev >= GLP_MSG_ERR)
436 xprintf("glp_simplex: column %d: lb = %g, ub = %g; incor"
437 "rect bounds\n", j, col->lb, col->ub);
438 ret = GLP_EBOUND;
439 goto done;
440 }
441 }
442 /* solve LP problem */
443 if (parm->msg_lev >= GLP_MSG_ALL)
444 { xprintf("GLPK Simplex Optimizer, v%s\n", glp_version());
445 xprintf("%d row%s, %d column%s, %d non-zero%s\n",
446 P->m, P->m == 1 ? "" : "s", P->n, P->n == 1 ? "" : "s",
447 P->nnz, P->nnz == 1 ? "" : "s");
448 }
449 if (P->nnz == 0)
450 trivial_lp(P, parm), ret = 0;
451 else if (!parm->presolve)
452 ret = solve_lp(P, parm);
453 else
454 ret = preprocess_and_solve_lp(P, parm);
455 done: /* return to the application program */
456 return ret;
457 }
459 /***********************************************************************
460 * NAME
461 *
462 * glp_init_smcp - initialize simplex method control parameters
463 *
464 * SYNOPSIS
465 *
466 * void glp_init_smcp(glp_smcp *parm);
467 *
468 * DESCRIPTION
469 *
470 * The routine glp_init_smcp initializes control parameters, which are
471 * used by the simplex solver, with default values.
472 *
473 * Default values of the control parameters are stored in a glp_smcp
474 * structure, which the parameter parm points to. */
476 void glp_init_smcp(glp_smcp *parm)
477 { parm->msg_lev = GLP_MSG_ALL;
478 parm->meth = GLP_PRIMAL;
479 parm->pricing = GLP_PT_PSE;
480 parm->r_test = GLP_RT_HAR;
481 parm->tol_bnd = 1e-7;
482 parm->tol_dj = 1e-7;
483 parm->tol_piv = 1e-10;
484 parm->obj_ll = -DBL_MAX;
485 parm->obj_ul = +DBL_MAX;
486 parm->it_lim = INT_MAX;
487 parm->tm_lim = INT_MAX;
488 parm->out_frq = 500;
489 parm->out_dly = 0;
490 parm->presolve = GLP_OFF;
491 return;
492 }
494 /***********************************************************************
495 * NAME
496 *
497 * glp_get_status - retrieve generic status of basic solution
498 *
499 * SYNOPSIS
500 *
501 * int glp_get_status(glp_prob *lp);
502 *
503 * RETURNS
504 *
505 * The routine glp_get_status reports the generic status of the basic
506 * solution for the specified problem object as follows:
507 *
508 * GLP_OPT - solution is optimal;
509 * GLP_FEAS - solution is feasible;
510 * GLP_INFEAS - solution is infeasible;
511 * GLP_NOFEAS - problem has no feasible solution;
512 * GLP_UNBND - problem has unbounded solution;
513 * GLP_UNDEF - solution is undefined. */
515 int glp_get_status(glp_prob *lp)
516 { int status;
517 status = glp_get_prim_stat(lp);
518 switch (status)
519 { case GLP_FEAS:
520 switch (glp_get_dual_stat(lp))
521 { case GLP_FEAS:
522 status = GLP_OPT;
523 break;
524 case GLP_NOFEAS:
525 status = GLP_UNBND;
526 break;
527 case GLP_UNDEF:
528 case GLP_INFEAS:
529 status = status;
530 break;
531 default:
532 xassert(lp != lp);
533 }
534 break;
535 case GLP_UNDEF:
536 case GLP_INFEAS:
537 case GLP_NOFEAS:
538 status = status;
539 break;
540 default:
541 xassert(lp != lp);
542 }
543 return status;
544 }
546 /***********************************************************************
547 * NAME
548 *
549 * glp_get_prim_stat - retrieve status of primal basic solution
550 *
551 * SYNOPSIS
552 *
553 * int glp_get_prim_stat(glp_prob *lp);
554 *
555 * RETURNS
556 *
557 * The routine glp_get_prim_stat reports the status of the primal basic
558 * solution for the specified problem object as follows:
559 *
560 * GLP_UNDEF - primal solution is undefined;
561 * GLP_FEAS - primal solution is feasible;
562 * GLP_INFEAS - primal solution is infeasible;
563 * GLP_NOFEAS - no primal feasible solution exists. */
565 int glp_get_prim_stat(glp_prob *lp)
566 { int pbs_stat = lp->pbs_stat;
567 return pbs_stat;
568 }
570 /***********************************************************************
571 * NAME
572 *
573 * glp_get_dual_stat - retrieve status of dual basic solution
574 *
575 * SYNOPSIS
576 *
577 * int glp_get_dual_stat(glp_prob *lp);
578 *
579 * RETURNS
580 *
581 * The routine glp_get_dual_stat reports the status of the dual basic
582 * solution for the specified problem object as follows:
583 *
584 * GLP_UNDEF - dual solution is undefined;
585 * GLP_FEAS - dual solution is feasible;
586 * GLP_INFEAS - dual solution is infeasible;
587 * GLP_NOFEAS - no dual feasible solution exists. */
589 int glp_get_dual_stat(glp_prob *lp)
590 { int dbs_stat = lp->dbs_stat;
591 return dbs_stat;
592 }
594 /***********************************************************************
595 * NAME
596 *
597 * glp_get_obj_val - retrieve objective value (basic solution)
598 *
599 * SYNOPSIS
600 *
601 * double glp_get_obj_val(glp_prob *lp);
602 *
603 * RETURNS
604 *
605 * The routine glp_get_obj_val returns value of the objective function
606 * for basic solution. */
608 double glp_get_obj_val(glp_prob *lp)
609 { /*struct LPXCPS *cps = lp->cps;*/
610 double z;
611 z = lp->obj_val;
612 /*if (cps->round && fabs(z) < 1e-9) z = 0.0;*/
613 return z;
614 }
616 /***********************************************************************
617 * NAME
618 *
619 * glp_get_row_stat - retrieve row status
620 *
621 * SYNOPSIS
622 *
623 * int glp_get_row_stat(glp_prob *lp, int i);
624 *
625 * RETURNS
626 *
627 * The routine glp_get_row_stat returns current status assigned to the
628 * auxiliary variable associated with i-th row as follows:
629 *
630 * GLP_BS - basic variable;
631 * GLP_NL - non-basic variable on its lower bound;
632 * GLP_NU - non-basic variable on its upper bound;
633 * GLP_NF - non-basic free (unbounded) variable;
634 * GLP_NS - non-basic fixed variable. */
636 int glp_get_row_stat(glp_prob *lp, int i)
637 { if (!(1 <= i && i <= lp->m))
638 xerror("glp_get_row_stat: i = %d; row number out of range\n",
639 i);
640 return lp->row[i]->stat;
641 }
643 /***********************************************************************
644 * NAME
645 *
646 * glp_get_row_prim - retrieve row primal value (basic solution)
647 *
648 * SYNOPSIS
649 *
650 * double glp_get_row_prim(glp_prob *lp, int i);
651 *
652 * RETURNS
653 *
654 * The routine glp_get_row_prim returns primal value of the auxiliary
655 * variable associated with i-th row. */
657 double glp_get_row_prim(glp_prob *lp, int i)
658 { /*struct LPXCPS *cps = lp->cps;*/
659 double prim;
660 if (!(1 <= i && i <= lp->m))
661 xerror("glp_get_row_prim: i = %d; row number out of range\n",
662 i);
663 prim = lp->row[i]->prim;
664 /*if (cps->round && fabs(prim) < 1e-9) prim = 0.0;*/
665 return prim;
666 }
668 /***********************************************************************
669 * NAME
670 *
671 * glp_get_row_dual - retrieve row dual value (basic solution)
672 *
673 * SYNOPSIS
674 *
675 * double glp_get_row_dual(glp_prob *lp, int i);
676 *
677 * RETURNS
678 *
679 * The routine glp_get_row_dual returns dual value (i.e. reduced cost)
680 * of the auxiliary variable associated with i-th row. */
682 double glp_get_row_dual(glp_prob *lp, int i)
683 { /*struct LPXCPS *cps = lp->cps;*/
684 double dual;
685 if (!(1 <= i && i <= lp->m))
686 xerror("glp_get_row_dual: i = %d; row number out of range\n",
687 i);
688 dual = lp->row[i]->dual;
689 /*if (cps->round && fabs(dual) < 1e-9) dual = 0.0;*/
690 return dual;
691 }
693 /***********************************************************************
694 * NAME
695 *
696 * glp_get_col_stat - retrieve column status
697 *
698 * SYNOPSIS
699 *
700 * int glp_get_col_stat(glp_prob *lp, int j);
701 *
702 * RETURNS
703 *
704 * The routine glp_get_col_stat returns current status assigned to the
705 * structural variable associated with j-th column as follows:
706 *
707 * GLP_BS - basic variable;
708 * GLP_NL - non-basic variable on its lower bound;
709 * GLP_NU - non-basic variable on its upper bound;
710 * GLP_NF - non-basic free (unbounded) variable;
711 * GLP_NS - non-basic fixed variable. */
713 int glp_get_col_stat(glp_prob *lp, int j)
714 { if (!(1 <= j && j <= lp->n))
715 xerror("glp_get_col_stat: j = %d; column number out of range\n"
716 , j);
717 return lp->col[j]->stat;
718 }
720 /***********************************************************************
721 * NAME
722 *
723 * glp_get_col_prim - retrieve column primal value (basic solution)
724 *
725 * SYNOPSIS
726 *
727 * double glp_get_col_prim(glp_prob *lp, int j);
728 *
729 * RETURNS
730 *
731 * The routine glp_get_col_prim returns primal value of the structural
732 * variable associated with j-th column. */
734 double glp_get_col_prim(glp_prob *lp, int j)
735 { /*struct LPXCPS *cps = lp->cps;*/
736 double prim;
737 if (!(1 <= j && j <= lp->n))
738 xerror("glp_get_col_prim: j = %d; column number out of range\n"
739 , j);
740 prim = lp->col[j]->prim;
741 /*if (cps->round && fabs(prim) < 1e-9) prim = 0.0;*/
742 return prim;
743 }
745 /***********************************************************************
746 * NAME
747 *
748 * glp_get_col_dual - retrieve column dual value (basic solution)
749 *
750 * SYNOPSIS
751 *
752 * double glp_get_col_dual(glp_prob *lp, int j);
753 *
754 * RETURNS
755 *
756 * The routine glp_get_col_dual returns dual value (i.e. reduced cost)
757 * of the structural variable associated with j-th column. */
759 double glp_get_col_dual(glp_prob *lp, int j)
760 { /*struct LPXCPS *cps = lp->cps;*/
761 double dual;
762 if (!(1 <= j && j <= lp->n))
763 xerror("glp_get_col_dual: j = %d; column number out of range\n"
764 , j);
765 dual = lp->col[j]->dual;
766 /*if (cps->round && fabs(dual) < 1e-9) dual = 0.0;*/
767 return dual;
768 }
770 /***********************************************************************
771 * NAME
772 *
773 * glp_get_unbnd_ray - determine variable causing unboundedness
774 *
775 * SYNOPSIS
776 *
777 * int glp_get_unbnd_ray(glp_prob *lp);
778 *
779 * RETURNS
780 *
781 * The routine glp_get_unbnd_ray returns the number k of a variable,
782 * which causes primal or dual unboundedness. If 1 <= k <= m, it is
783 * k-th auxiliary variable, and if m+1 <= k <= m+n, it is (k-m)-th
784 * structural variable, where m is the number of rows, n is the number
785 * of columns in the problem object. If such variable is not defined,
786 * the routine returns 0.
787 *
788 * COMMENTS
789 *
790 * If it is not exactly known which version of the simplex solver
791 * detected unboundedness, i.e. whether the unboundedness is primal or
792 * dual, it is sufficient to check the status of the variable reported
793 * with the routine glp_get_row_stat or glp_get_col_stat. If the
794 * variable is non-basic, the unboundedness is primal, otherwise, if
795 * the variable is basic, the unboundedness is dual (the latter case
796 * means that the problem has no primal feasible dolution). */
798 int glp_get_unbnd_ray(glp_prob *lp)
799 { int k;
800 k = lp->some;
801 xassert(k >= 0);
802 if (k > lp->m + lp->n) k = 0;
803 return k;
804 }
806 /* eof */