1 /* glpios.h (integer optimization suite) */ 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 #ifndef GLPIOS_H 26 #define GLPIOS_H 27 28 #define GLP_TREE_DEFINED 29 typedef struct glp_tree glp_tree; 30 31 #include "glpapi.h" 32 33 typedef struct IOSLOT IOSLOT; 34 typedef struct IOSNPD IOSNPD; 35 typedef struct IOSBND IOSBND; 36 typedef struct IOSTAT IOSTAT; 37 typedef struct IOSROW IOSROW; 38 typedef struct IOSAIJ IOSAIJ; 39 typedef struct IOSPOOL IOSPOOL; 40 typedef struct IOSCUT IOSCUT; 41 42 struct glp_tree 43 { /* branch-and-bound tree */ 44 int magic; 45 /* magic value used for debugging */ 46 DMP *pool; 47 /* memory pool to store all IOS components */ 48 int n; 49 /* number of columns (variables) */ 50 /*--------------------------------------------------------------*/ 51 /* problem components corresponding to the original MIP and its 52 LP relaxation (used to restore the original problem object on 53 exit from the solver) */ 54 int orig_m; 55 /* number of rows */ 56 unsigned char *orig_type; /* uchar orig_type[1+orig_m+n]; */ 57 /* types of all variables */ 58 double *orig_lb; /* double orig_lb[1+orig_m+n]; */ 59 /* lower bounds of all variables */ 60 double *orig_ub; /* double orig_ub[1+orig_m+n]; */ 61 /* upper bounds of all variables */ 62 unsigned char *orig_stat; /* uchar orig_stat[1+orig_m+n]; */ 63 /* statuses of all variables */ 64 double *orig_prim; /* double orig_prim[1+orig_m+n]; */ 65 /* primal values of all variables */ 66 double *orig_dual; /* double orig_dual[1+orig_m+n]; */ 67 /* dual values of all variables */ 68 double orig_obj; 69 /* optimal objective value for LP relaxation */ 70 /*--------------------------------------------------------------*/ 71 /* branch-and-bound tree */ 72 int nslots; 73 /* length of the array of slots (enlarged automatically) */ 74 int avail; 75 /* index of the first free slot; 0 means all slots are in use */ 76 IOSLOT *slot; /* IOSLOT slot[1+nslots]; */ 77 /* array of slots: 78 slot[0] is not used; 79 slot[p], 1 <= p <= nslots, either contains a pointer to some 80 node of the branch-and-bound tree, in which case p is used on 81 API level as the reference number of corresponding subproblem, 82 or is free; all free slots are linked into single linked list; 83 slot[1] always contains a pointer to the root node (it is free 84 only if the tree is empty) */ 85 IOSNPD *head; 86 /* pointer to the head of the active list */ 87 IOSNPD *tail; 88 /* pointer to the tail of the active list */ 89 /* the active list is a doubly linked list of active subproblems 90 which correspond to leaves of the tree; all subproblems in the 91 active list are ordered chronologically (each a new subproblem 92 is always added to the tail of the list) */ 93 int a_cnt; 94 /* current number of active nodes (including the current one) */ 95 int n_cnt; 96 /* current number of all (active and inactive) nodes */ 97 int t_cnt; 98 /* total number of nodes including those which have been already 99 removed from the tree; this count is increased by one whenever 100 a new node is created and never decreased */ 101 /*--------------------------------------------------------------*/ 102 /* problem components corresponding to the root subproblem */ 103 int root_m; 104 /* number of rows */ 105 unsigned char *root_type; /* uchar root_type[1+root_m+n]; */ 106 /* types of all variables */ 107 double *root_lb; /* double root_lb[1+root_m+n]; */ 108 /* lower bounds of all variables */ 109 double *root_ub; /* double root_ub[1+root_m+n]; */ 110 /* upper bounds of all variables */ 111 unsigned char *root_stat; /* uchar root_stat[1+root_m+n]; */ 112 /* statuses of all variables */ 113 /*--------------------------------------------------------------*/ 114 /* current subproblem and its LP relaxation */ 115 IOSNPD *curr; 116 /* pointer to the current subproblem (which can be only active); 117 NULL means the current subproblem does not exist */ 118 glp_prob *mip; 119 /* original problem object passed to the solver; if the current 120 subproblem exists, its LP segment corresponds to LP relaxation 121 of the current subproblem; if the current subproblem does not 122 exist, its LP segment corresponds to LP relaxation of the root 123 subproblem (note that the root subproblem may differ from the 124 original MIP, because it may be preprocessed and/or may have 125 additional rows) */ 126 unsigned char *non_int; /* uchar non_int[1+n]; */ 127 /* these column flags are set each time when LP relaxation of the 128 current subproblem has been solved; 129 non_int[0] is not used; 130 non_int[j], 1 <= j <= n, is j-th column flag; if this flag is 131 set, corresponding variable is required to be integer, but its 132 value in basic solution is fractional */ 133 /*--------------------------------------------------------------*/ 134 /* problem components corresponding to the parent (predecessor) 135 subproblem for the current subproblem; used to inspect changes 136 on freezing the current subproblem */ 137 int pred_m; 138 /* number of rows */ 139 int pred_max; 140 /* length of the following four arrays (enlarged automatically), 141 pred_max >= pred_m + n */ 142 unsigned char *pred_type; /* uchar pred_type[1+pred_m+n]; */ 143 /* types of all variables */ 144 double *pred_lb; /* double pred_lb[1+pred_m+n]; */ 145 /* lower bounds of all variables */ 146 double *pred_ub; /* double pred_ub[1+pred_m+n]; */ 147 /* upper bounds of all variables */ 148 unsigned char *pred_stat; /* uchar pred_stat[1+pred_m+n]; */ 149 /* statuses of all variables */ 150 /****************************************************************/ 151 /* built-in cut generators segment */ 152 IOSPOOL *local; 153 /* local cut pool */ 154 void *mir_gen; 155 /* pointer to working area used by the MIR cut generator */ 156 void *clq_gen; 157 /* pointer to working area used by the clique cut generator */ 158 /*--------------------------------------------------------------*/ 159 void *pcost; 160 /* pointer to working area used on pseudocost branching */ 161 int *iwrk; /* int iwrk[1+n]; */ 162 /* working array */ 163 double *dwrk; /* double dwrk[1+n]; */ 164 /* working array */ 165 /*--------------------------------------------------------------*/ 166 /* control parameters and statistics */ 167 const glp_iocp *parm; 168 /* copy of control parameters passed to the solver */ 169 glp_long tm_beg; 170 /* starting time of the search, in seconds; the total time of the 171 search is the difference between xtime() and tm_beg */ 172 glp_long tm_lag; 173 /* the most recent time, in seconds, at which the progress of the 174 the search was displayed */ 175 int sol_cnt; 176 /* number of integer feasible solutions found */ 177 /*--------------------------------------------------------------*/ 178 /* advanced solver interface */ 179 int reason; 180 /* flag indicating the reason why the callback routine is being 181 called (see glpk.h) */ 182 int stop; 183 /* flag indicating that the callback routine requires premature 184 termination of the search */ 185 int next_p; 186 /* reference number of active subproblem selected to continue 187 the search; 0 means no subproblem has been selected */ 188 int reopt; 189 /* flag indicating that the current LP relaxation needs to be 190 re-optimized */ 191 int reinv; 192 /* flag indicating that some (non-active) rows were removed from 193 the current LP relaxation, so if there no new rows appear, the 194 basis must be re-factorized */ 195 int br_var; 196 /* the number of variable chosen to branch on */ 197 int br_sel; 198 /* flag indicating which branch (subproblem) is suggested to be 199 selected to continue the search: 200 GLP_DN_BRNCH - select down-branch 201 GLP_UP_BRNCH - select up-branch 202 GLP_NO_BRNCH - use general selection technique */ 203 int child; 204 /* subproblem reference number corresponding to br_sel */ 205 }; 206 207 struct IOSLOT 208 { /* node subproblem slot */ 209 IOSNPD *node; 210 /* pointer to subproblem descriptor; NULL means free slot */ 211 int next; 212 /* index of another free slot (only if this slot is free) */ 213 }; 214 215 struct IOSNPD 216 { /* node subproblem descriptor */ 217 int p; 218 /* subproblem reference number (it is the index to corresponding 219 slot, i.e. slot[p] points to this descriptor) */ 220 IOSNPD *up; 221 /* pointer to the parent subproblem; NULL means this node is the 222 root of the tree, in which case p = 1 */ 223 int level; 224 /* node level (the root node has level 0) */ 225 int count; 226 /* if count = 0, this subproblem is active; if count > 0, this 227 subproblem is inactive, in which case count is the number of 228 its child subproblems */ 229 /* the following three linked lists are destroyed on reviving and 230 built anew on freezing the subproblem: */ 231 IOSBND *b_ptr; 232 /* linked list of rows and columns of the parent subproblem whose 233 types and bounds were changed */ 234 IOSTAT *s_ptr; 235 /* linked list of rows and columns of the parent subproblem whose 236 statuses were changed */ 237 IOSROW *r_ptr; 238 /* linked list of rows (cuts) added to the parent subproblem */ 239 int solved; 240 /* how many times LP relaxation of this subproblem was solved; 241 for inactive subproblem this count is always non-zero; 242 for active subproblem, which is not current, this count may be 243 non-zero, if the subproblem was temporarily suspended */ 244 double lp_obj; 245 /* optimal objective value to LP relaxation of this subproblem; 246 on creating a subproblem this value is inherited from its 247 parent; for the root subproblem, which has no parent, this 248 value is initially set to -DBL_MAX (minimization) or +DBL_MAX 249 (maximization); each time the subproblem is re-optimized, this 250 value is appropriately changed */ 251 double bound; 252 /* local lower (minimization) or upper (maximization) bound for 253 integer optimal solution to *this* subproblem; this bound is 254 local in the sense that only subproblems in the subtree rooted 255 at this node cannot have better integer feasible solutions; 256 on creating a subproblem its local bound is inherited from its 257 parent and then can be made stronger (never weaker); for the 258 root subproblem its local bound is initially set to -DBL_MAX 259 (minimization) or +DBL_MAX (maximization) and then improved as 260 the root LP relaxation has been solved */ 261 /* the following two quantities are defined only if LP relaxation 262 of this subproblem was solved at least once (solved > 0): */ 263 int ii_cnt; 264 /* number of integer variables whose value in optimal solution to 265 LP relaxation of this subproblem is fractional */ 266 double ii_sum; 267 /* sum of integer infeasibilities */ 268 #if 1 /* 30/XI-2009 */ 269 int changed; 270 /* how many times this subproblem was re-formulated (by adding 271 cutting plane constraints) */ 272 #endif 273 int br_var; 274 /* ordinal number of branching variable, 1 <= br_var <= n, used 275 to split this subproblem; 0 means that either this subproblem 276 is active or branching was made on a constraint */ 277 double br_val; 278 /* (fractional) value of branching variable in optimal solution 279 to final LP relaxation of this subproblem */ 280 void *data; /* char data[tree->cb_size]; */ 281 /* pointer to the application-specific data */ 282 IOSNPD *temp; 283 /* working pointer used by some routines */ 284 IOSNPD *prev; 285 /* pointer to previous subproblem in the active list */ 286 IOSNPD *next; 287 /* pointer to next subproblem in the active list */ 288 }; 289 290 struct IOSBND 291 { /* bounds change entry */ 292 int k; 293 /* ordinal number of corresponding row (1 <= k <= m) or column 294 (m+1 <= k <= m+n), where m and n are the number of rows and 295 columns, resp., in the parent subproblem */ 296 unsigned char type; 297 /* new type */ 298 double lb; 299 /* new lower bound */ 300 double ub; 301 /* new upper bound */ 302 IOSBND *next; 303 /* pointer to next entry for the same subproblem */ 304 }; 305 306 struct IOSTAT 307 { /* status change entry */ 308 int k; 309 /* ordinal number of corresponding row (1 <= k <= m) or column 310 (m+1 <= k <= m+n), where m and n are the number of rows and 311 columns, resp., in the parent subproblem */ 312 unsigned char stat; 313 /* new status */ 314 IOSTAT *next; 315 /* pointer to next entry for the same subproblem */ 316 }; 317 318 struct IOSROW 319 { /* row (constraint) addition entry */ 320 char *name; 321 /* row name or NULL */ 322 unsigned char origin; 323 /* row origin flag (see glp_attr.origin) */ 324 unsigned char klass; 325 /* row class descriptor (see glp_attr.klass) */ 326 unsigned char type; 327 /* row type (GLP_LO, GLP_UP, etc.) */ 328 double lb; 329 /* row lower bound */ 330 double ub; 331 /* row upper bound */ 332 IOSAIJ *ptr; 333 /* pointer to the row coefficient list */ 334 double rii; 335 /* row scale factor */ 336 unsigned char stat; 337 /* row status (GLP_BS, GLP_NL, etc.) */ 338 IOSROW *next; 339 /* pointer to next entry for the same subproblem */ 340 }; 341 342 struct IOSAIJ 343 { /* constraint coefficient */ 344 int j; 345 /* variable (column) number, 1 <= j <= n */ 346 double val; 347 /* non-zero coefficient value */ 348 IOSAIJ *next; 349 /* pointer to next coefficient for the same row */ 350 }; 351 352 struct IOSPOOL 353 { /* cut pool */ 354 int size; 355 /* pool size = number of cuts in the pool */ 356 IOSCUT *head; 357 /* pointer to the first cut */ 358 IOSCUT *tail; 359 /* pointer to the last cut */ 360 int ord; 361 /* ordinal number of the current cut, 1 <= ord <= size */ 362 IOSCUT *curr; 363 /* pointer to the current cut */ 364 }; 365 366 struct IOSCUT 367 { /* cut (cutting plane constraint) */ 368 char *name; 369 /* cut name or NULL */ 370 unsigned char klass; 371 /* cut class descriptor (see glp_attr.klass) */ 372 IOSAIJ *ptr; 373 /* pointer to the cut coefficient list */ 374 unsigned char type; 375 /* cut type: 376 GLP_LO: sum a[j] * x[j] >= b 377 GLP_UP: sum a[j] * x[j] <= b 378 GLP_FX: sum a[j] * x[j] = b */ 379 double rhs; 380 /* cut right-hand side */ 381 IOSCUT *prev; 382 /* pointer to previous cut */ 383 IOSCUT *next; 384 /* pointer to next cut */ 385 }; 386 387 #define ios_create_tree _glp_ios_create_tree 388 glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm); 389 /* create branch-and-bound tree */ 390 391 #define ios_revive_node _glp_ios_revive_node 392 void ios_revive_node(glp_tree *tree, int p); 393 /* revive specified subproblem */ 394 395 #define ios_freeze_node _glp_ios_freeze_node 396 void ios_freeze_node(glp_tree *tree); 397 /* freeze current subproblem */ 398 399 #define ios_clone_node _glp_ios_clone_node 400 void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]); 401 /* clone specified subproblem */ 402 403 #define ios_delete_node _glp_ios_delete_node 404 void ios_delete_node(glp_tree *tree, int p); 405 /* delete specified subproblem */ 406 407 #define ios_delete_tree _glp_ios_delete_tree 408 void ios_delete_tree(glp_tree *tree); 409 /* delete branch-and-bound tree */ 410 411 #define ios_eval_degrad _glp_ios_eval_degrad 412 void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up); 413 /* estimate obj. degrad. for down- and up-branches */ 414 415 #define ios_round_bound _glp_ios_round_bound 416 double ios_round_bound(glp_tree *tree, double bound); 417 /* improve local bound by rounding */ 418 419 #define ios_is_hopeful _glp_ios_is_hopeful 420 int ios_is_hopeful(glp_tree *tree, double bound); 421 /* check if subproblem is hopeful */ 422 423 #define ios_best_node _glp_ios_best_node 424 int ios_best_node(glp_tree *tree); 425 /* find active node with best local bound */ 426 427 #define ios_relative_gap _glp_ios_relative_gap 428 double ios_relative_gap(glp_tree *tree); 429 /* compute relative mip gap */ 430 431 #define ios_solve_node _glp_ios_solve_node 432 int ios_solve_node(glp_tree *tree); 433 /* solve LP relaxation of current subproblem */ 434 435 #define ios_create_pool _glp_ios_create_pool 436 IOSPOOL *ios_create_pool(glp_tree *tree); 437 /* create cut pool */ 438 439 #define ios_add_row _glp_ios_add_row 440 int ios_add_row(glp_tree *tree, IOSPOOL *pool, 441 const char *name, int klass, int flags, int len, const int ind[], 442 const double val[], int type, double rhs); 443 /* add row (constraint) to the cut pool */ 444 445 #define ios_find_row _glp_ios_find_row 446 IOSCUT *ios_find_row(IOSPOOL *pool, int i); 447 /* find row (constraint) in the cut pool */ 448 449 #define ios_del_row _glp_ios_del_row 450 void ios_del_row(glp_tree *tree, IOSPOOL *pool, int i); 451 /* remove row (constraint) from the cut pool */ 452 453 #define ios_clear_pool _glp_ios_clear_pool 454 void ios_clear_pool(glp_tree *tree, IOSPOOL *pool); 455 /* remove all rows (constraints) from the cut pool */ 456 457 #define ios_delete_pool _glp_ios_delete_pool 458 void ios_delete_pool(glp_tree *tree, IOSPOOL *pool); 459 /* delete cut pool */ 460 461 #define ios_preprocess_node _glp_ios_preprocess_node 462 int ios_preprocess_node(glp_tree *tree, int max_pass); 463 /* preprocess current subproblem */ 464 465 #define ios_driver _glp_ios_driver 466 int ios_driver(glp_tree *tree); 467 /* branch-and-bound driver */ 468 469 /**********************************************************************/ 470 471 typedef struct IOSVEC IOSVEC; 472 473 struct IOSVEC 474 { /* sparse vector v = (v[j]) */ 475 int n; 476 /* dimension, n >= 0 */ 477 int nnz; 478 /* number of non-zero components, 0 <= nnz <= n */ 479 int *pos; /* int pos[1+n]; */ 480 /* pos[j] = k, 1 <= j <= n, is position of (non-zero) v[j] in the 481 arrays ind and val, where 1 <= k <= nnz; pos[j] = 0 means that 482 v[j] is structural zero */ 483 int *ind; /* int ind[1+n]; */ 484 /* ind[k] = j, 1 <= k <= nnz, is index of v[j] */ 485 double *val; /* double val[1+n]; */ 486 /* val[k], 1 <= k <= nnz, is a numeric value of v[j] */ 487 }; 488 489 #define ios_create_vec _glp_ios_create_vec 490 IOSVEC *ios_create_vec(int n); 491 /* create sparse vector */ 492 493 #define ios_check_vec _glp_ios_check_vec 494 void ios_check_vec(IOSVEC *v); 495 /* check that sparse vector has correct representation */ 496 497 #define ios_get_vj _glp_ios_get_vj 498 double ios_get_vj(IOSVEC *v, int j); 499 /* retrieve component of sparse vector */ 500 501 #define ios_set_vj _glp_ios_set_vj 502 void ios_set_vj(IOSVEC *v, int j, double val); 503 /* set/change component of sparse vector */ 504 505 #define ios_clear_vec _glp_ios_clear_vec 506 void ios_clear_vec(IOSVEC *v); 507 /* set all components of sparse vector to zero */ 508 509 #define ios_clean_vec _glp_ios_clean_vec 510 void ios_clean_vec(IOSVEC *v, double eps); 511 /* remove zero or small components from sparse vector */ 512 513 #define ios_copy_vec _glp_ios_copy_vec 514 void ios_copy_vec(IOSVEC *x, IOSVEC *y); 515 /* copy sparse vector (x := y) */ 516 517 #define ios_linear_comb _glp_ios_linear_comb 518 void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y); 519 /* compute linear combination (x := x + a * y) */ 520 521 #define ios_delete_vec _glp_ios_delete_vec 522 void ios_delete_vec(IOSVEC *v); 523 /* delete sparse vector */ 524 525 /**********************************************************************/ 526 527 #define ios_gmi_gen _glp_ios_gmi_gen 528 void ios_gmi_gen(glp_tree *tree); 529 /* generate Gomory's mixed integer cuts */ 530 531 #define ios_mir_init _glp_ios_mir_init 532 void *ios_mir_init(glp_tree *tree); 533 /* initialize MIR cut generator */ 534 535 #define ios_mir_gen _glp_ios_mir_gen 536 void ios_mir_gen(glp_tree *tree, void *gen); 537 /* generate MIR cuts */ 538 539 #define ios_mir_term _glp_ios_mir_term 540 void ios_mir_term(void *gen); 541 /* terminate MIR cut generator */ 542 543 #define ios_cov_gen _glp_ios_cov_gen 544 void ios_cov_gen(glp_tree *tree); 545 /* generate mixed cover cuts */ 546 547 #define ios_clq_init _glp_ios_clq_init 548 void *ios_clq_init(glp_tree *tree); 549 /* initialize clique cut generator */ 550 551 #define ios_clq_gen _glp_ios_clq_gen 552 void ios_clq_gen(glp_tree *tree, void *gen); 553 /* generate clique cuts */ 554 555 #define ios_clq_term _glp_ios_clq_term 556 void ios_clq_term(void *gen); 557 /* terminate clique cut generator */ 558 559 #define ios_pcost_init _glp_ios_pcost_init 560 void *ios_pcost_init(glp_tree *tree); 561 /* initialize working data used on pseudocost branching */ 562 563 #define ios_pcost_branch _glp_ios_pcost_branch 564 int ios_pcost_branch(glp_tree *T, int *next); 565 /* choose branching variable with pseudocost branching */ 566 567 #define ios_pcost_update _glp_ios_pcost_update 568 void ios_pcost_update(glp_tree *tree); 569 /* update history information for pseudocost branching */ 570 571 #define ios_pcost_free _glp_ios_pcost_free 572 void ios_pcost_free(glp_tree *tree); 573 /* free working area used on pseudocost branching */ 574 575 #define ios_feas_pump _glp_ios_feas_pump 576 void ios_feas_pump(glp_tree *T); 577 /* feasibility pump heuristic */ 578 579 #define ios_process_cuts _glp_ios_process_cuts 580 void ios_process_cuts(glp_tree *T); 581 /* process cuts stored in the local cut pool */ 582 583 #define ios_choose_node _glp_ios_choose_node 584 int ios_choose_node(glp_tree *T); 585 /* select subproblem to continue the search */ 586 587 #define ios_choose_var _glp_ios_choose_var 588 int ios_choose_var(glp_tree *T, int *next); 589 /* select variable to branch on */ 590 591 #endif 592 593 /* eof */ 594