Scippy

SCIP

Solving Constraint Integer Programs

tree.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file tree.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for branch and bound tree
28 * @author Tobias Achterberg
29 * @author Timo Berthold
30 * @author Gerald Gamrath
31 */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
35#include <assert.h>
36
37#include "scip/def.h"
38#include "scip/set.h"
39#include "scip/stat.h"
40#include "scip/clock.h"
41#include "scip/visual.h"
42#include "scip/event.h"
43#include "scip/lp.h"
44#include "scip/relax.h"
45#include "scip/var.h"
46#include "scip/implics.h"
47#include "scip/primal.h"
48#include "scip/tree.h"
49#include "scip/reopt.h"
50#include "scip/conflictstore.h"
51#include "scip/solve.h"
52#include "scip/cons.h"
53#include "scip/nodesel.h"
54#include "scip/prop.h"
55#include "scip/debug.h"
56#include "scip/prob.h"
57#include "scip/scip.h"
58#include "scip/struct_scip.h"
59#include "scip/struct_mem.h"
60#include "scip/struct_event.h"
61#include "scip/pub_message.h"
62#include "lpi/lpi.h"
63
64
65#define MAXREPROPMARK 511 /**< maximal subtree repropagation marker; must correspond to node data structure */
66
67
68/*
69 * dynamic memory arrays
70 */
71
72/** resizes children arrays to be able to store at least num nodes */
73static
75 SCIP_TREE* tree, /**< branch and bound tree */
76 SCIP_SET* set, /**< global SCIP settings */
77 int num /**< minimal number of node slots in array */
78 )
79{
80 assert(tree != NULL);
81 assert(set != NULL);
82
83 if( num > tree->childrensize )
84 {
85 int newsize;
86
87 newsize = SCIPsetCalcMemGrowSize(set, num);
88 SCIP_ALLOC( BMSreallocMemoryArray(&tree->children, newsize) );
90 tree->childrensize = newsize;
91 }
92 assert(num <= tree->childrensize);
93
94 return SCIP_OKAY;
95}
96
97/** resizes path array to be able to store at least num nodes */
98static
100 SCIP_TREE* tree, /**< branch and bound tree */
101 SCIP_SET* set, /**< global SCIP settings */
102 int num /**< minimal number of node slots in path */
103 )
104{
105 assert(tree != NULL);
106 assert(set != NULL);
107
108 if( num > tree->pathsize )
109 {
110 int newsize;
111
112 newsize = SCIPsetCalcPathGrowSize(set, num);
113 SCIP_ALLOC( BMSreallocMemoryArray(&tree->path, newsize) );
114 SCIP_ALLOC( BMSreallocMemoryArray(&tree->pathnlpcols, newsize) );
115 SCIP_ALLOC( BMSreallocMemoryArray(&tree->pathnlprows, newsize) );
116 tree->pathsize = newsize;
117 }
118 assert(num <= tree->pathsize);
119
120 return SCIP_OKAY;
121}
122
123/** resizes pendingbdchgs array to be able to store at least num nodes */
124static
126 SCIP_TREE* tree, /**< branch and bound tree */
127 SCIP_SET* set, /**< global SCIP settings */
128 int num /**< minimal number of node slots in path */
129 )
130{
131 assert(tree != NULL);
132 assert(set != NULL);
133
134 if( num > tree->pendingbdchgssize )
135 {
136 int newsize;
137
138 newsize = SCIPsetCalcMemGrowSize(set, num);
140 tree->pendingbdchgssize = newsize;
141 }
142 assert(num <= tree->pendingbdchgssize);
143
144 return SCIP_OKAY;
145}
146
147
148
149
150/*
151 * Node methods
152 */
153
154/** node comparator for best lower bound */
155SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound)
156{ /*lint --e{715}*/
157 assert(elem1 != NULL);
158 assert(elem2 != NULL);
159
160 if( ((SCIP_NODE*)elem1)->lowerbound < ((SCIP_NODE*)elem2)->lowerbound )
161 return -1;
162 else if( ((SCIP_NODE*)elem1)->lowerbound > ((SCIP_NODE*)elem2)->lowerbound )
163 return +1;
164 else
165 return 0;
166}
167
168/** increases the reference counter of the LP state in the fork */
169static
171 SCIP_FORK* fork, /**< fork data */
172 int nuses /**< number to add to the usage counter */
173 )
174{
175 assert(fork != NULL);
176 assert(fork->nlpistateref >= 0);
177 assert(nuses > 0);
178
179 fork->nlpistateref += nuses;
180 SCIPdebugMessage("captured LPI state of fork %p %d times -> new nlpistateref=%d\n", (void*)fork, nuses, fork->nlpistateref);
181}
182
183/** decreases the reference counter of the LP state in the fork */
184static
186 SCIP_FORK* fork, /**< fork data */
187 BMS_BLKMEM* blkmem, /**< block memory buffers */
188 SCIP_LP* lp /**< current LP data */
189 )
190{
191 assert(fork != NULL);
192 assert(fork->nlpistateref > 0);
193 assert(blkmem != NULL);
194 assert(lp != NULL);
195
196 fork->nlpistateref--;
197 if( fork->nlpistateref == 0 )
198 {
199 SCIP_CALL( SCIPlpFreeState(lp, blkmem, &(fork->lpistate)) );
200 }
201
202 SCIPdebugMessage("released LPI state of fork %p -> new nlpistateref=%d\n", (void*)fork, fork->nlpistateref);
203
204 return SCIP_OKAY;
205}
206
207/** increases the reference counter of the LP state in the subroot */
208static
210 SCIP_SUBROOT* subroot, /**< subroot data */
211 int nuses /**< number to add to the usage counter */
212 )
213{
214 assert(subroot != NULL);
215 assert(subroot->nlpistateref >= 0);
216 assert(nuses > 0);
217
218 subroot->nlpistateref += nuses;
219 SCIPdebugMessage("captured LPI state of subroot %p %d times -> new nlpistateref=%d\n",
220 (void*)subroot, nuses, subroot->nlpistateref);
221}
222
223/** decreases the reference counter of the LP state in the subroot */
224static
226 SCIP_SUBROOT* subroot, /**< subroot data */
227 BMS_BLKMEM* blkmem, /**< block memory buffers */
228 SCIP_LP* lp /**< current LP data */
229 )
230{
231 assert(subroot != NULL);
232 assert(subroot->nlpistateref > 0);
233 assert(blkmem != NULL);
234 assert(lp != NULL);
235
236 subroot->nlpistateref--;
237 if( subroot->nlpistateref == 0 )
238 {
239 SCIP_CALL( SCIPlpFreeState(lp, blkmem, &(subroot->lpistate)) );
240 }
241
242 SCIPdebugMessage("released LPI state of subroot %p -> new nlpistateref=%d\n", (void*)subroot, subroot->nlpistateref);
243
244 return SCIP_OKAY;
245}
246
247/** increases the reference counter of the LP state in the fork or subroot node */
249 SCIP_NODE* node, /**< fork/subroot node */
250 int nuses /**< number to add to the usage counter */
251 )
252{
253 assert(node != NULL);
254
255 SCIPdebugMessage("capture %d times LPI state of node #%" SCIP_LONGINT_FORMAT " at depth %d (current: %d)\n",
256 nuses, SCIPnodeGetNumber(node), SCIPnodeGetDepth(node),
258
259 switch( SCIPnodeGetType(node) )
260 {
262 forkCaptureLPIState(node->data.fork, nuses);
263 break;
265 subrootCaptureLPIState(node->data.subroot, nuses);
266 break;
267 default:
268 SCIPerrorMessage("node for capturing the LPI state is neither fork nor subroot\n");
269 SCIPABORT();
270 return SCIP_INVALIDDATA; /*lint !e527*/
271 } /*lint !e788*/
272 return SCIP_OKAY;
273}
274
275/** decreases the reference counter of the LP state in the fork or subroot node */
277 SCIP_NODE* node, /**< fork/subroot node */
278 BMS_BLKMEM* blkmem, /**< block memory buffers */
279 SCIP_LP* lp /**< current LP data */
280 )
281{
282 assert(node != NULL);
283
284 SCIPdebugMessage("release LPI state of node #%" SCIP_LONGINT_FORMAT " at depth %d (current: %d)\n",
287 switch( SCIPnodeGetType(node) )
288 {
290 return forkReleaseLPIState(node->data.fork, blkmem, lp);
292 return subrootReleaseLPIState(node->data.subroot, blkmem, lp);
293 default:
294 SCIPerrorMessage("node for releasing the LPI state is neither fork nor subroot\n");
295 return SCIP_INVALIDDATA;
296 } /*lint !e788*/
297}
298
299/** creates probingnode data without LP information */
300static
302 SCIP_PROBINGNODE** probingnode, /**< pointer to probingnode data */
303 BMS_BLKMEM* blkmem, /**< block memory */
304 SCIP_LP* lp /**< current LP data */
305 )
306{
307 assert(probingnode != NULL);
308
309 SCIP_ALLOC( BMSallocBlockMemory(blkmem, probingnode) );
310
311 (*probingnode)->lpistate = NULL;
312 (*probingnode)->lpinorms = NULL;
313 (*probingnode)->ninitialcols = SCIPlpGetNCols(lp);
314 (*probingnode)->ninitialrows = SCIPlpGetNRows(lp);
315 (*probingnode)->ncols = (*probingnode)->ninitialcols;
316 (*probingnode)->nrows = (*probingnode)->ninitialrows;
317 (*probingnode)->origobjvars = NULL;
318 (*probingnode)->origobjvals = NULL;
319 (*probingnode)->nchgdobjs = 0;
320
321 SCIPdebugMessage("created probingnode information (%d cols, %d rows)\n", (*probingnode)->ncols, (*probingnode)->nrows);
322
323 return SCIP_OKAY;
324}
325
326/** updates LP information in probingnode data */
327static
329 SCIP_PROBINGNODE* probingnode, /**< probingnode data */
330 BMS_BLKMEM* blkmem, /**< block memory */
331 SCIP_TREE* tree, /**< branch and bound tree */
332 SCIP_LP* lp /**< current LP data */
333 )
334{
335 SCIP_Bool storenorms = FALSE;
336
337 assert(probingnode != NULL);
338 assert(SCIPtreeIsPathComplete(tree));
339 assert(lp != NULL);
340
341 /* free old LP state */
342 if( probingnode->lpistate != NULL )
343 {
344 SCIP_CALL( SCIPlpFreeState(lp, blkmem, &probingnode->lpistate) );
345 }
346
347 /* free old LP norms */
348 if( probingnode->lpinorms != NULL )
349 {
350 SCIP_CALL( SCIPlpFreeNorms(lp, blkmem, &probingnode->lpinorms) );
351 probingnode->lpinorms = NULL;
352 storenorms = TRUE;
353 }
354
355 /* get current LP state */
356 if( lp->flushed && lp->solved )
357 {
358 SCIP_CALL( SCIPlpGetState(lp, blkmem, &probingnode->lpistate) );
359
360 /* if LP norms were stored at this node before, store the new ones */
361 if( storenorms )
362 {
363 SCIP_CALL( SCIPlpGetNorms(lp, blkmem, &probingnode->lpinorms) );
364 }
365 probingnode->lpwasprimfeas = lp->primalfeasible;
366 probingnode->lpwasprimchecked = lp->primalchecked;
367 probingnode->lpwasdualfeas = lp->dualfeasible;
368 probingnode->lpwasdualchecked = lp->dualchecked;
369 }
370 else
371 probingnode->lpistate = NULL;
372
373 probingnode->ncols = SCIPlpGetNCols(lp);
374 probingnode->nrows = SCIPlpGetNRows(lp);
375
376 SCIPdebugMessage("updated probingnode information (%d cols, %d rows)\n", probingnode->ncols, probingnode->nrows);
377
378 return SCIP_OKAY;
379}
380
381/** frees probingnode data */
382static
384 SCIP_PROBINGNODE** probingnode, /**< probingnode data */
385 BMS_BLKMEM* blkmem, /**< block memory */
386 SCIP_LP* lp /**< current LP data */
387 )
388{
389 assert(probingnode != NULL);
390 assert(*probingnode != NULL);
391
392 /* free the associated LP state */
393 if( (*probingnode)->lpistate != NULL )
394 {
395 SCIP_CALL( SCIPlpFreeState(lp, blkmem, &(*probingnode)->lpistate) );
396 }
397 /* free the associated LP norms */
398 if( (*probingnode)->lpinorms != NULL )
399 {
400 SCIP_CALL( SCIPlpFreeNorms(lp, blkmem, &(*probingnode)->lpinorms) );
401 }
402
403 /* free objective information */
404 if( (*probingnode)->nchgdobjs > 0 )
405 {
406 assert((*probingnode)->origobjvars != NULL);
407 assert((*probingnode)->origobjvals != NULL);
408
409 BMSfreeMemoryArray(&(*probingnode)->origobjvars);
410 BMSfreeMemoryArray(&(*probingnode)->origobjvals);
411 }
412
413 BMSfreeBlockMemory(blkmem, probingnode);
414
415 return SCIP_OKAY;
416}
417
418/** initializes junction data */
419static
421 SCIP_JUNCTION* junction, /**< pointer to junction data */
422 SCIP_TREE* tree /**< branch and bound tree */
423 )
424{
425 assert(junction != NULL);
426 assert(tree != NULL);
427 assert(tree->nchildren > 0);
428 assert(SCIPtreeIsPathComplete(tree));
429 assert(tree->focusnode != NULL);
430
431 junction->nchildren = tree->nchildren;
432
433 /* increase the LPI state usage counter of the current LP fork */
434 if( tree->focuslpstatefork != NULL )
435 {
437 }
438
439 return SCIP_OKAY;
440}
441
442/** creates pseudofork data */
443static
445 SCIP_PSEUDOFORK** pseudofork, /**< pointer to pseudofork data */
446 BMS_BLKMEM* blkmem, /**< block memory */
447 SCIP_TREE* tree, /**< branch and bound tree */
448 SCIP_LP* lp /**< current LP data */
449 )
450{
451 assert(pseudofork != NULL);
452 assert(blkmem != NULL);
453 assert(tree != NULL);
454 assert(tree->nchildren > 0);
455 assert(SCIPtreeIsPathComplete(tree));
456 assert(tree->focusnode != NULL);
457
458 SCIP_ALLOC( BMSallocBlockMemory(blkmem, pseudofork) );
459
460 (*pseudofork)->addedcols = NULL;
461 (*pseudofork)->addedrows = NULL;
462 (*pseudofork)->naddedcols = SCIPlpGetNNewcols(lp);
463 (*pseudofork)->naddedrows = SCIPlpGetNNewrows(lp);
464 (*pseudofork)->nchildren = tree->nchildren;
465
466 SCIPdebugMessage("creating pseudofork information with %d children (%d new cols, %d new rows)\n",
467 (*pseudofork)->nchildren, (*pseudofork)->naddedcols, (*pseudofork)->naddedrows);
468
469 if( (*pseudofork)->naddedcols > 0 )
470 {
471 /* copy the newly created columns to the pseudofork's col array */
472 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*pseudofork)->addedcols, SCIPlpGetNewcols(lp), (*pseudofork)->naddedcols) ); /*lint !e666*/
473 }
474 if( (*pseudofork)->naddedrows > 0 )
475 {
476 int i;
477
478 /* copy the newly created rows to the pseudofork's row array */
479 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*pseudofork)->addedrows, SCIPlpGetNewrows(lp), (*pseudofork)->naddedrows) ); /*lint !e666*/
480
481 /* capture the added rows */
482 for( i = 0; i < (*pseudofork)->naddedrows; ++i )
483 SCIProwCapture((*pseudofork)->addedrows[i]);
484 }
485
486 /* increase the LPI state usage counter of the current LP fork */
487 if( tree->focuslpstatefork != NULL )
488 {
490 }
491
492 return SCIP_OKAY;
493}
494
495/** frees pseudofork data */
496static
498 SCIP_PSEUDOFORK** pseudofork, /**< pseudofork data */
499 BMS_BLKMEM* blkmem, /**< block memory */
500 SCIP_SET* set, /**< global SCIP settings */
501 SCIP_LP* lp /**< current LP data */
502 )
503{
504 int i;
505
506 assert(pseudofork != NULL);
507 assert(*pseudofork != NULL);
508 assert((*pseudofork)->nchildren == 0);
509 assert(blkmem != NULL);
510 assert(set != NULL);
511
512 /* release the added rows */
513 for( i = 0; i < (*pseudofork)->naddedrows; ++i )
514 {
515 SCIP_CALL( SCIProwRelease(&(*pseudofork)->addedrows[i], blkmem, set, lp) );
516 }
517
518 BMSfreeBlockMemoryArrayNull(blkmem, &(*pseudofork)->addedcols, (*pseudofork)->naddedcols);
519 BMSfreeBlockMemoryArrayNull(blkmem, &(*pseudofork)->addedrows, (*pseudofork)->naddedrows);
520 BMSfreeBlockMemory(blkmem, pseudofork);
521
522 return SCIP_OKAY;
523}
524
525/** creates fork data */
526static
528 SCIP_FORK** fork, /**< pointer to fork data */
529 BMS_BLKMEM* blkmem, /**< block memory */
530 SCIP_SET* set, /**< global SCIP settings */
531 SCIP_PROB* prob, /**< transformed problem after presolve */
532 SCIP_TREE* tree, /**< branch and bound tree */
533 SCIP_LP* lp /**< current LP data */
534 )
535{
536 assert(fork != NULL);
537 assert(blkmem != NULL);
538 assert(tree != NULL);
539 assert(tree->nchildren > 0);
540 assert(tree->nchildren < (1 << 30));
541 assert(SCIPtreeIsPathComplete(tree));
542 assert(tree->focusnode != NULL);
543 assert(lp != NULL);
544 assert(lp->flushed);
545 assert(lp->solved);
547
548 SCIP_ALLOC( BMSallocBlockMemory(blkmem, fork) );
549
550 SCIP_CALL( SCIPlpGetState(lp, blkmem, &((*fork)->lpistate)) );
551 (*fork)->lpwasprimfeas = lp->primalfeasible;
552 (*fork)->lpwasprimchecked = lp->primalchecked;
553 (*fork)->lpwasdualfeas = lp->dualfeasible;
554 (*fork)->lpwasdualchecked = lp->dualchecked;
555 (*fork)->lpobjval = SCIPlpGetObjval(lp, set, prob);
556 (*fork)->nlpistateref = 0;
557 (*fork)->addedcols = NULL;
558 (*fork)->addedrows = NULL;
559 (*fork)->naddedcols = SCIPlpGetNNewcols(lp);
560 (*fork)->naddedrows = SCIPlpGetNNewrows(lp);
561 (*fork)->nchildren = (unsigned int) tree->nchildren;
562
563 SCIPsetDebugMsg(set, "creating fork information with %u children (%d new cols, %d new rows)\n", (*fork)->nchildren, (*fork)->naddedcols, (*fork)->naddedrows);
564
565 if( (*fork)->naddedcols > 0 )
566 {
567 /* copy the newly created columns to the fork's col array */
568 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*fork)->addedcols, SCIPlpGetNewcols(lp), (*fork)->naddedcols) ); /*lint !e666*/
569 }
570 if( (*fork)->naddedrows > 0 )
571 {
572 int i;
573
574 /* copy the newly created rows to the fork's row array */
575 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*fork)->addedrows, SCIPlpGetNewrows(lp), (*fork)->naddedrows) ); /*lint !e666*/
576
577 /* capture the added rows */
578 for( i = 0; i < (*fork)->naddedrows; ++i )
579 SCIProwCapture((*fork)->addedrows[i]);
580 }
581
582 /* capture the LPI state for the children */
583 forkCaptureLPIState(*fork, tree->nchildren);
584
585 return SCIP_OKAY;
586}
587
588/** frees fork data */
589static
591 SCIP_FORK** fork, /**< fork data */
592 BMS_BLKMEM* blkmem, /**< block memory */
593 SCIP_SET* set, /**< global SCIP settings */
594 SCIP_LP* lp /**< current LP data */
595 )
596{
597 int i;
598
599 assert(fork != NULL);
600 assert(*fork != NULL);
601 assert((*fork)->nchildren == 0);
602 assert((*fork)->nlpistateref == 0);
603 assert((*fork)->lpistate == NULL);
604 assert(blkmem != NULL);
605 assert(set != NULL);
606 assert(lp != NULL);
607
608 /* release the added rows */
609 for( i = (*fork)->naddedrows - 1; i >= 0; --i )
610 {
611 SCIP_CALL( SCIProwRelease(&(*fork)->addedrows[i], blkmem, set, lp) );
612 }
613
614 BMSfreeBlockMemoryArrayNull(blkmem, &(*fork)->addedcols, (*fork)->naddedcols);
615 BMSfreeBlockMemoryArrayNull(blkmem, &(*fork)->addedrows, (*fork)->naddedrows);
616 BMSfreeBlockMemory(blkmem, fork);
617
618 return SCIP_OKAY;
619}
620
621#ifdef WITHSUBROOTS /** @todo test whether subroots should be created */
622/** creates subroot data */
623static
624SCIP_RETCODE subrootCreate(
625 SCIP_SUBROOT** subroot, /**< pointer to subroot data */
626 BMS_BLKMEM* blkmem, /**< block memory */
627 SCIP_SET* set, /**< global SCIP settings */
628 SCIP_PROB* prob, /**< transformed problem after presolve */
629 SCIP_TREE* tree, /**< branch and bound tree */
630 SCIP_LP* lp /**< current LP data */
631 )
632{
633 int i;
634
635 assert(subroot != NULL);
636 assert(blkmem != NULL);
637 assert(tree != NULL);
638 assert(tree->nchildren > 0);
639 assert(SCIPtreeIsPathComplete(tree));
640 assert(tree->focusnode != NULL);
641 assert(lp != NULL);
642 assert(lp->flushed);
643 assert(lp->solved);
645
646 SCIP_ALLOC( BMSallocBlockMemory(blkmem, subroot) );
647 (*subroot)->lpobjval = SCIPlpGetObjval(lp, set, prob);
648 (*subroot)->nlpistateref = 0;
649 (*subroot)->ncols = SCIPlpGetNCols(lp);
650 (*subroot)->nrows = SCIPlpGetNRows(lp);
651 (*subroot)->nchildren = (unsigned int) tree->nchildren;
652 SCIP_CALL( SCIPlpGetState(lp, blkmem, &((*subroot)->lpistate)) );
653 (*subroot)->lpwasprimfeas = lp->primalfeasible;
654 (*subroot)->lpwasprimchecked = lp->primalchecked;
655 (*subroot)->lpwasdualfeas = lp->dualfeasible;
656 (*subroot)->lpwasdualchecked = lp->dualchecked;
657
658 if( (*subroot)->ncols != 0 )
659 {
660 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*subroot)->cols, SCIPlpGetCols(lp), (*subroot)->ncols) );
661 }
662 else
663 (*subroot)->cols = NULL;
664 if( (*subroot)->nrows != 0 )
665 {
666 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*subroot)->rows, SCIPlpGetRows(lp), (*subroot)->nrows) );
667 }
668 else
669 (*subroot)->rows = NULL;
670
671 /* capture the rows of the subroot */
672 for( i = 0; i < (*subroot)->nrows; ++i )
673 SCIProwCapture((*subroot)->rows[i]);
674
675 /* capture the LPI state for the children */
676 subrootCaptureLPIState(*subroot, tree->nchildren);
677
678 return SCIP_OKAY;
679}
680#endif
681
682/** frees subroot */
683static
685 SCIP_SUBROOT** subroot, /**< subroot data */
686 BMS_BLKMEM* blkmem, /**< block memory */
687 SCIP_SET* set, /**< global SCIP settings */
688 SCIP_LP* lp /**< current LP data */
689 )
690{
691 int i;
692
693 assert(subroot != NULL);
694 assert(*subroot != NULL);
695 assert((*subroot)->nchildren == 0);
696 assert((*subroot)->nlpistateref == 0);
697 assert((*subroot)->lpistate == NULL);
698 assert(blkmem != NULL);
699 assert(set != NULL);
700 assert(lp != NULL);
701
702 /* release the rows of the subroot */
703 for( i = 0; i < (*subroot)->nrows; ++i )
704 {
705 SCIP_CALL( SCIProwRelease(&(*subroot)->rows[i], blkmem, set, lp) );
706 }
707
708 BMSfreeBlockMemoryArrayNull(blkmem, &(*subroot)->cols, (*subroot)->ncols);
709 BMSfreeBlockMemoryArrayNull(blkmem, &(*subroot)->rows, (*subroot)->nrows);
710 BMSfreeBlockMemory(blkmem, subroot);
711
712 return SCIP_OKAY;
713}
714
715/** removes given sibling node from the siblings array */
716static
718 SCIP_TREE* tree, /**< branch and bound tree */
719 SCIP_NODE* sibling /**< sibling node to remove */
720 )
721{
722 int delpos;
723
724 assert(tree != NULL);
725 assert(sibling != NULL);
726 assert(SCIPnodeGetType(sibling) == SCIP_NODETYPE_SIBLING);
727 assert(sibling->data.sibling.arraypos >= 0 && sibling->data.sibling.arraypos < tree->nsiblings);
728 assert(tree->siblings[sibling->data.sibling.arraypos] == sibling);
729 assert(SCIPnodeGetType(tree->siblings[tree->nsiblings-1]) == SCIP_NODETYPE_SIBLING);
730
731 delpos = sibling->data.sibling.arraypos;
732
733 /* move last sibling in array to position of removed sibling */
734 tree->siblings[delpos] = tree->siblings[tree->nsiblings-1];
735 tree->siblingsprio[delpos] = tree->siblingsprio[tree->nsiblings-1];
736 tree->siblings[delpos]->data.sibling.arraypos = delpos;
737 sibling->data.sibling.arraypos = -1;
738 tree->nsiblings--;
739}
740
741/** adds given child node to children array of focus node */
742static
744 SCIP_TREE* tree, /**< branch and bound tree */
745 SCIP_SET* set, /**< global SCIP settings */
746 SCIP_NODE* child, /**< child node to add */
747 SCIP_Real nodeselprio /**< node selection priority of child node */
748 )
749{
750 assert(tree != NULL);
751 assert(child != NULL);
752 assert(SCIPnodeGetType(child) == SCIP_NODETYPE_CHILD);
753 assert(child->data.child.arraypos == -1);
754
755 SCIP_CALL( treeEnsureChildrenMem(tree, set, tree->nchildren+1) );
756 tree->children[tree->nchildren] = child;
757 tree->childrenprio[tree->nchildren] = nodeselprio;
758 child->data.child.arraypos = tree->nchildren;
759 tree->nchildren++;
760
761 return SCIP_OKAY;
762}
763
764/** removes given child node from the children array */
765static
767 SCIP_TREE* tree, /**< branch and bound tree */
768 SCIP_NODE* child /**< child node to remove */
769 )
770{
771 int delpos;
772
773 assert(tree != NULL);
774 assert(child != NULL);
775 assert(SCIPnodeGetType(child) == SCIP_NODETYPE_CHILD);
776 assert(child->data.child.arraypos >= 0 && child->data.child.arraypos < tree->nchildren);
777 assert(tree->children[child->data.child.arraypos] == child);
778 assert(SCIPnodeGetType(tree->children[tree->nchildren-1]) == SCIP_NODETYPE_CHILD);
779
780 delpos = child->data.child.arraypos;
781
782 /* move last child in array to position of removed child */
783 tree->children[delpos] = tree->children[tree->nchildren-1];
784 tree->childrenprio[delpos] = tree->childrenprio[tree->nchildren-1];
785 tree->children[delpos]->data.child.arraypos = delpos;
786 child->data.child.arraypos = -1;
787 tree->nchildren--;
788}
789
790/** makes node a child of the given parent node, which must be the focus node; if the child is a probing node,
791 * the parent node can also be a refocused node or a probing node
792 */
793static
795 SCIP_NODE* node, /**< child node */
796 BMS_BLKMEM* blkmem, /**< block memory buffers */
797 SCIP_SET* set, /**< global SCIP settings */
798 SCIP_TREE* tree, /**< branch and bound tree */
799 SCIP_NODE* parent, /**< parent (= focus) node (or NULL, if node is root) */
800 SCIP_Real nodeselprio /**< node selection priority of child node */
801 )
802{
803 assert(node != NULL);
804 assert(node->parent == NULL);
806 assert(node->conssetchg == NULL);
807 assert(node->domchg == NULL);
808 assert(SCIPsetIsInfinity(set, -node->lowerbound)); /* node was just created */
809 assert(blkmem != NULL);
810 assert(set != NULL);
811 assert(tree != NULL);
812 assert(SCIPtreeIsPathComplete(tree));
813 assert(tree->pathlen == 0 || tree->path[tree->pathlen-1] == parent);
814 assert(parent == tree->focusnode || SCIPnodeGetType(parent) == SCIP_NODETYPE_PROBINGNODE);
815 assert(parent == NULL || SCIPnodeGetType(parent) == SCIP_NODETYPE_FOCUSNODE
819
820 /* link node to parent */
821 node->parent = parent;
822 if( parent != NULL )
823 {
824 assert(parent->lowerbound <= parent->estimate);
825 node->lowerbound = parent->lowerbound;
826 node->estimate = parent->estimate;
827 node->depth = parent->depth+1; /*lint !e732*/
828 if( parent->depth >= SCIP_MAXTREEDEPTH )
829 {
830 SCIPerrorMessage("maximal depth level exceeded\n");
831 return SCIP_MAXDEPTHLEVEL;
832 }
833 }
834 SCIPsetDebugMsg(set, "assigning parent #%" SCIP_LONGINT_FORMAT " to node #%" SCIP_LONGINT_FORMAT " at depth %d\n",
835 parent != NULL ? SCIPnodeGetNumber(parent) : -1, SCIPnodeGetNumber(node), SCIPnodeGetDepth(node));
836
837 /* register node in the childlist of the focus (the parent) node */
839 {
840 assert(parent == NULL || SCIPnodeGetType(parent) == SCIP_NODETYPE_FOCUSNODE);
841 SCIP_CALL( treeAddChild(tree, set, node, nodeselprio) );
842 }
843
844 return SCIP_OKAY;
845}
846
847/** decreases number of children of the parent, frees it if no children are left */
848static
850 SCIP_NODE* node, /**< child node */
851 BMS_BLKMEM* blkmem, /**< block memory buffer */
852 SCIP_SET* set, /**< global SCIP settings */
853 SCIP_STAT* stat, /**< problem statistics */
854 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
855 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
856 SCIP_TREE* tree, /**< branch and bound tree */
857 SCIP_LP* lp /**< current LP data */
858 )
859{
860 SCIP_NODE* parent;
861
862 assert(node != NULL);
863 assert(blkmem != NULL);
864 assert(tree != NULL);
865
866 SCIPsetDebugMsg(set, "releasing parent-child relationship of node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d with parent #%" SCIP_LONGINT_FORMAT " of type %d\n",
868 node->parent != NULL ? SCIPnodeGetNumber(node->parent) : -1,
869 node->parent != NULL ? (int)SCIPnodeGetType(node->parent) : -1);
870 parent = node->parent;
871 if( parent != NULL )
872 {
873 SCIP_Bool freeParent = FALSE;
874
875 switch( SCIPnodeGetType(parent) )
876 {
878 assert(parent->active);
882 treeRemoveChild(tree, node);
883 /* don't kill the focus node at this point => freeParent = FALSE */
884 break;
886 assert(SCIPtreeProbing(tree));
887 /* probing nodes have to be freed individually => freeParent = FALSE */
888 break;
890 SCIPerrorMessage("sibling cannot be a parent node\n");
891 return SCIP_INVALIDDATA;
893 SCIPerrorMessage("child cannot be a parent node\n");
894 return SCIP_INVALIDDATA;
896 SCIPerrorMessage("leaf cannot be a parent node\n");
897 return SCIP_INVALIDDATA;
899 SCIPerrorMessage("dead-end cannot be a parent node\n");
900 return SCIP_INVALIDDATA;
902 assert(parent->data.junction.nchildren > 0);
903 parent->data.junction.nchildren--;
904 freeParent = (parent->data.junction.nchildren == 0); /* free parent if it has no more children */
905 break;
907 assert(parent->data.pseudofork != NULL);
908 assert(parent->data.pseudofork->nchildren > 0);
909 parent->data.pseudofork->nchildren--;
910 freeParent = (parent->data.pseudofork->nchildren == 0); /* free parent if it has no more children */
911 break;
913 assert(parent->data.fork != NULL);
914 assert(parent->data.fork->nchildren > 0);
915 parent->data.fork->nchildren--;
916 freeParent = (parent->data.fork->nchildren == 0); /* free parent if it has no more children */
917 break;
919 assert(parent->data.subroot != NULL);
920 assert(parent->data.subroot->nchildren > 0);
921 parent->data.subroot->nchildren--;
922 freeParent = (parent->data.subroot->nchildren == 0); /* free parent if it has no more children */
923 break;
925 /* the only possible child a refocused node can have in its refocus state is the probing root node;
926 * we don't want to free the refocused node, because we first have to convert it back to its original
927 * type (where it possibly has children) => freeParent = FALSE
928 */
930 assert(!SCIPtreeProbing(tree));
931 break;
932 default:
933 SCIPerrorMessage("unknown node type %d\n", SCIPnodeGetType(parent));
934 return SCIP_INVALIDDATA;
935 }
936
937 /* free parent if it is not on the current active path */
938 if( freeParent && !parent->active )
939 {
940 SCIP_CALL( SCIPnodeFree(&node->parent, blkmem, set, stat, eventfilter, eventqueue, tree, lp) );
941 }
942 /* update the effective root depth if not in reoptimization and active parent has children */
943 else if( !set->reopt_enable && freeParent == !parent->active )
944 {
945 SCIP_Bool singleChild = FALSE;
946 int focusdepth = SCIPtreeGetFocusDepth(tree);
947
948 assert(tree->effectiverootdepth >= 0);
949
950 while( tree->effectiverootdepth < focusdepth )
951 {
952 SCIP_NODE* effectiveroot = tree->path[tree->effectiverootdepth];
953
954 switch( SCIPnodeGetType(effectiveroot) )
955 {
957 SCIPerrorMessage("focus shallower than focus depth\n");
958 return SCIP_INVALIDDATA;
960 SCIPerrorMessage("probing shallower than focus depth\n");
961 return SCIP_INVALIDDATA;
963 SCIPerrorMessage("sibling shallower than focus depth\n");
964 return SCIP_INVALIDDATA;
966 SCIPerrorMessage("child shallower than focus depth\n");
967 return SCIP_INVALIDDATA;
969 SCIPerrorMessage("leaf on focus path\n");
970 return SCIP_INVALIDDATA;
972 SCIPerrorMessage("dead-end on focus path\n");
973 return SCIP_INVALIDDATA;
975 singleChild = (effectiveroot->data.junction.nchildren == 1);
976 break;
978 singleChild = (effectiveroot->data.pseudofork->nchildren == 1);
979 break;
981 singleChild = (effectiveroot->data.fork->nchildren == 1);
982 break;
984 singleChild = (effectiveroot->data.subroot->nchildren == 1);
985 break;
987 singleChild = FALSE;
988 break;
989 default:
990 SCIPerrorMessage("unknown node type %d\n", SCIPnodeGetType(effectiveroot));
991 return SCIP_INVALIDDATA;
992 }
993
994 if( !singleChild )
995 break;
996
997 ++tree->effectiverootdepth;
998
1000 "unlinked node #%" SCIP_LONGINT_FORMAT " in depth %d -> new effective root depth: %d\n",
1002 }
1003
1004 assert(!singleChild || SCIPtreeGetEffectiveRootDepth(tree) == SCIPtreeGetFocusDepth(tree));
1005 }
1006 }
1007
1008 return SCIP_OKAY;
1009}
1010
1011/** creates a node data structure */
1012static
1014 SCIP_NODE** node, /**< pointer to node data structure */
1015 BMS_BLKMEM* blkmem, /**< block memory */
1016 SCIP_SET* set /**< global SCIP settings */
1017 )
1018{
1019 assert(node != NULL);
1020
1021 SCIP_ALLOC( BMSallocBlockMemory(blkmem, node) );
1022 (*node)->parent = NULL;
1023 (*node)->conssetchg = NULL;
1024 (*node)->domchg = NULL;
1025 (*node)->number = 0;
1026 (*node)->lowerbound = -SCIPsetInfinity(set);
1027 (*node)->estimate = -SCIPsetInfinity(set);
1028 (*node)->reoptid = 0;
1029 (*node)->reopttype = (unsigned int) SCIP_REOPTTYPE_NONE;
1030 (*node)->depth = 0;
1031 (*node)->active = FALSE;
1032 (*node)->cutoff = FALSE;
1033 (*node)->reprop = FALSE;
1034 (*node)->repropsubtreemark = 0;
1035
1036 return SCIP_OKAY;
1037}
1038
1039/** creates a child node of the focus node */
1041 SCIP_NODE** node, /**< pointer to node data structure */
1042 BMS_BLKMEM* blkmem, /**< block memory */
1043 SCIP_SET* set, /**< global SCIP settings */
1044 SCIP_STAT* stat, /**< problem statistics */
1045 SCIP_TREE* tree, /**< branch and bound tree */
1046 SCIP_Real nodeselprio, /**< node selection priority of new node */
1047 SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */
1048 )
1049{
1050 assert(node != NULL);
1051 assert(blkmem != NULL);
1052 assert(set != NULL);
1053 assert(stat != NULL);
1054 assert(tree != NULL);
1055 assert(SCIPtreeIsPathComplete(tree));
1056 assert(tree->pathlen == 0 || tree->path != NULL);
1057 assert((tree->pathlen == 0) == (tree->focusnode == NULL));
1058 assert(tree->focusnode == NULL || tree->focusnode == tree->path[tree->pathlen-1]);
1059 assert(tree->focusnode == NULL || SCIPnodeGetType(tree->focusnode) == SCIP_NODETYPE_FOCUSNODE);
1060
1061 stat->ncreatednodes++;
1062 stat->ncreatednodesrun++;
1063
1064 /* create the node data structure */
1065 SCIP_CALL( nodeCreate(node, blkmem, set) );
1066 (*node)->number = stat->ncreatednodesrun;
1067
1068 /* mark node to be a child node */
1069 (*node)->nodetype = SCIP_NODETYPE_CHILD; /*lint !e641*/
1070 (*node)->data.child.arraypos = -1;
1071
1072 /* make focus node the parent of the new child */
1073 SCIP_CALL( nodeAssignParent(*node, blkmem, set, tree, tree->focusnode, nodeselprio) );
1074
1075 /* update the estimate of the child */
1076 SCIPnodeSetEstimate(*node, set, estimate);
1077
1078 tree->lastbranchparentid = tree->focusnode == NULL ? -1L : SCIPnodeGetNumber(tree->focusnode);
1079
1080 /* output node creation to visualization file */
1081 SCIP_CALL( SCIPvisualNewChild(stat->visual, set, stat, *node) );
1082
1083 SCIPsetDebugMsg(set, "created child node #%" SCIP_LONGINT_FORMAT " at depth %u (prio: %g)\n", SCIPnodeGetNumber(*node), (*node)->depth, nodeselprio);
1084
1085 return SCIP_OKAY;
1086}
1087
1088/** query if focus node was already branched on */
1090 SCIP_TREE* tree, /**< branch and bound tree */
1091 SCIP_NODE* node /**< tree node, or NULL to check focus node */
1092 )
1093{
1094 node = node == NULL ? tree->focusnode : node;
1095 if( node != NULL && node->number == tree->lastbranchparentid )
1096 return TRUE;
1097
1098 return FALSE;
1099}
1100
1101/** frees node */
1103 SCIP_NODE** node, /**< node data */
1104 BMS_BLKMEM* blkmem, /**< block memory buffer */
1105 SCIP_SET* set, /**< global SCIP settings */
1106 SCIP_STAT* stat, /**< problem statistics */
1107 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1108 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1109 SCIP_TREE* tree, /**< branch and bound tree */
1110 SCIP_LP* lp /**< current LP data */
1111 )
1112{
1113 SCIP_Bool isroot;
1114
1115 assert(node != NULL);
1116 assert(*node != NULL);
1117 assert(!(*node)->active);
1118 assert(blkmem != NULL);
1119 assert(tree != NULL);
1120
1121 SCIPsetDebugMsg(set, "free node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d\n", SCIPnodeGetNumber(*node), SCIPnodeGetDepth(*node), SCIPnodeGetType(*node));
1122
1123 /* check lower bound w.r.t. debugging solution */
1125
1127 {
1128 SCIP_EVENT event;
1129
1130 /* trigger a node deletion event */
1132 SCIP_CALL( SCIPeventChgNode(&event, *node) );
1133 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
1134 }
1135
1136 /* inform solution debugger, that the node has been freed */
1137 SCIP_CALL( SCIPdebugRemoveNode(blkmem, set, *node) );
1138
1139 /* check, if the node to be freed is the root node */
1140 isroot = (SCIPnodeGetDepth(*node) == 0);
1141
1142 /* free nodetype specific data, and release no longer needed LPI states */
1143 switch( SCIPnodeGetType(*node) )
1144 {
1146 assert(tree->focusnode == *node);
1147 assert(!SCIPtreeProbing(tree));
1148 SCIPerrorMessage("cannot free focus node - has to be converted into a dead end first\n");
1149 return SCIP_INVALIDDATA;
1151 assert(SCIPtreeProbing(tree));
1152 assert(SCIPnodeGetDepth(tree->probingroot) <= SCIPnodeGetDepth(*node));
1153 assert(SCIPnodeGetDepth(*node) > 0);
1154 SCIP_CALL( probingnodeFree(&((*node)->data.probingnode), blkmem, lp) );
1155 break;
1157 assert((*node)->data.sibling.arraypos >= 0);
1158 assert((*node)->data.sibling.arraypos < tree->nsiblings);
1159 assert(tree->siblings[(*node)->data.sibling.arraypos] == *node);
1160 if( tree->focuslpstatefork != NULL )
1161 {
1165 }
1166 treeRemoveSibling(tree, *node);
1167 break;
1169 assert((*node)->data.child.arraypos >= 0);
1170 assert((*node)->data.child.arraypos < tree->nchildren);
1171 assert(tree->children[(*node)->data.child.arraypos] == *node);
1172 /* The children capture the LPI state at the moment, where the focus node is
1173 * converted into a junction, pseudofork, fork, or subroot, and a new node is focused.
1174 * At the same time, they become siblings or leaves, such that freeing a child
1175 * of the focus node doesn't require to release the LPI state;
1176 * we don't need to call treeRemoveChild(), because this is done in nodeReleaseParent()
1177 */
1178 break;
1179 case SCIP_NODETYPE_LEAF:
1180 if( (*node)->data.leaf.lpstatefork != NULL )
1181 {
1182 SCIP_CALL( SCIPnodeReleaseLPIState((*node)->data.leaf.lpstatefork, blkmem, lp) );
1183 }
1184 break;
1187 break;
1189 SCIP_CALL( pseudoforkFree(&((*node)->data.pseudofork), blkmem, set, lp) );
1190 break;
1191 case SCIP_NODETYPE_FORK:
1192
1193 /* release special root LPI state capture which is used to keep the root LPI state over the whole solving
1194 * process
1195 */
1196 if( isroot )
1197 {
1198 SCIP_CALL( SCIPnodeReleaseLPIState(*node, blkmem, lp) );
1199 }
1200 SCIP_CALL( forkFree(&((*node)->data.fork), blkmem, set, lp) );
1201 break;
1203 SCIP_CALL( subrootFree(&((*node)->data.subroot), blkmem, set, lp) );
1204 break;
1206 SCIPerrorMessage("cannot free node as long it is refocused\n");
1207 return SCIP_INVALIDDATA;
1208 default:
1209 SCIPerrorMessage("unknown node type %d\n", SCIPnodeGetType(*node));
1210 return SCIP_INVALIDDATA;
1211 }
1212
1213 /* free common data */
1214 SCIP_CALL( SCIPconssetchgFree(&(*node)->conssetchg, blkmem, set) );
1215 SCIP_CALL( SCIPdomchgFree(&(*node)->domchg, blkmem, set, eventqueue, lp) );
1216 SCIP_CALL( nodeReleaseParent(*node, blkmem, set, stat, eventfilter, eventqueue, tree, lp) );
1217
1218 /* check, if the node is the current probing root */
1219 if( *node == tree->probingroot )
1220 {
1222 tree->probingroot = NULL;
1223 }
1224
1225 BMSfreeBlockMemory(blkmem, node);
1226
1227 /* delete the tree's root node pointer, if the freed node was the root */
1228 if( isroot )
1229 tree->root = NULL;
1230
1231 return SCIP_OKAY;
1232}
1233
1234/** cuts off node and whole sub tree from branch and bound tree
1235 *
1236 * @note must not be used on a leaf because the node priority queue remains untouched
1237 */
1239 SCIP_NODE* node, /**< node that should be cut off */
1240 SCIP_SET* set, /**< global SCIP settings */
1241 SCIP_STAT* stat, /**< problem statistics */
1242 SCIP_TREE* tree, /**< branch and bound tree */
1243 SCIP_PROB* transprob, /**< transformed problem after presolve */
1244 SCIP_PROB* origprob, /**< original problem */
1245 SCIP_REOPT* reopt, /**< reoptimization data structure */
1246 SCIP_LP* lp, /**< current LP */
1247 BMS_BLKMEM* blkmem /**< block memory */
1248 )
1249{
1250 SCIP_NODETYPE nodetype = SCIPnodeGetType(node);
1251
1252 assert(set != NULL);
1253 assert(stat != NULL);
1254 assert(tree != NULL);
1255 assert((tree->focusnode != NULL && SCIPnodeGetType(tree->focusnode) == SCIP_NODETYPE_REFOCUSNODE) || !set->misc_calcintegral || SCIPtreeGetLowerbound(tree, set) == stat->lastlowerbound); /*lint !e777*/
1256
1257 SCIPsetDebugMsg(set, "cutting off %s node #%" SCIP_LONGINT_FORMAT " at depth %d (cutoffdepth: %d)\n",
1258 node->active ? "active" : "inactive", SCIPnodeGetNumber(node), SCIPnodeGetDepth(node), tree->cutoffdepth);
1259
1260 /* check if the node should be stored for reoptimization */
1261 if( set->reopt_enable )
1262 {
1264 SCIPlpGetSolstat(lp), tree->root == node, tree->focusnode == node, node->lowerbound,
1265 tree->effectiverootdepth) );
1266 }
1267
1268 assert(nodetype != SCIP_NODETYPE_LEAF);
1269
1270 node->cutoff = TRUE;
1272 node->estimate = SCIPsetInfinity(set);
1273
1274 if( node->active && tree->cutoffdepth > node->depth )
1275 tree->cutoffdepth = node->depth;
1276
1277 if( node->depth == 0 )
1279
1280 if( nodetype == SCIP_NODETYPE_FOCUSNODE || nodetype == SCIP_NODETYPE_CHILD || nodetype == SCIP_NODETYPE_SIBLING )
1281 {
1282 /* update primal-dual integrals */
1283 if( set->misc_calcintegral )
1284 {
1285 SCIP_Real lowerbound = SCIPtreeGetLowerbound(tree, set);
1286
1287 assert(lowerbound <= SCIPsetInfinity(set));
1288
1289 /* updating the primal integral is only necessary if lower bound has increased since last evaluation */
1290 if( lowerbound > stat->lastlowerbound )
1291 SCIPstatUpdatePrimalDualIntegrals(stat, set, transprob, origprob, SCIPsetInfinity(set), lowerbound);
1292 }
1293
1294 SCIPvisualCutoffNode(stat->visual, set, stat, node, TRUE);
1295 }
1296
1297 return SCIP_OKAY;
1298}
1299
1300/** marks node, that propagation should be applied again the next time, a node of its subtree is focused */
1302 SCIP_NODE* node, /**< node that should be propagated again */
1303 SCIP_SET* set, /**< global SCIP settings */
1304 SCIP_STAT* stat, /**< problem statistics */
1305 SCIP_TREE* tree /**< branch and bound tree */
1306 )
1307{
1308 assert(node != NULL);
1309 assert(set != NULL);
1310 assert(stat != NULL);
1311 assert(tree != NULL);
1312
1313 if( !node->reprop )
1314 {
1315 node->reprop = TRUE;
1316 if( node->active )
1317 tree->repropdepth = MIN(tree->repropdepth, (int)node->depth);
1318
1319 SCIPvisualMarkedRepropagateNode(stat->visual, stat, node);
1320
1321 SCIPsetDebugMsg(set, "marked %s node #%" SCIP_LONGINT_FORMAT " at depth %d to be propagated again (repropdepth: %d)\n",
1322 node->active ? "active" : "inactive", SCIPnodeGetNumber(node), SCIPnodeGetDepth(node), tree->repropdepth);
1323 }
1324}
1325
1326/** marks node, that it is completely propagated in the current repropagation subtree level */
1328 SCIP_NODE* node, /**< node that should be marked to be propagated */
1329 SCIP_TREE* tree /**< branch and bound tree */
1330 )
1331{
1332 assert(node != NULL);
1333 assert(tree != NULL);
1334
1335 if( node->parent != NULL )
1336 node->repropsubtreemark = node->parent->repropsubtreemark; /*lint !e732*/
1337 node->reprop = FALSE;
1338
1339 /* if the node was the highest repropagation node in the path, update the repropdepth in the tree data */
1340 if( node->active && node->depth == tree->repropdepth )
1341 {
1342 do
1343 {
1344 assert(tree->repropdepth < tree->pathlen);
1345 assert(tree->path[tree->repropdepth]->active);
1346 assert(!tree->path[tree->repropdepth]->reprop);
1347 tree->repropdepth++;
1348 }
1349 while( tree->repropdepth < tree->pathlen && !tree->path[tree->repropdepth]->reprop );
1350 if( tree->repropdepth == tree->pathlen )
1351 tree->repropdepth = INT_MAX;
1352 }
1353}
1354
1355/** moves the subtree repropagation counter to the next value */
1356static
1358 SCIP_TREE* tree /**< branch and bound tree */
1359 )
1360{
1361 assert(tree != NULL);
1362
1363 tree->repropsubtreecount++;
1364 tree->repropsubtreecount %= (MAXREPROPMARK+1);
1365}
1366
1367/** applies propagation on the node, that was marked to be propagated again */
1368static
1370 SCIP_NODE* node, /**< node to apply propagation on */
1371 BMS_BLKMEM* blkmem, /**< block memory buffers */
1372 SCIP_SET* set, /**< global SCIP settings */
1373 SCIP_STAT* stat, /**< dynamic problem statistics */
1374 SCIP_PROB* transprob, /**< transformed problem */
1375 SCIP_PROB* origprob, /**< original problem */
1376 SCIP_PRIMAL* primal, /**< primal data */
1377 SCIP_TREE* tree, /**< branch and bound tree */
1378 SCIP_REOPT* reopt, /**< reoptimization data structure */
1379 SCIP_LP* lp, /**< current LP data */
1380 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1381 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1382 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1383 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1384 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1385 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1386 )
1387{
1388 SCIP_NODETYPE oldtype;
1389 SCIP_NODE* oldfocusnode;
1390 SCIP_NODE* oldfocuslpfork;
1391 SCIP_NODE* oldfocuslpstatefork;
1392 SCIP_NODE* oldfocussubroot;
1393 SCIP_Longint oldfocuslpstateforklpcount;
1394 int oldnchildren;
1395 int oldnsiblings;
1396 SCIP_Bool oldfocusnodehaslp;
1397 SCIP_Longint oldnboundchgs;
1398 SCIP_Bool initialreprop;
1399 SCIP_Bool clockisrunning;
1400
1401 assert(node != NULL);
1407 assert(node->active);
1408 assert(node->reprop || node->repropsubtreemark != node->parent->repropsubtreemark);
1409 assert(stat != NULL);
1410 assert(tree != NULL);
1411 assert(SCIPeventqueueIsDelayed(eventqueue));
1412 assert(cutoff != NULL);
1413
1414 SCIPsetDebugMsg(set, "propagating again node #%" SCIP_LONGINT_FORMAT " at depth %d\n", SCIPnodeGetNumber(node), SCIPnodeGetDepth(node));
1415 initialreprop = node->reprop;
1416
1417 SCIPvisualRepropagatedNode(stat->visual, stat, node);
1418
1419 /* process the delayed events in order to flush the problem changes */
1420 SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, primal, lp, branchcand, eventfilter) );
1421
1422 /* stop node activation timer */
1423 clockisrunning = SCIPclockIsRunning(stat->nodeactivationtime);
1424 if( clockisrunning )
1426
1427 /* mark the node refocused and temporarily install it as focus node */
1428 oldtype = (SCIP_NODETYPE)node->nodetype;
1429 oldfocusnode = tree->focusnode;
1430 oldfocuslpfork = tree->focuslpfork;
1431 oldfocuslpstatefork = tree->focuslpstatefork;
1432 oldfocussubroot = tree->focussubroot;
1433 oldfocuslpstateforklpcount = tree->focuslpstateforklpcount;
1434 oldnchildren = tree->nchildren;
1435 oldnsiblings = tree->nsiblings;
1436 oldfocusnodehaslp = tree->focusnodehaslp;
1437 node->nodetype = SCIP_NODETYPE_REFOCUSNODE; /*lint !e641*/
1438 tree->focusnode = node;
1439 tree->focuslpfork = NULL;
1440 tree->focuslpstatefork = NULL;
1441 tree->focussubroot = NULL;
1442 tree->focuslpstateforklpcount = -1;
1443 tree->nchildren = 0;
1444 tree->nsiblings = 0;
1445 tree->focusnodehaslp = FALSE;
1446
1447 /* propagate the domains again */
1448 oldnboundchgs = stat->nboundchgs;
1449 SCIP_CALL( SCIPpropagateDomains(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
1450 eventqueue, conflict, cliquetable, SCIPnodeGetDepth(node), 0, SCIP_PROPTIMING_ALWAYS, cutoff) );
1451 assert(!node->reprop || *cutoff);
1452 assert(node->parent == NULL || node->repropsubtreemark == node->parent->repropsubtreemark);
1454 assert(tree->focusnode == node);
1455 assert(tree->focuslpfork == NULL);
1456 assert(tree->focuslpstatefork == NULL);
1457 assert(tree->focussubroot == NULL);
1458 assert(tree->focuslpstateforklpcount == -1);
1459 assert(tree->nchildren == 0);
1460 assert(tree->nsiblings == 0);
1461 assert(tree->focusnodehaslp == FALSE);
1462 assert(stat->nboundchgs >= oldnboundchgs);
1463 stat->nreprops++;
1464 stat->nrepropboundchgs += stat->nboundchgs - oldnboundchgs;
1465 if( *cutoff )
1466 stat->nrepropcutoffs++;
1467
1468 SCIPsetDebugMsg(set, "repropagation %" SCIP_LONGINT_FORMAT " at depth %u changed %" SCIP_LONGINT_FORMAT " bounds (total reprop bound changes: %" SCIP_LONGINT_FORMAT "), cutoff: %u\n",
1469 stat->nreprops, node->depth, stat->nboundchgs - oldnboundchgs, stat->nrepropboundchgs, *cutoff);
1470
1471 /* if a propagation marked with the reprop flag was successful, we want to repropagate the whole subtree */
1472 /**@todo because repropsubtree is only a bit flag, we cannot mark a whole subtree a second time for
1473 * repropagation; use a (small) part of the node's bits to be able to store larger numbers,
1474 * and update tree->repropsubtreelevel with this number
1475 */
1476 if( initialreprop && !(*cutoff) && stat->nboundchgs > oldnboundchgs )
1477 {
1479 node->repropsubtreemark = tree->repropsubtreecount; /*lint !e732*/
1480 SCIPsetDebugMsg(set, "initial repropagation at depth %u changed %" SCIP_LONGINT_FORMAT " bounds -> repropagating subtree (new mark: %d)\n",
1481 node->depth, stat->nboundchgs - oldnboundchgs, tree->repropsubtreecount);
1482 assert((int)(node->repropsubtreemark) == tree->repropsubtreecount); /* bitfield must be large enough */
1483 }
1484
1485 /* reset the node's type and reinstall the old focus node */
1486 node->nodetype = oldtype; /*lint !e641*/
1487 tree->focusnode = oldfocusnode;
1488 tree->focuslpfork = oldfocuslpfork;
1489 tree->focuslpstatefork = oldfocuslpstatefork;
1490 tree->focussubroot = oldfocussubroot;
1491 tree->focuslpstateforklpcount = oldfocuslpstateforklpcount;
1492 tree->nchildren = oldnchildren;
1493 tree->nsiblings = oldnsiblings;
1494 tree->focusnodehaslp = oldfocusnodehaslp;
1495
1496 /* make the domain change data static again to save memory */
1498 {
1499 SCIP_CALL( SCIPdomchgMakeStatic(&node->domchg, blkmem, set, eventqueue, lp) );
1500 }
1501
1502 /* start node activation timer again */
1503 if( clockisrunning )
1505
1506 /* delay events in path switching */
1507 SCIP_CALL( SCIPeventqueueDelay(eventqueue) );
1508
1509 /* mark the node to be cut off if a cutoff was detected */
1510 if( *cutoff )
1511 {
1512 SCIP_CALL( SCIPnodeCutoff(node, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1513 }
1514
1515 return SCIP_OKAY;
1516}
1517
1518/** informs node, that it is now on the active path and applies any domain and constraint set changes */
1519static
1521 SCIP_NODE* node, /**< node to activate */
1522 BMS_BLKMEM* blkmem, /**< block memory buffers */
1523 SCIP_SET* set, /**< global SCIP settings */
1524 SCIP_STAT* stat, /**< problem statistics */
1525 SCIP_PROB* transprob, /**< transformed problem */
1526 SCIP_PROB* origprob, /**< original problem */
1527 SCIP_PRIMAL* primal, /**< primal data */
1528 SCIP_TREE* tree, /**< branch and bound tree */
1529 SCIP_REOPT* reopt, /**< reotimization data structure */
1530 SCIP_LP* lp, /**< current LP data */
1531 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1532 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1533 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1534 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1535 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1536 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1537 )
1538{
1539 assert(node != NULL);
1540 assert(!node->active);
1541 assert(stat != NULL);
1542 assert(tree != NULL);
1543 assert(!SCIPtreeProbing(tree));
1544 assert(cutoff != NULL);
1545
1546 SCIPsetDebugMsg(set, "activate node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d (reprop subtree mark: %u)\n",
1548
1549 /* apply lower bound, variable domain, and constraint set changes */
1550 if( node->parent != NULL )
1551 SCIPnodeUpdateLowerbound(node, stat, set, tree, transprob, origprob, node->parent->lowerbound);
1552 SCIP_CALL( SCIPconssetchgApply(node->conssetchg, blkmem, set, stat, (int) node->depth,
1554 SCIP_CALL( SCIPdomchgApply(node->domchg, blkmem, set, stat, lp, branchcand, eventqueue, (int) node->depth, cutoff) );
1555
1556 /* mark node active */
1557 node->active = TRUE;
1558 stat->nactivatednodes++;
1559
1560 /* check if the domain change produced a cutoff */
1561 if( *cutoff )
1562 {
1563 /* try to repropagate the node to see, if the propagation also leads to a conflict and a conflict constraint
1564 * could be generated; if propagation conflict analysis is turned off, repropagating the node makes no
1565 * sense, since it is already cut off
1566 */
1567 node->reprop = set->conf_enable && set->conf_useprop;
1568
1569 /* mark the node to be cut off */
1570 SCIP_CALL( SCIPnodeCutoff(node, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1571 }
1572
1573 /* propagate node again, if the reprop flag is set; in the new focus node, no repropagation is necessary, because
1574 * the focus node is propagated anyways
1575 */
1577 && (node->reprop || (node->parent != NULL && node->repropsubtreemark != node->parent->repropsubtreemark)) )
1578 {
1579 SCIP_Bool propcutoff;
1580
1581 SCIP_CALL( nodeRepropagate(node, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, conflict,
1582 eventfilter, eventqueue, cliquetable, &propcutoff) );
1583 *cutoff = *cutoff || propcutoff;
1584 }
1585
1586 return SCIP_OKAY;
1587}
1588
1589/** informs node, that it is no longer on the active path and undoes any domain and constraint set changes */
1590static
1592 SCIP_NODE* node, /**< node to deactivate */
1593 BMS_BLKMEM* blkmem, /**< block memory buffers */
1594 SCIP_SET* set, /**< global SCIP settings */
1595 SCIP_STAT* stat, /**< problem statistics */
1596 SCIP_TREE* tree, /**< branch and bound tree */
1597 SCIP_LP* lp, /**< current LP data */
1598 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1599 SCIP_EVENTQUEUE* eventqueue /**< event queue */
1600 )
1601{
1602 assert(node != NULL);
1603 assert(node->active);
1604 assert(tree != NULL);
1606
1607 SCIPsetDebugMsg(set, "deactivate node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d (reprop subtree mark: %u)\n",
1609
1610 /* undo domain and constraint set changes */
1611 SCIP_CALL( SCIPdomchgUndo(node->domchg, blkmem, set, stat, lp, branchcand, eventqueue) );
1612 SCIP_CALL( SCIPconssetchgUndo(node->conssetchg, blkmem, set, stat) );
1613
1614 /* mark node inactive */
1615 node->active = FALSE;
1616
1617 /* count number of deactivated nodes (ignoring probing switches) */
1618 if( !SCIPtreeProbing(tree) )
1619 stat->ndeactivatednodes++;
1620
1621 return SCIP_OKAY;
1622}
1623
1624/** adds constraint locally to the node and captures it; activates constraint, if node is active;
1625 * if a local constraint is added to the root node, it is automatically upgraded into a global constraint
1626 */
1628 SCIP_NODE* node, /**< node to add constraint to */
1629 BMS_BLKMEM* blkmem, /**< block memory */
1630 SCIP_SET* set, /**< global SCIP settings */
1631 SCIP_STAT* stat, /**< problem statistics */
1632 SCIP_TREE* tree, /**< branch and bound tree */
1633 SCIP_CONS* cons /**< constraint to add */
1634 )
1635{
1636 assert(node != NULL);
1637 assert(cons != NULL);
1638 assert(cons->validdepth <= SCIPnodeGetDepth(node));
1639 assert(tree != NULL);
1640 assert(tree->effectiverootdepth >= 0);
1641 assert(tree->root != NULL);
1642 assert(SCIPconsIsGlobal(cons) || SCIPnodeGetDepth(node) > tree->effectiverootdepth);
1643
1644#ifndef NDEBUG
1645 /* check if we add this constraint to the same scip, where we create the constraint */
1646 if( cons->scip != set->scip )
1647 {
1648 SCIPerrorMessage("try to add a constraint of another scip instance\n");
1649 return SCIP_INVALIDDATA;
1650 }
1651#endif
1652
1653 /* add constraint addition to the node's constraint set change data, and activate constraint if node is active */
1654 SCIP_CALL( SCIPconssetchgAddAddedCons(&node->conssetchg, blkmem, set, stat, cons, (int) node->depth,
1655 (SCIPnodeGetType(node) == SCIP_NODETYPE_FOCUSNODE), node->active) );
1656 assert(node->conssetchg != NULL);
1657 assert(node->conssetchg->addedconss != NULL);
1658 assert(!node->active || SCIPconsIsActive(cons));
1659
1660 /* if the constraint is added to an active node which is not a probing node, increment the corresponding counter */
1661 if( node->active && SCIPnodeGetType(node) != SCIP_NODETYPE_PROBINGNODE )
1662 stat->nactiveconssadded++;
1663
1664 return SCIP_OKAY;
1665}
1666
1667/** locally deletes constraint at the given node by disabling its separation, enforcing, and propagation capabilities
1668 * at the node; captures constraint; disables constraint, if node is active
1669 */
1671 SCIP_NODE* node, /**< node to add constraint to */
1672 BMS_BLKMEM* blkmem, /**< block memory */
1673 SCIP_SET* set, /**< global SCIP settings */
1674 SCIP_STAT* stat, /**< problem statistics */
1675 SCIP_TREE* tree, /**< branch and bound tree */
1676 SCIP_CONS* cons /**< constraint to locally delete */
1677 )
1678{
1679 assert(node != NULL);
1680 assert(tree != NULL);
1681 assert(cons != NULL);
1682
1683 SCIPsetDebugMsg(set, "disabling constraint <%s> at node at depth %u\n", cons->name, node->depth);
1684
1685 /* add constraint disabling to the node's constraint set change data */
1686 SCIP_CALL( SCIPconssetchgAddDisabledCons(&node->conssetchg, blkmem, set, cons) );
1687 assert(node->conssetchg != NULL);
1688 assert(node->conssetchg->disabledconss != NULL);
1689
1690 /* disable constraint, if node is active */
1691 if( node->active && cons->enabled && !cons->updatedisable )
1692 {
1693 SCIP_CALL( SCIPconsDisable(cons, set, stat) );
1694 }
1695
1696 return SCIP_OKAY;
1697}
1698
1699/** returns all constraints added to a given node */
1701 SCIP_NODE* node, /**< node */
1702 SCIP_CONS** addedconss, /**< array to store the constraints */
1703 int* naddedconss, /**< number of added constraints */
1704 int addedconsssize /**< size of the constraint array */
1705 )
1706{
1707 int cons;
1708
1709 assert(node != NULL );
1710 assert(node->conssetchg != NULL);
1711 assert(node->conssetchg->addedconss != NULL);
1712 assert(node->conssetchg->naddedconss >= 1);
1713
1714 *naddedconss = node->conssetchg->naddedconss;
1715
1716 /* check the size and return if the array is not large enough */
1717 if( addedconsssize < *naddedconss )
1718 return;
1719
1720 /* fill the array */
1721 for( cons = 0; cons < *naddedconss; cons++ )
1722 {
1723 addedconss[cons] = node->conssetchg->addedconss[cons];
1724 }
1725
1726 return;
1727}
1728
1729/** returns the number of added constraints to the given node */
1731 SCIP_NODE* node /**< node */
1732 )
1733{
1734 assert(node != NULL);
1735
1736 if( node->conssetchg == NULL )
1737 return 0;
1738 else
1739 return node->conssetchg->naddedconss;
1740}
1741
1742/** adds the given bound change to the list of pending bound changes */
1743static
1745 SCIP_TREE* tree, /**< branch and bound tree */
1746 SCIP_SET* set, /**< global SCIP settings */
1747 SCIP_NODE* node, /**< node to add bound change to */
1748 SCIP_VAR* var, /**< variable to change the bounds for */
1749 SCIP_Real newbound, /**< new value for bound */
1750 SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
1751 SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
1752 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
1753 int inferinfo, /**< user information for inference to help resolving the conflict */
1754 SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
1755 )
1756{
1757 assert(tree != NULL);
1758
1759 /* make sure that enough memory is allocated for the pendingbdchgs array */
1761
1762 /* capture the variable */
1763 SCIPvarCapture(var);
1764
1765 /* add the bound change to the pending list */
1766 tree->pendingbdchgs[tree->npendingbdchgs].node = node;
1767 tree->pendingbdchgs[tree->npendingbdchgs].var = var;
1768 tree->pendingbdchgs[tree->npendingbdchgs].newbound = newbound;
1769 tree->pendingbdchgs[tree->npendingbdchgs].boundtype = boundtype;
1770 tree->pendingbdchgs[tree->npendingbdchgs].infercons = infercons;
1771 tree->pendingbdchgs[tree->npendingbdchgs].inferprop = inferprop;
1772 tree->pendingbdchgs[tree->npendingbdchgs].inferinfo = inferinfo;
1773 tree->pendingbdchgs[tree->npendingbdchgs].probingchange = probingchange;
1774 tree->npendingbdchgs++;
1775
1776 /* check global pending boundchanges against debug solution */
1777 if( node->depth == 0 )
1778 {
1779#ifndef NDEBUG
1780 SCIP_Real bound = newbound;
1781
1782 /* get bound adjusted for integrality(, this should already be done) */
1783 SCIPvarAdjustBd(var, set, boundtype, &bound);
1784
1785 if( boundtype == SCIP_BOUNDTYPE_LOWER )
1786 {
1787 /* check that the bound is feasible */
1788 if( bound > SCIPvarGetUbGlobal(var) )
1789 {
1790 /* due to numerics we only want to be feasible in feasibility tolerance */
1793 }
1794 }
1795 else
1796 {
1797 assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1798
1799 /* check that the bound is feasible */
1800 if( bound < SCIPvarGetLbGlobal(var) )
1801 {
1802 /* due to numerics we only want to be feasible in feasibility tolerance */
1805 }
1806 }
1807 /* check that the given bound was already adjusted for integrality */
1808 assert(SCIPsetIsEQ(set, newbound, bound));
1809#endif
1810 if( boundtype == SCIP_BOUNDTYPE_LOWER )
1811 {
1812 /* check bound on debugging solution */
1813 SCIP_CALL( SCIPdebugCheckLbGlobal(set->scip, var, newbound) ); /*lint !e506 !e774*/
1814 }
1815 else
1816 {
1817 assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1818
1819 /* check bound on debugging solution */
1820 SCIP_CALL( SCIPdebugCheckUbGlobal(set->scip, var, newbound) ); /*lint !e506 !e774*/
1821 }
1822 }
1823
1824 return SCIP_OKAY;
1825}
1826
1827/** adds bound change with inference information to focus node, child of focus node, or probing node;
1828 * if possible, adjusts bound to integral value;
1829 * at most one of infercons and inferprop may be non-NULL
1830 */
1832 SCIP_NODE* node, /**< node to add bound change to */
1833 BMS_BLKMEM* blkmem, /**< block memory */
1834 SCIP_SET* set, /**< global SCIP settings */
1835 SCIP_STAT* stat, /**< problem statistics */
1836 SCIP_PROB* transprob, /**< transformed problem after presolve */
1837 SCIP_PROB* origprob, /**< original problem */
1838 SCIP_TREE* tree, /**< branch and bound tree */
1839 SCIP_REOPT* reopt, /**< reoptimization data structure */
1840 SCIP_LP* lp, /**< current LP data */
1841 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1842 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1843 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1844 SCIP_VAR* var, /**< variable to change the bounds for */
1845 SCIP_Real newbound, /**< new value for bound */
1846 SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
1847 SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
1848 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
1849 int inferinfo, /**< user information for inference to help resolving the conflict */
1850 SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
1851 )
1852{
1853 SCIP_VAR* infervar;
1854 SCIP_BOUNDTYPE inferboundtype;
1855 SCIP_Real oldlb;
1856 SCIP_Real oldub;
1857 SCIP_Real oldbound;
1858 SCIP_Bool useglobal;
1859
1860 useglobal = (int) node->depth <= tree->effectiverootdepth;
1861 if( useglobal )
1862 {
1863 oldlb = SCIPvarGetLbGlobal(var);
1864 oldub = SCIPvarGetUbGlobal(var);
1865 }
1866 else
1867 {
1868 oldlb = SCIPvarGetLbLocal(var);
1869 oldub = SCIPvarGetUbLocal(var);
1870 }
1871
1872 assert(node != NULL);
1877 || node->depth == 0);
1878 assert(set != NULL);
1879 assert(tree != NULL);
1880 assert(tree->effectiverootdepth >= 0);
1881 assert(tree->root != NULL);
1882 assert(var != NULL);
1883 assert(node->active || (infercons == NULL && inferprop == NULL));
1884 assert((SCIP_NODETYPE)node->nodetype == SCIP_NODETYPE_PROBINGNODE || !probingchange);
1885 assert((boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, newbound, oldlb))
1886 || (boundtype == SCIP_BOUNDTYPE_LOWER && newbound > oldlb && newbound * oldlb <= 0.0)
1887 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, oldub))
1888 || (boundtype == SCIP_BOUNDTYPE_UPPER && newbound < oldub && newbound * oldub <= 0.0));
1889
1890 SCIPsetDebugMsg(set, "adding boundchange at node %" SCIP_LONGINT_FORMAT " at depth %u to variable <%s>: old bounds=[%g,%g], new %s bound: %g (infer%s=<%s>, inferinfo=%d)\n",
1891 node->number, node->depth, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
1892 boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", newbound, infercons != NULL ? "cons" : "prop",
1893 infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo);
1894
1895 /* remember variable as inference variable, and get corresponding active variable, bound and bound type */
1896 infervar = var;
1897 inferboundtype = boundtype;
1898
1899 SCIP_CALL( SCIPvarGetProbvarBound(&var, &newbound, &boundtype) );
1900
1902 {
1903 SCIPerrorMessage("cannot change bounds of multi-aggregated variable <%s>\n", SCIPvarGetName(var));
1904 SCIPABORT();
1905 return SCIP_INVALIDDATA; /*lint !e527*/
1906 }
1908
1909 /* the variable may have changed, make sure we have the correct bounds */
1910 if( useglobal )
1911 {
1912 oldlb = SCIPvarGetLbGlobal(var);
1913 oldub = SCIPvarGetUbGlobal(var);
1914 }
1915 else
1916 {
1917 oldlb = SCIPvarGetLbLocal(var);
1918 oldub = SCIPvarGetUbLocal(var);
1919 }
1920 assert(SCIPsetIsLE(set, oldlb, oldub));
1921
1922 if( boundtype == SCIP_BOUNDTYPE_LOWER )
1923 {
1924 /* adjust lower bound w.r.t. to integrality */
1925 SCIPvarAdjustLb(var, set, &newbound);
1926 assert(SCIPsetIsFeasLE(set, newbound, oldub));
1927 oldbound = oldlb;
1928 newbound = MIN(newbound, oldub);
1929
1930 if ( set->stage == SCIP_STAGE_SOLVING && SCIPsetIsInfinity(set, newbound) )
1931 {
1932 SCIPerrorMessage("cannot change lower bound of variable <%s> to infinity.\n", SCIPvarGetName(var));
1933 SCIPABORT();
1934 return SCIP_INVALIDDATA; /*lint !e527*/
1935 }
1936 }
1937 else
1938 {
1939 assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1940
1941 /* adjust the new upper bound */
1942 SCIPvarAdjustUb(var, set, &newbound);
1943 assert(SCIPsetIsFeasGE(set, newbound, oldlb));
1944 oldbound = oldub;
1945 newbound = MAX(newbound, oldlb);
1946
1947 if ( set->stage == SCIP_STAGE_SOLVING && SCIPsetIsInfinity(set, -newbound) )
1948 {
1949 SCIPerrorMessage("cannot change upper bound of variable <%s> to minus infinity.\n", SCIPvarGetName(var));
1950 SCIPABORT();
1951 return SCIP_INVALIDDATA; /*lint !e527*/
1952 }
1953 }
1954
1955 /* after switching to the active variable, the bounds might become redundant
1956 * if this happens, ignore the bound change
1957 */
1958 if( (boundtype == SCIP_BOUNDTYPE_LOWER && !SCIPsetIsGT(set, newbound, oldlb))
1959 || (boundtype == SCIP_BOUNDTYPE_UPPER && !SCIPsetIsLT(set, newbound, oldub)) )
1960 return SCIP_OKAY;
1961
1962 SCIPsetDebugMsg(set, " -> transformed to active variable <%s>: old bounds=[%g,%g], new %s bound: %g, obj: %g\n",
1963 SCIPvarGetName(var), oldlb, oldub, boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", newbound,
1964 SCIPvarGetObj(var));
1965
1966 /* if the bound change takes place at an active node but is conflicting with the current local bounds,
1967 * we cannot apply it immediately because this would introduce inconsistencies to the bound change data structures
1968 * in the tree and to the bound change information data in the variable;
1969 * instead we have to remember the bound change as a pending bound change and mark the affected nodes on the active
1970 * path to be infeasible
1971 */
1972 if( node->active )
1973 {
1974 int conflictingdepth;
1975
1976 conflictingdepth = SCIPvarGetConflictingBdchgDepth(var, set, boundtype, newbound);
1977
1978 if( conflictingdepth >= 0 )
1979 {
1980 /* 0 would mean the bound change conflicts with a global bound */
1981 assert(conflictingdepth > 0);
1982 assert(conflictingdepth < tree->pathlen);
1983
1984 SCIPsetDebugMsg(set, " -> bound change <%s> %s %g violates current local bounds [%g,%g] since depth %d: remember for later application\n",
1985 SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", newbound,
1986 SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), conflictingdepth);
1987
1988 /* remember the pending bound change */
1989 SCIP_CALL( treeAddPendingBdchg(tree, set, node, var, newbound, boundtype, infercons, inferprop, inferinfo,
1990 probingchange) );
1991
1992 /* mark the node with the conflicting bound change to be cut off */
1993 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictingdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1994
1995 return SCIP_OKAY;
1996 }
1997 }
1998
1999 SCIPstatIncrement(stat, set, nboundchgs);
2000
2001 /* if we are in probing mode we have to additionally count the bound changes for the probing statistic */
2002 if( tree->probingroot != NULL )
2003 SCIPstatIncrement(stat, set, nprobboundchgs);
2004
2005 /* if the node is the root node: change local and global bound immediately */
2006 if( SCIPnodeGetDepth(node) <= tree->effectiverootdepth )
2007 {
2008 assert(node->active || tree->focusnode == NULL );
2010 assert(!probingchange);
2011
2012 SCIPsetDebugMsg(set, " -> bound change in root node: perform global bound change\n");
2013 SCIP_CALL( SCIPvarChgBdGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, newbound, boundtype) );
2014
2015 if( set->stage == SCIP_STAGE_SOLVING )
2016 {
2017 /* the root should be repropagated due to the bound change */
2018 SCIPnodePropagateAgain(tree->root, set, stat, tree);
2019 SCIPsetDebugMsg(set, "marked root node to be repropagated due to global bound change <%s>:[%g,%g] -> [%g,%g] found in depth %u\n",
2020 SCIPvarGetName(var), oldlb, oldub, boundtype == SCIP_BOUNDTYPE_LOWER ? newbound : oldlb,
2021 boundtype == SCIP_BOUNDTYPE_LOWER ? oldub : newbound, node->depth);
2022 }
2023
2024 return SCIP_OKAY;
2025 }
2026
2027 /* if the node is a child, or the bound is a temporary probing bound
2028 * - the bound change is a branching decision
2029 * - the child's lower bound can be updated due to the changed pseudo solution
2030 * otherwise:
2031 * - the bound change is an inference
2032 */
2033 if( SCIPnodeGetType(node) == SCIP_NODETYPE_CHILD || probingchange )
2034 {
2035 SCIP_Real newpseudoobjval;
2036 SCIP_Real lpsolval;
2037
2038 assert(!node->active || SCIPnodeGetType(node) == SCIP_NODETYPE_PROBINGNODE);
2039
2040 /* get the solution value of variable in last solved LP on the active path:
2041 * - if the LP was solved at the current node, the LP values of the columns are valid
2042 * - if the last solved LP was the one in the current lpstatefork, the LP value in the columns are still valid
2043 * - otherwise, the LP values are invalid
2044 */
2045 if( SCIPtreeHasCurrentNodeLP(tree)
2047 {
2048 lpsolval = SCIPvarGetLPSol(var);
2049 }
2050 else
2051 lpsolval = SCIP_INVALID;
2052
2053 /* remember the bound change as branching decision (infervar/infercons/inferprop are not important: use NULL) */
2054 SCIP_CALL( SCIPdomchgAddBoundchg(&node->domchg, blkmem, set, var, newbound, boundtype, SCIP_BOUNDCHGTYPE_BRANCHING,
2055 lpsolval, NULL, NULL, NULL, 0, inferboundtype) );
2056
2057 /* update the child's lower bound */
2058 if( set->misc_exactsolve )
2059 newpseudoobjval = SCIPlpGetModifiedProvedPseudoObjval(lp, set, var, oldbound, newbound, boundtype);
2060 else
2061 newpseudoobjval = SCIPlpGetModifiedPseudoObjval(lp, set, transprob, var, oldbound, newbound, boundtype);
2062 SCIPnodeUpdateLowerbound(node, stat, set, tree, transprob, origprob, newpseudoobjval);
2063 }
2064 else
2065 {
2066 /* check the inferred bound change on the debugging solution */
2067 SCIP_CALL( SCIPdebugCheckInference(blkmem, set, node, var, newbound, boundtype) ); /*lint !e506 !e774*/
2068
2069 /* remember the bound change as inference (lpsolval is not important: use 0.0) */
2070 SCIP_CALL( SCIPdomchgAddBoundchg(&node->domchg, blkmem, set, var, newbound, boundtype,
2072 0.0, infervar, infercons, inferprop, inferinfo, inferboundtype) );
2073 }
2074
2075 assert(node->domchg != NULL);
2076 assert(node->domchg->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
2077 assert(node->domchg->domchgdyn.boundchgs != NULL);
2078 assert(node->domchg->domchgdyn.nboundchgs > 0);
2079 assert(node->domchg->domchgdyn.boundchgs[node->domchg->domchgdyn.nboundchgs-1].var == var);
2080 assert(node->domchg->domchgdyn.boundchgs[node->domchg->domchgdyn.nboundchgs-1].newbound == newbound); /*lint !e777*/
2081
2082 /* if node is active, apply the bound change immediately */
2083 if( node->active )
2084 {
2085 SCIP_Bool cutoff;
2086
2087 /**@todo if the node is active, it currently must either be the effective root (see above) or the current node;
2088 * if a bound change to an intermediate active node should be added, we must make sure, the bound change
2089 * information array of the variable stays sorted (new info must be sorted in instead of putting it to
2090 * the end of the array), and we should identify now redundant bound changes that are applied at a
2091 * later node on the active path
2092 */
2093 assert(SCIPtreeGetCurrentNode(tree) == node);
2095 blkmem, set, stat, lp, branchcand, eventqueue, (int) node->depth, node->domchg->domchgdyn.nboundchgs-1, &cutoff) );
2096 assert(node->domchg->domchgdyn.boundchgs[node->domchg->domchgdyn.nboundchgs-1].var == var);
2097 assert(!cutoff);
2098 }
2099
2100 return SCIP_OKAY;
2101}
2102
2103/** adds bound change to focus node, or child of focus node, or probing node;
2104 * if possible, adjusts bound to integral value
2105 */
2107 SCIP_NODE* node, /**< node to add bound change to */
2108 BMS_BLKMEM* blkmem, /**< block memory */
2109 SCIP_SET* set, /**< global SCIP settings */
2110 SCIP_STAT* stat, /**< problem statistics */
2111 SCIP_PROB* transprob, /**< transformed problem after presolve */
2112 SCIP_PROB* origprob, /**< original problem */
2113 SCIP_TREE* tree, /**< branch and bound tree */
2114 SCIP_REOPT* reopt, /**< reoptimization data structure */
2115 SCIP_LP* lp, /**< current LP data */
2116 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2117 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2118 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2119 SCIP_VAR* var, /**< variable to change the bounds for */
2120 SCIP_Real newbound, /**< new value for bound */
2121 SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
2122 SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
2123 )
2124{
2125 SCIP_CALL( SCIPnodeAddBoundinfer(node, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2126 cliquetable, var, newbound, boundtype, NULL, NULL, 0, probingchange) );
2127
2128 return SCIP_OKAY;
2129}
2130
2131/** adds hole with inference information to focus node, child of focus node, or probing node;
2132 * if possible, adjusts bound to integral value;
2133 * at most one of infercons and inferprop may be non-NULL
2134 */
2136 SCIP_NODE* node, /**< node to add bound change to */
2137 BMS_BLKMEM* blkmem, /**< block memory */
2138 SCIP_SET* set, /**< global SCIP settings */
2139 SCIP_STAT* stat, /**< problem statistics */
2140 SCIP_TREE* tree, /**< branch and bound tree */
2141 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2142 SCIP_VAR* var, /**< variable to change the bounds for */
2143 SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
2144 SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
2145 SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
2146 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
2147 int inferinfo, /**< user information for inference to help resolving the conflict */
2148 SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
2149 SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
2150 )
2151{
2152 assert(node != NULL);
2157 || node->depth == 0);
2158 assert(blkmem != NULL);
2159 assert(set != NULL);
2160 assert(tree != NULL);
2161 assert(tree->effectiverootdepth >= 0);
2162 assert(tree->root != NULL);
2163 assert(var != NULL);
2164 assert(node->active || (infercons == NULL && inferprop == NULL));
2165 assert((SCIP_NODETYPE)node->nodetype == SCIP_NODETYPE_PROBINGNODE || !probingchange);
2166
2167 /* the interval should not be empty */
2168 assert(SCIPsetIsLT(set, left, right));
2169
2170#ifndef NDEBUG
2171 {
2172 SCIP_Real adjustedleft;
2173 SCIP_Real adjustedright;
2174
2175 adjustedleft = left;
2176 adjustedright = right;
2177
2178 SCIPvarAdjustUb(var, set, &adjustedleft);
2179 SCIPvarAdjustLb(var, set, &adjustedright);
2180
2181 assert(SCIPsetIsEQ(set, left, adjustedleft));
2182 assert(SCIPsetIsEQ(set, right, adjustedright));
2183 }
2184#endif
2185
2186 /* the hole should lay within the lower and upper bounds */
2187 assert(SCIPsetIsGE(set, left, SCIPvarGetLbLocal(var)));
2188 assert(SCIPsetIsLE(set, right, SCIPvarGetUbLocal(var)));
2189
2190 SCIPsetDebugMsg(set, "adding hole (%g,%g) at node at depth %u to variable <%s>: bounds=[%g,%g], (infer%s=<%s>, inferinfo=%d)\n",
2191 left, right, node->depth, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), infercons != NULL ? "cons" : "prop",
2192 infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo);
2193
2194 SCIP_CALL( SCIPvarGetProbvarHole(&var, &left, &right) );
2195
2197 {
2198 SCIPerrorMessage("cannot change bounds of multi-aggregated variable <%s>\n", SCIPvarGetName(var));
2199 SCIPABORT();
2200 return SCIP_INVALIDDATA; /*lint !e527*/
2201 }
2203
2204 SCIPsetDebugMsg(set, " -> transformed to active variable <%s>: hole (%g,%g), obj: %g\n", SCIPvarGetName(var), left, right, SCIPvarGetObj(var));
2205
2206 stat->nholechgs++;
2207
2208 /* if we are in probing mode we have to additionally count the bound changes for the probing statistic */
2209 if( tree->probingroot != NULL )
2210 stat->nprobholechgs++;
2211
2212 /* if the node is the root node: change local and global bound immediately */
2213 if( SCIPnodeGetDepth(node) <= tree->effectiverootdepth )
2214 {
2215 assert(node->active || tree->focusnode == NULL );
2217 assert(!probingchange);
2218
2219 SCIPsetDebugMsg(set, " -> hole added in root node: perform global domain change\n");
2220 SCIP_CALL( SCIPvarAddHoleGlobal(var, blkmem, set, stat, eventqueue, left, right, added) );
2221
2222 if( set->stage == SCIP_STAGE_SOLVING && (*added) )
2223 {
2224 /* the root should be repropagated due to the bound change */
2225 SCIPnodePropagateAgain(tree->root, set, stat, tree);
2226 SCIPsetDebugMsg(set, "marked root node to be repropagated due to global added hole <%s>: (%g,%g) found in depth %u\n",
2227 SCIPvarGetName(var), left, right, node->depth);
2228 }
2229
2230 return SCIP_OKAY;
2231 }
2232
2233 /**@todo add adding of local domain holes */
2234
2235 (*added) = FALSE;
2236 SCIPerrorMessage("WARNING: currently domain holes can only be handled globally!\n");
2237
2238 stat->nholechgs--;
2239
2240 /* if we are in probing mode we have to additionally count the bound changes for the probing statistic */
2241 if( tree->probingroot != NULL )
2242 stat->nprobholechgs--;
2243
2244 return SCIP_OKAY;
2245}
2246
2247/** adds hole change to focus node, or child of focus node */
2249 SCIP_NODE* node, /**< node to add bound change to */
2250 BMS_BLKMEM* blkmem, /**< block memory */
2251 SCIP_SET* set, /**< global SCIP settings */
2252 SCIP_STAT* stat, /**< problem statistics */
2253 SCIP_TREE* tree, /**< branch and bound tree */
2254 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2255 SCIP_VAR* var, /**< variable to change the bounds for */
2256 SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
2257 SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
2258 SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
2259 SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
2260 )
2261{
2262 assert(node != NULL);
2266 assert(blkmem != NULL);
2267
2268 SCIPsetDebugMsg(set, "adding hole (%g,%g) at node at depth %u of variable <%s>\n",
2269 left, right, node->depth, SCIPvarGetName(var));
2270
2271 SCIP_CALL( SCIPnodeAddHoleinfer(node, blkmem, set, stat, tree, eventqueue, var, left, right,
2272 NULL, NULL, 0, probingchange, added) );
2273
2274 /**@todo apply hole change on active nodes and issue event */
2275
2276 return SCIP_OKAY;
2277}
2278
2279/** applies the pending bound changes */
2280static
2282 SCIP_TREE* tree, /**< branch and bound tree */
2283 SCIP_REOPT* reopt, /**< reoptimization data structure */
2284 BMS_BLKMEM* blkmem, /**< block memory */
2285 SCIP_SET* set, /**< global SCIP settings */
2286 SCIP_STAT* stat, /**< problem statistics */
2287 SCIP_PROB* transprob, /**< transformed problem after presolve */
2288 SCIP_PROB* origprob, /**< original problem */
2289 SCIP_LP* lp, /**< current LP data */
2290 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2291 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2292 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
2293 )
2294{
2295 SCIP_VAR* var;
2296 int npendingbdchgs;
2297 int conflictdepth;
2298 int i;
2299
2300 assert(tree != NULL);
2301
2302 npendingbdchgs = tree->npendingbdchgs;
2303 for( i = 0; i < npendingbdchgs; ++i )
2304 {
2305 var = tree->pendingbdchgs[i].var;
2306 assert(SCIPnodeGetDepth(tree->pendingbdchgs[i].node) < tree->cutoffdepth);
2307
2308 conflictdepth = SCIPvarGetConflictingBdchgDepth(var, set, tree->pendingbdchgs[i].boundtype,
2309 tree->pendingbdchgs[i].newbound);
2310
2311 /* It can happen, that a pending bound change conflicts with the global bounds, because when it was collected, it
2312 * just conflicted with the local bounds, but a conflicting global bound change was applied afterwards. In this
2313 * case, we can cut off the node where the pending bound change should be applied.
2314 */
2315 if( conflictdepth == 0 )
2316 {
2317 SCIP_CALL( SCIPnodeCutoff(tree->pendingbdchgs[i].node, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2318
2319 if( ((int) tree->pendingbdchgs[i].node->depth) <= tree->effectiverootdepth )
2320 break; /* break here to clear all pending bound changes */
2321 else
2322 continue;
2323 }
2324
2325 assert(conflictdepth == -1);
2326
2327 SCIPsetDebugMsg(set, "applying pending bound change <%s>[%g,%g] %s %g\n", SCIPvarGetName(var),
2329 tree->pendingbdchgs[i].boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
2330 tree->pendingbdchgs[i].newbound);
2331
2332 /* ignore bounds that are now redundant (for example, multiple entries in the pendingbdchgs for the same
2333 * variable)
2334 */
2336 {
2337 SCIP_Real lb;
2338
2339 lb = SCIPvarGetLbLocal(var);
2340 if( !SCIPsetIsGT(set, tree->pendingbdchgs[i].newbound, lb) )
2341 continue;
2342 }
2343 else
2344 {
2345 SCIP_Real ub;
2346
2347 assert(tree->pendingbdchgs[i].boundtype == SCIP_BOUNDTYPE_UPPER);
2348 ub = SCIPvarGetUbLocal(var);
2349 if( !SCIPsetIsLT(set, tree->pendingbdchgs[i].newbound, ub) )
2350 continue;
2351 }
2352
2353 SCIP_CALL( SCIPnodeAddBoundinfer(tree->pendingbdchgs[i].node, blkmem, set, stat, transprob, origprob, tree, reopt,
2354 lp, branchcand, eventqueue, cliquetable, var, tree->pendingbdchgs[i].newbound, tree->pendingbdchgs[i].boundtype,
2356 tree->pendingbdchgs[i].probingchange) );
2357 assert(tree->npendingbdchgs == npendingbdchgs); /* this time, the bound change can be applied! */
2358 }
2359
2360 /* clear pending bound changes */
2361 for( i = 0; i < tree->npendingbdchgs; ++i )
2362 {
2363 var = tree->pendingbdchgs[i].var;
2364 assert(var != NULL);
2365
2366 /* release the variable */
2367 SCIP_CALL( SCIPvarRelease(&var, blkmem, set, eventqueue, lp) );
2368 }
2369
2370 tree->npendingbdchgs = 0;
2371
2372 return SCIP_OKAY;
2373}
2374
2375/** if given value is larger than the node's lower bound, sets the node's lower bound to the new value
2376 *
2377 * @note must not be used on a leaf because the node priority queue remains untouched
2378 */
2380 SCIP_NODE* node, /**< node to update lower bound for */
2381 SCIP_STAT* stat, /**< problem statistics */
2382 SCIP_SET* set, /**< global SCIP settings */
2383 SCIP_TREE* tree, /**< branch and bound tree */
2384 SCIP_PROB* transprob, /**< transformed problem after presolve */
2385 SCIP_PROB* origprob, /**< original problem */
2386 SCIP_Real newbound /**< new lower bound for the node (if it's larger than the old one) */
2387 )
2388{
2389 assert(stat != NULL);
2390 assert(set != NULL);
2391 assert(!SCIPsetIsInfinity(set, newbound));
2392 assert((tree->focusnode != NULL && SCIPnodeGetType(tree->focusnode) == SCIP_NODETYPE_REFOCUSNODE) || !set->misc_calcintegral || SCIPtreeGetLowerbound(tree, set) == stat->lastlowerbound); /*lint !e777*/
2393
2394 if( SCIPnodeGetLowerbound(node) < newbound )
2395 {
2396 SCIP_NODETYPE nodetype = SCIPnodeGetType(node);
2397
2398 assert(nodetype != SCIP_NODETYPE_LEAF);
2399
2400 node->lowerbound = newbound;
2401
2402 if( node->estimate < newbound )
2403 node->estimate = newbound;
2404
2405 if( node->depth == 0 )
2406 stat->rootlowerbound = newbound;
2407
2408 if( nodetype == SCIP_NODETYPE_FOCUSNODE || nodetype == SCIP_NODETYPE_CHILD || nodetype == SCIP_NODETYPE_SIBLING )
2409 {
2410 SCIP_Real lowerbound = SCIPtreeGetLowerbound(tree, set);
2411
2412 assert(lowerbound <= newbound);
2413
2414 /* updating the primal integral is only necessary if lower bound has increased since last evaluation */
2415 if( set->misc_calcintegral && lowerbound > stat->lastlowerbound )
2416 SCIPstatUpdatePrimalDualIntegrals(stat, set, transprob, origprob, SCIPsetInfinity(set), lowerbound);
2417
2418 SCIPvisualLowerbound(stat->visual, set, stat, lowerbound);
2419 }
2420 }
2421}
2422
2423/** updates lower bound of node using lower bound of LP */
2425 SCIP_NODE* node, /**< node to set lower bound for */
2426 SCIP_SET* set, /**< global SCIP settings */
2427 SCIP_STAT* stat, /**< problem statistics */
2428 SCIP_TREE* tree, /**< branch and bound tree */
2429 SCIP_PROB* transprob, /**< transformed problem after presolve */
2430 SCIP_PROB* origprob, /**< original problem */
2431 SCIP_LP* lp /**< LP data */
2432 )
2433{
2434 assert(set != NULL);
2435 assert(lp != NULL);
2436 assert(lp->flushed);
2437
2438 /* in case of iteration or time limit, the LP value may not be a valid dual bound */
2439 /* @todo check for dual feasibility of LP solution and use sub-optimal solution if they are dual feasible */
2441 return SCIP_OKAY;
2442
2443 /* check for cutoff */
2445 {
2446 SCIP_CALL( SCIPnodeCutoff(node, set, stat, tree, transprob, origprob, set->scip->reopt, lp, set->scip->mem->probmem) );
2447 }
2448 else
2449 {
2450 SCIP_Real lpobjval;
2451
2452 if( set->misc_exactsolve )
2453 {
2454 SCIP_CALL( SCIPlpGetProvedLowerbound(lp, set, &lpobjval) );
2455 }
2456 else
2457 lpobjval = SCIPlpGetObjval(lp, set, transprob);
2458
2459 SCIPnodeUpdateLowerbound(node, stat, set, tree, transprob, origprob, lpobjval);
2460 }
2461
2462 return SCIP_OKAY;
2463}
2464
2465/** change the node selection priority of the given child */
2467 SCIP_TREE* tree, /**< branch and bound tree */
2468 SCIP_NODE* child, /**< child to update the node selection priority */
2469 SCIP_Real priority /**< node selection priority value */
2470 )
2471{
2472 int pos;
2473
2474 assert( SCIPnodeGetType(child) == SCIP_NODETYPE_CHILD );
2475
2476 pos = child->data.child.arraypos;
2477 assert( pos >= 0 );
2478
2479 tree->childrenprio[pos] = priority;
2480}
2481
2482
2483/** sets the node's estimated bound to the new value */
2485 SCIP_NODE* node, /**< node to update lower bound for */
2486 SCIP_SET* set, /**< global SCIP settings */
2487 SCIP_Real newestimate /**< new estimated bound for the node */
2488 )
2489{
2490 assert(node != NULL);
2491 assert(set != NULL);
2492 assert(SCIPsetIsRelGE(set, newestimate, node->lowerbound));
2493
2494 /* due to numerical reasons we need this check, see https://git.zib.de/integer/scip/issues/2866 */
2495 if( node->lowerbound <= newestimate )
2496 node->estimate = newestimate;
2497}
2498
2499/** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
2501 SCIP_NODE* node, /**< node to propagate implications on */
2502 BMS_BLKMEM* blkmem, /**< block memory */
2503 SCIP_SET* set, /**< global SCIP settings */
2504 SCIP_STAT* stat, /**< problem statistics */
2505 SCIP_PROB* transprob, /**< transformed problem after presolve */
2506 SCIP_PROB* origprob, /**< original problem */
2507 SCIP_TREE* tree, /**< branch and bound tree */
2508 SCIP_REOPT* reopt, /**< reoptimization data structure */
2509 SCIP_LP* lp, /**< current LP data */
2510 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2511 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2512 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2513 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
2514 )
2515{
2516 int nboundchgs;
2517 int i;
2518
2519 assert(node != NULL);
2520 assert(SCIPnodeIsActive(node));
2524 assert(cutoff != NULL);
2525
2526 SCIPsetDebugMsg(set, "implication graph propagation of node #%" SCIP_LONGINT_FORMAT " in depth %d\n",
2527 SCIPnodeGetNumber(node), SCIPnodeGetDepth(node));
2528
2529 *cutoff = FALSE;
2530
2531 /* propagate all fixings of binary variables performed at this node */
2532 nboundchgs = SCIPdomchgGetNBoundchgs(node->domchg);
2533 for( i = 0; i < nboundchgs && !(*cutoff); ++i )
2534 {
2535 SCIP_BOUNDCHG* boundchg;
2536 SCIP_VAR* var;
2537
2538 boundchg = SCIPdomchgGetBoundchg(node->domchg, i);
2539
2540 /* ignore redundant bound changes */
2541 if( SCIPboundchgIsRedundant(boundchg) )
2542 continue;
2543
2544 var = SCIPboundchgGetVar(boundchg);
2545 if( SCIPvarIsBinary(var) )
2546 {
2547 SCIP_Bool varfixing;
2548 int nimpls;
2549 SCIP_VAR** implvars;
2550 SCIP_BOUNDTYPE* impltypes;
2551 SCIP_Real* implbounds;
2552 SCIP_CLIQUE** cliques;
2553 int ncliques;
2554 int j;
2555
2556 varfixing = (SCIPboundchgGetBoundtype(boundchg) == SCIP_BOUNDTYPE_LOWER);
2557 nimpls = SCIPvarGetNImpls(var, varfixing);
2558 implvars = SCIPvarGetImplVars(var, varfixing);
2559 impltypes = SCIPvarGetImplTypes(var, varfixing);
2560 implbounds = SCIPvarGetImplBounds(var, varfixing);
2561
2562 /* apply implications */
2563 for( j = 0; j < nimpls; ++j )
2564 {
2565 SCIP_Real lb;
2566 SCIP_Real ub;
2567
2568 /* @note should this be checked here (because SCIPnodeAddBoundinfer fails for multi-aggregated variables)
2569 * or should SCIPnodeAddBoundinfer() just return for multi-aggregated variables?
2570 */
2571 if( SCIPvarGetStatus(implvars[j]) == SCIP_VARSTATUS_MULTAGGR ||
2573 continue;
2574
2575 /* check for infeasibility */
2576 lb = SCIPvarGetLbLocal(implvars[j]);
2577 ub = SCIPvarGetUbLocal(implvars[j]);
2578 if( impltypes[j] == SCIP_BOUNDTYPE_LOWER )
2579 {
2580 if( SCIPsetIsFeasGT(set, implbounds[j], ub) )
2581 {
2582 *cutoff = TRUE;
2583 return SCIP_OKAY;
2584 }
2585 if( SCIPsetIsFeasLE(set, implbounds[j], lb) )
2586 continue;
2587 }
2588 else
2589 {
2590 if( SCIPsetIsFeasLT(set, implbounds[j], lb) )
2591 {
2592 *cutoff = TRUE;
2593 return SCIP_OKAY;
2594 }
2595 if( SCIPsetIsFeasGE(set, implbounds[j], ub) )
2596 continue;
2597 }
2598
2599 /* @note the implication might affect a fixed variable (after resolving (multi-)aggregations);
2600 * normally, the implication should have been deleted in that case, but this is only possible
2601 * if the implied variable has the reverse implication stored as a variable bound;
2602 * due to numerics, the variable bound may not be present and so the implication is not deleted
2603 */
2605 continue;
2606
2607 /* apply the implication */
2608 SCIP_CALL( SCIPnodeAddBoundinfer(node, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2609 eventqueue, cliquetable, implvars[j], implbounds[j], impltypes[j], NULL, NULL, 0, FALSE) );
2610 }
2611
2612 /* apply cliques */
2613 ncliques = SCIPvarGetNCliques(var, varfixing);
2614 cliques = SCIPvarGetCliques(var, varfixing);
2615 for( j = 0; j < ncliques; ++j )
2616 {
2617 SCIP_VAR** vars;
2618 SCIP_Bool* values;
2619 int nvars;
2620 int k;
2621
2622 nvars = SCIPcliqueGetNVars(cliques[j]);
2623 vars = SCIPcliqueGetVars(cliques[j]);
2624 values = SCIPcliqueGetValues(cliques[j]);
2625 for( k = 0; k < nvars; ++k )
2626 {
2627 SCIP_Real lb;
2628 SCIP_Real ub;
2629
2630 assert(SCIPvarIsBinary(vars[k]));
2631
2632 if( SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_MULTAGGR ||
2634 continue;
2635
2636 if( vars[k] == var && values[k] == varfixing )
2637 continue;
2638
2639 /* check for infeasibility */
2640 lb = SCIPvarGetLbLocal(vars[k]);
2641 ub = SCIPvarGetUbLocal(vars[k]);
2642 if( values[k] == FALSE )
2643 {
2644 if( ub < 0.5 )
2645 {
2646 *cutoff = TRUE;
2647 return SCIP_OKAY;
2648 }
2649 if( lb > 0.5 )
2650 continue;
2651 }
2652 else
2653 {
2654 if( lb > 0.5 )
2655 {
2656 *cutoff = TRUE;
2657 return SCIP_OKAY;
2658 }
2659 if( ub < 0.5 )
2660 continue;
2661 }
2662
2664 continue;
2665
2666 /* apply the clique implication */
2667 SCIP_CALL( SCIPnodeAddBoundinfer(node, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2668 eventqueue, cliquetable, vars[k], (SCIP_Real)(!values[k]), values[k] ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER,
2669 NULL, NULL, 0, FALSE) );
2670 }
2671 }
2672 }
2673 }
2674
2675 return SCIP_OKAY;
2676}
2677
2678
2679
2680
2681/*
2682 * Path Switching
2683 */
2684
2685/** updates the LP sizes of the active path starting at the given depth */
2686static
2688 SCIP_TREE* tree, /**< branch and bound tree */
2689 int startdepth /**< depth to start counting */
2690 )
2691{
2692 SCIP_NODE* node;
2693 int ncols;
2694 int nrows;
2695 int i;
2696
2697 assert(tree != NULL);
2698 assert(startdepth >= 0);
2699 assert(startdepth <= tree->pathlen);
2700
2701 if( startdepth == 0 )
2702 {
2703 ncols = 0;
2704 nrows = 0;
2705 }
2706 else
2707 {
2708 ncols = tree->pathnlpcols[startdepth-1];
2709 nrows = tree->pathnlprows[startdepth-1];
2710 }
2711
2712 for( i = startdepth; i < tree->pathlen; ++i )
2713 {
2714 node = tree->path[i];
2715 assert(node != NULL);
2716 assert(node->active);
2717 assert((int)(node->depth) == i);
2718
2719 switch( SCIPnodeGetType(node) )
2720 {
2722 assert(i == tree->pathlen-1 || SCIPtreeProbing(tree));
2723 break;
2725 assert(SCIPtreeProbing(tree));
2726 assert(i >= 1);
2727 assert(SCIPnodeGetType(tree->path[i-1]) == SCIP_NODETYPE_FOCUSNODE
2728 || (ncols == node->data.probingnode->ninitialcols && nrows == node->data.probingnode->ninitialrows));
2729 assert(ncols <= node->data.probingnode->ncols || !tree->focuslpconstructed);
2730 assert(nrows <= node->data.probingnode->nrows || !tree->focuslpconstructed);
2731 if( i < tree->pathlen-1 )
2732 {
2733 ncols = node->data.probingnode->ncols;
2734 nrows = node->data.probingnode->nrows;
2735 }
2736 else
2737 {
2738 /* for the current probing node, the initial LP size is stored in the path */
2739 ncols = node->data.probingnode->ninitialcols;
2740 nrows = node->data.probingnode->ninitialrows;
2741 }
2742 break;
2744 SCIPerrorMessage("sibling cannot be in the active path\n");
2745 SCIPABORT();
2746 return SCIP_INVALIDDATA; /*lint !e527*/
2748 SCIPerrorMessage("child cannot be in the active path\n");
2749 SCIPABORT();
2750 return SCIP_INVALIDDATA; /*lint !e527*/
2751 case SCIP_NODETYPE_LEAF:
2752 SCIPerrorMessage("leaf cannot be in the active path\n");
2753 SCIPABORT();
2754 return SCIP_INVALIDDATA; /*lint !e527*/
2756 SCIPerrorMessage("dead-end cannot be in the active path\n");
2757 SCIPABORT();
2758 return SCIP_INVALIDDATA; /*lint !e527*/
2760 break;
2762 assert(node->data.pseudofork != NULL);
2763 ncols += node->data.pseudofork->naddedcols;
2764 nrows += node->data.pseudofork->naddedrows;
2765 break;
2766 case SCIP_NODETYPE_FORK:
2767 assert(node->data.fork != NULL);
2768 ncols += node->data.fork->naddedcols;
2769 nrows += node->data.fork->naddedrows;
2770 break;
2772 assert(node->data.subroot != NULL);
2773 ncols = node->data.subroot->ncols;
2774 nrows = node->data.subroot->nrows;
2775 break;
2777 SCIPerrorMessage("node cannot be of type REFOCUSNODE at this point\n");
2778 SCIPABORT();
2779 return SCIP_INVALIDDATA; /*lint !e527*/
2780 default:
2781 SCIPerrorMessage("unknown node type %d\n", SCIPnodeGetType(node));
2782 SCIPABORT();
2783 return SCIP_INVALIDDATA; /*lint !e527*/
2784 }
2785 tree->pathnlpcols[i] = ncols;
2786 tree->pathnlprows[i] = nrows;
2787 }
2788 return SCIP_OKAY;
2789}
2790
2791/** finds the common fork node, the new LP state defining fork, and the new focus subroot, if the path is switched to
2792 * the given node
2793 */
2794static
2796 SCIP_TREE* tree, /**< branch and bound tree */
2797 SCIP_NODE* node, /**< new focus node, or NULL */
2798 SCIP_NODE** commonfork, /**< pointer to store common fork node of old and new focus node */
2799 SCIP_NODE** newlpfork, /**< pointer to store the new LP defining fork node */
2800 SCIP_NODE** newlpstatefork, /**< pointer to store the new LP state defining fork node */
2801 SCIP_NODE** newsubroot, /**< pointer to store the new subroot node */
2802 SCIP_Bool* cutoff /**< pointer to store whether the given node can be cut off and no path switching
2803 * should be performed */
2804 )
2805{
2806 SCIP_NODE* fork;
2807 SCIP_NODE* lpfork;
2808 SCIP_NODE* lpstatefork;
2809 SCIP_NODE* subroot;
2810
2811 assert(tree != NULL);
2812 assert(tree->root != NULL);
2813 assert((tree->focusnode == NULL) == !tree->root->active);
2814 assert(tree->focuslpfork == NULL || tree->focusnode != NULL);
2815 assert(tree->focuslpfork == NULL || tree->focuslpfork->depth < tree->focusnode->depth);
2816 assert(tree->focuslpstatefork == NULL || tree->focuslpfork != NULL);
2817 assert(tree->focuslpstatefork == NULL || tree->focuslpstatefork->depth <= tree->focuslpfork->depth);
2818 assert(tree->focussubroot == NULL || tree->focuslpstatefork != NULL);
2819 assert(tree->focussubroot == NULL || tree->focussubroot->depth <= tree->focuslpstatefork->depth);
2820 assert(tree->cutoffdepth >= 0);
2821 assert(tree->cutoffdepth == INT_MAX || tree->cutoffdepth < tree->pathlen);
2822 assert(tree->cutoffdepth == INT_MAX || tree->path[tree->cutoffdepth]->cutoff);
2823 assert(tree->repropdepth >= 0);
2824 assert(tree->repropdepth == INT_MAX || tree->repropdepth < tree->pathlen);
2825 assert(tree->repropdepth == INT_MAX || tree->path[tree->repropdepth]->reprop);
2826 assert(commonfork != NULL);
2827 assert(newlpfork != NULL);
2828 assert(newlpstatefork != NULL);
2829 assert(newsubroot != NULL);
2830 assert(cutoff != NULL);
2831
2832 *commonfork = NULL;
2833 *newlpfork = NULL;
2834 *newlpstatefork = NULL;
2835 *newsubroot = NULL;
2836 *cutoff = FALSE;
2837
2838 /* if the new focus node is NULL, there is no common fork node, and the new LP fork, LP state fork, and subroot
2839 * are NULL
2840 */
2841 if( node == NULL )
2842 {
2843 tree->cutoffdepth = INT_MAX;
2844 tree->repropdepth = INT_MAX;
2845 return;
2846 }
2847
2848 /* check if the new node is marked to be cut off */
2849 if( node->cutoff )
2850 {
2851 *cutoff = TRUE;
2852 return;
2853 }
2854
2855 /* if the old focus node is NULL, there is no common fork node, and we have to search the new LP fork, LP state fork
2856 * and subroot
2857 */
2858 if( tree->focusnode == NULL )
2859 {
2860 assert(!tree->root->active);
2861 assert(tree->pathlen == 0);
2862 assert(tree->cutoffdepth == INT_MAX);
2863 assert(tree->repropdepth == INT_MAX);
2864
2865 lpfork = node;
2868 {
2869 lpfork = lpfork->parent;
2870 if( lpfork == NULL )
2871 return;
2872 if( lpfork->cutoff )
2873 {
2874 *cutoff = TRUE;
2875 return;
2876 }
2877 }
2878 *newlpfork = lpfork;
2879
2880 lpstatefork = lpfork;
2881 while( SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_FORK && SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_SUBROOT )
2882 {
2883 lpstatefork = lpstatefork->parent;
2884 if( lpstatefork == NULL )
2885 return;
2886 if( lpstatefork->cutoff )
2887 {
2888 *cutoff = TRUE;
2889 return;
2890 }
2891 }
2892 *newlpstatefork = lpstatefork;
2893
2894 subroot = lpstatefork;
2895 while( SCIPnodeGetType(subroot) != SCIP_NODETYPE_SUBROOT )
2896 {
2897 subroot = subroot->parent;
2898 if( subroot == NULL )
2899 return;
2900 if( subroot->cutoff )
2901 {
2902 *cutoff = TRUE;
2903 return;
2904 }
2905 }
2906 *newsubroot = subroot;
2907
2908 fork = subroot;
2909 while( fork->parent != NULL )
2910 {
2911 fork = fork->parent;
2912 if( fork->cutoff )
2913 {
2914 *cutoff = TRUE;
2915 return;
2916 }
2917 }
2918 return;
2919 }
2920
2921 /* find the common fork node, the new LP defining fork, the new LP state defining fork, and the new focus subroot */
2922 fork = node;
2923 lpfork = NULL;
2924 lpstatefork = NULL;
2925 subroot = NULL;
2926 assert(fork != NULL);
2927
2928 while( !fork->active )
2929 {
2930 fork = fork->parent;
2931 assert(fork != NULL); /* because the root is active, there must be a common fork node */
2932
2933 if( fork->cutoff )
2934 {
2935 *cutoff = TRUE;
2936 return;
2937 }
2938 if( lpfork == NULL
2941 lpfork = fork;
2942 if( lpstatefork == NULL
2944 lpstatefork = fork;
2945 if( subroot == NULL && SCIPnodeGetType(fork) == SCIP_NODETYPE_SUBROOT )
2946 subroot = fork;
2947 }
2948 assert(lpfork == NULL || !lpfork->active || lpfork == fork);
2949 assert(lpstatefork == NULL || !lpstatefork->active || lpstatefork == fork);
2950 assert(subroot == NULL || !subroot->active || subroot == fork);
2951 SCIPdebugMessage("find switch forks: forkdepth=%u\n", fork->depth);
2952
2953 /* if the common fork node is below the current cutoff depth, the cutoff node is an ancestor of the common fork
2954 * and thus an ancestor of the new focus node, s.t. the new node can also be cut off
2955 */
2956 assert((int)fork->depth != tree->cutoffdepth);
2957 if( (int)fork->depth > tree->cutoffdepth )
2958 {
2959#ifndef NDEBUG
2960 while( !fork->cutoff )
2961 {
2962 fork = fork->parent;
2963 assert(fork != NULL);
2964 }
2965 assert((int)fork->depth >= tree->cutoffdepth);
2966#endif
2967 *cutoff = TRUE;
2968 return;
2969 }
2970 tree->cutoffdepth = INT_MAX;
2971
2972 /* if not already found, continue searching the LP defining fork; it cannot be deeper than the common fork */
2973 if( lpfork == NULL )
2974 {
2975 if( tree->focuslpfork != NULL && tree->focuslpfork->depth > fork->depth )
2976 {
2977 /* focuslpfork is not on the same active path as the new node: we have to continue searching */
2978 lpfork = fork;
2979 while( lpfork != NULL
2983 {
2984 assert(lpfork->active);
2985 lpfork = lpfork->parent;
2986 }
2987 }
2988 else
2989 {
2990 /* focuslpfork is on the same active path as the new node: old and new node have the same lpfork */
2991 lpfork = tree->focuslpfork;
2992 }
2993 assert(lpfork == NULL || lpfork->depth <= fork->depth);
2994 assert(lpfork == NULL || lpfork->active);
2995 }
2996 assert(lpfork == NULL
3000 SCIPdebugMessage("find switch forks: lpforkdepth=%d\n", lpfork == NULL ? -1 : (int)(lpfork->depth));
3001
3002 /* if not already found, continue searching the LP state defining fork; it cannot be deeper than the
3003 * LP defining fork and the common fork
3004 */
3005 if( lpstatefork == NULL )
3006 {
3007 if( tree->focuslpstatefork != NULL && tree->focuslpstatefork->depth > fork->depth )
3008 {
3009 /* focuslpstatefork is not on the same active path as the new node: we have to continue searching */
3010 if( lpfork != NULL && lpfork->depth < fork->depth )
3011 lpstatefork = lpfork;
3012 else
3013 lpstatefork = fork;
3014 while( lpstatefork != NULL
3015 && SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_FORK
3016 && SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_SUBROOT )
3017 {
3018 assert(lpstatefork->active);
3019 lpstatefork = lpstatefork->parent;
3020 }
3021 }
3022 else
3023 {
3024 /* focuslpstatefork is on the same active path as the new node: old and new node have the same lpstatefork */
3025 lpstatefork = tree->focuslpstatefork;
3026 }
3027 assert(lpstatefork == NULL || lpstatefork->depth <= fork->depth);
3028 assert(lpstatefork == NULL || lpstatefork->active);
3029 }
3030 assert(lpstatefork == NULL
3031 || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK
3032 || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT);
3033 assert(lpstatefork == NULL || (lpfork != NULL && lpstatefork->depth <= lpfork->depth));
3034 SCIPdebugMessage("find switch forks: lpstateforkdepth=%d\n", lpstatefork == NULL ? -1 : (int)(lpstatefork->depth));
3035
3036 /* if not already found, continue searching the subroot; it cannot be deeper than the LP defining fork, the
3037 * LP state fork and the common fork
3038 */
3039 if( subroot == NULL )
3040 {
3041 if( tree->focussubroot != NULL && tree->focussubroot->depth > fork->depth )
3042 {
3043 /* focussubroot is not on the same active path as the new node: we have to continue searching */
3044 if( lpstatefork != NULL && lpstatefork->depth < fork->depth )
3045 subroot = lpstatefork;
3046 else if( lpfork != NULL && lpfork->depth < fork->depth )
3047 subroot = lpfork;
3048 else
3049 subroot = fork;
3050 while( subroot != NULL && SCIPnodeGetType(subroot) != SCIP_NODETYPE_SUBROOT )
3051 {
3052 assert(subroot->active);
3053 subroot = subroot->parent;
3054 }
3055 }
3056 else
3057 subroot = tree->focussubroot;
3058 assert(subroot == NULL || subroot->depth <= fork->depth);
3059 assert(subroot == NULL || subroot->active);
3060 }
3061 assert(subroot == NULL || SCIPnodeGetType(subroot) == SCIP_NODETYPE_SUBROOT);
3062 assert(subroot == NULL || (lpstatefork != NULL && subroot->depth <= lpstatefork->depth));
3063 SCIPdebugMessage("find switch forks: subrootdepth=%d\n", subroot == NULL ? -1 : (int)(subroot->depth));
3064
3065 /* if a node prior to the common fork should be repropagated, we select the node to be repropagated as common
3066 * fork in order to undo all bound changes up to this node, repropagate the node, and redo the bound changes
3067 * afterwards
3068 */
3069 if( (int)fork->depth > tree->repropdepth )
3070 {
3071 fork = tree->path[tree->repropdepth];
3072 assert(fork->active);
3073 assert(fork->reprop);
3074 }
3075
3076 *commonfork = fork;
3077 *newlpfork = lpfork;
3078 *newlpstatefork = lpstatefork;
3079 *newsubroot = subroot;
3080
3081#ifndef NDEBUG
3082 while( fork != NULL )
3083 {
3084 assert(fork->active);
3085 assert(!fork->cutoff);
3086 assert(fork->parent == NULL || !fork->parent->reprop);
3087 fork = fork->parent;
3088 }
3089#endif
3090 tree->repropdepth = INT_MAX;
3091}
3092
3093/** switches the active path to the new focus node, frees dead end, applies domain and constraint set changes */
3094static
3096 SCIP_TREE* tree, /**< branch and bound tree */
3097 SCIP_REOPT* reopt, /**< reoptimization data structure */
3098 BMS_BLKMEM* blkmem, /**< block memory buffers */
3099 SCIP_SET* set, /**< global SCIP settings */
3100 SCIP_STAT* stat, /**< problem statistics */
3101 SCIP_PROB* transprob, /**< transformed problem after presolve */
3102 SCIP_PROB* origprob, /**< original problem */
3103 SCIP_PRIMAL* primal, /**< primal data */
3104 SCIP_LP* lp, /**< current LP data */
3105 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3106 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3107 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3108 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3109 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3110 SCIP_NODE* fork, /**< common fork node of old and new focus node, or NULL */
3111 SCIP_NODE* focusnode, /**< new focus node, or NULL */
3112 SCIP_Bool* cutoff /**< pointer to store whether the new focus node can be cut off */
3113 )
3114{
3115 int newappliedeffectiverootdepth;
3116 int focusnodedepth; /* depth of the new focus node, or -1 if focusnode == NULL */
3117 int forkdepth; /* depth of the common subroot/fork/pseudofork/junction node, or -1 if no common fork exists */
3118 int i;
3119 SCIP_NODE* oldfocusnode;
3120
3121 assert(tree != NULL);
3122 assert(fork == NULL || (fork->active && !fork->cutoff));
3123 assert(fork == NULL || focusnode != NULL);
3124 assert(focusnode == NULL || (!focusnode->active && !focusnode->cutoff));
3125 assert(focusnode == NULL || SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
3126 assert(cutoff != NULL);
3127
3128 /* set new focus node */
3129 oldfocusnode = tree->focusnode;
3130 tree->focusnode = focusnode;
3131
3132 SCIPsetDebugMsg(set, "switch path: old pathlen=%d\n", tree->pathlen);
3133
3134 /* get the nodes' depths */
3135 focusnodedepth = (focusnode != NULL ? (int)focusnode->depth : -1);
3136 forkdepth = (fork != NULL ? (int)fork->depth : -1);
3137 assert(forkdepth <= focusnodedepth);
3138 assert(forkdepth < tree->pathlen);
3139
3140 /* delay events in node deactivations to fork and node activations to parent of new focus node */
3141 SCIP_CALL( SCIPeventqueueDelay(eventqueue) );
3142
3143 /* undo the domain and constraint set changes of the old active path by deactivating the path's nodes */
3144 for( i = tree->pathlen-1; i > forkdepth; --i )
3145 {
3146 SCIP_CALL( nodeDeactivate(tree->path[i], blkmem, set, stat, tree, lp, branchcand, eventqueue) );
3147 }
3148 tree->pathlen = forkdepth+1;
3149
3150 /* apply the pending bound changes */
3151 SCIP_CALL( treeApplyPendingBdchgs(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, cliquetable) );
3152
3153 /* create the new active path */
3154 SCIP_CALL( treeEnsurePathMem(tree, set, focusnodedepth+1) );
3155
3156 while( focusnode != fork )
3157 {
3158 assert(focusnode != NULL);
3159 assert(!focusnode->active);
3160 assert(!focusnode->cutoff);
3161 /* coverity[var_deref_op] */
3162 tree->path[focusnode->depth] = focusnode;
3163 focusnode = focusnode->parent;
3164 }
3165
3166 /* if the old focus node is a dead end (has no children), delete it */
3167 if( oldfocusnode != NULL )
3168 {
3169 SCIP_Bool freeNode;
3170
3171 switch( SCIPnodeGetType(oldfocusnode) )
3172 {
3176 case SCIP_NODETYPE_LEAF:
3178 freeNode = FALSE;
3179 break;
3181 freeNode = TRUE;
3182 break;
3184 freeNode = (oldfocusnode->data.junction.nchildren == 0);
3185 break;
3187 freeNode = (oldfocusnode->data.pseudofork->nchildren == 0);
3188 break;
3189 case SCIP_NODETYPE_FORK:
3190 freeNode = (oldfocusnode->data.fork->nchildren == 0);
3191 break;
3193 freeNode = (oldfocusnode->data.subroot->nchildren == 0);
3194 break;
3196 SCIPerrorMessage("probing node could not be the focus node\n");
3197 return SCIP_INVALIDDATA;
3198 default:
3199 SCIPerrorMessage("unknown node type %d\n", SCIPnodeGetType(oldfocusnode));
3200 return SCIP_INVALIDDATA;
3201 }
3202
3203 if( freeNode )
3204 {
3205 assert(tree->appliedeffectiverootdepth <= tree->effectiverootdepth);
3206 SCIP_CALL( SCIPnodeFree(&oldfocusnode, blkmem, set, stat, eventfilter, eventqueue, tree, lp) );
3207 assert(tree->effectiverootdepth <= focusnodedepth || tree->focusnode == NULL);
3208 }
3209 }
3210
3211 /* apply effective root shift up to the new focus node */
3212 *cutoff = FALSE;
3213 newappliedeffectiverootdepth = MIN(tree->effectiverootdepth, focusnodedepth);
3214
3215 /* promote the constraint set and bound changes up to the new effective root to be global changes */
3216 if( tree->appliedeffectiverootdepth < newappliedeffectiverootdepth )
3217 {
3219 "shift effective root from depth %d to %d: applying constraint set and bound changes to global problem\n",
3220 tree->appliedeffectiverootdepth, newappliedeffectiverootdepth);
3221
3222 /* at first globalize constraint changes to update constraint handlers before changing bounds */
3223 for( i = tree->appliedeffectiverootdepth + 1; i <= newappliedeffectiverootdepth; ++i )
3224 {
3225 SCIPsetDebugMsg(set, " -> applying constraint set changes of depth %d\n", i);
3226
3227 SCIP_CALL( SCIPconssetchgMakeGlobal(&tree->path[i]->conssetchg, blkmem, set, stat, transprob, reopt) );
3228 }
3229
3230 /* at last globalize bound changes triggering delayed events processed after the path switch */
3231 for( i = tree->appliedeffectiverootdepth + 1; i <= newappliedeffectiverootdepth && !(*cutoff); ++i )
3232 {
3233 SCIPsetDebugMsg(set, " -> applying bound changes of depth %d\n", i);
3234
3235 SCIP_CALL( SCIPdomchgApplyGlobal(tree->path[i]->domchg, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, cutoff) );
3236 }
3237
3238 /* update applied effective root depth */
3239 tree->appliedeffectiverootdepth = newappliedeffectiverootdepth;
3240 }
3241
3242 /* fork might be cut off when applying the pending bound changes */
3243 if( fork != NULL && fork->cutoff )
3244 *cutoff = TRUE;
3245 else if( fork != NULL && fork->reprop && !(*cutoff) )
3246 {
3247 /* propagate common fork again, if the reprop flag is set */
3248 assert(tree->path[forkdepth] == fork);
3249 assert(fork->active);
3250 assert(!fork->cutoff);
3251
3252 SCIP_CALL( nodeRepropagate(fork, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, conflict,
3253 eventfilter, eventqueue, cliquetable, cutoff) );
3254 }
3255 assert(fork != NULL || !(*cutoff));
3256
3257 /* Apply domain and constraint set changes of the new path by activating the path's nodes;
3258 * on the way, domain propagation might be applied again to the path's nodes, which can result in the cutoff of
3259 * the node (and its subtree).
3260 * We only activate all nodes down to the parent of the new focus node, because the events in this process are
3261 * delayed, which means that multiple changes of a bound of a variable are merged (and might even be cancelled out,
3262 * if the bound is first relaxed when deactivating a node on the old path and then tightened to the same value
3263 * when activating a node on the new path).
3264 * This is valid for all nodes down to the parent of the new focus node, since they have already been propagated.
3265 * Bound change events on the new focus node, however, must not be cancelled out, since they need to be propagated
3266 * and thus, the event must be thrown and catched by the constraint handlers to mark constraints for propagation.
3267 */
3268 for( i = forkdepth+1; i < focusnodedepth && !(*cutoff); ++i )
3269 {
3270 assert(!tree->path[i]->cutoff);
3271 assert(tree->pathlen == i);
3272
3273 /* activate the node, and apply domain propagation if the reprop flag is set */
3274 tree->pathlen++;
3275 SCIP_CALL( nodeActivate(tree->path[i], blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
3276 conflict, eventfilter, eventqueue, cliquetable, cutoff) );
3277 }
3278
3279 /* process the delayed events */
3280 SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, primal, lp, branchcand, eventfilter) );
3281
3282 /* activate the new focus node; there is no need to delay these events */
3283 if( !(*cutoff) && (i == focusnodedepth) )
3284 {
3285 assert(!tree->path[focusnodedepth]->cutoff);
3286 assert(tree->pathlen == focusnodedepth);
3287
3288 /* activate the node, and apply domain propagation if the reprop flag is set */
3289 tree->pathlen++;
3290 SCIP_CALL( nodeActivate(tree->path[focusnodedepth], blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
3291 conflict, eventfilter, eventqueue, cliquetable, cutoff) );
3292 }
3293
3294 /* mark new focus node to be cut off, if a cutoff was found */
3295 if( *cutoff )
3296 {
3297 SCIP_CALL( SCIPnodeCutoff(tree->focusnode, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
3298 }
3299
3300 /* count the new LP sizes of the path */
3301 SCIP_CALL( treeUpdatePathLPSize(tree, forkdepth+1) );
3302
3303 SCIPsetDebugMsg(set, "switch path: new pathlen=%d\n", tree->pathlen);
3304
3305 return SCIP_OKAY;
3306}
3307
3308/** loads the subroot's LP data */
3309static
3311 SCIP_NODE* subroot, /**< subroot node to construct LP for */
3312 BMS_BLKMEM* blkmem, /**< block memory buffers */
3313 SCIP_SET* set, /**< global SCIP settings */
3314 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3315 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3316 SCIP_LP* lp /**< current LP data */
3317 )
3318{
3319 SCIP_COL** cols;
3320 SCIP_ROW** rows;
3321 int ncols;
3322 int nrows;
3323 int c;
3324 int r;
3325
3326 assert(subroot != NULL);
3327 assert(SCIPnodeGetType(subroot) == SCIP_NODETYPE_SUBROOT);
3328 assert(subroot->data.subroot != NULL);
3329 assert(blkmem != NULL);
3330 assert(set != NULL);
3331 assert(lp != NULL);
3332
3333 cols = subroot->data.subroot->cols;
3334 rows = subroot->data.subroot->rows;
3335 ncols = subroot->data.subroot->ncols;
3336 nrows = subroot->data.subroot->nrows;
3337
3338 assert(ncols == 0 || cols != NULL);
3339 assert(nrows == 0 || rows != NULL);
3340
3341 for( c = 0; c < ncols; ++c )
3342 {
3343 SCIP_CALL( SCIPlpAddCol(lp, set, cols[c], (int) subroot->depth) );
3344 }
3345 for( r = 0; r < nrows; ++r )
3346 {
3347 SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, rows[r], (int) subroot->depth) );
3348 }
3349
3350 return SCIP_OKAY;
3351}
3352
3353/** loads the fork's additional LP data */
3354static
3356 SCIP_NODE* fork, /**< fork node to construct additional LP for */
3357 BMS_BLKMEM* blkmem, /**< block memory buffers */
3358 SCIP_SET* set, /**< global SCIP settings */
3359 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3360 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3361 SCIP_LP* lp /**< current LP data */
3362 )
3363{
3364 SCIP_COL** cols;
3365 SCIP_ROW** rows;
3366 int ncols;
3367 int nrows;
3368 int c;
3369 int r;
3370
3371 assert(fork != NULL);
3372 assert(SCIPnodeGetType(fork) == SCIP_NODETYPE_FORK);
3373 assert(fork->data.fork != NULL);
3374 assert(blkmem != NULL);
3375 assert(set != NULL);
3376 assert(lp != NULL);
3377
3378 cols = fork->data.fork->addedcols;
3379 rows = fork->data.fork->addedrows;
3380 ncols = fork->data.fork->naddedcols;
3381 nrows = fork->data.fork->naddedrows;
3382
3383 assert(ncols == 0 || cols != NULL);
3384 assert(nrows == 0 || rows != NULL);
3385
3386 for( c = 0; c < ncols; ++c )
3387 {
3388 SCIP_CALL( SCIPlpAddCol(lp, set, cols[c], (int) fork->depth) );
3389 }
3390 for( r = 0; r < nrows; ++r )
3391 {
3392 SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, rows[r], (int) fork->depth) );
3393 }
3394
3395 return SCIP_OKAY;
3396}
3397
3398/** loads the pseudofork's additional LP data */
3399static
3401 SCIP_NODE* pseudofork, /**< pseudofork node to construct additional LP for */
3402 BMS_BLKMEM* blkmem, /**< block memory buffers */
3403 SCIP_SET* set, /**< global SCIP settings */
3404 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3405 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3406 SCIP_LP* lp /**< current LP data */
3407 )
3408{
3409 SCIP_COL** cols;
3410 SCIP_ROW** rows;
3411 int ncols;
3412 int nrows;
3413 int c;
3414 int r;
3415
3416 assert(pseudofork != NULL);
3417 assert(SCIPnodeGetType(pseudofork) == SCIP_NODETYPE_PSEUDOFORK);
3418 assert(pseudofork->data.pseudofork != NULL);
3419 assert(blkmem != NULL);
3420 assert(set != NULL);
3421 assert(lp != NULL);
3422
3423 cols = pseudofork->data.pseudofork->addedcols;
3424 rows = pseudofork->data.pseudofork->addedrows;
3425 ncols = pseudofork->data.pseudofork->naddedcols;
3426 nrows = pseudofork->data.pseudofork->naddedrows;
3427
3428 assert(ncols == 0 || cols != NULL);
3429 assert(nrows == 0 || rows != NULL);
3430
3431 for( c = 0; c < ncols; ++c )
3432 {
3433 SCIP_CALL( SCIPlpAddCol(lp, set, cols[c], (int) pseudofork->depth) );
3434 }
3435 for( r = 0; r < nrows; ++r )
3436 {
3437 SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, rows[r], (int) pseudofork->depth) );
3438 }
3439
3440 return SCIP_OKAY;
3441}
3442
3443#ifndef NDEBUG
3444/** checks validity of active path */
3445static
3447 SCIP_TREE* tree /**< branch and bound tree */
3448 )
3449{
3450 SCIP_NODE* node;
3451 int ncols;
3452 int nrows;
3453 int d;
3454
3455 assert(tree != NULL);
3456 assert(tree->path != NULL);
3457
3458 ncols = 0;
3459 nrows = 0;
3460 for( d = 0; d < tree->pathlen; ++d )
3461 {
3462 node = tree->path[d];
3463 assert(node != NULL);
3464 assert((int)(node->depth) == d);
3465 switch( SCIPnodeGetType(node) )
3466 {
3468 assert(SCIPtreeProbing(tree));
3469 assert(d >= 1);
3470 assert(SCIPnodeGetType(tree->path[d-1]) == SCIP_NODETYPE_FOCUSNODE
3471 || (ncols == node->data.probingnode->ninitialcols && nrows == node->data.probingnode->ninitialrows));
3472 assert(ncols <= node->data.probingnode->ncols || !tree->focuslpconstructed);
3473 assert(nrows <= node->data.probingnode->nrows || !tree->focuslpconstructed);
3474 if( d < tree->pathlen-1 )
3475 {
3476 ncols = node->data.probingnode->ncols;
3477 nrows = node->data.probingnode->nrows;
3478 }
3479 else
3480 {
3481 /* for the current probing node, the initial LP size is stored in the path */
3482 ncols = node->data.probingnode->ninitialcols;
3483 nrows = node->data.probingnode->ninitialrows;
3484 }
3485 break;
3487 break;
3489 ncols += node->data.pseudofork->naddedcols;
3490 nrows += node->data.pseudofork->naddedrows;
3491 break;
3492 case SCIP_NODETYPE_FORK:
3493 ncols += node->data.fork->naddedcols;
3494 nrows += node->data.fork->naddedrows;
3495 break;
3497 ncols = node->data.subroot->ncols;
3498 nrows = node->data.subroot->nrows;
3499 break;
3502 assert(d == tree->pathlen-1 || SCIPtreeProbing(tree));
3503 break;
3504 default:
3505 SCIPerrorMessage("node at depth %d on active path has to be of type JUNCTION, PSEUDOFORK, FORK, SUBROOT, FOCUSNODE, REFOCUSNODE, or PROBINGNODE, but is %d\n",
3506 d, SCIPnodeGetType(node));
3507 SCIPABORT();
3508 } /*lint !e788*/
3509 assert(tree->pathnlpcols[d] == ncols);
3510 assert(tree->pathnlprows[d] == nrows);
3511 }
3512}
3513#else
3514#define treeCheckPath(tree) /**/
3515#endif
3516
3517/** constructs the LP relaxation of the focus node */
3519 SCIP_TREE* tree, /**< branch and bound tree */
3520 BMS_BLKMEM* blkmem, /**< block memory buffers */
3521 SCIP_SET* set, /**< global SCIP settings */
3522 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3523 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3524 SCIP_LP* lp, /**< current LP data */
3525 SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */
3526 )
3527{
3528 SCIP_NODE* lpfork;
3529 int lpforkdepth;
3530 int d;
3531
3532 assert(tree != NULL);
3533 assert(!tree->focuslpconstructed);
3534 assert(tree->path != NULL);
3535 assert(tree->pathlen > 0);
3536 assert(tree->focusnode != NULL);
3538 assert(SCIPnodeGetDepth(tree->focusnode) == tree->pathlen-1);
3539 assert(!SCIPtreeProbing(tree));
3540 assert(tree->focusnode == tree->path[tree->pathlen-1]);
3541 assert(blkmem != NULL);
3542 assert(set != NULL);
3543 assert(lp != NULL);
3544 assert(initroot != NULL);
3545
3546 SCIPsetDebugMsg(set, "load LP for current fork node #%" SCIP_LONGINT_FORMAT " at depth %d\n",
3547 tree->focuslpfork == NULL ? -1 : SCIPnodeGetNumber(tree->focuslpfork),
3548 tree->focuslpfork == NULL ? -1 : SCIPnodeGetDepth(tree->focuslpfork));
3549 SCIPsetDebugMsg(set, "-> old LP has %d cols and %d rows\n", SCIPlpGetNCols(lp), SCIPlpGetNRows(lp));
3550 SCIPsetDebugMsg(set, "-> correct LP has %d cols and %d rows\n",
3551 tree->correctlpdepth >= 0 ? tree->pathnlpcols[tree->correctlpdepth] : 0,
3552 tree->correctlpdepth >= 0 ? tree->pathnlprows[tree->correctlpdepth] : 0);
3553 SCIPsetDebugMsg(set, "-> old correctlpdepth: %d\n", tree->correctlpdepth);
3554
3555 treeCheckPath(tree);
3556
3557 lpfork = tree->focuslpfork;
3558
3559 /* find out the lpfork's depth (or -1, if lpfork is NULL) */
3560 if( lpfork == NULL )
3561 {
3562 assert(tree->correctlpdepth == -1 || tree->pathnlpcols[tree->correctlpdepth] == 0);
3563 assert(tree->correctlpdepth == -1 || tree->pathnlprows[tree->correctlpdepth] == 0);
3564 assert(tree->focuslpstatefork == NULL);
3565 assert(tree->focussubroot == NULL);
3566 lpforkdepth = -1;
3567 }
3568 else
3569 {
3572 assert(lpfork->active);
3573 assert(tree->path[lpfork->depth] == lpfork);
3574 lpforkdepth = (int) lpfork->depth;
3575 }
3576 assert(lpforkdepth < tree->pathlen-1); /* lpfork must not be the last (the focus) node of the active path */
3577
3578 /* find out, if we are in the same subtree */
3579 if( tree->correctlpdepth >= 0 )
3580 {
3581 /* same subtree: shrink LP to the deepest node with correct LP */
3582 assert(lpforkdepth == -1 || tree->pathnlpcols[tree->correctlpdepth] <= tree->pathnlpcols[lpforkdepth]);
3583 assert(lpforkdepth == -1 || tree->pathnlprows[tree->correctlpdepth] <= tree->pathnlprows[lpforkdepth]);
3584 assert(lpforkdepth >= 0 || tree->pathnlpcols[tree->correctlpdepth] == 0);
3585 assert(lpforkdepth >= 0 || tree->pathnlprows[tree->correctlpdepth] == 0);
3587 SCIP_CALL( SCIPlpShrinkRows(lp, blkmem, set, eventqueue, eventfilter, tree->pathnlprows[tree->correctlpdepth]) );
3588 }
3589 else
3590 {
3591 /* other subtree: fill LP with the subroot LP data */
3592 SCIP_CALL( SCIPlpClear(lp, blkmem, set, eventqueue, eventfilter) );
3593 if( tree->focussubroot != NULL )
3594 {
3595 SCIP_CALL( subrootConstructLP(tree->focussubroot, blkmem, set, eventqueue, eventfilter, lp) );
3596 tree->correctlpdepth = (int) tree->focussubroot->depth;
3597 }
3598 }
3599
3600 assert(lpforkdepth < tree->pathlen);
3601
3602 /* add the missing columns and rows */
3603 for( d = tree->correctlpdepth+1; d <= lpforkdepth; ++d )
3604 {
3605 SCIP_NODE* pathnode;
3606
3607 pathnode = tree->path[d];
3608 assert(pathnode != NULL);
3609 assert((int)(pathnode->depth) == d);
3610 assert(SCIPnodeGetType(pathnode) == SCIP_NODETYPE_JUNCTION
3612 || SCIPnodeGetType(pathnode) == SCIP_NODETYPE_FORK);
3613 if( SCIPnodeGetType(pathnode) == SCIP_NODETYPE_FORK )
3614 {
3615 SCIP_CALL( forkAddLP(pathnode, blkmem, set, eventqueue, eventfilter, lp) );
3616 }
3617 else if( SCIPnodeGetType(pathnode) == SCIP_NODETYPE_PSEUDOFORK )
3618 {
3619 SCIP_CALL( pseudoforkAddLP(pathnode, blkmem, set, eventqueue, eventfilter, lp) );
3620 }
3621 }
3622 tree->correctlpdepth = MAX(tree->correctlpdepth, lpforkdepth);
3623 assert(lpforkdepth == -1 || tree->pathnlpcols[tree->correctlpdepth] == tree->pathnlpcols[lpforkdepth]);
3624 assert(lpforkdepth == -1 || tree->pathnlprows[tree->correctlpdepth] == tree->pathnlprows[lpforkdepth]);
3625 assert(lpforkdepth == -1 || SCIPlpGetNCols(lp) == tree->pathnlpcols[lpforkdepth]);
3626 assert(lpforkdepth == -1 || SCIPlpGetNRows(lp) == tree->pathnlprows[lpforkdepth]);
3627 assert(lpforkdepth >= 0 || SCIPlpGetNCols(lp) == 0);
3628 assert(lpforkdepth >= 0 || SCIPlpGetNRows(lp) == 0);
3629
3630 /* mark the LP's size, such that we know which rows and columns were added in the new node */
3631 SCIPlpMarkSize(lp);
3632
3633 SCIPsetDebugMsg(set, "-> new correctlpdepth: %d\n", tree->correctlpdepth);
3634 SCIPsetDebugMsg(set, "-> new LP has %d cols and %d rows\n", SCIPlpGetNCols(lp), SCIPlpGetNRows(lp));
3635
3636 /* if the correct LP depth is still -1, the root LP relaxation has to be initialized */
3637 *initroot = (tree->correctlpdepth == -1);
3638
3639 /* mark the LP of the focus node constructed */
3640 tree->focuslpconstructed = TRUE;
3641
3642 return SCIP_OKAY;
3643}
3644
3645/** loads LP state for fork/subroot of the focus node */
3647 SCIP_TREE* tree, /**< branch and bound tree */
3648 BMS_BLKMEM* blkmem, /**< block memory buffers */
3649 SCIP_SET* set, /**< global SCIP settings */
3650 SCIP_PROB* prob, /**< problem data */
3651 SCIP_STAT* stat, /**< dynamic problem statistics */
3652 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3653 SCIP_LP* lp /**< current LP data */
3654 )
3655{
3656 SCIP_NODE* lpstatefork;
3657 SCIP_Bool updatefeas;
3658 SCIP_Bool checkbdchgs;
3659 int lpstateforkdepth;
3660 int d;
3661
3662 assert(tree != NULL);
3663 assert(tree->focuslpconstructed);
3664 assert(tree->path != NULL);
3665 assert(tree->pathlen > 0);
3666 assert(tree->focusnode != NULL);
3667 assert(tree->correctlpdepth < tree->pathlen);
3669 assert(SCIPnodeGetDepth(tree->focusnode) == tree->pathlen-1);
3670 assert(!SCIPtreeProbing(tree));
3671 assert(tree->focusnode == tree->path[tree->pathlen-1]);
3672 assert(blkmem != NULL);
3673 assert(set != NULL);
3674 assert(lp != NULL);
3675
3676 SCIPsetDebugMsg(set, "load LP state for current fork node #%" SCIP_LONGINT_FORMAT " at depth %d\n",
3679
3680 lpstatefork = tree->focuslpstatefork;
3681
3682 /* if there is no LP state defining fork, nothing can be done */
3683 if( lpstatefork == NULL )
3684 return SCIP_OKAY;
3685
3686 /* get the lpstatefork's depth */
3687 assert(SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT);
3688 assert(lpstatefork->active);
3689 assert(tree->path[lpstatefork->depth] == lpstatefork);
3690 lpstateforkdepth = (int) lpstatefork->depth;
3691 assert(lpstateforkdepth < tree->pathlen-1); /* lpstatefork must not be the last (the focus) node of the active path */
3692 assert(lpstateforkdepth <= tree->correctlpdepth); /* LP must have been constructed at least up to the fork depth */
3693 assert(tree->pathnlpcols[tree->correctlpdepth] >= tree->pathnlpcols[lpstateforkdepth]); /* LP can only grow */
3694 assert(tree->pathnlprows[tree->correctlpdepth] >= tree->pathnlprows[lpstateforkdepth]); /* LP can only grow */
3695
3696 /* load LP state */
3697 if( tree->focuslpstateforklpcount != stat->lpcount )
3698 {
3699 if( SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK )
3700 {
3701 assert(lpstatefork->data.fork != NULL);
3702 SCIP_CALL( SCIPlpSetState(lp, blkmem, set, prob, eventqueue, lpstatefork->data.fork->lpistate,
3703 lpstatefork->data.fork->lpwasprimfeas, lpstatefork->data.fork->lpwasprimchecked,
3704 lpstatefork->data.fork->lpwasdualfeas, lpstatefork->data.fork->lpwasdualchecked) );
3705 }
3706 else
3707 {
3708 assert(SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT);
3709 assert(lpstatefork->data.subroot != NULL);
3710 SCIP_CALL( SCIPlpSetState(lp, blkmem, set, prob, eventqueue, lpstatefork->data.subroot->lpistate,
3711 lpstatefork->data.subroot->lpwasprimfeas, lpstatefork->data.subroot->lpwasprimchecked,
3712 lpstatefork->data.subroot->lpwasdualfeas, lpstatefork->data.subroot->lpwasdualchecked) );
3713 }
3714 updatefeas = !lp->solved || !lp->solisbasic;
3715 checkbdchgs = TRUE;
3716 }
3717 else
3718 {
3719 updatefeas = TRUE;
3720
3721 /* we do not need to check the bounds, since primalfeasible is updated anyway when flushing the LP */
3722 checkbdchgs = FALSE;
3723 }
3724
3725 if( updatefeas )
3726 {
3727 /* check whether the size of the LP increased (destroying primal/dual feasibility) */
3729 && (tree->pathnlprows[tree->correctlpdepth] == tree->pathnlprows[lpstateforkdepth]);
3731 && (tree->pathnlprows[tree->correctlpdepth] == tree->pathnlprows[lpstateforkdepth]);
3732 lp->dualfeasible = lp->dualfeasible
3733 && (tree->pathnlpcols[tree->correctlpdepth] == tree->pathnlpcols[lpstateforkdepth]);
3734 lp->dualchecked = lp->dualchecked
3735 && (tree->pathnlpcols[tree->correctlpdepth] == tree->pathnlpcols[lpstateforkdepth]);
3736
3737 /* check the path from LP fork to focus node for domain changes (destroying primal feasibility of LP basis) */
3738 if( checkbdchgs )
3739 {
3740 for( d = lpstateforkdepth; d < (int)(tree->focusnode->depth) && lp->primalfeasible; ++d )
3741 {
3742 assert(d < tree->pathlen);
3743 lp->primalfeasible = (tree->path[d]->domchg == NULL || tree->path[d]->domchg->domchgbound.nboundchgs == 0);
3744 lp->primalchecked = lp->primalfeasible;
3745 }
3746 }
3747 }
3748
3749 SCIPsetDebugMsg(set, "-> primalfeasible=%u, dualfeasible=%u\n", lp->primalfeasible, lp->dualfeasible);
3750
3751 return SCIP_OKAY;
3752}
3753
3754
3755
3756
3757/*
3758 * Node Conversion
3759 */
3760
3761/** converts node into LEAF and moves it into the array of the node queue
3762 * if node's lower bound is greater or equal than the given upper bound, the node is deleted;
3763 * otherwise, it is moved to the node queue; anyways, the given pointer is NULL after the call
3764 */
3765static
3767 SCIP_NODE** node, /**< pointer to child or sibling node to convert */
3768 BMS_BLKMEM* blkmem, /**< block memory buffers */
3769 SCIP_SET* set, /**< global SCIP settings */
3770 SCIP_STAT* stat, /**< dynamic problem statistics */
3771 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3772 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3773 SCIP_TREE* tree, /**< branch and bound tree */
3774 SCIP_REOPT* reopt, /**< reoptimization data structure */
3775 SCIP_LP* lp, /**< current LP data */
3776 SCIP_NODE* lpstatefork, /**< LP state defining fork of the node */
3777 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
3778 )
3779{
3782 assert(stat != NULL);
3783 assert(lpstatefork == NULL || lpstatefork->depth < (*node)->depth);
3784 assert(lpstatefork == NULL || lpstatefork->active || SCIPsetIsGE(set, (*node)->lowerbound, cutoffbound));
3785 assert(lpstatefork == NULL
3786 || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK
3787 || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT);
3788
3789#ifndef NDEBUG
3790 /* check, if the LP state fork is the first node with LP state information on the path back to the root */
3791 if( !SCIPsetIsInfinity(set, -cutoffbound) ) /* if the node was cut off in SCIPnodeFocus(), the lpstatefork is invalid */
3792 {
3793 SCIP_NODE* pathnode;
3794 pathnode = (*node)->parent;
3795 while( pathnode != NULL && pathnode != lpstatefork )
3796 {
3797 assert(SCIPnodeGetType(pathnode) == SCIP_NODETYPE_JUNCTION
3799 pathnode = pathnode->parent;
3800 }
3801 assert(pathnode == lpstatefork);
3802 }
3803#endif
3804
3805 /* if node is good enough to keep, put it on the node queue */
3806 if( !SCIPsetIsInfinity(set, (*node)->lowerbound) && SCIPsetIsLT(set, (*node)->lowerbound, cutoffbound) )
3807 {
3808 /* convert node into leaf */
3809 SCIPsetDebugMsg(set, "convert node #%" SCIP_LONGINT_FORMAT " at depth %d to leaf with lpstatefork #%" SCIP_LONGINT_FORMAT " at depth %d\n",
3810 SCIPnodeGetNumber(*node), SCIPnodeGetDepth(*node),
3811 lpstatefork == NULL ? -1 : SCIPnodeGetNumber(lpstatefork),
3812 lpstatefork == NULL ? -1 : SCIPnodeGetDepth(lpstatefork));
3813 (*node)->nodetype = SCIP_NODETYPE_LEAF; /*lint !e641*/
3814 (*node)->data.leaf.lpstatefork = lpstatefork;
3815
3816 /* insert leaf in node queue */
3817 SCIP_CALL( SCIPnodepqInsert(tree->leaves, set, *node) );
3818
3819 /* make the domain change data static to save memory */
3820 SCIP_CALL( SCIPdomchgMakeStatic(&(*node)->domchg, blkmem, set, eventqueue, lp) );
3821
3822 /* node is now member of the node queue: delete the pointer to forbid further access */
3823 *node = NULL;
3824 }
3825 else
3826 {
3827 /* delete node due to bound cut off */
3828 SCIP_CALL( SCIPnodeCutoff(*node, set, stat, tree, set->scip->transprob, set->scip->origprob, reopt, lp, blkmem) );
3829 if( SCIPnodeGetType(*node) == SCIP_NODETYPE_CHILD && lpstatefork != NULL )
3830 {
3831 SCIP_CALL( SCIPnodeReleaseLPIState(lpstatefork, blkmem, lp) );
3832 }
3833 SCIP_CALL( SCIPnodeFree(node, blkmem, set, stat, eventfilter, eventqueue, tree, lp) );
3834 }
3835 assert(*node == NULL);
3836
3837 return SCIP_OKAY;
3838}
3839
3840/** removes variables from the problem, that are marked to be deletable, and were created at the focusnode;
3841 * only removes variables that were created at the focusnode, unless inlp is TRUE (e.g., when the node is cut off, anyway)
3842 */
3843static
3845 BMS_BLKMEM* blkmem, /**< block memory buffers */
3846 SCIP_SET* set, /**< global SCIP settings */
3847 SCIP_STAT* stat, /**< dynamic problem statistics */
3848 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3849 SCIP_PROB* transprob, /**< transformed problem after presolve */
3850 SCIP_PROB* origprob, /**< original problem */
3851 SCIP_TREE* tree, /**< branch and bound tree */
3852 SCIP_REOPT* reopt, /**< reoptimization data structure */
3853 SCIP_LP* lp, /**< current LP data */
3854 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3855 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3856 SCIP_Bool inlp /**< should variables in the LP be deleted, too?*/
3857 )
3858{
3859 SCIP_VAR* var;
3860 int i;
3861 int ndelvars;
3862 SCIP_Bool needdel;
3863 SCIP_Bool deleted;
3864
3865 assert(blkmem != NULL);
3866 assert(set != NULL);
3867 assert(stat != NULL);
3868 assert(tree != NULL);
3869 assert(!SCIPtreeProbing(tree));
3870 assert(tree->focusnode != NULL);
3872 assert(lp != NULL);
3873
3874 /* check the settings, whether variables should be deleted */
3875 needdel = (tree->focusnode == tree->root ? set->price_delvarsroot : set->price_delvars);
3876
3877 if( !needdel )
3878 return SCIP_OKAY;
3879
3880 ndelvars = 0;
3881
3882 /* also delete variables currently in the LP, thus remove all new variables from the LP, first */
3883 if( inlp )
3884 {
3885 /* remove all additions to the LP at this node */
3887
3888 SCIP_CALL( SCIPlpFlush(lp, blkmem, set, transprob, eventqueue) );
3889 }
3890
3891 /* mark variables as deleted */
3892 for( i = 0; i < transprob->nvars; i++ )
3893 {
3894 var = transprob->vars[i];
3895 assert(var != NULL);
3896
3897 /* check whether variable is deletable */
3898 if( SCIPvarIsDeletable(var) )
3899 {
3900 if( !SCIPvarIsInLP(var) )
3901 {
3902 /* fix the variable to 0, first */
3905
3907 {
3908 SCIP_CALL( SCIPnodeAddBoundchg(tree->root, blkmem, set, stat, transprob, origprob,
3909 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, 0.0, SCIP_BOUNDTYPE_LOWER, FALSE) );
3910 }
3912 {
3913 SCIP_CALL( SCIPnodeAddBoundchg(tree->root, blkmem, set, stat, transprob, origprob,
3914 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, 0.0, SCIP_BOUNDTYPE_UPPER, FALSE) );
3915 }
3916
3917 SCIP_CALL( SCIPprobDelVar(transprob, blkmem, set, eventqueue, var, &deleted) );
3918
3919 if( deleted )
3920 ndelvars++;
3921 }
3922 else
3923 {
3924 /* mark variable to be non-deletable, because it will be contained in the basis information
3925 * at this node and must not be deleted from now on
3926 */
3928 }
3929 }
3930 }
3931
3932 SCIPsetDebugMsg(set, "delvars at node %" SCIP_LONGINT_FORMAT ", deleted %d vars\n", stat->nnodes, ndelvars);
3933
3934 if( ndelvars > 0 )
3935 {
3936 /* perform the variable deletions from the problem */
3937 SCIP_CALL( SCIPprobPerformVarDeletions(transprob, blkmem, set, stat, eventqueue, cliquetable, lp, branchcand) );
3938 }
3939
3940 return SCIP_OKAY;
3941}
3942
3943/** converts the focus node into a dead-end node */
3944static
3946 BMS_BLKMEM* blkmem, /**< block memory buffers */
3947 SCIP_SET* set, /**< global SCIP settings */
3948 SCIP_STAT* stat, /**< dynamic problem statistics */
3949 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3950 SCIP_PROB* transprob, /**< transformed problem after presolve */
3951 SCIP_PROB* origprob, /**< original problem */
3952 SCIP_TREE* tree, /**< branch and bound tree */
3953 SCIP_REOPT* reopt, /**< reoptimization data structure */
3954 SCIP_LP* lp, /**< current LP data */
3955 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3956 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3957 )
3958{
3959 assert(blkmem != NULL);
3960 assert(tree != NULL);
3961 assert(!SCIPtreeProbing(tree));
3962 assert(tree->focusnode != NULL);
3964 assert(tree->nchildren == 0);
3965
3966 SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to dead-end at depth %d\n",
3968
3969 /* remove variables from the problem that are marked as deletable and were created at this node */
3970 SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable, TRUE) );
3971
3972 tree->focusnode->nodetype = SCIP_NODETYPE_DEADEND; /*lint !e641*/
3973
3974 /* release LPI state */
3975 if( tree->focuslpstatefork != NULL )
3976 {
3978 }
3979
3980 return SCIP_OKAY;
3981}
3982
3983/** converts the focus node into a leaf node (if it was postponed) */
3984static
3986 BMS_BLKMEM* blkmem, /**< block memory buffers */
3987 SCIP_SET* set, /**< global SCIP settings */
3988 SCIP_STAT* stat, /**< dynamic problem statistics */
3989 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3990 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3991 SCIP_TREE* tree, /**< branch and bound tree */
3992 SCIP_REOPT* reopt, /**< reoptimization data structure */
3993 SCIP_LP* lp, /**< current LP data */
3994 SCIP_NODE* lpstatefork, /**< LP state defining fork of the node */
3995 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
3996
3997 )
3998{
3999 assert(tree != NULL);
4000 assert(!SCIPtreeProbing(tree));
4001 assert(tree->focusnode != NULL);
4002 assert(tree->focusnode->active);
4004
4005 SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to leaf at depth %d\n",
4007
4008 SCIP_CALL( nodeToLeaf(&tree->focusnode, blkmem, set, stat, eventfilter, eventqueue, tree, reopt, lp, lpstatefork, cutoffbound));
4009
4010 return SCIP_OKAY;
4011}
4012
4013/** converts the focus node into a junction node */
4014static
4016 BMS_BLKMEM* blkmem, /**< block memory buffers */
4017 SCIP_SET* set, /**< global SCIP settings */
4018 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4019 SCIP_TREE* tree, /**< branch and bound tree */
4020 SCIP_LP* lp /**< current LP data */
4021 )
4022{
4023 assert(tree != NULL);
4024 assert(!SCIPtreeProbing(tree));
4025 assert(tree->focusnode != NULL);
4026 assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
4028 assert(SCIPlpGetNNewcols(lp) == 0);
4029
4030 SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to junction at depth %d\n",
4032
4033 /* convert node into junction */
4034 tree->focusnode->nodetype = SCIP_NODETYPE_JUNCTION; /*lint !e641*/
4035
4036 SCIP_CALL( junctionInit(&tree->focusnode->data.junction, tree) );
4037
4038 /* release LPI state */
4039 if( tree->focuslpstatefork != NULL )
4040 {
4042 }
4043
4044 /* make the domain change data static to save memory */
4045 SCIP_CALL( SCIPdomchgMakeStatic(&tree->focusnode->domchg, blkmem, set, eventqueue, lp) );
4046
4047 return SCIP_OKAY;
4048}
4049
4050/** converts the focus node into a pseudofork node */
4051static
4053 BMS_BLKMEM* blkmem, /**< block memory buffers */
4054 SCIP_SET* set, /**< global SCIP settings */
4055 SCIP_STAT* stat, /**< dynamic problem statistics */
4056 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4057 SCIP_PROB* transprob, /**< transformed problem after presolve */
4058 SCIP_PROB* origprob, /**< original problem */
4059 SCIP_TREE* tree, /**< branch and bound tree */
4060 SCIP_REOPT* reopt, /**< reoptimization data structure */
4061 SCIP_LP* lp, /**< current LP data */
4062 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4063 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
4064 )
4065{
4066 SCIP_PSEUDOFORK* pseudofork;
4067
4068 assert(blkmem != NULL);
4069 assert(tree != NULL);
4070 assert(!SCIPtreeProbing(tree));
4071 assert(tree->focusnode != NULL);
4072 assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
4074 assert(tree->nchildren > 0);
4075 assert(lp != NULL);
4076
4077 SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to pseudofork at depth %d\n",
4079
4080 /* remove variables from the problem that are marked as deletable and were created at this node */
4081 SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable, FALSE) );
4082
4083 /* create pseudofork data */
4084 SCIP_CALL( pseudoforkCreate(&pseudofork, blkmem, tree, lp) );
4085
4086 tree->focusnode->nodetype = SCIP_NODETYPE_PSEUDOFORK; /*lint !e641*/
4087 tree->focusnode->data.pseudofork = pseudofork;
4088
4089 /* release LPI state */
4090 if( tree->focuslpstatefork != NULL )
4091 {
4093 }
4094
4095 /* make the domain change data static to save memory */
4096 SCIP_CALL( SCIPdomchgMakeStatic(&tree->focusnode->domchg, blkmem, set, eventqueue, lp) );
4097
4098 return SCIP_OKAY;
4099}
4100
4101/** converts the focus node into a fork node */
4102static
4104 BMS_BLKMEM* blkmem, /**< block memory buffers */
4105 SCIP_SET* set, /**< global SCIP settings */
4106 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4107 SCIP_STAT* stat, /**< dynamic problem statistics */
4108 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4109 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
4110 SCIP_PROB* transprob, /**< transformed problem after presolve */
4111 SCIP_PROB* origprob, /**< original problem */
4112 SCIP_TREE* tree, /**< branch and bound tree */
4113 SCIP_REOPT* reopt, /**< reoptimization data structure */
4114 SCIP_LP* lp, /**< current LP data */
4115 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4116 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
4117 )
4118{
4119 SCIP_FORK* fork;
4120 SCIP_Bool lperror;
4121
4122 assert(blkmem != NULL);
4123 assert(tree != NULL);
4124 assert(!SCIPtreeProbing(tree));
4125 assert(tree->focusnode != NULL);
4126 assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
4128 assert(tree->nchildren > 0);
4129 assert(lp != NULL);
4130 assert(lp->flushed);
4131 assert(lp->solved || lp->resolvelperror);
4132
4133 SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to fork at depth %d\n",
4135
4136 /* usually, the LP should be solved to optimality; otherwise, numerical troubles occured,
4137 * and we have to forget about the LP and transform the node into a junction (see below)
4138 */
4139 lperror = FALSE;
4141 {
4142 /* clean up newly created part of LP to keep only necessary columns and rows */
4143 SCIP_CALL( SCIPlpCleanupNew(lp, blkmem, set, stat, eventqueue, eventfilter, (tree->focusnode->depth == 0)) );
4144
4145 /* resolve LP after cleaning up */
4146 SCIPsetDebugMsg(set, "resolving LP after cleanup\n");
4147 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, TRUE, &lperror) );
4148 }
4149 assert(lp->flushed);
4150 assert(lp->solved || lperror || lp->resolvelperror);
4151
4152 /* There are two reasons, that the (reduced) LP is not solved to optimality:
4153 * - The primal heuristics (called after the current node's LP was solved) found a new
4154 * solution, that is better than the current node's lower bound.
4155 * (But in this case, all children should be cut off and the node should be converted
4156 * into a dead-end instead of a fork.)
4157 * - Something numerically weird happened after cleaning up or after resolving a diving or probing LP.
4158 * The only thing we can do, is to completely forget about the LP and treat the node as
4159 * if it was only a pseudo-solution node. Therefore we have to remove all additional
4160 * columns and rows from the LP and convert the node into a junction.
4161 * However, the node's lower bound is kept, thus automatically throwing away nodes that
4162 * were cut off due to a primal solution.
4163 */
4164 if( lperror || lp->resolvelperror || SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL )
4165 {
4166 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4167 "(node %" SCIP_LONGINT_FORMAT ") numerical troubles: LP %" SCIP_LONGINT_FORMAT " not optimal -- convert node into junction instead of fork\n",
4168 stat->nnodes, stat->nlps);
4169
4170 /* remove all additions to the LP at this node */
4172 SCIP_CALL( SCIPlpShrinkRows(lp, blkmem, set, eventqueue, eventfilter, SCIPlpGetNRows(lp) - SCIPlpGetNNewrows(lp)) );
4173
4174 /* convert node into a junction */
4175 SCIP_CALL( focusnodeToJunction(blkmem, set, eventqueue, tree, lp) );
4176
4177 return SCIP_OKAY;
4178 }
4179 assert(lp->flushed);
4180 assert(lp->solved);
4182
4183 /* remove variables from the problem that are marked as deletable, were created at this node and are not contained in the LP */
4184 SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable, FALSE) );
4185
4186 assert(lp->flushed);
4187 assert(lp->solved);
4188
4189 /* create fork data */
4190 SCIP_CALL( forkCreate(&fork, blkmem, set, transprob, tree, lp) );
4191
4192 tree->focusnode->nodetype = SCIP_NODETYPE_FORK; /*lint !e641*/
4193 tree->focusnode->data.fork = fork;
4194
4195 /* capture the LPI state of the root node to ensure that the LPI state of the root stays for the whole solving
4196 * process
4197 */
4198 if( tree->focusnode == tree->root )
4199 forkCaptureLPIState(fork, 1);
4200
4201 /* release LPI state */
4202 if( tree->focuslpstatefork != NULL )
4203 {
4205 }
4206
4207 /* make the domain change data static to save memory */
4208 SCIP_CALL( SCIPdomchgMakeStatic(&tree->focusnode->domchg, blkmem, set, eventqueue, lp) );
4209
4210 return SCIP_OKAY;
4211}
4212
4213#ifdef WITHSUBROOTS /** @todo test whether subroots should be created */
4214/** converts the focus node into a subroot node */
4215static
4216SCIP_RETCODE focusnodeToSubroot(
4217 BMS_BLKMEM* blkmem, /**< block memory buffers */
4218 SCIP_SET* set, /**< global SCIP settings */
4219 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4220 SCIP_STAT* stat, /**< dynamic problem statistics */
4221 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4222 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
4223 SCIP_PROB* transprob, /**< transformed problem after presolve */
4224 SCIP_PROB* origprob, /**< original problem */
4225 SCIP_TREE* tree, /**< branch and bound tree */
4226 SCIP_LP* lp, /**< current LP data */
4227 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4228 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
4229 )
4230{
4231 SCIP_SUBROOT* subroot;
4232 SCIP_Bool lperror;
4233
4234 assert(blkmem != NULL);
4235 assert(tree != NULL);
4236 assert(!SCIPtreeProbing(tree));
4237 assert(tree->focusnode != NULL);
4239 assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
4240 assert(tree->nchildren > 0);
4241 assert(lp != NULL);
4242 assert(lp->flushed);
4243 assert(lp->solved);
4244
4245 SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to subroot at depth %d\n",
4247
4248 /* usually, the LP should be solved to optimality; otherwise, numerical troubles occured,
4249 * and we have to forget about the LP and transform the node into a junction (see below)
4250 */
4251 lperror = FALSE;
4253 {
4254 /* clean up whole LP to keep only necessary columns and rows */
4255#ifdef SCIP_DISABLED_CODE
4256 if( tree->focusnode->depth == 0 )
4257 {
4258 SCIP_CALL( SCIPlpCleanupAll(lp, blkmem, set, stat, eventqueue, eventfilter, (tree->focusnode->depth == 0)) );
4259 }
4260 else
4261#endif
4262 {
4263 SCIP_CALL( SCIPlpRemoveAllObsoletes(lp, blkmem, set, stat, eventqueue, eventfilter) );
4264 }
4265
4266 /* resolve LP after cleaning up */
4267 SCIPsetDebugMsg(set, "resolving LP after cleanup\n");
4268 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, TRUE, &lperror) );
4269 }
4270 assert(lp->flushed);
4271 assert(lp->solved || lperror);
4272
4273 /* There are two reasons, that the (reduced) LP is not solved to optimality:
4274 * - The primal heuristics (called after the current node's LP was solved) found a new
4275 * solution, that is better than the current node's lower bound.
4276 * (But in this case, all children should be cut off and the node should be converted
4277 * into a dead-end instead of a subroot.)
4278 * - Something numerically weird happened after cleaning up.
4279 * The only thing we can do, is to completely forget about the LP and treat the node as
4280 * if it was only a pseudo-solution node. Therefore we have to remove all additional
4281 * columns and rows from the LP and convert the node into a junction.
4282 * However, the node's lower bound is kept, thus automatically throwing away nodes that
4283 * were cut off due to a primal solution.
4284 */
4285 if( lperror || SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL )
4286 {
4287 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4288 "(node %" SCIP_LONGINT_FORMAT ") numerical troubles: LP %" SCIP_LONGINT_FORMAT " not optimal -- convert node into junction instead of subroot\n",
4289 stat->nnodes, stat->nlps);
4290
4291 /* remove all additions to the LP at this node */
4293 SCIP_CALL( SCIPlpShrinkRows(lp, blkmem, set, eventqueue, eventfilter, SCIPlpGetNRows(lp) - SCIPlpGetNNewrows(lp)) );
4294
4295 /* convert node into a junction */
4296 SCIP_CALL( focusnodeToJunction(blkmem, set, eventqueue, tree, lp) );
4297
4298 return SCIP_OKAY;
4299 }
4300 assert(lp->flushed);
4301 assert(lp->solved);
4303
4304 /* remove variables from the problem that are marked as deletable, were created at this node and are not contained in the LP */
4305 SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, lp, branchcand, cliquetable, FALSE) );
4306
4307 assert(lp->flushed);
4308 assert(lp->solved);
4309
4310 /* create subroot data */
4311 SCIP_CALL( subrootCreate(&subroot, blkmem, set, transprob, tree, lp) );
4312
4313 tree->focusnode->nodetype = SCIP_NODETYPE_SUBROOT; /*lint !e641*/
4314 tree->focusnode->data.subroot = subroot;
4315
4316 /* update the LP column and row counter for the converted node */
4318
4319 /* release LPI state */
4320 if( tree->focuslpstatefork != NULL )
4321 {
4323 }
4324
4325 /* make the domain change data static to save memory */
4326 SCIP_CALL( SCIPdomchgMakeStatic(&tree->focusnode->domchg, blkmem, set, eventqueue, lp) );
4327
4328 return SCIP_OKAY;
4329}
4330#endif
4331
4332/** puts all nodes in the array on the node queue and makes them LEAFs */
4333static
4335 SCIP_TREE* tree, /**< branch and bound tree */
4336 SCIP_REOPT* reopt, /**< reoptimization data structure */
4337 BMS_BLKMEM* blkmem, /**< block memory buffers */
4338 SCIP_SET* set, /**< global SCIP settings */
4339 SCIP_STAT* stat, /**< dynamic problem statistics */
4340 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4341 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4342 SCIP_LP* lp, /**< current LP data */
4343 SCIP_NODE** nodes, /**< array of nodes to put on the queue */
4344 int* nnodes, /**< pointer to number of nodes in the array */
4345 SCIP_NODE* lpstatefork, /**< LP state defining fork of the nodes */
4346 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
4347 )
4348{
4349 assert(tree != NULL);
4350 assert(set != NULL);
4351 assert(nnodes != NULL);
4352 assert(*nnodes == 0 || nodes != NULL);
4353
4354 /* as long as the node array has slots */
4355 while( *nnodes >= 1 )
4356 {
4357 /* convert last node to LEAF and put it into leaves queue, or delete it if its lower bound exceeds the cutoff bound */
4358 if( nodes[*nnodes-1] != NULL )
4359 {
4360 SCIP_CALL( nodeToLeaf(&nodes[*nnodes-1], blkmem, set, stat, eventfilter, eventqueue, tree, reopt, lp, lpstatefork, cutoffbound) );
4361 }
4362 else
4363 --(*nnodes);
4364 }
4365
4366 return SCIP_OKAY;
4367}
4368
4369/** converts children into siblings, clears children array */
4370static
4372 SCIP_TREE* tree /**< branch and bound tree */
4373 )
4374{
4375 SCIP_NODE** tmpnodes;
4376 SCIP_Real* tmpprios;
4377 int tmpnodessize;
4378 int i;
4379
4380 assert(tree != NULL);
4381 assert(tree->nsiblings == 0);
4382
4383 tmpnodes = tree->siblings;
4384 tmpprios = tree->siblingsprio;
4385 tmpnodessize = tree->siblingssize;
4386
4387 tree->siblings = tree->children;
4388 tree->siblingsprio = tree->childrenprio;
4389 tree->nsiblings = tree->nchildren;
4390 tree->siblingssize = tree->childrensize;
4391
4392 tree->children = tmpnodes;
4393 tree->childrenprio = tmpprios;
4394 tree->nchildren = 0;
4395 tree->childrensize = tmpnodessize;
4396
4397 for( i = 0; i < tree->nsiblings; ++i )
4398 {
4399 assert(SCIPnodeGetType(tree->siblings[i]) == SCIP_NODETYPE_CHILD);
4400 tree->siblings[i]->nodetype = SCIP_NODETYPE_SIBLING; /*lint !e641*/
4401
4402 /* because CHILD and SIBLING structs contain the same data in the same order, we do not have to copy it */
4403 assert(&(tree->siblings[i]->data.sibling.arraypos) == &(tree->siblings[i]->data.child.arraypos));
4404 }
4405}
4406
4407/** installs a child, a sibling, or a leaf node as the new focus node */
4409 SCIP_NODE** node, /**< pointer to node to focus (or NULL to remove focus); the node
4410 * is freed, if it was cut off due to a cut off subtree */
4411 BMS_BLKMEM* blkmem, /**< block memory buffers */
4412 SCIP_SET* set, /**< global SCIP settings */
4413 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4414 SCIP_STAT* stat, /**< problem statistics */
4415 SCIP_PROB* transprob, /**< transformed problem */
4416 SCIP_PROB* origprob, /**< original problem */
4417 SCIP_PRIMAL* primal, /**< primal data */
4418 SCIP_TREE* tree, /**< branch and bound tree */
4419 SCIP_REOPT* reopt, /**< reoptimization data structure */
4420 SCIP_LP* lp, /**< current LP data */
4421 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4422 SCIP_CONFLICT* conflict, /**< conflict analysis data */
4423 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4424 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4425 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4426 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4427 SCIP_Bool* cutoff, /**< pointer to store whether the given node can be cut off */
4428 SCIP_Bool postponed, /**< was the current focus node postponed? */
4429 SCIP_Bool exitsolve /**< are we in exitsolve stage, so we only need to loose the children */
4430 )
4431{ /*lint --e{715}*/
4432 SCIP_NODE* fork;
4433 SCIP_NODE* lpfork;
4434 SCIP_NODE* lpstatefork;
4435 SCIP_NODE* subroot;
4436 SCIP_NODE* childrenlpstatefork;
4437 int oldcutoffdepth;
4438
4439 assert(node != NULL);
4440 assert(*node == NULL
4443 || SCIPnodeGetType(*node) == SCIP_NODETYPE_LEAF);
4444 assert(*node == NULL || !(*node)->active);
4445 assert(stat != NULL);
4446 assert(tree != NULL);
4447 assert(!SCIPtreeProbing(tree));
4448 assert(lp != NULL);
4449 assert(conflictstore != NULL);
4450 assert(cutoff != NULL);
4451
4452 /* check global lower bound w.r.t. debugging solution */
4454
4455 /* check local lower bound w.r.t. debugging solution */
4456 SCIP_CALL( SCIPdebugCheckLocalLowerbound(blkmem, set, *node) );
4457
4458 SCIPsetDebugMsg(set, "focusing node #%" SCIP_LONGINT_FORMAT " of type %d in depth %d\n",
4459 *node != NULL ? SCIPnodeGetNumber(*node) : -1, *node != NULL ? (int)SCIPnodeGetType(*node) : 0,
4460 *node != NULL ? SCIPnodeGetDepth(*node) : -1);
4461
4462 /* remember old cutoff depth in order to know, whether the children and siblings can be deleted */
4463 oldcutoffdepth = tree->cutoffdepth;
4464
4465 /* find the common fork node, the new LP defining fork, and the new focus subroot,
4466 * thereby checking, if the new node can be cut off
4467 */
4468 treeFindSwitchForks(tree, *node, &fork, &lpfork, &lpstatefork, &subroot, cutoff);
4469 SCIPsetDebugMsg(set, "focus node: focusnodedepth=%ld, forkdepth=%ld, lpforkdepth=%ld, lpstateforkdepth=%ld, subrootdepth=%ld, cutoff=%u\n",
4470 *node != NULL ? (long)((*node)->depth) : -1, fork != NULL ? (long)(fork->depth) : -1, /*lint !e705 */
4471 lpfork != NULL ? (long)(lpfork->depth) : -1, lpstatefork != NULL ? (long)(lpstatefork->depth) : -1, /*lint !e705 */
4472 subroot != NULL ? (long)(subroot->depth) : -1, *cutoff); /*lint !e705 */
4473
4474 /* free the new node, if it is located in a cut off subtree */
4475 if( *cutoff )
4476 {
4477 assert(*node != NULL);
4478 assert(tree->cutoffdepth == oldcutoffdepth);
4479
4480 /* cut off node */
4481 if( SCIPnodeGetType(*node) == SCIP_NODETYPE_LEAF )
4482 {
4483 assert(!(*node)->active);
4484 assert((*node)->depth != 0 || tree->focusnode == NULL);
4485
4486 SCIPsetDebugMsg(set, "cutting off leaf node #%lld (queuelen=%d) at depth %d with lowerbound=%g\n",
4488
4489 /* check if the node should be stored for reoptimization */
4490 if( set->reopt_enable )
4491 {
4493 SCIPlpGetSolstat(lp), tree->root == *node, FALSE, (*node)->lowerbound, tree->effectiverootdepth) );
4494 }
4495
4496 /* remove node from the queue */
4497 SCIP_CALL( SCIPnodepqRemove(tree->leaves, set, *node) );
4498 (*node)->cutoff = TRUE;
4499
4500 if( (*node)->depth == 0 )
4502
4503 /* update primal-dual integrals */
4504 if( set->misc_calcintegral )
4505 {
4506 SCIP_Real lowerbound = SCIPtreeGetLowerbound(tree, set);
4507
4508 assert(lowerbound <= SCIPsetInfinity(set));
4509
4510 /* updating the primal integral is only necessary if lower bound has increased since last evaluation */
4511 if( lowerbound > stat->lastlowerbound )
4512 SCIPstatUpdatePrimalDualIntegrals(stat, set, transprob, origprob, SCIPsetInfinity(set), lowerbound);
4513 }
4514
4515 SCIPvisualCutoffNode(stat->visual, set, stat, *node, TRUE);
4516 }
4517 else
4518 {
4519 SCIP_CALL( SCIPnodeCutoff(*node, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
4520 }
4521
4522 /* free node memory */
4523 SCIP_CALL( SCIPnodeFree(node, blkmem, set, stat, eventfilter, eventqueue, tree,