glpapi06.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

            parm->pricing == GLP_PT_PSE))
         xerror("glp_simplex: pricing = %d; invalid parameter\n",
            parm->pricing);
      if (!(parm->r_test == GLP_RT_STD ||
            parm->r_test == GLP_RT_HAR))
         xerror("glp_simplex: r_test = %d; invalid parameter\n",
            parm->r_test);
      if (!(0.0 < parm->tol_bnd && parm->tol_bnd < 1.0))
         xerror("glp_simplex: tol_bnd = %g; invalid parameter\n",
            parm->tol_bnd);
      if (!(0.0 < parm->tol_dj && parm->tol_dj < 1.0))
         xerror("glp_simplex: tol_dj = %g; invalid parameter\n",
            parm->tol_dj);
      if (!(0.0 < parm->tol_piv && parm->tol_piv < 1.0))
         xerror("glp_simplex: tol_piv = %g; invalid parameter\n",
            parm->tol_piv);
      if (parm->it_lim < 0)
         xerror("glp_simplex: it_lim = %d; invalid parameter\n",
            parm->it_lim);
      if (parm->tm_lim < 0)
         xerror("glp_simplex: tm_lim = %d; invalid parameter\n",
            parm->tm_lim);
      if (parm->out_frq < 1)
         xerror("glp_simplex: out_frq = %d; invalid parameter\n",
            parm->out_frq);
      if (parm->out_dly < 0)
         xerror("glp_simplex: out_dly = %d; invalid parameter\n",
            parm->out_dly);
      if (!(parm->presolve == GLP_ON || parm->presolve == GLP_OFF))
         xerror("glp_simplex: presolve = %d; invalid parameter\n",
            parm->presolve);
      /* basic solution is currently undefined */
      lp->pbs_stat = lp->dbs_stat = GLP_UNDEF;
      lp->obj_val = 0.0;
      lp->some = 0;
      /* check bounds of double-bounded variables */
      for (i = 1; i <= lp->m; i++)
      {  GLPROW *row = lp->row[i];
         if (row->type == GLP_DB && row->lb >= row->ub)
         {  if (parm->msg_lev >= GLP_MSG_ERR)
               xprintf("glp_simplex: row %d: lb = %g, ub = %g; incorrec"
                  "t bounds\n", i, row->lb, row->ub);
            ret = GLP_EBOUND;
            goto done;
         }
      }
      for (j = 1; j <= lp->n; j++)
      {  GLPCOL *col = lp->col[j];
         if (col->type == GLP_DB && col->lb >= col->ub)
         {  if (parm->msg_lev >= GLP_MSG_ERR)
               xprintf("glp_simplex: column %d: lb = %g, ub = %g; incor"
                  "rect bounds\n", j, col->lb, col->ub);
            ret = GLP_EBOUND;
            goto done;
         }
      }
      /* solve LP problem */
      if (lp->m == 0)
         trivial1(lp, parm), ret = 0;
      else if (lp->n == 0)
         trivial2(lp, parm), ret = 0;
      else if (!parm->presolve)
         ret = simplex1(lp, parm);
      else
         ret = simplex2(lp, parm);
done: /* return to the application program */
      return ret;
}

/***********************************************************************
*  NAME
*
*  glp_init_smcp - initialize simplex method control parameters
*
*  SYNOPSIS
*
*  void glp_init_smcp(glp_smcp *parm);
*
*  DESCRIPTION
*
*  The routine glp_init_smcp initializes control parameters, which are
*  used by the simplex solver, with default values.
*
*  Default values of the control parameters are stored in a glp_smcp
*  structure, which the parameter parm points to. */

void glp_init_smcp(glp_smcp *parm)
{     parm->msg_lev = GLP_MSG_ALL;
      parm->meth = GLP_PRIMAL;
      parm->pricing = GLP_PT_PSE;
      parm->r_test = GLP_RT_HAR;
      parm->tol_bnd = 1e-7;
      parm->tol_dj = 1e-7;
      parm->tol_piv = 1e-10;
      parm->obj_ll = -DBL_MAX;
      parm->obj_ul = +DBL_MAX;
      parm->it_lim = INT_MAX;
      parm->tm_lim = INT_MAX;
      parm->out_frq = 200;
      parm->out_dly = 0;
      parm->presolve = GLP_OFF;
      return;
}

/***********************************************************************
*  NAME
*
*  glp_get_status - retrieve generic status of basic solution
*
*  SYNOPSIS
*
*  int glp_get_status(glp_prob *lp);
*
*  RETURNS
*
*  The routine glp_get_status reports the generic status of the basic
*  solution for the specified problem object as follows:
*
*  GLP_OPT    - solution is optimal;
*  GLP_FEAS   - solution is feasible;
*  GLP_INFEAS - solution is infeasible;
*  GLP_NOFEAS - problem has no feasible solution;
*  GLP_UNBND  - problem has unbounded solution;
*  GLP_UNDEF  - solution is undefined. */

int glp_get_status(glp_prob *lp)
{     int status;
      status = glp_get_prim_stat(lp);
      switch (status)
      {  case GLP_FEAS:
            switch (glp_get_dual_stat(lp))
            {  case GLP_FEAS:
                  status = GLP_OPT;
                  break;
               case GLP_NOFEAS:
                  status = GLP_UNBND;
                  break;
               case GLP_UNDEF:
               case GLP_INFEAS:
                  status = status;
                  break;
               default:
                  xassert(lp != lp);
            }
            break;
         case GLP_UNDEF:
         case GLP_INFEAS:
         case GLP_NOFEAS:
            status = status;
            break;
         default:
            xassert(lp != lp);
      }
      return status;
}

/***********************************************************************
*  NAME
*
*  glp_get_prim_stat - retrieve status of primal basic solution
*
*  SYNOPSIS
*
*  int glp_get_prim_stat(glp_prob *lp);
*
*  RETURNS
*
*  The routine glp_get_prim_stat reports the status of the primal basic
*  solution for the specified problem object as follows:
*
*  GLP_UNDEF  - primal solution is undefined;
*  GLP_FEAS   - primal solution is feasible;
*  GLP_INFEAS - primal solution is infeasible;
*  GLP_NOFEAS - no primal feasible solution exists. */

int glp_get_prim_stat(glp_prob *lp)
{     int pbs_stat = lp->pbs_stat;
      return pbs_stat;
}

/***********************************************************************
*  NAME
*
*  glp_get_dual_stat - retrieve status of dual basic solution
*
*  SYNOPSIS
*
*  int glp_get_dual_stat(glp_prob *lp);
*
*  RETURNS
*
*  The routine glp_get_dual_stat reports the status of the dual basic
*  solution for the specified problem object as follows:
*
*  GLP_UNDEF  - dual solution is undefined;
*  GLP_FEAS   - dual solution is feasible;
*  GLP_INFEAS - dual solution is infeasible;
*  GLP_NOFEAS - no dual feasible solution exists. */

int glp_get_dual_stat(glp_prob *lp)
{     int dbs_stat = lp->dbs_stat;
      return dbs_stat;
}

/***********************************************************************
*  NAME
*
*  glp_get_obj_val - retrieve objective value (basic solution)
*
*  SYNOPSIS
*
*  double glp_get_obj_val(glp_prob *lp);
*
*  RETURNS
*
*  The routine glp_get_obj_val returns value of the objective function
*  for basic solution. */

double glp_get_obj_val(glp_prob *lp)
{     struct LPXCPS *cps = lp->cps;
      double z;
      z = lp->obj_val;
      if (cps->round && fabs(z) < 1e-9) z = 0.0;
      return z;
}

/***********************************************************************
*  NAME
*
*  glp_get_row_stat - retrieve row status
*
*  SYNOPSIS
*
*  int glp_get_row_stat(glp_prob *lp, int i);
*
*  RETURNS
*
*  The routine glp_get_row_stat returns current status assigned to the
*  auxiliary variable associated with i-th row as follows:
*
*  GLP_BS - basic variable;
*  GLP_NL - non-basic variable on its lower bound;
*  GLP_NU - non-basic variable on its upper bound;
*  GLP_NF - non-basic free (unbounded) variable;
*  GLP_NS - non-basic fixed variable. */

int glp_get_row_stat(glp_prob *lp, int i)
{     if (!(1 <= i && i <= lp->m))
         xerror("glp_get_row_stat: i = %d; row number out of range\n",
            i);
      return lp->row[i]->stat;
}

/***********************************************************************
*  NAME
*
*  glp_get_row_prim - retrieve row primal value (basic solution)
*
*  SYNOPSIS
*
*  double glp_get_row_prim(glp_prob *lp, int i);
*
*  RETURNS
*
*  The routine glp_get_row_prim returns primal value of the auxiliary
*  variable associated with i-th row. */

double glp_get_row_prim(glp_prob *lp, int i)
{     struct LPXCPS *cps = lp->cps;
      double prim;
      if (!(1 <= i && i <= lp->m))
         xerror("glp_get_row_prim: i = %d; row number out of range\n",
            i);
      prim = lp->row[i]->prim;
      if (cps->round && fabs(prim) < 1e-9) prim = 0.0;
      return prim;
}

/***********************************************************************
*  NAME
*
*  glp_get_row_dual - retrieve row dual value (basic solution)
*
*  SYNOPSIS
*
*  double glp_get_row_dual(glp_prob *lp, int i);
*
*  RETURNS
*
*  The routine glp_get_row_dual returns dual value (i.e. reduced cost)
*  of the auxiliary variable associated with i-th row. */

double glp_get_row_dual(glp_prob *lp, int i)
{     struct LPXCPS *cps = lp->cps;
      double dual;
      if (!(1 <= i && i <= lp->m))
         xerror("glp_get_row_dual: i = %d; row number out of range\n",
            i);
      dual = lp->row[i]->dual;
      if (cps->round && fabs(dual) < 1e-9) dual = 0.0;
      return dual;
}

/***********************************************************************
*  NAME
*
*  glp_get_col_stat - retrieve column status
*
*  SYNOPSIS
*
*  int glp_get_col_stat(glp_prob *lp, int j);
*
*  RETURNS
*
*  The routine glp_get_col_stat returns current status assigned to the
*  structural variable associated with j-th column as follows:
*
*  GLP_BS - basic variable;
*  GLP_NL - non-basic variable on its lower bound;
*  GLP_NU - non-basic variable on its upper bound;
*  GLP_NF - non-basic free (unbounded) variable;
*  GLP_NS - non-basic fixed variable. */

int glp_get_col_stat(glp_prob *lp, int j)
{     if (!(1 <= j && j <= lp->n))
         xerror("glp_get_col_stat: j = %d; column number out of range\n"
            , j);
      return lp->col[j]->stat;
}

/***********************************************************************
*  NAME
*
*  glp_get_col_prim - retrieve column primal value (basic solution)
*
*  SYNOPSIS
*
*  double glp_get_col_prim(glp_prob *lp, int j);
*
*  RETURNS
*
*  The routine glp_get_col_prim returns primal value of the structural
*  variable associated with j-th column. */

double glp_get_col_prim(glp_prob *lp, int j)
{     struct LPXCPS *cps = lp->cps;
      double prim;
      if (!(1 <= j && j <= lp->n))
         xerror("glp_get_col_prim: j = %d; column number out of range\n"
            , j);
      prim = lp->col[j]->prim;
      if (cps->round && fabs(prim) < 1e-9) prim = 0.0;
      return prim;
}

/***********************************************************************
*  NAME
*
*  glp_get_col_dual - retrieve column dual value (basic solution)
*
*  SYNOPSIS
*
*  double glp_get_col_dual(glp_prob *lp, int j);
*
*  RETURNS
*
*  The routine glp_get_col_dual returns dual value (i.e. reduced cost)
*  of the structural variable associated with j-th column. */

double glp_get_col_dual(glp_prob *lp, int j)
{     struct LPXCPS *cps = lp->cps;
      double dual;
      if (!(1 <= j && j <= lp->n))
         xerror("glp_get_col_dual: j = %d; column number out of range\n"
            , j);
      dual = lp->col[j]->dual;
      if (cps->round && fabs(dual) < 1e-9) dual = 0.0;
      return dual;
}

/***********************************************************************
*  NAME
*
*  glp_get_unbnd_ray - determine variable causing unboundedness
*
*  SYNOPSIS
*
*  int glp_get_unbnd_ray(glp_prob *lp);
*
*  RETURNS
*
*  The routine glp_get_unbnd_ray returns the number k of a variable,
*  which causes primal or dual unboundedness. If 1 <= k <= m, it is
*  k-th auxiliary variable, and if m+1 <= k <= m+n, it is (k-m)-th
*  structural variable, where m is the number of rows, n is the number
*  of columns in the problem object. If such variable is not defined,
*  the routine returns 0.
*
*  COMMENTS
*
*  If it is not exactly known which version of the simplex solver
*  detected unboundedness, i.e. whether the unboundedness is primal or
*  dual, it is sufficient to check the status of the variable reported
*  with the routine glp_get_row_stat or glp_get_col_stat. If the
*  variable is non-basic, the unboundedness is primal, otherwise, if
*  the variable is basic, the unboundedness is dual (the latter case
*  means that the problem has no primal feasible dolution). */

int glp_get_unbnd_ray(glp_prob *lp)
{     int k;
      k = lp->some;
      xassert(k >= 0);
      if (k > lp->m + lp->n) k = 0;
      return k;
}

/* eof */