|
1 /* glpapi06.c (simplex method routines) */ |
|
2 |
|
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 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 ***********************************************************************/ |
|
24 |
|
25 #include "glpios.h" |
|
26 #include "glpnpp.h" |
|
27 #include "glpspx.h" |
|
28 |
|
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). */ |
|
106 |
|
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 } |
|
216 |
|
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 } |
|
254 |
|
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 } |
|
360 |
|
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 } |
|
458 |
|
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. */ |
|
475 |
|
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 } |
|
493 |
|
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. */ |
|
514 |
|
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 } |
|
545 |
|
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. */ |
|
564 |
|
565 int glp_get_prim_stat(glp_prob *lp) |
|
566 { int pbs_stat = lp->pbs_stat; |
|
567 return pbs_stat; |
|
568 } |
|
569 |
|
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. */ |
|
588 |
|
589 int glp_get_dual_stat(glp_prob *lp) |
|
590 { int dbs_stat = lp->dbs_stat; |
|
591 return dbs_stat; |
|
592 } |
|
593 |
|
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. */ |
|
607 |
|
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 } |
|
615 |
|
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. */ |
|
635 |
|
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 } |
|
642 |
|
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. */ |
|
656 |
|
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 } |
|
667 |
|
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. */ |
|
681 |
|
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 } |
|
692 |
|
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. */ |
|
712 |
|
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 } |
|
719 |
|
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. */ |
|
733 |
|
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 } |
|
744 |
|
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. */ |
|
758 |
|
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 } |
|
769 |
|
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). */ |
|
797 |
|
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 } |
|
805 |
|
806 /* eof */ |