[1] | 1 | /* glpapi09.c (mixed integer programming routines) */ |
---|
| 2 | |
---|
| 3 | /*********************************************************************** |
---|
| 4 | * This code is part of GLPK (GNU Linear Programming Kit). |
---|
| 5 | * |
---|
| 6 | * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
---|
| 7 | * 2009, 2010 Andrew Makhorin, Department for Applied Informatics, |
---|
| 8 | * Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
---|
| 9 | * E-mail: <mao@gnu.org>. |
---|
| 10 | * |
---|
| 11 | * GLPK is free software: you can redistribute it and/or modify it |
---|
| 12 | * under the terms of the GNU General Public License as published by |
---|
| 13 | * the Free Software Foundation, either version 3 of the License, or |
---|
| 14 | * (at your option) any later version. |
---|
| 15 | * |
---|
| 16 | * GLPK is distributed in the hope that it will be useful, but WITHOUT |
---|
| 17 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
---|
| 18 | * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
---|
| 19 | * License for more details. |
---|
| 20 | * |
---|
| 21 | * You should have received a copy of the GNU General Public License |
---|
| 22 | * along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
---|
| 23 | ***********************************************************************/ |
---|
| 24 | |
---|
| 25 | #include "glpios.h" |
---|
| 26 | #include "glpnpp.h" |
---|
| 27 | |
---|
| 28 | /*********************************************************************** |
---|
| 29 | * NAME |
---|
| 30 | * |
---|
| 31 | * glp_set_col_kind - set (change) column kind |
---|
| 32 | * |
---|
| 33 | * SYNOPSIS |
---|
| 34 | * |
---|
| 35 | * void glp_set_col_kind(glp_prob *mip, int j, int kind); |
---|
| 36 | * |
---|
| 37 | * DESCRIPTION |
---|
| 38 | * |
---|
| 39 | * The routine glp_set_col_kind sets (changes) the kind of j-th column |
---|
| 40 | * (structural variable) as specified by the parameter kind: |
---|
| 41 | * |
---|
| 42 | * GLP_CV - continuous variable; |
---|
| 43 | * GLP_IV - integer variable; |
---|
| 44 | * GLP_BV - binary variable. */ |
---|
| 45 | |
---|
| 46 | void glp_set_col_kind(glp_prob *mip, int j, int kind) |
---|
| 47 | { GLPCOL *col; |
---|
| 48 | if (!(1 <= j && j <= mip->n)) |
---|
| 49 | xerror("glp_set_col_kind: j = %d; column number out of range\n" |
---|
| 50 | , j); |
---|
| 51 | col = mip->col[j]; |
---|
| 52 | switch (kind) |
---|
| 53 | { case GLP_CV: |
---|
| 54 | col->kind = GLP_CV; |
---|
| 55 | break; |
---|
| 56 | case GLP_IV: |
---|
| 57 | col->kind = GLP_IV; |
---|
| 58 | break; |
---|
| 59 | case GLP_BV: |
---|
| 60 | col->kind = GLP_IV; |
---|
| 61 | if (!(col->type == GLP_DB && col->lb == 0.0 && col->ub == |
---|
| 62 | 1.0)) glp_set_col_bnds(mip, j, GLP_DB, 0.0, 1.0); |
---|
| 63 | break; |
---|
| 64 | default: |
---|
| 65 | xerror("glp_set_col_kind: j = %d; kind = %d; invalid column" |
---|
| 66 | " kind\n", j, kind); |
---|
| 67 | } |
---|
| 68 | return; |
---|
| 69 | } |
---|
| 70 | |
---|
| 71 | /*********************************************************************** |
---|
| 72 | * NAME |
---|
| 73 | * |
---|
| 74 | * glp_get_col_kind - retrieve column kind |
---|
| 75 | * |
---|
| 76 | * SYNOPSIS |
---|
| 77 | * |
---|
| 78 | * int glp_get_col_kind(glp_prob *mip, int j); |
---|
| 79 | * |
---|
| 80 | * RETURNS |
---|
| 81 | * |
---|
| 82 | * The routine glp_get_col_kind returns the kind of j-th column, i.e. |
---|
| 83 | * the kind of corresponding structural variable, as follows: |
---|
| 84 | * |
---|
| 85 | * GLP_CV - continuous variable; |
---|
| 86 | * GLP_IV - integer variable; |
---|
| 87 | * GLP_BV - binary variable */ |
---|
| 88 | |
---|
| 89 | int glp_get_col_kind(glp_prob *mip, int j) |
---|
| 90 | { GLPCOL *col; |
---|
| 91 | int kind; |
---|
| 92 | if (!(1 <= j && j <= mip->n)) |
---|
| 93 | xerror("glp_get_col_kind: j = %d; column number out of range\n" |
---|
| 94 | , j); |
---|
| 95 | col = mip->col[j]; |
---|
| 96 | kind = col->kind; |
---|
| 97 | switch (kind) |
---|
| 98 | { case GLP_CV: |
---|
| 99 | break; |
---|
| 100 | case GLP_IV: |
---|
| 101 | if (col->type == GLP_DB && col->lb == 0.0 && col->ub == 1.0) |
---|
| 102 | kind = GLP_BV; |
---|
| 103 | break; |
---|
| 104 | default: |
---|
| 105 | xassert(kind != kind); |
---|
| 106 | } |
---|
| 107 | return kind; |
---|
| 108 | } |
---|
| 109 | |
---|
| 110 | /*********************************************************************** |
---|
| 111 | * NAME |
---|
| 112 | * |
---|
| 113 | * glp_get_num_int - retrieve number of integer columns |
---|
| 114 | * |
---|
| 115 | * SYNOPSIS |
---|
| 116 | * |
---|
| 117 | * int glp_get_num_int(glp_prob *mip); |
---|
| 118 | * |
---|
| 119 | * RETURNS |
---|
| 120 | * |
---|
| 121 | * The routine glp_get_num_int returns the current number of columns, |
---|
| 122 | * which are marked as integer. */ |
---|
| 123 | |
---|
| 124 | int glp_get_num_int(glp_prob *mip) |
---|
| 125 | { GLPCOL *col; |
---|
| 126 | int j, count = 0; |
---|
| 127 | for (j = 1; j <= mip->n; j++) |
---|
| 128 | { col = mip->col[j]; |
---|
| 129 | if (col->kind == GLP_IV) count++; |
---|
| 130 | } |
---|
| 131 | return count; |
---|
| 132 | } |
---|
| 133 | |
---|
| 134 | /*********************************************************************** |
---|
| 135 | * NAME |
---|
| 136 | * |
---|
| 137 | * glp_get_num_bin - retrieve number of binary columns |
---|
| 138 | * |
---|
| 139 | * SYNOPSIS |
---|
| 140 | * |
---|
| 141 | * int glp_get_num_bin(glp_prob *mip); |
---|
| 142 | * |
---|
| 143 | * RETURNS |
---|
| 144 | * |
---|
| 145 | * The routine glp_get_num_bin returns the current number of columns, |
---|
| 146 | * which are marked as binary. */ |
---|
| 147 | |
---|
| 148 | int glp_get_num_bin(glp_prob *mip) |
---|
| 149 | { GLPCOL *col; |
---|
| 150 | int j, count = 0; |
---|
| 151 | for (j = 1; j <= mip->n; j++) |
---|
| 152 | { col = mip->col[j]; |
---|
| 153 | if (col->kind == GLP_IV && col->type == GLP_DB && col->lb == |
---|
| 154 | 0.0 && col->ub == 1.0) count++; |
---|
| 155 | } |
---|
| 156 | return count; |
---|
| 157 | } |
---|
| 158 | |
---|
| 159 | /*********************************************************************** |
---|
| 160 | * NAME |
---|
| 161 | * |
---|
| 162 | * glp_intopt - solve MIP problem with the branch-and-bound method |
---|
| 163 | * |
---|
| 164 | * SYNOPSIS |
---|
| 165 | * |
---|
| 166 | * int glp_intopt(glp_prob *P, const glp_iocp *parm); |
---|
| 167 | * |
---|
| 168 | * DESCRIPTION |
---|
| 169 | * |
---|
| 170 | * The routine glp_intopt is a driver to the MIP solver based on the |
---|
| 171 | * branch-and-bound method. |
---|
| 172 | * |
---|
| 173 | * On entry the problem object should contain optimal solution to LP |
---|
| 174 | * relaxation (which can be obtained with the routine glp_simplex). |
---|
| 175 | * |
---|
| 176 | * The MIP solver has a set of control parameters. Values of the control |
---|
| 177 | * parameters can be passed in a structure glp_iocp, which the parameter |
---|
| 178 | * parm points to. |
---|
| 179 | * |
---|
| 180 | * The parameter parm can be specified as NULL, in which case the MIP |
---|
| 181 | * solver uses default settings. |
---|
| 182 | * |
---|
| 183 | * RETURNS |
---|
| 184 | * |
---|
| 185 | * 0 The MIP problem instance has been successfully solved. This code |
---|
| 186 | * does not necessarily mean that the solver has found optimal |
---|
| 187 | * solution. It only means that the solution process was successful. |
---|
| 188 | * |
---|
| 189 | * GLP_EBOUND |
---|
| 190 | * Unable to start the search, because some double-bounded variables |
---|
| 191 | * have incorrect bounds or some integer variables have non-integer |
---|
| 192 | * (fractional) bounds. |
---|
| 193 | * |
---|
| 194 | * GLP_EROOT |
---|
| 195 | * Unable to start the search, because optimal basis for initial LP |
---|
| 196 | * relaxation is not provided. |
---|
| 197 | * |
---|
| 198 | * GLP_EFAIL |
---|
| 199 | * The search was prematurely terminated due to the solver failure. |
---|
| 200 | * |
---|
| 201 | * GLP_EMIPGAP |
---|
| 202 | * The search was prematurely terminated, because the relative mip |
---|
| 203 | * gap tolerance has been reached. |
---|
| 204 | * |
---|
| 205 | * GLP_ETMLIM |
---|
| 206 | * The search was prematurely terminated, because the time limit has |
---|
| 207 | * been exceeded. |
---|
| 208 | * |
---|
| 209 | * GLP_ENOPFS |
---|
| 210 | * The MIP problem instance has no primal feasible solution (only if |
---|
| 211 | * the MIP presolver is used). |
---|
| 212 | * |
---|
| 213 | * GLP_ENODFS |
---|
| 214 | * LP relaxation of the MIP problem instance has no dual feasible |
---|
| 215 | * solution (only if the MIP presolver is used). |
---|
| 216 | * |
---|
| 217 | * GLP_ESTOP |
---|
| 218 | * The search was prematurely terminated by application. */ |
---|
| 219 | |
---|
| 220 | static int solve_mip(glp_prob *P, const glp_iocp *parm) |
---|
| 221 | { /* solve MIP directly without using the preprocessor */ |
---|
| 222 | glp_tree *T; |
---|
| 223 | int ret; |
---|
| 224 | /* optimal basis to LP relaxation must be provided */ |
---|
| 225 | if (glp_get_status(P) != GLP_OPT) |
---|
| 226 | { if (parm->msg_lev >= GLP_MSG_ERR) |
---|
| 227 | xprintf("glp_intopt: optimal basis to initial LP relaxation" |
---|
| 228 | " not provided\n"); |
---|
| 229 | ret = GLP_EROOT; |
---|
| 230 | goto done; |
---|
| 231 | } |
---|
| 232 | /* it seems all is ok */ |
---|
| 233 | if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 234 | xprintf("Integer optimization begins...\n"); |
---|
| 235 | /* create the branch-and-bound tree */ |
---|
| 236 | T = ios_create_tree(P, parm); |
---|
| 237 | /* solve the problem instance */ |
---|
| 238 | ret = ios_driver(T); |
---|
| 239 | /* delete the branch-and-bound tree */ |
---|
| 240 | ios_delete_tree(T); |
---|
| 241 | /* analyze exit code reported by the mip driver */ |
---|
| 242 | if (ret == 0) |
---|
| 243 | { if (P->mip_stat == GLP_FEAS) |
---|
| 244 | { if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 245 | xprintf("INTEGER OPTIMAL SOLUTION FOUND\n"); |
---|
| 246 | P->mip_stat = GLP_OPT; |
---|
| 247 | } |
---|
| 248 | else |
---|
| 249 | { if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 250 | xprintf("PROBLEM HAS NO INTEGER FEASIBLE SOLUTION\n"); |
---|
| 251 | P->mip_stat = GLP_NOFEAS; |
---|
| 252 | } |
---|
| 253 | } |
---|
| 254 | else if (ret == GLP_EMIPGAP) |
---|
| 255 | { if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 256 | xprintf("RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINA" |
---|
| 257 | "TED\n"); |
---|
| 258 | } |
---|
| 259 | else if (ret == GLP_ETMLIM) |
---|
| 260 | { if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 261 | xprintf("TIME LIMIT EXCEEDED; SEARCH TERMINATED\n"); |
---|
| 262 | } |
---|
| 263 | else if (ret == GLP_EFAIL) |
---|
| 264 | { if (parm->msg_lev >= GLP_MSG_ERR) |
---|
| 265 | xprintf("glp_intopt: cannot solve current LP relaxation\n"); |
---|
| 266 | } |
---|
| 267 | else if (ret == GLP_ESTOP) |
---|
| 268 | { if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 269 | xprintf("SEARCH TERMINATED BY APPLICATION\n"); |
---|
| 270 | } |
---|
| 271 | else |
---|
| 272 | xassert(ret != ret); |
---|
| 273 | done: return ret; |
---|
| 274 | } |
---|
| 275 | |
---|
| 276 | static int preprocess_and_solve_mip(glp_prob *P, const glp_iocp *parm) |
---|
| 277 | { /* solve MIP using the preprocessor */ |
---|
| 278 | ENV *env = get_env_ptr(); |
---|
| 279 | int term_out = env->term_out; |
---|
| 280 | NPP *npp; |
---|
| 281 | glp_prob *mip = NULL; |
---|
| 282 | glp_bfcp bfcp; |
---|
| 283 | glp_smcp smcp; |
---|
| 284 | int ret; |
---|
| 285 | if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 286 | xprintf("Preprocessing...\n"); |
---|
| 287 | /* create preprocessor workspace */ |
---|
| 288 | npp = npp_create_wksp(); |
---|
| 289 | /* load original problem into the preprocessor workspace */ |
---|
| 290 | npp_load_prob(npp, P, GLP_OFF, GLP_MIP, GLP_OFF); |
---|
| 291 | /* process MIP prior to applying the branch-and-bound method */ |
---|
| 292 | if (!term_out || parm->msg_lev < GLP_MSG_ALL) |
---|
| 293 | env->term_out = GLP_OFF; |
---|
| 294 | else |
---|
| 295 | env->term_out = GLP_ON; |
---|
| 296 | ret = npp_integer(npp, parm); |
---|
| 297 | env->term_out = term_out; |
---|
| 298 | if (ret == 0) |
---|
| 299 | ; |
---|
| 300 | else if (ret == GLP_ENOPFS) |
---|
| 301 | { if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 302 | xprintf("PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION\n"); |
---|
| 303 | } |
---|
| 304 | else if (ret == GLP_ENODFS) |
---|
| 305 | { if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 306 | xprintf("LP RELAXATION HAS NO DUAL FEASIBLE SOLUTION\n"); |
---|
| 307 | } |
---|
| 308 | else |
---|
| 309 | xassert(ret != ret); |
---|
| 310 | if (ret != 0) goto done; |
---|
| 311 | /* build transformed MIP */ |
---|
| 312 | mip = glp_create_prob(); |
---|
| 313 | npp_build_prob(npp, mip); |
---|
| 314 | /* if the transformed MIP is empty, it has empty solution, which |
---|
| 315 | is optimal */ |
---|
| 316 | if (mip->m == 0 && mip->n == 0) |
---|
| 317 | { mip->mip_stat = GLP_OPT; |
---|
| 318 | mip->mip_obj = mip->c0; |
---|
| 319 | if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 320 | { xprintf("Objective value = %17.9e\n", mip->mip_obj); |
---|
| 321 | xprintf("INTEGER OPTIMAL SOLUTION FOUND BY MIP PREPROCESSOR" |
---|
| 322 | "\n"); |
---|
| 323 | } |
---|
| 324 | goto post; |
---|
| 325 | } |
---|
| 326 | /* display some statistics */ |
---|
| 327 | if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 328 | { int ni = glp_get_num_int(mip); |
---|
| 329 | int nb = glp_get_num_bin(mip); |
---|
| 330 | char s[50]; |
---|
| 331 | xprintf("%d row%s, %d column%s, %d non-zero%s\n", |
---|
| 332 | mip->m, mip->m == 1 ? "" : "s", mip->n, mip->n == 1 ? "" : |
---|
| 333 | "s", mip->nnz, mip->nnz == 1 ? "" : "s"); |
---|
| 334 | if (nb == 0) |
---|
| 335 | strcpy(s, "none of"); |
---|
| 336 | else if (ni == 1 && nb == 1) |
---|
| 337 | strcpy(s, ""); |
---|
| 338 | else if (nb == 1) |
---|
| 339 | strcpy(s, "one of"); |
---|
| 340 | else if (nb == ni) |
---|
| 341 | strcpy(s, "all of"); |
---|
| 342 | else |
---|
| 343 | sprintf(s, "%d of", nb); |
---|
| 344 | xprintf("%d integer variable%s, %s which %s binary\n", |
---|
| 345 | ni, ni == 1 ? "" : "s", s, nb == 1 ? "is" : "are"); |
---|
| 346 | } |
---|
| 347 | /* inherit basis factorization control parameters */ |
---|
| 348 | glp_get_bfcp(P, &bfcp); |
---|
| 349 | glp_set_bfcp(mip, &bfcp); |
---|
| 350 | /* scale the transformed problem */ |
---|
| 351 | if (!term_out || parm->msg_lev < GLP_MSG_ALL) |
---|
| 352 | env->term_out = GLP_OFF; |
---|
| 353 | else |
---|
| 354 | env->term_out = GLP_ON; |
---|
| 355 | glp_scale_prob(mip, |
---|
| 356 | GLP_SF_GM | GLP_SF_EQ | GLP_SF_2N | GLP_SF_SKIP); |
---|
| 357 | env->term_out = term_out; |
---|
| 358 | /* build advanced initial basis */ |
---|
| 359 | if (!term_out || parm->msg_lev < GLP_MSG_ALL) |
---|
| 360 | env->term_out = GLP_OFF; |
---|
| 361 | else |
---|
| 362 | env->term_out = GLP_ON; |
---|
| 363 | glp_adv_basis(mip, 0); |
---|
| 364 | env->term_out = term_out; |
---|
| 365 | /* solve initial LP relaxation */ |
---|
| 366 | if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 367 | xprintf("Solving LP relaxation...\n"); |
---|
| 368 | glp_init_smcp(&smcp); |
---|
| 369 | smcp.msg_lev = parm->msg_lev; |
---|
| 370 | mip->it_cnt = P->it_cnt; |
---|
| 371 | ret = glp_simplex(mip, &smcp); |
---|
| 372 | P->it_cnt = mip->it_cnt; |
---|
| 373 | if (ret != 0) |
---|
| 374 | { if (parm->msg_lev >= GLP_MSG_ERR) |
---|
| 375 | xprintf("glp_intopt: cannot solve LP relaxation\n"); |
---|
| 376 | ret = GLP_EFAIL; |
---|
| 377 | goto done; |
---|
| 378 | } |
---|
| 379 | /* check status of the basic solution */ |
---|
| 380 | ret = glp_get_status(mip); |
---|
| 381 | if (ret == GLP_OPT) |
---|
| 382 | ret = 0; |
---|
| 383 | else if (ret == GLP_NOFEAS) |
---|
| 384 | ret = GLP_ENOPFS; |
---|
| 385 | else if (ret == GLP_UNBND) |
---|
| 386 | ret = GLP_ENODFS; |
---|
| 387 | else |
---|
| 388 | xassert(ret != ret); |
---|
| 389 | if (ret != 0) goto done; |
---|
| 390 | /* solve the transformed MIP */ |
---|
| 391 | mip->it_cnt = P->it_cnt; |
---|
| 392 | ret = solve_mip(mip, parm); |
---|
| 393 | P->it_cnt = mip->it_cnt; |
---|
| 394 | /* only integer feasible solution can be postprocessed */ |
---|
| 395 | if (!(mip->mip_stat == GLP_OPT || mip->mip_stat == GLP_FEAS)) |
---|
| 396 | { P->mip_stat = mip->mip_stat; |
---|
| 397 | goto done; |
---|
| 398 | } |
---|
| 399 | /* postprocess solution from the transformed MIP */ |
---|
| 400 | post: npp_postprocess(npp, mip); |
---|
| 401 | /* the transformed MIP is no longer needed */ |
---|
| 402 | glp_delete_prob(mip), mip = NULL; |
---|
| 403 | /* store solution to the original problem */ |
---|
| 404 | npp_unload_sol(npp, P); |
---|
| 405 | done: /* delete the transformed MIP, if it exists */ |
---|
| 406 | if (mip != NULL) glp_delete_prob(mip); |
---|
| 407 | /* delete preprocessor workspace */ |
---|
| 408 | npp_delete_wksp(npp); |
---|
| 409 | return ret; |
---|
| 410 | } |
---|
| 411 | |
---|
| 412 | #ifndef HAVE_ALIEN_SOLVER /* 28/V-2010 */ |
---|
| 413 | int _glp_intopt1(glp_prob *P, const glp_iocp *parm) |
---|
| 414 | { xassert(P == P); |
---|
| 415 | xassert(parm == parm); |
---|
| 416 | xprintf("glp_intopt: no alien solver is available\n"); |
---|
| 417 | return GLP_EFAIL; |
---|
| 418 | } |
---|
| 419 | #endif |
---|
| 420 | |
---|
| 421 | int glp_intopt(glp_prob *P, const glp_iocp *parm) |
---|
| 422 | { /* solve MIP problem with the branch-and-bound method */ |
---|
| 423 | glp_iocp _parm; |
---|
| 424 | int i, j, ret; |
---|
| 425 | /* check problem object */ |
---|
| 426 | if (P == NULL || P->magic != GLP_PROB_MAGIC) |
---|
| 427 | xerror("glp_intopt: P = %p; invalid problem object\n", P); |
---|
| 428 | if (P->tree != NULL) |
---|
| 429 | xerror("glp_intopt: operation not allowed\n"); |
---|
| 430 | /* check control parameters */ |
---|
| 431 | if (parm == NULL) |
---|
| 432 | parm = &_parm, glp_init_iocp((glp_iocp *)parm); |
---|
| 433 | if (!(parm->msg_lev == GLP_MSG_OFF || |
---|
| 434 | parm->msg_lev == GLP_MSG_ERR || |
---|
| 435 | parm->msg_lev == GLP_MSG_ON || |
---|
| 436 | parm->msg_lev == GLP_MSG_ALL || |
---|
| 437 | parm->msg_lev == GLP_MSG_DBG)) |
---|
| 438 | xerror("glp_intopt: msg_lev = %d; invalid parameter\n", |
---|
| 439 | parm->msg_lev); |
---|
| 440 | if (!(parm->br_tech == GLP_BR_FFV || |
---|
| 441 | parm->br_tech == GLP_BR_LFV || |
---|
| 442 | parm->br_tech == GLP_BR_MFV || |
---|
| 443 | parm->br_tech == GLP_BR_DTH || |
---|
| 444 | parm->br_tech == GLP_BR_PCH)) |
---|
| 445 | xerror("glp_intopt: br_tech = %d; invalid parameter\n", |
---|
| 446 | parm->br_tech); |
---|
| 447 | if (!(parm->bt_tech == GLP_BT_DFS || |
---|
| 448 | parm->bt_tech == GLP_BT_BFS || |
---|
| 449 | parm->bt_tech == GLP_BT_BLB || |
---|
| 450 | parm->bt_tech == GLP_BT_BPH)) |
---|
| 451 | xerror("glp_intopt: bt_tech = %d; invalid parameter\n", |
---|
| 452 | parm->bt_tech); |
---|
| 453 | if (!(0.0 < parm->tol_int && parm->tol_int < 1.0)) |
---|
| 454 | xerror("glp_intopt: tol_int = %g; invalid parameter\n", |
---|
| 455 | parm->tol_int); |
---|
| 456 | if (!(0.0 < parm->tol_obj && parm->tol_obj < 1.0)) |
---|
| 457 | xerror("glp_intopt: tol_obj = %g; invalid parameter\n", |
---|
| 458 | parm->tol_obj); |
---|
| 459 | if (parm->tm_lim < 0) |
---|
| 460 | xerror("glp_intopt: tm_lim = %d; invalid parameter\n", |
---|
| 461 | parm->tm_lim); |
---|
| 462 | if (parm->out_frq < 0) |
---|
| 463 | xerror("glp_intopt: out_frq = %d; invalid parameter\n", |
---|
| 464 | parm->out_frq); |
---|
| 465 | if (parm->out_dly < 0) |
---|
| 466 | xerror("glp_intopt: out_dly = %d; invalid parameter\n", |
---|
| 467 | parm->out_dly); |
---|
| 468 | if (!(0 <= parm->cb_size && parm->cb_size <= 256)) |
---|
| 469 | xerror("glp_intopt: cb_size = %d; invalid parameter\n", |
---|
| 470 | parm->cb_size); |
---|
| 471 | if (!(parm->pp_tech == GLP_PP_NONE || |
---|
| 472 | parm->pp_tech == GLP_PP_ROOT || |
---|
| 473 | parm->pp_tech == GLP_PP_ALL)) |
---|
| 474 | xerror("glp_intopt: pp_tech = %d; invalid parameter\n", |
---|
| 475 | parm->pp_tech); |
---|
| 476 | if (parm->mip_gap < 0.0) |
---|
| 477 | xerror("glp_intopt: mip_gap = %g; invalid parameter\n", |
---|
| 478 | parm->mip_gap); |
---|
| 479 | if (!(parm->mir_cuts == GLP_ON || parm->mir_cuts == GLP_OFF)) |
---|
| 480 | xerror("glp_intopt: mir_cuts = %d; invalid parameter\n", |
---|
| 481 | parm->mir_cuts); |
---|
| 482 | if (!(parm->gmi_cuts == GLP_ON || parm->gmi_cuts == GLP_OFF)) |
---|
| 483 | xerror("glp_intopt: gmi_cuts = %d; invalid parameter\n", |
---|
| 484 | parm->gmi_cuts); |
---|
| 485 | if (!(parm->cov_cuts == GLP_ON || parm->cov_cuts == GLP_OFF)) |
---|
| 486 | xerror("glp_intopt: cov_cuts = %d; invalid parameter\n", |
---|
| 487 | parm->cov_cuts); |
---|
| 488 | if (!(parm->clq_cuts == GLP_ON || parm->clq_cuts == GLP_OFF)) |
---|
| 489 | xerror("glp_intopt: clq_cuts = %d; invalid parameter\n", |
---|
| 490 | parm->clq_cuts); |
---|
| 491 | if (!(parm->presolve == GLP_ON || parm->presolve == GLP_OFF)) |
---|
| 492 | xerror("glp_intopt: presolve = %d; invalid parameter\n", |
---|
| 493 | parm->presolve); |
---|
| 494 | if (!(parm->binarize == GLP_ON || parm->binarize == GLP_OFF)) |
---|
| 495 | xerror("glp_intopt: binarize = %d; invalid parameter\n", |
---|
| 496 | parm->binarize); |
---|
| 497 | if (!(parm->fp_heur == GLP_ON || parm->fp_heur == GLP_OFF)) |
---|
| 498 | xerror("glp_intopt: fp_heur = %d; invalid parameter\n", |
---|
| 499 | parm->fp_heur); |
---|
| 500 | #if 1 /* 28/V-2010 */ |
---|
| 501 | if (!(parm->alien == GLP_ON || parm->alien == GLP_OFF)) |
---|
| 502 | xerror("glp_intopt: alien = %d; invalid parameter\n", |
---|
| 503 | parm->alien); |
---|
| 504 | #endif |
---|
| 505 | /* integer solution is currently undefined */ |
---|
| 506 | P->mip_stat = GLP_UNDEF; |
---|
| 507 | P->mip_obj = 0.0; |
---|
| 508 | /* check bounds of double-bounded variables */ |
---|
| 509 | for (i = 1; i <= P->m; i++) |
---|
| 510 | { GLPROW *row = P->row[i]; |
---|
| 511 | if (row->type == GLP_DB && row->lb >= row->ub) |
---|
| 512 | { if (parm->msg_lev >= GLP_MSG_ERR) |
---|
| 513 | xprintf("glp_intopt: row %d: lb = %g, ub = %g; incorrect" |
---|
| 514 | " bounds\n", i, row->lb, row->ub); |
---|
| 515 | ret = GLP_EBOUND; |
---|
| 516 | goto done; |
---|
| 517 | } |
---|
| 518 | } |
---|
| 519 | for (j = 1; j <= P->n; j++) |
---|
| 520 | { GLPCOL *col = P->col[j]; |
---|
| 521 | if (col->type == GLP_DB && col->lb >= col->ub) |
---|
| 522 | { if (parm->msg_lev >= GLP_MSG_ERR) |
---|
| 523 | xprintf("glp_intopt: column %d: lb = %g, ub = %g; incorr" |
---|
| 524 | "ect bounds\n", j, col->lb, col->ub); |
---|
| 525 | ret = GLP_EBOUND; |
---|
| 526 | goto done; |
---|
| 527 | } |
---|
| 528 | } |
---|
| 529 | /* bounds of all integer variables must be integral */ |
---|
| 530 | for (j = 1; j <= P->n; j++) |
---|
| 531 | { GLPCOL *col = P->col[j]; |
---|
| 532 | if (col->kind != GLP_IV) continue; |
---|
| 533 | if (col->type == GLP_LO || col->type == GLP_DB) |
---|
| 534 | { if (col->lb != floor(col->lb)) |
---|
| 535 | { if (parm->msg_lev >= GLP_MSG_ERR) |
---|
| 536 | xprintf("glp_intopt: integer column %d has non-intege" |
---|
| 537 | "r lower bound %g\n", j, col->lb); |
---|
| 538 | ret = GLP_EBOUND; |
---|
| 539 | goto done; |
---|
| 540 | } |
---|
| 541 | } |
---|
| 542 | if (col->type == GLP_UP || col->type == GLP_DB) |
---|
| 543 | { if (col->ub != floor(col->ub)) |
---|
| 544 | { if (parm->msg_lev >= GLP_MSG_ERR) |
---|
| 545 | xprintf("glp_intopt: integer column %d has non-intege" |
---|
| 546 | "r upper bound %g\n", j, col->ub); |
---|
| 547 | ret = GLP_EBOUND; |
---|
| 548 | goto done; |
---|
| 549 | } |
---|
| 550 | } |
---|
| 551 | if (col->type == GLP_FX) |
---|
| 552 | { if (col->lb != floor(col->lb)) |
---|
| 553 | { if (parm->msg_lev >= GLP_MSG_ERR) |
---|
| 554 | xprintf("glp_intopt: integer column %d has non-intege" |
---|
| 555 | "r fixed value %g\n", j, col->lb); |
---|
| 556 | ret = GLP_EBOUND; |
---|
| 557 | goto done; |
---|
| 558 | } |
---|
| 559 | } |
---|
| 560 | } |
---|
| 561 | /* solve MIP problem */ |
---|
| 562 | if (parm->msg_lev >= GLP_MSG_ALL) |
---|
| 563 | { int ni = glp_get_num_int(P); |
---|
| 564 | int nb = glp_get_num_bin(P); |
---|
| 565 | char s[50]; |
---|
| 566 | xprintf("GLPK Integer Optimizer, v%s\n", glp_version()); |
---|
| 567 | xprintf("%d row%s, %d column%s, %d non-zero%s\n", |
---|
| 568 | P->m, P->m == 1 ? "" : "s", P->n, P->n == 1 ? "" : "s", |
---|
| 569 | P->nnz, P->nnz == 1 ? "" : "s"); |
---|
| 570 | if (nb == 0) |
---|
| 571 | strcpy(s, "none of"); |
---|
| 572 | else if (ni == 1 && nb == 1) |
---|
| 573 | strcpy(s, ""); |
---|
| 574 | else if (nb == 1) |
---|
| 575 | strcpy(s, "one of"); |
---|
| 576 | else if (nb == ni) |
---|
| 577 | strcpy(s, "all of"); |
---|
| 578 | else |
---|
| 579 | sprintf(s, "%d of", nb); |
---|
| 580 | xprintf("%d integer variable%s, %s which %s binary\n", |
---|
| 581 | ni, ni == 1 ? "" : "s", s, nb == 1 ? "is" : "are"); |
---|
| 582 | } |
---|
| 583 | #if 1 /* 28/V-2010 */ |
---|
| 584 | if (parm->alien) |
---|
| 585 | { /* use alien integer optimizer */ |
---|
| 586 | ret = _glp_intopt1(P, parm); |
---|
| 587 | goto done; |
---|
| 588 | } |
---|
| 589 | #endif |
---|
| 590 | if (!parm->presolve) |
---|
| 591 | ret = solve_mip(P, parm); |
---|
| 592 | else |
---|
| 593 | ret = preprocess_and_solve_mip(P, parm); |
---|
| 594 | done: /* return to the application program */ |
---|
| 595 | return ret; |
---|
| 596 | } |
---|
| 597 | |
---|
| 598 | /*********************************************************************** |
---|
| 599 | * NAME |
---|
| 600 | * |
---|
| 601 | * glp_init_iocp - initialize integer optimizer control parameters |
---|
| 602 | * |
---|
| 603 | * SYNOPSIS |
---|
| 604 | * |
---|
| 605 | * void glp_init_iocp(glp_iocp *parm); |
---|
| 606 | * |
---|
| 607 | * DESCRIPTION |
---|
| 608 | * |
---|
| 609 | * The routine glp_init_iocp initializes control parameters, which are |
---|
| 610 | * used by the integer optimizer, with default values. |
---|
| 611 | * |
---|
| 612 | * Default values of the control parameters are stored in a glp_iocp |
---|
| 613 | * structure, which the parameter parm points to. */ |
---|
| 614 | |
---|
| 615 | void glp_init_iocp(glp_iocp *parm) |
---|
| 616 | { parm->msg_lev = GLP_MSG_ALL; |
---|
| 617 | parm->br_tech = GLP_BR_DTH; |
---|
| 618 | parm->bt_tech = GLP_BT_BLB; |
---|
| 619 | parm->tol_int = 1e-5; |
---|
| 620 | parm->tol_obj = 1e-7; |
---|
| 621 | parm->tm_lim = INT_MAX; |
---|
| 622 | parm->out_frq = 5000; |
---|
| 623 | parm->out_dly = 10000; |
---|
| 624 | parm->cb_func = NULL; |
---|
| 625 | parm->cb_info = NULL; |
---|
| 626 | parm->cb_size = 0; |
---|
| 627 | parm->pp_tech = GLP_PP_ALL; |
---|
| 628 | parm->mip_gap = 0.0; |
---|
| 629 | parm->mir_cuts = GLP_OFF; |
---|
| 630 | parm->gmi_cuts = GLP_OFF; |
---|
| 631 | parm->cov_cuts = GLP_OFF; |
---|
| 632 | parm->clq_cuts = GLP_OFF; |
---|
| 633 | parm->presolve = GLP_OFF; |
---|
| 634 | parm->binarize = GLP_OFF; |
---|
| 635 | parm->fp_heur = GLP_OFF; |
---|
| 636 | #if 1 /* 28/V-2010 */ |
---|
| 637 | parm->alien = GLP_OFF; |
---|
| 638 | #endif |
---|
| 639 | return; |
---|
| 640 | } |
---|
| 641 | |
---|
| 642 | /*********************************************************************** |
---|
| 643 | * NAME |
---|
| 644 | * |
---|
| 645 | * glp_mip_status - retrieve status of MIP solution |
---|
| 646 | * |
---|
| 647 | * SYNOPSIS |
---|
| 648 | * |
---|
| 649 | * int glp_mip_status(glp_prob *mip); |
---|
| 650 | * |
---|
| 651 | * RETURNS |
---|
| 652 | * |
---|
| 653 | * The routine lpx_mip_status reports the status of MIP solution found |
---|
| 654 | * by the branch-and-bound solver as follows: |
---|
| 655 | * |
---|
| 656 | * GLP_UNDEF - MIP solution is undefined; |
---|
| 657 | * GLP_OPT - MIP solution is integer optimal; |
---|
| 658 | * GLP_FEAS - MIP solution is integer feasible but its optimality |
---|
| 659 | * (or non-optimality) has not been proven, perhaps due to |
---|
| 660 | * premature termination of the search; |
---|
| 661 | * GLP_NOFEAS - problem has no integer feasible solution (proven by the |
---|
| 662 | * solver). */ |
---|
| 663 | |
---|
| 664 | int glp_mip_status(glp_prob *mip) |
---|
| 665 | { int mip_stat = mip->mip_stat; |
---|
| 666 | return mip_stat; |
---|
| 667 | } |
---|
| 668 | |
---|
| 669 | /*********************************************************************** |
---|
| 670 | * NAME |
---|
| 671 | * |
---|
| 672 | * glp_mip_obj_val - retrieve objective value (MIP solution) |
---|
| 673 | * |
---|
| 674 | * SYNOPSIS |
---|
| 675 | * |
---|
| 676 | * double glp_mip_obj_val(glp_prob *mip); |
---|
| 677 | * |
---|
| 678 | * RETURNS |
---|
| 679 | * |
---|
| 680 | * The routine glp_mip_obj_val returns value of the objective function |
---|
| 681 | * for MIP solution. */ |
---|
| 682 | |
---|
| 683 | double glp_mip_obj_val(glp_prob *mip) |
---|
| 684 | { /*struct LPXCPS *cps = mip->cps;*/ |
---|
| 685 | double z; |
---|
| 686 | z = mip->mip_obj; |
---|
| 687 | /*if (cps->round && fabs(z) < 1e-9) z = 0.0;*/ |
---|
| 688 | return z; |
---|
| 689 | } |
---|
| 690 | |
---|
| 691 | /*********************************************************************** |
---|
| 692 | * NAME |
---|
| 693 | * |
---|
| 694 | * glp_mip_row_val - retrieve row value (MIP solution) |
---|
| 695 | * |
---|
| 696 | * SYNOPSIS |
---|
| 697 | * |
---|
| 698 | * double glp_mip_row_val(glp_prob *mip, int i); |
---|
| 699 | * |
---|
| 700 | * RETURNS |
---|
| 701 | * |
---|
| 702 | * The routine glp_mip_row_val returns value of the auxiliary variable |
---|
| 703 | * associated with i-th row. */ |
---|
| 704 | |
---|
| 705 | double glp_mip_row_val(glp_prob *mip, int i) |
---|
| 706 | { /*struct LPXCPS *cps = mip->cps;*/ |
---|
| 707 | double mipx; |
---|
| 708 | if (!(1 <= i && i <= mip->m)) |
---|
| 709 | xerror("glp_mip_row_val: i = %d; row number out of range\n", i) |
---|
| 710 | ; |
---|
| 711 | mipx = mip->row[i]->mipx; |
---|
| 712 | /*if (cps->round && fabs(mipx) < 1e-9) mipx = 0.0;*/ |
---|
| 713 | return mipx; |
---|
| 714 | } |
---|
| 715 | |
---|
| 716 | /*********************************************************************** |
---|
| 717 | * NAME |
---|
| 718 | * |
---|
| 719 | * glp_mip_col_val - retrieve column value (MIP solution) |
---|
| 720 | * |
---|
| 721 | * SYNOPSIS |
---|
| 722 | * |
---|
| 723 | * double glp_mip_col_val(glp_prob *mip, int j); |
---|
| 724 | * |
---|
| 725 | * RETURNS |
---|
| 726 | * |
---|
| 727 | * The routine glp_mip_col_val returns value of the structural variable |
---|
| 728 | * associated with j-th column. */ |
---|
| 729 | |
---|
| 730 | double glp_mip_col_val(glp_prob *mip, int j) |
---|
| 731 | { /*struct LPXCPS *cps = mip->cps;*/ |
---|
| 732 | double mipx; |
---|
| 733 | if (!(1 <= j && j <= mip->n)) |
---|
| 734 | xerror("glp_mip_col_val: j = %d; column number out of range\n", |
---|
| 735 | j); |
---|
| 736 | mipx = mip->col[j]->mipx; |
---|
| 737 | /*if (cps->round && fabs(mipx) < 1e-9) mipx = 0.0;*/ |
---|
| 738 | return mipx; |
---|
| 739 | } |
---|
| 740 | |
---|
| 741 | /* eof */ |
---|