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 */ |
---|