1
2 /*
3 Mixed integer programming optimization drivers for lp_solve v5.0+
4 ----------------------------------------------------------------------------------
5 Author: Michel Berkelaar (to lp_solve v3.2)
6 Kjell Eikland (v4.0 and forward)
7 Contact:
8 License terms: LGPL.
9
10 Requires: string.h, float.h, commonlib.h, lp_lib.h, lp_report.h,
11 lp_simplex.h
12
13 Release notes:
14 v5.0.0 31 January 2004 New unit isolating B&B routines.
15 v5.0.1 01 February 2004 Complete rewrite into non-recursive version.
16 v5.0.2 05 April 2004 Expanded pseudocosting with options for MIP fraction
17 counts and "cost/benefit" ratio (KE special!).
18 Added GUB functionality based on SOS structures.
19 v5.0.3 1 May 2004 Changed routine names to be more intuitive.
20 v5.0.4 15 May 2004 Added functinality to pack bounds in order to
21 conserve memory in B&B-processing large MIP models.
22 v5.1.0 25 July 2004 Added functions for dynamic cut generation.
23 v5.2.0 15 December 2004 Added functions for reduced cost variable fixing
24 and converted to delta-model of B&B bound storage.
25 ----------------------------------------------------------------------------------
26 */
27
28 #include <string.h>
29 #include <float.h>
30 #include "commonlib.h"
31 #include "lp_lib.h"
32 #include "lp_scale.h"
33 #include "lp_report.h"
34 #include "lp_simplex.h"
35 #include "lp_mipbb.h"
36
37 #ifdef FORTIFY
38 # include "lp_fortify.h"
39 #endif
40
41
42 /* Allocation routine for the BB record structure */
create_BB(lprec * lp,BBrec * parentBB,MYBOOL dofullcopy)43 STATIC BBrec *create_BB(lprec *lp, BBrec *parentBB, MYBOOL dofullcopy)
44 {
45 BBrec *newBB;
46
47 newBB = (BBrec *) calloc(1, sizeof(*newBB));
48 if(newBB != NULL) {
49
50 if(parentBB == NULL) {
51 allocREAL(lp, &newBB->upbo, lp->sum + 1, FALSE);
52 allocREAL(lp, &newBB->lowbo, lp->sum + 1, FALSE);
53 MEMCOPY(newBB->upbo, lp->orig_upbo, lp->sum + 1);
54 MEMCOPY(newBB->lowbo, lp->orig_lowbo, lp->sum + 1);
55 }
56 else if(dofullcopy) {
57 allocREAL(lp, &newBB->upbo, lp->sum + 1, FALSE);
58 allocREAL(lp, &newBB->lowbo, lp->sum + 1, FALSE);
59 MEMCOPY(newBB->upbo, parentBB->upbo, lp->sum + 1);
60 MEMCOPY(newBB->lowbo, parentBB->lowbo, lp->sum + 1);
61 }
62 else {
63 newBB->upbo = parentBB->upbo;
64 newBB->lowbo = parentBB->lowbo;
65 }
66 newBB->contentmode = dofullcopy;
67
68 newBB->lp = lp;
69
70 /* Set parent by default, but not child */
71 newBB->parent = parentBB;
72
73 }
74 return( newBB );
75 }
76
77
78 /* Pushing and popping routines for the B&B structure */
79
push_BB(lprec * lp,BBrec * parentBB,int varno,int vartype,int varcus)80 STATIC BBrec *push_BB(lprec *lp, BBrec *parentBB, int varno, int vartype, int varcus)
81 /* Push ingoing bounds and B&B data onto the stack */
82 {
83 BBrec *newBB;
84
85 /* Do initialization and updates */
86 if(parentBB == NULL)
87 parentBB = lp->bb_bounds;
88 newBB = create_BB(lp, parentBB, FALSE);
89 if(newBB != NULL) {
90
91 newBB->varno = varno;
92 newBB->vartype = vartype;
93 newBB->lastvarcus = varcus;
94 incrementUndoLadder(lp->bb_lowerchange);
95 newBB->LBtrack++;
96 incrementUndoLadder(lp->bb_upperchange);
97 newBB->UBtrack++;
98
99 /* Adjust variable fixing/bound tightening based on the last reduced cost */
100 if((parentBB != NULL) && (parentBB->lastrcf > 0)) {
101 MYBOOL isINT;
102 int k, ii, nfixed = 0, ntighten = 0;
103 REAL deltaUL;
104
105 for(k = 1; k <= lp->nzdrow[0]; k++) {
106 ii = lp->nzdrow[k];
107 #ifdef UseMilpSlacksRCF /* Check if we should include ranged constraints */
108 isINT = FALSE;
109 #else
110 if(ii <= lp->rows)
111 continue;
112 isINT = is_int(lp, ii-lp->rows);
113 #endif
114 #ifndef UseMilpExpandedRCF /* Don't include non-integers if it is not defined */
115 if(!isINT)
116 continue;
117 #endif
118 switch(abs(rcfbound_BB(newBB, ii, isINT, &deltaUL, NULL))) {
119 case LE: SETMIN(deltaUL, newBB->upbo[ii]);
120 SETMAX(deltaUL, newBB->lowbo[ii]);
121 modifyUndoLadder(lp->bb_upperchange, ii, newBB->upbo, deltaUL);
122 break;
123 case GE: SETMAX(deltaUL, newBB->lowbo[ii]);
124 SETMIN(deltaUL, newBB->upbo[ii]);
125 modifyUndoLadder(lp->bb_lowerchange, ii, newBB->lowbo, deltaUL);
126 break;
127 default: continue;
128 }
129 if(newBB->upbo[ii] == newBB->lowbo[ii])
130 nfixed++;
131 else
132 ntighten++;
133 }
134 if(lp->bb_trace) {
135 report(lp, DETAILED,
136 "push_BB: Used reduced cost to fix %d variables and tighten %d bounds\n",
137 nfixed, ntighten);
138 }
139 }
140
141 /* Handle case where we are pushing at the end */
142 if(parentBB == lp->bb_bounds)
143 lp->bb_bounds = newBB;
144 /* Handle case where we are pushing in the middle */
145 else
146 newBB->child = parentBB->child;
147 if(parentBB != NULL)
148 parentBB->child = newBB;
149
150 lp->bb_level++;
151 if(lp->bb_level > lp->bb_maxlevel)
152 lp->bb_maxlevel = lp->bb_level;
153
154 if(!initbranches_BB(newBB))
155 newBB = pop_BB(newBB);
156 else if(MIP_count(lp) > 0) {
157 if( (lp->bb_level <= 1) && (lp->bb_varactive == NULL) &&
158 (!allocINT(lp, &lp->bb_varactive, lp->columns+1, TRUE) ||
159 !initcuts_BB(lp)) )
160 newBB = pop_BB(newBB);
161 if(varno > 0) {
162 lp->bb_varactive[varno-lp->rows]++;
163 }
164 }
165 }
166 return( newBB );
167 }
168
free_BB(BBrec ** BB)169 STATIC MYBOOL free_BB(BBrec **BB)
170 {
171 MYBOOL parentreturned = FALSE;
172
173 if((BB != NULL) && (*BB != NULL)) {
174 BBrec *parent = (*BB)->parent;
175
176 if((parent == NULL) || (*BB)->contentmode) {
177 FREE((*BB)->upbo);
178 FREE((*BB)->lowbo);
179 }
180 FREE((*BB)->varmanaged);
181 FREE(*BB);
182
183 parentreturned = (MYBOOL) (parent != NULL);
184 if(parentreturned)
185 *BB = parent;
186
187 }
188 return( parentreturned );
189 }
190
pop_BB(BBrec * BB)191 STATIC BBrec *pop_BB(BBrec *BB)
192 /* Pop / free the previously "pushed" / saved bounds */
193 {
194 int k;
195 BBrec *parentBB;
196 lprec *lp = BB->lp;
197
198 if(BB == NULL)
199 return( BB );
200
201 /* Handle case where we are popping the end of the chain */
202 parentBB = BB->parent;
203 if(BB == lp->bb_bounds) {
204 lp->bb_bounds = parentBB;
205 if(parentBB != NULL)
206 parentBB->child = NULL;
207 }
208 /* Handle case where we are popping inside or at the beginning of the chain */
209 else {
210 if(parentBB != NULL)
211 parentBB->child = BB->child;
212 if(BB->child != NULL)
213 BB->child->parent = parentBB;
214 }
215
216 /* Unwind other variables */
217 restoreUndoLadder(lp->bb_upperchange, BB->upbo);
218 for(; BB->UBtrack > 0; BB->UBtrack--) {
219 decrementUndoLadder(lp->bb_upperchange);
220 restoreUndoLadder(lp->bb_upperchange, BB->upbo);
221 }
222 restoreUndoLadder(lp->bb_lowerchange, BB->lowbo);
223 for(; BB->LBtrack > 0; BB->LBtrack--) {
224 decrementUndoLadder(lp->bb_lowerchange);
225 restoreUndoLadder(lp->bb_lowerchange, BB->lowbo);
226 }
227 lp->bb_level--;
228 k = BB->varno - lp->rows;
229 if(lp->bb_level == 0) {
230 if(lp->bb_varactive != NULL) {
231 FREE(lp->bb_varactive);
232 freecuts_BB(lp);
233 }
234 if(lp->int_vars+lp->sc_vars > 0)
235 free_pseudocost(lp);
236 pop_basis(lp, FALSE);
237 lp->rootbounds = NULL;
238 }
239 else
240 lp->bb_varactive[k]--;
241
242 /* Undo SOS/GUB markers */
243 if(BB->isSOS && (BB->vartype != BB_INT))
244 SOS_unmark(lp->SOS, 0, k);
245 else if(BB->isGUB)
246 SOS_unmark(lp->GUB, 0, k);
247
248 /* Undo the SC marker */
249 if(BB->sc_canset)
250 lp->sc_lobound[k] *= -1;
251
252 /* Pop the associated basis */
253 #if 1
254 /* Original version that does not restore previous basis */
255 pop_basis(lp, FALSE);
256 #else
257 /* Experimental version that restores previous basis */
258 pop_basis(lp, BB->isSOS);
259 #endif
260
261 /* Finally free the B&B object */
262 free_BB(&BB);
263
264 /* Return the parent BB */
265 return( parentBB );
266 }
267
268 /* Here are heuristic routines to see if we need bother with branching further
269
270 1. A probing routine to see of the best OF can be better than incumbent
271 2. A presolve routine to fix other variables and detect infeasibility
272
273 THIS IS INACTIVE CODE, PLACEHOLDERS FOR FUTURE DEVELOPMENT!!! */
probe_BB(BBrec * BB)274 STATIC REAL probe_BB(BBrec *BB)
275 {
276 int i, ii;
277 REAL coefOF, sum = 0;
278 lprec *lp = BB->lp;
279
280 /* Loop over all ints to see if the best possible solution
281 stands any chance of being better than the incumbent solution */
282 if(lp->solutioncount == 0)
283 return( lp->infinite );
284 for(i = 1; i <= lp->columns; i++) {
285 if(!is_int(lp, i))
286 continue;
287 ii = lp->rows + i;
288 coefOF = lp->obj[i];
289 if(coefOF < 0) {
290 if(is_infinite(lp, BB->lowbo[ii]))
291 return( lp->infinite );
292 sum += coefOF * (lp->solution[ii]-BB->lowbo[ii]);
293 }
294 else {
295 if(is_infinite(lp, BB->upbo[ii]))
296 return( lp->infinite );
297 sum += coefOF * (BB->upbo[ii] - lp->solution[ii]);
298 }
299 }
300 return( sum );
301 }
302
presolve_BB(BBrec * BB)303 STATIC REAL presolve_BB(BBrec *BB)
304 {
305 return( 0 );
306 }
307
308 /* Node and branch management routines */
initbranches_BB(BBrec * BB)309 STATIC MYBOOL initbranches_BB(BBrec *BB)
310 {
311 REAL new_bound, temp;
312 int k;
313 lprec *lp = BB->lp;
314
315 /* Create and initialize local bounds and basis */
316 BB->nodestatus = NOTRUN;
317 BB->noderesult = lp->infinite;
318 push_basis(lp, NULL, NULL, NULL);
319
320 /* Set default number of branches at the current B&B branch */
321 if(BB->vartype == BB_REAL)
322 BB->nodesleft = 1;
323
324 else {
325 /* The default is a binary up-low branching */
326 BB->nodesleft = 2;
327
328 /* Initialize the MIP status code pair and set reference values */
329 k = BB->varno - lp->rows;
330 BB->lastsolution = lp->solution[BB->varno];
331
332 /* Determine if we must process in the B&B SOS mode */
333 BB->isSOS = (MYBOOL) ((BB->vartype == BB_SOS) || SOS_is_member(lp->SOS, 0, k));
334 #ifdef Paranoia
335 if((BB->vartype == BB_SOS) && !SOS_is_member(lp->SOS, 0, k))
336 report(lp, SEVERE, "initbranches_BB: Inconsistent identification of SOS variable %s (%d)\n",
337 get_col_name(lp, k), k);
338 #endif
339
340 /* Check if we have a GUB-member variable that needs a triple-branch */
341 BB->isGUB = (MYBOOL) ((BB->vartype == BB_INT) && SOS_can_activate(lp->GUB, 0, k));
342 if(BB->isGUB) {
343 /* Obtain variable index list from applicable GUB - now the first GUB is used,
344 but we could also consider selecting the longest */
345 BB->varmanaged = SOS_get_candidates(lp->GUB, -1, k, TRUE, BB->upbo, BB->lowbo);
346 BB->nodesleft++;
347 }
348
349
350 /* Set local pruning info, automatic, or user-defined strategy */
351 if(BB->vartype == BB_SOS) {
352 if(!SOS_can_activate(lp->SOS, 0, k)) {
353 BB->nodesleft--;
354 BB->isfloor = TRUE;
355 }
356 else
357 BB->isfloor = (MYBOOL) (BB->lastsolution == 0);
358 }
359
360 /* First check if the user wishes to select the branching direction */
361 else if(lp->bb_usebranch != NULL)
362 BB->isfloor = (MYBOOL) lp->bb_usebranch(lp, lp->bb_branchhandle, k);
363
364 /* Otherwise check if we should do automatic branching */
365 else if(get_var_branch(lp, k) == BRANCH_AUTOMATIC) {
366 new_bound = modf(BB->lastsolution/get_pseudorange(lp->bb_PseudoCost, k, BB->vartype), &temp);
367 #if 0
368 if(_isnan(new_bound))
369 new_bound = 0;
370 else if(new_bound < 0)
371 #endif
372 if (new_bound < 0)
373 new_bound += 1.0;
374 BB->isfloor = (MYBOOL) (new_bound <= 0.5);
375
376 /* Set direction by OF value; note that a zero-value in
377 the OF gives priority to floor_first = TRUE */
378 if(is_bb_mode(lp, NODE_GREEDYMODE)) {
379 if(is_bb_mode(lp, NODE_PSEUDOCOSTMODE))
380 BB->sc_bound = get_pseudonodecost(lp->bb_PseudoCost, k, BB->vartype, BB->lastsolution);
381 else
382 BB->sc_bound = mat_getitem(lp->matA, 0, k);
383 new_bound -= 0.5;
384 BB->sc_bound *= new_bound;
385 BB->isfloor = (MYBOOL) (BB->sc_bound > 0);
386 }
387 /* Set direction by pseudocost (normally used in tandem with NODE_PSEUDOxxxSELECT) */
388 else if(is_bb_mode(lp, NODE_PSEUDOCOSTMODE)) {
389 BB->isfloor = (MYBOOL) (get_pseudobranchcost(lp->bb_PseudoCost, k, TRUE) >
390 get_pseudobranchcost(lp->bb_PseudoCost, k, FALSE));
391 if(is_maxim(lp))
392 BB->isfloor = !BB->isfloor;
393 }
394
395 /* Check for reversal */
396 if(is_bb_mode(lp, NODE_BRANCHREVERSEMODE))
397 BB->isfloor = !BB->isfloor;
398 }
399 else
400 BB->isfloor = (MYBOOL) (get_var_branch(lp, k) == BRANCH_FLOOR);
401
402 /* SC logic: If the current SC variable value is in the [0..NZLOBOUND> range, then
403
404 UP: Set lower bound to NZLOBOUND, upper bound is the original
405 LO: Fix the variable by setting upper/lower bound to zero
406
407 ... indicate that the variable is B&B-active by reversing sign of sc_lobound[]. */
408 new_bound = fabs(lp->sc_lobound[k]);
409 BB->sc_bound = new_bound;
410 BB->sc_canset = (MYBOOL) (new_bound != 0);
411
412 /* Must make sure that we handle fractional lower bounds properly;
413 also to ensure that we do a full binary tree search */
414 new_bound = unscaled_value(lp, new_bound, BB->varno);
415 if(is_int(lp, k) && ((new_bound > 0) &&
416 (BB->lastsolution > floor(new_bound)))) {
417 if(BB->lastsolution < ceil(new_bound))
418 BB->lastsolution += 1;
419 modifyUndoLadder(lp->bb_lowerchange, BB->varno, BB->lowbo,
420 scaled_floor(lp, BB->varno, BB->lastsolution, 1));
421 }
422 }
423
424 /* Now initialize the brances and set to first */
425 return( fillbranches_BB(BB) );
426 }
427
fillbranches_BB(BBrec * BB)428 STATIC MYBOOL fillbranches_BB(BBrec *BB)
429 {
430 int K, k;
431 REAL ult_upbo, ult_lowbo;
432 REAL new_bound, SC_bound, intmargin = BB->lp->epsprimal;
433 lprec *lp = BB->lp;
434 MYBOOL OKstatus = FALSE;
435
436 if(lp->bb_break || userabort(lp, MSG_MILPSTRATEGY))
437 return( OKstatus );
438
439 K = BB->varno;
440 if(K > 0) {
441
442 /* Shortcut variables */
443 k = BB->varno - lp->rows;
444 ult_upbo = lp->orig_upbo[K];
445 ult_lowbo = lp->orig_lowbo[K];
446 SC_bound = unscaled_value(lp, BB->sc_bound, K);
447
448 /* First, establish the upper bound to be applied (when isfloor == TRUE)
449 --------------------------------------------------------------------- */
450 /*SetUB:*/
451 BB->UPbound = lp->infinite;
452
453 /* Handle SC-variables for the [0-LoBound> range */
454 if((SC_bound > 0) && (fabs(BB->lastsolution) < SC_bound)) {
455 new_bound = 0;
456 }
457 /* Handle pure integers (non-SOS, non-SC) */
458 else if(BB->vartype == BB_INT) {
459 #if 1
460 if(((ult_lowbo >= 0) &&
461 ((floor(BB->lastsolution) < /* Skip cases where the lower bound becomes violated */
462 unscaled_value(lp, MAX(ult_lowbo, fabs(lp->sc_lobound[k])), K)-intmargin))) ||
463 ((ult_upbo <= 0) && /* Was ((ult_lowbo < 0) && */
464 ((floor(BB->lastsolution) > /* Skip cases where the upper bound becomes violated */
465 unscaled_value(lp, MIN(ult_upbo, -fabs(lp->sc_lobound[k])), K)-intmargin)))) {
466 #else
467 if((floor(BB->lastsolution) < /* Skip cases where the lower bound becomes violated */
468 unscaled_value(lp, MAX(ult_lowbo, fabs(lp->sc_lobound[k])), K)-intmargin)) {
469 #endif
470 BB->nodesleft--;
471 goto SetLB;
472 }
473 new_bound = scaled_floor(lp, K, BB->lastsolution, 1);
474 }
475 else if(BB->isSOS) { /* Handle all SOS variants */
476 new_bound = ult_lowbo;
477 if(is_int(lp, k))
478 new_bound = scaled_ceil(lp, K, unscaled_value(lp, new_bound, K), -1);
479 }
480 else /* Handle all other variable incarnations */
481 new_bound = BB->sc_bound;
482
483 /* Check if the new bound might conflict and possibly make adjustments */
484 if(new_bound < BB->lowbo[K])
485 new_bound = BB->lowbo[K] - my_avoidtiny(new_bound-BB->lowbo[K], lp->epsvalue);
486 if(new_bound < BB->lowbo[K]) {
487 #ifdef Paranoia
488 debug_print(lp,
489 "New upper bound value %g conflicts with old lower bound %g\n",
490 new_bound, BB->lowbo[K]);
491 #endif
492 BB->nodesleft--;
493 goto SetLB;
494 }
495 #ifdef Paranoia
496 /* Do additional consistency checking */
497 else if(!check_if_less(lp, new_bound, BB->upbo[K], K)) {
498 BB->nodesleft--;
499 goto SetLB;
500 }
501 #endif
502 /* Bound (at least near) feasible */
503 else {
504 /* Makes a difference with models like QUEEN
505 (note consistent use of epsint for scaled integer variables) */
506 if(fabs(new_bound - BB->lowbo[K]) < intmargin*SCALEDINTFIXRANGE)
507 new_bound = BB->lowbo[K];
508 }
509
510 BB->UPbound = new_bound;
511
512
513 /* Next, establish the lower bound to be applied (when isfloor == FALSE)
514 --------------------------------------------------------------------- */
515 SetLB:
516 BB->LObound = -lp->infinite;
517
518 /* Handle SC-variables for the [0-LoBound> range */
519 if((SC_bound > 0) && (fabs(BB->lastsolution) < SC_bound)) {
520 if(is_int(lp, k))
521 new_bound = scaled_ceil(lp, K, SC_bound, 1);
522 else
523 new_bound = BB->sc_bound;
524 }
525 /* Handle pure integers (non-SOS, non-SC, but Ok for GUB!) */
526 else if((BB->vartype == BB_INT)) {
527 if(((ceil(BB->lastsolution) == BB->lastsolution)) || /* Skip branch 0 if the current solution is integer */
528 (ceil(BB->lastsolution) > /* Skip cases where the upper bound becomes violated */
529 unscaled_value(lp, ult_upbo, K)+intmargin) ||
530 (BB->isSOS && (BB->lastsolution == 0))) { /* Don't branch 0 since this is handled in SOS logic */
531 BB->nodesleft--;
532 goto Finish;
533 }
534 new_bound = scaled_ceil(lp, K, BB->lastsolution, 1);
535 }
536 else if(BB->isSOS) { /* Handle all SOS variants */
537 if(SOS_is_member_of_type(lp->SOS, k, SOS3))
538 new_bound = scaled_floor(lp, K, 1, 1);
539 else {
540 new_bound = ult_lowbo;
541 if(is_int(lp, k))
542 new_bound = scaled_floor(lp, K, unscaled_value(lp, new_bound, K), 1);
543 /* If we have a high-order SOS (SOS3+) and this variable is "intermediate"
544 between members previously lower-bounded at a non-zero level, then we should
545 set this and similar neighbouring variables at non-zero lowbo-values (remember
546 that SOS3+ members are all either integers or semi-continuous). Flag this
547 situation and prune tree, since we cannot lower-bound. */
548 if((lp->SOS->maxorder > 2) && (BB->lastsolution == 0) &&
549 SOS_is_member_of_type(lp->SOS, k, SOSn)) {
550 BB->isSOS = AUTOMATIC;
551 }
552 }
553 }
554 else /* Handle all other variable incarnations */
555 new_bound = BB->sc_bound;
556
557 /* Check if the new bound might conflict and possibly make adjustments */
558 if(new_bound > BB->upbo[K])
559 new_bound = BB->upbo[K] + my_avoidtiny(new_bound-BB->upbo[K], lp->epsvalue);
560 if(new_bound > BB->upbo[K]) {
561 #ifdef Paranoia
562 debug_print(lp,
563 "New lower bound value %g conflicts with old upper bound %g\n",
564 new_bound, BB->upbo[K]);
565 #endif
566 BB->nodesleft--;
567 goto Finish;
568 }
569 #ifdef Paranoia
570 /* Do additional consistency checking */
571 else if(!check_if_less(lp, BB->lowbo[K], new_bound, K)) {
572 BB->nodesleft--;
573 goto Finish;
574 }
575 #endif
576 /* Bound (at least near-)feasible */
577 else {
578 /* Makes a difference with models like QUEEN
579 (note consistent use of lp->epsprimal for scaled integer variables) */
580 if(fabs(BB->upbo[K]-new_bound) < intmargin*SCALEDINTFIXRANGE)
581 new_bound = BB->upbo[K];
582 }
583
584 BB->LObound = new_bound;
585
586 /* Prepare for the first branch by making sure we are pointing correctly */
587 Finish:
588 if(BB->nodesleft > 0) {
589
590 /* Make sure the change tracker levels are "clean" for the B&B */
591 if(countsUndoLadder(lp->bb_upperchange) > 0) {
592 incrementUndoLadder(lp->bb_upperchange);
593 BB->UBtrack++;
594 }
595 if(countsUndoLadder(lp->bb_lowerchange) > 0) {
596 incrementUndoLadder(lp->bb_lowerchange);
597 BB->LBtrack++;
598 }
599
600 /* Do adjustments */
601 if((BB->vartype != BB_SOS) && (fabs(BB->LObound-BB->UPbound) < intmargin)) {
602 BB->nodesleft--;
603 if(fabs(BB->lowbo[K]-BB->LObound) < intmargin)
604 BB->isfloor = FALSE;
605 else if(fabs(BB->upbo[K]-BB->UPbound) < intmargin)
606 BB->isfloor = TRUE;
607 else
608 report(BB->lp, IMPORTANT, "fillbranches_BB: Inconsistent equal-valued bounds for %s\n",
609 get_col_name(BB->lp, k));
610 }
611 if((BB->nodesleft == 1) &&
612 ((BB->isfloor && (BB->UPbound >= lp->infinite)) ||
613 (!BB->isfloor && (BB->LObound <= -lp->infinite))))
614 BB->isfloor = !BB->isfloor;
615 /* Header initialization */
616 BB->isfloor = !BB->isfloor;
617 while(!OKstatus && !lp->bb_break && (BB->nodesleft > 0))
618 OKstatus = nextbranch_BB( BB );
619 }
620
621 /* Set an SC variable active, if necessary */
622 if(BB->sc_canset)
623 lp->sc_lobound[k] *= -1;
624
625 }
626 else {
627 BB->nodesleft--;
628 OKstatus = TRUE;
629 }
630
631 return( OKstatus );
632 }
633
634 STATIC MYBOOL nextbranch_BB(BBrec *BB)
635 {
636 int k;
637 lprec *lp = BB->lp;
638 MYBOOL OKstatus = FALSE;
639
640 /* Undo the most recently imposed B&B bounds using the data
641 in the last level of change tracker; this code handles changes
642 to both upper and lower bounds */
643 if(BB->nodessolved > 0) {
644 restoreUndoLadder(lp->bb_upperchange, BB->upbo);
645 restoreUndoLadder(lp->bb_lowerchange, BB->lowbo);
646 }
647
648 if(lp->bb_break || userabort(lp, MSG_MILPSTRATEGY)) {
649 /* Handle the special case of B&B restart;
650 (typically used with the restart after pseudocost initialization) */
651 if((lp->bb_level == 1) && (lp->bb_break == AUTOMATIC)) {
652 lp->bb_break = FALSE;
653 OKstatus = TRUE;
654 }
655 return( OKstatus );
656 }
657
658 if(BB->nodesleft > 0) {
659
660 /* Step and update remaining branch count */
661 k = BB->varno - lp->rows;
662 BB->isfloor = !BB->isfloor;
663 BB->nodesleft--;
664
665 /* Special SOS handling:
666 1) Undo and set new marker for k,
667 2) In case that previous branch was ceiling restore upper bounds of the
668 non-k variables outside of the SOS window set to 0 */
669 if(BB->isSOS && (BB->vartype != BB_INT)) {
670
671 /* First undo previous marker */
672 if((BB->nodessolved > 0) || ((BB->nodessolved == 0) && (BB->nodesleft == 0))) {
673 if(BB->isfloor) {
674 if((BB->nodesleft == 0) && (lp->orig_lowbo[BB->varno] != 0))
675 return( OKstatus );
676 }
677 SOS_unmark(lp->SOS, 0, k);
678 }
679
680 /* Set new SOS marker */
681 if(BB->isfloor) {
682 SOS_set_marked(lp->SOS, 0, k, (MYBOOL) (BB->UPbound != 0));
683 /* Do case of high-order SOS where intervening variables need to be set */
684 if(BB->isSOS == AUTOMATIC) {
685
686 /* SOS_fix_list(lp->SOS, 0, k, BB->lowbo, NULL, AUTOMATIC, lp->bb_lowerchange); */
687 }
688 }
689 else {
690 SOS_set_marked(lp->SOS, 0, k, TRUE);
691 if(SOS_fix_unmarked(lp->SOS, 0, k, BB->upbo, 0, TRUE,
692 NULL, lp->bb_upperchange) < 0)
693 return( OKstatus );
694 }
695 }
696
697 /* Special GUB handling (three branches):
698 1) Undo and set new marker for k,
699 2) Restore upper bounds of the left/right/all non-k variables
700 set to 0 in the previous branch
701 3) Set new upper bounds for the non-k variables (k is set later) */
702 else if(BB->isGUB) {
703
704 /* First undo previous marker */
705 if(BB->nodessolved > 0)
706 SOS_unmark(lp->GUB, 0, k);
707
708 /* Make sure we take floor bound twice */
709 if((BB->nodesleft == 0) && !BB->isfloor)
710 BB->isfloor = !BB->isfloor;
711
712 /* Handle two floor instances;
713 (selected variable and left/right halves of non-selected variables at 0) */
714 SOS_set_marked(lp->GUB, 0, k, (MYBOOL) !BB->isfloor);
715 if(BB->isfloor) {
716 if(SOS_fix_list(lp->GUB, 0, k, BB->upbo,
717 BB->varmanaged, (MYBOOL) (BB->nodesleft > 0), lp->bb_upperchange) < 0)
718 return( OKstatus );
719 }
720 /* Handle one ceil instance;
721 (selected variable at 1, all other at 0) */
722 else {
723 if(SOS_fix_unmarked(lp->GUB, 0, k, BB->upbo, 0, TRUE,
724 NULL, lp->bb_upperchange) < 0)
725 return( OKstatus );
726 }
727 }
728
729 OKstatus = TRUE;
730
731 }
732 /* Initialize simplex status variables */
733 if(OKstatus) {
734 lp->bb_totalnodes++;
735 BB->nodestatus = NOTRUN;
736 BB->noderesult = lp->infinite;
737 }
738 return( OKstatus );
739 }
740
741
742 /* Cut generation and management routines */
743 STATIC MYBOOL initcuts_BB(lprec *lp)
744 {
745 return( TRUE );
746 }
747
748 STATIC int updatecuts_BB(lprec *lp)
749 {
750 return( 0 );
751 }
752
753 STATIC MYBOOL freecuts_BB(lprec *lp)
754 {
755 if(lp->bb_cuttype != NULL)
756 FREE(lp->bb_cuttype);
757 return( TRUE );
758 }
759
760 /* B&B solver routines */
761 STATIC int solve_LP(lprec *lp, BBrec *BB)
762 {
763 int tilted, restored, status;
764 REAL testOF, *upbo = BB->upbo, *lowbo = BB->lowbo;
765 BBrec *perturbed = NULL;
766
767 if(lp->bb_break)
768 return(PROCBREAK);
769
770 #ifdef Paranoia
771 debug_print(lp, "solve_LP: Starting solve for iter %.0f, B&B node level %d.\n",
772 (double) lp->total_iter, lp->bb_level);
773 if(lp->bb_trace &&
774 !validate_bounds(lp, upbo, lowbo))
775 report(lp, SEVERE, "solve_LP: Inconsistent bounds at iter %.0f, B&B node level %d.\n",
776 (double) lp->total_iter, lp->bb_level);
777 #endif
778
779 /* Copy user-specified entering bounds into lp_solve working bounds */
780 impose_bounds(lp, upbo, lowbo);
781
782 /* Restore previously pushed / saved basis for this level if we are in
783 the B&B mode and it is not the first call of the binary tree */
784 if(BB->nodessolved > 1)
785 restore_basis(lp);
786
787 /* Solve and possibly handle degeneracy cases via bound relaxations */
788 status = RUNNING;
789 tilted = 0;
790 restored = 0;
791
792 while(status == RUNNING) {
793
794 /* Copy user-specified entering bounds into lp_solve working bounds and run */
795 status = spx_run(lp, (MYBOOL) (tilted+restored > 0));
796 lp->bb_status = status;
797 lp->spx_perturbed = FALSE;
798
799 if(tilted < 0)
800 break;
801
802 else if((status == OPTIMAL) && (tilted > 0)) {
803 if(lp->spx_trace)
804 report(lp, DETAILED, "solve_LP: Restoring relaxed bounds at level %d.\n",
805 tilted);
806
807 /* Restore original pre-perturbed problem bounds, and solve again using the basis
808 found for the perturbed problem; also make sure we rebase and recompute. */
809 free_BB(&perturbed);
810 if((perturbed == NULL) || (perturbed == BB)) {
811 perturbed = NULL;
812 impose_bounds(lp, upbo, lowbo);
813 }
814 else
815 impose_bounds(lp, perturbed->upbo, perturbed->lowbo);
816 set_action(&lp->spx_action, ACTION_REBASE | ACTION_RECOMPUTE);
817 BB->UBzerobased = FALSE;
818 if(lp->bb_totalnodes == 0)
819 lp->real_solution = lp->infinite;
820 status = RUNNING;
821 tilted--;
822 restored++;
823 lp->spx_perturbed = TRUE;
824 }
825
826 else if(((lp->bb_level <= 1) || is_anti_degen(lp, ANTIDEGEN_DURINGBB)) &&
827 (((status == LOSTFEAS) && is_anti_degen(lp, ANTIDEGEN_LOSTFEAS)) ||
828 ((status == INFEASIBLE) && is_anti_degen(lp, ANTIDEGEN_INFEASIBLE)) ||
829 ((status == NUMFAILURE) && is_anti_degen(lp, ANTIDEGEN_NUMFAILURE)) ||
830 ((status == DEGENERATE) && is_anti_degen(lp, ANTIDEGEN_STALLING)))) {
831 /* Allow up to .. consecutive relaxations for non-B&B phases */
832 if((tilted <= DEF_MAXRELAX) && /* Conventional recovery case,... */
833 !((tilted == 0) && (restored > DEF_MAXRELAX))) { /* but not iterating infeasibility */
834
835 /* Create working copy of ingoing bounds if this is the first perturbation */
836 if(tilted == 0)
837 perturbed = BB;
838 perturbed = create_BB(lp, perturbed, TRUE);
839
840 /* Perturb/shift variable bounds; also make sure we rebase and recompute
841 (no refactorization is necessary, since the basis is unchanged) */
842 #if 1
843 perturb_bounds(lp, perturbed, TRUE, TRUE, TRUE);
844 #else
845 perturb_bounds(lp, perturbed, TRUE, TRUE, FALSE);
846 #endif
847 impose_bounds(lp, perturbed->upbo, perturbed->lowbo);
848 set_action(&lp->spx_action, ACTION_REBASE | ACTION_RECOMPUTE);
849 BB->UBzerobased = FALSE;
850 status = RUNNING;
851 tilted++;
852 lp->perturb_count++;
853 lp->spx_perturbed = TRUE;
854 if(lp->spx_trace)
855 report(lp, DETAILED, "solve_LP: Starting bound relaxation #%d ('%s')\n",
856 tilted, get_statustext(lp, status));
857 }
858 else {
859 if(lp->spx_trace)
860 report(lp, DETAILED, "solve_LP: Relaxation limit exceeded in resolving infeasibility\n");
861 while((perturbed != NULL) && (perturbed != BB))
862 free_BB(&perturbed);
863 perturbed = NULL;
864 }
865 }
866 }
867
868 /* Handle the different simplex outcomes */
869 if(status != OPTIMAL) {
870 lp->bb_parentOF = lp->infinite;
871 if((status == USERABORT) || (status == TIMEOUT)) {
872 /* Construct the last feasible solution, if available */
873 if((lp->solutioncount == 0) &&
874 ((lp->simplex_mode & (SIMPLEX_Phase2_PRIMAL | SIMPLEX_Phase2_DUAL)) > 0)) {
875 lp->solutioncount++;
876 construct_solution(lp, NULL);
877 transfer_solution(lp, TRUE);
878 }
879 /* Return messages */
880 report(lp, NORMAL, "\nlp_solve optimization was stopped %s.\n",
881 ((status == USERABORT) ? "by the user" : "due to time-out"));
882 }
883 else if(BB->varno == 0)
884 report(lp, NORMAL, "The model %s\n",
885 (status == UNBOUNDED) ? "is UNBOUNDED" :
886 ((status == INFEASIBLE) ? "is INFEASIBLE" : "FAILED"));
887 }
888
889 else { /* ... there is a good solution */
890 construct_solution(lp, NULL);
891 if((lp->bb_level <= 1) && (restored > 0))
892 report(lp, DETAILED, "%s numerics encountered; validate accuracy\n",
893 (restored == 1) ? "Difficult" : "Severe");
894 /* Handle case where a user bound on the OF was found to
895 have been set too aggressively, giving an infeasible model */
896 if(lp->spx_status != OPTIMAL)
897 status = lp->spx_status;
898
899 else if((lp->bb_totalnodes == 0) && (MIP_count(lp) > 0)) {
900 if(lp->lag_status != RUNNING) {
901 report(lp, NORMAL, "\nRelaxed solution " RESULTVALUEMASK " after %10.0f iter is B&B base.\n",
902 lp->solution[0], (double) lp->total_iter);
903 report(lp, NORMAL, " \n");
904 }
905 if((lp->usermessage != NULL) && (lp->msgmask & MSG_LPOPTIMAL))
906 lp->usermessage(lp, lp->msghandle, MSG_LPOPTIMAL);
907 set_var_priority(lp);
908 }
909
910 /* Check if we have a numeric problem (an earlier version of this code used the
911 absolute difference, but it is not robust for large-valued OFs) */
912 testOF = my_chsign(is_maxim(lp), my_reldiff(lp->solution[0], lp->real_solution));
913 if(testOF < -lp->epsprimal) {
914 report(lp, DETAILED, "solve_LP: A MIP subproblem returned a value better than the base.\n");
915 status = INFEASIBLE;
916 lp->spx_status = status;
917 set_action(&lp->spx_action, ACTION_REBASE | ACTION_REINVERT | ACTION_RECOMPUTE);
918 }
919 else if(testOF < 0) /* Avoid problems later (could undo integer roundings, but usually Ok) */
920 lp->solution[0] = lp->real_solution;
921
922 }
923
924 /* status can have the following values:
925 OPTIMAL, SUBOPTIMAL, TIMEOUT, USERABORT, PROCFAIL, UNBOUNDED and INFEASIBLE. */
926
927 return( status );
928 } /* solve_LP */
929
930 STATIC BBrec *findself_BB(BBrec *BB)
931 {
932 int varno = BB->varno, vartype = BB->vartype;
933
934 BB = BB->parent;
935 while((BB != NULL) && (BB->vartype != vartype) && (BB->varno != varno))
936 BB = BB->parent;
937 return( BB );
938 }
939
940 /* Function to determine the opportunity for variable fixing and bound
941 tightening based on a previous best MILP solution and a variable's
942 reduced cost at the current relaxation - inspired by Wolsley */
943 STATIC int rcfbound_BB(BBrec *BB, int varno, MYBOOL isINT, REAL *newbound, MYBOOL *isfeasible)
944 {
945 int i = FR;
946 lprec *lp = BB->lp;
947 REAL deltaRC, rangeLU, deltaOF, lowbo, upbo;
948
949 /* Make sure we only accept non-basic variables */
950 if(lp->is_basic[varno])
951 return( i );
952
953 /* Make sure we only accept non-fixed variables */
954 lowbo = BB->lowbo[varno];
955 upbo = BB->upbo[varno];
956 rangeLU = upbo - lowbo;
957
958 if(rangeLU > lp->epsprimal) {
959 deltaOF = lp->rhs[0] - lp->bb_workOF;
960 deltaRC = my_chsign(!lp->is_lower[varno], lp->drow[varno]);
961 /* Protect against divisions with tiny numbers and stray sign
962 reversals of the reduced cost */
963 if(deltaRC < lp->epspivot)
964 return( i );
965 deltaRC = deltaOF / deltaRC; /* Should always be a positive number! */
966 #ifdef Paranoia
967 if(deltaRC <= 0)
968 report(lp, SEVERE, "rcfbound_BB: A negative bound fixing level was encountered after node %.0f\n",
969 (double) lp->bb_totalnodes);
970 #endif
971
972 /* Check if bound implied by the reduced cost is less than existing range */
973 if(deltaRC < rangeLU + lp->epsint) {
974 if(lp->is_lower[varno]) {
975 if(isINT)
976 deltaRC = scaled_floor(lp, varno, unscaled_value(lp, deltaRC, varno)+lp->epsprimal, 1);
977 upbo = lowbo + deltaRC;
978 deltaRC = upbo;
979 i = LE; /* Sets the upper bound */
980 }
981 else {
982 if(isINT)
983 deltaRC = scaled_ceil(lp, varno, unscaled_value(lp, deltaRC, varno)+lp->epsprimal, 1);
984 lowbo = upbo - deltaRC;
985 deltaRC = lowbo;
986 i = GE; /* Sets the lower bound */
987 }
988
989 /* Check and set feasibility status */
990 if((isfeasible != NULL) && (upbo - lowbo < -lp->epsprimal))
991 *isfeasible = FALSE;
992
993 /* Flag that we can fix the variable by returning the relation code negated */
994 else if(fabs(upbo - lowbo) < lp->epsprimal)
995 i = -i;
996 if(newbound != NULL) {
997 my_roundzero(deltaRC, lp->epsprimal);
998 *newbound = deltaRC;
999 }
1000 }
1001
1002 }
1003 return( i );
1004 }
1005
1006
1007 STATIC MYBOOL findnode_BB(BBrec *BB, int *varno, int *vartype, int *varcus)
1008 {
1009 int countsossc, countnint, k;
1010 REAL varsol;
1011 MYBOOL is_better = FALSE, is_equal = FALSE, is_feasible = TRUE;
1012 lprec *lp = BB->lp;
1013
1014 /* Initialize result and return variables */
1015 *varno = 0;
1016 *vartype = BB_REAL;
1017 *varcus = 0;
1018 countnint = 0;
1019 BB->nodestatus = lp->spx_status;
1020 BB->noderesult = lp->solution[0];
1021
1022 /* If this solution is worse than the best so far, this branch dies.
1023 If we can only have integer OF values, and we only need the first solution
1024 then the OF must be at least (unscaled) 1 better than the best so far */
1025 if((lp->bb_limitlevel != 1) && (MIP_count(lp) > 0)) {
1026
1027 /* Check that we don't have a limit on the recursion level; two versions supported:
1028 1) Absolute B&B level (bb_limitlevel > 0), and
1029 2) B&B level relative to the "B&B order" (bb_limitlevel < 0). */
1030 countsossc = lp->sos_vars + lp->sc_vars;
1031 if((lp->bb_limitlevel > 0) && (lp->bb_level > lp->bb_limitlevel+countsossc))
1032 return( FALSE );
1033 else if((lp->bb_limitlevel < 0) &&
1034 (lp->bb_level > 2*(lp->int_vars+countsossc)*abs(lp->bb_limitlevel))) {
1035 if(lp->bb_limitlevel == DEF_BB_LIMITLEVEL)
1036 report(lp, IMPORTANT, "findnode_BB: Default B&B limit reached at %d; optionally change strategy or limit.\n\n",
1037 lp->bb_level);
1038 return( FALSE );
1039 }
1040
1041 /* First initialize or update pseudo-costs from previous optimal solution */
1042 if(BB->varno == 0) {
1043 varsol = lp->infinite;
1044 if((lp->int_vars+lp->sc_vars > 0) && (lp->bb_PseudoCost == NULL))
1045 lp->bb_PseudoCost = init_pseudocost(lp, get_bb_rule(lp));
1046 }
1047 else {
1048 varsol = lp->solution[BB->varno];
1049 if( ((lp->int_vars > 0) && (BB->vartype == BB_INT)) ||
1050 ((lp->sc_vars > 0) && (BB->vartype == BB_SC) && !is_int(lp, BB->varno-lp->rows)) )
1051 update_pseudocost(lp->bb_PseudoCost, BB->varno-lp->rows, BB->vartype, BB->isfloor, varsol);
1052 }
1053
1054 /* Make sure we don't have numeric problems (typically due to integer scaling) */
1055 if((lp->bb_totalnodes > 0) && !bb_better(lp, OF_RELAXED, OF_TEST_WE)) {
1056 if(lp->bb_trace)
1057 report(lp, IMPORTANT, "findnode_BB: Simplex failure due to loss of numeric accuracy\n");
1058 lp->spx_status = NUMFAILURE;
1059 return( FALSE );
1060 }
1061
1062 /* Abandon this branch if the solution is "worse" than a heuristically
1063 determined limit or the previous best MIP solution */
1064 if(((lp->solutioncount == 0) && !bb_better(lp, OF_HEURISTIC, OF_TEST_BE)) ||
1065 ((lp->solutioncount > 0) &&
1066 (!bb_better(lp, OF_INCUMBENT | OF_DELTA, OF_TEST_BE | OF_TEST_RELGAP) ||
1067 !bb_better(lp, OF_INCUMBENT | OF_DELTA, OF_TEST_BE)))) {
1068 return( FALSE );
1069 }
1070
1071 /* Collect violated SC variables (since they can also be real-valued); the
1072 approach is to get them out of the way, since a 0-value is assumed to be "cheap" */
1073 if(lp->sc_vars > 0) {
1074 *varno = find_sc_bbvar(lp, &countnint);
1075 if(*varno > 0)
1076 *vartype = BB_SC;
1077 }
1078
1079 /* Look among SOS variables if no SC candidate was found */
1080 if((SOS_count(lp) > 0) && (*varno == 0)) {
1081 *varno = find_sos_bbvar(lp, &countnint, FALSE);
1082 if(*varno < 0)
1083 *varno = 0;
1084 else if(*varno > 0)
1085 *vartype = BB_SOS;
1086 }
1087
1088 /* Then collect INTS that are not integer valued, and verify bounds */
1089 if((lp->int_vars > 0) && (*varno == 0)) {
1090 *varno = find_int_bbvar(lp, &countnint, BB, &is_feasible);
1091 if(*varno > 0) {
1092 *vartype = BB_INT;
1093 if((countnint == 1) && !is_feasible) {
1094 BB->lastrcf = 0;
1095 return( FALSE );
1096 }
1097 }
1098 }
1099
1100 #if 1 /* peno */
1101 /* Check if we have reached the depth limit for any individual variable
1102 (protects against infinite recursions of mainly integer variables) */
1103 k = *varno-lp->rows;
1104 if((*varno > 0) && (lp->bb_varactive[k] >= abs(DEF_BB_LIMITLEVEL))) {
1105 /* if(!is_action(lp->nomessage, NOMSG_BBLIMIT)) {*/
1106 /*
1107 report(lp, IMPORTANT, "findnode_BB: Reached B&B depth limit %d for variable %d; will not dive further.\n\n",
1108 lp->bb_varactive[k], k);
1109 */
1110 /* set_action(&lp->nomessage, NOMSG_BBLIMIT); */
1111 /* } */
1112 return( FALSE );
1113 }
1114 #endif
1115
1116 /* Check if the current MIP solution is optimal; equal or better */
1117 if(*varno == 0) {
1118 is_better = (MYBOOL) (lp->solutioncount == 0) || bb_better(lp, OF_INCUMBENT | OF_DELTA, OF_TEST_BT);
1119 is_better &= bb_better(lp, OF_INCUMBENT | OF_DELTA, OF_TEST_BT | OF_TEST_RELGAP);
1120 is_equal = !is_better;
1121
1122 if(is_equal) {
1123 if((lp->solutionlimit <= 0) || (lp->solutioncount < lp->solutionlimit)) {
1124 lp->solutioncount++;
1125 SETMIN(lp->bb_solutionlevel, lp->bb_level);
1126 if((lp->usermessage != NULL) && (lp->msgmask & MSG_MILPEQUAL))
1127 lp->usermessage(lp, lp->msghandle, MSG_MILPEQUAL);
1128 }
1129 }
1130
1131 /* Current solution is better */
1132 else if(is_better) {
1133
1134 /* Update grand total solution count and check if we should go from
1135 depth-first to best-first variable selection mode */
1136 if(lp->bb_varactive != NULL) {
1137 lp->bb_varactive[0]++;
1138 if((lp->bb_varactive[0] == 1) &&
1139 is_bb_mode(lp, NODE_DEPTHFIRSTMODE) && is_bb_mode(lp, NODE_DYNAMICMODE))
1140 lp->bb_rule &= !NODE_DEPTHFIRSTMODE;
1141 }
1142
1143 if(lp->bb_trace ||
1144 ((lp->verbose >= NORMAL) && (lp->print_sol == FALSE) && (lp->lag_status != RUNNING))) {
1145 report(lp, IMPORTANT,
1146 "%s solution " RESULTVALUEMASK " after %10.0f iter, %9.0f nodes (gap %.1f%%)\n",
1147 (lp->bb_improvements == 0) ? "Feasible" : "Improved",
1148 lp->solution[0], (double) lp->total_iter, (double) lp->bb_totalnodes,
1149 100.0*fabs(my_reldiff(lp->solution[0], lp->bb_limitOF)));
1150 }
1151 if((lp->usermessage != NULL) && (MIP_count(lp) > 0)) {
1152 if((lp->msgmask & MSG_MILPFEASIBLE) && (lp->bb_improvements == 0))
1153 lp->usermessage(lp, lp->msghandle, MSG_MILPFEASIBLE);
1154 else if((lp->msgmask & MSG_MILPBETTER) && (lp->msgmask & MSG_MILPBETTER))
1155 lp->usermessage(lp, lp->msghandle, MSG_MILPBETTER);
1156 }
1157
1158 lp->bb_status = FEASFOUND;
1159 lp->bb_solutionlevel = lp->bb_level;
1160 lp->solutioncount = 1;
1161 lp->bb_improvements++;
1162 lp->bb_workOF = lp->rhs[0];
1163
1164 if(lp->bb_breakfirst ||
1165 (!is_infinite(lp, lp->bb_breakOF) && bb_better(lp, OF_USERBREAK, OF_TEST_BE)))
1166 lp->bb_break = TRUE;
1167 }
1168 }
1169 }
1170 else {
1171 is_better = TRUE;
1172 lp->solutioncount = 1;
1173 }
1174
1175 /* Transfer the successful solution vector */
1176 if(is_better || is_equal) {
1177 #ifdef ParanoiaMIP
1178 if((lp->bb_level > 0) &&
1179 (check_solution(lp, lp->columns, lp->solution,
1180 lp->orig_upbo, lp->orig_lowbo, lp->epssolution) != OPTIMAL)) {
1181 lp->solutioncount = 0;
1182 lp->spx_status = NUMFAILURE;
1183 lp->bb_status = lp->spx_status;
1184 lp->bb_break = TRUE;
1185 return( FALSE );
1186 }
1187 #endif
1188 transfer_solution(lp, (MYBOOL) ((lp->do_presolve & PRESOLVE_LASTMASKMODE) != PRESOLVE_NONE));
1189 if((MIP_count(lp) > 0) && (lp->bb_totalnodes > 0)) {
1190 if ((!construct_duals(lp)) ||
1191 (is_presolve(lp, PRESOLVE_SENSDUALS) &&
1192 (!construct_sensitivity_duals(lp) || !construct_sensitivity_obj(lp))
1193 )
1194 ) {
1195 }
1196 }
1197 if(lp->print_sol != FALSE) {
1198 print_objective(lp);
1199 print_solution(lp, 1);
1200 }
1201 }
1202
1203 /* Do tracing and determine if we have arrived at the estimated lower MIP limit */
1204 *varcus = countnint;
1205 if(MIP_count(lp) > 0) {
1206 if((countnint == 0) && (lp->solutioncount == 1) && (lp->solutionlimit == 1) &&
1207 (bb_better(lp, OF_DUALLIMIT, OF_TEST_BE) || bb_better(lp, OF_USERBREAK, OF_TEST_BE | OF_TEST_RELGAP))) {
1208 lp->bb_break = (MYBOOL) (countnint == 0);
1209 return( FALSE );
1210 }
1211 else if(lp->bb_level > 0) {
1212 #ifdef MIPboundWithOF
1213 if((lp->constraintOF > 0) && (countnint == 0))
1214 set_rh(lp, lp->constraintOF, lp->solution[0] + my_chsign(!is_maxim(lp), lp->bb_deltaOF));
1215 #endif
1216 if(lp->spx_trace)
1217 report(lp, DETAILED, "B&B level %5d OPT %16s value " RESULTVALUEMASK "\n",
1218 lp->bb_level, (*varno) ? " " : "INT", lp->solution[0]);
1219 }
1220 return( (MYBOOL) (*varno > 0));
1221 }
1222 else
1223 return( FALSE );
1224
1225 }
1226
1227 STATIC int solve_BB(BBrec *BB)
1228 {
1229 int K, status;
1230 lprec *lp = BB->lp;
1231
1232 /* Protect against infinite recursions do to integer rounding effects */
1233 status = PROCFAIL;
1234
1235 /* Shortcut variables, set default bounds */
1236 K = BB->varno;
1237
1238 /* Load simple MIP bounds */
1239 if(K > 0) {
1240
1241 /* Update cuts, if specified */
1242 updatecuts_BB(lp);
1243
1244 /* BRANCH_FLOOR: Force the variable to be smaller than the B&B upper bound */
1245 if(BB->isfloor)
1246 modifyUndoLadder(lp->bb_upperchange, K, BB->upbo, BB->UPbound);
1247
1248 /* BRANCH_CEILING: Force the variable to be greater than the B&B lower bound */
1249 else
1250 modifyUndoLadder(lp->bb_lowerchange, K, BB->lowbo, BB->LObound);
1251
1252 /* Update MIP node count */
1253 BB->nodessolved++;
1254
1255 }
1256
1257 /* Solve! */
1258 status = solve_LP(lp, BB);
1259
1260 /* Do special feasibility assessment of high order SOS'es */
1261 #if 1
1262 if((status == OPTIMAL) && (BB->vartype == BB_SOS) && !SOS_is_feasible(lp->SOS, 0, lp->solution))
1263 status = INFEASIBLE;
1264 #endif
1265
1266 return( status );
1267 }
1268
1269 /* Routine to compute a "strong" pseudo-cost update for a node */
1270 STATIC MYBOOL strongbranch_BB(lprec *lp, BBrec *BB, int varno, int vartype, int varcus)
1271 {
1272 MYBOOL success = FALSE;
1273 int i;
1274 BBrec *strongBB;
1275
1276 /* Create new B&B level and solve each of the branches */
1277 lp->is_strongbranch = TRUE;
1278 push_basis(lp, lp->var_basic, lp->is_basic, lp->is_lower);
1279 strongBB = push_BB(lp, BB, lp->rows+varno, vartype, varcus);
1280 if(strongBB == BB)
1281 return( success );
1282
1283 do {
1284
1285 /* Solve incremental problem to local optimality */
1286 lp->bb_strongbranches++;
1287 /* set_action(&lp->spx_action, ACTION_REBASE | ACTION_RECOMPUTE); */
1288 if(solve_BB(strongBB) == OPTIMAL) {
1289
1290 /* Update result indicator*/
1291 success |= 1 << strongBB->isfloor;
1292
1293 /* Compute new count of non-ints */
1294 strongBB->lastvarcus = 0;
1295 for(i = 1; i <= lp->columns; i++) {
1296 if(is_int(lp, i) && !solution_is_int(lp, lp->rows+i, FALSE))
1297 strongBB->lastvarcus++;
1298 }
1299
1300 /* Perform the pseudo-cost update */
1301 update_pseudocost(lp->bb_PseudoCost, varno, strongBB->vartype, strongBB->isfloor,
1302 lp->solution[strongBB->varno]);
1303 }
1304 }
1305 while(nextbranch_BB(strongBB));
1306
1307 strongBB = pop_BB(strongBB);
1308 if(strongBB != BB)
1309 report(lp, SEVERE, "strongbranch_BB: Invalid bound settings restored for variable %d\n",
1310 varno);
1311 pop_basis(lp, TRUE);
1312 set_action(&lp->spx_action, ACTION_REBASE | ACTION_REINVERT | ACTION_RECOMPUTE);
1313
1314 lp->is_strongbranch = FALSE;
1315
1316 return( success );
1317 }
1318
1319 /* Future functions */
1320 STATIC MYBOOL pre_BB(lprec *lp)
1321 {
1322 return( TRUE );
1323 }
1324 STATIC MYBOOL post_BB(lprec *lp)
1325 {
1326 return( TRUE );
1327 }
1328
1329 /* This is the non-recursive B&B driver routine - beautifully simple, yet so subtle! */
1330 STATIC int run_BB(lprec *lp)
1331 {
1332 BBrec *currentBB;
1333 int varno, vartype, varcus, prevsolutions;
1334 int status = NOTRUN;
1335
1336 /* Initialize */
1337 pre_BB(lp);
1338 prevsolutions = lp->solutioncount;
1339 #ifdef UseMilpSlacksRCF /* Check if we should include ranged constraints */
1340 varno = lp->sum;
1341 #else
1342 varno = lp->columns;
1343 #endif
1344 lp->bb_upperchange = createUndoLadder(lp, varno, 2*MIP_count(lp));
1345 lp->bb_lowerchange = createUndoLadder(lp, varno, 2*MIP_count(lp));
1346 lp->rootbounds = currentBB = push_BB(lp, NULL, 0, BB_REAL, 0);
1347
1348 /* Perform the branch & bound loop */
1349 while(lp->bb_level > 0) {
1350
1351 status = solve_BB(currentBB);
1352
1353 if((status == OPTIMAL) && findnode_BB(currentBB, &varno, &vartype, &varcus))
1354 currentBB = push_BB(lp, currentBB, varno, vartype, varcus);
1355
1356 else while((lp->bb_level > 0) && !nextbranch_BB(currentBB))
1357 currentBB = pop_BB(currentBB);
1358
1359 }
1360
1361 /* Finalize */
1362 freeUndoLadder(&(lp->bb_upperchange));
1363 freeUndoLadder(&(lp->bb_lowerchange));
1364
1365 /* Check if we should adjust status */
1366 if(lp->solutioncount > prevsolutions) {
1367 if((status == PROCBREAK) || (status == USERABORT) || (status == TIMEOUT))
1368 status = SUBOPTIMAL;
1369 else
1370 status = OPTIMAL;
1371 if(lp->bb_totalnodes > 0)
1372 lp->spx_status = OPTIMAL;
1373 }
1374 post_BB(lp);
1375 return( status );
1376 }
1377
1378