glpapi09.c

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

         goto done;
      }
      /* build resultant MIP problem object */
      prob = ipp_build_prob(ipp);
      {  glp_bfcp bfcp;
         glp_get_bfcp(orig, &bfcp);
         glp_set_bfcp(prob, &bfcp);
      }
      /* display some statistics */
      if (parm->msg_lev >= GLP_MSG_ALL)
      {  int m = lpx_get_num_rows(prob);
         int n = lpx_get_num_cols(prob);
         int nnz = lpx_get_num_nz(prob);
         int ni = lpx_get_num_int(prob);
         int nb = lpx_get_num_bin(prob);
         char s[50];
         xprintf("glp_intopt: presolved MIP has %d row%s, %d column%s, "
            "%d non-zero%s\n",
            m, m == 1 ? "" : "s", n, n == 1 ? "" : "s",
            nnz, nnz == 1 ? "" : "s");
         if (nb == 0)
            strcpy(s, "none of");
         else if (ni == 1 && nb == 1)
            strcpy(s, "");
         else if (nb == 1)
            strcpy(s, "one of");
         else if (nb == ni)
            strcpy(s, "all of");
         else
            sprintf(s, "%d of", nb);
         xprintf(
            "glp_intopt: %d integer column%s, %s which %s binary\n",
            ni, ni == 1 ? "" : "s", s, nb == 1 ? "is" : "are");
      }
      /* solve LP relaxation */
      if (!term_out || parm->msg_lev < GLP_MSG_ALL)
         env->term_out = GLP_OFF;
      else
         env->term_out = GLP_ON;
      glp_scale_prob(prob,
         GLP_SF_GM | GLP_SF_EQ | GLP_SF_2N | GLP_SF_SKIP);
      glp_adv_basis(prob, 0);
      env->term_out = term_out;
      if (parm->msg_lev >= GLP_MSG_ALL)
         xprintf("Solving LP relaxation...\n");
      prob->it_cnt = orig->it_cnt;
      {  glp_smcp smcp;
         glp_init_smcp(&smcp);
         smcp.msg_lev = parm->msg_lev;
         ret = glp_simplex(prob, &smcp);
      }
      orig->it_cnt = prob->it_cnt;
      if (ret != 0)
      {  if (parm->msg_lev >= GLP_MSG_ERR)
            xprintf("glp_intopt: cannot solve LP relaxation\n");
         ret = GLP_EFAIL;
         goto done;
      }
      /* analyze status of the basic solution */
      switch (glp_get_status(prob))
      {  case GLP_OPT:
            break;
         case GLP_NOFEAS:
            ret = GLP_ENOPFS;
            goto done;
         case GLP_UNBND:
            ret = GLP_ENODFS;
            goto done;
         default:
            xassert(prob != prob);
      }
      /* try to solve the resultant problem */
      prob->it_cnt = orig->it_cnt;
      ret = driver1(prob, parm);
      orig->it_cnt = prob->it_cnt;
      /* determine status of MIP solution */
      i_stat = glp_mip_status(prob);
      if (i_stat == GLP_OPT || i_stat == GLP_FEAS)
      {  /* load MIP solution of the resultant problem into presolver
            workspace */
         ipp_load_sol(ipp, prob);
         /* perform MIP postsolve processing */
         ipp_postsolve(ipp);
         /* unload recovered MIP solution and store it in the original
            problem object */
         ipp_unload_sol(ipp, orig,
            i_stat == GLP_OPT ? LPX_I_OPT : LPX_I_FEAS);
      }
      else
      {  /* just set the status of MIP solution */
         orig->mip_stat = i_stat;
      }
done: /* delete the resultant problem object */
      if (prob != NULL) lpx_delete_prob(prob);
      /* delete MIP presolver workspace */
      if (ipp != NULL) ipp_delete_wksp(ipp);
      return ret;
}

int glp_intopt(glp_prob *mip, const glp_iocp *parm)
{     glp_iocp _parm;
      int m = mip->m;
      int n = mip->n;
      int i, j, ret;
      if (mip->tree != NULL)
         xerror("glp_intopt: problem object is already used by the MIP "
            "solver\n");
      if (parm == NULL)
         glp_init_iocp(&_parm);
      else
         memcpy(&_parm, parm, sizeof(glp_iocp));
      parm = &_parm;
      /* check control parameters */
      if (!(parm->msg_lev == GLP_MSG_OFF ||
            parm->msg_lev == GLP_MSG_ERR ||
            parm->msg_lev == GLP_MSG_ON  ||
            parm->msg_lev == GLP_MSG_ALL ||
            parm->msg_lev == GLP_MSG_DBG))
         xerror("glp_intopt: msg_lev = %d; invalid parameter\n",
            parm->msg_lev);
      if (!(parm->br_tech == GLP_BR_FFV ||
            parm->br_tech == GLP_BR_LFV ||
            parm->br_tech == GLP_BR_MFV ||
            parm->br_tech == GLP_BR_DTH ||
            parm->br_tech == GLP_BR_HPC))
         xerror("glp_intopt: br_tech = %d; invalid parameter\n",
            parm->br_tech);
      if (!(parm->bt_tech == GLP_BT_DFS ||
            parm->bt_tech == GLP_BT_BFS ||
            parm->bt_tech == GLP_BT_BLB ||
            parm->bt_tech == GLP_BT_BPH))
         xerror("glp_intopt: bt_tech = %d; invalid parameter\n",
            parm->bt_tech);
      if (!(0.0 < parm->tol_int && parm->tol_int < 1.0))
         xerror("glp_intopt: tol_int = %g; invalid parameter\n",
            parm->tol_int);
      if (!(0.0 < parm->tol_obj && parm->tol_obj < 1.0))
         xerror("glp_intopt: tol_obj = %g; invalid parameter\n",
            parm->tol_obj);
      if (parm->tm_lim < 0)
         xerror("glp_intopt: tm_lim = %d; invalid parameter\n",
            parm->tm_lim);
      if (parm->out_frq < 0)
         xerror("glp_intopt: out_frq = %d; invalid parameter\n",
            parm->out_frq);
      if (parm->out_dly < 0)
         xerror("glp_intopt: out_dly = %d; invalid parameter\n",
            parm->out_dly);
      if (!(0 <= parm->cb_size && parm->cb_size <= 256))
         xerror("glp_intopt: cb_size = %d; invalid parameter\n",
            parm->cb_size);
      if (!(parm->pp_tech == GLP_PP_NONE ||
            parm->pp_tech == GLP_PP_ROOT ||
            parm->pp_tech == GLP_PP_ALL))
         xerror("glp_intopt: pp_tech = %d; invalid parameter\n",
            parm->pp_tech);
      if (parm->mip_gap < 0.0)
         xerror("glp_intopt: mip_gap = %g; invalid parameter\n",
            parm->mip_gap);
      if (!(parm->mir_cuts == GLP_ON || parm->mir_cuts == GLP_OFF))
         xerror("glp_intopt: mir_cuts = %d; invalid parameter\n",
            parm->mir_cuts);
      if (!(parm->gmi_cuts == GLP_ON || parm->gmi_cuts == GLP_OFF))
         xerror("glp_intopt: gmi_cuts = %d; invalid parameter\n",
            parm->gmi_cuts);
      if (!(parm->cov_cuts == GLP_ON || parm->cov_cuts == GLP_OFF))
         xerror("glp_intopt: cov_cuts = %d; invalid parameter\n",
            parm->cov_cuts);
      if (!(parm->clq_cuts == GLP_ON || parm->clq_cuts == GLP_OFF))
         xerror("glp_intopt: clq_cuts = %d; invalid parameter\n",
            parm->clq_cuts);
      if (!(parm->presolve == GLP_ON || parm->presolve == GLP_OFF))
         xerror("glp_intopt: presolve = %d; invalid parameter\n",
            parm->presolve);
      if (!(parm->binarize == GLP_ON || parm->binarize == GLP_OFF))
         xerror("glp_intopt: binarize = %d; invalid parameter\n",
            parm->binarize);
      /* integer solution is currently undefined */
      mip->mip_stat = GLP_UNDEF;
      mip->mip_obj = 0.0;
      /* check bounds of double-bounded variables */
      for (i = 1; i <= m; i++)
      {  GLPROW *row = mip->row[i];
         if (row->type == GLP_DB && row->lb >= row->ub)
         {  if (parm->msg_lev >= GLP_MSG_ERR)
               xprintf("glp_intopt: row %d: lb = %g, ub = %g; incorrect"
                  " bounds\n", i, row->lb, row->ub);
            ret = GLP_EBOUND;
            goto done;
         }
      }
      for (j = 1; j <= n; j++)
      {  GLPCOL *col = mip->col[j];
         if (col->type == GLP_DB && col->lb >= col->ub)
         {  if (parm->msg_lev >= GLP_MSG_ERR)
               xprintf("glp_intopt: column %d: lb = %g, ub = %g; incorr"
                  "ect bounds\n", j, col->lb, col->ub);
            ret = GLP_EBOUND;
            goto done;
         }
      }
      /* bounds of all integer variables must be integral */
      for (j = 1; j <= n; j++)
      {  GLPCOL *col = mip->col[j];
         if (col->kind != GLP_IV) continue;
         if (col->type == GLP_LO || col->type == GLP_DB)
         {  if (col->lb != floor(col->lb))
            {  if (parm->msg_lev >= GLP_MSG_ERR)
                  xprintf("glp_intopt: integer column %d has non-intege"
                     "r lower bound %g\n", j, col->lb);
               ret = GLP_EBOUND;
               goto done;
            }
         }
         if (col->type == GLP_UP || col->type == GLP_DB)
         {  if (col->ub != floor(col->ub))
            {  if (parm->msg_lev >= GLP_MSG_ERR)
                  xprintf("glp_intopt: integer column %d has non-intege"
                     "r upper bound %g\n", j, col->ub);
               ret = GLP_EBOUND;
               goto done;
            }
         }
         if (col->type == GLP_FX)
         {  if (col->lb != floor(col->lb))
            {  if (parm->msg_lev >= GLP_MSG_ERR)
                  xprintf("glp_intopt: integer column %d has non-intege"
                     "r fixed value %g\n", j, col->lb);
               ret = GLP_EBOUND;
               goto done;
            }
         }
      }
      /* solve MIP problem */
      if (!parm->presolve)
         ret = driver1(mip, parm);
      else
         ret = driver2(mip, parm);
done: /* return to the application program */
      return ret;
}

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

void glp_init_iocp(glp_iocp *parm)
{     parm->msg_lev = GLP_MSG_ALL;
      parm->br_tech = GLP_BR_DTH;
      parm->bt_tech = GLP_BT_BLB;
      parm->tol_int = 1e-5;
      parm->tol_obj = 1e-7;
      parm->tm_lim = INT_MAX;
      parm->out_frq = 5000;
      parm->out_dly = 10000;
      parm->cb_func = NULL;
      parm->cb_info = NULL;
      parm->cb_size = 0;
      parm->pp_tech = GLP_PP_ALL;
      parm->mip_gap = 0.0;
      parm->mir_cuts = GLP_OFF;
      parm->gmi_cuts = GLP_OFF;
      parm->cov_cuts = GLP_OFF;
      parm->clq_cuts = GLP_OFF;
      parm->presolve = GLP_OFF;
      parm->binarize = GLP_OFF;
      parm->fn_sol = NULL;
      return;
}

/***********************************************************************
*  NAME
*
*  glp_mip_status - retrieve status of MIP solution
*
*  SYNOPSIS
*
*  int glp_mip_status(glp_prob *mip);
*
*  RETURNS
*
*  The routine lpx_mip_status reports the status of MIP solution found
*  by the branch-and-bound solver as follows:
*
*  GLP_UNDEF  - MIP solution is undefined;
*  GLP_OPT    - MIP solution is integer optimal;
*  GLP_FEAS   - MIP solution is integer feasible but its optimality
*               (or non-optimality) has not been proven, perhaps due to
*               premature termination of the search;
*  GLP_NOFEAS - problem has no integer feasible solution (proven by the
*               solver). */

int glp_mip_status(glp_prob *mip)
{     int mip_stat = mip->mip_stat;
      return mip_stat;
}

/***********************************************************************
*  NAME
*
*  glp_mip_obj_val - retrieve objective value (MIP solution)
*
*  SYNOPSIS
*
*  double glp_mip_obj_val(glp_prob *mip);
*
*  RETURNS
*
*  The routine glp_mip_obj_val returns value of the objective function
*  for MIP solution. */

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

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

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

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

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

/* eof */