lemon-project-template-glpk

comparison deps/glpk/src/glpapi13.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:52bd574dd272
1 /* glpapi13.c (branch-and-bound interface 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, 2011 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
27 /***********************************************************************
28 * NAME
29 *
30 * glp_ios_reason - determine reason for calling the callback routine
31 *
32 * SYNOPSIS
33 *
34 * glp_ios_reason(glp_tree *tree);
35 *
36 * RETURNS
37 *
38 * The routine glp_ios_reason returns a code, which indicates why the
39 * user-defined callback routine is being called. */
40
41 int glp_ios_reason(glp_tree *tree)
42 { return
43 tree->reason;
44 }
45
46 /***********************************************************************
47 * NAME
48 *
49 * glp_ios_get_prob - access the problem object
50 *
51 * SYNOPSIS
52 *
53 * glp_prob *glp_ios_get_prob(glp_tree *tree);
54 *
55 * DESCRIPTION
56 *
57 * The routine glp_ios_get_prob can be called from the user-defined
58 * callback routine to access the problem object, which is used by the
59 * MIP solver. It is the original problem object passed to the routine
60 * glp_intopt if the MIP presolver is not used; otherwise it is an
61 * internal problem object built by the presolver. If the current
62 * subproblem exists, LP segment of the problem object corresponds to
63 * its LP relaxation.
64 *
65 * RETURNS
66 *
67 * The routine glp_ios_get_prob returns a pointer to the problem object
68 * used by the MIP solver. */
69
70 glp_prob *glp_ios_get_prob(glp_tree *tree)
71 { return
72 tree->mip;
73 }
74
75 /***********************************************************************
76 * NAME
77 *
78 * glp_ios_tree_size - determine size of the branch-and-bound tree
79 *
80 * SYNOPSIS
81 *
82 * void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
83 * int *t_cnt);
84 *
85 * DESCRIPTION
86 *
87 * The routine glp_ios_tree_size stores the following three counts which
88 * characterize the current size of the branch-and-bound tree:
89 *
90 * a_cnt is the current number of active nodes, i.e. the current size of
91 * the active list;
92 *
93 * n_cnt is the current number of all (active and inactive) nodes;
94 *
95 * t_cnt is the total number of nodes including those which have been
96 * already removed from the tree. This count is increased whenever
97 * a new node appears in the tree and never decreased.
98 *
99 * If some of the parameters a_cnt, n_cnt, t_cnt is a null pointer, the
100 * corresponding count is not stored. */
101
102 void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
103 int *t_cnt)
104 { if (a_cnt != NULL) *a_cnt = tree->a_cnt;
105 if (n_cnt != NULL) *n_cnt = tree->n_cnt;
106 if (t_cnt != NULL) *t_cnt = tree->t_cnt;
107 return;
108 }
109
110 /***********************************************************************
111 * NAME
112 *
113 * glp_ios_curr_node - determine current active subproblem
114 *
115 * SYNOPSIS
116 *
117 * int glp_ios_curr_node(glp_tree *tree);
118 *
119 * RETURNS
120 *
121 * The routine glp_ios_curr_node returns the reference number of the
122 * current active subproblem. However, if the current subproblem does
123 * not exist, the routine returns zero. */
124
125 int glp_ios_curr_node(glp_tree *tree)
126 { IOSNPD *node;
127 /* obtain pointer to the current subproblem */
128 node = tree->curr;
129 /* return its reference number */
130 return node == NULL ? 0 : node->p;
131 }
132
133 /***********************************************************************
134 * NAME
135 *
136 * glp_ios_next_node - determine next active subproblem
137 *
138 * SYNOPSIS
139 *
140 * int glp_ios_next_node(glp_tree *tree, int p);
141 *
142 * RETURNS
143 *
144 * If the parameter p is zero, the routine glp_ios_next_node returns
145 * the reference number of the first active subproblem. However, if the
146 * tree is empty, zero is returned.
147 *
148 * If the parameter p is not zero, it must specify the reference number
149 * of some active subproblem, in which case the routine returns the
150 * reference number of the next active subproblem. However, if there is
151 * no next active subproblem in the list, zero is returned.
152 *
153 * All subproblems in the active list are ordered chronologically, i.e.
154 * subproblem A precedes subproblem B if A was created before B. */
155
156 int glp_ios_next_node(glp_tree *tree, int p)
157 { IOSNPD *node;
158 if (p == 0)
159 { /* obtain pointer to the first active subproblem */
160 node = tree->head;
161 }
162 else
163 { /* obtain pointer to the specified subproblem */
164 if (!(1 <= p && p <= tree->nslots))
165 err: xerror("glp_ios_next_node: p = %d; invalid subproblem refer"
166 "ence number\n", p);
167 node = tree->slot[p].node;
168 if (node == NULL) goto err;
169 /* the specified subproblem must be active */
170 if (node->count != 0)
171 xerror("glp_ios_next_node: p = %d; subproblem not in the ac"
172 "tive list\n", p);
173 /* obtain pointer to the next active subproblem */
174 node = node->next;
175 }
176 /* return the reference number */
177 return node == NULL ? 0 : node->p;
178 }
179
180 /***********************************************************************
181 * NAME
182 *
183 * glp_ios_prev_node - determine previous active subproblem
184 *
185 * SYNOPSIS
186 *
187 * int glp_ios_prev_node(glp_tree *tree, int p);
188 *
189 * RETURNS
190 *
191 * If the parameter p is zero, the routine glp_ios_prev_node returns
192 * the reference number of the last active subproblem. However, if the
193 * tree is empty, zero is returned.
194 *
195 * If the parameter p is not zero, it must specify the reference number
196 * of some active subproblem, in which case the routine returns the
197 * reference number of the previous active subproblem. However, if there
198 * is no previous active subproblem in the list, zero is returned.
199 *
200 * All subproblems in the active list are ordered chronologically, i.e.
201 * subproblem A precedes subproblem B if A was created before B. */
202
203 int glp_ios_prev_node(glp_tree *tree, int p)
204 { IOSNPD *node;
205 if (p == 0)
206 { /* obtain pointer to the last active subproblem */
207 node = tree->tail;
208 }
209 else
210 { /* obtain pointer to the specified subproblem */
211 if (!(1 <= p && p <= tree->nslots))
212 err: xerror("glp_ios_prev_node: p = %d; invalid subproblem refer"
213 "ence number\n", p);
214 node = tree->slot[p].node;
215 if (node == NULL) goto err;
216 /* the specified subproblem must be active */
217 if (node->count != 0)
218 xerror("glp_ios_prev_node: p = %d; subproblem not in the ac"
219 "tive list\n", p);
220 /* obtain pointer to the previous active subproblem */
221 node = node->prev;
222 }
223 /* return the reference number */
224 return node == NULL ? 0 : node->p;
225 }
226
227 /***********************************************************************
228 * NAME
229 *
230 * glp_ios_up_node - determine parent subproblem
231 *
232 * SYNOPSIS
233 *
234 * int glp_ios_up_node(glp_tree *tree, int p);
235 *
236 * RETURNS
237 *
238 * The parameter p must specify the reference number of some (active or
239 * inactive) subproblem, in which case the routine iet_get_up_node
240 * returns the reference number of its parent subproblem. However, if
241 * the specified subproblem is the root of the tree and, therefore, has
242 * no parent, the routine returns zero. */
243
244 int glp_ios_up_node(glp_tree *tree, int p)
245 { IOSNPD *node;
246 /* obtain pointer to the specified subproblem */
247 if (!(1 <= p && p <= tree->nslots))
248 err: xerror("glp_ios_up_node: p = %d; invalid subproblem reference "
249 "number\n", p);
250 node = tree->slot[p].node;
251 if (node == NULL) goto err;
252 /* obtain pointer to the parent subproblem */
253 node = node->up;
254 /* return the reference number */
255 return node == NULL ? 0 : node->p;
256 }
257
258 /***********************************************************************
259 * NAME
260 *
261 * glp_ios_node_level - determine subproblem level
262 *
263 * SYNOPSIS
264 *
265 * int glp_ios_node_level(glp_tree *tree, int p);
266 *
267 * RETURNS
268 *
269 * The routine glp_ios_node_level returns the level of the subproblem,
270 * whose reference number is p, in the branch-and-bound tree. (The root
271 * subproblem has level 0, and the level of any other subproblem is the
272 * level of its parent plus one.) */
273
274 int glp_ios_node_level(glp_tree *tree, int p)
275 { IOSNPD *node;
276 /* obtain pointer to the specified subproblem */
277 if (!(1 <= p && p <= tree->nslots))
278 err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen"
279 "ce number\n", p);
280 node = tree->slot[p].node;
281 if (node == NULL) goto err;
282 /* return the node level */
283 return node->level;
284 }
285
286 /***********************************************************************
287 * NAME
288 *
289 * glp_ios_node_bound - determine subproblem local bound
290 *
291 * SYNOPSIS
292 *
293 * double glp_ios_node_bound(glp_tree *tree, int p);
294 *
295 * RETURNS
296 *
297 * The routine glp_ios_node_bound returns the local bound for (active or
298 * inactive) subproblem, whose reference number is p.
299 *
300 * COMMENTS
301 *
302 * The local bound for subproblem p is an lower (minimization) or upper
303 * (maximization) bound for integer optimal solution to this subproblem
304 * (not to the original problem). This bound is local in the sense that
305 * only subproblems in the subtree rooted at node p cannot have better
306 * integer feasible solutions.
307 *
308 * On creating a subproblem (due to the branching step) its local bound
309 * is inherited from its parent and then may get only stronger (never
310 * weaker). For the root subproblem its local bound is initially set to
311 * -DBL_MAX (minimization) or +DBL_MAX (maximization) and then improved
312 * as the root LP relaxation has been solved.
313 *
314 * Note that the local bound is not necessarily the optimal objective
315 * value to corresponding LP relaxation; it may be stronger. */
316
317 double glp_ios_node_bound(glp_tree *tree, int p)
318 { IOSNPD *node;
319 /* obtain pointer to the specified subproblem */
320 if (!(1 <= p && p <= tree->nslots))
321 err: xerror("glp_ios_node_bound: p = %d; invalid subproblem referen"
322 "ce number\n", p);
323 node = tree->slot[p].node;
324 if (node == NULL) goto err;
325 /* return the node local bound */
326 return node->bound;
327 }
328
329 /***********************************************************************
330 * NAME
331 *
332 * glp_ios_best_node - find active subproblem with best local bound
333 *
334 * SYNOPSIS
335 *
336 * int glp_ios_best_node(glp_tree *tree);
337 *
338 * RETURNS
339 *
340 * The routine glp_ios_best_node returns the reference number of the
341 * active subproblem, whose local bound is best (i.e. smallest in case
342 * of minimization or largest in case of maximization). However, if the
343 * tree is empty, the routine returns zero.
344 *
345 * COMMENTS
346 *
347 * The best local bound is an lower (minimization) or upper
348 * (maximization) bound for integer optimal solution to the original
349 * MIP problem. */
350
351 int glp_ios_best_node(glp_tree *tree)
352 { return
353 ios_best_node(tree);
354 }
355
356 /***********************************************************************
357 * NAME
358 *
359 * glp_ios_mip_gap - compute relative MIP gap
360 *
361 * SYNOPSIS
362 *
363 * double glp_ios_mip_gap(glp_tree *tree);
364 *
365 * DESCRIPTION
366 *
367 * The routine glp_ios_mip_gap computes the relative MIP gap with the
368 * following formula:
369 *
370 * gap = |best_mip - best_bnd| / (|best_mip| + DBL_EPSILON),
371 *
372 * where best_mip is the best integer feasible solution found so far,
373 * best_bnd is the best (global) bound. If no integer feasible solution
374 * has been found yet, gap is set to DBL_MAX.
375 *
376 * RETURNS
377 *
378 * The routine glp_ios_mip_gap returns the relative MIP gap. */
379
380 double glp_ios_mip_gap(glp_tree *tree)
381 { return
382 ios_relative_gap(tree);
383 }
384
385 /***********************************************************************
386 * NAME
387 *
388 * glp_ios_node_data - access subproblem application-specific data
389 *
390 * SYNOPSIS
391 *
392 * void *glp_ios_node_data(glp_tree *tree, int p);
393 *
394 * DESCRIPTION
395 *
396 * The routine glp_ios_node_data allows the application accessing a
397 * memory block allocated for the subproblem (which may be active or
398 * inactive), whose reference number is p.
399 *
400 * The size of the block is defined by the control parameter cb_size
401 * passed to the routine glp_intopt. The block is initialized by binary
402 * zeros on creating corresponding subproblem, and its contents is kept
403 * until the subproblem will be removed from the tree.
404 *
405 * The application may use these memory blocks to store specific data
406 * for each subproblem.
407 *
408 * RETURNS
409 *
410 * The routine glp_ios_node_data returns a pointer to the memory block
411 * for the specified subproblem. Note that if cb_size = 0, the routine
412 * returns a null pointer. */
413
414 void *glp_ios_node_data(glp_tree *tree, int p)
415 { IOSNPD *node;
416 /* obtain pointer to the specified subproblem */
417 if (!(1 <= p && p <= tree->nslots))
418 err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen"
419 "ce number\n", p);
420 node = tree->slot[p].node;
421 if (node == NULL) goto err;
422 /* return pointer to the application-specific data */
423 return node->data;
424 }
425
426 /***********************************************************************
427 * NAME
428 *
429 * glp_ios_row_attr - retrieve additional row attributes
430 *
431 * SYNOPSIS
432 *
433 * void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr);
434 *
435 * DESCRIPTION
436 *
437 * The routine glp_ios_row_attr retrieves additional attributes of row
438 * i and stores them in the structure glp_attr. */
439
440 void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr)
441 { GLPROW *row;
442 if (!(1 <= i && i <= tree->mip->m))
443 xerror("glp_ios_row_attr: i = %d; row number out of range\n",
444 i);
445 row = tree->mip->row[i];
446 attr->level = row->level;
447 attr->origin = row->origin;
448 attr->klass = row->klass;
449 return;
450 }
451
452 /**********************************************************************/
453
454 int glp_ios_pool_size(glp_tree *tree)
455 { /* determine current size of the cut pool */
456 if (tree->reason != GLP_ICUTGEN)
457 xerror("glp_ios_pool_size: operation not allowed\n");
458 xassert(tree->local != NULL);
459 return tree->local->size;
460 }
461
462 /**********************************************************************/
463
464 int glp_ios_add_row(glp_tree *tree,
465 const char *name, int klass, int flags, int len, const int ind[],
466 const double val[], int type, double rhs)
467 { /* add row (constraint) to the cut pool */
468 int num;
469 if (tree->reason != GLP_ICUTGEN)
470 xerror("glp_ios_add_row: operation not allowed\n");
471 xassert(tree->local != NULL);
472 num = ios_add_row(tree, tree->local, name, klass, flags, len,
473 ind, val, type, rhs);
474 return num;
475 }
476
477 /**********************************************************************/
478
479 void glp_ios_del_row(glp_tree *tree, int i)
480 { /* remove row (constraint) from the cut pool */
481 if (tree->reason != GLP_ICUTGEN)
482 xerror("glp_ios_del_row: operation not allowed\n");
483 ios_del_row(tree, tree->local, i);
484 return;
485 }
486
487 /**********************************************************************/
488
489 void glp_ios_clear_pool(glp_tree *tree)
490 { /* remove all rows (constraints) from the cut pool */
491 if (tree->reason != GLP_ICUTGEN)
492 xerror("glp_ios_clear_pool: operation not allowed\n");
493 ios_clear_pool(tree, tree->local);
494 return;
495 }
496
497 /***********************************************************************
498 * NAME
499 *
500 * glp_ios_can_branch - check if can branch upon specified variable
501 *
502 * SYNOPSIS
503 *
504 * int glp_ios_can_branch(glp_tree *tree, int j);
505 *
506 * RETURNS
507 *
508 * If j-th variable (column) can be used to branch upon, the routine
509 * glp_ios_can_branch returns non-zero, otherwise zero. */
510
511 int glp_ios_can_branch(glp_tree *tree, int j)
512 { if (!(1 <= j && j <= tree->mip->n))
513 xerror("glp_ios_can_branch: j = %d; column number out of range"
514 "\n", j);
515 return tree->non_int[j];
516 }
517
518 /***********************************************************************
519 * NAME
520 *
521 * glp_ios_branch_upon - choose variable to branch upon
522 *
523 * SYNOPSIS
524 *
525 * void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
526 *
527 * DESCRIPTION
528 *
529 * The routine glp_ios_branch_upon can be called from the user-defined
530 * callback routine in response to the reason GLP_IBRANCH to choose a
531 * branching variable, whose ordinal number is j. Should note that only
532 * variables, for which the routine glp_ios_can_branch returns non-zero,
533 * can be used to branch upon.
534 *
535 * The parameter sel is a flag that indicates which branch (subproblem)
536 * should be selected next to continue the search:
537 *
538 * GLP_DN_BRNCH - select down-branch;
539 * GLP_UP_BRNCH - select up-branch;
540 * GLP_NO_BRNCH - use general selection technique. */
541
542 void glp_ios_branch_upon(glp_tree *tree, int j, int sel)
543 { if (!(1 <= j && j <= tree->mip->n))
544 xerror("glp_ios_branch_upon: j = %d; column number out of rang"
545 "e\n", j);
546 if (!(sel == GLP_DN_BRNCH || sel == GLP_UP_BRNCH ||
547 sel == GLP_NO_BRNCH))
548 xerror("glp_ios_branch_upon: sel = %d: invalid branch selectio"
549 "n flag\n", sel);
550 if (!(tree->non_int[j]))
551 xerror("glp_ios_branch_upon: j = %d; variable cannot be used t"
552 "o branch upon\n", j);
553 if (tree->br_var != 0)
554 xerror("glp_ios_branch_upon: branching variable already chosen"
555 "\n");
556 tree->br_var = j;
557 tree->br_sel = sel;
558 return;
559 }
560
561 /***********************************************************************
562 * NAME
563 *
564 * glp_ios_select_node - select subproblem to continue the search
565 *
566 * SYNOPSIS
567 *
568 * void glp_ios_select_node(glp_tree *tree, int p);
569 *
570 * DESCRIPTION
571 *
572 * The routine glp_ios_select_node can be called from the user-defined
573 * callback routine in response to the reason GLP_ISELECT to select an
574 * active subproblem, whose reference number is p. The search will be
575 * continued from the subproblem selected. */
576
577 void glp_ios_select_node(glp_tree *tree, int p)
578 { IOSNPD *node;
579 /* obtain pointer to the specified subproblem */
580 if (!(1 <= p && p <= tree->nslots))
581 err: xerror("glp_ios_select_node: p = %d; invalid subproblem refere"
582 "nce number\n", p);
583 node = tree->slot[p].node;
584 if (node == NULL) goto err;
585 /* the specified subproblem must be active */
586 if (node->count != 0)
587 xerror("glp_ios_select_node: p = %d; subproblem not in the act"
588 "ive list\n", p);
589 /* no subproblem must be selected yet */
590 if (tree->next_p != 0)
591 xerror("glp_ios_select_node: subproblem already selected\n");
592 /* select the specified subproblem to continue the search */
593 tree->next_p = p;
594 return;
595 }
596
597 /***********************************************************************
598 * NAME
599 *
600 * glp_ios_heur_sol - provide solution found by heuristic
601 *
602 * SYNOPSIS
603 *
604 * int glp_ios_heur_sol(glp_tree *tree, const double x[]);
605 *
606 * DESCRIPTION
607 *
608 * The routine glp_ios_heur_sol can be called from the user-defined
609 * callback routine in response to the reason GLP_IHEUR to provide an
610 * integer feasible solution found by a primal heuristic.
611 *
612 * Primal values of *all* variables (columns) found by the heuristic
613 * should be placed in locations x[1], ..., x[n], where n is the number
614 * of columns in the original problem object. Note that the routine
615 * glp_ios_heur_sol *does not* check primal feasibility of the solution
616 * provided.
617 *
618 * Using the solution passed in the array x the routine computes value
619 * of the objective function. If the objective value is better than the
620 * best known integer feasible solution, the routine computes values of
621 * auxiliary variables (rows) and stores all solution components in the
622 * problem object.
623 *
624 * RETURNS
625 *
626 * If the provided solution is accepted, the routine glp_ios_heur_sol
627 * returns zero. Otherwise, if the provided solution is rejected, the
628 * routine returns non-zero. */
629
630 int glp_ios_heur_sol(glp_tree *tree, const double x[])
631 { glp_prob *mip = tree->mip;
632 int m = tree->orig_m;
633 int n = tree->n;
634 int i, j;
635 double obj;
636 xassert(mip->m >= m);
637 xassert(mip->n == n);
638 /* check values of integer variables and compute value of the
639 objective function */
640 obj = mip->c0;
641 for (j = 1; j <= n; j++)
642 { GLPCOL *col = mip->col[j];
643 if (col->kind == GLP_IV)
644 { /* provided value must be integral */
645 if (x[j] != floor(x[j])) return 1;
646 }
647 obj += col->coef * x[j];
648 }
649 /* check if the provided solution is better than the best known
650 integer feasible solution */
651 if (mip->mip_stat == GLP_FEAS)
652 { switch (mip->dir)
653 { case GLP_MIN:
654 if (obj >= tree->mip->mip_obj) return 1;
655 break;
656 case GLP_MAX:
657 if (obj <= tree->mip->mip_obj) return 1;
658 break;
659 default:
660 xassert(mip != mip);
661 }
662 }
663 /* it is better; store it in the problem object */
664 if (tree->parm->msg_lev >= GLP_MSG_ON)
665 xprintf("Solution found by heuristic: %.12g\n", obj);
666 mip->mip_stat = GLP_FEAS;
667 mip->mip_obj = obj;
668 for (j = 1; j <= n; j++)
669 mip->col[j]->mipx = x[j];
670 for (i = 1; i <= m; i++)
671 { GLPROW *row = mip->row[i];
672 GLPAIJ *aij;
673 row->mipx = 0.0;
674 for (aij = row->ptr; aij != NULL; aij = aij->r_next)
675 row->mipx += aij->val * aij->col->mipx;
676 }
677 return 0;
678 }
679
680 /***********************************************************************
681 * NAME
682 *
683 * glp_ios_terminate - terminate the solution process.
684 *
685 * SYNOPSIS
686 *
687 * void glp_ios_terminate(glp_tree *tree);
688 *
689 * DESCRIPTION
690 *
691 * The routine glp_ios_terminate sets a flag indicating that the MIP
692 * solver should prematurely terminate the search. */
693
694 void glp_ios_terminate(glp_tree *tree)
695 { if (tree->parm->msg_lev >= GLP_MSG_DBG)
696 xprintf("The search is prematurely terminated due to applicati"
697 "on request\n");
698 tree->stop = 1;
699 return;
700 }
701
702 /* eof */