1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glpapi09.c	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,741 @@
     1.4 +/* glpapi09.c (mixed integer programming routines) */
     1.5 +
     1.6 +/***********************************************************************
     1.7 +*  This code is part of GLPK (GNU Linear Programming Kit).
     1.8 +*
     1.9 +*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
    1.10 +*  2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
    1.11 +*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
    1.12 +*  E-mail: <mao@gnu.org>.
    1.13 +*
    1.14 +*  GLPK is free software: you can redistribute it and/or modify it
    1.15 +*  under the terms of the GNU General Public License as published by
    1.16 +*  the Free Software Foundation, either version 3 of the License, or
    1.17 +*  (at your option) any later version.
    1.18 +*
    1.19 +*  GLPK is distributed in the hope that it will be useful, but WITHOUT
    1.20 +*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.21 +*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
    1.22 +*  License for more details.
    1.23 +*
    1.24 +*  You should have received a copy of the GNU General Public License
    1.25 +*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
    1.26 +***********************************************************************/
    1.27 +
    1.28 +#include "glpios.h"
    1.29 +#include "glpnpp.h"
    1.30 +
    1.31 +/***********************************************************************
    1.32 +*  NAME
    1.33 +*
    1.34 +*  glp_set_col_kind - set (change) column kind
    1.35 +*
    1.36 +*  SYNOPSIS
    1.37 +*
    1.38 +*  void glp_set_col_kind(glp_prob *mip, int j, int kind);
    1.39 +*
    1.40 +*  DESCRIPTION
    1.41 +*
    1.42 +*  The routine glp_set_col_kind sets (changes) the kind of j-th column
    1.43 +*  (structural variable) as specified by the parameter kind:
    1.44 +*
    1.45 +*  GLP_CV - continuous variable;
    1.46 +*  GLP_IV - integer variable;
    1.47 +*  GLP_BV - binary variable. */
    1.48 +
    1.49 +void glp_set_col_kind(glp_prob *mip, int j, int kind)
    1.50 +{     GLPCOL *col;
    1.51 +      if (!(1 <= j && j <= mip->n))
    1.52 +         xerror("glp_set_col_kind: j = %d; column number out of range\n"
    1.53 +            , j);
    1.54 +      col = mip->col[j];
    1.55 +      switch (kind)
    1.56 +      {  case GLP_CV:
    1.57 +            col->kind = GLP_CV;
    1.58 +            break;
    1.59 +         case GLP_IV:
    1.60 +            col->kind = GLP_IV;
    1.61 +            break;
    1.62 +         case GLP_BV:
    1.63 +            col->kind = GLP_IV;
    1.64 +            if (!(col->type == GLP_DB && col->lb == 0.0 && col->ub ==
    1.65 +               1.0)) glp_set_col_bnds(mip, j, GLP_DB, 0.0, 1.0);
    1.66 +            break;
    1.67 +         default:
    1.68 +            xerror("glp_set_col_kind: j = %d; kind = %d; invalid column"
    1.69 +               " kind\n", j, kind);
    1.70 +      }
    1.71 +      return;
    1.72 +}
    1.73 +
    1.74 +/***********************************************************************
    1.75 +*  NAME
    1.76 +*
    1.77 +*  glp_get_col_kind - retrieve column kind
    1.78 +*
    1.79 +*  SYNOPSIS
    1.80 +*
    1.81 +*  int glp_get_col_kind(glp_prob *mip, int j);
    1.82 +*
    1.83 +*  RETURNS
    1.84 +*
    1.85 +*  The routine glp_get_col_kind returns the kind of j-th column, i.e.
    1.86 +*  the kind of corresponding structural variable, as follows:
    1.87 +*
    1.88 +*  GLP_CV - continuous variable;
    1.89 +*  GLP_IV - integer variable;
    1.90 +*  GLP_BV - binary variable */
    1.91 +
    1.92 +int glp_get_col_kind(glp_prob *mip, int j)
    1.93 +{     GLPCOL *col;
    1.94 +      int kind;
    1.95 +      if (!(1 <= j && j <= mip->n))
    1.96 +         xerror("glp_get_col_kind: j = %d; column number out of range\n"
    1.97 +            , j);
    1.98 +      col = mip->col[j];
    1.99 +      kind = col->kind;
   1.100 +      switch (kind)
   1.101 +      {  case GLP_CV:
   1.102 +            break;
   1.103 +         case GLP_IV:
   1.104 +            if (col->type == GLP_DB && col->lb == 0.0 && col->ub == 1.0)
   1.105 +               kind = GLP_BV;
   1.106 +            break;
   1.107 +         default:
   1.108 +            xassert(kind != kind);
   1.109 +      }
   1.110 +      return kind;
   1.111 +}
   1.112 +
   1.113 +/***********************************************************************
   1.114 +*  NAME
   1.115 +*
   1.116 +*  glp_get_num_int - retrieve number of integer columns
   1.117 +*
   1.118 +*  SYNOPSIS
   1.119 +*
   1.120 +*  int glp_get_num_int(glp_prob *mip);
   1.121 +*
   1.122 +*  RETURNS
   1.123 +*
   1.124 +*  The routine glp_get_num_int returns the current number of columns,
   1.125 +*  which are marked as integer. */
   1.126 +
   1.127 +int glp_get_num_int(glp_prob *mip)
   1.128 +{     GLPCOL *col;
   1.129 +      int j, count = 0;
   1.130 +      for (j = 1; j <= mip->n; j++)
   1.131 +      {  col = mip->col[j];
   1.132 +         if (col->kind == GLP_IV) count++;
   1.133 +      }
   1.134 +      return count;
   1.135 +}
   1.136 +
   1.137 +/***********************************************************************
   1.138 +*  NAME
   1.139 +*
   1.140 +*  glp_get_num_bin - retrieve number of binary columns
   1.141 +*
   1.142 +*  SYNOPSIS
   1.143 +*
   1.144 +*  int glp_get_num_bin(glp_prob *mip);
   1.145 +*
   1.146 +*  RETURNS
   1.147 +*
   1.148 +*  The routine glp_get_num_bin returns the current number of columns,
   1.149 +*  which are marked as binary. */
   1.150 +
   1.151 +int glp_get_num_bin(glp_prob *mip)
   1.152 +{     GLPCOL *col;
   1.153 +      int j, count = 0;
   1.154 +      for (j = 1; j <= mip->n; j++)
   1.155 +      {  col = mip->col[j];
   1.156 +         if (col->kind == GLP_IV && col->type == GLP_DB && col->lb ==
   1.157 +            0.0 && col->ub == 1.0) count++;
   1.158 +      }
   1.159 +      return count;
   1.160 +}
   1.161 +
   1.162 +/***********************************************************************
   1.163 +*  NAME
   1.164 +*
   1.165 +*  glp_intopt - solve MIP problem with the branch-and-bound method
   1.166 +*
   1.167 +*  SYNOPSIS
   1.168 +*
   1.169 +*  int glp_intopt(glp_prob *P, const glp_iocp *parm);
   1.170 +*
   1.171 +*  DESCRIPTION
   1.172 +*
   1.173 +*  The routine glp_intopt is a driver to the MIP solver based on the
   1.174 +*  branch-and-bound method.
   1.175 +*
   1.176 +*  On entry the problem object should contain optimal solution to LP
   1.177 +*  relaxation (which can be obtained with the routine glp_simplex).
   1.178 +*
   1.179 +*  The MIP solver has a set of control parameters. Values of the control
   1.180 +*  parameters can be passed in a structure glp_iocp, which the parameter
   1.181 +*  parm points to.
   1.182 +*
   1.183 +*  The parameter parm can be specified as NULL, in which case the MIP
   1.184 +*  solver uses default settings.
   1.185 +*
   1.186 +*  RETURNS
   1.187 +*
   1.188 +*  0  The MIP problem instance has been successfully solved. This code
   1.189 +*     does not necessarily mean that the solver has found optimal
   1.190 +*     solution. It only means that the solution process was successful.
   1.191 +*
   1.192 +*  GLP_EBOUND
   1.193 +*     Unable to start the search, because some double-bounded variables
   1.194 +*     have incorrect bounds or some integer variables have non-integer
   1.195 +*     (fractional) bounds.
   1.196 +*
   1.197 +*  GLP_EROOT
   1.198 +*     Unable to start the search, because optimal basis for initial LP
   1.199 +*     relaxation is not provided.
   1.200 +*
   1.201 +*  GLP_EFAIL
   1.202 +*     The search was prematurely terminated due to the solver failure.
   1.203 +*
   1.204 +*  GLP_EMIPGAP
   1.205 +*     The search was prematurely terminated, because the relative mip
   1.206 +*     gap tolerance has been reached.
   1.207 +*
   1.208 +*  GLP_ETMLIM
   1.209 +*     The search was prematurely terminated, because the time limit has
   1.210 +*     been exceeded.
   1.211 +*
   1.212 +*  GLP_ENOPFS
   1.213 +*     The MIP problem instance has no primal feasible solution (only if
   1.214 +*     the MIP presolver is used).
   1.215 +*
   1.216 +*  GLP_ENODFS
   1.217 +*     LP relaxation of the MIP problem instance has no dual feasible
   1.218 +*     solution (only if the MIP presolver is used).
   1.219 +*
   1.220 +*  GLP_ESTOP
   1.221 +*     The search was prematurely terminated by application. */
   1.222 +
   1.223 +static int solve_mip(glp_prob *P, const glp_iocp *parm)
   1.224 +{     /* solve MIP directly without using the preprocessor */
   1.225 +      glp_tree *T;
   1.226 +      int ret;
   1.227 +      /* optimal basis to LP relaxation must be provided */
   1.228 +      if (glp_get_status(P) != GLP_OPT)
   1.229 +      {  if (parm->msg_lev >= GLP_MSG_ERR)
   1.230 +            xprintf("glp_intopt: optimal basis to initial LP relaxation"
   1.231 +               " not provided\n");
   1.232 +         ret = GLP_EROOT;
   1.233 +         goto done;
   1.234 +      }
   1.235 +      /* it seems all is ok */
   1.236 +      if (parm->msg_lev >= GLP_MSG_ALL)
   1.237 +         xprintf("Integer optimization begins...\n");
   1.238 +      /* create the branch-and-bound tree */
   1.239 +      T = ios_create_tree(P, parm);
   1.240 +      /* solve the problem instance */
   1.241 +      ret = ios_driver(T);
   1.242 +      /* delete the branch-and-bound tree */
   1.243 +      ios_delete_tree(T);
   1.244 +      /* analyze exit code reported by the mip driver */
   1.245 +      if (ret == 0)
   1.246 +      {  if (P->mip_stat == GLP_FEAS)
   1.247 +         {  if (parm->msg_lev >= GLP_MSG_ALL)
   1.248 +               xprintf("INTEGER OPTIMAL SOLUTION FOUND\n");
   1.249 +            P->mip_stat = GLP_OPT;
   1.250 +         }
   1.251 +         else
   1.252 +         {  if (parm->msg_lev >= GLP_MSG_ALL)
   1.253 +               xprintf("PROBLEM HAS NO INTEGER FEASIBLE SOLUTION\n");
   1.254 +            P->mip_stat = GLP_NOFEAS;
   1.255 +         }
   1.256 +      }
   1.257 +      else if (ret == GLP_EMIPGAP)
   1.258 +      {  if (parm->msg_lev >= GLP_MSG_ALL)
   1.259 +            xprintf("RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINA"
   1.260 +               "TED\n");
   1.261 +      }
   1.262 +      else if (ret == GLP_ETMLIM)
   1.263 +      {  if (parm->msg_lev >= GLP_MSG_ALL)
   1.264 +            xprintf("TIME LIMIT EXCEEDED; SEARCH TERMINATED\n");
   1.265 +      }
   1.266 +      else if (ret == GLP_EFAIL)
   1.267 +      {  if (parm->msg_lev >= GLP_MSG_ERR)
   1.268 +            xprintf("glp_intopt: cannot solve current LP relaxation\n");
   1.269 +      }
   1.270 +      else if (ret == GLP_ESTOP)
   1.271 +      {  if (parm->msg_lev >= GLP_MSG_ALL)
   1.272 +            xprintf("SEARCH TERMINATED BY APPLICATION\n");
   1.273 +      }
   1.274 +      else
   1.275 +         xassert(ret != ret);
   1.276 +done: return ret;
   1.277 +}
   1.278 +
   1.279 +static int preprocess_and_solve_mip(glp_prob *P, const glp_iocp *parm)
   1.280 +{     /* solve MIP using the preprocessor */
   1.281 +      ENV *env = get_env_ptr();
   1.282 +      int term_out = env->term_out;
   1.283 +      NPP *npp;
   1.284 +      glp_prob *mip = NULL;
   1.285 +      glp_bfcp bfcp;
   1.286 +      glp_smcp smcp;
   1.287 +      int ret;
   1.288 +      if (parm->msg_lev >= GLP_MSG_ALL)
   1.289 +         xprintf("Preprocessing...\n");
   1.290 +      /* create preprocessor workspace */
   1.291 +      npp = npp_create_wksp();
   1.292 +      /* load original problem into the preprocessor workspace */
   1.293 +      npp_load_prob(npp, P, GLP_OFF, GLP_MIP, GLP_OFF);
   1.294 +      /* process MIP prior to applying the branch-and-bound method */
   1.295 +      if (!term_out || parm->msg_lev < GLP_MSG_ALL)
   1.296 +         env->term_out = GLP_OFF;
   1.297 +      else
   1.298 +         env->term_out = GLP_ON;
   1.299 +      ret = npp_integer(npp, parm);
   1.300 +      env->term_out = term_out;
   1.301 +      if (ret == 0)
   1.302 +         ;
   1.303 +      else if (ret == GLP_ENOPFS)
   1.304 +      {  if (parm->msg_lev >= GLP_MSG_ALL)
   1.305 +            xprintf("PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION\n");
   1.306 +      }
   1.307 +      else if (ret == GLP_ENODFS)
   1.308 +      {  if (parm->msg_lev >= GLP_MSG_ALL)
   1.309 +            xprintf("LP RELAXATION HAS NO DUAL FEASIBLE SOLUTION\n");
   1.310 +      }
   1.311 +      else
   1.312 +         xassert(ret != ret);
   1.313 +      if (ret != 0) goto done;
   1.314 +      /* build transformed MIP */
   1.315 +      mip = glp_create_prob();
   1.316 +      npp_build_prob(npp, mip);
   1.317 +      /* if the transformed MIP is empty, it has empty solution, which
   1.318 +         is optimal */
   1.319 +      if (mip->m == 0 && mip->n == 0)
   1.320 +      {  mip->mip_stat = GLP_OPT;
   1.321 +         mip->mip_obj = mip->c0;
   1.322 +         if (parm->msg_lev >= GLP_MSG_ALL)
   1.323 +         {  xprintf("Objective value = %17.9e\n", mip->mip_obj);
   1.324 +            xprintf("INTEGER OPTIMAL SOLUTION FOUND BY MIP PREPROCESSOR"
   1.325 +               "\n");
   1.326 +         }
   1.327 +         goto post;
   1.328 +      }
   1.329 +      /* display some statistics */
   1.330 +      if (parm->msg_lev >= GLP_MSG_ALL)
   1.331 +      {  int ni = glp_get_num_int(mip);
   1.332 +         int nb = glp_get_num_bin(mip);
   1.333 +         char s[50];
   1.334 +         xprintf("%d row%s, %d column%s, %d non-zero%s\n",
   1.335 +            mip->m, mip->m == 1 ? "" : "s", mip->n, mip->n == 1 ? "" :
   1.336 +            "s", mip->nnz, mip->nnz == 1 ? "" : "s");
   1.337 +         if (nb == 0)
   1.338 +            strcpy(s, "none of");
   1.339 +         else if (ni == 1 && nb == 1)
   1.340 +            strcpy(s, "");
   1.341 +         else if (nb == 1)
   1.342 +            strcpy(s, "one of");
   1.343 +         else if (nb == ni)
   1.344 +            strcpy(s, "all of");
   1.345 +         else
   1.346 +            sprintf(s, "%d of", nb);
   1.347 +         xprintf("%d integer variable%s, %s which %s binary\n",
   1.348 +            ni, ni == 1 ? "" : "s", s, nb == 1 ? "is" : "are");
   1.349 +      }
   1.350 +      /* inherit basis factorization control parameters */
   1.351 +      glp_get_bfcp(P, &bfcp);
   1.352 +      glp_set_bfcp(mip, &bfcp);
   1.353 +      /* scale the transformed problem */
   1.354 +      if (!term_out || parm->msg_lev < GLP_MSG_ALL)
   1.355 +         env->term_out = GLP_OFF;
   1.356 +      else
   1.357 +         env->term_out = GLP_ON;
   1.358 +      glp_scale_prob(mip,
   1.359 +         GLP_SF_GM | GLP_SF_EQ | GLP_SF_2N | GLP_SF_SKIP);
   1.360 +      env->term_out = term_out;
   1.361 +      /* build advanced initial basis */
   1.362 +      if (!term_out || parm->msg_lev < GLP_MSG_ALL)
   1.363 +         env->term_out = GLP_OFF;
   1.364 +      else
   1.365 +         env->term_out = GLP_ON;
   1.366 +      glp_adv_basis(mip, 0);
   1.367 +      env->term_out = term_out;
   1.368 +      /* solve initial LP relaxation */
   1.369 +      if (parm->msg_lev >= GLP_MSG_ALL)
   1.370 +         xprintf("Solving LP relaxation...\n");
   1.371 +      glp_init_smcp(&smcp);
   1.372 +      smcp.msg_lev = parm->msg_lev;
   1.373 +      mip->it_cnt = P->it_cnt;
   1.374 +      ret = glp_simplex(mip, &smcp);
   1.375 +      P->it_cnt = mip->it_cnt;
   1.376 +      if (ret != 0)
   1.377 +      {  if (parm->msg_lev >= GLP_MSG_ERR)
   1.378 +            xprintf("glp_intopt: cannot solve LP relaxation\n");
   1.379 +         ret = GLP_EFAIL;
   1.380 +         goto done;
   1.381 +      }
   1.382 +      /* check status of the basic solution */
   1.383 +      ret = glp_get_status(mip);
   1.384 +      if (ret == GLP_OPT)
   1.385 +         ret = 0;
   1.386 +      else if (ret == GLP_NOFEAS)
   1.387 +         ret = GLP_ENOPFS;
   1.388 +      else if (ret == GLP_UNBND)
   1.389 +         ret = GLP_ENODFS;
   1.390 +      else
   1.391 +         xassert(ret != ret);
   1.392 +      if (ret != 0) goto done;
   1.393 +      /* solve the transformed MIP */
   1.394 +      mip->it_cnt = P->it_cnt;
   1.395 +      ret = solve_mip(mip, parm);
   1.396 +      P->it_cnt = mip->it_cnt;
   1.397 +      /* only integer feasible solution can be postprocessed */
   1.398 +      if (!(mip->mip_stat == GLP_OPT || mip->mip_stat == GLP_FEAS))
   1.399 +      {  P->mip_stat = mip->mip_stat;
   1.400 +         goto done;
   1.401 +      }
   1.402 +      /* postprocess solution from the transformed MIP */
   1.403 +post: npp_postprocess(npp, mip);
   1.404 +      /* the transformed MIP is no longer needed */
   1.405 +      glp_delete_prob(mip), mip = NULL;
   1.406 +      /* store solution to the original problem */
   1.407 +      npp_unload_sol(npp, P);
   1.408 +done: /* delete the transformed MIP, if it exists */
   1.409 +      if (mip != NULL) glp_delete_prob(mip);
   1.410 +      /* delete preprocessor workspace */
   1.411 +      npp_delete_wksp(npp);
   1.412 +      return ret;
   1.413 +}
   1.414 +
   1.415 +#ifndef HAVE_ALIEN_SOLVER /* 28/V-2010 */
   1.416 +int _glp_intopt1(glp_prob *P, const glp_iocp *parm)
   1.417 +{     xassert(P == P);
   1.418 +      xassert(parm == parm);
   1.419 +      xprintf("glp_intopt: no alien solver is available\n");
   1.420 +      return GLP_EFAIL;
   1.421 +}
   1.422 +#endif
   1.423 +
   1.424 +int glp_intopt(glp_prob *P, const glp_iocp *parm)
   1.425 +{     /* solve MIP problem with the branch-and-bound method */
   1.426 +      glp_iocp _parm;
   1.427 +      int i, j, ret;
   1.428 +      /* check problem object */
   1.429 +      if (P == NULL || P->magic != GLP_PROB_MAGIC)
   1.430 +         xerror("glp_intopt: P = %p; invalid problem object\n", P);
   1.431 +      if (P->tree != NULL)
   1.432 +         xerror("glp_intopt: operation not allowed\n");
   1.433 +      /* check control parameters */
   1.434 +      if (parm == NULL)
   1.435 +         parm = &_parm, glp_init_iocp((glp_iocp *)parm);
   1.436 +      if (!(parm->msg_lev == GLP_MSG_OFF ||
   1.437 +            parm->msg_lev == GLP_MSG_ERR ||
   1.438 +            parm->msg_lev == GLP_MSG_ON  ||
   1.439 +            parm->msg_lev == GLP_MSG_ALL ||
   1.440 +            parm->msg_lev == GLP_MSG_DBG))
   1.441 +         xerror("glp_intopt: msg_lev = %d; invalid parameter\n",
   1.442 +            parm->msg_lev);
   1.443 +      if (!(parm->br_tech == GLP_BR_FFV ||
   1.444 +            parm->br_tech == GLP_BR_LFV ||
   1.445 +            parm->br_tech == GLP_BR_MFV ||
   1.446 +            parm->br_tech == GLP_BR_DTH ||
   1.447 +            parm->br_tech == GLP_BR_PCH))
   1.448 +         xerror("glp_intopt: br_tech = %d; invalid parameter\n",
   1.449 +            parm->br_tech);
   1.450 +      if (!(parm->bt_tech == GLP_BT_DFS ||
   1.451 +            parm->bt_tech == GLP_BT_BFS ||
   1.452 +            parm->bt_tech == GLP_BT_BLB ||
   1.453 +            parm->bt_tech == GLP_BT_BPH))
   1.454 +         xerror("glp_intopt: bt_tech = %d; invalid parameter\n",
   1.455 +            parm->bt_tech);
   1.456 +      if (!(0.0 < parm->tol_int && parm->tol_int < 1.0))
   1.457 +         xerror("glp_intopt: tol_int = %g; invalid parameter\n",
   1.458 +            parm->tol_int);
   1.459 +      if (!(0.0 < parm->tol_obj && parm->tol_obj < 1.0))
   1.460 +         xerror("glp_intopt: tol_obj = %g; invalid parameter\n",
   1.461 +            parm->tol_obj);
   1.462 +      if (parm->tm_lim < 0)
   1.463 +         xerror("glp_intopt: tm_lim = %d; invalid parameter\n",
   1.464 +            parm->tm_lim);
   1.465 +      if (parm->out_frq < 0)
   1.466 +         xerror("glp_intopt: out_frq = %d; invalid parameter\n",
   1.467 +            parm->out_frq);
   1.468 +      if (parm->out_dly < 0)
   1.469 +         xerror("glp_intopt: out_dly = %d; invalid parameter\n",
   1.470 +            parm->out_dly);
   1.471 +      if (!(0 <= parm->cb_size && parm->cb_size <= 256))
   1.472 +         xerror("glp_intopt: cb_size = %d; invalid parameter\n",
   1.473 +            parm->cb_size);
   1.474 +      if (!(parm->pp_tech == GLP_PP_NONE ||
   1.475 +            parm->pp_tech == GLP_PP_ROOT ||
   1.476 +            parm->pp_tech == GLP_PP_ALL))
   1.477 +         xerror("glp_intopt: pp_tech = %d; invalid parameter\n",
   1.478 +            parm->pp_tech);
   1.479 +      if (parm->mip_gap < 0.0)
   1.480 +         xerror("glp_intopt: mip_gap = %g; invalid parameter\n",
   1.481 +            parm->mip_gap);
   1.482 +      if (!(parm->mir_cuts == GLP_ON || parm->mir_cuts == GLP_OFF))
   1.483 +         xerror("glp_intopt: mir_cuts = %d; invalid parameter\n",
   1.484 +            parm->mir_cuts);
   1.485 +      if (!(parm->gmi_cuts == GLP_ON || parm->gmi_cuts == GLP_OFF))
   1.486 +         xerror("glp_intopt: gmi_cuts = %d; invalid parameter\n",
   1.487 +            parm->gmi_cuts);
   1.488 +      if (!(parm->cov_cuts == GLP_ON || parm->cov_cuts == GLP_OFF))
   1.489 +         xerror("glp_intopt: cov_cuts = %d; invalid parameter\n",
   1.490 +            parm->cov_cuts);
   1.491 +      if (!(parm->clq_cuts == GLP_ON || parm->clq_cuts == GLP_OFF))
   1.492 +         xerror("glp_intopt: clq_cuts = %d; invalid parameter\n",
   1.493 +            parm->clq_cuts);
   1.494 +      if (!(parm->presolve == GLP_ON || parm->presolve == GLP_OFF))
   1.495 +         xerror("glp_intopt: presolve = %d; invalid parameter\n",
   1.496 +            parm->presolve);
   1.497 +      if (!(parm->binarize == GLP_ON || parm->binarize == GLP_OFF))
   1.498 +         xerror("glp_intopt: binarize = %d; invalid parameter\n",
   1.499 +            parm->binarize);
   1.500 +      if (!(parm->fp_heur == GLP_ON || parm->fp_heur == GLP_OFF))
   1.501 +         xerror("glp_intopt: fp_heur = %d; invalid parameter\n",
   1.502 +            parm->fp_heur);
   1.503 +#if 1 /* 28/V-2010 */
   1.504 +      if (!(parm->alien == GLP_ON || parm->alien == GLP_OFF))
   1.505 +         xerror("glp_intopt: alien = %d; invalid parameter\n",
   1.506 +            parm->alien);
   1.507 +#endif
   1.508 +      /* integer solution is currently undefined */
   1.509 +      P->mip_stat = GLP_UNDEF;
   1.510 +      P->mip_obj = 0.0;
   1.511 +      /* check bounds of double-bounded variables */
   1.512 +      for (i = 1; i <= P->m; i++)
   1.513 +      {  GLPROW *row = P->row[i];
   1.514 +         if (row->type == GLP_DB && row->lb >= row->ub)
   1.515 +         {  if (parm->msg_lev >= GLP_MSG_ERR)
   1.516 +               xprintf("glp_intopt: row %d: lb = %g, ub = %g; incorrect"
   1.517 +                  " bounds\n", i, row->lb, row->ub);
   1.518 +            ret = GLP_EBOUND;
   1.519 +            goto done;
   1.520 +         }
   1.521 +      }
   1.522 +      for (j = 1; j <= P->n; j++)
   1.523 +      {  GLPCOL *col = P->col[j];
   1.524 +         if (col->type == GLP_DB && col->lb >= col->ub)
   1.525 +         {  if (parm->msg_lev >= GLP_MSG_ERR)
   1.526 +               xprintf("glp_intopt: column %d: lb = %g, ub = %g; incorr"
   1.527 +                  "ect bounds\n", j, col->lb, col->ub);
   1.528 +            ret = GLP_EBOUND;
   1.529 +            goto done;
   1.530 +         }
   1.531 +      }
   1.532 +      /* bounds of all integer variables must be integral */
   1.533 +      for (j = 1; j <= P->n; j++)
   1.534 +      {  GLPCOL *col = P->col[j];
   1.535 +         if (col->kind != GLP_IV) continue;
   1.536 +         if (col->type == GLP_LO || col->type == GLP_DB)
   1.537 +         {  if (col->lb != floor(col->lb))
   1.538 +            {  if (parm->msg_lev >= GLP_MSG_ERR)
   1.539 +                  xprintf("glp_intopt: integer column %d has non-intege"
   1.540 +                     "r lower bound %g\n", j, col->lb);
   1.541 +               ret = GLP_EBOUND;
   1.542 +               goto done;
   1.543 +            }
   1.544 +         }
   1.545 +         if (col->type == GLP_UP || col->type == GLP_DB)
   1.546 +         {  if (col->ub != floor(col->ub))
   1.547 +            {  if (parm->msg_lev >= GLP_MSG_ERR)
   1.548 +                  xprintf("glp_intopt: integer column %d has non-intege"
   1.549 +                     "r upper bound %g\n", j, col->ub);
   1.550 +               ret = GLP_EBOUND;
   1.551 +               goto done;
   1.552 +            }
   1.553 +         }
   1.554 +         if (col->type == GLP_FX)
   1.555 +         {  if (col->lb != floor(col->lb))
   1.556 +            {  if (parm->msg_lev >= GLP_MSG_ERR)
   1.557 +                  xprintf("glp_intopt: integer column %d has non-intege"
   1.558 +                     "r fixed value %g\n", j, col->lb);
   1.559 +               ret = GLP_EBOUND;
   1.560 +               goto done;
   1.561 +            }
   1.562 +         }
   1.563 +      }
   1.564 +      /* solve MIP problem */
   1.565 +      if (parm->msg_lev >= GLP_MSG_ALL)
   1.566 +      {  int ni = glp_get_num_int(P);
   1.567 +         int nb = glp_get_num_bin(P);
   1.568 +         char s[50];
   1.569 +         xprintf("GLPK Integer Optimizer, v%s\n", glp_version());
   1.570 +         xprintf("%d row%s, %d column%s, %d non-zero%s\n",
   1.571 +            P->m, P->m == 1 ? "" : "s", P->n, P->n == 1 ? "" : "s",
   1.572 +            P->nnz, P->nnz == 1 ? "" : "s");
   1.573 +         if (nb == 0)
   1.574 +            strcpy(s, "none of");
   1.575 +         else if (ni == 1 && nb == 1)
   1.576 +            strcpy(s, "");
   1.577 +         else if (nb == 1)
   1.578 +            strcpy(s, "one of");
   1.579 +         else if (nb == ni)
   1.580 +            strcpy(s, "all of");
   1.581 +         else
   1.582 +            sprintf(s, "%d of", nb);
   1.583 +         xprintf("%d integer variable%s, %s which %s binary\n",
   1.584 +            ni, ni == 1 ? "" : "s", s, nb == 1 ? "is" : "are");
   1.585 +      }
   1.586 +#if 1 /* 28/V-2010 */
   1.587 +      if (parm->alien)
   1.588 +      {  /* use alien integer optimizer */
   1.589 +         ret = _glp_intopt1(P, parm);
   1.590 +         goto done;
   1.591 +      }
   1.592 +#endif
   1.593 +      if (!parm->presolve)
   1.594 +         ret = solve_mip(P, parm);
   1.595 +      else
   1.596 +         ret = preprocess_and_solve_mip(P, parm);
   1.597 +done: /* return to the application program */
   1.598 +      return ret;
   1.599 +}
   1.600 +
   1.601 +/***********************************************************************
   1.602 +*  NAME
   1.603 +*
   1.604 +*  glp_init_iocp - initialize integer optimizer control parameters
   1.605 +*
   1.606 +*  SYNOPSIS
   1.607 +*
   1.608 +*  void glp_init_iocp(glp_iocp *parm);
   1.609 +*
   1.610 +*  DESCRIPTION
   1.611 +*
   1.612 +*  The routine glp_init_iocp initializes control parameters, which are
   1.613 +*  used by the integer optimizer, with default values.
   1.614 +*
   1.615 +*  Default values of the control parameters are stored in a glp_iocp
   1.616 +*  structure, which the parameter parm points to. */
   1.617 +
   1.618 +void glp_init_iocp(glp_iocp *parm)
   1.619 +{     parm->msg_lev = GLP_MSG_ALL;
   1.620 +      parm->br_tech = GLP_BR_DTH;
   1.621 +      parm->bt_tech = GLP_BT_BLB;
   1.622 +      parm->tol_int = 1e-5;
   1.623 +      parm->tol_obj = 1e-7;
   1.624 +      parm->tm_lim = INT_MAX;
   1.625 +      parm->out_frq = 5000;
   1.626 +      parm->out_dly = 10000;
   1.627 +      parm->cb_func = NULL;
   1.628 +      parm->cb_info = NULL;
   1.629 +      parm->cb_size = 0;
   1.630 +      parm->pp_tech = GLP_PP_ALL;
   1.631 +      parm->mip_gap = 0.0;
   1.632 +      parm->mir_cuts = GLP_OFF;
   1.633 +      parm->gmi_cuts = GLP_OFF;
   1.634 +      parm->cov_cuts = GLP_OFF;
   1.635 +      parm->clq_cuts = GLP_OFF;
   1.636 +      parm->presolve = GLP_OFF;
   1.637 +      parm->binarize = GLP_OFF;
   1.638 +      parm->fp_heur = GLP_OFF;
   1.639 +#if 1 /* 28/V-2010 */
   1.640 +      parm->alien = GLP_OFF;
   1.641 +#endif
   1.642 +      return;
   1.643 +}
   1.644 +
   1.645 +/***********************************************************************
   1.646 +*  NAME
   1.647 +*
   1.648 +*  glp_mip_status - retrieve status of MIP solution
   1.649 +*
   1.650 +*  SYNOPSIS
   1.651 +*
   1.652 +*  int glp_mip_status(glp_prob *mip);
   1.653 +*
   1.654 +*  RETURNS
   1.655 +*
   1.656 +*  The routine lpx_mip_status reports the status of MIP solution found
   1.657 +*  by the branch-and-bound solver as follows:
   1.658 +*
   1.659 +*  GLP_UNDEF  - MIP solution is undefined;
   1.660 +*  GLP_OPT    - MIP solution is integer optimal;
   1.661 +*  GLP_FEAS   - MIP solution is integer feasible but its optimality
   1.662 +*               (or non-optimality) has not been proven, perhaps due to
   1.663 +*               premature termination of the search;
   1.664 +*  GLP_NOFEAS - problem has no integer feasible solution (proven by the
   1.665 +*               solver). */
   1.666 +
   1.667 +int glp_mip_status(glp_prob *mip)
   1.668 +{     int mip_stat = mip->mip_stat;
   1.669 +      return mip_stat;
   1.670 +}
   1.671 +
   1.672 +/***********************************************************************
   1.673 +*  NAME
   1.674 +*
   1.675 +*  glp_mip_obj_val - retrieve objective value (MIP solution)
   1.676 +*
   1.677 +*  SYNOPSIS
   1.678 +*
   1.679 +*  double glp_mip_obj_val(glp_prob *mip);
   1.680 +*
   1.681 +*  RETURNS
   1.682 +*
   1.683 +*  The routine glp_mip_obj_val returns value of the objective function
   1.684 +*  for MIP solution. */
   1.685 +
   1.686 +double glp_mip_obj_val(glp_prob *mip)
   1.687 +{     /*struct LPXCPS *cps = mip->cps;*/
   1.688 +      double z;
   1.689 +      z = mip->mip_obj;
   1.690 +      /*if (cps->round && fabs(z) < 1e-9) z = 0.0;*/
   1.691 +      return z;
   1.692 +}
   1.693 +
   1.694 +/***********************************************************************
   1.695 +*  NAME
   1.696 +*
   1.697 +*  glp_mip_row_val - retrieve row value (MIP solution)
   1.698 +*
   1.699 +*  SYNOPSIS
   1.700 +*
   1.701 +*  double glp_mip_row_val(glp_prob *mip, int i);
   1.702 +*
   1.703 +*  RETURNS
   1.704 +*
   1.705 +*  The routine glp_mip_row_val returns value of the auxiliary variable
   1.706 +*  associated with i-th row. */
   1.707 +
   1.708 +double glp_mip_row_val(glp_prob *mip, int i)
   1.709 +{     /*struct LPXCPS *cps = mip->cps;*/
   1.710 +      double mipx;
   1.711 +      if (!(1 <= i && i <= mip->m))
   1.712 +         xerror("glp_mip_row_val: i = %d; row number out of range\n", i)
   1.713 +            ;
   1.714 +      mipx = mip->row[i]->mipx;
   1.715 +      /*if (cps->round && fabs(mipx) < 1e-9) mipx = 0.0;*/
   1.716 +      return mipx;
   1.717 +}
   1.718 +
   1.719 +/***********************************************************************
   1.720 +*  NAME
   1.721 +*
   1.722 +*  glp_mip_col_val - retrieve column value (MIP solution)
   1.723 +*
   1.724 +*  SYNOPSIS
   1.725 +*
   1.726 +*  double glp_mip_col_val(glp_prob *mip, int j);
   1.727 +*
   1.728 +*  RETURNS
   1.729 +*
   1.730 +*  The routine glp_mip_col_val returns value of the structural variable
   1.731 +*  associated with j-th column. */
   1.732 +
   1.733 +double glp_mip_col_val(glp_prob *mip, int j)
   1.734 +{     /*struct LPXCPS *cps = mip->cps;*/
   1.735 +      double mipx;
   1.736 +      if (!(1 <= j && j <= mip->n))
   1.737 +         xerror("glp_mip_col_val: j = %d; column number out of range\n",
   1.738 +            j);
   1.739 +      mipx = mip->col[j]->mipx;
   1.740 +      /*if (cps->round && fabs(mipx) < 1e-9) mipx = 0.0;*/
   1.741 +      return mipx;
   1.742 +}
   1.743 +
   1.744 +/* eof */