1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpapi09.c Mon Dec 06 13:09:21 2010 +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 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 */