COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpapi06.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 26.0 KB
Line 
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
107static 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)
160lo:         col->stat = GLP_NL, col->prim = col->lb;
161         else if (col->type == GLP_UP)
162up:         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
217static 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);
252done: return ret;
253}
254
255static 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      }
346post: /* 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;
354done: /* 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
361int 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);
455done: /* 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
476void 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
515int 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
565int 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
589int 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
608double 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
636int 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
657double 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
682double 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
713int 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
734double 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
759double 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
798int 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 */
Note: See TracBrowser for help on using the repository browser.