alpar@9: /* glpapi06.c (simplex method routines) */ alpar@9: alpar@9: /*********************************************************************** alpar@9: * This code is part of GLPK (GNU Linear Programming Kit). alpar@9: * alpar@9: * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, alpar@9: * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics, alpar@9: * Moscow Aviation Institute, Moscow, Russia. All rights reserved. alpar@9: * E-mail: . alpar@9: * alpar@9: * GLPK is free software: you can redistribute it and/or modify it alpar@9: * under the terms of the GNU General Public License as published by alpar@9: * the Free Software Foundation, either version 3 of the License, or alpar@9: * (at your option) any later version. alpar@9: * alpar@9: * GLPK is distributed in the hope that it will be useful, but WITHOUT alpar@9: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY alpar@9: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public alpar@9: * License for more details. alpar@9: * alpar@9: * You should have received a copy of the GNU General Public License alpar@9: * along with GLPK. If not, see . alpar@9: ***********************************************************************/ alpar@9: alpar@9: #include "glpios.h" alpar@9: #include "glpnpp.h" alpar@9: #include "glpspx.h" alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_simplex - solve LP problem with the simplex method alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * int glp_simplex(glp_prob *P, const glp_smcp *parm); alpar@9: * alpar@9: * DESCRIPTION alpar@9: * alpar@9: * The routine glp_simplex is a driver to the LP solver based on the alpar@9: * simplex method. This routine retrieves problem data from the alpar@9: * specified problem object, calls the solver to solve the problem alpar@9: * instance, and stores results of computations back into the problem alpar@9: * object. alpar@9: * alpar@9: * The simplex solver has a set of control parameters. Values of the alpar@9: * control parameters can be passed in a structure glp_smcp, which the alpar@9: * parameter parm points to. alpar@9: * alpar@9: * The parameter parm can be specified as NULL, in which case the LP alpar@9: * solver uses default settings. alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * 0 The LP problem instance has been successfully solved. This code alpar@9: * does not necessarily mean that the solver has found optimal alpar@9: * solution. It only means that the solution process was successful. alpar@9: * alpar@9: * GLP_EBADB alpar@9: * Unable to start the search, because the initial basis specified alpar@9: * in the problem object is invalid--the number of basic (auxiliary alpar@9: * and structural) variables is not the same as the number of rows in alpar@9: * the problem object. alpar@9: * alpar@9: * GLP_ESING alpar@9: * Unable to start the search, because the basis matrix correspodning alpar@9: * to the initial basis is singular within the working precision. alpar@9: * alpar@9: * GLP_ECOND alpar@9: * Unable to start the search, because the basis matrix correspodning alpar@9: * to the initial basis is ill-conditioned, i.e. its condition number alpar@9: * is too large. alpar@9: * alpar@9: * GLP_EBOUND alpar@9: * Unable to start the search, because some double-bounded variables alpar@9: * have incorrect bounds. alpar@9: * alpar@9: * GLP_EFAIL alpar@9: * The search was prematurely terminated due to the solver failure. alpar@9: * alpar@9: * GLP_EOBJLL alpar@9: * The search was prematurely terminated, because the objective alpar@9: * function being maximized has reached its lower limit and continues alpar@9: * decreasing (dual simplex only). alpar@9: * alpar@9: * GLP_EOBJUL alpar@9: * The search was prematurely terminated, because the objective alpar@9: * function being minimized has reached its upper limit and continues alpar@9: * increasing (dual simplex only). alpar@9: * alpar@9: * GLP_EITLIM alpar@9: * The search was prematurely terminated, because the simplex alpar@9: * iteration limit has been exceeded. alpar@9: * alpar@9: * GLP_ETMLIM alpar@9: * The search was prematurely terminated, because the time limit has alpar@9: * been exceeded. alpar@9: * alpar@9: * GLP_ENOPFS alpar@9: * The LP problem instance has no primal feasible solution (only if alpar@9: * the LP presolver is used). alpar@9: * alpar@9: * GLP_ENODFS alpar@9: * The LP problem instance has no dual feasible solution (only if the alpar@9: * LP presolver is used). */ alpar@9: alpar@9: static void trivial_lp(glp_prob *P, const glp_smcp *parm) alpar@9: { /* solve trivial LP which has empty constraint matrix */ alpar@9: GLPROW *row; alpar@9: GLPCOL *col; alpar@9: int i, j; alpar@9: double p_infeas, d_infeas, zeta; alpar@9: P->valid = 0; alpar@9: P->pbs_stat = P->dbs_stat = GLP_FEAS; alpar@9: P->obj_val = P->c0; alpar@9: P->some = 0; alpar@9: p_infeas = d_infeas = 0.0; alpar@9: /* make all auxiliary variables basic */ alpar@9: for (i = 1; i <= P->m; i++) alpar@9: { row = P->row[i]; alpar@9: row->stat = GLP_BS; alpar@9: row->prim = row->dual = 0.0; alpar@9: /* check primal feasibility */ alpar@9: if (row->type == GLP_LO || row->type == GLP_DB || alpar@9: row->type == GLP_FX) alpar@9: { /* row has lower bound */ alpar@9: if (row->lb > + parm->tol_bnd) alpar@9: { P->pbs_stat = GLP_NOFEAS; alpar@9: if (P->some == 0 && parm->meth != GLP_PRIMAL) alpar@9: P->some = i; alpar@9: } alpar@9: if (p_infeas < + row->lb) alpar@9: p_infeas = + row->lb; alpar@9: } alpar@9: if (row->type == GLP_UP || row->type == GLP_DB || alpar@9: row->type == GLP_FX) alpar@9: { /* row has upper bound */ alpar@9: if (row->ub < - parm->tol_bnd) alpar@9: { P->pbs_stat = GLP_NOFEAS; alpar@9: if (P->some == 0 && parm->meth != GLP_PRIMAL) alpar@9: P->some = i; alpar@9: } alpar@9: if (p_infeas < - row->ub) alpar@9: p_infeas = - row->ub; alpar@9: } alpar@9: } alpar@9: /* determine scale factor for the objective row */ alpar@9: zeta = 1.0; alpar@9: for (j = 1; j <= P->n; j++) alpar@9: { col = P->col[j]; alpar@9: if (zeta < fabs(col->coef)) zeta = fabs(col->coef); alpar@9: } alpar@9: zeta = (P->dir == GLP_MIN ? +1.0 : -1.0) / zeta; alpar@9: /* make all structural variables non-basic */ alpar@9: for (j = 1; j <= P->n; j++) alpar@9: { col = P->col[j]; alpar@9: if (col->type == GLP_FR) alpar@9: col->stat = GLP_NF, col->prim = 0.0; alpar@9: else if (col->type == GLP_LO) alpar@9: lo: col->stat = GLP_NL, col->prim = col->lb; alpar@9: else if (col->type == GLP_UP) alpar@9: up: col->stat = GLP_NU, col->prim = col->ub; alpar@9: else if (col->type == GLP_DB) alpar@9: { if (zeta * col->coef > 0.0) alpar@9: goto lo; alpar@9: else if (zeta * col->coef < 0.0) alpar@9: goto up; alpar@9: else if (fabs(col->lb) <= fabs(col->ub)) alpar@9: goto lo; alpar@9: else alpar@9: goto up; alpar@9: } alpar@9: else if (col->type == GLP_FX) alpar@9: col->stat = GLP_NS, col->prim = col->lb; alpar@9: col->dual = col->coef; alpar@9: P->obj_val += col->coef * col->prim; alpar@9: /* check dual feasibility */ alpar@9: if (col->type == GLP_FR || col->type == GLP_LO) alpar@9: { /* column has no upper bound */ alpar@9: if (zeta * col->dual < - parm->tol_dj) alpar@9: { P->dbs_stat = GLP_NOFEAS; alpar@9: if (P->some == 0 && parm->meth == GLP_PRIMAL) alpar@9: P->some = P->m + j; alpar@9: } alpar@9: if (d_infeas < - zeta * col->dual) alpar@9: d_infeas = - zeta * col->dual; alpar@9: } alpar@9: if (col->type == GLP_FR || col->type == GLP_UP) alpar@9: { /* column has no lower bound */ alpar@9: if (zeta * col->dual > + parm->tol_dj) alpar@9: { P->dbs_stat = GLP_NOFEAS; alpar@9: if (P->some == 0 && parm->meth == GLP_PRIMAL) alpar@9: P->some = P->m + j; alpar@9: } alpar@9: if (d_infeas < + zeta * col->dual) alpar@9: d_infeas = + zeta * col->dual; alpar@9: } alpar@9: } alpar@9: /* simulate the simplex solver output */ alpar@9: if (parm->msg_lev >= GLP_MSG_ON && parm->out_dly == 0) alpar@9: { xprintf("~%6d: obj = %17.9e infeas = %10.3e\n", P->it_cnt, alpar@9: P->obj_val, parm->meth == GLP_PRIMAL ? p_infeas : d_infeas); alpar@9: } alpar@9: if (parm->msg_lev >= GLP_MSG_ALL && parm->out_dly == 0) alpar@9: { if (P->pbs_stat == GLP_FEAS && P->dbs_stat == GLP_FEAS) alpar@9: xprintf("OPTIMAL SOLUTION FOUND\n"); alpar@9: else if (P->pbs_stat == GLP_NOFEAS) alpar@9: xprintf("PROBLEM HAS NO FEASIBLE SOLUTION\n"); alpar@9: else if (parm->meth == GLP_PRIMAL) alpar@9: xprintf("PROBLEM HAS UNBOUNDED SOLUTION\n"); alpar@9: else alpar@9: xprintf("PROBLEM HAS NO DUAL FEASIBLE SOLUTION\n"); alpar@9: } alpar@9: return; alpar@9: } alpar@9: alpar@9: static int solve_lp(glp_prob *P, const glp_smcp *parm) alpar@9: { /* solve LP directly without using the preprocessor */ alpar@9: int ret; alpar@9: if (!glp_bf_exists(P)) alpar@9: { ret = glp_factorize(P); alpar@9: if (ret == 0) alpar@9: ; alpar@9: else if (ret == GLP_EBADB) alpar@9: { if (parm->msg_lev >= GLP_MSG_ERR) alpar@9: xprintf("glp_simplex: initial basis is invalid\n"); alpar@9: } alpar@9: else if (ret == GLP_ESING) alpar@9: { if (parm->msg_lev >= GLP_MSG_ERR) alpar@9: xprintf("glp_simplex: initial basis is singular\n"); alpar@9: } alpar@9: else if (ret == GLP_ECOND) alpar@9: { if (parm->msg_lev >= GLP_MSG_ERR) alpar@9: xprintf( alpar@9: "glp_simplex: initial basis is ill-conditioned\n"); alpar@9: } alpar@9: else alpar@9: xassert(ret != ret); alpar@9: if (ret != 0) goto done; alpar@9: } alpar@9: if (parm->meth == GLP_PRIMAL) alpar@9: ret = spx_primal(P, parm); alpar@9: else if (parm->meth == GLP_DUALP) alpar@9: { ret = spx_dual(P, parm); alpar@9: if (ret == GLP_EFAIL && P->valid) alpar@9: ret = spx_primal(P, parm); alpar@9: } alpar@9: else if (parm->meth == GLP_DUAL) alpar@9: ret = spx_dual(P, parm); alpar@9: else alpar@9: xassert(parm != parm); alpar@9: done: return ret; alpar@9: } alpar@9: alpar@9: static int preprocess_and_solve_lp(glp_prob *P, const glp_smcp *parm) alpar@9: { /* solve LP using the preprocessor */ alpar@9: NPP *npp; alpar@9: glp_prob *lp = NULL; alpar@9: glp_bfcp bfcp; alpar@9: int ret; alpar@9: if (parm->msg_lev >= GLP_MSG_ALL) alpar@9: xprintf("Preprocessing...\n"); alpar@9: /* create preprocessor workspace */ alpar@9: npp = npp_create_wksp(); alpar@9: /* load original problem into the preprocessor workspace */ alpar@9: npp_load_prob(npp, P, GLP_OFF, GLP_SOL, GLP_OFF); alpar@9: /* process LP prior to applying primal/dual simplex method */ alpar@9: ret = npp_simplex(npp, parm); alpar@9: if (ret == 0) alpar@9: ; alpar@9: else if (ret == GLP_ENOPFS) alpar@9: { if (parm->msg_lev >= GLP_MSG_ALL) alpar@9: xprintf("PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION\n"); alpar@9: } alpar@9: else if (ret == GLP_ENODFS) alpar@9: { if (parm->msg_lev >= GLP_MSG_ALL) alpar@9: xprintf("PROBLEM HAS NO DUAL FEASIBLE SOLUTION\n"); alpar@9: } alpar@9: else alpar@9: xassert(ret != ret); alpar@9: if (ret != 0) goto done; alpar@9: /* build transformed LP */ alpar@9: lp = glp_create_prob(); alpar@9: npp_build_prob(npp, lp); alpar@9: /* if the transformed LP is empty, it has empty solution, which alpar@9: is optimal */ alpar@9: if (lp->m == 0 && lp->n == 0) alpar@9: { lp->pbs_stat = lp->dbs_stat = GLP_FEAS; alpar@9: lp->obj_val = lp->c0; alpar@9: if (parm->msg_lev >= GLP_MSG_ON && parm->out_dly == 0) alpar@9: { xprintf("~%6d: obj = %17.9e infeas = %10.3e\n", P->it_cnt, alpar@9: lp->obj_val, 0.0); alpar@9: } alpar@9: if (parm->msg_lev >= GLP_MSG_ALL) alpar@9: xprintf("OPTIMAL SOLUTION FOUND BY LP PREPROCESSOR\n"); alpar@9: goto post; alpar@9: } alpar@9: if (parm->msg_lev >= GLP_MSG_ALL) alpar@9: { xprintf("%d row%s, %d column%s, %d non-zero%s\n", alpar@9: lp->m, lp->m == 1 ? "" : "s", lp->n, lp->n == 1 ? "" : "s", alpar@9: lp->nnz, lp->nnz == 1 ? "" : "s"); alpar@9: } alpar@9: /* inherit basis factorization control parameters */ alpar@9: glp_get_bfcp(P, &bfcp); alpar@9: glp_set_bfcp(lp, &bfcp); alpar@9: /* scale the transformed problem */ alpar@9: { ENV *env = get_env_ptr(); alpar@9: int term_out = env->term_out; alpar@9: if (!term_out || parm->msg_lev < GLP_MSG_ALL) alpar@9: env->term_out = GLP_OFF; alpar@9: else alpar@9: env->term_out = GLP_ON; alpar@9: glp_scale_prob(lp, GLP_SF_AUTO); alpar@9: env->term_out = term_out; alpar@9: } alpar@9: /* build advanced initial basis */ alpar@9: { ENV *env = get_env_ptr(); alpar@9: int term_out = env->term_out; alpar@9: if (!term_out || parm->msg_lev < GLP_MSG_ALL) alpar@9: env->term_out = GLP_OFF; alpar@9: else alpar@9: env->term_out = GLP_ON; alpar@9: glp_adv_basis(lp, 0); alpar@9: env->term_out = term_out; alpar@9: } alpar@9: /* solve the transformed LP */ alpar@9: lp->it_cnt = P->it_cnt; alpar@9: ret = solve_lp(lp, parm); alpar@9: P->it_cnt = lp->it_cnt; alpar@9: /* only optimal solution can be postprocessed */ alpar@9: if (!(ret == 0 && lp->pbs_stat == GLP_FEAS && lp->dbs_stat == alpar@9: GLP_FEAS)) alpar@9: { if (parm->msg_lev >= GLP_MSG_ERR) alpar@9: xprintf("glp_simplex: unable to recover undefined or non-op" alpar@9: "timal solution\n"); alpar@9: if (ret == 0) alpar@9: { if (lp->pbs_stat == GLP_NOFEAS) alpar@9: ret = GLP_ENOPFS; alpar@9: else if (lp->dbs_stat == GLP_NOFEAS) alpar@9: ret = GLP_ENODFS; alpar@9: else alpar@9: xassert(lp != lp); alpar@9: } alpar@9: goto done; alpar@9: } alpar@9: post: /* postprocess solution from the transformed LP */ alpar@9: npp_postprocess(npp, lp); alpar@9: /* the transformed LP is no longer needed */ alpar@9: glp_delete_prob(lp), lp = NULL; alpar@9: /* store solution to the original problem */ alpar@9: npp_unload_sol(npp, P); alpar@9: /* the original LP has been successfully solved */ alpar@9: ret = 0; alpar@9: done: /* delete the transformed LP, if it exists */ alpar@9: if (lp != NULL) glp_delete_prob(lp); alpar@9: /* delete preprocessor workspace */ alpar@9: npp_delete_wksp(npp); alpar@9: return ret; alpar@9: } alpar@9: alpar@9: int glp_simplex(glp_prob *P, const glp_smcp *parm) alpar@9: { /* solve LP problem with the simplex method */ alpar@9: glp_smcp _parm; alpar@9: int i, j, ret; alpar@9: /* check problem object */ alpar@9: if (P == NULL || P->magic != GLP_PROB_MAGIC) alpar@9: xerror("glp_simplex: P = %p; invalid problem object\n", P); alpar@9: if (P->tree != NULL && P->tree->reason != 0) alpar@9: xerror("glp_simplex: operation not allowed\n"); alpar@9: /* check control parameters */ alpar@9: if (parm == NULL) alpar@9: parm = &_parm, glp_init_smcp((glp_smcp *)parm); alpar@9: if (!(parm->msg_lev == GLP_MSG_OFF || alpar@9: parm->msg_lev == GLP_MSG_ERR || alpar@9: parm->msg_lev == GLP_MSG_ON || alpar@9: parm->msg_lev == GLP_MSG_ALL || alpar@9: parm->msg_lev == GLP_MSG_DBG)) alpar@9: xerror("glp_simplex: msg_lev = %d; invalid parameter\n", alpar@9: parm->msg_lev); alpar@9: if (!(parm->meth == GLP_PRIMAL || alpar@9: parm->meth == GLP_DUALP || alpar@9: parm->meth == GLP_DUAL)) alpar@9: xerror("glp_simplex: meth = %d; invalid parameter\n", alpar@9: parm->meth); alpar@9: if (!(parm->pricing == GLP_PT_STD || alpar@9: parm->pricing == GLP_PT_PSE)) alpar@9: xerror("glp_simplex: pricing = %d; invalid parameter\n", alpar@9: parm->pricing); alpar@9: if (!(parm->r_test == GLP_RT_STD || alpar@9: parm->r_test == GLP_RT_HAR)) alpar@9: xerror("glp_simplex: r_test = %d; invalid parameter\n", alpar@9: parm->r_test); alpar@9: if (!(0.0 < parm->tol_bnd && parm->tol_bnd < 1.0)) alpar@9: xerror("glp_simplex: tol_bnd = %g; invalid parameter\n", alpar@9: parm->tol_bnd); alpar@9: if (!(0.0 < parm->tol_dj && parm->tol_dj < 1.0)) alpar@9: xerror("glp_simplex: tol_dj = %g; invalid parameter\n", alpar@9: parm->tol_dj); alpar@9: if (!(0.0 < parm->tol_piv && parm->tol_piv < 1.0)) alpar@9: xerror("glp_simplex: tol_piv = %g; invalid parameter\n", alpar@9: parm->tol_piv); alpar@9: if (parm->it_lim < 0) alpar@9: xerror("glp_simplex: it_lim = %d; invalid parameter\n", alpar@9: parm->it_lim); alpar@9: if (parm->tm_lim < 0) alpar@9: xerror("glp_simplex: tm_lim = %d; invalid parameter\n", alpar@9: parm->tm_lim); alpar@9: if (parm->out_frq < 1) alpar@9: xerror("glp_simplex: out_frq = %d; invalid parameter\n", alpar@9: parm->out_frq); alpar@9: if (parm->out_dly < 0) alpar@9: xerror("glp_simplex: out_dly = %d; invalid parameter\n", alpar@9: parm->out_dly); alpar@9: if (!(parm->presolve == GLP_ON || parm->presolve == GLP_OFF)) alpar@9: xerror("glp_simplex: presolve = %d; invalid parameter\n", alpar@9: parm->presolve); alpar@9: /* basic solution is currently undefined */ alpar@9: P->pbs_stat = P->dbs_stat = GLP_UNDEF; alpar@9: P->obj_val = 0.0; alpar@9: P->some = 0; alpar@9: /* check bounds of double-bounded variables */ alpar@9: for (i = 1; i <= P->m; i++) alpar@9: { GLPROW *row = P->row[i]; alpar@9: if (row->type == GLP_DB && row->lb >= row->ub) alpar@9: { if (parm->msg_lev >= GLP_MSG_ERR) alpar@9: xprintf("glp_simplex: row %d: lb = %g, ub = %g; incorrec" alpar@9: "t bounds\n", i, row->lb, row->ub); alpar@9: ret = GLP_EBOUND; alpar@9: goto done; alpar@9: } alpar@9: } alpar@9: for (j = 1; j <= P->n; j++) alpar@9: { GLPCOL *col = P->col[j]; alpar@9: if (col->type == GLP_DB && col->lb >= col->ub) alpar@9: { if (parm->msg_lev >= GLP_MSG_ERR) alpar@9: xprintf("glp_simplex: column %d: lb = %g, ub = %g; incor" alpar@9: "rect bounds\n", j, col->lb, col->ub); alpar@9: ret = GLP_EBOUND; alpar@9: goto done; alpar@9: } alpar@9: } alpar@9: /* solve LP problem */ alpar@9: if (parm->msg_lev >= GLP_MSG_ALL) alpar@9: { xprintf("GLPK Simplex Optimizer, v%s\n", glp_version()); alpar@9: xprintf("%d row%s, %d column%s, %d non-zero%s\n", alpar@9: P->m, P->m == 1 ? "" : "s", P->n, P->n == 1 ? "" : "s", alpar@9: P->nnz, P->nnz == 1 ? "" : "s"); alpar@9: } alpar@9: if (P->nnz == 0) alpar@9: trivial_lp(P, parm), ret = 0; alpar@9: else if (!parm->presolve) alpar@9: ret = solve_lp(P, parm); alpar@9: else alpar@9: ret = preprocess_and_solve_lp(P, parm); alpar@9: done: /* return to the application program */ alpar@9: return ret; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_init_smcp - initialize simplex method control parameters alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * void glp_init_smcp(glp_smcp *parm); alpar@9: * alpar@9: * DESCRIPTION alpar@9: * alpar@9: * The routine glp_init_smcp initializes control parameters, which are alpar@9: * used by the simplex solver, with default values. alpar@9: * alpar@9: * Default values of the control parameters are stored in a glp_smcp alpar@9: * structure, which the parameter parm points to. */ alpar@9: alpar@9: void glp_init_smcp(glp_smcp *parm) alpar@9: { parm->msg_lev = GLP_MSG_ALL; alpar@9: parm->meth = GLP_PRIMAL; alpar@9: parm->pricing = GLP_PT_PSE; alpar@9: parm->r_test = GLP_RT_HAR; alpar@9: parm->tol_bnd = 1e-7; alpar@9: parm->tol_dj = 1e-7; alpar@9: parm->tol_piv = 1e-10; alpar@9: parm->obj_ll = -DBL_MAX; alpar@9: parm->obj_ul = +DBL_MAX; alpar@9: parm->it_lim = INT_MAX; alpar@9: parm->tm_lim = INT_MAX; alpar@9: parm->out_frq = 500; alpar@9: parm->out_dly = 0; alpar@9: parm->presolve = GLP_OFF; alpar@9: return; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_status - retrieve generic status of basic solution alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * int glp_get_status(glp_prob *lp); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_status reports the generic status of the basic alpar@9: * solution for the specified problem object as follows: alpar@9: * alpar@9: * GLP_OPT - solution is optimal; alpar@9: * GLP_FEAS - solution is feasible; alpar@9: * GLP_INFEAS - solution is infeasible; alpar@9: * GLP_NOFEAS - problem has no feasible solution; alpar@9: * GLP_UNBND - problem has unbounded solution; alpar@9: * GLP_UNDEF - solution is undefined. */ alpar@9: alpar@9: int glp_get_status(glp_prob *lp) alpar@9: { int status; alpar@9: status = glp_get_prim_stat(lp); alpar@9: switch (status) alpar@9: { case GLP_FEAS: alpar@9: switch (glp_get_dual_stat(lp)) alpar@9: { case GLP_FEAS: alpar@9: status = GLP_OPT; alpar@9: break; alpar@9: case GLP_NOFEAS: alpar@9: status = GLP_UNBND; alpar@9: break; alpar@9: case GLP_UNDEF: alpar@9: case GLP_INFEAS: alpar@9: status = status; alpar@9: break; alpar@9: default: alpar@9: xassert(lp != lp); alpar@9: } alpar@9: break; alpar@9: case GLP_UNDEF: alpar@9: case GLP_INFEAS: alpar@9: case GLP_NOFEAS: alpar@9: status = status; alpar@9: break; alpar@9: default: alpar@9: xassert(lp != lp); alpar@9: } alpar@9: return status; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_prim_stat - retrieve status of primal basic solution alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * int glp_get_prim_stat(glp_prob *lp); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_prim_stat reports the status of the primal basic alpar@9: * solution for the specified problem object as follows: alpar@9: * alpar@9: * GLP_UNDEF - primal solution is undefined; alpar@9: * GLP_FEAS - primal solution is feasible; alpar@9: * GLP_INFEAS - primal solution is infeasible; alpar@9: * GLP_NOFEAS - no primal feasible solution exists. */ alpar@9: alpar@9: int glp_get_prim_stat(glp_prob *lp) alpar@9: { int pbs_stat = lp->pbs_stat; alpar@9: return pbs_stat; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_dual_stat - retrieve status of dual basic solution alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * int glp_get_dual_stat(glp_prob *lp); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_dual_stat reports the status of the dual basic alpar@9: * solution for the specified problem object as follows: alpar@9: * alpar@9: * GLP_UNDEF - dual solution is undefined; alpar@9: * GLP_FEAS - dual solution is feasible; alpar@9: * GLP_INFEAS - dual solution is infeasible; alpar@9: * GLP_NOFEAS - no dual feasible solution exists. */ alpar@9: alpar@9: int glp_get_dual_stat(glp_prob *lp) alpar@9: { int dbs_stat = lp->dbs_stat; alpar@9: return dbs_stat; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_obj_val - retrieve objective value (basic solution) alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * double glp_get_obj_val(glp_prob *lp); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_obj_val returns value of the objective function alpar@9: * for basic solution. */ alpar@9: alpar@9: double glp_get_obj_val(glp_prob *lp) alpar@9: { /*struct LPXCPS *cps = lp->cps;*/ alpar@9: double z; alpar@9: z = lp->obj_val; alpar@9: /*if (cps->round && fabs(z) < 1e-9) z = 0.0;*/ alpar@9: return z; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_row_stat - retrieve row status alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * int glp_get_row_stat(glp_prob *lp, int i); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_row_stat returns current status assigned to the alpar@9: * auxiliary variable associated with i-th row as follows: alpar@9: * alpar@9: * GLP_BS - basic variable; alpar@9: * GLP_NL - non-basic variable on its lower bound; alpar@9: * GLP_NU - non-basic variable on its upper bound; alpar@9: * GLP_NF - non-basic free (unbounded) variable; alpar@9: * GLP_NS - non-basic fixed variable. */ alpar@9: alpar@9: int glp_get_row_stat(glp_prob *lp, int i) alpar@9: { if (!(1 <= i && i <= lp->m)) alpar@9: xerror("glp_get_row_stat: i = %d; row number out of range\n", alpar@9: i); alpar@9: return lp->row[i]->stat; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_row_prim - retrieve row primal value (basic solution) alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * double glp_get_row_prim(glp_prob *lp, int i); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_row_prim returns primal value of the auxiliary alpar@9: * variable associated with i-th row. */ alpar@9: alpar@9: double glp_get_row_prim(glp_prob *lp, int i) alpar@9: { /*struct LPXCPS *cps = lp->cps;*/ alpar@9: double prim; alpar@9: if (!(1 <= i && i <= lp->m)) alpar@9: xerror("glp_get_row_prim: i = %d; row number out of range\n", alpar@9: i); alpar@9: prim = lp->row[i]->prim; alpar@9: /*if (cps->round && fabs(prim) < 1e-9) prim = 0.0;*/ alpar@9: return prim; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_row_dual - retrieve row dual value (basic solution) alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * double glp_get_row_dual(glp_prob *lp, int i); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_row_dual returns dual value (i.e. reduced cost) alpar@9: * of the auxiliary variable associated with i-th row. */ alpar@9: alpar@9: double glp_get_row_dual(glp_prob *lp, int i) alpar@9: { /*struct LPXCPS *cps = lp->cps;*/ alpar@9: double dual; alpar@9: if (!(1 <= i && i <= lp->m)) alpar@9: xerror("glp_get_row_dual: i = %d; row number out of range\n", alpar@9: i); alpar@9: dual = lp->row[i]->dual; alpar@9: /*if (cps->round && fabs(dual) < 1e-9) dual = 0.0;*/ alpar@9: return dual; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_col_stat - retrieve column status alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * int glp_get_col_stat(glp_prob *lp, int j); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_col_stat returns current status assigned to the alpar@9: * structural variable associated with j-th column as follows: alpar@9: * alpar@9: * GLP_BS - basic variable; alpar@9: * GLP_NL - non-basic variable on its lower bound; alpar@9: * GLP_NU - non-basic variable on its upper bound; alpar@9: * GLP_NF - non-basic free (unbounded) variable; alpar@9: * GLP_NS - non-basic fixed variable. */ alpar@9: alpar@9: int glp_get_col_stat(glp_prob *lp, int j) alpar@9: { if (!(1 <= j && j <= lp->n)) alpar@9: xerror("glp_get_col_stat: j = %d; column number out of range\n" alpar@9: , j); alpar@9: return lp->col[j]->stat; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_col_prim - retrieve column primal value (basic solution) alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * double glp_get_col_prim(glp_prob *lp, int j); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_col_prim returns primal value of the structural alpar@9: * variable associated with j-th column. */ alpar@9: alpar@9: double glp_get_col_prim(glp_prob *lp, int j) alpar@9: { /*struct LPXCPS *cps = lp->cps;*/ alpar@9: double prim; alpar@9: if (!(1 <= j && j <= lp->n)) alpar@9: xerror("glp_get_col_prim: j = %d; column number out of range\n" alpar@9: , j); alpar@9: prim = lp->col[j]->prim; alpar@9: /*if (cps->round && fabs(prim) < 1e-9) prim = 0.0;*/ alpar@9: return prim; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_col_dual - retrieve column dual value (basic solution) alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * double glp_get_col_dual(glp_prob *lp, int j); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_col_dual returns dual value (i.e. reduced cost) alpar@9: * of the structural variable associated with j-th column. */ alpar@9: alpar@9: double glp_get_col_dual(glp_prob *lp, int j) alpar@9: { /*struct LPXCPS *cps = lp->cps;*/ alpar@9: double dual; alpar@9: if (!(1 <= j && j <= lp->n)) alpar@9: xerror("glp_get_col_dual: j = %d; column number out of range\n" alpar@9: , j); alpar@9: dual = lp->col[j]->dual; alpar@9: /*if (cps->round && fabs(dual) < 1e-9) dual = 0.0;*/ alpar@9: return dual; alpar@9: } alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * glp_get_unbnd_ray - determine variable causing unboundedness alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * int glp_get_unbnd_ray(glp_prob *lp); alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine glp_get_unbnd_ray returns the number k of a variable, alpar@9: * which causes primal or dual unboundedness. If 1 <= k <= m, it is alpar@9: * k-th auxiliary variable, and if m+1 <= k <= m+n, it is (k-m)-th alpar@9: * structural variable, where m is the number of rows, n is the number alpar@9: * of columns in the problem object. If such variable is not defined, alpar@9: * the routine returns 0. alpar@9: * alpar@9: * COMMENTS alpar@9: * alpar@9: * If it is not exactly known which version of the simplex solver alpar@9: * detected unboundedness, i.e. whether the unboundedness is primal or alpar@9: * dual, it is sufficient to check the status of the variable reported alpar@9: * with the routine glp_get_row_stat or glp_get_col_stat. If the alpar@9: * variable is non-basic, the unboundedness is primal, otherwise, if alpar@9: * the variable is basic, the unboundedness is dual (the latter case alpar@9: * means that the problem has no primal feasible dolution). */ alpar@9: alpar@9: int glp_get_unbnd_ray(glp_prob *lp) alpar@9: { int k; alpar@9: k = lp->some; alpar@9: xassert(k >= 0); alpar@9: if (k > lp->m + lp->n) k = 0; alpar@9: return k; alpar@9: } alpar@9: alpar@9: /* eof */