alpar@1: /* glpapi09.c (mixed integer programming routines) */
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@1: *
alpar@1: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@1: *  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@1: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@1: *  E-mail: <mao@gnu.org>.
alpar@1: *
alpar@1: *  GLPK is free software: you can redistribute it and/or modify it
alpar@1: *  under the terms of the GNU General Public License as published by
alpar@1: *  the Free Software Foundation, either version 3 of the License, or
alpar@1: *  (at your option) any later version.
alpar@1: *
alpar@1: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@1: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@1: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@1: *  License for more details.
alpar@1: *
alpar@1: *  You should have received a copy of the GNU General Public License
alpar@1: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: #include "glpios.h"
alpar@1: #include "glpnpp.h"
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_set_col_kind - set (change) column kind
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  void glp_set_col_kind(glp_prob *mip, int j, int kind);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine glp_set_col_kind sets (changes) the kind of j-th column
alpar@1: *  (structural variable) as specified by the parameter kind:
alpar@1: *
alpar@1: *  GLP_CV - continuous variable;
alpar@1: *  GLP_IV - integer variable;
alpar@1: *  GLP_BV - binary variable. */
alpar@1: 
alpar@1: void glp_set_col_kind(glp_prob *mip, int j, int kind)
alpar@1: {     GLPCOL *col;
alpar@1:       if (!(1 <= j && j <= mip->n))
alpar@1:          xerror("glp_set_col_kind: j = %d; column number out of range\n"
alpar@1:             , j);
alpar@1:       col = mip->col[j];
alpar@1:       switch (kind)
alpar@1:       {  case GLP_CV:
alpar@1:             col->kind = GLP_CV;
alpar@1:             break;
alpar@1:          case GLP_IV:
alpar@1:             col->kind = GLP_IV;
alpar@1:             break;
alpar@1:          case GLP_BV:
alpar@1:             col->kind = GLP_IV;
alpar@1:             if (!(col->type == GLP_DB && col->lb == 0.0 && col->ub ==
alpar@1:                1.0)) glp_set_col_bnds(mip, j, GLP_DB, 0.0, 1.0);
alpar@1:             break;
alpar@1:          default:
alpar@1:             xerror("glp_set_col_kind: j = %d; kind = %d; invalid column"
alpar@1:                " kind\n", j, kind);
alpar@1:       }
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_get_col_kind - retrieve column kind
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  int glp_get_col_kind(glp_prob *mip, int j);
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine glp_get_col_kind returns the kind of j-th column, i.e.
alpar@1: *  the kind of corresponding structural variable, as follows:
alpar@1: *
alpar@1: *  GLP_CV - continuous variable;
alpar@1: *  GLP_IV - integer variable;
alpar@1: *  GLP_BV - binary variable */
alpar@1: 
alpar@1: int glp_get_col_kind(glp_prob *mip, int j)
alpar@1: {     GLPCOL *col;
alpar@1:       int kind;
alpar@1:       if (!(1 <= j && j <= mip->n))
alpar@1:          xerror("glp_get_col_kind: j = %d; column number out of range\n"
alpar@1:             , j);
alpar@1:       col = mip->col[j];
alpar@1:       kind = col->kind;
alpar@1:       switch (kind)
alpar@1:       {  case GLP_CV:
alpar@1:             break;
alpar@1:          case GLP_IV:
alpar@1:             if (col->type == GLP_DB && col->lb == 0.0 && col->ub == 1.0)
alpar@1:                kind = GLP_BV;
alpar@1:             break;
alpar@1:          default:
alpar@1:             xassert(kind != kind);
alpar@1:       }
alpar@1:       return kind;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_get_num_int - retrieve number of integer columns
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  int glp_get_num_int(glp_prob *mip);
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine glp_get_num_int returns the current number of columns,
alpar@1: *  which are marked as integer. */
alpar@1: 
alpar@1: int glp_get_num_int(glp_prob *mip)
alpar@1: {     GLPCOL *col;
alpar@1:       int j, count = 0;
alpar@1:       for (j = 1; j <= mip->n; j++)
alpar@1:       {  col = mip->col[j];
alpar@1:          if (col->kind == GLP_IV) count++;
alpar@1:       }
alpar@1:       return count;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_get_num_bin - retrieve number of binary columns
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  int glp_get_num_bin(glp_prob *mip);
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine glp_get_num_bin returns the current number of columns,
alpar@1: *  which are marked as binary. */
alpar@1: 
alpar@1: int glp_get_num_bin(glp_prob *mip)
alpar@1: {     GLPCOL *col;
alpar@1:       int j, count = 0;
alpar@1:       for (j = 1; j <= mip->n; j++)
alpar@1:       {  col = mip->col[j];
alpar@1:          if (col->kind == GLP_IV && col->type == GLP_DB && col->lb ==
alpar@1:             0.0 && col->ub == 1.0) count++;
alpar@1:       }
alpar@1:       return count;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_intopt - solve MIP problem with the branch-and-bound method
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  int glp_intopt(glp_prob *P, const glp_iocp *parm);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine glp_intopt is a driver to the MIP solver based on the
alpar@1: *  branch-and-bound method.
alpar@1: *
alpar@1: *  On entry the problem object should contain optimal solution to LP
alpar@1: *  relaxation (which can be obtained with the routine glp_simplex).
alpar@1: *
alpar@1: *  The MIP solver has a set of control parameters. Values of the control
alpar@1: *  parameters can be passed in a structure glp_iocp, which the parameter
alpar@1: *  parm points to.
alpar@1: *
alpar@1: *  The parameter parm can be specified as NULL, in which case the MIP
alpar@1: *  solver uses default settings.
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  0  The MIP problem instance has been successfully solved. This code
alpar@1: *     does not necessarily mean that the solver has found optimal
alpar@1: *     solution. It only means that the solution process was successful.
alpar@1: *
alpar@1: *  GLP_EBOUND
alpar@1: *     Unable to start the search, because some double-bounded variables
alpar@1: *     have incorrect bounds or some integer variables have non-integer
alpar@1: *     (fractional) bounds.
alpar@1: *
alpar@1: *  GLP_EROOT
alpar@1: *     Unable to start the search, because optimal basis for initial LP
alpar@1: *     relaxation is not provided.
alpar@1: *
alpar@1: *  GLP_EFAIL
alpar@1: *     The search was prematurely terminated due to the solver failure.
alpar@1: *
alpar@1: *  GLP_EMIPGAP
alpar@1: *     The search was prematurely terminated, because the relative mip
alpar@1: *     gap tolerance has been reached.
alpar@1: *
alpar@1: *  GLP_ETMLIM
alpar@1: *     The search was prematurely terminated, because the time limit has
alpar@1: *     been exceeded.
alpar@1: *
alpar@1: *  GLP_ENOPFS
alpar@1: *     The MIP problem instance has no primal feasible solution (only if
alpar@1: *     the MIP presolver is used).
alpar@1: *
alpar@1: *  GLP_ENODFS
alpar@1: *     LP relaxation of the MIP problem instance has no dual feasible
alpar@1: *     solution (only if the MIP presolver is used).
alpar@1: *
alpar@1: *  GLP_ESTOP
alpar@1: *     The search was prematurely terminated by application. */
alpar@1: 
alpar@1: static int solve_mip(glp_prob *P, const glp_iocp *parm)
alpar@1: {     /* solve MIP directly without using the preprocessor */
alpar@1:       glp_tree *T;
alpar@1:       int ret;
alpar@1:       /* optimal basis to LP relaxation must be provided */
alpar@1:       if (glp_get_status(P) != GLP_OPT)
alpar@1:       {  if (parm->msg_lev >= GLP_MSG_ERR)
alpar@1:             xprintf("glp_intopt: optimal basis to initial LP relaxation"
alpar@1:                " not provided\n");
alpar@1:          ret = GLP_EROOT;
alpar@1:          goto done;
alpar@1:       }
alpar@1:       /* it seems all is ok */
alpar@1:       if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:          xprintf("Integer optimization begins...\n");
alpar@1:       /* create the branch-and-bound tree */
alpar@1:       T = ios_create_tree(P, parm);
alpar@1:       /* solve the problem instance */
alpar@1:       ret = ios_driver(T);
alpar@1:       /* delete the branch-and-bound tree */
alpar@1:       ios_delete_tree(T);
alpar@1:       /* analyze exit code reported by the mip driver */
alpar@1:       if (ret == 0)
alpar@1:       {  if (P->mip_stat == GLP_FEAS)
alpar@1:          {  if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:                xprintf("INTEGER OPTIMAL SOLUTION FOUND\n");
alpar@1:             P->mip_stat = GLP_OPT;
alpar@1:          }
alpar@1:          else
alpar@1:          {  if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:                xprintf("PROBLEM HAS NO INTEGER FEASIBLE SOLUTION\n");
alpar@1:             P->mip_stat = GLP_NOFEAS;
alpar@1:          }
alpar@1:       }
alpar@1:       else if (ret == GLP_EMIPGAP)
alpar@1:       {  if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:             xprintf("RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINA"
alpar@1:                "TED\n");
alpar@1:       }
alpar@1:       else if (ret == GLP_ETMLIM)
alpar@1:       {  if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:             xprintf("TIME LIMIT EXCEEDED; SEARCH TERMINATED\n");
alpar@1:       }
alpar@1:       else if (ret == GLP_EFAIL)
alpar@1:       {  if (parm->msg_lev >= GLP_MSG_ERR)
alpar@1:             xprintf("glp_intopt: cannot solve current LP relaxation\n");
alpar@1:       }
alpar@1:       else if (ret == GLP_ESTOP)
alpar@1:       {  if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:             xprintf("SEARCH TERMINATED BY APPLICATION\n");
alpar@1:       }
alpar@1:       else
alpar@1:          xassert(ret != ret);
alpar@1: done: return ret;
alpar@1: }
alpar@1: 
alpar@1: static int preprocess_and_solve_mip(glp_prob *P, const glp_iocp *parm)
alpar@1: {     /* solve MIP using the preprocessor */
alpar@1:       ENV *env = get_env_ptr();
alpar@1:       int term_out = env->term_out;
alpar@1:       NPP *npp;
alpar@1:       glp_prob *mip = NULL;
alpar@1:       glp_bfcp bfcp;
alpar@1:       glp_smcp smcp;
alpar@1:       int ret;
alpar@1:       if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:          xprintf("Preprocessing...\n");
alpar@1:       /* create preprocessor workspace */
alpar@1:       npp = npp_create_wksp();
alpar@1:       /* load original problem into the preprocessor workspace */
alpar@1:       npp_load_prob(npp, P, GLP_OFF, GLP_MIP, GLP_OFF);
alpar@1:       /* process MIP prior to applying the branch-and-bound method */
alpar@1:       if (!term_out || parm->msg_lev < GLP_MSG_ALL)
alpar@1:          env->term_out = GLP_OFF;
alpar@1:       else
alpar@1:          env->term_out = GLP_ON;
alpar@1:       ret = npp_integer(npp, parm);
alpar@1:       env->term_out = term_out;
alpar@1:       if (ret == 0)
alpar@1:          ;
alpar@1:       else if (ret == GLP_ENOPFS)
alpar@1:       {  if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:             xprintf("PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION\n");
alpar@1:       }
alpar@1:       else if (ret == GLP_ENODFS)
alpar@1:       {  if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:             xprintf("LP RELAXATION HAS NO DUAL FEASIBLE SOLUTION\n");
alpar@1:       }
alpar@1:       else
alpar@1:          xassert(ret != ret);
alpar@1:       if (ret != 0) goto done;
alpar@1:       /* build transformed MIP */
alpar@1:       mip = glp_create_prob();
alpar@1:       npp_build_prob(npp, mip);
alpar@1:       /* if the transformed MIP is empty, it has empty solution, which
alpar@1:          is optimal */
alpar@1:       if (mip->m == 0 && mip->n == 0)
alpar@1:       {  mip->mip_stat = GLP_OPT;
alpar@1:          mip->mip_obj = mip->c0;
alpar@1:          if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:          {  xprintf("Objective value = %17.9e\n", mip->mip_obj);
alpar@1:             xprintf("INTEGER OPTIMAL SOLUTION FOUND BY MIP PREPROCESSOR"
alpar@1:                "\n");
alpar@1:          }
alpar@1:          goto post;
alpar@1:       }
alpar@1:       /* display some statistics */
alpar@1:       if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:       {  int ni = glp_get_num_int(mip);
alpar@1:          int nb = glp_get_num_bin(mip);
alpar@1:          char s[50];
alpar@1:          xprintf("%d row%s, %d column%s, %d non-zero%s\n",
alpar@1:             mip->m, mip->m == 1 ? "" : "s", mip->n, mip->n == 1 ? "" :
alpar@1:             "s", mip->nnz, mip->nnz == 1 ? "" : "s");
alpar@1:          if (nb == 0)
alpar@1:             strcpy(s, "none of");
alpar@1:          else if (ni == 1 && nb == 1)
alpar@1:             strcpy(s, "");
alpar@1:          else if (nb == 1)
alpar@1:             strcpy(s, "one of");
alpar@1:          else if (nb == ni)
alpar@1:             strcpy(s, "all of");
alpar@1:          else
alpar@1:             sprintf(s, "%d of", nb);
alpar@1:          xprintf("%d integer variable%s, %s which %s binary\n",
alpar@1:             ni, ni == 1 ? "" : "s", s, nb == 1 ? "is" : "are");
alpar@1:       }
alpar@1:       /* inherit basis factorization control parameters */
alpar@1:       glp_get_bfcp(P, &bfcp);
alpar@1:       glp_set_bfcp(mip, &bfcp);
alpar@1:       /* scale the transformed problem */
alpar@1:       if (!term_out || parm->msg_lev < GLP_MSG_ALL)
alpar@1:          env->term_out = GLP_OFF;
alpar@1:       else
alpar@1:          env->term_out = GLP_ON;
alpar@1:       glp_scale_prob(mip,
alpar@1:          GLP_SF_GM | GLP_SF_EQ | GLP_SF_2N | GLP_SF_SKIP);
alpar@1:       env->term_out = term_out;
alpar@1:       /* build advanced initial basis */
alpar@1:       if (!term_out || parm->msg_lev < GLP_MSG_ALL)
alpar@1:          env->term_out = GLP_OFF;
alpar@1:       else
alpar@1:          env->term_out = GLP_ON;
alpar@1:       glp_adv_basis(mip, 0);
alpar@1:       env->term_out = term_out;
alpar@1:       /* solve initial LP relaxation */
alpar@1:       if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:          xprintf("Solving LP relaxation...\n");
alpar@1:       glp_init_smcp(&smcp);
alpar@1:       smcp.msg_lev = parm->msg_lev;
alpar@1:       mip->it_cnt = P->it_cnt;
alpar@1:       ret = glp_simplex(mip, &smcp);
alpar@1:       P->it_cnt = mip->it_cnt;
alpar@1:       if (ret != 0)
alpar@1:       {  if (parm->msg_lev >= GLP_MSG_ERR)
alpar@1:             xprintf("glp_intopt: cannot solve LP relaxation\n");
alpar@1:          ret = GLP_EFAIL;
alpar@1:          goto done;
alpar@1:       }
alpar@1:       /* check status of the basic solution */
alpar@1:       ret = glp_get_status(mip);
alpar@1:       if (ret == GLP_OPT)
alpar@1:          ret = 0;
alpar@1:       else if (ret == GLP_NOFEAS)
alpar@1:          ret = GLP_ENOPFS;
alpar@1:       else if (ret == GLP_UNBND)
alpar@1:          ret = GLP_ENODFS;
alpar@1:       else
alpar@1:          xassert(ret != ret);
alpar@1:       if (ret != 0) goto done;
alpar@1:       /* solve the transformed MIP */
alpar@1:       mip->it_cnt = P->it_cnt;
alpar@1:       ret = solve_mip(mip, parm);
alpar@1:       P->it_cnt = mip->it_cnt;
alpar@1:       /* only integer feasible solution can be postprocessed */
alpar@1:       if (!(mip->mip_stat == GLP_OPT || mip->mip_stat == GLP_FEAS))
alpar@1:       {  P->mip_stat = mip->mip_stat;
alpar@1:          goto done;
alpar@1:       }
alpar@1:       /* postprocess solution from the transformed MIP */
alpar@1: post: npp_postprocess(npp, mip);
alpar@1:       /* the transformed MIP is no longer needed */
alpar@1:       glp_delete_prob(mip), mip = NULL;
alpar@1:       /* store solution to the original problem */
alpar@1:       npp_unload_sol(npp, P);
alpar@1: done: /* delete the transformed MIP, if it exists */
alpar@1:       if (mip != NULL) glp_delete_prob(mip);
alpar@1:       /* delete preprocessor workspace */
alpar@1:       npp_delete_wksp(npp);
alpar@1:       return ret;
alpar@1: }
alpar@1: 
alpar@1: #ifndef HAVE_ALIEN_SOLVER /* 28/V-2010 */
alpar@1: int _glp_intopt1(glp_prob *P, const glp_iocp *parm)
alpar@1: {     xassert(P == P);
alpar@1:       xassert(parm == parm);
alpar@1:       xprintf("glp_intopt: no alien solver is available\n");
alpar@1:       return GLP_EFAIL;
alpar@1: }
alpar@1: #endif
alpar@1: 
alpar@1: int glp_intopt(glp_prob *P, const glp_iocp *parm)
alpar@1: {     /* solve MIP problem with the branch-and-bound method */
alpar@1:       glp_iocp _parm;
alpar@1:       int i, j, ret;
alpar@1:       /* check problem object */
alpar@1:       if (P == NULL || P->magic != GLP_PROB_MAGIC)
alpar@1:          xerror("glp_intopt: P = %p; invalid problem object\n", P);
alpar@1:       if (P->tree != NULL)
alpar@1:          xerror("glp_intopt: operation not allowed\n");
alpar@1:       /* check control parameters */
alpar@1:       if (parm == NULL)
alpar@1:          parm = &_parm, glp_init_iocp((glp_iocp *)parm);
alpar@1:       if (!(parm->msg_lev == GLP_MSG_OFF ||
alpar@1:             parm->msg_lev == GLP_MSG_ERR ||
alpar@1:             parm->msg_lev == GLP_MSG_ON  ||
alpar@1:             parm->msg_lev == GLP_MSG_ALL ||
alpar@1:             parm->msg_lev == GLP_MSG_DBG))
alpar@1:          xerror("glp_intopt: msg_lev = %d; invalid parameter\n",
alpar@1:             parm->msg_lev);
alpar@1:       if (!(parm->br_tech == GLP_BR_FFV ||
alpar@1:             parm->br_tech == GLP_BR_LFV ||
alpar@1:             parm->br_tech == GLP_BR_MFV ||
alpar@1:             parm->br_tech == GLP_BR_DTH ||
alpar@1:             parm->br_tech == GLP_BR_PCH))
alpar@1:          xerror("glp_intopt: br_tech = %d; invalid parameter\n",
alpar@1:             parm->br_tech);
alpar@1:       if (!(parm->bt_tech == GLP_BT_DFS ||
alpar@1:             parm->bt_tech == GLP_BT_BFS ||
alpar@1:             parm->bt_tech == GLP_BT_BLB ||
alpar@1:             parm->bt_tech == GLP_BT_BPH))
alpar@1:          xerror("glp_intopt: bt_tech = %d; invalid parameter\n",
alpar@1:             parm->bt_tech);
alpar@1:       if (!(0.0 < parm->tol_int && parm->tol_int < 1.0))
alpar@1:          xerror("glp_intopt: tol_int = %g; invalid parameter\n",
alpar@1:             parm->tol_int);
alpar@1:       if (!(0.0 < parm->tol_obj && parm->tol_obj < 1.0))
alpar@1:          xerror("glp_intopt: tol_obj = %g; invalid parameter\n",
alpar@1:             parm->tol_obj);
alpar@1:       if (parm->tm_lim < 0)
alpar@1:          xerror("glp_intopt: tm_lim = %d; invalid parameter\n",
alpar@1:             parm->tm_lim);
alpar@1:       if (parm->out_frq < 0)
alpar@1:          xerror("glp_intopt: out_frq = %d; invalid parameter\n",
alpar@1:             parm->out_frq);
alpar@1:       if (parm->out_dly < 0)
alpar@1:          xerror("glp_intopt: out_dly = %d; invalid parameter\n",
alpar@1:             parm->out_dly);
alpar@1:       if (!(0 <= parm->cb_size && parm->cb_size <= 256))
alpar@1:          xerror("glp_intopt: cb_size = %d; invalid parameter\n",
alpar@1:             parm->cb_size);
alpar@1:       if (!(parm->pp_tech == GLP_PP_NONE ||
alpar@1:             parm->pp_tech == GLP_PP_ROOT ||
alpar@1:             parm->pp_tech == GLP_PP_ALL))
alpar@1:          xerror("glp_intopt: pp_tech = %d; invalid parameter\n",
alpar@1:             parm->pp_tech);
alpar@1:       if (parm->mip_gap < 0.0)
alpar@1:          xerror("glp_intopt: mip_gap = %g; invalid parameter\n",
alpar@1:             parm->mip_gap);
alpar@1:       if (!(parm->mir_cuts == GLP_ON || parm->mir_cuts == GLP_OFF))
alpar@1:          xerror("glp_intopt: mir_cuts = %d; invalid parameter\n",
alpar@1:             parm->mir_cuts);
alpar@1:       if (!(parm->gmi_cuts == GLP_ON || parm->gmi_cuts == GLP_OFF))
alpar@1:          xerror("glp_intopt: gmi_cuts = %d; invalid parameter\n",
alpar@1:             parm->gmi_cuts);
alpar@1:       if (!(parm->cov_cuts == GLP_ON || parm->cov_cuts == GLP_OFF))
alpar@1:          xerror("glp_intopt: cov_cuts = %d; invalid parameter\n",
alpar@1:             parm->cov_cuts);
alpar@1:       if (!(parm->clq_cuts == GLP_ON || parm->clq_cuts == GLP_OFF))
alpar@1:          xerror("glp_intopt: clq_cuts = %d; invalid parameter\n",
alpar@1:             parm->clq_cuts);
alpar@1:       if (!(parm->presolve == GLP_ON || parm->presolve == GLP_OFF))
alpar@1:          xerror("glp_intopt: presolve = %d; invalid parameter\n",
alpar@1:             parm->presolve);
alpar@1:       if (!(parm->binarize == GLP_ON || parm->binarize == GLP_OFF))
alpar@1:          xerror("glp_intopt: binarize = %d; invalid parameter\n",
alpar@1:             parm->binarize);
alpar@1:       if (!(parm->fp_heur == GLP_ON || parm->fp_heur == GLP_OFF))
alpar@1:          xerror("glp_intopt: fp_heur = %d; invalid parameter\n",
alpar@1:             parm->fp_heur);
alpar@1: #if 1 /* 28/V-2010 */
alpar@1:       if (!(parm->alien == GLP_ON || parm->alien == GLP_OFF))
alpar@1:          xerror("glp_intopt: alien = %d; invalid parameter\n",
alpar@1:             parm->alien);
alpar@1: #endif
alpar@1:       /* integer solution is currently undefined */
alpar@1:       P->mip_stat = GLP_UNDEF;
alpar@1:       P->mip_obj = 0.0;
alpar@1:       /* check bounds of double-bounded variables */
alpar@1:       for (i = 1; i <= P->m; i++)
alpar@1:       {  GLPROW *row = P->row[i];
alpar@1:          if (row->type == GLP_DB && row->lb >= row->ub)
alpar@1:          {  if (parm->msg_lev >= GLP_MSG_ERR)
alpar@1:                xprintf("glp_intopt: row %d: lb = %g, ub = %g; incorrect"
alpar@1:                   " bounds\n", i, row->lb, row->ub);
alpar@1:             ret = GLP_EBOUND;
alpar@1:             goto done;
alpar@1:          }
alpar@1:       }
alpar@1:       for (j = 1; j <= P->n; j++)
alpar@1:       {  GLPCOL *col = P->col[j];
alpar@1:          if (col->type == GLP_DB && col->lb >= col->ub)
alpar@1:          {  if (parm->msg_lev >= GLP_MSG_ERR)
alpar@1:                xprintf("glp_intopt: column %d: lb = %g, ub = %g; incorr"
alpar@1:                   "ect bounds\n", j, col->lb, col->ub);
alpar@1:             ret = GLP_EBOUND;
alpar@1:             goto done;
alpar@1:          }
alpar@1:       }
alpar@1:       /* bounds of all integer variables must be integral */
alpar@1:       for (j = 1; j <= P->n; j++)
alpar@1:       {  GLPCOL *col = P->col[j];
alpar@1:          if (col->kind != GLP_IV) continue;
alpar@1:          if (col->type == GLP_LO || col->type == GLP_DB)
alpar@1:          {  if (col->lb != floor(col->lb))
alpar@1:             {  if (parm->msg_lev >= GLP_MSG_ERR)
alpar@1:                   xprintf("glp_intopt: integer column %d has non-intege"
alpar@1:                      "r lower bound %g\n", j, col->lb);
alpar@1:                ret = GLP_EBOUND;
alpar@1:                goto done;
alpar@1:             }
alpar@1:          }
alpar@1:          if (col->type == GLP_UP || col->type == GLP_DB)
alpar@1:          {  if (col->ub != floor(col->ub))
alpar@1:             {  if (parm->msg_lev >= GLP_MSG_ERR)
alpar@1:                   xprintf("glp_intopt: integer column %d has non-intege"
alpar@1:                      "r upper bound %g\n", j, col->ub);
alpar@1:                ret = GLP_EBOUND;
alpar@1:                goto done;
alpar@1:             }
alpar@1:          }
alpar@1:          if (col->type == GLP_FX)
alpar@1:          {  if (col->lb != floor(col->lb))
alpar@1:             {  if (parm->msg_lev >= GLP_MSG_ERR)
alpar@1:                   xprintf("glp_intopt: integer column %d has non-intege"
alpar@1:                      "r fixed value %g\n", j, col->lb);
alpar@1:                ret = GLP_EBOUND;
alpar@1:                goto done;
alpar@1:             }
alpar@1:          }
alpar@1:       }
alpar@1:       /* solve MIP problem */
alpar@1:       if (parm->msg_lev >= GLP_MSG_ALL)
alpar@1:       {  int ni = glp_get_num_int(P);
alpar@1:          int nb = glp_get_num_bin(P);
alpar@1:          char s[50];
alpar@1:          xprintf("GLPK Integer Optimizer, v%s\n", glp_version());
alpar@1:          xprintf("%d row%s, %d column%s, %d non-zero%s\n",
alpar@1:             P->m, P->m == 1 ? "" : "s", P->n, P->n == 1 ? "" : "s",
alpar@1:             P->nnz, P->nnz == 1 ? "" : "s");
alpar@1:          if (nb == 0)
alpar@1:             strcpy(s, "none of");
alpar@1:          else if (ni == 1 && nb == 1)
alpar@1:             strcpy(s, "");
alpar@1:          else if (nb == 1)
alpar@1:             strcpy(s, "one of");
alpar@1:          else if (nb == ni)
alpar@1:             strcpy(s, "all of");
alpar@1:          else
alpar@1:             sprintf(s, "%d of", nb);
alpar@1:          xprintf("%d integer variable%s, %s which %s binary\n",
alpar@1:             ni, ni == 1 ? "" : "s", s, nb == 1 ? "is" : "are");
alpar@1:       }
alpar@1: #if 1 /* 28/V-2010 */
alpar@1:       if (parm->alien)
alpar@1:       {  /* use alien integer optimizer */
alpar@1:          ret = _glp_intopt1(P, parm);
alpar@1:          goto done;
alpar@1:       }
alpar@1: #endif
alpar@1:       if (!parm->presolve)
alpar@1:          ret = solve_mip(P, parm);
alpar@1:       else
alpar@1:          ret = preprocess_and_solve_mip(P, parm);
alpar@1: done: /* return to the application program */
alpar@1:       return ret;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_init_iocp - initialize integer optimizer control parameters
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  void glp_init_iocp(glp_iocp *parm);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine glp_init_iocp initializes control parameters, which are
alpar@1: *  used by the integer optimizer, with default values.
alpar@1: *
alpar@1: *  Default values of the control parameters are stored in a glp_iocp
alpar@1: *  structure, which the parameter parm points to. */
alpar@1: 
alpar@1: void glp_init_iocp(glp_iocp *parm)
alpar@1: {     parm->msg_lev = GLP_MSG_ALL;
alpar@1:       parm->br_tech = GLP_BR_DTH;
alpar@1:       parm->bt_tech = GLP_BT_BLB;
alpar@1:       parm->tol_int = 1e-5;
alpar@1:       parm->tol_obj = 1e-7;
alpar@1:       parm->tm_lim = INT_MAX;
alpar@1:       parm->out_frq = 5000;
alpar@1:       parm->out_dly = 10000;
alpar@1:       parm->cb_func = NULL;
alpar@1:       parm->cb_info = NULL;
alpar@1:       parm->cb_size = 0;
alpar@1:       parm->pp_tech = GLP_PP_ALL;
alpar@1:       parm->mip_gap = 0.0;
alpar@1:       parm->mir_cuts = GLP_OFF;
alpar@1:       parm->gmi_cuts = GLP_OFF;
alpar@1:       parm->cov_cuts = GLP_OFF;
alpar@1:       parm->clq_cuts = GLP_OFF;
alpar@1:       parm->presolve = GLP_OFF;
alpar@1:       parm->binarize = GLP_OFF;
alpar@1:       parm->fp_heur = GLP_OFF;
alpar@1: #if 1 /* 28/V-2010 */
alpar@1:       parm->alien = GLP_OFF;
alpar@1: #endif
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_mip_status - retrieve status of MIP solution
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  int glp_mip_status(glp_prob *mip);
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine lpx_mip_status reports the status of MIP solution found
alpar@1: *  by the branch-and-bound solver as follows:
alpar@1: *
alpar@1: *  GLP_UNDEF  - MIP solution is undefined;
alpar@1: *  GLP_OPT    - MIP solution is integer optimal;
alpar@1: *  GLP_FEAS   - MIP solution is integer feasible but its optimality
alpar@1: *               (or non-optimality) has not been proven, perhaps due to
alpar@1: *               premature termination of the search;
alpar@1: *  GLP_NOFEAS - problem has no integer feasible solution (proven by the
alpar@1: *               solver). */
alpar@1: 
alpar@1: int glp_mip_status(glp_prob *mip)
alpar@1: {     int mip_stat = mip->mip_stat;
alpar@1:       return mip_stat;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_mip_obj_val - retrieve objective value (MIP solution)
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  double glp_mip_obj_val(glp_prob *mip);
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine glp_mip_obj_val returns value of the objective function
alpar@1: *  for MIP solution. */
alpar@1: 
alpar@1: double glp_mip_obj_val(glp_prob *mip)
alpar@1: {     /*struct LPXCPS *cps = mip->cps;*/
alpar@1:       double z;
alpar@1:       z = mip->mip_obj;
alpar@1:       /*if (cps->round && fabs(z) < 1e-9) z = 0.0;*/
alpar@1:       return z;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_mip_row_val - retrieve row value (MIP solution)
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  double glp_mip_row_val(glp_prob *mip, int i);
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine glp_mip_row_val returns value of the auxiliary variable
alpar@1: *  associated with i-th row. */
alpar@1: 
alpar@1: double glp_mip_row_val(glp_prob *mip, int i)
alpar@1: {     /*struct LPXCPS *cps = mip->cps;*/
alpar@1:       double mipx;
alpar@1:       if (!(1 <= i && i <= mip->m))
alpar@1:          xerror("glp_mip_row_val: i = %d; row number out of range\n", i)
alpar@1:             ;
alpar@1:       mipx = mip->row[i]->mipx;
alpar@1:       /*if (cps->round && fabs(mipx) < 1e-9) mipx = 0.0;*/
alpar@1:       return mipx;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  glp_mip_col_val - retrieve column value (MIP solution)
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  double glp_mip_col_val(glp_prob *mip, int j);
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine glp_mip_col_val returns value of the structural variable
alpar@1: *  associated with j-th column. */
alpar@1: 
alpar@1: double glp_mip_col_val(glp_prob *mip, int j)
alpar@1: {     /*struct LPXCPS *cps = mip->cps;*/
alpar@1:       double mipx;
alpar@1:       if (!(1 <= j && j <= mip->n))
alpar@1:          xerror("glp_mip_col_val: j = %d; column number out of range\n",
alpar@1:             j);
alpar@1:       mipx = mip->col[j]->mipx;
alpar@1:       /*if (cps->round && fabs(mipx) < 1e-9) mipx = 0.0;*/
alpar@1:       return mipx;
alpar@1: }
alpar@1: 
alpar@1: /* eof */