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