SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
solve.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 solve.c
26 * @ingroup OTHER_CFILES
27 * @brief main solving loop and node processing
28 * @author Tobias Achterberg
29 * @author Timo Berthold
30 * @author Marc Pfetsch
31 * @author Gerald Gamrath
32 */
33
34/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35#include <assert.h>
36
37#include "lpi/lpi.h"
38#include "scip/branch.h"
39#include "scip/clock.h"
40#include "scip/concurrent.h"
41#include "scip/conflict.h"
42#include "scip/cons.h"
43#include "scip/cutpool.h"
44#include "scip/disp.h"
45#include "scip/event.h"
46#include "scip/heur.h"
47#include "scip/interrupt.h"
48#include "scip/lp.h"
49#include "scip/nodesel.h"
50#include "scip/pricer.h"
51#include "scip/pricestore.h"
52#include "scip/primal.h"
53#include "scip/prob.h"
54#include "scip/prop.h"
55#include "scip/pub_cons.h"
56#include "scip/pub_heur.h"
57#include "scip/pub_message.h"
58#include "scip/pub_misc.h"
59#include "scip/pub_pricer.h"
60#include "scip/pub_prop.h"
61#include "scip/pub_relax.h"
62#include "scip/pub_sepa.h"
63#include "scip/pub_tree.h"
64#include "scip/pub_var.h"
65#include "scip/relax.h"
66#include "scip/reopt.h"
68#include "scip/scip_mem.h"
69#include "scip/scip_prob.h"
70#include "scip/scip_sol.h"
72#include "scip/sepa.h"
73#include "scip/sepastore.h"
74#include "scip/set.h"
75#include "scip/sol.h"
76#include "scip/solve.h"
77#include "scip/stat.h"
78#include "scip/struct_cons.h"
79#include "scip/struct_event.h"
80#include "scip/struct_lp.h"
81#include "scip/struct_mem.h"
82#include "scip/struct_primal.h"
83#include "scip/struct_prob.h"
84#include "scip/struct_set.h"
85#include "scip/struct_stat.h"
86#include "scip/struct_tree.h"
87#include "scip/struct_var.h"
88#include "scip/syncstore.h"
89#include "scip/tree.h"
90#include "scip/var.h"
91#include "scip/visual.h"
92
93
94#define MAXNLPERRORS 10 /**< maximal number of LP error loops in a single node */
95#define MAXNCLOCKSKIPS 64 /**< maximum number of SCIPsolveIsStopped() calls without checking the clock */
96#define NINITCALLS 1000L /**< minimum number of calls to SCIPsolveIsStopped() prior to dynamic clock skips */
97#define SAFETYFACTOR 1e-2 /**< the probability that SCIP skips the clock call after the time limit has already been reached */
98
99/** returns whether the solving process will be / was stopped before proving optimality;
100 * if the solving process was stopped, stores the reason as status in stat
101 */
103 SCIP_SET* set, /**< global SCIP settings */
104 SCIP_STAT* stat, /**< dynamic problem statistics */
105 SCIP_Bool checknodelimits /**< should the node limits be involved in the check? */
106 )
107{
108 assert(set != NULL);
109 assert(stat != NULL);
110
111 /* increase the number of calls to this method */
112 SCIPstatIncrement(stat, set, nisstoppedcalls);
113
114 /* in case lowerbound >= upperbound, we do not want to terminate with SCIP_STATUS_GAPLIMIT but with the ordinary
115 * SCIP_STATUS_OPTIMAL/INFEASIBLE/...
116 */
118 return TRUE;
119
120 /* if some limit has been changed since the last call, we reset the status */
121 if( set->limitchanged )
122 {
124 set->limitchanged = FALSE;
125 }
126
127 if( SCIPinterrupted() || stat->userinterrupt )
128 {
130 stat->userinterrupt = FALSE;
131
132 /* only reset the interrupted counter if this is the main SCIP catching CTRL-C */
133 if( set->misc_catchctrlc )
134 {
136 }
137 }
138 else if( SCIPterminated() )
139 {
141
142 return TRUE;
143 }
144 /* only measure the clock if a time limit is set */
145 else if( set->istimelimitfinite )
146 {
147 /* check if we have already called this function sufficiently often for a valid estimation of its average call interval */
148 if( stat->nclockskipsleft <= 0 || stat->nisstoppedcalls < NINITCALLS )
149 {
150 SCIP_Real currtime = SCIPclockGetTime(stat->solvingtime);
151
152 /* use the measured time to update the average time interval between two calls to this method */
153 if( set->time_rareclockcheck && stat->nisstoppedcalls >= NINITCALLS )
154 {
155 SCIP_Real avgisstoppedfreq;
157
159
160 /* if we are approaching the time limit, reset the number of clock skips to 0 */
161 if( (SAFETYFACTOR * (set->limit_time - currtime) / (avgisstoppedfreq + 1e-6)) < nclockskips )
162 nclockskips = 0;
163
165 }
166 else
167 stat->nclockskipsleft = 0;
168
169 /* set the status if the time limit was hit */
170 if( currtime >= set->limit_time )
171 {
173 return TRUE;
174 }
175 }
176 else if( SCIPclockGetLastTime(stat->solvingtime) >= set->limit_time )
177 {
178 /* use information if clock has been updated more recently */
180 return TRUE;
181 }
182 else
183 --stat->nclockskipsleft;
184 }
185 if( SCIPgetConcurrentMemTotal(set->scip) >= set->limit_memory*1048576.0 - stat->externmemestim * (1.0 + SCIPgetNConcurrentSolvers(set->scip)) )
187 else if( SCIPgetNLimSolsFound(set->scip) > 0
188 && (SCIPsetIsLT(set, SCIPgetGap(set->scip), set->limit_gap)
189 || SCIPsetIsLT(set, (SCIPgetUpperbound(set->scip) - SCIPgetLowerbound(set->scip)) * SCIPgetTransObjscale(set->scip), set->limit_absgap )) )
191 else if( set->limit_solutions >= 0 && set->stage >= SCIP_STAGE_PRESOLVING
192 && SCIPgetNLimSolsFound(set->scip) >= set->limit_solutions )
194 else if( set->limit_bestsol >= 0 && set->stage >= SCIP_STAGE_PRESOLVING
195 && SCIPgetNBestSolsFound(set->scip) >= set->limit_bestsol )
197 else if( checknodelimits && set->limit_nodes >= 0 && stat->nnodes >= set->limit_nodes )
199 else if( checknodelimits && set->limit_totalnodes >= 0 && stat->ntotalnodes >= set->limit_totalnodes )
201 else if( checknodelimits && set->limit_stallnodes >= 0 && stat->nnodes >= stat->bestsolnode + set->limit_stallnodes )
203
204 /* If stat->status was initialized to SCIP_STATUS_NODELIMIT or SCIP_STATUS_STALLNODELIMIT due to a previous call to SCIPsolveIsStopped(,,TRUE),
205 * in the case of checknodelimits == FALSE, we do not want to report here that the solve will be stopped due to a nodelimit.
206 */
207 if( !checknodelimits )
209 else
211}
212
213/** calls primal heuristics */
215 SCIP_SET* set, /**< global SCIP settings */
216 SCIP_STAT* stat, /**< dynamic problem statistics */
217 SCIP_PROB* prob, /**< transformed problem after presolve */
218 SCIP_PRIMAL* primal, /**< primal data */
219 SCIP_TREE* tree, /**< branch and bound tree, or NULL if called during presolving */
220 SCIP_LP* lp, /**< LP data, or NULL if called during presolving or propagation */
221 SCIP_NODE* nextnode, /**< next node that will be processed, or NULL if no more nodes left
222 * (only needed when calling after node heuristics) */
223 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
224 SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */
225 SCIP_Bool* foundsol, /**< pointer to store whether a solution has been found */
226 SCIP_Bool* unbounded /**< pointer to store whether an unbounded ray was found in the LP */
227 )
228{ /*lint --e{715}*/
230 SCIP_Longint oldnbestsolsfound;
231 SCIP_Real lowerbound;
232 int ndelayedheurs;
233 int depth;
235 int h;
236#ifndef NDEBUG
237 SCIP_Bool inprobing;
238 SCIP_Bool indiving;
239#endif
240
241 assert(set != NULL);
242 assert(primal != NULL);
252 assert(foundsol != NULL);
253
254 *foundsol = FALSE;
255
256 /* nothing to do, if no heuristics are available, or if the branch-and-bound process is finished */
257 if( set->nheurs == 0 || (heurtiming == SCIP_HEURTIMING_AFTERNODE && nextnode == NULL) )
258 return SCIP_OKAY;
259
260 /* do not continue if we reached a time limit */
261 if( SCIPsolveIsStopped(set, stat, FALSE) )
262 return SCIP_OKAY;
263
264 /* sort heuristics by priority, but move the delayed heuristics to the front */
266
267 /* specialize the AFTERNODE timing flag */
269 {
270 SCIP_Bool plunging;
271 SCIP_Bool pseudonode;
272
273 /* clear the AFTERNODE flags and replace them by the right ones */
275
276 /* we are in plunging mode iff the next node is a sibling or a child, and no leaf */
283 if( plunging && SCIPtreeGetCurrentDepth(tree) > 0 ) /* call plunging heuristics also at root node */
284 {
285 if( !pseudonode )
287 else
289 }
290 else
291 {
292 if( !pseudonode )
294 else
296 }
297 }
298
299 /* initialize the tree related data, if we are not in presolving */
301 {
302 depth = -1;
303 lpstateforkdepth = -1;
304
305 SCIPsetDebugMsg(set, "calling primal heuristics %s presolving\n",
306 heurtiming == SCIP_HEURTIMING_BEFOREPRESOL ? "before" : "during");
307 }
308 else
309 {
310 assert(tree != NULL); /* for lint */
313
314 SCIPsetDebugMsg(set, "calling primal heuristics in depth %d (timing: %u)\n", depth, heurtiming);
315 }
316
317 /* call heuristics */
318 ndelayedheurs = 0;
320
321#ifndef NDEBUG
322 /* remember old probing and diving status */
323 inprobing = tree != NULL && SCIPtreeProbing(tree);
324 indiving = lp != NULL && SCIPlpDiving(lp);
325
326 /* heuristics should currently not be called in diving mode */
327 assert(!indiving);
328#endif
329
330 /* collect lower bound of current node */
331 if( tree != NULL )
332 {
335 }
336 else if( lp != NULL )
337 lowerbound = SCIPlpGetPseudoObjval(lp, set, prob);
338 else
339 lowerbound = -SCIPsetInfinity(set);
340
341 for( h = 0; h < set->nheurs; ++h )
342 {
343#ifndef NDEBUG
345#endif
346 /* it might happen that a diving heuristic renders the previously solved node LP invalid
347 * such that additional calls to LP heuristics will fail; better abort the loop in this case
348 */
349 if( lp != NULL && lp->resolvelperror)
350 break;
351
352#ifdef SCIP_DEBUG
353 {
354 SCIP_Bool delayed;
356 {
357 SCIPsetDebugMsg(set, " -> executing heuristic <%s> with priority %d\n",
358 SCIPheurGetName(set->heurs[h]), SCIPheurGetPriority(set->heurs[h]));
359 }
360 }
361#endif
362
364 &ndelayedheurs, &result) );
365
366#ifndef NDEBUG
368 {
369 SCIPerrorMessage("Buffer not completely freed after executing heuristic <%s>\n", SCIPheurGetName(set->heurs[h]));
370 SCIPABORT();
371 }
372#endif
373
374 /* if the new solution cuts off the current node due to a new primal solution (via the cutoff bound) interrupt
375 * calling the remaining heuristics
376 */
377 if( (result == SCIP_FOUNDSOL && lowerbound > primal->cutoffbound) || SCIPsolveIsStopped(set, stat, FALSE) )
378 break;
379
380 /* check if the problem is proven to be unbounded, currently this happens only in reoptimization */
381 if( result == SCIP_UNBOUNDED )
382 {
383 *unbounded = TRUE;
384 break;
385 }
386
387 /* make sure that heuristic did not change probing or diving status */
388 assert(tree == NULL || inprobing == SCIPtreeProbing(tree));
389 assert(lp == NULL || indiving == SCIPlpDiving(lp));
390 }
392
394
395 return SCIP_OKAY;
396}
397
398/** applies one round of propagation */
399static
401 BMS_BLKMEM* blkmem, /**< block memory buffers */
402 SCIP_SET* set, /**< global SCIP settings */
403 SCIP_STAT* stat, /**< dynamic problem statistics */
404 SCIP_TREE* tree, /**< branch and bound tree */
405 int depth, /**< depth level to use for propagator frequency checks */
406 SCIP_Bool fullpropagation, /**< should all constraints be propagated (or only new ones)? */
407 SCIP_Bool onlydelayed, /**< should only delayed propagators be called? */
408 SCIP_Bool* delayed, /**< pointer to store whether a propagator was delayed */
409 SCIP_Bool* propagain, /**< pointer to store whether propagation should be applied again */
410 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */
411 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
412 SCIP_Bool* postpone /**< pointer to store whether the node should be postponed */
413 )
414{ /*lint --e{715}*/
416 SCIP_Bool abortoncutoff;
417 int i;
418
419 assert(set != NULL);
420 assert(delayed != NULL);
422 assert(cutoff != NULL);
423 assert(postpone != NULL);
424
425 *delayed = FALSE;
426 *propagain = FALSE;
427
428 /* sort propagators */
430
431 /* check if we want to abort on a cutoff; if we are not in the solving stage (e.g., in presolving), we want to abort
432 * anyway
433 */
434 abortoncutoff = set->prop_abortoncutoff || (set->stage != SCIP_STAGE_SOLVING);
435
436 /* call additional propagators with nonnegative priority */
437 for( i = 0; i < set->nprops && !(*postpone) && (!(*cutoff) || !abortoncutoff); ++i )
438 {
439#ifndef NDEBUG
441#endif
442 /* timing needs to fit */
443 if( (SCIPpropGetTimingmask(set->props[i]) & timingmask) == 0 )
444 continue;
445
446 if( SCIPpropGetPriority(set->props[i]) < 0 )
447 continue;
448
449 if( onlydelayed && !SCIPpropWasDelayed(set->props[i]) )
450 continue;
451
452 SCIPsetDebugMsg(set, "calling propagator <%s>\n", SCIPpropGetName(set->props[i]));
453
454 SCIP_CALL( SCIPpropExec(set->props[i], set, stat, depth, onlydelayed, tree->sbprobing, timingmask, &result) );
455
456#ifndef NDEBUG
458 {
459 SCIPerrorMessage("Buffer not completely freed after executing propagator <%s>\n", SCIPpropGetName(set->props[i]));
460 SCIPABORT();
461 }
462#endif
463
466
467 /* beside the result pointer of the propagator we have to check if an internal cutoff was detected; this can
468 * happen when a global bound change was applied which is globally valid and leads locally (for the current node
469 * and others) to an infeasible problem;
470 */
471 *cutoff = *cutoff || (result == SCIP_CUTOFF) || (tree->cutoffdepth <= SCIPtreeGetCurrentDepth(tree));
472 *postpone = (result == SCIP_DELAYNODE) && !(*cutoff);
473
474 if( result == SCIP_CUTOFF )
475 {
476 SCIPsetDebugMsg(set, " -> propagator <%s> detected cutoff\n", SCIPpropGetName(set->props[i]));
477 }
478
479 /* if we work off the delayed propagators, we stop immediately if a reduction was found */
481 {
482 *delayed = TRUE;
483 return SCIP_OKAY;
484 }
485 }
486
487 /* propagate constraints */
488 for( i = 0; i < set->nconshdlrs && !(*postpone) && (!(*cutoff) || !abortoncutoff); ++i )
489 {
490 /* timing needs to fit */
491 if( (SCIPconshdlrGetPropTiming(set->conshdlrs[i]) & timingmask) == 0 )
492 continue;
493
495 continue;
496
497 SCIPsetDebugMsg(set, "calling propagation method of constraint handler <%s>\n", SCIPconshdlrGetName(set->conshdlrs[i]));
498
500 tree->sbprobing, timingmask, &result) );
503
504 /* beside the result pointer of the propagator we have to check if an internal cutoff was detected; this can
505 * happen when a global bound change was applied which is globally valid and leads locally (for the current node
506 * and others) to an infeasible problem;
507 */
508 *cutoff = *cutoff || (result == SCIP_CUTOFF) || (tree->cutoffdepth <= SCIPtreeGetCurrentDepth(tree));
509 *postpone = (result == SCIP_DELAYNODE) && !(*cutoff);
510
511 if( result == SCIP_CUTOFF )
512 {
513 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in propagation\n",
514 SCIPconshdlrGetName(set->conshdlrs[i]));
515 }
516
517 /* if we work off the delayed propagators, we stop immediately if a reduction was found */
519 {
520 *delayed = TRUE;
521 return SCIP_OKAY;
522 }
523 }
524
525 /* call additional propagators with negative priority */
526 for( i = 0; i < set->nprops && !(*postpone) && (!(*cutoff) || !abortoncutoff); ++i )
527 {
528 /* timing needs to fit */
529 if( (SCIPpropGetTimingmask(set->props[i]) & timingmask) == 0 )
530 continue;
531
532 if( SCIPpropGetPriority(set->props[i]) >= 0 )
533 continue;
534
535 if( onlydelayed && !SCIPpropWasDelayed(set->props[i]) )
536 continue;
537
538 SCIPsetDebugMsg(set, "calling propagator <%s>\n", SCIPpropGetName(set->props[i]));
539
540 SCIP_CALL( SCIPpropExec(set->props[i], set, stat, depth, onlydelayed, tree->sbprobing, timingmask, &result) );
543
544 /* beside the result pointer of the propagator we have to check if an internal cutoff was detected; this can
545 * happen when a global bound change was applied which is globally valid and leads locally (for the current node
546 * and others) to an infeasible problem;
547 */
548 *cutoff = *cutoff || (result == SCIP_CUTOFF) || (tree->cutoffdepth <= SCIPtreeGetCurrentDepth(tree));
549 *postpone = (result == SCIP_DELAYNODE) && !(*cutoff);
550
551 if( result == SCIP_CUTOFF )
552 {
553 SCIPsetDebugMsg(set, " -> propagator <%s> detected cutoff\n", SCIPpropGetName(set->props[i]));
554 }
555
556 /* if we work off the delayed propagators, we stop immediately if a reduction was found */
558 {
559 *delayed = TRUE;
560 return SCIP_OKAY;
561 }
562 }
563
564 return SCIP_OKAY;
565}
566
567/** applies domain propagation on current node */
568static
570 BMS_BLKMEM* blkmem, /**< block memory buffers */
571 SCIP_SET* set, /**< global SCIP settings */
572 SCIP_STAT* stat, /**< dynamic problem statistics */
573 SCIP_TREE* tree, /**< branch and bound tree */
574 int depth, /**< depth level to use for propagator frequency checks */
575 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
576 SCIP_Bool fullpropagation, /**< should all constraints be propagated (or only new ones)? */
577 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */
578 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
579 SCIP_Bool* postpone /**< pointer to store whether the node should be postponed */
580 )
581{
582 SCIP_NODE* node;
583 SCIP_Bool delayed;
584 SCIP_Bool propagain;
585 int propround;
586
587 assert(set != NULL);
588 assert(tree != NULL);
589 assert(depth >= 0);
590 assert(cutoff != NULL);
591
592 node = SCIPtreeGetCurrentNode(tree);
593 assert(node != NULL && SCIPnodeIsActive(node));
597
598 /* adjust maximal number of propagation rounds */
599 if( maxproprounds == 0 )
600 maxproprounds = (depth == 0 ? set->prop_maxroundsroot : set->prop_maxrounds);
601 if( maxproprounds == -1 )
602 maxproprounds = INT_MAX;
603
604 SCIPsetDebugMsg(set, "domain propagation of node %p in depth %d (using depth %d, maxrounds %d, proptiming %u)\n",
605 (void*)node, SCIPnodeGetDepth(node), depth, maxproprounds, timingmask);
606
607 /* propagate as long new bound changes were found and the maximal number of propagation rounds is not exceeded */
608 *cutoff = FALSE;
609 *postpone = FALSE;
610 propround = 0;
611 propagain = TRUE;
612 while( propagain && !(*cutoff) && !(*postpone) && propround < maxproprounds && !SCIPsolveIsStopped(set, stat, FALSE) )
613 {
614 propround++;
615
616 /* perform the propagation round by calling the propagators and constraint handlers */
617 SCIP_CALL( propagationRound(blkmem, set, stat, tree, depth, fullpropagation, FALSE, &delayed, &propagain, timingmask, cutoff, postpone) );
618
619 /* if the propagation will be terminated, call the delayed propagators */
620 while( delayed && (!propagain || propround >= maxproprounds) && !(*cutoff) )
621 {
622 /* call the delayed propagators and constraint handlers */
623 SCIP_CALL( propagationRound(blkmem, set, stat, tree, depth, fullpropagation, TRUE, &delayed, &propagain, timingmask, cutoff, postpone) );
624 }
625
626 /* if a reduction was found, we want to do another full propagation round (even if the propagator only claimed
627 * to have done a domain reduction without applying a domain change)
628 */
630 }
631
632 /* mark the node to be completely propagated in the current repropagation subtree level */
633 SCIPnodeMarkPropagated(node, tree);
634
635 if( *cutoff )
636 {
637 SCIPsetDebugMsg(set, " --> domain propagation of node %p finished: cutoff!\n", (void*)node);
638 }
639
640 return SCIP_OKAY;
641}
642
643/** applies domain propagation on current node and flushes the conflict store afterwards */
645 BMS_BLKMEM* blkmem, /**< block memory buffers */
646 SCIP_SET* set, /**< global SCIP settings */
647 SCIP_STAT* stat, /**< dynamic problem statistics */
648 SCIP_PROB* transprob, /**< transformed problem */
649 SCIP_PROB* origprob, /**< original problem */
650 SCIP_TREE* tree, /**< branch and bound tree */
651 SCIP_REOPT* reopt, /**< reoptimization data structure */
652 SCIP_LP* lp, /**< LP data */
653 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
654 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
655 SCIP_CONFLICT* conflict, /**< conflict analysis data */
656 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
657 int depth, /**< depth level to use for propagator frequency checks */
658 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
659 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */
660 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
661 )
662{
663 SCIP_Bool postpone;
664
665 /* apply domain propagation */
666 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, depth, maxproprounds, TRUE, timingmask, cutoff, &postpone) );
667
668 /* flush the conflict set storage */
669 SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable) );
670
671 return SCIP_OKAY;
672}
673
674/** returns whether the given variable with the old LP solution value should lead to an update of the pseudo cost entry */
675static
677 SCIP_VAR* var, /**< problem variable */
678 SCIP_SET* set, /**< global SCIP settings */
679 SCIP_Real oldlpsolval, /**< solution value of variable in old LP */
680 SCIP_Bool updateintegers, /**< whether to update pseudo costs for integer variables */
681 SCIP_Bool updatecontinuous /**< whether to update pseudo costs for continuous variables */
682 )
683{
684 SCIP_Real newlpsolval;
685
686 assert(var != NULL);
687
689 return FALSE;
690
692 return FALSE;
693
694 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS && set->branch_lpgainnorm != 'l' )
695 {
696 /* if the variable is fixed at +/- infinity or it has an unbounded domain, then the domain-based update strategies will not work */
698 return FALSE;
699
700 /* @todo if set->branch_lpgainnorm == 's', then we would need to know then domain before branching
701 * since this is difficult to get, we don't check for unboundedness here and let the pscost update fail later
702 * however, this makes the weights used to spread a pseudo cost update over all domain changes inaccurate
703 */
704
705 return TRUE;
706 }
707
708 /* if the old LP solution value is unknown, the pseudo cost update cannot be performed */
710 return FALSE;
711
712 /* the bound change on the given variable was responsible for the gain in the dual bound, if the variable's
713 * old solution value is outside the current bounds, and the new solution value is equal to the bound
714 * closest to the old solution value
715 */
716
717 /* find out, which of the current bounds is violated by the old LP solution value */
719 {
722 }
724 {
727 }
728 else
729 return FALSE;
730}
731
732/** pseudo cost flag stored in the variables to mark them for the pseudo cost update */
734{
735 PSEUDOCOST_NONE = 0, /**< variable's bounds were not changed */
736 PSEUDOCOST_IGNORE = 1, /**< bound changes on variable should be ignored for pseudo cost updates */
737 PSEUDOCOST_UPDATE = 2 /**< pseudo cost value of variable should be updated */
740
741/** updates the variable's pseudo cost values after the node's initial LP was solved */
742static
744 SCIP_SET* set, /**< global SCIP settings */
745 SCIP_STAT* stat, /**< dynamic problem statistics */
746 SCIP_PROB* prob, /**< transformed problem after presolve */
747 SCIP_TREE* tree, /**< branch and bound tree */
748 SCIP_LP* lp, /**< LP data */
749 SCIP_Bool updateintegers, /**< whether to update pseudo costs for integer variables */
750 SCIP_Bool updatecontinuous /**< whether to update pseudo costs for continuous variables */
751 )
752{
753 SCIP_NODE* focusnode;
754 int actdepth;
755
756 assert(lp != NULL);
757 assert(tree != NULL);
758 assert(tree->path != NULL);
759
760 focusnode = SCIPtreeGetFocusNode(tree);
761 assert(SCIPnodeIsActive(focusnode));
763 actdepth = SCIPnodeGetDepth(focusnode);
764 assert(tree->path[actdepth] == focusnode);
765
767 {
769 SCIP_NODE* node;
770 SCIP_VAR* var;
771 SCIP_Real weight;
772 SCIP_Real lpgain;
773 int nupdates;
774 int nvalidupdates;
775 int d;
776 int i;
777
779 assert(tree->path[tree->focuslpstatefork->depth] == tree->focuslpstatefork);
780
781 /* get a buffer for the collected bound changes; start with a size twice as large as the number of nodes between
782 * current node and LP fork
783 */
785 nupdates = 0;
786 nvalidupdates = 0;
787
788 /* search the nodes from LP fork down to current node for bound changes in between; move in this direction,
789 * because the bound changes closer to the LP fork are more likely to have a valid LP solution information
790 * attached; collect the bound changes for pseudo cost value updates and mark the corresponding variables such
791 * that they are not updated twice in case of more than one bound change on the same variable
792 */
793 for( d = tree->focuslpstatefork->depth+1; d <= actdepth; ++d )
794 {
795 node = tree->path[d];
796
797 if( node->domchg != NULL )
798 {
799 SCIP_BOUNDCHG* boundchgs;
800 int nboundchgs;
801
802 boundchgs = node->domchg->domchgbound.boundchgs;
803 nboundchgs = (int) node->domchg->domchgbound.nboundchgs;
804 for( i = 0; i < nboundchgs; ++i )
805 {
806 var = boundchgs[i].var;
807 assert(var != NULL);
808
809 /* we even collect redundant bound changes, since they were not redundant in the LP branching decision
810 * and therefore should be regarded in the pseudocost updates
811 *
812 * however, if the variable is continuous and we normalize the pseudo costs by the domain reduction,
813 * then getting the variable bound before the branching is not possible by looking at the variables branching information (since redundant branchings are not applied)
814 * thus, in this case we ignore the boundchange
815 */
816 if( (SCIP_BOUNDCHGTYPE)boundchgs[i].boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING &&
818 )
819 {
820 /* remember the bound change and mark the variable */
822 updates[nupdates] = &boundchgs[i];
823 nupdates++;
824
825 /* check, if the bound change would lead to a valid pseudo cost update
826 * and see comment above (however, ...) */
828 (SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS || !boundchgs[i].redundant || set->branch_lpgainnorm != 'd')
829 )
830 {
831 var->pseudocostflag = PSEUDOCOST_UPDATE; /*lint !e641*/
833 }
834 else
835 var->pseudocostflag = PSEUDOCOST_IGNORE; /*lint !e641*/
836 }
837 }
838 }
839 }
840
841 /* update the pseudo cost values and reset the variables' flags; assume, that the responsibility for the dual gain
842 * is equally spread on all bound changes that lead to valid pseudo cost updates
843 */
845 weight = (nvalidupdates > 0 ? 1.0 / (SCIP_Real)nvalidupdates : 1.0);
846 lpgain = (SCIPlpGetObjval(lp, set, prob) - tree->focuslpstatefork->data.fork->lpobjval) * weight;
847 lpgain = MAX(lpgain, 0.0);
848
849 for( i = 0; i < nupdates; ++i )
850 {
852
853 var = updates[i]->var;
854 assert(var != NULL);
856
858 {
859 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS || set->branch_lpgainnorm == 'l' )
860 {
861 SCIPsetDebugMsg(set, "updating pseudocosts of <%s>: sol: %g -> %g, LP: %e -> %e => solvaldelta = %g, gain=%g, weight: %g\n",
862 SCIPvarGetName(var), updates[i]->data.branchingdata.lpsolval, SCIPvarGetLPSol(var),
864 SCIPvarGetLPSol(var) - updates[i]->data.branchingdata.lpsolval, lpgain, weight);
866 SCIPvarGetLPSol(var) - updates[i]->data.branchingdata.lpsolval, lpgain, weight) );
867 }
868 else
869 {
870 /* set->branch_lpgainnorm == 'd':
871 * For continuous variables, we want to pseudocosts to be the average of the gain in the LP value
872 * if the domain is reduced from x% of its original width to y% of its original (e.g., global) width, i.e.,
873 * to be the average of LPgain / (oldwidth/origwidth - newwidth/origwidth) = LPgain * origwidth / (oldwidth - newwidth).
874 * Then an expected improvement in the LP value by a reduction of the domain width
875 * from x% to y% of its original width can be computed by pseudocost * (oldwidth - newwidth) / origwidth.
876 * Since the original width cancels out, we can also define the pseudocosts as average of LPgain / (oldwidth - newwidth)
877 * and compute the expected improvement as pseudocost * (oldwidth - newwidth).
878 *
879 * Let var have bounds [a,c] before the branching and assume we branched on some value b.
880 * b is given by updates[i]->newbound.
881 *
882 * If updates[i]->boundtype = upper, then node corresponds to the child [a,b].
883 * Thus, we have oldwidth = c-a, newwidth = b-a, and oldwidth - newwidth = c-b.
884 * To get c (the previous upper bound), we look into the var->ubchginfos array.
885 *
886 * If updates[i]->boundtype = lower, then node corresponds to the child [b,c].
887 * Thus, we have oldwidth = c-a, newwidth = c-b, and oldwidth - newwidth = b-a.
888 * To get c (the previous lower bound), we look into the var->lbchginfos array.
889 */
891 SCIP_Real oldbound;
892 SCIP_Real delta;
893 int j;
894 int nbdchginfos;
895
896 assert(set->branch_lpgainnorm == 'd' || set->branch_lpgainnorm == 's');
897
898 oldbound = SCIP_INVALID;
899
900 if( set->branch_lpgainnorm == 'd' )
901 {
902 assert(!updates[i]->redundant);
903
904 if( (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER )
905 {
906 nbdchginfos = SCIPvarGetNBdchgInfosUb(var);
907
908 /* walk backwards through bound change information array to find the bound change corresponding to branching in updates[i]
909 * usually it will be the first one we look at */
910 for( j = nbdchginfos-1; j >= 0; --j )
911 {
913
914 if( bdchginfo->oldbound > updates[i]->newbound )
915 {
916 /* first boundchange which upper bound is above the upper bound set by the branching in updates[i]
917 * if bdchginfo->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING, then this should be exactly the bound change that we are looking for
918 * if bdchginfo->boundchgtype != SCIP_BOUNDCHGTYPE_BRANCHING, then this should be because the branching domain change has not been applied to the variable due to redundancy
919 * in this case, i.e., if there was another boundchange coming from somewhere else, I am not sure whether oldbound is an accurate value to compute the old domain size, so we skip the pseudocosts update
920 */
922 {
923 assert(bdchginfo->newbound == updates[i]->newbound); /*lint !e777*/
924 oldbound = bdchginfo->oldbound;
925 }
926 else
927 assert(updates[i]->redundant);
928
929 break;
930 }
931 }
932 /* if the bound change was redundant (e.g., due to a change in the global bound), then it was not applied, so there exists no corresponding bound change info
933 * if it is not redundant, then we should have found at least one corresponding boundchange */
934 assert(j >= 0 || updates[i]->redundant);
935 if( oldbound != SCIP_INVALID ) /*lint !e777*/
936 {
937 assert(!SCIPsetIsInfinity(set, -oldbound)); /* branching on a variable fixed to -infinity does not make sense */
938 assert(!SCIPsetIsInfinity(set, updates[i]->newbound)); /* branching to infinity does not make sense */
939
940 /* if the old upper bound is at infinity or the new upper bound is at -infinity, then we say the delta (c-b) is infinity */
941 if( SCIPsetIsInfinity(set, oldbound) || SCIPsetIsInfinity(set, -updates[i]->newbound) )
942 delta = SCIP_INVALID;
943 else
944 delta = updates[i]->newbound - oldbound;
945 }
946 else
947 delta = SCIP_INVALID;
948 }
949 else
950 {
952 nbdchginfos = SCIPvarGetNBdchgInfosLb(var);
953
954 /* walk backwards through bound change information array to find the bound change corresponding to branching in updates[i]
955 * usually it will be the first one we look at */
956 for( j = nbdchginfos-1; j >= 0; --j )
957 {
959
960 if( bdchginfo->oldbound < updates[i]->newbound )
961 {
962 /* first boundchange which lower bound is below the lower bound set by the branching in updates[i]
963 * if bdchginfo->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING, then this should be exactly the bound change that we are looking for
964 * if bdchginfo->boundchgtype != SCIP_BOUNDCHGTYPE_BRANCHING, then this should be because the branching domain change has not been applied to the variable due to redundancy
965 * in this case, i.e., if there was another boundchange coming from somewhere else, I am not sure whether oldbound is an accurate value to compute the old domain size, so we skip the pseudocosts update
966 */
968 {
969 assert(bdchginfo->newbound == updates[i]->newbound); /*lint !e777*/
970 oldbound = bdchginfo->oldbound;
971 }
972 else
973 assert(updates[i]->redundant);
974
975 break;
976 }
977 }
978 /* if the bound change was redundant (e.g., due to a change in the global bound), then it was not applied, so there exists no corresponding bound change info
979 * if it is not redundant, then we should have found at least one corresponding boundchange */
980 assert(j >= 0 || updates[i]->redundant);
981 if( oldbound != SCIP_INVALID ) /*lint !e777*/
982 {
983 assert(!SCIPsetIsInfinity(set, oldbound)); /* branching on a variable fixed to +infinity does not make sense */
984 assert(!SCIPsetIsInfinity(set, -updates[i]->newbound)); /* branching to infinity does not make sense */
985
986 /* if the old lower bound is at -infinity or the new lower bound is at +infinity, then we say the delta (b-a) is infinity */
987 if( SCIPsetIsInfinity(set, -oldbound) || SCIPsetIsInfinity(set, updates[i]->newbound) )
988 delta = SCIP_INVALID;
989 else
990 delta = updates[i]->newbound - oldbound;
991 }
992 else
993 delta = SCIP_INVALID;
994 }
995 }
996 else
997 {
998 /* set->branch_lpgainnorm == 's':
999 * Here, we divide the LPgain by the reduction in the sibling node.
1000 *
1001 * If updates[i]->boundtype = upper, then node corresponds to the child [a,b].
1002 * Thus, we have oldwidth = c-a, newwidth = c-b, and oldwidth - newwidth = b-a.
1003 * Conveniently, we just use the current lower bound for a (it may have been tightened, though).
1004 *
1005 * If updates[i]->boundtype = lower, then node corresponds to the child [b,a].
1006 * Thus, we have oldwidth = c-a, newwidth = b-a, and oldwidth - newwidth = c-b.
1007 * Conveniently, we just use the current upper bound for c (it may have been tightened, though).
1008 */
1009 if( (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER )
1010 {
1011 assert(!SCIPsetIsInfinity(set, updates[i]->newbound)); /* branching on a variable fixed to +infinity does not make sense */
1012 assert(!SCIPsetIsInfinity(set, SCIPvarGetLbLocal(var))); /* branching to infinity does not make sense */
1014 delta = SCIP_INVALID;
1015 else
1016 delta = updates[i]->newbound - SCIPvarGetLbLocal(var);
1017 }
1018 else
1019 {
1021 assert(!SCIPsetIsInfinity(set, -updates[i]->newbound)); /* branching on a variable fixed to -infinity does not make sense */
1022 assert(!SCIPsetIsInfinity(set, -SCIPvarGetUbLocal(var))); /* branching to -infinity does not make sense */
1024 delta = SCIP_INVALID;
1025 else
1026 delta = -(SCIPvarGetUbLocal(var) - updates[i]->newbound);
1027 }
1028 }
1029
1030 if( delta != SCIP_INVALID ) /*lint !e777*/
1031 {
1032 SCIPsetDebugMsg(set, "updating pseudocosts of <%s> with strategy %c: domain: [%g,%g] -> [%g,%g], LP: %e -> %e => "
1033 "delta = %g, gain=%g, weight: %g\n",
1034 SCIPvarGetName(var), set->branch_lpgainnorm,
1035 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? SCIPvarGetLbLocal(var) : oldbound,
1036 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? oldbound : SCIPvarGetUbLocal(var),
1040 delta, lpgain, weight);
1041
1042 SCIP_CALL( SCIPvarUpdatePseudocost(var, set, stat, delta, lpgain, weight) );
1043 }
1044 }
1045 }
1046 var->pseudocostflag = PSEUDOCOST_NONE; /*lint !e641*/
1047 }
1048
1049 /* free the buffer for the collected bound changes */
1051 }
1052
1053 return SCIP_OKAY;
1054}
1055
1056/** updates the estimated value of a primal feasible solution for the focus node after the LP was solved */
1057static
1059 SCIP_SET* set, /**< global SCIP settings */
1060 SCIP_STAT* stat, /**< problem statistics */
1061 SCIP_TREE* tree, /**< branch and bound tree */
1062 SCIP_LP* lp, /**< current LP data */
1063 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
1064 )
1065{
1066 SCIP_NODE* focusnode;
1067 SCIP_VAR** lpcands;
1068 SCIP_Real* lpcandsfrac;
1069 SCIP_Real estimate;
1070 int nlpcands;
1071 int i;
1072
1073 /* estimate is only available if LP was solved to optimality */
1075 return SCIP_OKAY;
1076
1077 focusnode = SCIPtreeGetFocusNode(tree);
1078 assert(focusnode != NULL);
1079
1080 /* get the fractional variables */
1081 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, &lpcands, NULL, &lpcandsfrac, &nlpcands, NULL, NULL) );
1082
1083 /* calculate the estimate: lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) */
1084 estimate = SCIPnodeGetLowerbound(focusnode);
1085
1086 /* an infinite lower bound implies an infinite estimate */
1087 if( SCIPsetIsInfinity(set, estimate) )
1088 {
1089 SCIPnodeSetEstimate(focusnode, set, estimate);
1090 return SCIP_OKAY;
1091 }
1092
1093 for( i = 0; i < nlpcands; ++i )
1094 {
1095 SCIP_Real pscdown;
1096 SCIP_Real pscup;
1097
1100 estimate += MIN(pscdown, pscup);
1101 }
1102 SCIPnodeSetEstimate(focusnode, set, estimate);
1103
1104 return SCIP_OKAY;
1105}
1106
1107/** puts all constraints with initial flag TRUE into the LP */
1109 BMS_BLKMEM* blkmem, /**< block memory buffers */
1110 SCIP_SET* set, /**< global SCIP settings */
1111 SCIP_SEPASTORE* sepastore, /**< separation storage */
1112 SCIP_CUTPOOL* cutpool, /**< global cutpool */
1113 SCIP_STAT* stat, /**< dynamic problem statistics */
1114 SCIP_PROB* transprob, /**< transformed problem */
1115 SCIP_PROB* origprob, /**< original problem */
1116 SCIP_TREE* tree, /**< branch and bound tree */
1117 SCIP_REOPT* reopt, /**< reoptimization data structure */
1118 SCIP_LP* lp, /**< LP data */
1119 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1120 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1121 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1122 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1123 SCIP_Bool root, /**< is this the initial root LP? */
1124 SCIP_Bool firstsubtreeinit, /**< is this the first call in the current subtree after jumping through the tree? */
1125 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1126 )
1127{
1128 int h;
1129
1130 assert(set != NULL);
1131 assert(lp != NULL);
1132 assert(cutoff != NULL);
1133
1134 *cutoff = FALSE;
1135
1136 /* inform separation storage, that LP is now filled with initial data */
1137 SCIPsepastoreStartInitialLP(sepastore);
1138
1139 /* add LP relaxations of all initial constraints to LP */
1140 SCIPsetDebugMsg(set, "init LP: initial rows\n");
1141 for( h = 0; h < set->nconshdlrs && !(*cutoff); ++h )
1142 {
1143 SCIP_CALL( SCIPconshdlrInitLP(set->conshdlrs[h], blkmem, set, stat, tree, firstsubtreeinit, cutoff) );
1144 }
1145
1146 if( set->reopt_enable && set->reopt_usecuts && firstsubtreeinit && !(*cutoff) )
1147 {
1148 /* add stored cuts from last reoptimization run */
1149 SCIP_CALL( SCIPreoptApplyCuts(reopt, tree->focusnode, sepastore, cutpool, blkmem, set, stat, eventqueue,
1150 eventfilter, lp, root) );
1151 }
1152
1153 if( !(*cutoff) )
1154 {
1155 /* apply cuts */
1156 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
1157 eventqueue, eventfilter, cliquetable, root, SCIP_EFFICIACYCHOICE_LP, cutoff) );
1158 }
1159 else
1160 {
1161 /* the current node will be cut off; we clear the sepastore */
1162 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
1163 }
1164
1165 /* inform separation storage, that initial LP setup is now finished */
1166 SCIPsepastoreEndInitialLP(sepastore);
1167
1168 return SCIP_OKAY;
1169}
1170
1171/** constructs the initial LP of the current node */
1172static
1174 BMS_BLKMEM* blkmem, /**< block memory buffers */
1175 SCIP_SET* set, /**< global SCIP settings */
1176 SCIP_STAT* stat, /**< dynamic problem statistics */
1177 SCIP_PROB* transprob, /**< transformed problem */
1178 SCIP_PROB* origprob, /**< original problem */
1179 SCIP_TREE* tree, /**< branch and bound tree */
1180 SCIP_REOPT* reopt, /**< reoptimization data structure */
1181 SCIP_LP* lp, /**< LP data */
1182 SCIP_PRICESTORE* pricestore, /**< pricing storage */
1183 SCIP_SEPASTORE* sepastore, /**< separation storage */
1184 SCIP_CUTPOOL* cutpool, /**< global cut pool */
1185 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1186 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1187 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1188 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1189 SCIP_Bool root, /**< is this the initial root LP? */
1190 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1191 )
1192{
1193 SCIP_VAR* var;
1194 int oldnvars = 0;
1195 int v;
1196
1197 assert(set != NULL);
1198 assert(transprob != NULL);
1199 assert(lp != NULL);
1200 assert(cutoff != NULL);
1201
1202 *cutoff = FALSE;
1203
1204 /* at the root node, we have to add the initial variables as columns */
1205 if( root )
1206 {
1207 assert(SCIPlpGetNCols(lp) == 0);
1208 assert(SCIPlpGetNRows(lp) == 0);
1209 assert(lp->nremovablecols == 0);
1210 assert(lp->nremovablerows == 0);
1211
1212 /* store number of variables for later */
1213 oldnvars = transprob->nvars;
1214
1215 /* inform pricing storage, that LP is now filled with initial data */
1216 SCIPpricestoreStartInitialLP(pricestore);
1217
1218 /* add all initial variables to LP */
1219 SCIPsetDebugMsg(set, "init LP: initial columns\n");
1220 for( v = 0; v < transprob->nvars && !(*cutoff); ++v )
1221 {
1222 var = transprob->vars[v];
1224
1225 if( SCIPvarIsInitial(var) )
1226 {
1227 SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, 0.0, TRUE) );
1228 }
1229
1230 /* check for empty domains (necessary if no presolving was performed) */
1232 *cutoff = TRUE;
1233 }
1234 assert(lp->nremovablecols == 0);
1235 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) );
1236
1237 /* inform pricing storage, that initial LP setup is now finished */
1238 SCIPpricestoreEndInitialLP(pricestore);
1239 }
1240
1241 if( *cutoff )
1242 return SCIP_OKAY;
1243
1244 /* put all initial constraints into the LP */
1245 /* @todo check whether we jumped through the tree */
1246 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
1247 eventfilter, cliquetable, root, TRUE, cutoff) );
1248
1249 /* putting all initial constraints into the LP might have added new variables */
1250 if( root && !(*cutoff) && transprob->nvars > oldnvars )
1251 {
1252 /* inform pricing storage, that LP is now filled with initial data */
1253 SCIPpricestoreStartInitialLP(pricestore);
1254
1255 /* check all initial variables */
1256 for( v = 0; v < transprob->nvars && !(*cutoff); ++v )
1257 {
1258 var = transprob->vars[v];
1260
1262 {
1263 SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, 0.0, TRUE) );
1264 }
1265
1266 /* check for empty domains (necessary if no presolving was performed) */
1268 *cutoff = TRUE;
1269 }
1270 assert(lp->nremovablecols == 0);
1271 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) );
1272
1273 /* inform pricing storage, that initial LP setup is now finished */
1274 SCIPpricestoreEndInitialLP(pricestore);
1275 }
1276
1277 return SCIP_OKAY;
1278}
1279
1280/** constructs the LP of the current node, but does not load the LP state and warmstart information */
1282 BMS_BLKMEM* blkmem, /**< block memory buffers */
1283 SCIP_SET* set, /**< global SCIP settings */
1284 SCIP_STAT* stat, /**< dynamic problem statistics */
1285 SCIP_PROB* transprob, /**< transformed problem */
1286 SCIP_PROB* origprob, /**< original problem */
1287 SCIP_TREE* tree, /**< branch and bound tree */
1288 SCIP_REOPT* reopt, /**< reoptimization data structure */
1289 SCIP_LP* lp, /**< LP data */
1290 SCIP_PRICESTORE* pricestore, /**< pricing storage */
1291 SCIP_SEPASTORE* sepastore, /**< separation storage */
1292 SCIP_CUTPOOL* cutpool, /**< global cutpool */
1293 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1294 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1295 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1296 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1297 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
1298 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1299 )
1300{
1301 SCIP_Bool initroot = FALSE;
1302
1303 assert(tree != NULL);
1304 assert(cutoff != NULL);
1305
1306 *cutoff = FALSE;
1307
1309 {
1310 /* inform separation storage, that LP is now filled with initial data */
1311 SCIPsepastoreStartInitialLP(sepastore);
1312
1313 if( tree->correctlpdepth >= 0 )
1314 {
1315 int i;
1316
1317 for( i = tree->pathnlprows[tree->correctlpdepth]; i < lp->nrows; ++i )
1318 {
1319 /* keep all active global cuts that where applied in the previous node in the lp */
1320 if( !lp->rows[i]->local && lp->rows[i]->age == 0 )
1321 {
1322 lp->rows[i]->fromcutpool = TRUE; /* this has no effect inside initial LP, but is set for consistency */
1323 SCIP_CALL( SCIPsepastoreAddCut(sepastore, blkmem, set, stat, eventqueue, eventfilter, lp, lp->rows[i],
1324 TRUE, (SCIPtreeGetCurrentDepth(tree) == 0), cutoff) );
1325 }
1326 }
1327 }
1328
1329 if( !(*cutoff) )
1330 {
1331 /* load the LP into the solver and load the LP state */
1332 SCIPsetDebugMsg(set, "loading LP\n");
1333 SCIP_CALL( SCIPtreeLoadLP(tree, blkmem, set, eventqueue, eventfilter, lp, &initroot) );
1336
1337 /* apply cuts */
1338 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
1339 eventqueue, eventfilter, cliquetable, (SCIPtreeGetCurrentDepth(tree) == 0), SCIP_EFFICIACYCHOICE_LP, cutoff) );
1340 }
1341 else
1342 {
1343 /* the current node will be cut off; we clear the sepastore */
1344 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
1345 }
1346
1347 /* inform separation storage, that initial LP setup is now finished */
1348 SCIPsepastoreEndInitialLP(sepastore);
1349
1350 if( !(*cutoff) )
1351 {
1352 /* setup initial LP relaxation of node */
1353 SCIP_CALL( initLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, pricestore, sepastore, cutpool, branchcand,
1354 eventqueue, eventfilter, cliquetable, initroot, cutoff) );
1355 }
1356 }
1357 else if( newinitconss )
1358 {
1359 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob,
1360 origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE,
1361 cutoff) );
1362 }
1363
1364 return SCIP_OKAY;
1365}
1366
1367/** updates the primal ray stored in primal data
1368 * clears previously stored primal ray, if existing and there was no LP error
1369 * stores current primal ray, if LP is unbounded and there has been no error
1370 */
1371static
1373 BMS_BLKMEM* blkmem, /**< block memory buffers */
1374 SCIP_SET* set, /**< global SCIP settings */
1375 SCIP_STAT* stat, /**< dynamic problem statistics */
1376 SCIP_PROB* prob, /**< transformed problem after presolve */
1377 SCIP_PRIMAL* primal, /**< primal data */
1378 SCIP_TREE* tree, /**< branch and bound tree */
1379 SCIP_LP* lp, /**< LP data */
1380 SCIP_Bool lperror /**< has there been an LP error? */
1381 )
1382{
1383 assert(blkmem != NULL);
1384 assert(set != NULL);
1385 assert(stat != NULL);
1386 assert(prob != NULL);
1387 assert(primal != NULL);
1388 assert(tree != NULL);
1389 assert(lp != NULL);
1390
1391 if( lperror )
1392 return SCIP_OKAY;
1393
1394 /* clear previously stored primal ray, if any */
1395 if( primal->primalray != NULL )
1396 {
1397 SCIP_CALL( SCIPsolFree(&primal->primalray, blkmem, primal) );
1398 }
1399
1400 /* store unbounded ray, if LP is unbounded */
1402 {
1403 SCIP_VAR** vars;
1404 SCIP_Real* ray;
1405 int nvars;
1406 int i;
1407
1408 SCIPsetDebugMsg(set, "LP is unbounded, store primal ray\n");
1409
1410 vars = prob->vars;
1411 nvars = prob->nvars;
1412
1413 /* get buffer memory for storing the ray and load the ray values into it */
1417
1418 /* create solution to store the primal ray in */
1419 assert(primal->primalray == NULL);
1420 SCIP_CALL( SCIPsolCreate(&primal->primalray, blkmem, set, stat, primal, tree, NULL) );
1421
1422 /* set values of all active variable in the solution that represents the primal ray */
1423 for( i = 0; i < nvars; i++ )
1424 {
1425 SCIP_CALL( SCIPsolSetVal(primal->primalray, set, stat, tree, vars[i], ray[i]) );
1426 }
1427
1428 SCIPdebug( SCIP_CALL( SCIPprintRay(set->scip, primal->primalray, NULL, FALSE) ) );
1429
1430 /* free memory for buffering the ray values */
1432 }
1433
1434 return SCIP_OKAY;
1435}
1436
1437/** load and solve the initial LP of a node */
1438static
1440 BMS_BLKMEM* blkmem, /**< block memory buffers */
1441 SCIP_SET* set, /**< global SCIP settings */
1442 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1443 SCIP_STAT* stat, /**< dynamic problem statistics */
1444 SCIP_PROB* transprob, /**< transformed problem after presolve */
1445 SCIP_PROB* origprob, /**< original problem */
1446 SCIP_PRIMAL* primal, /**< primal data */
1447 SCIP_TREE* tree, /**< branch and bound tree */
1448 SCIP_REOPT* reopt, /**< reoptimization data structure */
1449 SCIP_LP* lp, /**< LP data */
1450 SCIP_PRICESTORE* pricestore, /**< pricing storage */
1451 SCIP_SEPASTORE* sepastore, /**< separation storage */
1452 SCIP_CUTPOOL* cutpool, /**< global cutpool */
1453 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1454 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1455 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1456 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1457 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
1458 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
1459 SCIP_Bool* lperror /**< pointer to store whether an unresolved error in LP solving occured */
1460 )
1461{
1462 /* initializing variables for compiler warnings, which are not correct */
1463 SCIP_Real starttime = 0.0;
1464 SCIP_Longint nlpiterations = 0;
1465 SCIP_NODE* focusnode;
1466
1467 assert(stat != NULL);
1468 assert(tree != NULL);
1469 assert(lp != NULL);
1470 assert(cutoff != NULL);
1471 assert(lperror != NULL);
1474
1475 *cutoff = FALSE;
1476 *lperror = FALSE;
1477
1478 /* load the LP into the solver */
1479 SCIP_CALL( SCIPconstructCurrentLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, pricestore, sepastore, cutpool,
1480 branchcand, eventqueue, eventfilter, cliquetable, newinitconss, cutoff) );
1481
1482 if( *cutoff )
1483 return SCIP_OKAY;
1484
1485 /* load the LP state */
1486 SCIP_CALL( SCIPtreeLoadLPState(tree, blkmem, set, transprob, stat, eventqueue, lp) );
1487
1488 focusnode = SCIPtreeGetFocusNode(tree);
1489
1490 /* store current LP iteration count and solving time if we are at the root node */
1491 if( focusnode->depth == 0 )
1492 {
1494 starttime = SCIPclockGetTime(stat->solvingtime);
1495 }
1496
1497 /* solve initial LP */
1498 SCIPsetDebugMsg(set, "node: solve initial LP\n");
1499 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
1500 SCIPnodeGetDepth(SCIPtreeGetFocusNode(tree)) == 0 ? set->lp_rootiterlim : set->lp_iterlim, TRUE, TRUE, FALSE, lperror) );
1501 assert(lp->flushed);
1502 assert(lp->solved || *lperror);
1503
1504 /* save time for very first LP in root node */
1505 if ( stat->nnodelps == 0 && focusnode->depth == 0 )
1506 {
1507 stat->firstlptime = SCIPclockGetTime(stat->solvingtime) - starttime;
1508 }
1509
1510 /* remove previous primal ray, store new one if LP is unbounded */
1511 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
1512
1513 if( !(*lperror) )
1514 {
1515 /* cppcheck-suppress unassignedVariable */
1517
1519 {
1520 /* issue FIRSTLPSOLVED event */
1523 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
1524 }
1525
1526 /* update pseudo cost values for integer variables (always) and for continuous variables (if not delayed) */
1527 SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, TRUE, !set->branch_delaypscost) );
1528
1529 /* update lower bound of current node w.r.t. initial lp */
1530 assert(!(*cutoff));
1533 && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
1534 {
1535 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
1536
1537 /* if this is the first LP solved at the root, store its iteration count and solution value */
1538 if( stat->nnodelps == 0 && focusnode->depth == 0 )
1539 {
1540 SCIP_Real lowerbound;
1541
1542 assert(stat->nrootfirstlpiterations == 0);
1544
1545 if( set->misc_exactsolve )
1546 {
1547 SCIP_CALL( SCIPlpGetProvedLowerbound(lp, set, &lowerbound) );
1548 }
1549 else
1550 lowerbound = SCIPlpGetObjval(lp, set, transprob);
1551
1552 stat->firstlpdualbound = SCIPprobExternObjval(transprob, origprob, set, lowerbound);
1553 }
1554 }
1555 }
1556
1557 return SCIP_OKAY;
1558}
1559
1560/** makes sure the LP is flushed and solved */
1561static
1563 BMS_BLKMEM* blkmem, /**< block memory buffers */
1564 SCIP_SET* set, /**< global SCIP settings */
1565 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1566 SCIP_STAT* stat, /**< dynamic problem statistics */
1567 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1568 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1569 SCIP_PROB* prob, /**< transformed problem after presolve */
1570 SCIP_PRIMAL* primal, /**< primal data */
1571 SCIP_TREE* tree, /**< branch and bound tree */
1572 SCIP_LP* lp, /**< LP data */
1573 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
1574 SCIP_Bool* mustsepa, /**< pointer to store TRUE if additional separation rounds should be performed */
1575 SCIP_Bool* mustprice /**< pointer to store TRUE if additional pricing rounds should be performed */
1576 )
1577{
1578 assert(lp != NULL);
1579 assert(lperror != NULL);
1580 assert(mustsepa != NULL);
1581 assert(mustprice != NULL);
1582
1583 /* if bound changes were applied in the separation round, we have to resolve the LP */
1584 if( !lp->flushed )
1585 {
1586 /* solve LP (with dual simplex) */
1587 SCIPsetDebugMsg(set, "separation: resolve LP\n");
1588 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, prob, set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
1589 assert(lp->flushed);
1590 assert(lp->solved || *lperror);
1591 *mustsepa = TRUE;
1592 *mustprice = TRUE;
1593
1594 /* remove previous primal ray, store new one if LP is unbounded */
1595 SCIP_CALL( updatePrimalRay(blkmem, set, stat, prob, primal, tree, lp, *lperror) );
1596 }
1597
1598 return SCIP_OKAY;
1599}
1600
1601/** applies one round of LP separation */
1602static
1604 BMS_BLKMEM* blkmem, /**< block memory buffers */
1605 SCIP_SET* set, /**< global SCIP settings */
1606 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1607 SCIP_STAT* stat, /**< dynamic problem statistics */
1608 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1609 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1610 SCIP_PROB* prob, /**< transformed problem after presolve */
1611 SCIP_PRIMAL* primal, /**< primal data */
1612 SCIP_TREE* tree, /**< branch and bound tree */
1613 SCIP_LP* lp, /**< LP data */
1614 SCIP_SEPASTORE* sepastore, /**< separation storage */
1615 int actdepth, /**< current depth in the tree */
1616 SCIP_Real bounddist, /**< current relative distance of local dual bound to global dual bound */
1617 SCIP_Bool allowlocal, /**< should the separators be asked to separate local cuts */
1618 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
1619 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
1620 SCIP_Bool* enoughcuts, /**< pointer to store whether enough cuts have been found this round */
1621 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
1622 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
1623 SCIP_Bool* mustsepa, /**< pointer to store TRUE if additional separation rounds should be performed */
1624 SCIP_Bool* mustprice /**< pointer to store TRUE if additional pricing rounds should be performed */
1625 )
1626{
1628 int i;
1629 SCIP_Bool consadded;
1630 SCIP_Bool root;
1631
1632 assert(set != NULL);
1633 assert(lp != NULL);
1634 assert(set->conshdlrs_sepa != NULL);
1635 assert(delayed != NULL);
1637 assert(cutoff != NULL);
1638 assert(lperror != NULL);
1639
1640 root = (actdepth == 0);
1641 *delayed = FALSE;
1643 *enoughcuts = TRUE;
1645 *enoughcuts = FALSE;
1646 else
1649 *lperror = FALSE;
1650 consadded = FALSE;
1651
1652 SCIPsetDebugMsg(set, "calling separators on LP solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed);
1653
1654 /* sort separators by priority */
1656
1657 /* call LP separators with nonnegative priority */
1658 for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1660 ++i )
1661 {
1662#ifndef NDEBUG
1664#endif
1665
1666 if( SCIPsepaGetPriority(set->sepas[i]) < 0 )
1667 continue;
1668
1669 if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) )
1670 continue;
1671
1672 SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n",
1673 SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i]));
1674 SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) );
1675#ifndef NDEBUG
1677 {
1678 SCIPerrorMessage("Buffer not completely freed after executing separator <%s>\n", SCIPsepaGetName(set->sepas[i]));
1679 SCIPABORT();
1680 }
1681#endif
1682 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1683 consadded = consadded || (result == SCIP_CONSADDED);
1685 *enoughcuts = TRUE;
1688 else
1689 {
1692 || (result == SCIP_NEWROUND);
1693 }
1694 *delayed = *delayed || (result == SCIP_DELAYED);
1695
1696 if( !(*cutoff) )
1697 {
1698 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1699 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1700 }
1701 else
1702 {
1703 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1704 }
1705
1706 /* if we work off the delayed separators, we stop immediately if a cut was found */
1708 {
1709 SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i]));
1710 *delayed = TRUE;
1711 return SCIP_OKAY;
1712 }
1713 }
1714
1715 /* try separating constraints of the constraint handlers */
1716 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1718 ++i )
1719 {
1720 if( onlydelayed && !SCIPconshdlrWasLPSeparationDelayed(set->conshdlrs_sepa[i]) )
1721 continue;
1722
1723 SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n",
1724 SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i]));
1725 SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed,
1726 &result) );
1727
1728 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1729 consadded = consadded || (result == SCIP_CONSADDED);
1731 *enoughcuts = TRUE;
1734 else
1735 {
1738 || (result == SCIP_NEWROUND);
1739 }
1740 *delayed = *delayed || (result == SCIP_DELAYED);
1741
1742 if( !(*cutoff) )
1743 {
1744 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1745 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1746 }
1747 else
1748 {
1749 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1750 }
1751
1752 /* if we work off the delayed separators, we stop immediately if a cut was found */
1754 {
1755 SCIPsetDebugMsg(set, " -> delayed constraint handler <%s> found a cut\n",
1756 SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1757 *delayed = TRUE;
1758 return SCIP_OKAY;
1759 }
1760 }
1761
1762 /* call LP separators with negative priority */
1763 for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1765 ++i )
1766 {
1767 if( SCIPsepaGetPriority(set->sepas[i]) >= 0 )
1768 continue;
1769
1770 if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) )
1771 continue;
1772
1773 SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n",
1774 SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i]));
1775 SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) );
1776
1777 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1778 consadded = consadded || (result == SCIP_CONSADDED);
1780 *enoughcuts = TRUE;
1783 else
1784 {
1787 || (result == SCIP_NEWROUND);
1788 }
1789 *delayed = *delayed || (result == SCIP_DELAYED);
1790
1791 if( !(*cutoff) )
1792 {
1793 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1794 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1795 }
1796 else
1797 {
1798 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1799 }
1800
1801 /* if we work off the delayed separators, we stop immediately if a cut was found */
1803 {
1804 SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i]));
1805 *delayed = TRUE;
1806 return SCIP_OKAY;
1807 }
1808 }
1809
1810 /* process the constraints that were added during this separation round */
1811 while( consadded )
1812 {
1814 consadded = FALSE;
1815
1816 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1818 ++i )
1819 {
1820 SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n",
1821 SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i]));
1822 SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed,
1823 &result) );
1824
1825 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1826 consadded = consadded || (result == SCIP_CONSADDED);
1828 *enoughcuts = TRUE;
1831 else
1832 {
1835 || (result == SCIP_NEWROUND);
1836 }
1837 *delayed = *delayed || (result == SCIP_DELAYED);
1838
1839 if( !(*cutoff) )
1840 {
1841 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1842 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1843 }
1844 else
1845 {
1846 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1847 }
1848 }
1849 }
1850
1851 SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, lpflushed=%u, cutoff=%u\n",
1852 *delayed, *enoughcuts, lp->flushed, *cutoff);
1853
1854 return SCIP_OKAY;
1855}
1856
1857/** applies one round of separation on the given primal solution */
1858static
1860 BMS_BLKMEM* blkmem, /**< block memory buffers */
1861 SCIP_SET* set, /**< global SCIP settings */
1862 SCIP_STAT* stat, /**< dynamic problem statistics */
1863 SCIP_SEPASTORE* sepastore, /**< separation storage */
1864 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
1865 int actdepth, /**< current depth in the tree */
1866 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
1867 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
1868 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
1869 SCIP_Bool* enoughcuts, /**< pointer to store whether enough cuts have been found this round */
1870 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1871 )
1872{
1874 int i;
1875 SCIP_Bool consadded;
1876 SCIP_Bool root;
1877
1878 assert(set != NULL);
1879 assert(set->conshdlrs_sepa != NULL);
1880 assert(delayed != NULL);
1882 assert(cutoff != NULL);
1883
1884 *delayed = FALSE;
1885 *enoughcuts = FALSE;
1886 consadded = FALSE;
1887 root = (actdepth == 0);
1888
1889 SCIPsetDebugMsg(set, "calling separators on primal solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed);
1890
1891 /* sort separators by priority */
1893
1894 /* call separators with nonnegative priority */
1895 for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1896 {
1897 if( SCIPsepaGetPriority(set->sepas[i]) < 0 )
1898 continue;
1899
1900 if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) )
1901 continue;
1902
1903 SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) );
1904 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1905 consadded = consadded || (result == SCIP_CONSADDED);
1907 *enoughcuts = TRUE;
1910 else
1911 {
1914 || (result == SCIP_NEWROUND);
1915 }
1916 *delayed = *delayed || (result == SCIP_DELAYED);
1917 if( *cutoff )
1918 {
1919 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1920 }
1921
1922 /* if we work off the delayed separators, we stop immediately if a cut was found */
1924 {
1925 *delayed = TRUE;
1926 return SCIP_OKAY;
1927 }
1928 }
1929
1930 /* try separating constraints of the constraint handlers */
1931 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1932 {
1933 if( onlydelayed && !SCIPconshdlrWasSolSeparationDelayed(set->conshdlrs_sepa[i]) )
1934 continue;
1935
1936 SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed,
1937 &result) );
1938 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1939 consadded = consadded || (result == SCIP_CONSADDED);
1941 *enoughcuts = TRUE;
1944 else
1945 {
1948 || (result == SCIP_NEWROUND);
1949 }
1950 *delayed = *delayed || (result == SCIP_DELAYED);
1951 if( *cutoff )
1952 {
1953 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n",
1954 SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1955 }
1956
1957 /* if we work off the delayed separators, we stop immediately if a cut was found */
1959 {
1960 *delayed = TRUE;
1961 return SCIP_OKAY;
1962 }
1963 }
1964
1965 /* call separators with negative priority */
1966 for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1967 {
1968 if( SCIPsepaGetPriority(set->sepas[i]) >= 0 )
1969 continue;
1970
1971 if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) )
1972 continue;
1973
1974 SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) );
1975 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1976 consadded = consadded || (result == SCIP_CONSADDED);
1978 *enoughcuts = TRUE;
1981 else
1982 {
1985 || (result == SCIP_NEWROUND);
1986 }
1987 *delayed = *delayed || (result == SCIP_DELAYED);
1988 if( *cutoff )
1989 {
1990 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1991 }
1992
1993 /* if we work off the delayed separators, we stop immediately if a cut was found */
1995 {
1996 *delayed = TRUE;
1997 return SCIP_OKAY;
1998 }
1999 }
2000
2001 /* process the constraints that were added during this separation round */
2002 while( consadded )
2003 {
2005 consadded = FALSE;
2006
2007 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
2008 {
2009 SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed, &result) );
2010 *cutoff = *cutoff || (result == SCIP_CUTOFF);
2011 consadded = consadded || (result == SCIP_CONSADDED);
2013 *enoughcuts = TRUE;
2016 else
2017 {
2020 || (result == SCIP_NEWROUND);
2021 }
2022 *delayed = *delayed || (result == SCIP_DELAYED);
2023 if( *cutoff )
2024 {
2025 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n",
2026 SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
2027 }
2028 }
2029 }
2030
2031 SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, cutoff=%u\n",
2033
2034 return SCIP_OKAY;
2035}
2036
2037/** applies one round of separation on the given primal solution or on the LP solution */
2039 BMS_BLKMEM* blkmem, /**< block memory buffers */
2040 SCIP_SET* set, /**< global SCIP settings */
2041 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2042 SCIP_STAT* stat, /**< dynamic problem statistics */
2043 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2044 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
2045 SCIP_PROB* prob, /**< transformed problem after presolve */
2046 SCIP_PRIMAL* primal, /**< primal data */
2047 SCIP_TREE* tree, /**< branch and bound tree */
2048 SCIP_LP* lp, /**< LP data */
2049 SCIP_SEPASTORE* sepastore, /**< separation storage */
2050 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
2051 int actdepth, /**< current depth in the tree */
2052 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
2053 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
2054 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
2055 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
2056 )
2057{
2058 SCIP_Bool enoughcuts;
2059
2060 assert(delayed != NULL);
2061 assert(cutoff != NULL);
2062
2063 *delayed = FALSE;
2064 *cutoff = FALSE;
2065 enoughcuts = FALSE;
2066
2067 if( sol == NULL )
2068 {
2069 SCIP_Bool lperror;
2070 SCIP_Bool mustsepa;
2071 SCIP_Bool mustprice;
2072
2073 /* apply a separation round on the LP solution */
2074 lperror = FALSE;
2075 mustsepa = FALSE;
2076 mustprice = FALSE;
2077 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, sepastore, \
2078 actdepth, 0.0, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff, \
2079 &lperror, &mustsepa, &mustprice) );
2080 }
2081 else
2082 {
2083 /* apply a separation round on the given primal solution */
2084 SCIP_CALL( separationRoundSol(blkmem, set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff) );
2085 }
2086
2087 return SCIP_OKAY;
2088}
2089
2090/** solves the current LP completely with pricing in new variables */
2092 BMS_BLKMEM* blkmem, /**< block memory buffers */
2093 SCIP_SET* set, /**< global SCIP settings */
2094 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2095 SCIP_STAT* stat, /**< dynamic problem statistics */
2096 SCIP_PROB* transprob, /**< transformed problem */
2097 SCIP_PROB* origprob, /**< original problem */
2098 SCIP_PRIMAL* primal, /**< primal data */
2099 SCIP_TREE* tree, /**< branch and bound tree */
2100 SCIP_REOPT* reopt, /**< reoptimization data structure */
2101 SCIP_LP* lp, /**< LP data */
2102 SCIP_PRICESTORE* pricestore, /**< pricing storage */
2103 SCIP_SEPASTORE* sepastore, /**< separation storage */
2104 SCIP_CUTPOOL* cutpool, /**< global cutpool */
2105 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2106 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2107 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
2108 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2109 SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */
2110 SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */
2111 int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit);
2112 * a finite limit means that the LP might not be solved to optimality! */
2113 int* npricedcolvars, /**< pointer to store number of column variables after problem vars were priced */
2114 SCIP_Bool* mustsepa, /**< pointer to store TRUE if a separation round should follow */
2115 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
2116 SCIP_Bool* aborted /**< pointer to store whether the pricing was aborted and the lower bound must
2117 * not be used */
2118 )
2119{
2120 SCIP_NODE* currentnode;
2121 int npricerounds;
2122 SCIP_Bool mustprice;
2123 SCIP_Bool cutoff;
2124 SCIP_Bool unbounded;
2125
2126 assert(transprob != NULL);
2127 assert(lp != NULL);
2128 assert(lp->flushed);
2129 assert(lp->solved);
2131 assert(mustsepa != NULL);
2132 assert(lperror != NULL);
2133 assert(aborted != NULL);
2134
2135 currentnode = SCIPtreeGetCurrentNode(tree);
2136 assert(currentnode == SCIPtreeGetFocusNode(tree) || SCIPtreeProbing(tree));
2137 *npricedcolvars = transprob->ncolvars;
2138 *lperror = FALSE;
2139 *aborted = FALSE;
2140
2141 /* if the LP is unbounded, we don't need to price */
2145
2146 /* if all the variables are already in the LP, we don't need to price */
2147 mustprice = mustprice && !SCIPprobAllColsInLP(transprob, set, lp);
2148
2149 /* check if infinite number of pricing rounds should be used */
2150 if( maxpricerounds == -1 )
2152
2153 /* pricing (has to be done completely to get a valid lower bound) */
2154 npricerounds = 0;
2155 while( !(*lperror) && mustprice && npricerounds < maxpricerounds )
2156 {
2157 SCIP_Bool enoughvars;
2159 SCIP_Real lb;
2160 SCIP_Bool foundsol;
2161 SCIP_Bool stopearly;
2162 SCIP_Bool stoppricing;
2163 int p;
2164
2165 assert(lp->flushed);
2166 assert(lp->solved);
2168
2169 /* check if pricing loop should be aborted */
2170 if( SCIPsolveIsStopped(set, stat, FALSE) )
2171 {
2172 /* do not print the warning message if we stopped because the problem is solved */
2174 SCIPmessagePrintWarning(messagehdlr, "pricing has been interrupted -- LP of current node is invalid\n");
2175
2176 *aborted = TRUE;
2177 break;
2178 }
2179
2180 /* call primal heuristics which are callable during pricing */
2181 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGPRICINGLOOP,
2182 FALSE, &foundsol, &unbounded) );
2183
2184 /* price problem variables */
2185 SCIPsetDebugMsg(set, "problem variable pricing\n");
2186 assert(SCIPpricestoreGetNVars(pricestore) == 0);
2187 assert(SCIPpricestoreGetNBoundResets(pricestore) == 0);
2188 SCIP_CALL( SCIPpricestoreAddProbVars(pricestore, blkmem, set, stat, transprob, tree, lp, branchcand, eventqueue) );
2189 *npricedcolvars = transprob->ncolvars;
2190
2191 /* call external pricers to create additional problem variables */
2192 SCIPsetDebugMsg(set, "external variable pricing\n");
2193
2194 /* sort pricer algorithms by priority */
2196
2197 /* call external pricer algorithms, that are active for the current problem */
2201 for( p = 0; p < set->nactivepricers && !enoughvars; ++p )
2202 {
2203 SCIP_CALL( SCIPpricerExec(set->pricers[p], set, transprob, lp, pricestore, &lb, &stopearly, &result) );
2205 SCIPsetDebugMsg(set, "pricing: pricer %s returned result = %s, lowerbound = %f\n",
2206 SCIPpricerGetName(set->pricers[p]), (result == SCIP_DIDNOTRUN ? "didnotrun" : "success"), lb);
2209 *aborted = ( (*aborted) || (result == SCIP_DIDNOTRUN) );
2210
2211 /* set stoppricing to TRUE, if the first pricer wants to stop pricing */
2212 if( p == 0 && stopearly )
2213 stoppricing = TRUE;
2214
2215 /* stoppricing only remains TRUE, if all other pricers want to stop pricing as well */
2216 if( stoppricing && !stopearly )
2218
2219 /* update lower bound w.r.t. the lower bound given by the pricer */
2220 SCIPnodeUpdateLowerbound(currentnode, stat, set, tree, transprob, origprob, lb);
2221 SCIPsetDebugMsg(set, " -> new lower bound given by pricer %s: %g\n", SCIPpricerGetName(set->pricers[p]), lb);
2222 }
2223
2224 /* apply the priced variables to the LP */
2225 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) );
2226 assert(SCIPpricestoreGetNVars(pricestore) == 0);
2227 assert(!lp->flushed || lp->solved);
2228 mustprice = !lp->flushed || (transprob->ncolvars != *npricedcolvars);
2229 *mustsepa = *mustsepa || !lp->flushed;
2230
2231 /* after adding columns, the LP should be primal feasible such that the primal simplex is applicable;
2232 * if LP was infeasible, we have to use dual simplex
2233 */
2234 SCIPsetDebugMsg(set, "pricing: solve LP\n");
2235 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, TRUE, FALSE, lperror) );
2236 assert(lp->flushed);
2237 assert(lp->solved || *lperror);
2238
2239 /* reset bounds temporarily set by pricer to their original values */
2240 SCIPsetDebugMsg(set, "pricing: reset bounds\n");
2241 SCIP_CALL( SCIPpricestoreResetBounds(pricestore, blkmem, set, stat, lp, branchcand, eventqueue) );
2242 assert(SCIPpricestoreGetNVars(pricestore) == 0);
2243 assert(SCIPpricestoreGetNBoundResets(pricestore) == 0);
2244 assert(!lp->flushed || lp->solved || *lperror);
2245
2246 /* put all initial constraints into the LP */
2247 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2248 eventfilter, cliquetable, FALSE, FALSE, &cutoff) );
2249 assert(cutoff == FALSE);
2250
2251 mustprice = mustprice || !lp->flushed || (transprob->ncolvars != *npricedcolvars);
2252 *mustsepa = *mustsepa || !lp->flushed;
2253
2254 /* if all pricers wanted to stop pricing, do not do another pricing round (LP value is no valid dual bound in this case) */
2255 if( stoppricing )
2256 {
2257 SCIPsetDebugMsg(set, "pricing: stop pricing and perform early branching\n");
2258 mustprice = FALSE;
2259 *aborted = TRUE;
2260 }
2261
2262 /* solve LP again after resetting bounds and adding new initial constraints (with dual simplex) */
2263 SCIPsetDebugMsg(set, "pricing: solve LP after resetting bounds and adding new initial constraints\n");
2264 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) );
2265 assert(lp->flushed);
2266 assert(lp->solved || *lperror);
2267
2268 /* remove previous primal ray, store new one if LP is unbounded */
2269 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2270
2271 /* increase pricing round counter */
2272 stat->npricerounds++;
2273 npricerounds++;
2274
2275 /* display node information line */
2276 if( displayinfo && mustprice )
2277 {
2278 if( (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_FULL
2279 || ((SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH && npricerounds % 100 == 1) )
2280 {
2281 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
2282 }
2283 }
2284
2285 /* if the LP is unbounded, we can stop pricing */
2286 mustprice = mustprice &&
2290
2291 /* if the lower bound is already higher than the cutoff bound, we can stop pricing */
2293 } /*lint !e438*/
2294 assert(lp->flushed);
2295 assert(lp->solved || *lperror);
2296
2297 *aborted = ( (*aborted) || (*lperror) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_NOTSOLVED
2298 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ERROR || npricerounds == maxpricerounds );
2299
2300 /* set information, whether the current lp is a valid relaxation of the current problem */
2301 SCIPlpSetIsRelax(lp, !(*aborted));
2302
2303 return SCIP_OKAY; /*lint !e438*/
2304}
2305
2306/** separates cuts of the cut pool */
2307static
2309 SCIP_CUTPOOL* cutpool, /**< cut pool */
2310 BMS_BLKMEM* blkmem, /**< block memory */
2311 SCIP_SET* set, /**< global SCIP settings */
2312 SCIP_STAT* stat, /**< problem statistics data */
2313 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2314 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
2315 SCIP_LP* lp, /**< current LP data */
2316 SCIP_SEPASTORE* sepastore, /**< separation storage */
2317 SCIP_Bool cutpoolisdelayed, /**< is the cutpool delayed (count cuts found)? */
2318 SCIP_Bool root, /**< are we at the root node? */
2319 int actdepth, /**< the depth of the focus node */
2320 SCIP_Bool* enoughcuts, /**< pointer to store if enough cuts were found in current separation round */
2321 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
2322 )
2323{
2324 if( (set->sepa_poolfreq == 0 && actdepth == 0)
2325 || (set->sepa_poolfreq > 0 && actdepth % set->sepa_poolfreq == 0) )
2326 {
2328
2329 SCIP_CALL( SCIPcutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, NULL, cutpoolisdelayed, root, &result) );
2330 *cutoff = *cutoff || (result == SCIP_CUTOFF);
2332 *enoughcuts = TRUE;
2335 else
2336 {
2339 || (result == SCIP_NEWROUND);
2340 }
2341 }
2342
2343 return SCIP_OKAY;
2344}
2345
2346/** solve the current LP of a node with a price-and-cut loop */
2347static
2349 BMS_BLKMEM* blkmem, /**< block memory buffers */
2350 SCIP_SET* set, /**< global SCIP settings */
2351 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2352 SCIP_STAT* stat, /**< dynamic problem statistics */
2353 SCIP_MEM* mem, /**< block memory pools */
2354 SCIP_PROB* transprob, /**< transformed problem */
2355 SCIP_PROB* origprob, /**< original problem */
2356 SCIP_PRIMAL* primal, /**< primal data */
2357 SCIP_TREE* tree, /**< branch and bound tree */
2358 SCIP_REOPT* reopt, /**< reoptimization data structure */
2359 SCIP_LP* lp, /**< LP data */
2360 SCIP_PRICESTORE* pricestore, /**< pricing storage */
2361 SCIP_SEPASTORE* sepastore, /**< separation storage */
2362 SCIP_CUTPOOL* cutpool, /**< global cut pool */
2363 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
2364 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2365 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2366 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2367 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
2368 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2369 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2370 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
2371 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
2372 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
2373 SCIP_Bool* unbounded, /**< pointer to store whether an unbounded ray was found in the LP */
2374 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
2375 SCIP_Bool* pricingaborted /**< pointer to store whether the pricing was aborted and the lower bound must
2376 * not be used */
2377 )
2378{
2379 SCIP_NODE* focusnode;
2380 /* cppcheck-suppress unassignedVariable */
2383 SCIP_Real loclowerbound;
2384 SCIP_Real glblowerbound;
2385 SCIP_Real bounddist;
2386 SCIP_Real stalllpobjval;
2387 SCIP_Bool separate;
2388 SCIP_Bool mustprice;
2389 SCIP_Bool mustsepa;
2390 SCIP_Bool delayedsepa;
2391 SCIP_Bool root;
2392 SCIP_Bool allowlocal;
2393 int maxseparounds;
2394 int nsepastallrounds;
2396 int stallnfracs;
2397 int actdepth;
2398 int npricedcolvars;
2399
2400 assert(set != NULL);
2401 assert(blkmem != NULL);
2402 assert(stat != NULL);
2403 assert(transprob != NULL);
2404 assert(tree != NULL);
2405 assert(lp != NULL);
2406 assert(pricestore != NULL);
2407 assert(sepastore != NULL);
2408 assert(cutpool != NULL);
2409 assert(delayedcutpool != NULL);
2410 assert(primal != NULL);
2411 assert(cutoff != NULL);
2412 assert(unbounded != NULL);
2413 assert(lperror != NULL);
2414
2415 focusnode = SCIPtreeGetFocusNode(tree);
2416 assert(focusnode != NULL);
2418 actdepth = SCIPnodeGetDepth(focusnode);
2419 root = (actdepth == 0);
2420
2421 /* check, if we want to separate at this node */
2424 assert(primal->cutoffbound > glblowerbound);
2425 bounddist = (loclowerbound - glblowerbound)/(primal->cutoffbound - glblowerbound);
2426 allowlocal = SCIPsetIsLE(set, bounddist, set->sepa_maxlocalbounddist);
2427 separate = (set->sepa_maxruns == -1 || stat->nruns < set->sepa_maxruns);
2428
2429 /* get maximal number of separation rounds */
2430 maxseparounds = (root ? set->sepa_maxroundsroot : set->sepa_maxrounds);
2431 if( maxseparounds == -1 )
2432 maxseparounds = INT_MAX;
2433 if( stat->nruns > 1 && root && set->sepa_maxroundsrootsubrun >= 0 )
2434 maxseparounds = MIN(maxseparounds, set->sepa_maxroundsrootsubrun);
2435 if( !fullseparation && set->sepa_maxaddrounds >= 0 )
2436 maxseparounds = MIN(maxseparounds, stat->nseparounds + set->sepa_maxaddrounds);
2437 maxnsepastallrounds = root ? set->sepa_maxstallroundsroot : set->sepa_maxstallrounds;
2438 if( maxnsepastallrounds == -1 )
2440
2441 /* solve initial LP of price-and-cut loop */
2442 SCIPsetDebugMsg(set, "node: solve LP with price and cut\n");
2443 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2444 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2445 assert(lp->flushed);
2446 assert(lp->solved || *lperror);
2447
2448 /* remove previous primal ray, store new one if LP is unbounded */
2449 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2450
2451 /* price-and-cut loop */
2452 npricedcolvars = transprob->ncolvars;
2453 mustprice = TRUE;
2454 mustsepa = separate;
2456 *cutoff = FALSE;
2458 nsepastallrounds = 0;
2462 lp->installing = FALSE;
2463 while( !(*cutoff) && !(*unbounded) && !(*lperror) && (mustprice || mustsepa || delayedsepa) )
2464 {
2465 SCIPsetDebugMsg(set, "-------- node solving loop --------\n");
2466 assert(lp->flushed);
2467 assert(lp->solved);
2468
2469 /* solve the LP with pricing in new variables */
2470 while( mustprice && !(*lperror) )
2471 {
2472 SCIP_CALL( SCIPpriceLoop(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
2473 pricestore, sepastore, cutpool, branchcand, eventqueue, eventfilter, cliquetable, root, root, -1, &npricedcolvars,
2475
2476 mustprice = FALSE;
2477
2478 assert(lp->flushed);
2479 assert(lp->solved || *lperror);
2480
2481 /* update lower bound w.r.t. the LP solution */
2482 if( !(*lperror) && !(*pricingaborted) && SCIPlpIsRelax(lp) )
2483 {
2484 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2485 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2486 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2487
2488 /* update node estimate */
2489 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2490
2491 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2492 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2493 }
2494 else
2495 {
2496 SCIPsetDebugMsg(set, " -> error solving LP or pricing aborted. keeping old bound: %g\n", SCIPnodeGetLowerbound(focusnode));
2497 }
2498
2499 /* display node information line for root node */
2500 if( root && (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH )
2501 {
2502 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
2503 }
2504
2505 if( !(*lperror) )
2506 {
2507 /* call propagators that are applicable during LP solving loop only if the node is not cut off */
2508 if( SCIPsetIsLT(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound) )
2509 {
2510 SCIP_Longint oldnboundchgs;
2511 SCIP_Longint oldninitconssadded;
2512 SCIP_Bool postpone;
2513
2514 oldnboundchgs = stat->nboundchgs;
2516
2517 SCIPsetDebugMsg(set, " -> LP solved: call propagators that are applicable during LP solving loop\n");
2518
2519 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, FALSE,
2522 assert(!postpone);
2523
2524 if( stat->ninitconssadded != oldninitconssadded )
2525 {
2526 SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n", oldninitconssadded, stat->ninitconssadded);
2527
2528 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2529 branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2530 }
2531
2532 if( !(*cutoff) && !(*unbounded) )
2533 {
2534 /* if we found something, solve LP again */
2535 if( !lp->flushed )
2536 {
2537 SCIPsetDebugMsg(set, " -> found reduction: resolve LP\n");
2538
2539 /* in the root node, remove redundant rows permanently from the LP */
2540 if( root )
2541 {
2542 SCIP_CALL( SCIPlpFlush(lp, blkmem, set, transprob, eventqueue) );
2543 SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2544 }
2545
2546 /* resolve LP */
2547 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2548 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2549 assert(lp->flushed);
2550 assert(lp->solved || *lperror);
2551
2552 /* remove previous primal ray, store new one if LP is unbounded */
2553 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2554
2555 mustprice = TRUE;
2557 }
2558 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective
2559 * value which is added to the LP value; because of the loose status, the LP might not be reoptimized,
2560 * but the lower bound of the node needs to be updated
2561 */
2562 else if( stat->nboundchgs > oldnboundchgs )
2563 {
2565
2566 if( lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2567 {
2568 assert(lp->flushed);
2569 assert(lp->solved);
2570
2571 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2572 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2573 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2574
2575 /* update node estimate */
2576 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2577
2578 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2579 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2580 }
2581 }
2582 }
2583 }
2584 }
2585
2586 /* call primal heuristics that are applicable during node LP solving loop */
2588 {
2589 SCIP_Bool foundsol;
2590
2591 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGLPLOOP,
2592 FALSE, &foundsol, unbounded) );
2594
2595 *lperror = *lperror || lp->resolvelperror;
2596 } /*lint !e438*/
2597 }
2598 assert(lp->flushed || *cutoff || *unbounded);
2599 assert(lp->solved || *lperror || *cutoff || *unbounded);
2600
2601 /* check, if we exceeded the separation round limit */
2603 && stat->nseparounds < maxseparounds
2605 && !(*cutoff);
2606
2607 /* if separators were delayed, we want to apply a final separation round with the delayed separators */
2608 delayedsepa = delayedsepa && !mustsepa && !(*cutoff); /* if regular separation applies, we ignore delayed separators */
2610
2611 if( mustsepa )
2612 {
2613 /* if the LP is infeasible, unbounded, exceeded the objective limit or a global performance limit was reached,
2614 * we don't need to separate cuts
2615 * (the global limits are only checked at the root node in order to not query system time too often)
2616 */
2617 if( !separate || (*cutoff) || (*unbounded)
2619 || SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)
2620 || (root && SCIPsolveIsStopped(set, stat, FALSE)) )
2621 {
2622 mustsepa = FALSE;
2624 }
2625 else
2626 assert(!(*lperror));
2627 }
2628
2629 /* separation (needs not to be done completely, because we just want to increase the lower bound) */
2630 if( mustsepa )
2631 {
2632 SCIP_Longint olddomchgcount;
2633 SCIP_Longint oldninitconssadded;
2634 SCIP_Bool enoughcuts;
2635
2636 assert(lp->flushed);
2637 assert(lp->solved);
2639 assert(!(*lperror));
2640 assert(!(*cutoff));
2641
2644
2645 mustsepa = FALSE;
2647
2648 /* global cut pool separation */
2649 if( !enoughcuts && !delayedsepa )
2650 {
2651 SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2653
2654 if( *cutoff )
2655 {
2656 SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2657 }
2658 }
2659 assert(lp->flushed);
2660 assert(lp->solved);
2662 assert(!(*lperror));
2663
2664 /* separate constraints and LP */
2665 if( !(*cutoff) && !enoughcuts )
2666 {
2667 /* constraint and LP separation */
2668 SCIPsetDebugMsg(set, "constraint and LP separation\n");
2669
2670 /* apply a separation round */
2671 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal, tree,
2672 lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2675
2676 /* if we are close to the stall round limit, also call the delayed separators */
2677 if( !(*cutoff) && !(*lperror) && !enoughcuts && lp->solved
2680 {
2681 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal,
2682 tree, lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2685 }
2686 }
2687
2688 /* call global cut pool separation again since separators may add cuts to the pool instead of the sepastore */
2689 if( !(*cutoff) && !(*lperror) && lp->solved && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && !enoughcuts )
2690 {
2691 SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2693
2694 if( *cutoff )
2695 {
2696 SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2697 }
2698 }
2699
2700 /* delayed global cut pool separation */
2701 if( !(*cutoff) && !(*lperror) && lp->solved && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && SCIPsepastoreGetNCuts(sepastore) == 0 && !enoughcuts )
2702 {
2703 SCIP_CALL( cutpoolSeparate(delayedcutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, TRUE,
2704 root, actdepth, &enoughcuts, cutoff) );
2705
2706 if( *cutoff )
2707 {
2708 SCIPsetDebugMsg(set, " -> delayed global cut pool detected cutoff\n");
2709 }
2710 assert(lp->solved);
2712 assert(lp->flushed);
2713 }
2714
2715 /* delayed separation if no cuts where produced */
2716 if( !(*cutoff) && !(*lperror) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && SCIPsepastoreGetNCuts(sepastore) == 0 && delayedsepa )
2717 {
2718 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal,
2719 tree, lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2722
2723 /* call delayed cut pool separation again, since separators may add cuts to the pool instead of the sepastore */
2725 {
2726 assert( !(*lperror) );
2727
2728 SCIP_CALL( cutpoolSeparate(delayedcutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, TRUE,
2729 root, actdepth, &enoughcuts, cutoff) );
2730
2731 if( *cutoff )
2732 {
2733 SCIPsetDebugMsg(set, " -> delayed global cut pool detected cutoff\n");
2734 }
2736 assert(lp->flushed);
2737 assert(lp->solved);
2738 }
2739 }
2740
2741 assert(*cutoff || *lperror || SCIPlpIsSolved(lp));
2749
2750 if( *cutoff || *lperror
2753 {
2754 /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
2755 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
2756 }
2757 else
2758 {
2759 /* apply found cuts */
2760 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2761 branchcand, eventqueue, eventfilter, cliquetable, root, SCIP_EFFICIACYCHOICE_LP, cutoff) );
2762
2763 if( !(*cutoff) )
2764 {
2765 mustprice = mustprice || !lp->flushed || (transprob->ncolvars != npricedcolvars);
2766 mustsepa = mustsepa || !lp->flushed;
2767
2768 /* if a new bound change (e.g. a cut with only one column) was found, propagate domains again */
2769 if( stat->domchgcount != olddomchgcount )
2770 {
2771 SCIPsetDebugMsg(set, " -> separation changed bound: propagate again\n");
2772
2774
2775 /* in the root node, remove redundant rows permanently from the LP */
2776 if( root )
2777 {
2778 SCIP_CALL( SCIPlpFlush(lp, blkmem, set, transprob, eventqueue) );
2779 SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2780 }
2781 }
2782
2783 if( stat->ninitconssadded != oldninitconssadded )
2784 {
2785 SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n",
2787
2788 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2789 branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2790 }
2791
2792 if( !(*cutoff) )
2793 {
2794 SCIP_Real lpobjval;
2795
2796 /* solve LP (with dual simplex) */
2797 SCIPsetDebugMsg(set, "separation: solve LP\n");
2798 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2799 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2800 assert(lp->flushed);
2801 assert(lp->solved || *lperror);
2802
2803 /* remove previous primal ray, store new one if LP is unbounded */
2804 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2805
2806 if( !(*lperror) )
2807 {
2808 SCIP_Bool stalling;
2809
2810 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
2811 * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
2812 * bound of the node needs to be updated
2813 */
2814 if( stat->domchgcount != olddomchgcount && (!mustprice || mustsepa) && !(*cutoff)
2815 && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2816 {
2817 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2818 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2819 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2820
2821 /* update node estimate */
2822 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2823
2824 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2825 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2826 }
2827
2828 /* check if we are stalling
2829 * If we have an LP solution, then we are stalling if
2830 * we had an LP solution before and
2831 * the LP value did not improve and
2832 * the number of fractional variables did not decrease.
2833 * If we do not have an LP solution, then we are stalling if the solution status of the LP did not change.
2834 */
2836 {
2837 SCIP_Real objreldiff;
2838 int nfracs;
2839
2840 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nfracs, NULL,
2841 NULL) );
2842 lpobjval = SCIPlpGetObjval(lp, set, transprob);
2843
2845 SCIPsetDebugMsg(set, " -> LP bound moved from %g to %g (reldiff: %g)\n",
2846 stalllpobjval, lpobjval, objreldiff);
2847
2849 objreldiff <= 1e-04 &&
2850 nfracs >= (0.9 - 0.1 * nsepastallrounds) * stallnfracs);
2851
2852 stalllpobjval = lpobjval;
2854 } /*lint !e438*/
2855 else
2856 {
2858 }
2859
2860 if( !stalling )
2861 {
2862 nsepastallrounds = 0;
2863 lp->installing = FALSE;
2864 }
2865 else
2866 {
2868 }
2870
2871 /* tell LP that we are (close to) stalling */
2873 lp->installing = TRUE;
2874 SCIPsetDebugMsg(set, " -> nsepastallrounds=%d/%d\n", nsepastallrounds, maxnsepastallrounds);
2875 }
2876 }
2877 }
2878 }
2879 assert(*cutoff || *lperror || (lp->flushed && lp->solved)); /* cutoff: LP may be unsolved due to bound changes */
2880
2881 SCIPsetDebugMsg(set, "separation round %d/%d finished (%d/%d stall rounds): mustprice=%u, mustsepa=%u, delayedsepa=%u, propagateagain=%u\n",
2883
2884 /* increase separation round counter */
2885 stat->nseparounds++;
2886 }
2887 }
2888
2889 if( root && nsepastallrounds >= maxnsepastallrounds )
2890 {
2891 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
2892 "Truncate separation round because of stalling (%d stall rounds).\n", maxnsepastallrounds);
2893 }
2894
2895 if( !*lperror )
2896 {
2897 /* update pseudo cost values for continuous variables, if it should be delayed */
2898 SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, FALSE, set->branch_delaypscost) );
2899 }
2900
2901 /* update lower bound w.r.t. the LP solution */
2902 if( *cutoff )
2903 {
2904 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
2905 }
2906 else if( !(*lperror) )
2907 {
2908 assert(lp->flushed);
2909 assert(lp->solved);
2910
2911 if( SCIPlpIsRelax(lp) )
2912 {
2913 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2914 }
2915
2916 /* update node estimate */
2917 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2918
2919 /* issue LPSOLVED event */
2921 {
2923 SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
2924 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
2925 }
2926
2927 /* if the LP is a relaxation and we are not solving exactly, then we may analyze an infeasible or bound exceeding
2928 * LP (not necessary in the root node) and cut off the current node
2929 */
2930 if( !set->misc_exactsolve && !root && SCIPlpIsRelax(lp) && SCIPprobAllColsInLP(transprob, set, lp)
2932 {
2933 SCIP_CALL( SCIPconflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt,
2934 lp, branchcand, eventqueue, cliquetable, NULL) );
2935 *cutoff = TRUE;
2936 }
2937 }
2938 /* check for unboundedness */
2939 if( !(*lperror) )
2940 {
2942 /* assert(!(*unbounded) || root); */ /* unboundedness can only happen in the root node; no, of course it can also happens in the tree if a branching did not help to resolve unboundedness */
2943 }
2944
2945 lp->installing = FALSE;
2946
2947 SCIPsetDebugMsg(set, " -> final lower bound: %g (LP status: %d, LP obj: %g)\n",
2949 (*cutoff || *unbounded) ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
2950
2951 return SCIP_OKAY; /*lint !e438*/
2952}
2953
2954/** updates the current lower bound with the pseudo objective value, cuts off node by bounding, and applies conflict
2955 * analysis if the pseudo objective lead to the cutoff
2956 */
2957static
2959 BMS_BLKMEM* blkmem, /**< block memory buffers */
2960 SCIP_SET* set, /**< global SCIP settings */
2961 SCIP_STAT* stat, /**< dynamic problem statistics */
2962 SCIP_PROB* transprob, /**< tranformed problem after presolve */
2963 SCIP_PROB* origprob, /**< original problem */
2964 SCIP_PRIMAL* primal, /**< primal data */
2965 SCIP_TREE* tree, /**< branch and bound tree */
2966 SCIP_REOPT* reopt, /**< reoptimization data structure */
2967 SCIP_LP* lp, /**< LP data */
2968 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2969 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2970 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2971 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2972 SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
2973 )
2974{
2975 assert(transprob != NULL);
2976 assert(origprob != NULL);
2977 assert(primal != NULL);
2978 assert(cutoff != NULL);
2979
2980 if( !(*cutoff) )
2981 {
2982 SCIP_NODE* focusnode;
2983 SCIP_Real pseudoobjval;
2984
2985 /* get current focus node */
2986 focusnode = SCIPtreeGetFocusNode(tree);
2987
2988 /* update lower bound w.r.t. the pseudo solution */
2989 pseudoobjval = SCIPlpGetPseudoObjval(lp, set, transprob);
2990 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, pseudoobjval);
2991 SCIPsetDebugMsg(set, " -> lower bound: %g [%g] (pseudoobj: %g [%g]), cutoff bound: %g [%g]\n",
2992 SCIPnodeGetLowerbound(focusnode), SCIPprobExternObjval(transprob, origprob, set, SCIPnodeGetLowerbound(focusnode)) + SCIPgetOrigObjoffset(set->scip),
2993 pseudoobjval, SCIPprobExternObjval(transprob, origprob, set, pseudoobjval) + SCIPgetOrigObjoffset(set->scip),
2994 primal->cutoffbound, SCIPprobExternObjval(transprob, origprob, set, primal->cutoffbound) + SCIPgetOrigObjoffset(set->scip));
2995
2996 /* check for infeasible node by bounding */
2997 if( (set->misc_exactsolve && SCIPnodeGetLowerbound(focusnode) >= primal->cutoffbound)
2998 || (!set->misc_exactsolve && SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)) )
2999 {
3000 SCIPsetDebugMsg(set, "node is cut off by bounding (lower=%g, upper=%g)\n",
3001 SCIPnodeGetLowerbound(focusnode), primal->cutoffbound);
3002 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
3003 *cutoff = TRUE;
3004
3005 /* call pseudo conflict analysis, if the node is cut off due to the pseudo objective value */
3006 if( pseudoobjval >= primal->cutoffbound && !SCIPsetIsInfinity(set, primal->cutoffbound) && !SCIPsetIsInfinity(set, -pseudoobjval) )
3007 {
3008 SCIP_CALL( SCIPconflictAnalyzePseudo(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, NULL) );
3009 }
3010 }
3011 }
3012
3013 return SCIP_OKAY;
3014}
3015
3016/** marks all relaxators to be unsolved */
3017static
3019 SCIP_SET* set, /**< global SCIP settings */
3020 SCIP_RELAXATION* relaxation /**< global relaxation data */
3021 )
3022{
3023 int r;
3024
3025 assert(set != NULL);
3026 assert(relaxation != NULL);
3027
3029
3030 for( r = 0; r < set->nrelaxs; ++r )
3031 SCIPrelaxMarkUnsolved(set->relaxs[r]);
3032}
3033
3034/** solves the current node's LP in a price-and-cut loop */
3035static
3037 BMS_BLKMEM* blkmem, /**< block memory buffers */
3038 SCIP_SET* set, /**< global SCIP settings */
3039 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3040 SCIP_STAT* stat, /**< dynamic problem statistics */
3041 SCIP_MEM* mem, /**< block memory pools */
3042 SCIP_PROB* origprob, /**< original problem */
3043 SCIP_PROB* transprob, /**< transformed problem after presolve */
3044 SCIP_PRIMAL* primal, /**< primal data */
3045 SCIP_TREE* tree, /**< branch and bound tree */
3046 SCIP_REOPT* reopt, /**< reoptimization data structure */
3047 SCIP_LP* lp, /**< LP data */
3048 SCIP_RELAXATION* relaxation, /**< relaxators */
3049 SCIP_PRICESTORE* pricestore, /**< pricing storage */
3050 SCIP_SEPASTORE* sepastore, /**< separation storage */
3051 SCIP_CUTPOOL* cutpool, /**< global cut pool */
3052 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
3053 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3054 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3055 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
3056 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3057 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3058 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3059 SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
3060 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
3061 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
3062 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
3063 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
3064 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3065 SCIP_Bool* unbounded, /**< pointer to store TRUE, if an unbounded ray was found in the LP */
3066 SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
3067 SCIP_Bool* pricingaborted /**< pointer to store TRUE, if the pricing was aborted and the lower bound
3068 * must not be used */
3069 )
3070{
3071 SCIP_Longint nlpiterations;
3072 SCIP_Longint nlps;
3073 SCIP_Longint nzeroitlps;
3074
3075 assert(stat != NULL);
3076 assert(tree != NULL);
3078 assert(cutoff != NULL);
3079 assert(unbounded != NULL);
3080 assert(lperror != NULL);
3081 assert(*cutoff == FALSE);
3082 assert(*unbounded == FALSE);
3083 assert(*lperror == FALSE);
3084
3085 nlps = stat->nlps;
3088
3089 if( !initiallpsolved )
3090 {
3091 /* load and solve the initial LP of the node */
3092 SCIP_CALL( solveNodeInitialLP(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
3093 pricestore, sepastore, cutpool, branchcand, eventfilter, eventqueue, cliquetable, newinitconss, cutoff, lperror) );
3094
3095 assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3096 SCIPsetDebugMsg(set, "price-and-cut-loop: initial LP status: %d, LP obj: %g\n",
3097 SCIPlpGetSolstat(lp),
3099
3100 /* update initial LP iteration counter */
3101 stat->ninitlps += stat->nlps - nlps;
3103
3104 /* In the root node, we try if the initial LP solution is feasible to avoid expensive setup of data structures in
3105 * separators; in case the root LP is aborted, e.g., by hitting the time limit, we do not check the LP solution
3106 * since the corresponding data structures have not been updated.
3107 */
3108 if( SCIPtreeGetCurrentDepth(tree) == 0 && !(*cutoff) && !(*lperror)
3110 && !SCIPsolveIsStopped(set, stat, FALSE) )
3111 {
3112 SCIP_Bool checklprows;
3113 SCIP_Bool stored;
3114 SCIP_SOL* sol;
3115 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
3116
3117 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
3118
3121 else
3122 checklprows = TRUE;
3123
3124#ifndef NDEBUG
3125 /* in the debug mode we want to explicitly check if the solution is feasible if it was stored */
3126 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
3127 eventqueue, eventfilter, sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
3128
3129 if( stored )
3130 {
3131 SCIP_Bool feasible;
3132
3133 SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, FALSE, FALSE, TRUE, TRUE,
3134 checklprows, &feasible) );
3136 }
3137
3138 SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) );
3139#else
3140 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
3141 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
3142#endif
3143 if( stored )
3144 {
3145 stat->nlpsolsfound++;
3146
3147 if( primal->nbestsolsfound != oldnbestsolsfound )
3148 {
3149 stat->nlpbestsolsfound++;
3151 }
3152
3153 if( set->reopt_enable )
3154 {
3155 assert(reopt != NULL);
3157 SCIPlpGetSolstat(lp), tree->root == tree->focusnode, TRUE, tree->focusnode->lowerbound,
3158 tree->effectiverootdepth) );
3159 }
3160 }
3161
3163 *unbounded = TRUE;
3164 }
3165 }
3166 else
3167 {
3168 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob,
3169 origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE,
3170 cutoff) );
3171 }
3172 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3173
3174 /* check for infeasible node by bounding */
3175 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
3176#ifdef SCIP_DEBUG
3177 if( *cutoff )
3178 {
3179 if( SCIPtreeGetCurrentDepth(tree) == 0 )
3180 {
3181 SCIPsetDebugMsg(set, "solution cuts off root node, stop solution process\n");
3182 }
3183 else
3184 {
3185 SCIPsetDebugMsg(set, "solution cuts off node\n");
3186 }
3187 }
3188#endif
3189
3190 if( !(*cutoff) && !(*lperror) )
3191 {
3192 SCIP_Longint oldninitconssadded;
3193 SCIP_Longint oldnboundchgs;
3194 SCIP_Longint olddomchgcount;
3195 int oldnpricedvars;
3196 int oldncutsapplied;
3197
3198 oldnpricedvars = transprob->ncolvars;
3201 oldnboundchgs = stat->nboundchgs;
3203
3204 /* solve the LP with price-and-cut*/
3205 SCIP_CALL( priceAndCutLoop(blkmem, set, messagehdlr, stat, mem, transprob, origprob, primal, tree, reopt, lp,
3206 pricestore, sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter,
3207 eventqueue, cliquetable, fullseparation, propagateagain, cutoff, unbounded, lperror, pricingaborted) );
3208
3209 /* check if the problem was changed and the relaxation needs to be resolved */
3210 if( (transprob->ncolvars != oldnpricedvars) || (stat->ninitconssadded != oldninitconssadded) ||
3212 (stat->domchgcount != olddomchgcount) )
3213 {
3215 markRelaxsUnsolved(set, relaxation);
3216 }
3217 }
3218 assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3219
3220 /* if there is no LP error, then *unbounded should be TRUE, iff the LP solution status is unboundedray */
3222
3223 /* If pricing was aborted while solving the LP of the node and the node cannot be cut off due to the lower bound computed by the pricer,
3224 * the solving of the LP might be stopped due to the objective limit, but the node may not be cut off, since the LP objective
3225 * is not a feasible lower bound for the solutions in the current subtree.
3226 * In this case, the LP has to be solved to optimality by temporarily removing the cutoff bound.
3227 */
3229 && !(*cutoff) )
3230 {
3231 SCIP_Real tmpcutoff;
3232
3233 /* temporarily disable cutoffbound, which also disables the objective limit */
3234 tmpcutoff = lp->cutoffbound;
3236
3237 lp->solved = FALSE;
3238 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) );
3239
3240 /* reinstall old cutoff bound */
3241 lp->cutoffbound = tmpcutoff;
3242
3243 SCIPsetDebugMsg(set, "re-optimized LP without cutoff bound: LP status: %d, LP obj: %g\n",
3244 SCIPlpGetSolstat(lp), *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
3245
3246 /* lp solstat should not be objlimit, since the cutoff bound was removed temporarily */
3248 /* lp solstat should not be unboundedray, since the lp was dual feasible */
3250 /* there should be no primal ray, since the lp was dual feasible */
3251 assert(primal->primalray == NULL);
3253 {
3254 *cutoff = TRUE;
3255 }
3256 }
3257
3258 assert(!(*pricingaborted) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL /* cppcheck-suppress assertWithSideEffect */
3260
3261 assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3262
3263 /* update node's LP iteration counter */
3264 stat->nnodelps += stat->nlps - nlps;
3267
3268 /* update number of root node LPs and iterations if the root node was processed */
3269 if( SCIPnodeGetDepth(tree->focusnode) == 0 )
3270 {
3271 stat->nrootlps += stat->nlps - nlps;
3273 }
3274
3275 return SCIP_OKAY;
3276}
3277
3278/** calls relaxators */
3279static
3281 SCIP_SET* set, /**< global SCIP settings */
3282 SCIP_STAT* stat, /**< dynamic problem statistics */
3283 SCIP_TREE* tree, /**< branch and bound tree */
3284 SCIP_RELAXATION* relaxation, /**< relaxators */
3285 SCIP_PROB* transprob, /**< transformed problem */
3286 SCIP_PROB* origprob, /**< original problem */
3287 int depth, /**< depth of current node */
3288 SCIP_Bool beforelp, /**< should the relaxators with non-negative or negative priority be called? */
3289 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3290 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3291 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3292 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called
3293 * again */
3294 SCIP_Bool* relaxcalled /**< pointer to store TRUE, if at least one relaxator was called (unmodified
3295 * otherwise) */
3296 )
3297{
3299 SCIP_Real lowerbound;
3300 int r;
3301
3302 assert(set != NULL);
3303 assert(relaxation != NULL);
3304 assert(cutoff != NULL);
3309 assert(!(*cutoff));
3310
3311 /* sort by priority */
3313
3314 for( r = 0; r < set->nrelaxs && !(*cutoff); ++r )
3315 {
3316 if( beforelp != (SCIPrelaxGetPriority(set->relaxs[r]) >= 0) )
3317 continue;
3318
3319 *relaxcalled = TRUE;
3320
3321 lowerbound = -SCIPsetInfinity(set);
3322
3323 SCIP_CALL( SCIPrelaxExec(set->relaxs[r], set, tree, stat, depth, &lowerbound, &result) );
3324
3325 switch( result )
3326 {
3327 case SCIP_CUTOFF:
3328 *cutoff = TRUE;
3329 SCIPsetDebugMsg(set, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(set->relaxs[r]));
3330 /* @todo does it make sense to proceed if the node is proven to be infeasible? */
3331 return SCIP_OKAY;
3332
3333 case SCIP_CONSADDED:
3334 *solvelpagain = TRUE; /* the separation for new constraints should be called */
3335 *propagateagain = TRUE; /* the propagation for new constraints should be called */
3336 break;
3337
3338 case SCIP_REDUCEDDOM:
3339 *solvelpagain = TRUE;
3341 break;
3342
3343 case SCIP_SEPARATED:
3344 *solvelpagain = TRUE;
3345 break;
3346
3347 case SCIP_SUSPENDED:
3349 break;
3350
3351 case SCIP_SUCCESS:
3352 case SCIP_DIDNOTRUN:
3353 break;
3354
3355 default:
3356 SCIPerrorMessage("invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(set->relaxs[r]));
3357 return SCIP_INVALIDRESULT;
3358 } /*lint !e788*/
3359
3361 {
3362 SCIP_NODE* focusnode;
3363
3364 focusnode = SCIPtreeGetFocusNode(tree);
3365 assert(focusnode != NULL);
3367
3368 /* update lower bound w.r.t. the lower bound given by the relaxator */
3369 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, lowerbound);
3370 SCIPsetDebugMsg(set, " -> new lower bound given by relaxator %s: %g\n",
3371 SCIPrelaxGetName(set->relaxs[r]), lowerbound);
3372 }
3373 }
3374
3375 return SCIP_OKAY;
3376}
3377
3378/** enforces constraints by branching, separation, or domain reduction */
3379static
3381 BMS_BLKMEM* blkmem, /**< block memory buffers */
3382 SCIP_SET* set, /**< global SCIP settings */
3383 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3384 SCIP_STAT* stat, /**< dynamic problem statistics */
3385 SCIP_PROB* prob, /**< transformed problem after presolve */
3386 SCIP_PRIMAL* primal, /**< primal data */
3387 SCIP_TREE* tree, /**< branch and bound tree */
3388 SCIP_LP* lp, /**< LP data */
3389 SCIP_RELAXATION* relaxation, /**< global relaxation data */
3390 SCIP_SEPASTORE* sepastore, /**< separation storage */
3391 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3392 SCIP_Bool* branched, /**< pointer to store whether a branching was created */
3393 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3394 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the LP/pseudo solution is infeasible */
3395 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3396 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3397 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
3398 SCIP_Bool forced /**< should enforcement of pseudo solution be forced? */
3399 )
3400{
3402 SCIP_SOL* relaxsol = NULL;
3403 SCIP_Real pseudoobjval;
3404 SCIP_Bool resolved;
3405 SCIP_Bool objinfeasible;
3406 SCIP_Bool enforcerelaxsol;
3407 int h;
3408
3409 assert(set != NULL);
3410 assert(stat != NULL);
3411 assert(tree != NULL);
3413 assert(branched != NULL);
3414 assert(cutoff != NULL);
3415 assert(infeasible != NULL);
3419 assert(!(*cutoff));
3421 assert(!(*solvelpagain));
3423
3424 *branched = FALSE;
3425 /**@todo avoid checking the same pseudosolution twice */
3426
3427 /* enforce (best) relaxation solution if the LP has a worse objective value */
3429 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, prob)));
3430
3431 /* check if all constraint handlers implement the enforelax callback, otherwise enforce the LP solution */
3432 for( h = 0; h < set->nconshdlrs && enforcerelaxsol; ++h )
3433 {
3434 if( set->conshdlrs_enfo[h]->consenforelax == NULL && ((! set->conshdlrs_enfo[h]->needscons) ||
3435 (set->conshdlrs_enfo[h]->nconss > 0)) )
3436 {
3437 SCIP_VERBLEVEL verblevel;
3438
3440
3441 verblevel = SCIP_VERBLEVEL_FULL;
3442
3443 if( !stat->disableenforelaxmsg && set->disp_verblevel == SCIP_VERBLEVEL_HIGH )
3444 {
3445 verblevel = SCIP_VERBLEVEL_HIGH;
3446
3447 /* remember that the disable relaxation enforcement message was posted and only post it again if the
3448 * verblevel is SCIP_VERBLEVEL_FULL
3449 */
3450 stat->disableenforelaxmsg = TRUE;
3451 }
3452 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel, "Disable enforcement of relaxation solutions"
3453 " since constraint handler %s does not implement enforelax-callback\n",
3454 SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3455 }
3456 }
3457
3458 /* enforce constraints by branching, applying additional cutting planes (if LP is being processed),
3459 * introducing new constraints, or tighten the domains
3460 */
3461#ifndef SCIP_NDEBUG
3462 if( enforcerelaxsol )
3463 {
3464 SCIPsetDebugMsg(set, "enforcing constraints on relaxation solution\n");
3465 }
3466 else
3467 {
3468 SCIPsetDebugMsg(set, "enforcing constraints on %s solution\n", SCIPtreeHasFocusNodeLP(tree) ? "LP" : "pseudo");
3469 }
3470#endif
3471
3472 /* check, if the solution is infeasible anyway due to it's objective value */
3475 else
3476 {
3477 pseudoobjval = SCIPlpGetPseudoObjval(lp, set, prob);
3479 }
3480
3481 /* during constraint enforcement, generated cuts should enter the LP in any case; otherwise, a constraint handler
3482 * would fail to enforce its constraints if it relies on the modification of the LP relaxation
3483 */
3484 SCIPsepastoreStartForceCuts(sepastore);
3485
3486 /* enforce constraints until a handler resolved an infeasibility with cutting off the node, branching,
3487 * reducing a domain, or separating a cut
3488 * if a constraint handler introduced new constraints to enforce his constraints, the newly added constraints
3489 * have to be enforced themselves
3490 */
3491 resolved = FALSE;
3492
3493 /* in case the relaxation solution should be enforced, we need to create the corresponding solution for the enforelax callbacks */
3494 if( enforcerelaxsol )
3495 {
3496 SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
3497 }
3498
3499 for( h = 0; h < set->nconshdlrs && !resolved; ++h )
3500 {
3501 assert(SCIPsepastoreGetNCuts(sepastore) == 0); /* otherwise, the LP should have been resolved first */
3502
3503 /* enforce LP, pseudo, or relaxation solution */
3504 if( enforcerelaxsol )
3505 {
3506 SCIPsetDebugMsg(set, "enforce relaxation solution with value %g\n", SCIPrelaxationGetSolObj(relaxation));
3507
3508 SCIP_CALL( SCIPconshdlrEnforceRelaxSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore,
3509 relaxsol, *infeasible, &result) );
3510 }
3511 else if( SCIPtreeHasFocusNodeLP(tree) )
3512 {
3513 SCIPsetDebugMsg(set, "enforce LP solution with value %g\n", SCIPlpGetObjval(lp, set, prob));
3514
3515 assert(lp->flushed);
3516 assert(lp->solved);
3518 SCIP_CALL( SCIPconshdlrEnforceLPSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore, *infeasible,
3519 &result) );
3520 }
3521 else
3522 {
3523 SCIP_CALL( SCIPconshdlrEnforcePseudoSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, branchcand, *infeasible,
3525 if( SCIPsepastoreGetNCuts(sepastore) != 0 )
3526 {
3527 SCIPerrorMessage("pseudo enforcing method of constraint handler <%s> separated cuts\n",
3528 SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3529 return SCIP_INVALIDRESULT;
3530 }
3531 }
3532 SCIPsetDebugMsg(set, "enforcing of <%s> returned result %d\n", SCIPconshdlrGetName(set->conshdlrs_enfo[h]), result);
3533
3534 switch( result )
3535 {
3536 case SCIP_CUTOFF:
3537 assert(tree->nchildren == 0);
3538 *cutoff = TRUE;
3539 *infeasible = TRUE;
3540 resolved = TRUE;
3541 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in enforcement\n",
3542 SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3543 break;
3544
3545 case SCIP_CONSADDED:
3546 assert(tree->nchildren == 0);
3547 *infeasible = TRUE;
3548 *propagateagain = TRUE; /* the propagation for new constraints should be called */
3549 *solvelpagain = TRUE; /* the separation for new constraints should be called */
3551 markRelaxsUnsolved(set, relaxation);
3552 resolved = TRUE;
3553 break;
3554
3555 case SCIP_REDUCEDDOM:
3556 assert(tree->nchildren == 0);
3557 *infeasible = TRUE;
3559 *solvelpagain = TRUE;
3561 markRelaxsUnsolved(set, relaxation);
3562 resolved = TRUE;
3563 break;
3564
3565 case SCIP_SEPARATED:
3566 assert(tree->nchildren == 0);
3567 assert(SCIPsepastoreGetNCuts(sepastore) > 0);
3568 *infeasible = TRUE;
3569 *solvelpagain = TRUE;
3571 markRelaxsUnsolved(set, relaxation);
3572 resolved = TRUE;
3573 break;
3574
3575 case SCIP_BRANCHED:
3576 assert(tree->nchildren >= 1);
3577 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3578 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3579 *infeasible = TRUE;
3580 *branched = TRUE;
3581 resolved = TRUE;
3582
3583 /* increase the number of internal nodes */
3584 stat->ninternalnodes++;
3585 stat->ntotalinternalnodes++;
3586 break;
3587
3588 case SCIP_SOLVELP:
3589 /* either LP was not solved, or it is not solved anymore (e.g., because feastol has been tightened by some constraint handler) */
3590 assert(!SCIPtreeHasFocusNodeLP(tree) || !lp->solved);
3591 assert(tree->nchildren == 0);
3592 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3593 *infeasible = TRUE;
3594 *solvelpagain = TRUE;
3595 resolved = TRUE;
3596 SCIPtreeSetFocusNodeLP(tree, TRUE); /* the node's LP must be solved */
3597 break;
3598
3599 case SCIP_INFEASIBLE:
3600 assert(tree->nchildren == 0);
3601 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3602 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3603 *infeasible = TRUE;
3604 break;
3605
3606 case SCIP_FEASIBLE:
3607 assert(tree->nchildren == 0);
3608 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3609 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3610 break;
3611
3612 case SCIP_DIDNOTRUN:
3613 assert(tree->nchildren == 0);
3614 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3615 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3617 *infeasible = TRUE;
3618 break;
3619
3620 default:
3621 SCIPerrorMessage("invalid result code <%d> from enforcing method of constraint handler <%s>\n",
3622 result, SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3623 return SCIP_INVALIDRESULT;
3624 } /*lint !e788*/
3625
3626 /* the enforcement method may add a primal solution, after which the LP status could be set to
3627 * objective limit reached
3628 */
3630 {
3631 *cutoff = TRUE;
3632 *infeasible = TRUE;
3633 resolved = TRUE;
3634 SCIPsetDebugMsg(set, " -> LP exceeded objective limit\n");
3635
3636 /* If we used the probing mode during branching, it might happen that we added a constraint or global bound
3637 * and returned SCIP_CONSADDED or SCIP_REDUCEDDOM, but when reoptimizing the LP after ending the probing mode,
3638 * this leads to hitting the objective limit. In this case, we do not need to propagate or solve the LP again.
3639 */
3642 }
3643
3644 assert(!(*branched) || (resolved && !(*cutoff) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3645 assert(!(*cutoff) || (resolved && !(*branched) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3646 assert(*infeasible || (!resolved && !(*branched) && !(*cutoff) && !(*propagateagain) && !(*solvelpagain)));
3647 assert(!(*propagateagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3648 assert(!(*solvelpagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3649 }
3650 assert(!objinfeasible || *infeasible);
3652 assert(*cutoff || *solvelpagain || SCIPsepastoreGetNCuts(sepastore) == 0);
3653
3654 /* in case the relaxation solution was enforced, free the created solution */
3655 if( enforcerelaxsol )
3656 {
3657 SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
3658 }
3659
3660 /* deactivate the cut forcing of the constraint enforcement */
3661 SCIPsepastoreEndForceCuts(sepastore);
3662
3663 SCIPsetDebugMsg(set, " -> enforcing result: branched=%u, cutoff=%u, infeasible=%u, propagateagain=%u, solvelpagain=%u, resolved=%u\n",
3664 *branched, *cutoff, *infeasible, *propagateagain, *solvelpagain, resolved);
3665
3666 return SCIP_OKAY;
3667}
3668
3669/** applies the cuts stored in the separation store, or clears the store if the node can be cut off */
3670static
3672 BMS_BLKMEM* blkmem, /**< block memory buffers */
3673 SCIP_SET* set, /**< global SCIP settings */
3674 SCIP_STAT* stat, /**< dynamic problem statistics */
3675 SCIP_PROB* transprob, /**< transformed problem */
3676 SCIP_PROB* origprob, /**< original problem */
3677 SCIP_TREE* tree, /**< branch and bound tree */
3678 SCIP_REOPT* reopt, /**< reotimization data structure */
3679 SCIP_LP* lp, /**< LP data */
3680 SCIP_RELAXATION* relaxation, /**< relaxators */
3681 SCIP_SEPASTORE* sepastore, /**< separation storage */
3682 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3683 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3684 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3685 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3686 SCIP_Bool root, /**< is this the initial root LP? */
3687 SCIP_EFFICIACYCHOICE efficiacychoice, /**< type of solution to base efficiacy computation on */
3688 SCIP_Bool* cutoff, /**< pointer to whether the node can be cut off */
3689 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3690 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3691 SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if the node's relaxation has to be solved again */
3692 )
3693{
3694 assert(stat != NULL);
3695 assert(cutoff != NULL);
3698
3699 if( *cutoff )
3700 {
3701 /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
3702 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
3703 }
3704 else if( SCIPsepastoreGetNCuts(sepastore) > 0 )
3705 {
3706 SCIP_Longint olddomchgcount;
3707 int oldncutsapplied;
3708
3711 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
3712 eventqueue, eventfilter, cliquetable, root, efficiacychoice, cutoff) );
3714 *solvelpagain = TRUE;
3716 {
3718 markRelaxsUnsolved(set, relaxation);
3719 }
3720 }
3721
3722 return SCIP_OKAY;
3723}
3724
3725/** updates the cutoff, propagateagain, and solverelaxagain status of the current solving loop */
3726static
3728 SCIP_SET* set, /**< global SCIP settings */
3729 SCIP_STAT* stat, /**< dynamic problem statistics */
3730 SCIP_TREE* tree, /**< branch and bound tree */
3731 int depth, /**< depth of current node */
3732 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3733 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3734 SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if at least one relaxator should be called again */
3735 )
3736{
3737 SCIP_NODE* focusnode;
3738 int r;
3739
3740 assert(set != NULL);
3741 assert(stat != NULL);
3742 assert(cutoff != NULL);
3745
3746 /* check, if the path was cutoff */
3747 *cutoff = *cutoff || (tree->cutoffdepth <= depth);
3748
3749 /* check if branching was already performed */
3750 if( tree->nchildren == 0 )
3751 {
3752 /* check, if the focus node should be repropagated */
3753 focusnode = SCIPtreeGetFocusNode(tree);
3755
3756 /* check, if one of the external relaxations should be solved again */
3757 for( r = 0; r < set->nrelaxs && !(*solverelaxagain); ++r )
3758 *solverelaxagain = *solverelaxagain || ( !SCIPrelaxIsSolved(set->relaxs[r], stat) );
3759 }
3760 else
3761 {
3762 /* if branching was performed, avoid another node loop iteration */
3765 }
3766}
3767
3768/** propagate domains and solve relaxation and lp */
3769static
3771 BMS_BLKMEM* blkmem, /**< block memory buffers */
3772 SCIP_SET* set, /**< global SCIP settings */
3773 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3774 SCIP_STAT* stat, /**< dynamic problem statistics */
3775 SCIP_MEM* mem, /**< block memory pools */
3776 SCIP_PROB* origprob, /**< original problem */
3777 SCIP_PROB* transprob, /**< transformed problem after presolve */
3778 SCIP_PRIMAL* primal, /**< primal data */
3779 SCIP_TREE* tree, /**< branch and bound tree */
3780 SCIP_REOPT* reopt, /**< reoptimization data structure */
3781 SCIP_LP* lp, /**< LP data */
3782 SCIP_RELAXATION* relaxation, /**< global relaxation data */
3783 SCIP_PRICESTORE* pricestore, /**< pricing storage */
3784 SCIP_SEPASTORE* sepastore, /**< separation storage */
3785 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3786 SCIP_CUTPOOL* cutpool, /**< global cut pool */
3787 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
3788 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3789 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
3790 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3791 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3792 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3793 SCIP_NODE* focusnode, /**< focused node */
3794 int actdepth, /**< depth in the b&b tree */
3795 SCIP_Bool propagate, /**< should we propagate */
3796 SCIP_Bool solvelp, /**< should we solve the lp */
3797 SCIP_Bool solverelax, /**< should we solve the relaxation */
3798 SCIP_Bool forcedlpsolve, /**< is there a need for a solve lp */
3799 SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
3800 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
3801 SCIP_Longint* afterlpproplps, /**< pointer to store the last LP count for which AFTERLP propagation was performed */
3802 SCIP_HEURTIMING* heurtiming, /**< timing for running heuristics after propagation call */
3803 int* nlperrors, /**< pointer to store the number of lp errors */
3804 SCIP_Bool* fullpropagation, /**< pointer to store whether we want to do a fullpropagation next time */
3805 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
3806 SCIP_Bool* lpsolved, /**< pointer to store whether the lp was solved */
3807 SCIP_Bool* relaxcalled, /**< pointer to store whether a relaxator was called; initialized with last loop's result */
3808 SCIP_Bool* solvelpagain, /**< pointer to store whether we want to solve the lp again */
3809 SCIP_Bool* solverelaxagain, /**< pointer to store whether we want to solve the relaxation again */
3810 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
3811 SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
3812 SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
3813 SCIP_Bool* stopped, /**< pointer to store whether solving was interrupted */
3814 SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
3815 SCIP_Bool* pricingaborted, /**< pointer to store TRUE, if the pricing was aborted and the lower bound must not be used */
3816 SCIP_Bool* forcedenforcement /**< pointer to store whether the enforcement of pseudo solution should be forced */
3817 )
3818{
3819 SCIP_Bool newinitconss;
3820
3821 assert(set != NULL);
3822 assert(stat != NULL);
3823 assert(origprob != NULL);
3824 assert(transprob != NULL);
3825 assert(tree != NULL);
3826 assert(lp != NULL);
3827 assert(primal != NULL);
3828 assert(pricestore != NULL);
3829 assert(sepastore != NULL);
3830 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3831 assert(branchcand != NULL);
3832 assert(cutpool != NULL);
3833 assert(delayedcutpool != NULL);
3834 assert(conflict != NULL);
3835 assert(SCIPconflictGetNConflicts(conflict) == 0);
3836 assert(eventfilter != NULL);
3837 assert(eventqueue != NULL);
3838 assert(focusnode != NULL);
3840 assert(nlperrors != NULL);
3844 assert(lpsolved != NULL);
3847 assert(cutoff != NULL);
3848 assert(postpone != NULL);
3849 assert(unbounded != NULL);
3850 assert(lperror != NULL);
3853
3855
3856 if( !(*cutoff) && !(*postpone) )
3857 {
3858 SCIP_Longint oldninitconssadded;
3859 SCIP_Longint oldnboundchgs;
3860 SCIP_Bool lpwasflushed;
3861
3862 lpwasflushed = lp->flushed;
3863 oldnboundchgs = stat->nboundchgs;
3865
3866 /* call after LP propagators */
3867 if( ((*afterlpproplps) < stat->nnodelps && (*lpsolved)) || (*relaxcalled) )
3868 {
3869 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3872
3873 /* check, if the path was cutoff */
3874 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3875 *afterlpproplps = stat->nnodelps;
3877 }
3878
3879 /* call before LP propagators */
3880 if( propagate && !(*cutoff) )
3881 {
3882 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3885 }
3886
3889
3890 /* check, if the path was cutoff */
3891 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3892
3893 /* if the LP was flushed and is now no longer flushed, a bound change occurred, and the LP has to be resolved;
3894 * we also have to solve the LP if new intial constraints were added which need to be added to the LP
3895 */
3896 solvelp = solvelp || (lpwasflushed && (!lp->flushed || newinitconss));
3898
3899 /* the number of bound changes was increased by the propagation call, thus the relaxation should be solved again */
3900 if( stat->nboundchgs > oldnboundchgs )
3901 {
3902 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
3903 * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
3904 * bound of the node needs to be updated
3905 */
3906 if( !solvelp && lp->flushed && lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
3907 {
3908 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
3909 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
3910 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
3911
3912 if( SCIPtreeHasFocusNodeLP(tree) )
3913 {
3914 /* update node estimate */
3915 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
3916
3918 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
3919 }
3920 }
3921
3922 solverelax = TRUE;
3923 markRelaxsUnsolved(set, relaxation);
3924 }
3925
3926 /* update lower bound with the pseudo objective value, and cut off node by bounding */
3927 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
3928 conflict, cliquetable, cutoff) );
3929 }
3930 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3931
3932 if( *postpone )
3933 return SCIP_OKAY;
3934
3935 /* call primal heuristics that are applicable after propagation loop before lp solve;
3936 * the first time we go here, we call the before node heuristics instead
3937 */
3938 if( !(*cutoff) && !SCIPtreeProbing(tree) )
3939 {
3940 /* if the heuristics find a new incumbent solution, propagate again */
3941 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, *heurtiming,
3944
3946
3947 /* check if primal heuristics found a solution and we therefore reached a solution limit */
3948 if( SCIPsolveIsStopped(set, stat, FALSE) )
3949 {
3950 /* cppcheck-suppress unassignedVariable */
3951 SCIP_NODE* node;
3952
3953 /* we reached a solution limit and do not want to continue the processing of the current node, but in order to
3954 * allow restarting the optimization process later, we need to create a "branching" with only one child node that
3955 * is a copy of the focusnode
3956 */
3958 SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) );
3959 assert(tree->nchildren >= 1);
3960 *stopped = TRUE;
3961 return SCIP_OKAY;
3962 }
3963
3964 /* if diving produced an LP error, switch back to non-LP node */
3965 if( lp->resolvelperror )
3966 {
3968 lp->resolvelperror = FALSE;
3969 }
3970
3971 if( *propagateagain )
3972 {
3975
3976 return SCIP_OKAY;
3977 }
3978 }
3979
3980 /* solve external relaxations with non-negative priority */
3981 *relaxcalled = FALSE;
3982 if( solverelax && !(*cutoff) )
3983 {
3984 /* clear the storage of external branching candidates */
3986
3987 SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, TRUE,
3990
3991 /* check, if the path was cutoff */
3992 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3993
3994 /* apply found cuts */
3995 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
3996 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
3998
3999 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4000 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4001 }
4002 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4003
4004 /* check, if we want to solve the LP at this node */
4005 if( solvelp && !(*cutoff) && SCIPtreeHasFocusNodeLP(tree) )
4006 {
4007 *lperror = FALSE;
4008 *unbounded = FALSE;
4009
4010 /* solve the node's LP */
4011 SCIP_CALL( solveNodeLP(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation, pricestore,
4012 sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable,
4014
4015 *lpsolved = TRUE;
4017 SCIPsetDebugMsg(set, " -> LP status: %d, LP obj: %g, iter: %" SCIP_LONGINT_FORMAT ", count: %" SCIP_LONGINT_FORMAT "\n",
4018 SCIPlpGetSolstat(lp),
4019 *cutoff ? SCIPsetInfinity(set) : (*lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob)),
4020 stat->nlpiterations, stat->lpcount);
4021
4022 /* check, if the path was cutoff */
4023 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
4024
4025 /* if an error occured during LP solving, switch to pseudo solution */
4026 if( *lperror )
4027 {
4028 if( forcedlpsolve )
4029 {
4030 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4031 stat->nnodes, stat->nlps);
4032 return SCIP_LPERROR;
4033 }
4035 ++(*nlperrors);
4036 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
4037 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4038 stat->nnodes, stat->nlps, *nlperrors);
4039 }
4040
4042 {
4045
4046 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
4047 "(node %" SCIP_LONGINT_FORMAT ") LP solver hit %s limit in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead\n",
4048 stat->nnodes, SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT ? "time" : "iteration", stat->nlps);
4049 }
4050
4052 {
4053 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4054 "(node %" SCIP_LONGINT_FORMAT ") LP relaxation is unbounded (LP %" SCIP_LONGINT_FORMAT ")\n", stat->nnodes, stat->nlps);
4055 }
4056
4057 /* if we solve exactly, the LP claims to be infeasible but the infeasibility could not be proved,
4058 * we have to forget about the LP and use the pseudo solution instead
4059 */
4060 if( !(*cutoff) && !(*lperror) && (set->misc_exactsolve || *pricingaborted) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE
4061 && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound )
4062 {
4063 if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 && transprob->ncontvars > 0 )
4064 {
4065 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") could not prove infeasibility of LP %" SCIP_LONGINT_FORMAT " (exactsolve=%u, pricingaborted=%u), all variables are fixed, %d continuous vars\n",
4066 stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, transprob->ncontvars);
4067 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") -> have to call PerPlex() (feature not yet implemented)\n", stat->nnodes);
4068 /**@todo call PerPlex */
4069 return SCIP_LPERROR;
4070 }
4071 else
4072 {
4075
4076 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4077 "(node %" SCIP_LONGINT_FORMAT ") could not prove infeasibility of LP %" SCIP_LONGINT_FORMAT " (exactsolve=%u, pricingaborted=%u) -- using pseudo solution (%d unfixed vars) instead\n",
4078 stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, SCIPbranchcandGetNPseudoCands(branchcand));
4079 }
4080 }
4081
4082 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4083 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
4084 cliquetable, cutoff) );
4085 }
4086 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4087 assert(*cutoff || !SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
4088
4089 /* reset solverelaxagain if no relaxations were solved up to this point (the LP-changes are already included in
4090 * relaxators called after the LP)
4091 */
4093
4094 /* solve external relaxations with negative priority */
4095 if( solverelax && !(*cutoff) )
4096 {
4097 SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, FALSE, cutoff,
4100
4101 /* check, if the path was cutoff */
4102 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
4103
4104 /* apply found cuts */
4105 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4106 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
4108
4109 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4110 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
4111 cliquetable, cutoff) );
4112 }
4113 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4114
4115 return SCIP_OKAY;
4116}
4117
4118/** check if a restart can be performed */
4119#ifndef NDEBUG
4120static
4122 SCIP_SET* set, /**< global SCIP settings */
4123 SCIP_STAT* stat /**< dynamic problem statistics */
4124 )
4125{
4126 assert(set != NULL);
4127 assert(stat != NULL);
4128
4129 return (set->nactivepricers == 0 && !set->reopt_enable
4130 && (set->presol_maxrestarts == -1 || stat->nruns <= set->presol_maxrestarts)
4131 && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts));
4132}
4133#else
4134#define restartAllowed(set,stat) ((set)->nactivepricers == 0 && !set->reopt_enable && ((set)->presol_maxrestarts == -1 || (stat)->nruns <= (set)->presol_maxrestarts) \
4135 && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts))
4136#endif
4137
4138/** solves the focus node */
4139static
4141 BMS_BLKMEM* blkmem, /**< block memory buffers */
4142 SCIP_SET* set, /**< global SCIP settings */
4143 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4144 SCIP_STAT* stat, /**< dynamic problem statistics */
4145 SCIP_MEM* mem, /**< block memory pools */
4146 SCIP_PROB* origprob, /**< original problem */
4147 SCIP_PROB* transprob, /**< transformed problem after presolve */
4148 SCIP_PRIMAL* primal, /**< primal data */
4149 SCIP_TREE* tree, /**< branch and bound tree */
4150 SCIP_REOPT* reopt, /**< reoptimization data structure */
4151 SCIP_LP* lp, /**< LP data */
4152 SCIP_RELAXATION* relaxation, /**< global relaxation data */
4153 SCIP_PRICESTORE* pricestore, /**< pricing storage */
4154 SCIP_SEPASTORE* sepastore, /**< separation storage */
4155 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4156 SCIP_CUTPOOL* cutpool, /**< global cut pool */
4157 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
4158 SCIP_CONFLICT* conflict, /**< conflict analysis data */
4159 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4160 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4161 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4162 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4163 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
4164 SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
4165 SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
4166 SCIP_Bool* infeasible, /**< pointer to store whether the focus node's solution is infeasible */
4167 SCIP_Bool* restart, /**< should solving process be started again with presolving? */
4168 SCIP_Bool* afternodeheur, /**< pointer to store whether AFTERNODE heuristics were already called */
4169 SCIP_Bool* stopped /**< pointer to store whether solving was interrupted */
4170 )
4171{
4172 SCIP_NODE* focusnode;
4173 SCIP_Longint lastdomchgcount;
4174 SCIP_Longint afterlpproplps;
4175 SCIP_Real restartfac;
4176 SCIP_Longint lastlpcount;
4178 int actdepth;
4179 int nlperrors;
4180 int nloops;
4181 SCIP_Bool foundsol;
4182 SCIP_Bool focusnodehaslp;
4183 SCIP_Bool lpsolved;
4184 SCIP_Bool initiallpsolved;
4185 SCIP_Bool fullseparation;
4186 SCIP_Bool solverelaxagain;
4187 SCIP_Bool solvelpagain;
4188 SCIP_Bool propagateagain;
4189 SCIP_Bool fullpropagation;
4190 SCIP_Bool branched;
4191 SCIP_Bool forcedlpsolve;
4192 SCIP_Bool wasforcedlpsolve;
4193 SCIP_Bool pricingaborted;
4194
4195 assert(set != NULL);
4196 assert(stat != NULL);
4197 assert(origprob != NULL);
4198 assert(transprob != NULL);
4199 assert(tree != NULL);
4200 assert(primal != NULL);
4201 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4202 assert(SCIPconflictGetNConflicts(conflict) == 0);
4203 assert(cutoff != NULL);
4204 assert(postpone != NULL);
4205 assert(unbounded != NULL);
4206 assert(infeasible != NULL);
4207 assert(restart != NULL);
4209
4210 *cutoff = FALSE;
4211 *postpone = FALSE;
4212 *unbounded = FALSE;
4213 *infeasible = FALSE;
4214 *restart = FALSE;
4216 *stopped = FALSE;
4218
4219 focusnode = SCIPtreeGetFocusNode(tree);
4220 assert(focusnode != NULL);
4222 actdepth = SCIPnodeGetDepth(focusnode);
4223
4224 /* invalidate relaxation solution */
4226
4227 /* clear the storage of external branching candidates */
4229
4230 SCIPsetDebugMsg(set, "Processing node %" SCIP_LONGINT_FORMAT " in depth %d, %d siblings\n",
4231 stat->nnodes, actdepth, tree->nsiblings);
4232 SCIPsetDebugMsg(set, "current pseudosolution: obj=%g\n", SCIPlpGetPseudoObjval(lp, set, transprob));
4233 /*debug(SCIPprobPrintPseudoSol(transprob, set));*/
4234
4235 /* check, if we want to solve the LP at the selected node:
4236 * - solve the LP, if the lp solve depth and frequency demand solving
4237 * - solve the root LP, if the LP solve frequency is set to 0
4238 * - solve the root LP, if there are continuous variables present
4239 * - don't solve the node if its cut off by the pseudo objective value anyway
4240 */
4241 focusnodehaslp = (set->lp_solvedepth == -1 || actdepth <= set->lp_solvedepth);
4242 focusnodehaslp = focusnodehaslp && (set->lp_solvefreq >= 1 && actdepth % set->lp_solvefreq == 0);
4243 focusnodehaslp = focusnodehaslp || (actdepth == 0 && set->lp_solvefreq == 0);
4244 focusnodehaslp = focusnodehaslp && SCIPsetIsLT(set, SCIPlpGetPseudoObjval(lp, set, transprob), primal->cutoffbound);
4245 focusnodehaslp = set->reopt_enable ? focusnodehaslp && SCIPreoptGetSolveLP(reopt, set, focusnode) : focusnodehaslp;
4246 SCIPtreeSetFocusNodeLP(tree, focusnodehaslp);
4247
4248 /* external node solving loop:
4249 * - propagate domains
4250 * - solve SCIP_LP
4251 * - enforce constraints
4252 * if a constraint handler adds constraints to enforce its own constraints, both, propagation and LP solving
4253 * is applied again (if applicable on current node); however, if the new constraints don't have the enforce flag set,
4254 * it is possible, that the current infeasible solution is not cut off; in this case, we have to declare the solution
4255 * infeasible and perform a branching
4256 */
4258 lastlpcount = stat->lpcount;
4262 nlperrors = 0;
4263 stat->npricerounds = 0;
4264 stat->nseparounds = 0;
4270 nloops = 0;
4271
4272 while( !(*cutoff) && !(*postpone) && (solverelaxagain || solvelpagain || propagateagain) && nlperrors < MAXNLPERRORS && !(*restart) )
4273 {
4274 SCIP_Bool lperror;
4275 SCIP_Bool solverelax;
4276 SCIP_Bool solvelp;
4277 SCIP_Bool propagate;
4278 SCIP_Bool forcedenforcement;
4279 SCIP_Bool relaxcalled;
4280
4281 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4282
4283 *unbounded = FALSE;
4284 *infeasible = FALSE;
4285 foundsol = FALSE;
4286
4287 nloops++;
4288 lperror = FALSE;
4289 lpsolved = FALSE;
4292 afterlpproplps = -1L;
4293
4295 || (afterlpproplps < stat->nnodelps && lpsolved) || relaxcalled) )
4296 {
4303
4304 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4305 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
4306 conflict, cliquetable, cutoff) );
4307
4308 /* propagate domains before lp solving and solve relaxation and lp */
4309 SCIPsetDebugMsg(set, " -> node solving loop: call propagators that are applicable before%s LP is solved\n",
4310 lpsolved ? " and after" : "");
4311 SCIP_CALL( propAndSolve(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp,
4312 relaxation, pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter,
4313 eventqueue, cliquetable, focusnode, actdepth, propagate, solvelp, solverelax, forcedlpsolve, initiallpsolved,
4317
4318 /* time or solution limit was hit and we already created a dummy child node to terminate fast */
4319 if( *stopped )
4320 {
4321 /* reset LP feastol to normal value, in case someone tightened it during node solving */
4323 return SCIP_OKAY;
4324 }
4325 }
4327
4328 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4330
4331 /* call primal heuristics that should be applied after the LP relaxation of the node was solved;
4332 * if this is the first loop of the root node, call also AFTERNODE heuristics already here, since they might help
4333 * to improve the primal bound, thereby producing additional reduced cost strengthenings and strong branching
4334 * bound fixings which also might lead to a restart
4335 */
4336 if( !(*postpone) && (!(*cutoff) || SCIPtreeGetNNodes(tree) > 0) )
4337 {
4338 if( actdepth == 0 && !(*afternodeheur) )
4339 {
4340 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL,
4342 *afternodeheur = TRUE; /* the AFTERNODE heuristics should not be called again after the node */
4343 }
4344 else if( lpsolved || SCIPrelaxationIsSolValid(relaxation) )
4345 {
4346 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_AFTERLPLOOP,
4347 *cutoff, &foundsol, unbounded) );
4348 }
4350
4351 /* heuristics might have found a solution or set the cutoff bound such that the current node is cut off */
4352 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4353 }
4354
4355 /* check if heuristics leave us with an invalid LP */
4356 if( lp->resolvelperror )
4357 {
4358 if( forcedlpsolve )
4359 {
4360 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4361 stat->nnodes, stat->nlps);
4362 return SCIP_LPERROR;
4363 }
4365 lp->resolvelperror = FALSE;
4366 nlperrors++;
4367 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4368 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4369 stat->nnodes, stat->nlps, nlperrors);
4370 }
4371
4373 {
4375
4376 /* if we just ran into the time limit this is not really a numerical trouble;
4377 * however, if this is not the case, we print messages about numerical troubles in the current LP
4378 */
4379 if( !SCIPsolveIsStopped(set, stat, FALSE) )
4380 {
4381 if( forcedlpsolve )
4382 {
4383 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4384 stat->nnodes, stat->nlps);
4385 return SCIP_LPERROR;
4386 }
4387 nlperrors++;
4388 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4389 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4390 stat->nnodes, stat->nlps, nlperrors);
4391 }
4392 }
4393
4394 /* if an improved solution was found, propagate and solve the relaxations again */
4395 if( foundsol && !(*cutoff) )
4396 {
4400 markRelaxsUnsolved(set, relaxation);
4401 }
4402
4403 /* check for immediate restart */
4404 *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart
4405 || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars)
4406 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4407
4408 /* enforce constraints */
4409 branched = FALSE;
4410 if( !(*postpone) && !(*restart) && !(*cutoff) && !solverelaxagain && !solvelpagain && !propagateagain )
4411 {
4412 /* if the solution changed since the last enforcement, we have to completely reenforce it; otherwise, we
4413 * only have to enforce the additional constraints added in the last enforcement, but keep the infeasible
4414 * flag TRUE in order to not declare the infeasible solution feasible due to disregarding the already
4415 * enforced constraints
4416 */
4417 if( lastdomchgcount != stat->domchgcount || lastlpcount != stat->lpcount )
4418 {
4420 lastlpcount = stat->lpcount;
4421 *infeasible = FALSE;
4422 }
4423
4424 /* call constraint enforcement */
4425 SCIP_CALL( enforceConstraints(blkmem, set, messagehdlr, stat, transprob, primal, tree, lp, relaxation, sepastore,
4426 branchcand, &branched, cutoff, infeasible, &propagateagain, &solvelpagain, &solverelaxagain,
4428 assert(branched == (tree->nchildren > 0));
4429 assert(!branched || (!(*cutoff) && *infeasible && !propagateagain && !solvelpagain));
4430 assert(!(*cutoff) || (!branched && *infeasible && !propagateagain && !solvelpagain));
4431 assert(*infeasible || (!branched && !(*cutoff) && !propagateagain && !solvelpagain));
4432 assert(!propagateagain || (!branched && !(*cutoff) && *infeasible));
4433 assert(!solvelpagain || (!branched && !(*cutoff) && *infeasible));
4434
4436
4437 /* apply found cuts */
4438 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4439 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain,
4441
4442 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4443 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4444
4445 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4447 }
4448 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4449
4450 /* The enforcement detected no infeasibility, so, no branching was performed,
4451 * but the pricing was aborted and the current feasible solution does not have to be the
4452 * best solution in the current subtree --> we have to do a pseudo branching,
4453 * so we set infeasible TRUE and add the current solution to the solution pool
4454 */
4455 if( pricingaborted && !(*infeasible) && !(*cutoff) && !(*postpone) && !(*restart) )
4456 {
4457 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
4458 SCIP_SOL* sol;
4459 SCIP_Bool stored;
4460
4461 /* in case the relaxation was enforced add this solution, otherwise decide between LP and pseudosol */
4463 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4464 {
4465 SCIP_SOL* relaxsol;
4466
4467 SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4468
4469 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4470 eventqueue, eventfilter, relaxsol, FALSE, FALSE, TRUE, TRUE, TRUE,
4471 &stored) );
4472
4473 SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
4474
4475 if( stored )
4476 {
4477 stat->nrelaxsolsfound++;
4478
4479 if( primal->nbestsolsfound != oldnbestsolsfound )
4480 {
4481 stat->nrelaxbestsolsfound++;
4483 }
4484 }
4485 }
4486 else
4487 {
4488 SCIP_CALL( SCIPsolCreateCurrentSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4489 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4490 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
4491
4492 if( stored )
4493 {
4494 stat->nlpsolsfound++;
4495
4496 if( primal->nbestsolsfound != oldnbestsolsfound )
4497 {
4498 stat->nlpbestsolsfound++;
4500 }
4501 }
4502 }
4503
4504 *infeasible = TRUE;
4505 }
4506
4507 /* if the node is infeasible, but no constraint handler could resolve the infeasibility
4508 * -> branch on LP, external candidates, or the pseudo solution
4509 * -> e.g. select non-fixed binary or integer variable x with value x', create three
4510 * sons: x <= x'-1, x = x', and x >= x'+1.
4511 * In the left and right branch, the current solution is cut off. In the middle
4512 * branch, the constraints can hopefully reduce domains of other variables to cut
4513 * off the current solution.
4514 * In LP branching, we cannot allow adding constraints, because this does not necessary change the LP and can
4515 * therefore lead to an infinite loop.
4516 */
4519 if( (*infeasible) && !(*cutoff) && !(*postpone) && !(*restart)
4520 && (!(*unbounded) || SCIPbranchcandGetNExternCands(branchcand) > 0 || SCIPbranchcandGetNPseudoCands(branchcand) > 0)
4522 {
4524 int nlpcands = 0;
4525
4526 if( SCIPtreeHasFocusNodeLP(tree) )
4527 {
4528 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpcands, NULL, NULL) );
4529 }
4530
4531 if ( nlpcands > 0 || SCIPbranchcandGetNExternCands(branchcand) > 0 )
4532 {
4533 /* If there are LP candidates and their maximal priority is at least the maximal priority of the external
4534 * candidates, then branch on the LP candidates. Note that due to implicit integer variables,
4535 * SCIPbranchcandGetLPMaxPrio(branchcand) might be finite and SCIPbranchcandGetNPrioLPCands(branchcand) > 0,
4536 * but nlpcands == 0. */
4537 if ( SCIPbranchcandGetLPMaxPrio(branchcand) >= SCIPbranchcandGetExternMaxPrio(branchcand) && nlpcands > 0 )
4538 {
4539 assert( SCIPbranchcandGetNPrioLPCands(branchcand) > 0 );
4540 assert( nlpcands > 0 );
4541
4542 /* branch on LP solution */
4543 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on LP solution with %d fractionals\n",
4544 SCIPnodeGetDepth(focusnode), nlpcands);
4545 SCIP_CALL( SCIPbranchExecLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4546 eventqueue, primal->cutoffbound, FALSE, &result) );
4549 }
4550 else
4551 {
4552 assert( SCIPbranchcandGetNPrioExternCands(branchcand) > 0 );
4553 assert( SCIPbranchcandGetNExternCands(branchcand) > 0 );
4554
4555 /* branch on external candidates */
4556 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on %d external branching candidates.\n",
4557 SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNExternCands(branchcand));
4558 SCIP_CALL( SCIPbranchExecExtern(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4559 eventqueue, primal->cutoffbound, TRUE, &result) );
4561 }
4562 }
4563
4565 {
4566 /* branch on pseudo solution */
4567 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on pseudo solution with %d unfixed integers\n",
4568 SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNPseudoCands(branchcand));
4569 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
4570 primal->cutoffbound, TRUE, &result) );
4572 }
4573
4574 /* SCIP cannot guarantee convergence if it is necessary to branch on unbounded variables */
4575 if( result == SCIP_BRANCHED )
4576 {
4577 SCIP_VAR* var = stat->lastbranchvar;
4578
4581 {
4582 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
4583 "Starting spatial branch-and-bound on unbounded variable <%s> ([%g,%g]) - cannot guarantee finite termination.\n",
4585 stat->branchedunbdvar = TRUE;
4586 }
4587 }
4588
4589 switch( result )
4590 {
4591 case SCIP_CUTOFF:
4592 assert(tree->nchildren == 0);
4593 *cutoff = TRUE;
4594 SCIPsetDebugMsg(set, " -> branching rule detected cutoff\n");
4595 break;
4596 case SCIP_CONSADDED:
4597 assert(tree->nchildren == 0);
4598 if( nlpcands > 0 )
4599 {
4600 SCIPerrorMessage("LP branching rule added constraint, which was not allowed this time\n");
4601 return SCIP_INVALIDRESULT;
4602 }
4606 markRelaxsUnsolved(set, relaxation);
4607 break;
4608 case SCIP_REDUCEDDOM:
4609 assert(tree->nchildren == 0);
4613 markRelaxsUnsolved(set, relaxation);
4614 break;
4615 case SCIP_SEPARATED:
4616 assert(tree->nchildren == 0);
4617 assert(SCIPsepastoreGetNCuts(sepastore) > 0);
4620 markRelaxsUnsolved(set, relaxation);
4621 break;
4622 case SCIP_BRANCHED:
4623 assert(tree->nchildren >= 1);
4624 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4625 branched = TRUE;
4626
4627 /* increase the number of internal nodes */
4628 stat->ninternalnodes++;
4629 stat->ntotalinternalnodes++;
4630 break;
4631 case SCIP_DIDNOTFIND: /*lint -fallthrough*/
4632 case SCIP_DIDNOTRUN:
4633 /* all integer variables in the infeasible solution are fixed,
4634 * - if no continuous variables exist and all variables are known, the infeasible pseudo solution is completely
4635 * fixed, and the node can be cut off
4636 * - if at least one continuous variable exists or we do not know all variables due to external pricers, we
4637 * cannot resolve the infeasibility by branching -> solve LP (and maybe price in additional variables)
4638 */
4639 assert(tree->nchildren == 0);
4640 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4641 assert(SCIPbranchcandGetNPseudoCands(branchcand) == 0);
4642
4643 if( transprob->ncontvars == 0 && set->nactivepricers == 0 )
4644 {
4645 *cutoff = TRUE;
4646 SCIPsetDebugMsg(set, " -> cutoff because all variables are fixed in current node\n");
4647 }
4648 else
4649 {
4650 /* feasible LP solutions with all integers fixed must be feasible
4651 * if also no external branching candidates were available
4652 */
4654
4656 {
4657 SCIP_NODE* node;
4658
4659 /* as we hit the time or iteration limit or another interrupt (e.g., gap limit), we do not want to solve the LP again.
4660 * in order to terminate correctly, we create a "branching" with only one child node
4661 * that is a copy of the focusnode
4662 */
4663 SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) );
4664 assert(tree->nchildren >= 1);
4665 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4666 branched = TRUE;
4667 }
4668 else
4669 {
4670 SCIP_VERBLEVEL verblevel;
4671
4672 if( pricingaborted )
4673 {
4674 SCIPerrorMessage("pricing was aborted, but no branching could be created!\n");
4675 return SCIP_INVALIDRESULT;
4676 }
4677
4678 if( wasforcedlpsolve )
4679 {
4681 SCIPerrorMessage("LP was solved, all integers fixed, some constraint still infeasible, but no branching could be created!\n");
4682 return SCIP_INVALIDRESULT;
4683 }
4684
4685 verblevel = SCIP_VERBLEVEL_FULL;
4686
4687 if( !tree->forcinglpmessage && set->disp_verblevel == SCIP_VERBLEVEL_HIGH )
4688 {
4689 verblevel = SCIP_VERBLEVEL_HIGH;
4690
4691 /* remember that the forcing LP solving message was posted and do only post it again if the
4692 * verblevel is SCIP_VERBLEVEL_FULL
4693 */
4694 tree->forcinglpmessage = TRUE;
4695 }
4696
4697 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel,
4698 "(node %" SCIP_LONGINT_FORMAT ") forcing the solution of an LP (last LP %" SCIP_LONGINT_FORMAT ")...\n", stat->nnodes, stat->nlps);
4699
4700 /* solve the LP in the next loop */
4703 forcedlpsolve = TRUE; /* this LP must be solved without error - otherwise we have to abort */
4704 }
4705 }
4706 break;
4707 default:
4708 SCIPerrorMessage("invalid result code <%d> from SCIPbranchLP(), SCIPbranchExt() or SCIPbranchPseudo()\n", result);
4709 return SCIP_INVALIDRESULT;
4710 } /*lint !e788*/
4711 assert(*cutoff || solvelpagain || propagateagain || branched); /* something must have been done */
4713 assert(!solvelpagain || (!(*cutoff) && !branched));
4714 assert(!propagateagain || (!(*cutoff) && !branched));
4716 assert(branched == (tree->nchildren > 0));
4717
4718 /* apply found cuts */
4719 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4720 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain,
4722
4723 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4724 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4725
4726 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4728 }
4729
4730 /* check for immediate restart */
4731 *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart
4732 || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars)
4733 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4734
4735 SCIPsetDebugMsg(set, "node solving iteration %d finished: cutoff=%u, postpone=%u, propagateagain=%u, solverelaxagain=%u, solvelpagain=%u, nlperrors=%d, restart=%u\n",
4737 }
4738 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4739 assert(*cutoff || SCIPconflictGetNConflicts(conflict) == 0);
4740
4741 /* flush the conflict set storage */
4742 SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable) );
4743
4744 /* check for too many LP errors */
4745 if( nlperrors >= MAXNLPERRORS )
4746 {
4747 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- aborting\n", stat->nnodes, stat->nlps);
4748 return SCIP_LPERROR;
4749 }
4750
4751 /* check for final restart */
4752 restartfac = set->presol_subrestartfac;
4753 if( actdepth == 0 )
4754 restartfac = MIN(restartfac, set->presol_restartfac);
4755 *restart = *restart || (restartAllowed(set, stat) && (stat->userrestart
4756 || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars)
4757 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4758
4759 /* remember the last root LP solution */
4760 if( actdepth == 0 && !(*cutoff) && !(*unbounded) && !(*postpone) )
4761 {
4762 /* the root pseudo objective value and pseudo objective value should be equal in the root node */
4764
4765 SCIPprobStoreRootSol(transprob, set, stat, lp, SCIPtreeHasFocusNodeLP(tree));
4766 }
4767
4768 /* check for cutoff */
4769 if( *cutoff )
4770 {
4771 SCIPsetDebugMsg(set, "node is cut off\n");
4772
4773 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
4774 *infeasible = TRUE;
4775 SCIP_CALL( SCIPdebugRemoveNode(blkmem, set, focusnode) ); /*lint !e506 !e774*/
4776
4777 /* the LP might have been unbounded but not enforced, because the node is cut off anyway */
4778 *unbounded = FALSE;
4779 }
4780 else if( !(*unbounded) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && lp->looseobjvalinf == 0 )
4781 {
4782 /* update the regression statistic nlpbranchcands and LP objective value */
4783 int nlpbranchcands;
4784 SCIP_Real lpobjval;
4785
4786 /* get number of LP candidate variables */
4787 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpbranchcands, NULL, NULL) );
4788
4789 /* get LP objective value */
4790 lpobjval = SCIPlpGetObjval(lp, set, transprob);
4791 assert(lpobjval != SCIP_INVALID); /*lint !e777*/
4792
4793 /* add the observation to the regression */
4795 }
4796
4797 /* reset LP feastol to normal value, in case someone tightened it during node solving */
4799
4800 return SCIP_OKAY;
4801}
4802
4803/** if feasible, adds current solution to the solution storage */
4804static
4806 BMS_BLKMEM* blkmem, /**< block memory buffers */
4807 SCIP_SET* set, /**< global SCIP settings */
4808 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4809 SCIP_STAT* stat, /**< dynamic problem statistics */
4810 SCIP_PROB* origprob, /**< original problem */
4811 SCIP_PROB* transprob, /**< transformed problem after presolve */
4812 SCIP_PRIMAL* primal, /**< primal data */
4813 SCIP_RELAXATION* relaxation, /**< global relaxation data */
4814 SCIP_TREE* tree, /**< branch and bound tree */
4815 SCIP_REOPT* reopt, /**< reoptimization data structure */
4816 SCIP_LP* lp, /**< LP data */
4817 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4818 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4819 SCIP_Bool checksol /**< should the solution be checked? */
4820 )
4821{
4822 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
4823 SCIP_SOL* sol;
4824 SCIP_Bool foundsol;
4825
4826 /* found a feasible solution */
4828 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4829 {
4830 /* start clock for relaxation solutions */
4832
4833 SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4834
4835 SCIPsetDebugMsg(set, "found relaxation solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4836
4837 if( checksol || set->misc_exactsolve )
4838 {
4839 /* if we want to solve exactly, we have to check the solution exactly again */
4840 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4841 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4842 }
4843 else
4844 {
4845 SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4846 eventqueue, eventfilter, &sol, &foundsol) );
4847 }
4848
4849 if( foundsol )
4850 {
4851 stat->nrelaxsolsfound++;
4852
4853 if( primal->nbestsolsfound != oldnbestsolsfound )
4854 {
4855 stat->nrelaxbestsolsfound++;
4857 }
4858 }
4859
4860 /* stop clock for relaxation solutions */
4862 }
4863 else if( SCIPtreeHasFocusNodeLP(tree) )
4864 {
4866
4867 /* start clock for LP solutions */
4869
4870 /* add solution to storage */
4871 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4872
4873 SCIPsetDebugMsg(set, "found lp solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4874
4875 if( checksol || set->misc_exactsolve )
4876 {
4877 /* if we want to solve exactly, we have to check the solution exactly again */
4878 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4879 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4880 }
4881 else
4882 {
4883 SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4884 eventqueue, eventfilter, &sol, &foundsol) );
4885 }
4886
4887 if( foundsol )
4888 {
4889 stat->nlpsolsfound++;
4890
4891 if( primal->nbestsolsfound != oldnbestsolsfound )
4892 {
4893 stat->nlpbestsolsfound++;
4895 }
4896 }
4897
4898 /* stop clock for LP solutions */
4899 SCIPclockStop(stat->lpsoltime, set);
4900 }
4901 else
4902 {
4903 /* start clock for pseudo solutions */
4905
4906 /* add solution to storage */
4907 SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4908
4909 SCIPsetDebugMsg(set, "found pseudo solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4910
4911 if( checksol || set->misc_exactsolve )
4912 {
4913 /* if we want to solve exactly, we have to check the solution exactly again */
4914 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4915 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4916 }
4917 else
4918 {
4919 SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4920 eventqueue, eventfilter, &sol, &foundsol) );
4921 }
4922
4923 /* stop clock for pseudo solutions */
4925
4926 if( foundsol )
4927 {
4928 stat->npssolsfound++;
4929
4930 if( primal->nbestsolsfound != oldnbestsolsfound )
4931 {
4932 stat->npsbestsolsfound++;
4934 }
4935 }
4936 }
4937
4938 return SCIP_OKAY;
4939}
4940
4941/** main solving loop */
4943 BMS_BLKMEM* blkmem, /**< block memory buffers */
4944 SCIP_SET* set, /**< global SCIP settings */
4945 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4946 SCIP_STAT* stat, /**< dynamic problem statistics */
4947 SCIP_MEM* mem, /**< block memory pools */
4948 SCIP_PROB* origprob, /**< original problem */
4949 SCIP_PROB* transprob, /**< transformed problem after presolve */
4950 SCIP_PRIMAL* primal, /**< primal data */
4951 SCIP_TREE* tree, /**< branch and bound tree */
4952 SCIP_REOPT* reopt, /**< reoptimization data structure */
4953 SCIP_LP* lp, /**< LP data */
4954 SCIP_RELAXATION* relaxation, /**< global relaxation data */
4955 SCIP_PRICESTORE* pricestore, /**< pricing storage */
4956 SCIP_SEPASTORE* sepastore, /**< separation storage */
4957 SCIP_CUTPOOL* cutpool, /**< global cut pool */
4958 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
4959 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4960 SCIP_CONFLICT* conflict, /**< conflict analysis data */
4961 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4962 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4963 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4964 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4965 SCIP_Bool* restart /**< should solving process be started again with presolving? */
4966 )
4967{
4968 SCIP_NODESEL* nodesel;
4969 SCIP_NODE* focusnode;
4972 SCIP_Real restartfac;
4973 SCIP_Real restartconfnum;
4974 int nnodes;
4975 int depth;
4976 SCIP_Bool cutoff;
4977 SCIP_Bool postpone;
4978 SCIP_Bool unbounded;
4979 SCIP_Bool infeasible;
4980 SCIP_Bool foundsol;
4981
4982 assert(set != NULL);
4983 assert(blkmem != NULL);
4984 assert(stat != NULL);
4985 assert(transprob != NULL);
4986 assert(tree != NULL);
4987 assert(lp != NULL);
4988 assert(pricestore != NULL);
4989 assert(sepastore != NULL);
4990 assert(branchcand != NULL);
4991 assert(cutpool != NULL);
4992 assert(delayedcutpool != NULL);
4993 assert(primal != NULL);
4994 assert(eventfilter != NULL);
4995 assert(eventqueue != NULL);
4996 assert(restart != NULL);
4997
4998 /* check for immediate restart (if problem solving marked to be restarted was aborted) */
4999 restartfac = set->presol_subrestartfac;
5000 if( SCIPtreeGetCurrentDepth(tree) == 0 )
5001 restartfac = MIN(restartfac, set->presol_restartfac);
5002 *restart = restartAllowed(set, stat) && (stat->userrestart
5003 || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars)
5004 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars)) );
5005
5006 /* calculate the number of successful conflict analysis calls that should trigger a restart */
5007 if( set->conf_restartnum > 0 )
5008 {
5009 int i;
5010
5011 restartconfnum = (SCIP_Real)set->conf_restartnum;
5012 for( i = 0; i < stat->nconfrestarts; ++i )
5013 restartconfnum *= set->conf_restartfac;
5014 }
5015 else
5017 assert(restartconfnum >= 0.0);
5018
5019 /* switch status to UNKNOWN */
5021
5022 focusnode = NULL;
5023 nextnode = NULL;
5024 unbounded = FALSE;
5025 postpone = FALSE;
5026
5027 while( !SCIPsolveIsStopped(set, stat, TRUE) && !(*restart) )
5028 {
5029 SCIP_Longint nsuccessconflicts;
5030 SCIP_Bool afternodeheur;
5031 SCIP_Bool stopped;
5032 SCIP_Bool branched;
5033
5035
5036 foundsol = FALSE;
5037 infeasible = FALSE;
5038
5039 do
5040 {
5041 /* update the memory saving flag, switch algorithms respectively */
5042 SCIPstatUpdateMemsaveMode(stat, set, messagehdlr, mem);
5043
5044 /* get the current node selector */
5045 nodesel = SCIPsetGetNodesel(set, stat);
5046
5047 /* inform tree about the current node selector */
5048 SCIP_CALL( SCIPtreeSetNodesel(tree, set, messagehdlr, stat, nodesel) );
5049
5050 /* the next node was usually already selected in the previous solving loop before the primal heuristics were
5051 * called, because they need to know, if the next node will be a child/sibling (plunging) or not;
5052 * if the heuristics found a new best solution that cut off some of the nodes, the node selector must be called
5053 * again, because the selected next node may be invalid due to cut off
5054 */
5055 if( nextnode == NULL )
5056 {
5057 /* select next node to process */
5058 SCIP_CALL( SCIPnodeselSelect(nodesel, set, &nextnode) );
5059 }
5060 focusnode = nextnode;
5061 nextnode = NULL;
5063
5064 /* start node activation timer */
5066
5067 /* focus selected node */
5068 SCIP_CALL( SCIPnodeFocus(&focusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt,
5069 lp, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, FALSE, FALSE) );
5070 if( cutoff )
5071 stat->ndelayedcutoffs++;
5072
5073 /* stop node activation timer */
5075
5077 }
5078 while( cutoff ); /* select new node, if the current one was located in a cut off subtree */
5079
5080 assert(SCIPtreeGetCurrentNode(tree) == focusnode);
5081 assert(SCIPtreeGetFocusNode(tree) == focusnode);
5082
5083 /* if no more node was selected, we finished optimization */
5084 if( focusnode == NULL )
5085 {
5086 assert(SCIPtreeGetNNodes(tree) == 0);
5087 break;
5088 }
5089
5090 /* update maxdepth and node count statistics */
5091 depth = SCIPnodeGetDepth(focusnode);
5092 stat->maxdepth = MAX(stat->maxdepth, depth);
5093 stat->maxtotaldepth = MAX(stat->maxtotaldepth, depth);
5094 stat->nnodes++;
5095 stat->ntotalnodes++;
5096
5097 /* update reference bound statistic, if available */
5098 if( SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), stat->referencebound) )
5099 stat->nnodesaboverefbound++;
5100
5101 /* issue NODEFOCUSED event */
5103 SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
5104 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
5105
5106 /* solve focus node */
5107 SCIP_CALL( solveNode(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation,
5108 pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter, eventqueue,
5109 cliquetable, &cutoff, &postpone, &unbounded, &infeasible, restart, &afternodeheur, &stopped) );
5110 assert(!cutoff || infeasible);
5112 assert(SCIPtreeGetCurrentNode(tree) == focusnode);
5113 assert(SCIPtreeGetFocusNode(tree) == focusnode);
5114
5115 branched = (tree->nchildren > 0);
5116
5117 if( stopped )
5118 break;
5119
5120 /* check for restart */
5121 if( !(*restart) && !postpone )
5122 {
5123 /* change color of node in visualization */
5124 SCIPvisualSolvedNode(stat->visual, set, stat, focusnode);
5125
5126 /* check, if the current solution is feasible */
5127 if( !infeasible )
5128 {
5129 SCIP_Bool feasible;
5130
5131 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
5132 assert(!cutoff);
5133
5134 /* in the unbounded case, we check the solution w.r.t. the original problem, because we do not want to rely
5135 * on the LP feasibility and integrality is not checked for unbounded solutions, anyway
5136 */
5137 if( unbounded )
5138 {
5139 SCIP_SOL* sol;
5140
5142 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
5143 {
5144 SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) );
5145 }
5146 else if( SCIPtreeHasFocusNodeLP(tree) )
5147 {
5148 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
5149 }
5150 else
5151 {
5152 SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
5153 }
5155
5156 SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) );
5157 }
5158 else
5159 feasible = TRUE;
5160
5161 /* node solution is feasible: add it to the solution store */
5162 if( feasible )
5163 {
5164 SCIP_CALL( addCurrentSolution(blkmem, set, messagehdlr, stat, origprob, transprob, primal, relaxation, tree, reopt,
5165 lp, eventqueue, eventfilter, FALSE) );
5166
5167 /* update the cutoff pointer if the new solution made the cutoff bound equal to the lower bound */
5168 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, &cutoff) );
5169
5170 /* increment number of feasible leaf nodes */
5171 stat->nfeasleaves++;
5172
5173 /* issue NODEFEASIBLE event */
5175 SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
5176 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
5177
5178 if( set->reopt_enable )
5179 {
5180 assert(reopt != NULL);
5181 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp,
5182 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5183 focusnode->lowerbound, tree->effectiverootdepth) );
5184 }
5185 }
5186 }
5187 else if( !unbounded || branched )
5188 {
5189 /* node solution is not feasible */
5190 if( !branched )
5191 {
5192 assert(tree->nchildren == 0);
5193
5194 /* change color of node in visualization output */
5195 SCIPvisualCutoffNode(stat->visual, set, stat, focusnode, TRUE);
5196
5197 /* issue NODEINFEASIBLE event */
5199
5200 /* we only increase the number of objective leaf nodes if we hit the LP objective limit; we might have also
5201 * hit the objective limit at a node that is actually infeasible, or a dual reduction led to an infeasibility prior
5202 * to LP solving such that the node will be marked as infeasible */
5204 stat->nobjleaves++;
5205 else
5206 stat->ninfeasleaves++;
5207
5208 if( set->reopt_enable )
5209 {
5210 assert(reopt != NULL);
5211 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEINFEASIBLE, lp,
5212 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5213 focusnode->lowerbound, tree->effectiverootdepth) );
5214 }
5215
5216 /* increase the cutoff counter of the branching variable */
5217 if( stat->lastbranchvar != NULL )
5218 {
5219 SCIP_CALL( SCIPvarIncCutoffSum(stat->lastbranchvar, blkmem, set, stat, stat->lastbranchdir, stat->lastbranchvalue, 1.0) );
5220 }
5221 /**@todo if last branching variable is unknown, retrieve it from the nodes' boundchg arrays */
5222 }
5223 else
5224 {
5225 assert(tree->nchildren > 0);
5226
5227 /* issue NODEBRANCHED event */
5229
5230 if( set->reopt_enable )
5231 {
5232 assert(reopt != NULL);
5233 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEBRANCHED, lp,
5234 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5235 focusnode->lowerbound, tree->effectiverootdepth) );
5236 }
5237 }
5238 SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
5239 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
5240 }
5242
5243 /* if no branching was created, the node was not cut off, but its lower bound is still smaller than
5244 * the cutoff bound, we have to branch on a non-fixed variable;
5245 * this can happen, if we want to solve exactly, the current solution was declared feasible by the
5246 * constraint enforcement, but in exact solution checking it was found out to be infeasible;
5247 * in this case, no branching would have been generated by the enforcement of constraints, but we
5248 * have to further investigate the current sub tree;
5249 * note that we must not check tree->nchildren > 0 here to determine whether we branched, we rather
5250 * check it directly after solveNode() and store the result, because an event handler might impose a
5251 * new cutoff bound (as is the case in ParaSCIP)
5252 */
5253 if( !cutoff && !unbounded && !branched && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound )
5254 {
5256
5257 assert(set->misc_exactsolve);
5258
5259 do
5260 {
5262 if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 )
5263 {
5264 if( transprob->ncontvars > 0 )
5265 {
5266 /**@todo call PerPlex */
5267 SCIPerrorMessage("cannot branch on all-fixed LP -- have to call PerPlex instead\n");
5268 }
5269 }
5270 else
5271 {
5272 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
5273 eventqueue, primal->cutoffbound, FALSE, &result) );
5275 }
5276 }
5277 while( result == SCIP_REDUCEDDOM );
5278 }
5280
5281 /* select node to process in next solving loop; the primal heuristics need to know whether a child/sibling
5282 * (plunging) will be selected as next node or not
5283 */
5284 SCIP_CALL( SCIPnodeselSelect(nodesel, set, &nextnode) );
5286
5287 /* call primal heuristics that should be applied after the node was solved */
5288 nnodes = SCIPtreeGetNNodes(tree);
5289 stopped = SCIPsolveIsStopped(set, stat, FALSE);
5290 if( !afternodeheur && (!cutoff || nnodes > 0) && !stopped )
5291 {
5292 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, nextnode, SCIP_HEURTIMING_AFTERNODE,
5293 cutoff, &foundsol, &unbounded) );
5295
5296 stopped = SCIPsolveIsStopped(set, stat, FALSE);
5297 }
5298
5299 /* if the heuristics found a new best solution that cut off some of the nodes, the node selector must be called
5300 * again, because the selected next node may be invalid due to cut off
5301 */
5302 assert(!tree->cutoffdelayed);
5303
5304 if( nnodes != SCIPtreeGetNNodes(tree) || stopped )
5305 nextnode = NULL;
5306 }
5307 else if( !infeasible && !postpone )
5308 {
5309 /* The current solution was not proven to be infeasible, but due to the restart, this does not mean that it is
5310 * feasible, we might just have skipped the check. Thus, we try to add it to the solution store, but check it
5311 * again.
5312 */
5313 SCIP_CALL( addCurrentSolution(blkmem, set, messagehdlr, stat, origprob, transprob, primal, relaxation, tree, reopt, lp,
5314 eventqueue, eventfilter, TRUE) );
5315
5316 if( set->reopt_enable )
5317 {
5318 assert(reopt != NULL);
5319 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp,
5320 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode, focusnode->lowerbound,
5321 tree->effectiverootdepth) );
5322 }
5323 }
5324 /* we want to put the focusnode back into the leaf queue if it was postponed */
5325 else if( postpone )
5326 {
5328
5329 /* @todo should we re-install the old focus node in order to somehow set the forks more clever? */
5330 SCIP_CALL( SCIPnodeFocus(&newfocusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
5331 branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, TRUE, FALSE) );
5332 }
5333 /* compute number of successfully applied conflicts */
5337
5338 /* trigger restart due to conflicts and the restart parameters allow another restart */
5340 {
5341 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
5342 "(run %d, node %" SCIP_LONGINT_FORMAT ") restarting after %" SCIP_LONGINT_FORMAT " successful conflict analysis calls\n",
5343 stat->nruns, stat->nnodes, nsuccessconflicts);
5344 *restart = TRUE;
5345
5346 stat->nconfrestarts++;
5347 }
5348
5349 /* restart if the userrestart was set to true, we have still some nodes left and the restart parameters allow
5350 * another restart
5351 */
5352 *restart = *restart || (stat->userrestart && SCIPtreeGetNNodes(tree) > 0 && restartAllowed(set, stat));
5353 if( restartAllowed(set, stat) && set->limit_autorestartnodes == stat->nnodes && stat->ntotalnodes - stat->nruns + 1 == set->limit_autorestartnodes )
5354 {
5355 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
5356 "(run %d, node %" SCIP_LONGINT_FORMAT ") restarting: triggering parameter controlled restart)\n",
5357 stat->nruns, stat->nnodes);
5358 *restart = TRUE;
5359 }
5360 /* if restart limit was exceeded, change the status; if status is different from unknown, ie some other limit was
5361 * hit, leave it unchanged
5362 */
5363 if( *restart && stat->status == SCIP_STATUS_UNKNOWN && set->limit_restarts >= 0 && stat->nruns > set->limit_restarts )
5364 {
5365 *restart = FALSE;
5367 }
5368
5369 /* display node information line */
5370 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, (SCIPnodeGetDepth(focusnode) == 0) && infeasible && !foundsol, TRUE) );
5371
5372 SCIPsetDebugMsg(set, "Processing of node %" SCIP_LONGINT_FORMAT " in depth %d finished. %d siblings, %d children, %d leaves left\n",
5373 stat->nnodes, SCIPnodeGetDepth(focusnode), tree->nsiblings, tree->nchildren, SCIPtreeGetNLeaves(tree));
5374 SCIPsetDebugMsg(set, "**********************************************************************\n");
5375 }
5376
5377 /* update the primal-dual integral if node or time limits were hit or an interruption signal was called */
5378 if( SCIPsolveIsStopped(set, stat, TRUE) )
5379 {
5381 }
5382
5384
5385 SCIPsetDebugMsg(set, "Problem solving finished with status %d (restart=%u, userrestart=%u)\n", stat->status, *restart, stat->userrestart);
5386
5387 /* cuts off nodes with lower bound is not better than given cutoff bound, manually; this necessary to ensure that
5388 * SCIP terminates with a proper solve stage
5389 */
5390 SCIP_CALL( SCIPtreeCutoff(tree, reopt, blkmem, set, stat, eventfilter, eventqueue, lp, primal->cutoffbound) );
5391
5392 /* if the current node is the only remaining node, and if its lower bound exceeds the upper bound, we have
5393 * to delete it manually in order to get to the SOLVED stage instead of thinking, that only the gap limit
5394 * was reached (this may happen, if the current node is the one defining the global lower bound and a
5395 * feasible solution with the same value was found at this node)
5396 */
5397 if( tree->focusnode != NULL && SCIPtreeGetNNodes(tree) == 0
5398 && SCIPsetIsGE(set, tree->focusnode->lowerbound, primal->cutoffbound) )
5399 {
5400 if( set->reopt_enable )
5401 {
5402 assert(reopt != NULL);
5404 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode, tree->focusnode->lowerbound,
5405 tree->effectiverootdepth) );
5406 }
5407
5408 focusnode = NULL;
5409 SCIP_CALL( SCIPnodeFocus(&focusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
5410 branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, FALSE, FALSE) );
5411 }
5412
5413 /* check whether we finished solving */
5414 if( SCIPtreeGetNNodes(tree) == 0 && SCIPtreeGetCurrentNode(tree) == NULL )
5415 {
5416 /* no restart necessary */
5417 *restart = FALSE;
5418
5419 /* set the solution status */
5421 {
5422 if( primal->nsols > 0 )
5423 {
5424 /* switch status to UNBOUNDED */
5426 }
5427 else
5428 {
5429 /* switch status to INFORUNB */
5431 }
5432 }
5433 else if( primal->nlimsolsfound == 0 )
5434 {
5435 assert(primal->nsols == 0 || SCIPsetIsGT(set, SCIPsolGetObj(primal->sols[0], set, transprob, origprob),
5436 SCIPprobInternObjval(transprob, origprob, set, SCIPprobGetObjlim(transprob, set))));
5437
5438 /* switch status to INFEASIBLE */
5440 }
5441 else
5442 {
5443 /* switch status to OPTIMAL */
5445 }
5446 }
5447
5448 return SCIP_OKAY;
5449}
SCIP_RETCODE SCIPbranchcandGetLPCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition branch.c:405
int SCIPbranchcandGetNExternCands(SCIP_BRANCHCAND *branchcand)
Definition branch.c:507
SCIP_RETCODE SCIPbranchExecPseudo(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition branch.c:2769
int SCIPbranchcandGetNPrioExternCands(SCIP_BRANCHCAND *branchcand)
Definition branch.c:517
void SCIPbranchcandClearExternCands(SCIP_BRANCHCAND *branchcand)
Definition branch.c:697
int SCIPbranchcandGetExternMaxPrio(SCIP_BRANCHCAND *branchcand)
Definition branch.c:497
int SCIPbranchcandGetNPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition branch.c:852
int SCIPbranchcandGetNPrioLPCands(SCIP_BRANCHCAND *branchcand)
Definition branch.c:487
SCIP_RETCODE SCIPbranchExecExtern(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition branch.c:2638
SCIP_RETCODE SCIPbranchExecLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition branch.c:2536
int SCIPbranchcandGetLPMaxPrio(SCIP_BRANCHCAND *branchcand)
Definition branch.c:477
internal methods for branching rules and branching candidate storage
SCIP_VAR * h
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition clock.c:360
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition clock.c:290
SCIP_Real SCIPclockGetLastTime(SCIP_CLOCK *clck)
Definition clock.c:529
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition clock.c:438
internal methods for clocks and timing issues
SCIP_Longint SCIPgetConcurrentMemTotal(SCIP *scip)
Definition concurrent.c:288
int SCIPgetNConcurrentSolvers(SCIP *scip)
Definition concurrent.c:117
helper functions for concurrent scip solvers
internal methods for conflict analysis
int SCIPconflictGetNConflicts(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNInfeasibleLPSuccess(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNBoundexceedingLPSuccess(SCIP_CONFLICT *conflict)
SCIP_RETCODE SCIPconflictAnalyzePseudo(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *success)
SCIP_RETCODE SCIPconflictAnalyzeLP(SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *success)
SCIP_Longint SCIPconflictGetNPseudoSuccess(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNPropSuccess(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNStrongbranchSuccess(SCIP_CONFLICT *conflict)
SCIP_RETCODE SCIPconflictFlushConss(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable)
SCIP_RETCODE SCIPconshdlrSeparateLP(SCIP_CONSHDLR *conshdlr, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_SEPASTORE *sepastore, int depth, SCIP_Bool execdelayed, SCIP_RESULT *result)
Definition cons.c:2877
SCIP_RETCODE SCIPconshdlrEnforceRelaxSol(SCIP_CONSHDLR *conshdlr, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_SEPASTORE *sepastore, SCIP_SOL *relaxsol, SCIP_Bool solinfeasible, SCIP_RESULT *result)
Definition cons.c:3163
SCIP_RETCODE SCIPconshdlrSeparateSol(SCIP_CONSHDLR *conshdlr, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_SEPASTORE *sepastore, SCIP_SOL *sol, int depth, SCIP_Bool execdelayed, SCIP_RESULT *result)
Definition cons.c:3034
SCIP_RETCODE SCIPconshdlrEnforceLPSol(SCIP_CONSHDLR *conshdlr, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_SEPASTORE *sepastore, SCIP_Bool solinfeasible, SCIP_RESULT *result)
Definition cons.c:3351
SCIP_RETCODE SCIPconshdlrInitLP(SCIP_CONSHDLR *conshdlr, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_Bool initkeptconss, SCIP_Bool *cutoff)
Definition cons.c:2770
SCIP_RETCODE SCIPconshdlrPropagate(SCIP_CONSHDLR *conshdlr, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, int depth, SCIP_Bool fullpropagation, SCIP_Bool execdelayed, SCIP_Bool instrongbranching, SCIP_PROPTIMING proptiming, SCIP_RESULT *result)
Definition cons.c:3822
SCIP_RETCODE SCIPconshdlrEnforcePseudoSol(SCIP_CONSHDLR *conshdlr, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_BRANCHCAND *branchcand, SCIP_Bool solinfeasible, SCIP_Bool objinfeasible, SCIP_Bool forced, SCIP_RESULT *result)
Definition cons.c:3556
internal methods for constraints and constraint handlers
SCIP_RETCODE SCIPcutpoolSeparate(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_SOL *sol, SCIP_Bool cutpoolisdelayed, SCIP_Bool root, SCIP_RESULT *result)
Definition cutpool.c:835
internal methods for storing cuts in a cut pool
#define SCIPdebugRemoveNode(blkmem, set, node)
Definition debug.h:288
#define NULL
Definition def.h:267
#define SCIP_Longint
Definition def.h:158
#define SCIP_REAL_MAX
Definition def.h:174
#define SCIP_INVALID
Definition def.h:193
#define MIN(x, y)
Definition def.h:243
#define SCIP_Real
Definition def.h:173
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define SCIP_LONGINT_FORMAT
Definition def.h:165
#define SCIPABORT()
Definition def.h:346
#define SCIP_REAL_MIN
Definition def.h:175
#define REALABS(x)
Definition def.h:197
#define SCIP_CALL(x)
Definition def.h:374
SCIP_RETCODE SCIPdispPrintLine(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, FILE *file, SCIP_Bool forcedisplay, SCIP_Bool endline)
Definition disp.c:415
internal methods for displaying runtime statistics
SCIP_RETCODE SCIPeventChgNode(SCIP_EVENT *event, SCIP_NODE *node)
Definition event.c:1317
SCIP_RETCODE SCIPeventProcess(SCIP_EVENT *event, SCIP_SET *set, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter)
Definition event.c:1574
SCIP_RETCODE SCIPeventChgType(SCIP_EVENT *event, SCIP_EVENTTYPE eventtype)
Definition event.c:1040
internal methods for managing events
#define nnodes
Definition gastrans.c:74
SCIP_Real SCIPgetOrigObjoffset(SCIP *scip)
Definition scip_prob.c:1319
SCIP_Real SCIPgetTransObjscale(SCIP *scip)
Definition scip_prob.c:1390
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
Definition lpi_clp.cpp:3919
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition misc.c:11184
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
Definition lp.c:17115
SCIP_PROPTIMING SCIPconshdlrGetPropTiming(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5250
SCIP_Bool SCIPconshdlrWasSolSeparationDelayed(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5210
int SCIPconshdlrGetSepaPriority(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5100
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4197
SCIP_Bool SCIPconshdlrWasLPSeparationDelayed(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5200
SCIP_Bool SCIPconshdlrWasPropagationDelayed(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5220
int SCIPheurGetPriority(SCIP_HEUR *heur)
Definition heur.c:1514
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1453
BMS_BUFMEM * SCIPbuffer(SCIP *scip)
Definition scip_mem.c:72
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition tree.c:7434
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition tree.c:7464
SCIP_Bool SCIPnodeIsActive(SCIP_NODE *node)
Definition tree.c:8199
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition tree.c:7454
SCIP_Bool SCIPnodeIsPropagatedAgain(SCIP_NODE *node)
Definition tree.c:8209
SCIP_SYNCSTORE * SCIPgetSyncstore(SCIP *scip)
const char * SCIPpricerGetName(SCIP_PRICER *pricer)
Definition pricer.c:600
SCIP_Bool SCIPpropWasDelayed(SCIP_PROP *prop)
Definition prop.c:1146
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition prop.c:941
int SCIPpropGetPriority(SCIP_PROP *prop)
Definition prop.c:961
SCIP_PROPTIMING SCIPpropGetTimingmask(SCIP_PROP *prop)
Definition prop.c:1276
void SCIPrelaxMarkUnsolved(SCIP_RELAX *relax)
Definition relax.c:720
const char * SCIPrelaxGetName(SCIP_RELAX *relax)
Definition relax.c:542
int SCIPrelaxGetPriority(SCIP_RELAX *relax)
Definition relax.c:562
SCIP_Bool SCIPsepaWasSolDelayed(SCIP_SEPA *sepa)
Definition sepa.c:1109
int SCIPsepaGetPriority(SCIP_SEPA *sepa)
Definition sepa.c:763
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition sepa.c:743
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
Definition sepa.c:1099
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition scip_sol.c:3309
SCIP_RETCODE SCIPprintRay(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:2034
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Real SCIPgetGap(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLimSolsFound(SCIP *scip)
void SCIPstoreSolutionGap(SCIP *scip)
SCIP_Longint SCIPgetNBestSolsFound(SCIP *scip)
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition var.c:17620
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition var.c:17789
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition var.c:18452
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_BDCHGINFO * SCIPvarGetBdchgInfoLb(SCIP_VAR *var, int pos)
Definition var.c:18478
int SCIPvarGetNBdchgInfosUb(SCIP_VAR *var)
Definition var.c:18510
SCIP_BDCHGINFO * SCIPvarGetBdchgInfoUb(SCIP_VAR *var, int pos)
Definition var.c:18498
int SCIPvarGetNBdchgInfosLb(SCIP_VAR *var)
Definition var.c:18490
void SCIPregressionAddObservation(SCIP_REGRESSION *regression, SCIP_Real x, SCIP_Real y)
Definition misc.c:381
SCIP_RETCODE SCIPheurExec(SCIP_HEUR *heur, SCIP_SET *set, SCIP_PRIMAL *primal, int depth, int lpstateforkdepth, SCIP_HEURTIMING heurtiming, SCIP_Bool nodeinfeasible, int *ndelayedheurs, SCIP_RESULT *result)
Definition heur.c:1263
SCIP_Bool SCIPheurShouldBeExecuted(SCIP_HEUR *heur, int depth, int lpstateforkdepth, SCIP_HEURTIMING heurtiming, SCIP_Bool *delayed)
Definition heur.c:1201
internal methods for primal heuristics
return SCIP_OKAY
SCIP_Bool lperror
heurdata nlpiterations
int depth
SCIP_Bool cutoff
static SCIP_SOL * sol
int nlpcands
SCIP_Longint nlps
int r
SCIP_VAR ** lpcands
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
SCIP_Real * lpcandsfrac
static SCIP_Bool propagate
static SCIP_VAR ** vars
void SCIPresetInterrupted(void)
Definition interrupt.c:190
SCIP_Bool SCIPterminated(void)
Definition interrupt.c:171
SCIP_Bool SCIPinterrupted(void)
Definition interrupt.c:163
methods for catching the user CTRL-C interrupt
SCIP_RETCODE SCIPlpFlush(SCIP_LP *lp, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_EVENTQUEUE *eventqueue)
Definition lp.c:8671
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition lp.c:13103
void SCIPlpSetIsRelax(SCIP_LP *lp, SCIP_Bool relax)
Definition lp.c:17784
SCIP_Bool SCIPlpIsRelax(SCIP_LP *lp)
Definition lp.c:17797
SCIP_Real SCIPlpGetObjval(SCIP_LP *lp, SCIP_SET *set, SCIP_PROB *prob)
Definition lp.c:13119
SCIP_RETCODE SCIPlpGetProvedLowerbound(SCIP_LP *lp, SCIP_SET *set, SCIP_Real *bound)
Definition lp.c:16491
SCIP_LPI * SCIPlpGetLPI(SCIP_LP *lp)
Definition lp.c:17774
SCIP_RETCODE SCIPlpRemoveRedundantRows(SCIP_LP *lp, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter)
Definition lp.c:15929
SCIP_Bool SCIPlpDiving(SCIP_LP *lp)
Definition lp.c:17847
SCIP_Bool SCIPlpIsSolved(SCIP_LP *lp)
Definition lp.c:17807
SCIP_Real SCIPlpGetGlobalPseudoObjval(SCIP_LP *lp, SCIP_SET *set, SCIP_PROB *prob)
Definition lp.c:13270
int SCIPlpGetNCols(SCIP_LP *lp)
Definition lp.c:17575
SCIP_RETCODE SCIPlpSolveAndEval(SCIP_LP *lp, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_PROB *prob, SCIP_Longint itlim, SCIP_Bool limitresolveiters, SCIP_Bool aging, SCIP_Bool keepsol, SCIP_Bool *lperror)
Definition lp.c:12413
void SCIPlpResetFeastol(SCIP_LP *lp, SCIP_SET *set)
Definition lp.c:10281
SCIP_RETCODE SCIPlpGetPrimalRay(SCIP_LP *lp, SCIP_SET *set, SCIP_Real *ray)
Definition lp.c:14991
int SCIPlpGetNRows(SCIP_LP *lp)
Definition lp.c:17622
SCIP_Real SCIPlpGetPseudoObjval(SCIP_LP *lp, SCIP_SET *set, SCIP_PROB *prob)
Definition lp.c:13302
internal methods for LP management
interface methods for specific LP solvers
size_t BMSgetNUsedBufferMemory(BMS_BUFMEM *buffer)
Definition memory.c:3121
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:130
struct BMS_BlkMem BMS_BLKMEM
Definition memory.h:437
void SCIPmessagePrintWarning(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition message.c:427
void SCIPmessagePrintVerbInfo(SCIP_MESSAGEHDLR *messagehdlr, SCIP_VERBLEVEL verblevel, SCIP_VERBLEVEL msgverblevel, const char *formatstr,...)
Definition message.c:678
SCIP_RETCODE SCIPnodeselSelect(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE **selnode)
Definition nodesel.c:1012
internal methods for node selectors and node priority queues
SCIP_RETCODE SCIPpricerExec(SCIP_PRICER *pricer, SCIP_SET *set, SCIP_PROB *prob, SCIP_LP *lp, SCIP_PRICESTORE *pricestore, SCIP_Real *lowerbound, SCIP_Bool *stopearly, SCIP_RESULT *result)
Definition pricer.c:474
internal methods for variable pricers
void SCIPpricestoreStartInitialLP(SCIP_PRICESTORE *pricestore)
Definition pricestore.c:157
SCIP_RETCODE SCIPpricestoreApplyVars(SCIP_PRICESTORE *pricestore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_LP *lp)
Definition pricestore.c:480
int SCIPpricestoreGetNVars(SCIP_PRICESTORE *pricestore)
Definition pricestore.c:609
SCIP_RETCODE SCIPpricestoreAddProbVars(SCIP_PRICESTORE *pricestore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue)
Definition pricestore.c:354
SCIP_RETCODE SCIPpricestoreAddVar(SCIP_PRICESTORE *pricestore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp, SCIP_VAR *var, SCIP_Real score, SCIP_Bool root)
Definition pricestore.c:181
int SCIPpricestoreGetNBoundResets(SCIP_PRICESTORE *pricestore)
Definition pricestore.c:620
void SCIPpricestoreEndInitialLP(SCIP_PRICESTORE *pricestore)
Definition pricestore.c:169
SCIP_RETCODE SCIPpricestoreResetBounds(SCIP_PRICESTORE *pricestore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue)
Definition pricestore.c:569
internal methods for storing priced variables
SCIP_RETCODE SCIPprimalTrySolFree(SCIP_PRIMAL *primal, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition primal.c:1588
SCIP_RETCODE SCIPprimalTrySol(SCIP_PRIMAL *primal, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition primal.c:1518
SCIP_RETCODE SCIPprimalAddSolFree(SCIP_PRIMAL *primal, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_SOL **sol, SCIP_Bool *stored)
Definition primal.c:1294
internal methods for collecting primal CIP solutions and primal informations
SCIP_Real SCIPprobGetObjlim(SCIP_PROB *prob, SCIP_SET *set)
Definition prob.c:2362
SCIP_Real SCIPprobExternObjval(SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_SET *set, SCIP_Real objval)
Definition prob.c:2157
void SCIPprobStoreRootSol(SCIP_PROB *prob, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_Bool roothaslp)
Definition prob.c:1778
SCIP_Bool SCIPprobAllColsInLP(SCIP_PROB *prob, SCIP_SET *set, SCIP_LP *lp)
Definition prob.c:2350
void SCIPprobUpdateBestRootSol(SCIP_PROB *prob, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition prob.c:1805
SCIP_Real SCIPprobInternObjval(SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_SET *set, SCIP_Real objval)
Definition prob.c:2179
internal methods for storing and manipulating the main problem
SCIP_RETCODE SCIPpropExec(SCIP_PROP *prop, SCIP_SET *set, SCIP_STAT *stat, int depth, SCIP_Bool execdelayed, SCIP_Bool instrongbranching, SCIP_PROPTIMING proptiming, SCIP_RESULT *result)
Definition prop.c:645
internal methods for propagators
public methods for managing constraints
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebug(x)
Definition pub_message.h:93
public data structures and miscellaneous methods
public methods for variable pricers
public methods for propagators
public methods for relaxation handlers
public methods for separators
public methods for branch and bound tree
public methods for problem variables
void SCIPrelaxationSetSolValid(SCIP_RELAXATION *relaxation, SCIP_Bool isvalid, SCIP_Bool includeslp)
Definition relax.c:795
SCIP_Real SCIPrelaxationGetSolObj(SCIP_RELAXATION *relaxation)
Definition relax.c:839
SCIP_Bool SCIPrelaxIsSolved(SCIP_RELAX *relax, SCIP_STAT *stat)
Definition relax.c:708
SCIP_RETCODE SCIPrelaxExec(SCIP_RELAX *relax, SCIP_SET *set, SCIP_TREE *tree, SCIP_STAT *stat, int depth, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition relax.c:353
SCIP_Bool SCIPrelaxationIsLpIncludedForSol(SCIP_RELAXATION *relaxation)
Definition relax.c:818
SCIP_Bool SCIPrelaxationIsSolValid(SCIP_RELAXATION *relaxation)
Definition relax.c:808
internal methods for relaxators
SCIP_RETCODE SCIPreoptCheckCutoff(SCIP_REOPT *reopt, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_NODE *node, SCIP_EVENTTYPE eventtype, SCIP_LP *lp, SCIP_LPSOLSTAT lpsolstat, SCIP_Bool isrootnode, SCIP_Bool isfocusnode, SCIP_Real lowerbound, int effectiverootdepth)
Definition reopt.c:5989
SCIP_RETCODE SCIPreoptApplyCuts(SCIP_REOPT *reopt, SCIP_NODE *node, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_Bool root)
Definition reopt.c:7730
SCIP_Bool SCIPreoptGetSolveLP(SCIP_REOPT *reopt, SCIP_SET *set, SCIP_NODE *node)
Definition reopt.c:7860
data structures and methods for collecting reoptimization information
public methods for concurrent solving mode
public methods for memory management
public methods for global and local (sub)problems
public methods for solutions
public methods for querying solving statistics
SCIP_RETCODE SCIPsepaExecLP(SCIP_SEPA *sepa, SCIP_SET *set, SCIP_STAT *stat, SCIP_SEPASTORE *sepastore, int depth, SCIP_Real bounddist, SCIP_Bool allowlocal, SCIP_Bool execdelayed, SCIP_RESULT *result)
Definition sepa.c:403
SCIP_RETCODE SCIPsepaExecSol(SCIP_SEPA *sepa, SCIP_SET *set, SCIP_STAT *stat, SCIP_SEPASTORE *sepastore, SCIP_SOL *sol, int depth, SCIP_Bool allowlocal, SCIP_Bool execdelayed, SCIP_RESULT *result)
Definition sepa.c:521
internal methods for separators
void SCIPsepastoreEndInitialLP(SCIP_SEPASTORE *sepastore)
Definition sepastore.c:144
SCIP_RETCODE SCIPsepastoreClearCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp)
Definition sepastore.c:1027
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition sepastore.c:1149
SCIP_RETCODE SCIPsepastoreAddCut(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool root, SCIP_Bool *infeasible)
Definition sepastore.c:428
void SCIPsepastoreStartForceCuts(SCIP_SEPASTORE *sepastore)
Definition sepastore.c:156
void SCIPsepastoreEndForceCuts(SCIP_SEPASTORE *sepastore)
Definition sepastore.c:167
void SCIPsepastoreStartInitialLP(SCIP_SEPASTORE *sepastore)
Definition sepastore.c:132
SCIP_RETCODE SCIPsepastoreApplyCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool root, SCIP_EFFICIACYCHOICE efficiacychoice, SCIP_Bool *cutoff)
Definition sepastore.c:921
int SCIPsepastoreGetNCutsApplied(SCIP_SEPASTORE *sepastore)
Definition sepastore.c:1200
internal methods for storing separated cuts
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6281
SCIP_Real SCIPsetCeil(SCIP_SET *set, SCIP_Real val)
Definition set.c:6385
int SCIPsetGetSepaMaxcuts(SCIP_SET *set, SCIP_Bool root)
Definition set.c:5905
SCIP_Bool SCIPsetIsFeasEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6585
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6245
void SCIPsetSortRelaxs(SCIP_SET *set)
Definition set.c:4184
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6209
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6607
void SCIPsetSortPricers(SCIP_SET *set)
Definition set.c:3731
void SCIPsetSortSepas(SCIP_SET *set)
Definition set.c:4258
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition set.c:6052
void SCIPsetSortProps(SCIP_SET *set)
Definition set.c:4393
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6227
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition set.c:6187
void SCIPsetSortHeurs(SCIP_SET *set)
Definition set.c:4613
SCIP_Real SCIPsetGetSepaMaxcutsGenFactor(SCIP_SET *set, SCIP_Bool root)
Definition set.c:5891
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6263
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition set.c:6299
int SCIPsetGetPriceMaxvars(SCIP_SET *set, SCIP_Bool root)
Definition set.c:5877
SCIP_NODESEL * SCIPsetGetNodesel(SCIP_SET *set, SCIP_STAT *stat)
Definition set.c:4811
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition set.c:6321
internal methods for global SCIP settings
#define SCIPsetFreeBufferArray(set, ptr)
Definition set.h:1755
#define SCIPsetAllocBufferArray(set, ptr, num)
Definition set.h:1748
#define SCIPsetDebugMsg
Definition set.h:1784
#define SCIPsetReallocBufferArray(set, ptr, num)
Definition set.h:1752
SCIP_RETCODE SCIPsolCreateRelaxSol(SCIP_SOL **sol, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_RELAXATION *relaxation, SCIP_HEUR *heur)
Definition sol.c:652
SCIP_RETCODE SCIPsolCheck(SCIP_SOL *sol, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition sol.c:1838
SCIP_RETCODE SCIPsolFree(SCIP_SOL **sol, BMS_BLKMEM *blkmem, SCIP_PRIMAL *primal)
Definition sol.c:801
SCIP_RETCODE SCIPsolCreateCurrentSol(SCIP_SOL **sol, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_HEUR *heur)
Definition sol.c:703
SCIP_RETCODE SCIPsolSetVal(SCIP_SOL *sol, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_VAR *var, SCIP_Real val)
Definition sol.c:1077
SCIP_RETCODE SCIPsolCreatePseudoSol(SCIP_SOL **sol, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_HEUR *heur)
Definition sol.c:678
SCIP_RETCODE SCIPsolCreateLPSol(SCIP_SOL **sol, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_HEUR *heur)
Definition sol.c:608
SCIP_Real SCIPsolGetObj(SCIP_SOL *sol, SCIP_SET *set, SCIP_PROB *transprob, SCIP_PROB *origprob)
Definition sol.c:1571
SCIP_RETCODE SCIPsolCreate(SCIP_SOL **sol, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_HEUR *heur)
Definition sol.c:288
internal methods for storing primal CIP solutions
static SCIP_RETCODE cutpoolSeparate(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_Bool cutpoolisdelayed, SCIP_Bool root, int actdepth, SCIP_Bool *enoughcuts, SCIP_Bool *cutoff)
Definition solve.c:2308
static SCIP_RETCODE enforceConstraints(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_Bool *branched, SCIP_Bool *cutoff, SCIP_Bool *infeasible, SCIP_Bool *propagateagain, SCIP_Bool *solvelpagain, SCIP_Bool *solverelaxagain, SCIP_Bool forced)
Definition solve.c:3380
static SCIP_RETCODE updateEstimate(SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand)
Definition solve.c:1058
enum PseudocostFlag PSEUDOCOSTFLAG
Definition solve.c:739
static SCIP_RETCODE applyBounding(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CONFLICT *conflict, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *cutoff)
Definition solve.c:2958
static SCIP_RETCODE solveNodeInitialLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool newinitconss, SCIP_Bool *cutoff, SCIP_Bool *lperror)
Definition solve.c:1439
static SCIP_RETCODE updatePseudocost(SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_LP *lp, SCIP_Bool updateintegers, SCIP_Bool updatecontinuous)
Definition solve.c:743
SCIP_RETCODE SCIPsolveCIP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_MEM *mem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_CUTPOOL *delayedcutpool, SCIP_BRANCHCAND *branchcand, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *restart)
Definition solve.c:4942
#define SAFETYFACTOR
Definition solve.c:97
static SCIP_RETCODE separationRoundSol(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_SEPASTORE *sepastore, SCIP_SOL *sol, int actdepth, SCIP_Bool allowlocal, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *enoughcuts, SCIP_Bool *cutoff)
Definition solve.c:1859
static void updateLoopStatus(SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, int depth, SCIP_Bool *cutoff, SCIP_Bool *propagateagain, SCIP_Bool *solverelaxagain)
Definition solve.c:3727
static SCIP_RETCODE propAndSolve(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_MEM *mem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_CUTPOOL *cutpool, SCIP_CUTPOOL *delayedcutpool, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_NODE *focusnode, int actdepth, SCIP_Bool propagate, SCIP_Bool solvelp, SCIP_Bool solverelax, SCIP_Bool forcedlpsolve, SCIP_Bool initiallpsolved, SCIP_Bool fullseparation, SCIP_Longint *afterlpproplps, SCIP_HEURTIMING *heurtiming, int *nlperrors, SCIP_Bool *fullpropagation, SCIP_Bool *propagateagain, SCIP_Bool *lpsolved, SCIP_Bool *relaxcalled, SCIP_Bool *solvelpagain, SCIP_Bool *solverelaxagain, SCIP_Bool *cutoff, SCIP_Bool *postpone, SCIP_Bool *unbounded, SCIP_Bool *stopped, SCIP_Bool *lperror, SCIP_Bool *pricingaborted, SCIP_Bool *forcedenforcement)
Definition solve.c:3770
PseudocostFlag
Definition solve.c:734
@ PSEUDOCOST_UPDATE
Definition solve.c:737
@ PSEUDOCOST_IGNORE
Definition solve.c:736
@ PSEUDOCOST_NONE
Definition solve.c:735
SCIP_RETCODE SCIPpropagateDomains(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CONFLICT *conflict, SCIP_CLIQUETABLE *cliquetable, int depth, int maxproprounds, SCIP_PROPTIMING timingmask, SCIP_Bool *cutoff)
Definition solve.c:644
static SCIP_RETCODE separationRoundLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, int actdepth, SCIP_Real bounddist, SCIP_Bool allowlocal, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *enoughcuts, SCIP_Bool *cutoff, SCIP_Bool *lperror, SCIP_Bool *mustsepa, SCIP_Bool *mustprice)
Definition solve.c:1603
static SCIP_RETCODE solveNodeLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_MEM *mem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_CUTPOOL *delayedcutpool, SCIP_BRANCHCAND *branchcand, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool initiallpsolved, SCIP_Bool fullseparation, SCIP_Bool newinitconss, SCIP_Bool *propagateagain, SCIP_Bool *solverelaxagain, SCIP_Bool *cutoff, SCIP_Bool *unbounded, SCIP_Bool *lperror, SCIP_Bool *pricingaborted)
Definition solve.c:3036
SCIP_RETCODE SCIPinitConssLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool root, SCIP_Bool firstsubtreeinit, SCIP_Bool *cutoff)
Definition solve.c:1108
static SCIP_RETCODE solveNodeRelax(SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob, SCIP_PROB *origprob, int depth, SCIP_Bool beforelp, SCIP_Bool *cutoff, SCIP_Bool *propagateagain, SCIP_Bool *solvelpagain, SCIP_Bool *solverelaxagain, SCIP_Bool *relaxcalled)
Definition solve.c:3280
static SCIP_RETCODE applyCuts(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool root, SCIP_EFFICIACYCHOICE efficiacychoice, SCIP_Bool *cutoff, SCIP_Bool *propagateagain, SCIP_Bool *solvelpagain, SCIP_Bool *solverelaxagain)
Definition solve.c:3671
static SCIP_RETCODE propagationRound(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, int depth, SCIP_Bool fullpropagation, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *propagain, SCIP_PROPTIMING timingmask, SCIP_Bool *cutoff, SCIP_Bool *postpone)
Definition solve.c:400
static SCIP_RETCODE propagateDomains(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, int depth, int maxproprounds, SCIP_Bool fullpropagation, SCIP_PROPTIMING timingmask, SCIP_Bool *cutoff, SCIP_Bool *postpone)
Definition solve.c:569
SCIP_RETCODE SCIPpriceLoop(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool pretendroot, SCIP_Bool displayinfo, int maxpricerounds, int *npricedcolvars, SCIP_Bool *mustsepa, SCIP_Bool *lperror, SCIP_Bool *aborted)
Definition solve.c:2091
SCIP_RETCODE SCIPconstructCurrentLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool newinitconss, SCIP_Bool *cutoff)
Definition solve.c:1281
#define MAXNLPERRORS
Definition solve.c:94
static SCIP_RETCODE addCurrentSolution(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_PRIMAL *primal, SCIP_RELAXATION *relaxation, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_Bool checksol)
Definition solve.c:4805
SCIP_Bool SCIPsolveIsStopped(SCIP_SET *set, SCIP_STAT *stat, SCIP_Bool checknodelimits)
Definition solve.c:102
static SCIP_RETCODE priceAndCutLoop(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_MEM *mem, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_CUTPOOL *delayedcutpool, SCIP_BRANCHCAND *branchcand, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool fullseparation, SCIP_Bool *propagateagain, SCIP_Bool *cutoff, SCIP_Bool *unbounded, SCIP_Bool *lperror, SCIP_Bool *pricingaborted)
Definition solve.c:2348
static SCIP_RETCODE solveNode(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_MEM *mem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_CUTPOOL *cutpool, SCIP_CUTPOOL *delayedcutpool, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *cutoff, SCIP_Bool *postpone, SCIP_Bool *unbounded, SCIP_Bool *infeasible, SCIP_Bool *restart, SCIP_Bool *afternodeheur, SCIP_Bool *stopped)
Definition solve.c:4140
static SCIP_RETCODE updatePrimalRay(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_Bool lperror)
Definition solve.c:1372
#define NINITCALLS
Definition solve.c:96
static void markRelaxsUnsolved(SCIP_SET *set, SCIP_RELAXATION *relaxation)
Definition solve.c:3018
SCIP_RETCODE SCIPseparationRound(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_SOL *sol, int actdepth, SCIP_Bool allowlocal, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *cutoff)
Definition solve.c:2038
static SCIP_Bool restartAllowed(SCIP_SET *set, SCIP_STAT *stat)
Definition solve.c:4121
static SCIP_RETCODE initLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool root, SCIP_Bool *cutoff)
Definition solve.c:1173
static SCIP_RETCODE separationRoundResolveLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_Bool *lperror, SCIP_Bool *mustsepa, SCIP_Bool *mustprice)
Definition solve.c:1562
static SCIP_Bool isPseudocostUpdateValid(SCIP_VAR *var, SCIP_SET *set, SCIP_Real oldlpsolval, SCIP_Bool updateintegers, SCIP_Bool updatecontinuous)
Definition solve.c:676
SCIP_RETCODE SCIPprimalHeuristics(SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_NODE *nextnode, SCIP_HEURTIMING heurtiming, SCIP_Bool nodeinfeasible, SCIP_Bool *foundsol, SCIP_Bool *unbounded)
Definition solve.c:214
#define MAXNCLOCKSKIPS
Definition solve.c:95
internal methods for main solving loop and node processing
void SCIPstatUpdatePrimalDualIntegrals(SCIP_STAT *stat, SCIP_SET *set, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_Real upperbound, SCIP_Real lowerbound)
Definition stat.c:459
void SCIPstatUpdateMemsaveMode(SCIP_STAT *stat, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_MEM *mem)
Definition stat.c:697
internal methods for problem statistics
#define SCIPstatIncrement(stat, set, field)
Definition stat.h:260
SCIP_VAR * var
Definition struct_var.h:99
SCIP_BRANCHINGDATA branchingdata
Definition struct_var.h:96
SCIP_BOUNDCHG * boundchgs
Definition struct_var.h:134
unsigned int nboundchgs
Definition struct_var.h:132
SCIP_Real lpobjval
SCIP_ROW ** rows
Definition struct_lp.h:303
SCIP_Bool primalfeasible
Definition struct_lp.h:368
SCIP_Real cutoffbound
Definition struct_lp.h:284
int nremovablerows
Definition struct_lp.h:335
SCIP_Bool installing
Definition struct_lp.h:376
int nrows
Definition struct_lp.h:334
SCIP_Bool solved
Definition struct_lp.h:367
SCIP_Bool resolvelperror
Definition struct_lp.h:383
int nremovablecols
Definition struct_lp.h:331
int looseobjvalinf
Definition struct_lp.h:337
SCIP_Bool flushed
Definition struct_lp.h:366
BMS_BUFMEM * buffer
Definition struct_mem.h:50
SCIP_DOMCHG * domchg
SCIP_FORK * fork
union SCIP_Node::@19 data
SCIP_Real lowerbound
SCIP_Real estimate
unsigned int depth
SCIP_SOL ** sols
SCIP_Longint nbestsolsfound
SCIP_SOL * primalray
SCIP_Longint nlimsolsfound
SCIP_Real cutoffbound
int ncontvars
Definition struct_prob.h:75
SCIP_VAR ** vars
Definition struct_prob.h:64
unsigned int local
Definition struct_lp.h:259
unsigned int fromcutpool
Definition struct_lp.h:249
SCIP_STATUS status
SCIP_Longint nrelaxsolsfound
SCIP_Longint nprimalzeroitlps
SCIP_Longint nnodes
Definition struct_stat.h:82
SCIP_REGRESSION * regressioncandsobjval
Definition struct_stat.h:61
SCIP_Longint ntotalnodes
Definition struct_stat.h:87
SCIP_Bool disableenforelaxmsg
SCIP_Longint ninfeasleaves
Definition struct_stat.h:86
SCIP_VAR * lastbranchvar
int nclockskipsleft
SCIP_Longint ndelayedcutoffs
Definition struct_stat.h:97
SCIP_CLOCK * nodeactivationtime
SCIP_Longint nlps
SCIP_Longint externmemestim
SCIP_Longint domchgcount
SCIP_Longint nnodelps
SCIP_Longint lpcount
int prevrunnvars
SCIP_Longint nrootfirstlpiterations
Definition struct_stat.h:64
SCIP_Longint ninitconssadded
int nseparounds
SCIP_Longint nlpiterations
Definition struct_stat.h:62
int nconfrestarts
SCIP_Longint nfeasleaves
Definition struct_stat.h:85
int npricerounds
SCIP_VISUAL * visual
SCIP_Longint nnodesaboverefbound
Definition struct_stat.h:95
SCIP_Real firstlpdualbound
SCIP_Longint nrootlpiterations
Definition struct_stat.h:63
int nrootintfixingsrun
SCIP_Longint ninternalnodes
Definition struct_stat.h:83
SCIP_CLOCK * relaxsoltime
SCIP_Longint ntotalinternalnodes
Definition struct_stat.h:88
SCIP_Longint nobjleaves
Definition struct_stat.h:84
SCIP_Real referencebound
SCIP_BRANCHDIR lastbranchdir
SCIP_CLOCK * pseudosoltime
SCIP_Bool userrestart
SCIP_Longint nlpbestsolsfound
SCIP_Longint nboundchgs
SCIP_Real firstlptime
SCIP_Longint nrelaxbestsolsfound
SCIP_Longint npsbestsolsfound
SCIP_Longint ninitlps
SCIP_Longint nisstoppedcalls
int maxtotaldepth
SCIP_Longint ndualzeroitlps
SCIP_Longint nrootlps
SCIP_Longint nnodelpiterations
Definition struct_stat.h:72
SCIP_Longint bestsolnode
SCIP_Longint nnodezeroitlps
SCIP_Longint npssolsfound
SCIP_Longint nbarrierzeroitlps
SCIP_CLOCK * lpsoltime
SCIP_Bool branchedunbdvar
SCIP_CLOCK * solvingtime
SCIP_Longint nlpsolsfound
SCIP_Real lastbranchvalue
SCIP_Longint ninitlpiterations
Definition struct_stat.h:73
SCIP_Bool userinterrupt
int correctlpdepth
SCIP_NODE * root
SCIP_Bool cutoffdelayed
SCIP_NODE * focuslpstatefork
int cutoffdepth
int * pathnlprows
SCIP_NODE ** path
SCIP_Bool sbprobing
SCIP_NODE * focusnode
SCIP_Bool forcinglpmessage
int effectiverootdepth
unsigned int pseudocostflag
Definition struct_var.h:282
datastructures for constraints and constraint handlers
datastructures for managing events
data structures for LP management
datastructures for block memory pools and memory buffers
datastructures for collecting primal CIP solutions and primal informations
datastructures for storing and manipulating the main problem
datastructures for global SCIP settings
datastructures for problem statistics
data structures for branch and bound tree
datastructures for problem variables
SCIP_Bool SCIPsyncstoreSolveIsStopped(SCIP_SYNCSTORE *syncstore)
Definition syncstore.c:239
the function declarations for the synchronization store
void SCIPnodeUpdateLowerbound(SCIP_NODE *node, SCIP_STAT *stat, SCIP_SET *set, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_Real newbound)
Definition tree.c:2365
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition tree.c:8367
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition tree.c:8312
SCIP_Bool SCIPtreeProbing(SCIP_TREE *tree)
Definition tree.c:8286
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition tree.c:8329
SCIP_RETCODE SCIPtreeSetNodesel(SCIP_TREE *tree, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_NODESEL *nodesel)
Definition tree.c:5108
void SCIPnodeSetEstimate(SCIP_NODE *node, SCIP_SET *set, SCIP_Real newestimate)
Definition tree.c:2461
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition tree.c:8387
void SCIPnodeMarkPropagated(SCIP_NODE *node, SCIP_TREE *tree)
Definition tree.c:1274
int SCIPtreeGetNLeaves(SCIP_TREE *tree)
Definition tree.c:8249
SCIP_RETCODE SCIPnodeCreateChild(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition tree.c:993
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition tree.c:8421
SCIP_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7257
void SCIPtreeSetFocusNodeLP(SCIP_TREE *tree, SCIP_Bool solvelp)
Definition tree.c:8356
int SCIPtreeGetNNodes(SCIP_TREE *tree)
Definition tree.c:8259
SCIP_Bool SCIPtreeHasFocusNodeLP(SCIP_TREE *tree)
Definition tree.c:8346
SCIP_RETCODE SCIPnodeFocus(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *cutoff, SCIP_Bool postponed, SCIP_Bool exitsolve)
Definition tree.c:4352
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition tree.c:8404
SCIP_RETCODE SCIPnodeUpdateLowerboundLP(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp)
Definition tree.c:2409
SCIP_RETCODE SCIPtreeCutoff(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp, SCIP_Real cutoffbound)
Definition tree.c:5136
SCIP_RETCODE SCIPtreeLoadLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition tree.c:3588
SCIP_RETCODE SCIPtreeLoadLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_Bool *initroot)
Definition tree.c:3460
internal methods for branch and bound tree
#define SCIP_EVENTTYPE_FIRSTLPSOLVED
Definition type_event.h:100
#define SCIP_EVENTTYPE_NODEFEASIBLE
Definition type_event.h:93
#define SCIP_EVENTTYPE_NODEFOCUSED
Definition type_event.h:92
#define SCIP_EVENTTYPE_NODEINFEASIBLE
Definition type_event.h:94
#define SCIP_EVENTTYPE_NODEBRANCHED
Definition type_event.h:95
#define SCIP_EVENTTYPE_LPSOLVED
Definition type_event.h:101
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition type_lp.h:51
@ SCIP_BOUNDTYPE_UPPER
Definition type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition type_lp.h:59
@ SCIP_LPSOLSTAT_ERROR
Definition type_lp.h:49
@ SCIP_LPSOLSTAT_NOTSOLVED
Definition type_lp.h:42
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_LPSOLSTAT_TIMELIMIT
Definition type_lp.h:48
@ SCIP_LPSOLSTAT_UNBOUNDEDRAY
Definition type_lp.h:45
@ SCIP_LPSOLSTAT_INFEASIBLE
Definition type_lp.h:44
@ SCIP_LPSOLSTAT_OBJLIMIT
Definition type_lp.h:46
@ SCIP_LPSOLSTAT_ITERLIMIT
Definition type_lp.h:47
enum SCIP_VerbLevel SCIP_VERBLEVEL
@ SCIP_VERBLEVEL_HIGH
@ SCIP_VERBLEVEL_NORMAL
@ SCIP_VERBLEVEL_FULL
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_FEASIBLE
Definition type_result.h:45
@ SCIP_DELAYED
Definition type_result.h:43
@ SCIP_REDUCEDDOM
Definition type_result.h:51
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_CONSADDED
Definition type_result.h:52
@ SCIP_UNBOUNDED
Definition type_result.h:47
@ SCIP_FOUNDSOL
Definition type_result.h:56
@ SCIP_SUSPENDED
Definition type_result.h:57
@ SCIP_BRANCHED
Definition type_result.h:54
@ SCIP_SEPARATED
Definition type_result.h:49
@ SCIP_SOLVELP
Definition type_result.h:55
@ SCIP_NEWROUND
Definition type_result.h:50
@ SCIP_SUCCESS
Definition type_result.h:58
@ SCIP_DELAYNODE
Definition type_result.h:59
@ SCIP_INFEASIBLE
Definition type_result.h:46
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_LPERROR
@ SCIP_INVALIDRESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_EFFICIACYCHOICE_LP
@ SCIP_EFFICIACYCHOICE_RELAX
enum SCIP_Efficiacychoice SCIP_EFFICIACYCHOICE
@ SCIP_STAGE_PRESOLVING
Definition type_set.h:49
@ SCIP_STAGE_SOLVING
Definition type_set.h:53
@ SCIP_STATUS_OPTIMAL
Definition type_stat.h:61
@ SCIP_STATUS_TOTALNODELIMIT
Definition type_stat.h:45
@ SCIP_STATUS_BESTSOLLIMIT
Definition type_stat.h:57
@ SCIP_STATUS_SOLLIMIT
Definition type_stat.h:54
@ SCIP_STATUS_UNBOUNDED
Definition type_stat.h:63
@ SCIP_STATUS_UNKNOWN
Definition type_stat.h:42
@ SCIP_STATUS_GAPLIMIT
Definition type_stat.h:53
@ SCIP_STATUS_USERINTERRUPT
Definition type_stat.h:43
@ SCIP_STATUS_TERMINATE
Definition type_stat.h:65
@ SCIP_STATUS_INFORUNBD
Definition type_stat.h:64
@ SCIP_STATUS_STALLNODELIMIT
Definition type_stat.h:48
@ SCIP_STATUS_TIMELIMIT
Definition type_stat.h:51
@ SCIP_STATUS_INFEASIBLE
Definition type_stat.h:62
@ SCIP_STATUS_NODELIMIT
Definition type_stat.h:44
@ SCIP_STATUS_MEMLIMIT
Definition type_stat.h:52
@ SCIP_STATUS_RESTARTLIMIT
Definition type_stat.h:60
#define SCIP_HEURTIMING_BEFOREPRESOL
Definition type_timing.h:90
#define SCIP_HEURTIMING_DURINGPRICINGLOOP
Definition type_timing.h:89
#define SCIP_HEURTIMING_AFTERPSEUDONODE
Definition type_timing.h:83
#define SCIP_HEURTIMING_AFTERPROPLOOP
Definition type_timing.h:92
unsigned int SCIP_PROPTIMING
Definition type_timing.h:74
unsigned int SCIP_HEURTIMING
#define SCIP_HEURTIMING_DURINGLPLOOP
Definition type_timing.h:79
#define SCIP_HEURTIMING_DURINGPRESOLLOOP
Definition type_timing.h:91
#define SCIP_HEURTIMING_AFTERNODE
Definition type_timing.h:96
#define SCIP_PROPTIMING_AFTERLPLOOP
Definition type_timing.h:67
#define SCIP_HEURTIMING_AFTERLPPLUNGE
Definition type_timing.h:85
#define SCIP_HEURTIMING_AFTERPSEUDOPLUNGE
Definition type_timing.h:87
#define SCIP_PROPTIMING_BEFORELP
Definition type_timing.h:65
#define SCIP_HEURTIMING_AFTERLPNODE
Definition type_timing.h:81
#define SCIP_HEURTIMING_AFTERLPLOOP
Definition type_timing.h:80
#define SCIP_HEURTIMING_BEFORENODE
Definition type_timing.h:78
#define SCIP_PROPTIMING_DURINGLPLOOP
Definition type_timing.h:66
@ SCIP_NODETYPE_REFOCUSNODE
Definition type_tree.h:51
@ SCIP_NODETYPE_FORK
Definition type_tree.h:49
@ SCIP_NODETYPE_CHILD
Definition type_tree.h:44
@ SCIP_NODETYPE_PROBINGNODE
Definition type_tree.h:42
@ SCIP_NODETYPE_SIBLING
Definition type_tree.h:43
@ SCIP_NODETYPE_LEAF
Definition type_tree.h:45
@ SCIP_NODETYPE_FOCUSNODE
Definition type_tree.h:41
enum SCIP_BoundchgType SCIP_BOUNDCHGTYPE
Definition type_var.h:91
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_BOUNDCHGTYPE_BRANCHING
Definition type_var.h:87
@ SCIP_VARSTATUS_COLUMN
Definition type_var.h:51
SCIP_DOMCHGBOUND domchgbound
Definition struct_var.h:162
SCIP_Real SCIPvarGetPseudocost(SCIP_VAR *var, SCIP_STAT *stat, SCIP_Real solvaldelta)
Definition var.c:14477
SCIP_RETCODE SCIPvarUpdatePseudocost(SCIP_VAR *var, SCIP_SET *set, SCIP_STAT *stat, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition var.c:14379
SCIP_RETCODE SCIPvarIncCutoffSum(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Real weight)
Definition var.c:15615
internal methods for problem variables
void SCIPvisualSolvedNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node)
Definition visual.c:473
void SCIPvisualCutoffNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node, SCIP_Bool infeasible)
Definition visual.c:533
methods for creating output for visualization tools (VBC, BAK)