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-2023 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 *lperror = FALSE;
1644 consadded = FALSE;
1645
1646 SCIPsetDebugMsg(set, "calling separators on LP solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed);
1647
1648 /* sort separators by priority */
1650
1651 /* call LP separators with nonnegative priority */
1652 for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1654 ++i )
1655 {
1656#ifndef NDEBUG
1658#endif
1659
1660 if( SCIPsepaGetPriority(set->sepas[i]) < 0 )
1661 continue;
1662
1663 if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) )
1664 continue;
1665
1666 SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n",
1667 SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i]));
1668 SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) );
1669#ifndef NDEBUG
1671 {
1672 SCIPerrorMessage("Buffer not completely freed after executing separator <%s>\n", SCIPsepaGetName(set->sepas[i]));
1673 SCIPABORT();
1674 }
1675#endif
1676 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1677 consadded = consadded || (result == SCIP_CONSADDED);
1679 *delayed = *delayed || (result == SCIP_DELAYED);
1680
1681 if( !(*cutoff) )
1682 {
1683 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1684 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1685 }
1686 else
1687 {
1688 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1689 }
1690
1691 /* if we work off the delayed separators, we stop immediately if a cut was found */
1693 {
1694 SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i]));
1695 *delayed = TRUE;
1696 return SCIP_OKAY;
1697 }
1698 }
1699
1700 /* try separating constraints of the constraint handlers */
1701 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1703 ++i )
1704 {
1705 if( onlydelayed && !SCIPconshdlrWasLPSeparationDelayed(set->conshdlrs_sepa[i]) )
1706 continue;
1707
1708 SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n",
1709 SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i]));
1710 SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed,
1711 &result) );
1712
1713 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1714 consadded = consadded || (result == SCIP_CONSADDED);
1716 *delayed = *delayed || (result == SCIP_DELAYED);
1717
1718 if( !(*cutoff) )
1719 {
1720 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1721 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1722 }
1723 else
1724 {
1725 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1726 }
1727
1728 /* if we work off the delayed separators, we stop immediately if a cut was found */
1730 {
1731 SCIPsetDebugMsg(set, " -> delayed constraint handler <%s> found a cut\n",
1732 SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1733 *delayed = TRUE;
1734 return SCIP_OKAY;
1735 }
1736 }
1737
1738 /* call LP separators with negative priority */
1739 for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1741 ++i )
1742 {
1743 if( SCIPsepaGetPriority(set->sepas[i]) >= 0 )
1744 continue;
1745
1746 if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) )
1747 continue;
1748
1749 SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n",
1750 SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i]));
1751 SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) );
1752
1753 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1754 consadded = consadded || (result == SCIP_CONSADDED);
1756 *delayed = *delayed || (result == SCIP_DELAYED);
1757
1758 if( !(*cutoff) )
1759 {
1760 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1761 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1762 }
1763 else
1764 {
1765 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1766 }
1767
1768 /* if we work off the delayed separators, we stop immediately if a cut was found */
1770 {
1771 SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i]));
1772 *delayed = TRUE;
1773 return SCIP_OKAY;
1774 }
1775 }
1776
1777 /* process the constraints that were added during this separation round */
1778 while( consadded )
1779 {
1781 consadded = FALSE;
1782
1783 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1785 ++i )
1786 {
1787 SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n",
1788 SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i]));
1789 SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed,
1790 &result) );
1791
1792 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1793 consadded = consadded || (result == SCIP_CONSADDED);
1795 *delayed = *delayed || (result == SCIP_DELAYED);
1796
1797 if( !(*cutoff) )
1798 {
1799 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1800 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1801 }
1802 else
1803 {
1804 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1805 }
1806 }
1807 }
1808
1809 SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, lpflushed=%u, cutoff=%u\n",
1810 *delayed, *enoughcuts, lp->flushed, *cutoff);
1811
1812 return SCIP_OKAY;
1813}
1814
1815/** applies one round of separation on the given primal solution */
1816static
1818 BMS_BLKMEM* blkmem, /**< block memory buffers */
1819 SCIP_SET* set, /**< global SCIP settings */
1820 SCIP_STAT* stat, /**< dynamic problem statistics */
1821 SCIP_SEPASTORE* sepastore, /**< separation storage */
1822 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
1823 int actdepth, /**< current depth in the tree */
1824 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
1825 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
1826 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
1827 SCIP_Bool* enoughcuts, /**< pointer to store whether enough cuts have been found this round */
1828 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1829 )
1830{
1832 int i;
1833 SCIP_Bool consadded;
1834 SCIP_Bool root;
1835
1836 assert(set != NULL);
1837 assert(set->conshdlrs_sepa != NULL);
1838 assert(delayed != NULL);
1840 assert(cutoff != NULL);
1841
1842 *delayed = FALSE;
1843 *enoughcuts = FALSE;
1844 consadded = FALSE;
1845 root = (actdepth == 0);
1846
1847 SCIPsetDebugMsg(set, "calling separators on primal solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed);
1848
1849 /* sort separators by priority */
1851
1852 /* call separators with nonnegative priority */
1853 for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1854 {
1855 if( SCIPsepaGetPriority(set->sepas[i]) < 0 )
1856 continue;
1857
1858 if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) )
1859 continue;
1860
1861 SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) );
1862 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1863 consadded = consadded || (result == SCIP_CONSADDED);
1865 *delayed = *delayed || (result == SCIP_DELAYED);
1866 if( *cutoff )
1867 {
1868 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1869 }
1870
1871 /* if we work off the delayed separators, we stop immediately if a cut was found */
1873 {
1874 *delayed = TRUE;
1875 return SCIP_OKAY;
1876 }
1877 }
1878
1879 /* try separating constraints of the constraint handlers */
1880 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1881 {
1882 if( onlydelayed && !SCIPconshdlrWasSolSeparationDelayed(set->conshdlrs_sepa[i]) )
1883 continue;
1884
1885 SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed,
1886 &result) );
1887 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1888 consadded = consadded || (result == SCIP_CONSADDED);
1890 *delayed = *delayed || (result == SCIP_DELAYED);
1891 if( *cutoff )
1892 {
1893 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n",
1894 SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1895 }
1896
1897 /* if we work off the delayed separators, we stop immediately if a cut was found */
1899 {
1900 *delayed = TRUE;
1901 return SCIP_OKAY;
1902 }
1903 }
1904
1905 /* call separators with negative priority */
1906 for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1907 {
1908 if( SCIPsepaGetPriority(set->sepas[i]) >= 0 )
1909 continue;
1910
1911 if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) )
1912 continue;
1913
1914 SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) );
1915 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1916 consadded = consadded || (result == SCIP_CONSADDED);
1918 *delayed = *delayed || (result == SCIP_DELAYED);
1919 if( *cutoff )
1920 {
1921 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1922 }
1923
1924 /* if we work off the delayed separators, we stop immediately if a cut was found */
1926 {
1927 *delayed = TRUE;
1928 return SCIP_OKAY;
1929 }
1930 }
1931
1932 /* process the constraints that were added during this separation round */
1933 while( consadded )
1934 {
1936 consadded = FALSE;
1937
1938 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1939 {
1940 SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed, &result) );
1941 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1942 consadded = consadded || (result == SCIP_CONSADDED);
1944 *delayed = *delayed || (result == SCIP_DELAYED);
1945 if( *cutoff )
1946 {
1947 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n",
1948 SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1949 }
1950 }
1951 }
1952
1953 SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, cutoff=%u\n",
1955
1956 return SCIP_OKAY;
1957}
1958
1959/** applies one round of separation on the given primal solution or on the LP solution */
1961 BMS_BLKMEM* blkmem, /**< block memory buffers */
1962 SCIP_SET* set, /**< global SCIP settings */
1963 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1964 SCIP_STAT* stat, /**< dynamic problem statistics */
1965 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1966 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1967 SCIP_PROB* prob, /**< transformed problem after presolve */
1968 SCIP_PRIMAL* primal, /**< primal data */
1969 SCIP_TREE* tree, /**< branch and bound tree */
1970 SCIP_LP* lp, /**< LP data */
1971 SCIP_SEPASTORE* sepastore, /**< separation storage */
1972 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
1973 int actdepth, /**< current depth in the tree */
1974 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
1975 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
1976 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
1977 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1978 )
1979{
1980 SCIP_Bool enoughcuts;
1981
1982 assert(delayed != NULL);
1983 assert(cutoff != NULL);
1984
1985 *delayed = FALSE;
1986 *cutoff = FALSE;
1987 enoughcuts = FALSE;
1988
1989 if( sol == NULL )
1990 {
1991 SCIP_Bool lperror;
1992 SCIP_Bool mustsepa;
1993 SCIP_Bool mustprice;
1994
1995 /* apply a separation round on the LP solution */
1996 lperror = FALSE;
1997 mustsepa = FALSE;
1998 mustprice = FALSE;
1999 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, sepastore, \
2000 actdepth, 0.0, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff, \
2001 &lperror, &mustsepa, &mustprice) );
2002 }
2003 else
2004 {
2005 /* apply a separation round on the given primal solution */
2006 SCIP_CALL( separationRoundSol(blkmem, set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff) );
2007 }
2008
2009 return SCIP_OKAY;
2010}
2011
2012/** solves the current LP completely with pricing in new variables */
2014 BMS_BLKMEM* blkmem, /**< block memory buffers */
2015 SCIP_SET* set, /**< global SCIP settings */
2016 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2017 SCIP_STAT* stat, /**< dynamic problem statistics */
2018 SCIP_PROB* transprob, /**< transformed problem */
2019 SCIP_PROB* origprob, /**< original problem */
2020 SCIP_PRIMAL* primal, /**< primal data */
2021 SCIP_TREE* tree, /**< branch and bound tree */
2022 SCIP_REOPT* reopt, /**< reoptimization data structure */
2023 SCIP_LP* lp, /**< LP data */
2024 SCIP_PRICESTORE* pricestore, /**< pricing storage */
2025 SCIP_SEPASTORE* sepastore, /**< separation storage */
2026 SCIP_CUTPOOL* cutpool, /**< global cutpool */
2027 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2028 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2029 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
2030 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2031 SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */
2032 SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */
2033 int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit);
2034 * a finite limit means that the LP might not be solved to optimality! */
2035 int* npricedcolvars, /**< pointer to store number of column variables after problem vars were priced */
2036 SCIP_Bool* mustsepa, /**< pointer to store TRUE if a separation round should follow */
2037 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
2038 SCIP_Bool* aborted /**< pointer to store whether the pricing was aborted and the lower bound must
2039 * not be used */
2040 )
2041{
2042 SCIP_NODE* currentnode;
2043 int npricerounds;
2044 SCIP_Bool mustprice;
2045 SCIP_Bool cutoff;
2046 SCIP_Bool unbounded;
2047
2048 assert(transprob != NULL);
2049 assert(lp != NULL);
2050 assert(lp->flushed);
2051 assert(lp->solved);
2053 assert(mustsepa != NULL);
2054 assert(lperror != NULL);
2055 assert(aborted != NULL);
2056
2057 currentnode = SCIPtreeGetCurrentNode(tree);
2058 assert(currentnode == SCIPtreeGetFocusNode(tree) || SCIPtreeProbing(tree));
2059 *npricedcolvars = transprob->ncolvars;
2060 *lperror = FALSE;
2061 *aborted = FALSE;
2062
2063 /* if the LP is unbounded, we don't need to price */
2067
2068 /* if all the variables are already in the LP, we don't need to price */
2069 mustprice = mustprice && !SCIPprobAllColsInLP(transprob, set, lp);
2070
2071 /* check if infinite number of pricing rounds should be used */
2072 if( maxpricerounds == -1 )
2074
2075 /* pricing (has to be done completely to get a valid lower bound) */
2076 npricerounds = 0;
2077 while( !(*lperror) && mustprice && npricerounds < maxpricerounds )
2078 {
2079 SCIP_Bool enoughvars;
2081 SCIP_Real lb;
2082 SCIP_Bool foundsol;
2083 SCIP_Bool stopearly;
2084 SCIP_Bool stoppricing;
2085 int p;
2086
2087 assert(lp->flushed);
2088 assert(lp->solved);
2090
2091 /* check if pricing loop should be aborted */
2092 if( SCIPsolveIsStopped(set, stat, FALSE) )
2093 {
2094 /* do not print the warning message if we stopped because the problem is solved */
2096 SCIPmessagePrintWarning(messagehdlr, "pricing has been interrupted -- LP of current node is invalid\n");
2097
2098 *aborted = TRUE;
2099 break;
2100 }
2101
2102 /* call primal heuristics which are callable during pricing */
2103 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGPRICINGLOOP,
2104 FALSE, &foundsol, &unbounded) );
2105
2106 /* price problem variables */
2107 SCIPsetDebugMsg(set, "problem variable pricing\n");
2108 assert(SCIPpricestoreGetNVars(pricestore) == 0);
2109 assert(SCIPpricestoreGetNBoundResets(pricestore) == 0);
2110 SCIP_CALL( SCIPpricestoreAddProbVars(pricestore, blkmem, set, stat, transprob, tree, lp, branchcand, eventqueue) );
2111 *npricedcolvars = transprob->ncolvars;
2112
2113 /* call external pricers to create additional problem variables */
2114 SCIPsetDebugMsg(set, "external variable pricing\n");
2115
2116 /* sort pricer algorithms by priority */
2118
2119 /* call external pricer algorithms, that are active for the current problem */
2123 for( p = 0; p < set->nactivepricers && !enoughvars; ++p )
2124 {
2125 SCIP_CALL( SCIPpricerExec(set->pricers[p], set, transprob, lp, pricestore, &lb, &stopearly, &result) );
2127 SCIPsetDebugMsg(set, "pricing: pricer %s returned result = %s, lowerbound = %f\n",
2128 SCIPpricerGetName(set->pricers[p]), (result == SCIP_DIDNOTRUN ? "didnotrun" : "success"), lb);
2131 *aborted = ( (*aborted) || (result == SCIP_DIDNOTRUN) );
2132
2133 /* set stoppricing to TRUE, if the first pricer wants to stop pricing */
2134 if( p == 0 && stopearly )
2135 stoppricing = TRUE;
2136
2137 /* stoppricing only remains TRUE, if all other pricers want to stop pricing as well */
2138 if( stoppricing && !stopearly )
2140
2141 /* update lower bound w.r.t. the lower bound given by the pricer */
2142 SCIPnodeUpdateLowerbound(currentnode, stat, set, tree, transprob, origprob, lb);
2143 SCIPsetDebugMsg(set, " -> new lower bound given by pricer %s: %g\n", SCIPpricerGetName(set->pricers[p]), lb);
2144 }
2145
2146 /* apply the priced variables to the LP */
2147 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) );
2148 assert(SCIPpricestoreGetNVars(pricestore) == 0);
2149 assert(!lp->flushed || lp->solved);
2150 mustprice = !lp->flushed || (transprob->ncolvars != *npricedcolvars);
2151 *mustsepa = *mustsepa || !lp->flushed;
2152
2153 /* after adding columns, the LP should be primal feasible such that the primal simplex is applicable;
2154 * if LP was infeasible, we have to use dual simplex
2155 */
2156 SCIPsetDebugMsg(set, "pricing: solve LP\n");
2157 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, TRUE, FALSE, lperror) );
2158 assert(lp->flushed);
2159 assert(lp->solved || *lperror);
2160
2161 /* reset bounds temporarily set by pricer to their original values */
2162 SCIPsetDebugMsg(set, "pricing: reset bounds\n");
2163 SCIP_CALL( SCIPpricestoreResetBounds(pricestore, blkmem, set, stat, lp, branchcand, eventqueue) );
2164 assert(SCIPpricestoreGetNVars(pricestore) == 0);
2165 assert(SCIPpricestoreGetNBoundResets(pricestore) == 0);
2166 assert(!lp->flushed || lp->solved || *lperror);
2167
2168 /* put all initial constraints into the LP */
2169 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2170 eventfilter, cliquetable, FALSE, FALSE, &cutoff) );
2171 assert(cutoff == FALSE);
2172
2173 mustprice = mustprice || !lp->flushed || (transprob->ncolvars != *npricedcolvars);
2174 *mustsepa = *mustsepa || !lp->flushed;
2175
2176 /* if all pricers wanted to stop pricing, do not do another pricing round (LP value is no valid dual bound in this case) */
2177 if( stoppricing )
2178 {
2179 SCIPsetDebugMsg(set, "pricing: stop pricing and perform early branching\n");
2180 mustprice = FALSE;
2181 *aborted = TRUE;
2182 }
2183
2184 /* solve LP again after resetting bounds and adding new initial constraints (with dual simplex) */
2185 SCIPsetDebugMsg(set, "pricing: solve LP after resetting bounds and adding new initial constraints\n");
2186 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) );
2187 assert(lp->flushed);
2188 assert(lp->solved || *lperror);
2189
2190 /* remove previous primal ray, store new one if LP is unbounded */
2191 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2192
2193 /* increase pricing round counter */
2194 stat->npricerounds++;
2195 npricerounds++;
2196
2197 /* display node information line */
2198 if( displayinfo && mustprice )
2199 {
2200 if( (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_FULL
2201 || ((SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH && npricerounds % 100 == 1) )
2202 {
2203 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
2204 }
2205 }
2206
2207 /* if the LP is unbounded, we can stop pricing */
2208 mustprice = mustprice &&
2212
2213 /* if the lower bound is already higher than the cutoff bound, we can stop pricing */
2215 } /*lint !e438*/
2216 assert(lp->flushed);
2217 assert(lp->solved || *lperror);
2218
2219 *aborted = ( (*aborted) || (*lperror) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_NOTSOLVED
2220 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ERROR || npricerounds == maxpricerounds );
2221
2222 /* set information, whether the current lp is a valid relaxation of the current problem */
2223 SCIPlpSetIsRelax(lp, !(*aborted));
2224
2225 return SCIP_OKAY; /*lint !e438*/
2226}
2227
2228/** separates cuts of the cut pool */
2229static
2231 SCIP_CUTPOOL* cutpool, /**< cut pool */
2232 BMS_BLKMEM* blkmem, /**< block memory */
2233 SCIP_SET* set, /**< global SCIP settings */
2234 SCIP_STAT* stat, /**< problem statistics data */
2235 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2236 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
2237 SCIP_LP* lp, /**< current LP data */
2238 SCIP_SEPASTORE* sepastore, /**< separation storage */
2239 SCIP_Bool cutpoolisdelayed, /**< is the cutpool delayed (count cuts found)? */
2240 SCIP_Bool root, /**< are we at the root node? */
2241 int actdepth, /**< the depth of the focus node */
2242 SCIP_Bool* enoughcuts, /**< pointer to store if enough cuts were found in current separation round */
2243 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
2244 )
2245{
2246 if( (set->sepa_poolfreq == 0 && actdepth == 0)
2247 || (set->sepa_poolfreq > 0 && actdepth % set->sepa_poolfreq == 0) )
2248 {
2250
2251 SCIP_CALL( SCIPcutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, NULL, cutpoolisdelayed, root, &result) );
2252 *cutoff = *cutoff || (result == SCIP_CUTOFF);
2254 }
2255
2256 return SCIP_OKAY;
2257}
2258
2259/** solve the current LP of a node with a price-and-cut loop */
2260static
2262 BMS_BLKMEM* blkmem, /**< block memory buffers */
2263 SCIP_SET* set, /**< global SCIP settings */
2264 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2265 SCIP_STAT* stat, /**< dynamic problem statistics */
2266 SCIP_MEM* mem, /**< block memory pools */
2267 SCIP_PROB* transprob, /**< transformed problem */
2268 SCIP_PROB* origprob, /**< original problem */
2269 SCIP_PRIMAL* primal, /**< primal data */
2270 SCIP_TREE* tree, /**< branch and bound tree */
2271 SCIP_REOPT* reopt, /**< reoptimization data structure */
2272 SCIP_LP* lp, /**< LP data */
2273 SCIP_PRICESTORE* pricestore, /**< pricing storage */
2274 SCIP_SEPASTORE* sepastore, /**< separation storage */
2275 SCIP_CUTPOOL* cutpool, /**< global cut pool */
2276 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
2277 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2278 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2279 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2280 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
2281 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2282 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2283 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
2284 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
2285 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
2286 SCIP_Bool* unbounded, /**< pointer to store whether an unbounded ray was found in the LP */
2287 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
2288 SCIP_Bool* pricingaborted /**< pointer to store whether the pricing was aborted and the lower bound must
2289 * not be used */
2290 )
2291{
2292 SCIP_NODE* focusnode;
2293 /* cppcheck-suppress unassignedVariable */
2296 SCIP_Real loclowerbound;
2297 SCIP_Real glblowerbound;
2298 SCIP_Real bounddist;
2299 SCIP_Real stalllpobjval;
2300 SCIP_Bool separate;
2301 SCIP_Bool mustprice;
2302 SCIP_Bool mustsepa;
2303 SCIP_Bool delayedsepa;
2304 SCIP_Bool root;
2305 SCIP_Bool allowlocal;
2306 int maxseparounds;
2307 int nsepastallrounds;
2309 int stallnfracs;
2310 int actdepth;
2311 int npricedcolvars;
2312
2313 assert(set != NULL);
2314 assert(blkmem != NULL);
2315 assert(stat != NULL);
2316 assert(transprob != NULL);
2317 assert(tree != NULL);
2318 assert(lp != NULL);
2319 assert(pricestore != NULL);
2320 assert(sepastore != NULL);
2321 assert(cutpool != NULL);
2322 assert(delayedcutpool != NULL);
2323 assert(primal != NULL);
2324 assert(cutoff != NULL);
2325 assert(unbounded != NULL);
2326 assert(lperror != NULL);
2327
2328 focusnode = SCIPtreeGetFocusNode(tree);
2329 assert(focusnode != NULL);
2331 actdepth = SCIPnodeGetDepth(focusnode);
2332 root = (actdepth == 0);
2333
2334 /* check, if we want to separate at this node */
2337 assert(primal->cutoffbound > glblowerbound);
2338 bounddist = (loclowerbound - glblowerbound)/(primal->cutoffbound - glblowerbound);
2339 allowlocal = SCIPsetIsLE(set, bounddist, set->sepa_maxlocalbounddist);
2340 separate = (set->sepa_maxruns == -1 || stat->nruns <= set->sepa_maxruns);
2341
2342 /* get maximal number of separation rounds */
2343 maxseparounds = (root ? set->sepa_maxroundsroot : set->sepa_maxrounds);
2344 if( maxseparounds == -1 )
2345 maxseparounds = INT_MAX;
2346 if( stat->nruns > 1 && root && set->sepa_maxroundsrootsubrun >= 0 )
2347 maxseparounds = MIN(maxseparounds, set->sepa_maxroundsrootsubrun);
2348 if( !fullseparation && set->sepa_maxaddrounds >= 0 )
2349 maxseparounds = MIN(maxseparounds, stat->nseparounds + set->sepa_maxaddrounds);
2350 maxnsepastallrounds = root ? set->sepa_maxstallroundsroot : set->sepa_maxstallrounds;
2351 if( maxnsepastallrounds == -1 )
2353
2354 /* solve initial LP of price-and-cut loop */
2355 SCIPsetDebugMsg(set, "node: solve LP with price and cut\n");
2356 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2357 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2358 assert(lp->flushed);
2359 assert(lp->solved || *lperror);
2360
2361 /* remove previous primal ray, store new one if LP is unbounded */
2362 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2363
2364 /* price-and-cut loop */
2365 npricedcolvars = transprob->ncolvars;
2366 mustprice = TRUE;
2367 mustsepa = separate;
2369 *cutoff = FALSE;
2371 nsepastallrounds = 0;
2375 lp->installing = FALSE;
2376 while( !(*cutoff) && !(*unbounded) && !(*lperror) && (mustprice || mustsepa || delayedsepa) )
2377 {
2378 SCIPsetDebugMsg(set, "-------- node solving loop --------\n");
2379 assert(lp->flushed);
2380 assert(lp->solved);
2381
2382 /* solve the LP with pricing in new variables */
2383 while( mustprice && !(*lperror) )
2384 {
2385 SCIP_CALL( SCIPpriceLoop(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
2386 pricestore, sepastore, cutpool, branchcand, eventqueue, eventfilter, cliquetable, root, root, -1, &npricedcolvars,
2388
2389 mustprice = FALSE;
2390
2391 assert(lp->flushed);
2392 assert(lp->solved || *lperror);
2393
2394 /* update lower bound w.r.t. the LP solution */
2395 if( !(*lperror) && !(*pricingaborted) && SCIPlpIsRelax(lp) )
2396 {
2397 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2398 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2399 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2400
2401 /* update node estimate */
2402 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2403
2404 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2405 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2406 }
2407 else
2408 {
2409 SCIPsetDebugMsg(set, " -> error solving LP or pricing aborted. keeping old bound: %g\n", SCIPnodeGetLowerbound(focusnode));
2410 }
2411
2412 /* display node information line for root node */
2413 if( root && (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH )
2414 {
2415 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
2416 }
2417
2418 if( !(*lperror) )
2419 {
2420 /* call propagators that are applicable during LP solving loop only if the node is not cut off */
2421 if( SCIPsetIsLT(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound) )
2422 {
2423 SCIP_Longint oldnboundchgs;
2424 SCIP_Longint oldninitconssadded;
2425 SCIP_Bool postpone;
2426
2427 oldnboundchgs = stat->nboundchgs;
2429
2430 SCIPsetDebugMsg(set, " -> LP solved: call propagators that are applicable during LP solving loop\n");
2431
2432 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, FALSE,
2435 assert(!postpone);
2436
2437 if( stat->ninitconssadded != oldninitconssadded )
2438 {
2439 SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n", oldninitconssadded, stat->ninitconssadded);
2440
2441 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2442 branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2443 }
2444
2445 if( !(*cutoff) && !(*unbounded) )
2446 {
2447 /* if we found something, solve LP again */
2448 if( !lp->flushed )
2449 {
2450 SCIPsetDebugMsg(set, " -> found reduction: resolve LP\n");
2451
2452 /* in the root node, remove redundant rows permanently from the LP */
2453 if( root )
2454 {
2455 SCIP_CALL( SCIPlpFlush(lp, blkmem, set, transprob, eventqueue) );
2456 SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2457 }
2458
2459 /* resolve LP */
2460 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2461 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2462 assert(lp->flushed);
2463 assert(lp->solved || *lperror);
2464
2465 /* remove previous primal ray, store new one if LP is unbounded */
2466 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2467
2468 mustprice = TRUE;
2470 }
2471 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective
2472 * value which is added to the LP value; because of the loose status, the LP might not be reoptimized,
2473 * but the lower bound of the node needs to be updated
2474 */
2475 else if( stat->nboundchgs > oldnboundchgs )
2476 {
2478
2479 if( lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2480 {
2481 assert(lp->flushed);
2482 assert(lp->solved);
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 }
2495 }
2496 }
2497 }
2498
2499 /* call primal heuristics that are applicable during node LP solving loop */
2501 {
2502 SCIP_Bool foundsol;
2503
2504 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGLPLOOP,
2505 FALSE, &foundsol, unbounded) );
2507
2508 *lperror = *lperror || lp->resolvelperror;
2509 } /*lint !e438*/
2510 }
2511 assert(lp->flushed || *cutoff || *unbounded);
2512 assert(lp->solved || *lperror || *cutoff || *unbounded);
2513
2514 /* check, if we exceeded the separation round limit */
2516 && stat->nseparounds < maxseparounds
2518 && !(*cutoff);
2519
2520 /* if separators were delayed, we want to apply a final separation round with the delayed separators */
2521 delayedsepa = delayedsepa && !mustsepa && !(*cutoff); /* if regular separation applies, we ignore delayed separators */
2523
2524 if( mustsepa )
2525 {
2526 /* if the LP is infeasible, unbounded, exceeded the objective limit or a global performance limit was reached,
2527 * we don't need to separate cuts
2528 * (the global limits are only checked at the root node in order to not query system time too often)
2529 */
2530 if( !separate || (*cutoff) || (*unbounded)
2532 || SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)
2533 || (root && SCIPsolveIsStopped(set, stat, FALSE)) )
2534 {
2535 mustsepa = FALSE;
2537 }
2538 else
2539 assert(!(*lperror));
2540 }
2541
2542 /* separation (needs not to be done completely, because we just want to increase the lower bound) */
2543 if( mustsepa )
2544 {
2545 SCIP_Longint olddomchgcount;
2546 SCIP_Longint oldninitconssadded;
2547 SCIP_Bool enoughcuts;
2548
2549 assert(lp->flushed);
2550 assert(lp->solved);
2552
2555
2556 mustsepa = FALSE;
2557 enoughcuts = (SCIPsetGetSepaMaxcuts(set, root) == 0);
2558
2559 /* global cut pool separation */
2560 if( !enoughcuts && !delayedsepa )
2561 {
2562 SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2564
2565 if( *cutoff )
2566 {
2567 SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2568 }
2569 }
2570 assert(lp->flushed);
2571 assert(lp->solved);
2573
2574 /* constraint separation */
2575 SCIPsetDebugMsg(set, "constraint separation\n");
2576
2577 /* separate constraints and LP */
2578 if( !(*cutoff) && !(*lperror) && !enoughcuts && lp->solved )
2579 {
2580 /* apply a separation round */
2581 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal, tree,
2582 lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2585
2586 /* if we are close to the stall round limit, also call the delayed separators */
2587 if( !(*cutoff) && !(*lperror) && !enoughcuts && lp->solved
2590 {
2591 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal,
2592 tree, lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2595 }
2596 }
2597
2598 /* call global cut pool separation again since separators may add cuts to the pool instead of the sepastore */
2599 if( !(*cutoff) && !(*lperror) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && !enoughcuts && lp->solved )
2600 {
2601 SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2603
2604 if( *cutoff )
2605 {
2606 SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2607 }
2608 }
2609
2610 /* delayed global cut pool separation */
2611 if( !(*cutoff) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && SCIPsepastoreGetNCuts(sepastore) == 0 &&
2612 !enoughcuts )
2613 {
2614 assert( !(*lperror) );
2615
2616 SCIP_CALL( cutpoolSeparate(delayedcutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, TRUE,
2617 root, actdepth, &enoughcuts, cutoff) );
2618
2619 if( *cutoff )
2620 {
2621 SCIPsetDebugMsg(set, " -> delayed global cut pool detected cutoff\n");
2622 }
2624 assert(lp->flushed);
2625 assert(lp->solved);
2626 }
2627
2628 assert(*cutoff || *lperror || SCIPlpIsSolved(lp));
2636
2637 if( *cutoff || *lperror
2640 {
2641 /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
2642 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
2643 }
2644 else
2645 {
2646 /* apply found cuts */
2647 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2648 branchcand, eventqueue, eventfilter, cliquetable, root, SCIP_EFFICIACYCHOICE_LP, cutoff) );
2649
2650 if( !(*cutoff) )
2651 {
2652 mustprice = mustprice || !lp->flushed || (transprob->ncolvars != npricedcolvars);
2653 mustsepa = mustsepa || !lp->flushed;
2654
2655 /* if a new bound change (e.g. a cut with only one column) was found, propagate domains again */
2656 if( stat->domchgcount != olddomchgcount )
2657 {
2658 SCIPsetDebugMsg(set, " -> separation changed bound: propagate again\n");
2659
2661
2662 /* in the root node, remove redundant rows permanently from the LP */
2663 if( root )
2664 {
2665 SCIP_CALL( SCIPlpFlush(lp, blkmem, set, transprob, eventqueue) );
2666 SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2667 }
2668 }
2669
2670 if( stat->ninitconssadded != oldninitconssadded )
2671 {
2672 SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n",
2674
2675 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2676 branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2677 }
2678
2679 if( !(*cutoff) )
2680 {
2681 SCIP_Real lpobjval;
2682
2683 /* solve LP (with dual simplex) */
2684 SCIPsetDebugMsg(set, "separation: solve LP\n");
2685 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2686 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2687 assert(lp->flushed);
2688 assert(lp->solved || *lperror);
2689
2690 /* remove previous primal ray, store new one if LP is unbounded */
2691 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2692
2693 if( !(*lperror) )
2694 {
2695 SCIP_Bool stalling;
2696
2697 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
2698 * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
2699 * bound of the node needs to be updated
2700 */
2701 if( stat->domchgcount != olddomchgcount && (!mustprice || mustsepa) && !(*cutoff)
2702 && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2703 {
2704 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2705 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2706 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2707
2708 /* update node estimate */
2709 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2710
2711 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2712 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2713 }
2714
2715 /* check if we are stalling
2716 * If we have an LP solution, then we are stalling if
2717 * we had an LP solution before and
2718 * the LP value did not improve and
2719 * the number of fractional variables did not decrease.
2720 * If we do not have an LP solution, then we are stalling if the solution status of the LP did not change.
2721 */
2723 {
2724 SCIP_Real objreldiff;
2725 int nfracs;
2726
2727 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nfracs, NULL,
2728 NULL) );
2729 lpobjval = SCIPlpGetObjval(lp, set, transprob);
2730
2732 SCIPsetDebugMsg(set, " -> LP bound moved from %g to %g (reldiff: %g)\n",
2733 stalllpobjval, lpobjval, objreldiff);
2734
2736 objreldiff <= 1e-04 &&
2737 nfracs >= (0.9 - 0.1 * nsepastallrounds) * stallnfracs);
2738
2739 stalllpobjval = lpobjval;
2741 } /*lint !e438*/
2742 else
2743 {
2745 }
2746
2747 if( !stalling )
2748 {
2749 nsepastallrounds = 0;
2750 lp->installing = FALSE;
2751 }
2752 else
2753 {
2755 }
2757
2758 /* tell LP that we are (close to) stalling */
2760 lp->installing = TRUE;
2761 SCIPsetDebugMsg(set, " -> nsepastallrounds=%d/%d\n", nsepastallrounds, maxnsepastallrounds);
2762 }
2763 }
2764 }
2765 }
2766 assert(*cutoff || *lperror || (lp->flushed && lp->solved)); /* cutoff: LP may be unsolved due to bound changes */
2767
2768 SCIPsetDebugMsg(set, "separation round %d/%d finished (%d/%d stall rounds): mustprice=%u, mustsepa=%u, delayedsepa=%u, propagateagain=%u\n",
2770
2771 /* increase separation round counter */
2772 stat->nseparounds++;
2773 }
2774 }
2775
2776 if( root && nsepastallrounds >= maxnsepastallrounds )
2777 {
2778 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
2779 "Truncate separation round because of stalling (%d stall rounds).\n", maxnsepastallrounds);
2780 }
2781
2782 if( !*lperror )
2783 {
2784 /* update pseudo cost values for continuous variables, if it should be delayed */
2785 SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, FALSE, set->branch_delaypscost) );
2786 }
2787
2788 /* update lower bound w.r.t. the LP solution */
2789 if( *cutoff )
2790 {
2791 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
2792 }
2793 else if( !(*lperror) )
2794 {
2795 assert(lp->flushed);
2796 assert(lp->solved);
2797
2798 if( SCIPlpIsRelax(lp) )
2799 {
2800 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2801 }
2802
2803 /* update node estimate */
2804 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2805
2806 /* issue LPSOLVED event */
2808 {
2810 SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
2811 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
2812 }
2813
2814 /* if the LP is a relaxation and we are not solving exactly, then we may analyze an infeasible or bound exceeding
2815 * LP (not necessary in the root node) and cut off the current node
2816 */
2817 if( !set->misc_exactsolve && !root && SCIPlpIsRelax(lp) && SCIPprobAllColsInLP(transprob, set, lp)
2819 {
2820 SCIP_CALL( SCIPconflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt,
2821 lp, branchcand, eventqueue, cliquetable, NULL) );
2822 *cutoff = TRUE;
2823 }
2824 }
2825 /* check for unboundedness */
2826 if( !(*lperror) )
2827 {
2829 /* 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 */
2830 }
2831
2832 lp->installing = FALSE;
2833
2834 SCIPsetDebugMsg(set, " -> final lower bound: %g (LP status: %d, LP obj: %g)\n",
2836 (*cutoff || *unbounded) ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
2837
2838 return SCIP_OKAY; /*lint !e438*/
2839}
2840
2841/** updates the current lower bound with the pseudo objective value, cuts off node by bounding, and applies conflict
2842 * analysis if the pseudo objective lead to the cutoff
2843 */
2844static
2846 BMS_BLKMEM* blkmem, /**< block memory buffers */
2847 SCIP_SET* set, /**< global SCIP settings */
2848 SCIP_STAT* stat, /**< dynamic problem statistics */
2849 SCIP_PROB* transprob, /**< tranformed problem after presolve */
2850 SCIP_PROB* origprob, /**< original problem */
2851 SCIP_PRIMAL* primal, /**< primal data */
2852 SCIP_TREE* tree, /**< branch and bound tree */
2853 SCIP_REOPT* reopt, /**< reoptimization data structure */
2854 SCIP_LP* lp, /**< LP data */
2855 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2856 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2857 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2858 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2859 SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
2860 )
2861{
2862 assert(transprob != NULL);
2863 assert(origprob != NULL);
2864 assert(primal != NULL);
2865 assert(cutoff != NULL);
2866
2867 if( !(*cutoff) )
2868 {
2869 SCIP_NODE* focusnode;
2870 SCIP_Real pseudoobjval;
2871
2872 /* get current focus node */
2873 focusnode = SCIPtreeGetFocusNode(tree);
2874
2875 /* update lower bound w.r.t. the pseudo solution */
2876 pseudoobjval = SCIPlpGetPseudoObjval(lp, set, transprob);
2877 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, pseudoobjval);
2878 SCIPsetDebugMsg(set, " -> lower bound: %g [%g] (pseudoobj: %g [%g]), cutoff bound: %g [%g]\n",
2879 SCIPnodeGetLowerbound(focusnode), SCIPprobExternObjval(transprob, origprob, set, SCIPnodeGetLowerbound(focusnode)) + SCIPgetOrigObjoffset(set->scip),
2880 pseudoobjval, SCIPprobExternObjval(transprob, origprob, set, pseudoobjval) + SCIPgetOrigObjoffset(set->scip),
2881 primal->cutoffbound, SCIPprobExternObjval(transprob, origprob, set, primal->cutoffbound) + SCIPgetOrigObjoffset(set->scip));
2882
2883 /* check for infeasible node by bounding */
2884 if( (set->misc_exactsolve && SCIPnodeGetLowerbound(focusnode) >= primal->cutoffbound)
2885 || (!set->misc_exactsolve && SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)) )
2886 {
2887 SCIPsetDebugMsg(set, "node is cut off by bounding (lower=%g, upper=%g)\n",
2888 SCIPnodeGetLowerbound(focusnode), primal->cutoffbound);
2889 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
2890 *cutoff = TRUE;
2891
2892 /* call pseudo conflict analysis, if the node is cut off due to the pseudo objective value */
2893 if( pseudoobjval >= primal->cutoffbound && !SCIPsetIsInfinity(set, primal->cutoffbound) && !SCIPsetIsInfinity(set, -pseudoobjval) )
2894 {
2895 SCIP_CALL( SCIPconflictAnalyzePseudo(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, NULL) );
2896 }
2897 }
2898 }
2899
2900 return SCIP_OKAY;
2901}
2902
2903/** marks all relaxators to be unsolved */
2904static
2906 SCIP_SET* set, /**< global SCIP settings */
2907 SCIP_RELAXATION* relaxation /**< global relaxation data */
2908 )
2909{
2910 int r;
2911
2912 assert(set != NULL);
2913 assert(relaxation != NULL);
2914
2916
2917 for( r = 0; r < set->nrelaxs; ++r )
2918 SCIPrelaxMarkUnsolved(set->relaxs[r]);
2919}
2920
2921/** solves the current node's LP in a price-and-cut loop */
2922static
2924 BMS_BLKMEM* blkmem, /**< block memory buffers */
2925 SCIP_SET* set, /**< global SCIP settings */
2926 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2927 SCIP_STAT* stat, /**< dynamic problem statistics */
2928 SCIP_MEM* mem, /**< block memory pools */
2929 SCIP_PROB* origprob, /**< original problem */
2930 SCIP_PROB* transprob, /**< transformed problem after presolve */
2931 SCIP_PRIMAL* primal, /**< primal data */
2932 SCIP_TREE* tree, /**< branch and bound tree */
2933 SCIP_REOPT* reopt, /**< reoptimization data structure */
2934 SCIP_LP* lp, /**< LP data */
2935 SCIP_RELAXATION* relaxation, /**< relaxators */
2936 SCIP_PRICESTORE* pricestore, /**< pricing storage */
2937 SCIP_SEPASTORE* sepastore, /**< separation storage */
2938 SCIP_CUTPOOL* cutpool, /**< global cut pool */
2939 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
2940 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2941 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2942 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2943 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
2944 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2945 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2946 SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
2947 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
2948 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
2949 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
2950 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
2951 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2952 SCIP_Bool* unbounded, /**< pointer to store TRUE, if an unbounded ray was found in the LP */
2953 SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
2954 SCIP_Bool* pricingaborted /**< pointer to store TRUE, if the pricing was aborted and the lower bound
2955 * must not be used */
2956 )
2957{
2958 SCIP_Longint nlpiterations;
2959 SCIP_Longint nlps;
2960 SCIP_Longint nzeroitlps;
2961
2962 assert(stat != NULL);
2963 assert(tree != NULL);
2965 assert(cutoff != NULL);
2966 assert(unbounded != NULL);
2967 assert(lperror != NULL);
2968 assert(*cutoff == FALSE);
2969 assert(*unbounded == FALSE);
2970 assert(*lperror == FALSE);
2971
2972 nlps = stat->nlps;
2975
2976 if( !initiallpsolved )
2977 {
2978 /* load and solve the initial LP of the node */
2979 SCIP_CALL( solveNodeInitialLP(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
2980 pricestore, sepastore, cutpool, branchcand, eventfilter, eventqueue, cliquetable, newinitconss, cutoff, lperror) );
2981
2982 assert(*cutoff || *lperror || (lp->flushed && lp->solved));
2983 SCIPsetDebugMsg(set, "price-and-cut-loop: initial LP status: %d, LP obj: %g\n",
2984 SCIPlpGetSolstat(lp),
2986
2987 /* update initial LP iteration counter */
2988 stat->ninitlps += stat->nlps - nlps;
2990
2991 /* In the root node, we try if the initial LP solution is feasible to avoid expensive setup of data structures in
2992 * separators; in case the root LP is aborted, e.g., by hitting the time limit, we do not check the LP solution
2993 * since the corresponding data structures have not been updated.
2994 */
2995 if( SCIPtreeGetCurrentDepth(tree) == 0 && !(*cutoff) && !(*lperror)
2997 && !SCIPsolveIsStopped(set, stat, FALSE) )
2998 {
2999 SCIP_Bool checklprows;
3000 SCIP_Bool stored;
3001 SCIP_SOL* sol;
3002 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
3003
3004 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
3005
3008 else
3009 checklprows = TRUE;
3010
3011#ifndef NDEBUG
3012 /* in the debug mode we want to explicitly check if the solution is feasible if it was stored */
3013 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
3014 eventqueue, eventfilter, sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
3015
3016 if( stored )
3017 {
3018 SCIP_Bool feasible;
3019
3020 SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, FALSE, FALSE, TRUE, TRUE,
3021 checklprows, &feasible) );
3023 }
3024
3025 SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) );
3026#else
3027 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
3028 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
3029#endif
3030 if( stored )
3031 {
3032 stat->nlpsolsfound++;
3033
3034 if( primal->nbestsolsfound != oldnbestsolsfound )
3035 {
3036 stat->nlpbestsolsfound++;
3038 }
3039
3040 if( set->reopt_enable )
3041 {
3042 assert(reopt != NULL);
3044 SCIPlpGetSolstat(lp), tree->root == tree->focusnode, TRUE, tree->focusnode->lowerbound,
3045 tree->effectiverootdepth) );
3046 }
3047 }
3048
3050 *unbounded = TRUE;
3051 }
3052 }
3053 else
3054 {
3055 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob,
3056 origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE,
3057 cutoff) );
3058 }
3059 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3060
3061 /* check for infeasible node by bounding */
3062 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
3063#ifdef SCIP_DEBUG
3064 if( *cutoff )
3065 {
3066 if( SCIPtreeGetCurrentDepth(tree) == 0 )
3067 {
3068 SCIPsetDebugMsg(set, "solution cuts off root node, stop solution process\n");
3069 }
3070 else
3071 {
3072 SCIPsetDebugMsg(set, "solution cuts off node\n");
3073 }
3074 }
3075#endif
3076
3077 if( !(*cutoff) && !(*lperror) )
3078 {
3079 SCIP_Longint oldninitconssadded;
3080 SCIP_Longint oldnboundchgs;
3081 SCIP_Longint olddomchgcount;
3082 int oldnpricedvars;
3083 int oldncutsapplied;
3084
3085 oldnpricedvars = transprob->ncolvars;
3088 oldnboundchgs = stat->nboundchgs;
3090
3091 /* solve the LP with price-and-cut*/
3092 SCIP_CALL( priceAndCutLoop(blkmem, set, messagehdlr, stat, mem, transprob, origprob, primal, tree, reopt, lp,
3093 pricestore, sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter,
3094 eventqueue, cliquetable, fullseparation, propagateagain, cutoff, unbounded, lperror, pricingaborted) );
3095
3096 /* check if the problem was changed and the relaxation needs to be resolved */
3097 if( (transprob->ncolvars != oldnpricedvars) || (stat->ninitconssadded != oldninitconssadded) ||
3099 (stat->domchgcount != olddomchgcount) )
3100 {
3102 markRelaxsUnsolved(set, relaxation);
3103 }
3104 }
3105 assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3106
3107 /* if there is no LP error, then *unbounded should be TRUE, iff the LP solution status is unboundedray */
3109
3110 /* 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,
3111 * 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
3112 * is not a feasible lower bound for the solutions in the current subtree.
3113 * In this case, the LP has to be solved to optimality by temporarily removing the cutoff bound.
3114 */
3116 && !(*cutoff) )
3117 {
3118 SCIP_Real tmpcutoff;
3119
3120 /* temporarily disable cutoffbound, which also disables the objective limit */
3121 tmpcutoff = lp->cutoffbound;
3123
3124 lp->solved = FALSE;
3125 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) );
3126
3127 /* reinstall old cutoff bound */
3128 lp->cutoffbound = tmpcutoff;
3129
3130 SCIPsetDebugMsg(set, "re-optimized LP without cutoff bound: LP status: %d, LP obj: %g\n",
3131 SCIPlpGetSolstat(lp), *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
3132
3133 /* lp solstat should not be objlimit, since the cutoff bound was removed temporarily */
3135 /* lp solstat should not be unboundedray, since the lp was dual feasible */
3137 /* there should be no primal ray, since the lp was dual feasible */
3138 assert(primal->primalray == NULL);
3140 {
3141 *cutoff = TRUE;
3142 }
3143 }
3144
3145 assert(!(*pricingaborted) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL /* cppcheck-suppress assertWithSideEffect */
3147
3148 assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3149
3150 /* update node's LP iteration counter */
3151 stat->nnodelps += stat->nlps - nlps;
3154
3155 /* update number of root node LPs and iterations if the root node was processed */
3156 if( SCIPnodeGetDepth(tree->focusnode) == 0 )
3157 {
3158 stat->nrootlps += stat->nlps - nlps;
3160 }
3161
3162 return SCIP_OKAY;
3163}
3164
3165/** calls relaxators */
3166static
3168 SCIP_SET* set, /**< global SCIP settings */
3169 SCIP_STAT* stat, /**< dynamic problem statistics */
3170 SCIP_TREE* tree, /**< branch and bound tree */
3171 SCIP_RELAXATION* relaxation, /**< relaxators */
3172 SCIP_PROB* transprob, /**< transformed problem */
3173 SCIP_PROB* origprob, /**< original problem */
3174 int depth, /**< depth of current node */
3175 SCIP_Bool beforelp, /**< should the relaxators with non-negative or negative priority be called? */
3176 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3177 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3178 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3179 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called
3180 * again */
3181 SCIP_Bool* relaxcalled /**< pointer to store TRUE, if at least one relaxator was called (unmodified
3182 * otherwise) */
3183 )
3184{
3186 SCIP_Real lowerbound;
3187 int r;
3188
3189 assert(set != NULL);
3190 assert(relaxation != NULL);
3191 assert(cutoff != NULL);
3196 assert(!(*cutoff));
3197
3198 /* sort by priority */
3200
3201 for( r = 0; r < set->nrelaxs && !(*cutoff); ++r )
3202 {
3203 if( beforelp != (SCIPrelaxGetPriority(set->relaxs[r]) >= 0) )
3204 continue;
3205
3206 *relaxcalled = TRUE;
3207
3208 lowerbound = -SCIPsetInfinity(set);
3209
3210 SCIP_CALL( SCIPrelaxExec(set->relaxs[r], set, tree, stat, depth, &lowerbound, &result) );
3211
3212 switch( result )
3213 {
3214 case SCIP_CUTOFF:
3215 *cutoff = TRUE;
3216 SCIPsetDebugMsg(set, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(set->relaxs[r]));
3217 /* @todo does it make sense to proceed if the node is proven to be infeasible? */
3218 return SCIP_OKAY;
3219
3220 case SCIP_CONSADDED:
3221 *solvelpagain = TRUE; /* the separation for new constraints should be called */
3222 *propagateagain = TRUE; /* the propagation for new constraints should be called */
3223 break;
3224
3225 case SCIP_REDUCEDDOM:
3226 *solvelpagain = TRUE;
3228 break;
3229
3230 case SCIP_SEPARATED:
3231 *solvelpagain = TRUE;
3232 break;
3233
3234 case SCIP_SUSPENDED:
3236 break;
3237
3238 case SCIP_SUCCESS:
3239 case SCIP_DIDNOTRUN:
3240 break;
3241
3242 default:
3243 SCIPerrorMessage("invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(set->relaxs[r]));
3244 return SCIP_INVALIDRESULT;
3245 } /*lint !e788*/
3246
3248 {
3249 SCIP_NODE* focusnode;
3250
3251 focusnode = SCIPtreeGetFocusNode(tree);
3252 assert(focusnode != NULL);
3254
3255 /* update lower bound w.r.t. the lower bound given by the relaxator */
3256 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, lowerbound);
3257 SCIPsetDebugMsg(set, " -> new lower bound given by relaxator %s: %g\n",
3258 SCIPrelaxGetName(set->relaxs[r]), lowerbound);
3259 }
3260 }
3261
3262 return SCIP_OKAY;
3263}
3264
3265/** enforces constraints by branching, separation, or domain reduction */
3266static
3268 BMS_BLKMEM* blkmem, /**< block memory buffers */
3269 SCIP_SET* set, /**< global SCIP settings */
3270 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3271 SCIP_STAT* stat, /**< dynamic problem statistics */
3272 SCIP_PROB* prob, /**< transformed problem after presolve */
3273 SCIP_PRIMAL* primal, /**< primal data */
3274 SCIP_TREE* tree, /**< branch and bound tree */
3275 SCIP_LP* lp, /**< LP data */
3276 SCIP_RELAXATION* relaxation, /**< global relaxation data */
3277 SCIP_SEPASTORE* sepastore, /**< separation storage */
3278 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3279 SCIP_Bool* branched, /**< pointer to store whether a branching was created */
3280 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3281 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the LP/pseudo solution is infeasible */
3282 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3283 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3284 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
3285 SCIP_Bool forced /**< should enforcement of pseudo solution be forced? */
3286 )
3287{
3289 SCIP_SOL* relaxsol = NULL;
3290 SCIP_Real pseudoobjval;
3291 SCIP_Bool resolved;
3292 SCIP_Bool objinfeasible;
3293 SCIP_Bool enforcerelaxsol;
3294 int h;
3295
3296 assert(set != NULL);
3297 assert(stat != NULL);
3298 assert(tree != NULL);
3300 assert(branched != NULL);
3301 assert(cutoff != NULL);
3302 assert(infeasible != NULL);
3306 assert(!(*cutoff));
3308 assert(!(*solvelpagain));
3310
3311 *branched = FALSE;
3312 /**@todo avoid checking the same pseudosolution twice */
3313
3314 /* enforce (best) relaxation solution if the LP has a worse objective value */
3316 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, prob)));
3317
3318 /* check if all constraint handlers implement the enforelax callback, otherwise enforce the LP solution */
3319 for( h = 0; h < set->nconshdlrs && enforcerelaxsol; ++h )
3320 {
3321 if( set->conshdlrs_enfo[h]->consenforelax == NULL && ((! set->conshdlrs_enfo[h]->needscons) ||
3322 (set->conshdlrs_enfo[h]->nconss > 0)) )
3323 {
3324 SCIP_VERBLEVEL verblevel;
3325
3327
3328 verblevel = SCIP_VERBLEVEL_FULL;
3329
3330 if( !stat->disableenforelaxmsg && set->disp_verblevel == SCIP_VERBLEVEL_HIGH )
3331 {
3332 verblevel = SCIP_VERBLEVEL_HIGH;
3333
3334 /* remember that the disable relaxation enforcement message was posted and only post it again if the
3335 * verblevel is SCIP_VERBLEVEL_FULL
3336 */
3337 stat->disableenforelaxmsg = TRUE;
3338 }
3339 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel, "Disable enforcement of relaxation solutions"
3340 " since constraint handler %s does not implement enforelax-callback\n",
3341 SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3342 }
3343 }
3344
3345 /* enforce constraints by branching, applying additional cutting planes (if LP is being processed),
3346 * introducing new constraints, or tighten the domains
3347 */
3348#ifndef SCIP_NDEBUG
3349 if( enforcerelaxsol )
3350 {
3351 SCIPsetDebugMsg(set, "enforcing constraints on relaxation solution\n");
3352 }
3353 else
3354 {
3355 SCIPsetDebugMsg(set, "enforcing constraints on %s solution\n", SCIPtreeHasFocusNodeLP(tree) ? "LP" : "pseudo");
3356 }
3357#endif
3358
3359 /* check, if the solution is infeasible anyway due to it's objective value */
3362 else
3363 {
3364 pseudoobjval = SCIPlpGetPseudoObjval(lp, set, prob);
3366 }
3367
3368 /* during constraint enforcement, generated cuts should enter the LP in any case; otherwise, a constraint handler
3369 * would fail to enforce its constraints if it relies on the modification of the LP relaxation
3370 */
3371 SCIPsepastoreStartForceCuts(sepastore);
3372
3373 /* enforce constraints until a handler resolved an infeasibility with cutting off the node, branching,
3374 * reducing a domain, or separating a cut
3375 * if a constraint handler introduced new constraints to enforce his constraints, the newly added constraints
3376 * have to be enforced themselves
3377 */
3378 resolved = FALSE;
3379
3380 /* in case the relaxation solution should be enforced, we need to create the corresponding solution for the enforelax callbacks */
3381 if( enforcerelaxsol )
3382 {
3383 SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
3384 }
3385
3386 for( h = 0; h < set->nconshdlrs && !resolved; ++h )
3387 {
3388 assert(SCIPsepastoreGetNCuts(sepastore) == 0); /* otherwise, the LP should have been resolved first */
3389
3390 /* enforce LP, pseudo, or relaxation solution */
3391 if( enforcerelaxsol )
3392 {
3393 SCIPsetDebugMsg(set, "enforce relaxation solution with value %g\n", SCIPrelaxationGetSolObj(relaxation));
3394
3395 SCIP_CALL( SCIPconshdlrEnforceRelaxSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore,
3396 relaxsol, *infeasible, &result) );
3397 }
3398 else if( SCIPtreeHasFocusNodeLP(tree) )
3399 {
3400 SCIPsetDebugMsg(set, "enforce LP solution with value %g\n", SCIPlpGetObjval(lp, set, prob));
3401
3402 assert(lp->flushed);
3403 assert(lp->solved);
3405 SCIP_CALL( SCIPconshdlrEnforceLPSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore, *infeasible,
3406 &result) );
3407 }
3408 else
3409 {
3410 SCIP_CALL( SCIPconshdlrEnforcePseudoSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, branchcand, *infeasible,
3412 if( SCIPsepastoreGetNCuts(sepastore) != 0 )
3413 {
3414 SCIPerrorMessage("pseudo enforcing method of constraint handler <%s> separated cuts\n",
3415 SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3416 return SCIP_INVALIDRESULT;
3417 }
3418 }
3419 SCIPsetDebugMsg(set, "enforcing of <%s> returned result %d\n", SCIPconshdlrGetName(set->conshdlrs_enfo[h]), result);
3420
3421 switch( result )
3422 {
3423 case SCIP_CUTOFF:
3424 assert(tree->nchildren == 0);
3425 *cutoff = TRUE;
3426 *infeasible = TRUE;
3427 resolved = TRUE;
3428 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in enforcement\n",
3429 SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3430 break;
3431
3432 case SCIP_CONSADDED:
3433 assert(tree->nchildren == 0);
3434 *infeasible = TRUE;
3435 *propagateagain = TRUE; /* the propagation for new constraints should be called */
3436 *solvelpagain = TRUE; /* the separation for new constraints should be called */
3438 markRelaxsUnsolved(set, relaxation);
3439 resolved = TRUE;
3440 break;
3441
3442 case SCIP_REDUCEDDOM:
3443 assert(tree->nchildren == 0);
3444 *infeasible = TRUE;
3446 *solvelpagain = TRUE;
3448 markRelaxsUnsolved(set, relaxation);
3449 resolved = TRUE;
3450 break;
3451
3452 case SCIP_SEPARATED:
3453 assert(tree->nchildren == 0);
3454 assert(SCIPsepastoreGetNCuts(sepastore) > 0);
3455 *infeasible = TRUE;
3456 *solvelpagain = TRUE;
3458 markRelaxsUnsolved(set, relaxation);
3459 resolved = TRUE;
3460 break;
3461
3462 case SCIP_BRANCHED:
3463 assert(tree->nchildren >= 1);
3464 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3465 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3466 *infeasible = TRUE;
3467 *branched = TRUE;
3468 resolved = TRUE;
3469
3470 /* increase the number of internal nodes */
3471 stat->ninternalnodes++;
3472 stat->ntotalinternalnodes++;
3473 break;
3474
3475 case SCIP_SOLVELP:
3476 /* either LP was not solved, or it is not solved anymore (e.g., because feastol has been tightened by some constraint handler) */
3477 assert(!SCIPtreeHasFocusNodeLP(tree) || !lp->solved);
3478 assert(tree->nchildren == 0);
3479 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3480 *infeasible = TRUE;
3481 *solvelpagain = TRUE;
3482 resolved = TRUE;
3483 SCIPtreeSetFocusNodeLP(tree, TRUE); /* the node's LP must be solved */
3484 break;
3485
3486 case SCIP_INFEASIBLE:
3487 assert(tree->nchildren == 0);
3488 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3489 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3490 *infeasible = TRUE;
3491 break;
3492
3493 case SCIP_FEASIBLE:
3494 assert(tree->nchildren == 0);
3495 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3496 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3497 break;
3498
3499 case SCIP_DIDNOTRUN:
3500 assert(tree->nchildren == 0);
3501 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3502 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3504 *infeasible = TRUE;
3505 break;
3506
3507 default:
3508 SCIPerrorMessage("invalid result code <%d> from enforcing method of constraint handler <%s>\n",
3509 result, SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3510 return SCIP_INVALIDRESULT;
3511 } /*lint !e788*/
3512
3513 /* the enforcement method may add a primal solution, after which the LP status could be set to
3514 * objective limit reached
3515 */
3517 {
3518 *cutoff = TRUE;
3519 *infeasible = TRUE;
3520 resolved = TRUE;
3521 SCIPsetDebugMsg(set, " -> LP exceeded objective limit\n");
3522
3523 /* If we used the probing mode during branching, it might happen that we added a constraint or global bound
3524 * and returned SCIP_CONSADDED or SCIP_REDUCEDDOM, but when reoptimizing the LP after ending the probing mode,
3525 * this leads to hitting the objective limit. In this case, we do not need to propagate or solve the LP again.
3526 */
3529 }
3530
3531 assert(!(*branched) || (resolved && !(*cutoff) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3532 assert(!(*cutoff) || (resolved && !(*branched) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3533 assert(*infeasible || (!resolved && !(*branched) && !(*cutoff) && !(*propagateagain) && !(*solvelpagain)));
3534 assert(!(*propagateagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3535 assert(!(*solvelpagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3536 }
3537 assert(!objinfeasible || *infeasible);
3539 assert(*cutoff || *solvelpagain || SCIPsepastoreGetNCuts(sepastore) == 0);
3540
3541 /* in case the relaxation solution was enforced, free the created solution */
3542 if( enforcerelaxsol )
3543 {
3544 SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
3545 }
3546
3547 /* deactivate the cut forcing of the constraint enforcement */
3548 SCIPsepastoreEndForceCuts(sepastore);
3549
3550 SCIPsetDebugMsg(set, " -> enforcing result: branched=%u, cutoff=%u, infeasible=%u, propagateagain=%u, solvelpagain=%u, resolved=%u\n",
3551 *branched, *cutoff, *infeasible, *propagateagain, *solvelpagain, resolved);
3552
3553 return SCIP_OKAY;
3554}
3555
3556/** applies the cuts stored in the separation store, or clears the store if the node can be cut off */
3557static
3559 BMS_BLKMEM* blkmem, /**< block memory buffers */
3560 SCIP_SET* set, /**< global SCIP settings */
3561 SCIP_STAT* stat, /**< dynamic problem statistics */
3562 SCIP_PROB* transprob, /**< transformed problem */
3563 SCIP_PROB* origprob, /**< original problem */
3564 SCIP_TREE* tree, /**< branch and bound tree */
3565 SCIP_REOPT* reopt, /**< reotimization data structure */
3566 SCIP_LP* lp, /**< LP data */
3567 SCIP_RELAXATION* relaxation, /**< relaxators */
3568 SCIP_SEPASTORE* sepastore, /**< separation storage */
3569 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3570 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3571 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3572 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3573 SCIP_Bool root, /**< is this the initial root LP? */
3574 SCIP_EFFICIACYCHOICE efficiacychoice, /**< type of solution to base efficiacy computation on */
3575 SCIP_Bool* cutoff, /**< pointer to whether the node can be cut off */
3576 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3577 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3578 SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if the node's relaxation has to be solved again */
3579 )
3580{
3581 assert(stat != NULL);
3582 assert(cutoff != NULL);
3585
3586 if( *cutoff )
3587 {
3588 /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
3589 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
3590 }
3591 else if( SCIPsepastoreGetNCuts(sepastore) > 0 )
3592 {
3593 SCIP_Longint olddomchgcount;
3594 int oldncutsapplied;
3595
3598 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
3599 eventqueue, eventfilter, cliquetable, root, efficiacychoice, cutoff) );
3601 *solvelpagain = TRUE;
3603 {
3605 markRelaxsUnsolved(set, relaxation);
3606 }
3607 }
3608
3609 return SCIP_OKAY;
3610}
3611
3612/** updates the cutoff, propagateagain, and solverelaxagain status of the current solving loop */
3613static
3615 SCIP_SET* set, /**< global SCIP settings */
3616 SCIP_STAT* stat, /**< dynamic problem statistics */
3617 SCIP_TREE* tree, /**< branch and bound tree */
3618 int depth, /**< depth of current node */
3619 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3620 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3621 SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if at least one relaxator should be called again */
3622 )
3623{
3624 SCIP_NODE* focusnode;
3625 int r;
3626
3627 assert(set != NULL);
3628 assert(stat != NULL);
3629 assert(cutoff != NULL);
3632
3633 /* check, if the path was cutoff */
3634 *cutoff = *cutoff || (tree->cutoffdepth <= depth);
3635
3636 /* check if branching was already performed */
3637 if( tree->nchildren == 0 )
3638 {
3639 /* check, if the focus node should be repropagated */
3640 focusnode = SCIPtreeGetFocusNode(tree);
3642
3643 /* check, if one of the external relaxations should be solved again */
3644 for( r = 0; r < set->nrelaxs && !(*solverelaxagain); ++r )
3645 *solverelaxagain = *solverelaxagain || ( !SCIPrelaxIsSolved(set->relaxs[r], stat) );
3646 }
3647 else
3648 {
3649 /* if branching was performed, avoid another node loop iteration */
3652 }
3653}
3654
3655/** propagate domains and solve relaxation and lp */
3656static
3658 BMS_BLKMEM* blkmem, /**< block memory buffers */
3659 SCIP_SET* set, /**< global SCIP settings */
3660 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3661 SCIP_STAT* stat, /**< dynamic problem statistics */
3662 SCIP_MEM* mem, /**< block memory pools */
3663 SCIP_PROB* origprob, /**< original problem */
3664 SCIP_PROB* transprob, /**< transformed problem after presolve */
3665 SCIP_PRIMAL* primal, /**< primal data */
3666 SCIP_TREE* tree, /**< branch and bound tree */
3667 SCIP_REOPT* reopt, /**< reoptimization data structure */
3668 SCIP_LP* lp, /**< LP data */
3669 SCIP_RELAXATION* relaxation, /**< global relaxation data */
3670 SCIP_PRICESTORE* pricestore, /**< pricing storage */
3671 SCIP_SEPASTORE* sepastore, /**< separation storage */
3672 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3673 SCIP_CUTPOOL* cutpool, /**< global cut pool */
3674 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
3675 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3676 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
3677 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3678 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3679 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3680 SCIP_NODE* focusnode, /**< focused node */
3681 int actdepth, /**< depth in the b&b tree */
3682 SCIP_Bool propagate, /**< should we propagate */
3683 SCIP_Bool solvelp, /**< should we solve the lp */
3684 SCIP_Bool solverelax, /**< should we solve the relaxation */
3685 SCIP_Bool forcedlpsolve, /**< is there a need for a solve lp */
3686 SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
3687 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
3688 SCIP_Longint* afterlpproplps, /**< pointer to store the last LP count for which AFTERLP propagation was performed */
3689 SCIP_HEURTIMING* heurtiming, /**< timing for running heuristics after propagation call */
3690 int* nlperrors, /**< pointer to store the number of lp errors */
3691 SCIP_Bool* fullpropagation, /**< pointer to store whether we want to do a fullpropagation next time */
3692 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
3693 SCIP_Bool* lpsolved, /**< pointer to store whether the lp was solved */
3694 SCIP_Bool* relaxcalled, /**< pointer to store whether a relaxator was called; initialized with last loop's result */
3695 SCIP_Bool* solvelpagain, /**< pointer to store whether we want to solve the lp again */
3696 SCIP_Bool* solverelaxagain, /**< pointer to store whether we want to solve the relaxation again */
3697 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
3698 SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
3699 SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
3700 SCIP_Bool* stopped, /**< pointer to store whether solving was interrupted */
3701 SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
3702 SCIP_Bool* pricingaborted, /**< pointer to store TRUE, if the pricing was aborted and the lower bound must not be used */
3703 SCIP_Bool* forcedenforcement /**< pointer to store whether the enforcement of pseudo solution should be forced */
3704 )
3705{
3706 SCIP_Bool newinitconss;
3707
3708 assert(set != NULL);
3709 assert(stat != NULL);
3710 assert(origprob != NULL);
3711 assert(transprob != NULL);
3712 assert(tree != NULL);
3713 assert(lp != NULL);
3714 assert(primal != NULL);
3715 assert(pricestore != NULL);
3716 assert(sepastore != NULL);
3717 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3718 assert(branchcand != NULL);
3719 assert(cutpool != NULL);
3720 assert(delayedcutpool != NULL);
3721 assert(conflict != NULL);
3722 assert(SCIPconflictGetNConflicts(conflict) == 0);
3723 assert(eventfilter != NULL);
3724 assert(eventqueue != NULL);
3725 assert(focusnode != NULL);
3727 assert(nlperrors != NULL);
3731 assert(lpsolved != NULL);
3734 assert(cutoff != NULL);
3735 assert(postpone != NULL);
3736 assert(unbounded != NULL);
3737 assert(lperror != NULL);
3740
3742
3743 if( !(*cutoff) && !(*postpone) )
3744 {
3745 SCIP_Longint oldninitconssadded;
3746 SCIP_Longint oldnboundchgs;
3747 SCIP_Bool lpwasflushed;
3748
3749 lpwasflushed = lp->flushed;
3750 oldnboundchgs = stat->nboundchgs;
3752
3753 /* call after LP propagators */
3754 if( ((*afterlpproplps) < stat->nnodelps && (*lpsolved)) || (*relaxcalled) )
3755 {
3756 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3759
3760 /* check, if the path was cutoff */
3761 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3762 *afterlpproplps = stat->nnodelps;
3764 }
3765
3766 /* call before LP propagators */
3767 if( propagate && !(*cutoff) )
3768 {
3769 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3772 }
3773
3776
3777 /* check, if the path was cutoff */
3778 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3779
3780 /* if the LP was flushed and is now no longer flushed, a bound change occurred, and the LP has to be resolved;
3781 * we also have to solve the LP if new intial constraints were added which need to be added to the LP
3782 */
3783 solvelp = solvelp || (lpwasflushed && (!lp->flushed || newinitconss));
3785
3786 /* the number of bound changes was increased by the propagation call, thus the relaxation should be solved again */
3787 if( stat->nboundchgs > oldnboundchgs )
3788 {
3789 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
3790 * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
3791 * bound of the node needs to be updated
3792 */
3793 if( !solvelp && lp->flushed && lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
3794 {
3795 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
3796 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
3797 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
3798
3799 if( SCIPtreeHasFocusNodeLP(tree) )
3800 {
3801 /* update node estimate */
3802 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
3803
3805 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
3806 }
3807 }
3808
3809 solverelax = TRUE;
3810 markRelaxsUnsolved(set, relaxation);
3811 }
3812
3813 /* update lower bound with the pseudo objective value, and cut off node by bounding */
3814 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
3815 conflict, cliquetable, cutoff) );
3816 }
3817 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3818
3819 if( *postpone )
3820 return SCIP_OKAY;
3821
3822 /* call primal heuristics that are applicable after propagation loop before lp solve;
3823 * the first time we go here, we call the before node heuristics instead
3824 */
3825 if( !(*cutoff) && !SCIPtreeProbing(tree) )
3826 {
3827 /* if the heuristics find a new incumbent solution, propagate again */
3828 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, *heurtiming,
3831
3833
3834 /* check if primal heuristics found a solution and we therefore reached a solution limit */
3835 if( SCIPsolveIsStopped(set, stat, FALSE) )
3836 {
3837 /* cppcheck-suppress unassignedVariable */
3838 SCIP_NODE* node;
3839
3840 /* we reached a solution limit and do not want to continue the processing of the current node, but in order to
3841 * allow restarting the optimization process later, we need to create a "branching" with only one child node that
3842 * is a copy of the focusnode
3843 */
3845 SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) );
3846 assert(tree->nchildren >= 1);
3847 *stopped = TRUE;
3848 return SCIP_OKAY;
3849 }
3850
3851 /* if diving produced an LP error, switch back to non-LP node */
3852 if( lp->resolvelperror )
3853 {
3855 lp->resolvelperror = FALSE;
3856 }
3857
3858 if( *propagateagain )
3859 {
3862
3863 return SCIP_OKAY;
3864 }
3865 }
3866
3867 /* solve external relaxations with non-negative priority */
3868 *relaxcalled = FALSE;
3869 if( solverelax && !(*cutoff) )
3870 {
3871 /* clear the storage of external branching candidates */
3873
3874 SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, TRUE,
3877
3878 /* check, if the path was cutoff */
3879 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3880
3881 /* apply found cuts */
3882 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
3883 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
3885
3886 /* update lower bound with the pseudo objective value, and cut off node by bounding */
3887 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
3888 }
3889 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3890
3891 /* check, if we want to solve the LP at this node */
3892 if( solvelp && !(*cutoff) && SCIPtreeHasFocusNodeLP(tree) )
3893 {
3894 *lperror = FALSE;
3895 *unbounded = FALSE;
3896
3897 /* solve the node's LP */
3898 SCIP_CALL( solveNodeLP(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation, pricestore,
3899 sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable,
3901
3902 *lpsolved = TRUE;
3904 SCIPsetDebugMsg(set, " -> LP status: %d, LP obj: %g, iter: %" SCIP_LONGINT_FORMAT ", count: %" SCIP_LONGINT_FORMAT "\n",
3905 SCIPlpGetSolstat(lp),
3906 *cutoff ? SCIPsetInfinity(set) : (*lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob)),
3907 stat->nlpiterations, stat->lpcount);
3908
3909 /* check, if the path was cutoff */
3910 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3911
3912 /* if an error occured during LP solving, switch to pseudo solution */
3913 if( *lperror )
3914 {
3915 if( forcedlpsolve )
3916 {
3917 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
3918 stat->nnodes, stat->nlps);
3919 return SCIP_LPERROR;
3920 }
3922 ++(*nlperrors);
3923 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
3924 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
3925 stat->nnodes, stat->nlps, *nlperrors);
3926 }
3927
3929 {
3932
3933 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
3934 "(node %" SCIP_LONGINT_FORMAT ") LP solver hit %s limit in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead\n",
3935 stat->nnodes, SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT ? "time" : "iteration", stat->nlps);
3936 }
3937
3939 {
3940 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
3941 "(node %" SCIP_LONGINT_FORMAT ") LP relaxation is unbounded (LP %" SCIP_LONGINT_FORMAT ")\n", stat->nnodes, stat->nlps);
3942 }
3943
3944 /* if we solve exactly, the LP claims to be infeasible but the infeasibility could not be proved,
3945 * we have to forget about the LP and use the pseudo solution instead
3946 */
3947 if( !(*cutoff) && !(*lperror) && (set->misc_exactsolve || *pricingaborted) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE
3948 && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound )
3949 {
3950 if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 && transprob->ncontvars > 0 )
3951 {
3952 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",
3953 stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, transprob->ncontvars);
3954 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") -> have to call PerPlex() (feature not yet implemented)\n", stat->nnodes);
3955 /**@todo call PerPlex */
3956 return SCIP_LPERROR;
3957 }
3958 else
3959 {
3962
3963 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
3964 "(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",
3965 stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, SCIPbranchcandGetNPseudoCands(branchcand));
3966 }
3967 }
3968
3969 /* update lower bound with the pseudo objective value, and cut off node by bounding */
3970 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
3971 cliquetable, cutoff) );
3972 }
3973 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3974 assert(*cutoff || !SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3975
3976 /* reset solverelaxagain if no relaxations were solved up to this point (the LP-changes are already included in
3977 * relaxators called after the LP)
3978 */
3980
3981 /* solve external relaxations with negative priority */
3982 if( solverelax && !(*cutoff) )
3983 {
3984 SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, FALSE, cutoff,
3987
3988 /* check, if the path was cutoff */
3989 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3990
3991 /* apply found cuts */
3992 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
3993 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
3995
3996 /* update lower bound with the pseudo objective value, and cut off node by bounding */
3997 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
3998 cliquetable, cutoff) );
3999 }
4000 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4001
4002 return SCIP_OKAY;
4003}
4004
4005/** check if a restart can be performed */
4006#ifndef NDEBUG
4007static
4009 SCIP_SET* set, /**< global SCIP settings */
4010 SCIP_STAT* stat /**< dynamic problem statistics */
4011 )
4012{
4013 assert(set != NULL);
4014 assert(stat != NULL);
4015
4016 return (set->nactivepricers == 0 && !set->reopt_enable
4017 && (set->presol_maxrestarts == -1 || stat->nruns <= set->presol_maxrestarts)
4018 && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts));
4019}
4020#else
4021#define restartAllowed(set,stat) ((set)->nactivepricers == 0 && !set->reopt_enable && ((set)->presol_maxrestarts == -1 || (stat)->nruns <= (set)->presol_maxrestarts) \
4022 && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts))
4023#endif
4024
4025/** solves the focus node */
4026static
4028 BMS_BLKMEM* blkmem, /**< block memory buffers */
4029 SCIP_SET* set, /**< global SCIP settings */
4030 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4031 SCIP_STAT* stat, /**< dynamic problem statistics */
4032 SCIP_MEM* mem, /**< block memory pools */
4033 SCIP_PROB* origprob, /**< original problem */
4034 SCIP_PROB* transprob, /**< transformed problem after presolve */
4035 SCIP_PRIMAL* primal, /**< primal data */
4036 SCIP_TREE* tree, /**< branch and bound tree */
4037 SCIP_REOPT* reopt, /**< reoptimization data structure */
4038 SCIP_LP* lp, /**< LP data */
4039 SCIP_RELAXATION* relaxation, /**< global relaxation data */
4040 SCIP_PRICESTORE* pricestore, /**< pricing storage */
4041 SCIP_SEPASTORE* sepastore, /**< separation storage */
4042 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4043 SCIP_CUTPOOL* cutpool, /**< global cut pool */
4044 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
4045 SCIP_CONFLICT* conflict, /**< conflict analysis data */
4046 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4047 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4048 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4049 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4050 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
4051 SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
4052 SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
4053 SCIP_Bool* infeasible, /**< pointer to store whether the focus node's solution is infeasible */
4054 SCIP_Bool* restart, /**< should solving process be started again with presolving? */
4055 SCIP_Bool* afternodeheur, /**< pointer to store whether AFTERNODE heuristics were already called */
4056 SCIP_Bool* stopped /**< pointer to store whether solving was interrupted */
4057 )
4058{
4059 SCIP_NODE* focusnode;
4060 SCIP_Longint lastdomchgcount;
4061 SCIP_Longint afterlpproplps;
4062 SCIP_Real restartfac;
4063 SCIP_Longint lastlpcount;
4065 int actdepth;
4066 int nlperrors;
4067 int nloops;
4068 SCIP_Bool foundsol;
4069 SCIP_Bool focusnodehaslp;
4070 SCIP_Bool lpsolved;
4071 SCIP_Bool initiallpsolved;
4072 SCIP_Bool fullseparation;
4073 SCIP_Bool solverelaxagain;
4074 SCIP_Bool solvelpagain;
4075 SCIP_Bool propagateagain;
4076 SCIP_Bool fullpropagation;
4077 SCIP_Bool branched;
4078 SCIP_Bool forcedlpsolve;
4079 SCIP_Bool wasforcedlpsolve;
4080 SCIP_Bool pricingaborted;
4081
4082 assert(set != NULL);
4083 assert(stat != NULL);
4084 assert(origprob != NULL);
4085 assert(transprob != NULL);
4086 assert(tree != NULL);
4087 assert(primal != NULL);
4088 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4089 assert(SCIPconflictGetNConflicts(conflict) == 0);
4090 assert(cutoff != NULL);
4091 assert(postpone != NULL);
4092 assert(unbounded != NULL);
4093 assert(infeasible != NULL);
4094 assert(restart != NULL);
4096
4097 *cutoff = FALSE;
4098 *postpone = FALSE;
4099 *unbounded = FALSE;
4100 *infeasible = FALSE;
4101 *restart = FALSE;
4103 *stopped = FALSE;
4105
4106 focusnode = SCIPtreeGetFocusNode(tree);
4107 assert(focusnode != NULL);
4109 actdepth = SCIPnodeGetDepth(focusnode);
4110
4111 /* invalidate relaxation solution */
4113
4114 /* clear the storage of external branching candidates */
4116
4117 SCIPsetDebugMsg(set, "Processing node %" SCIP_LONGINT_FORMAT " in depth %d, %d siblings\n",
4118 stat->nnodes, actdepth, tree->nsiblings);
4119 SCIPsetDebugMsg(set, "current pseudosolution: obj=%g\n", SCIPlpGetPseudoObjval(lp, set, transprob));
4120 /*debug(SCIPprobPrintPseudoSol(transprob, set));*/
4121
4122 /* check, if we want to solve the LP at the selected node:
4123 * - solve the LP, if the lp solve depth and frequency demand solving
4124 * - solve the root LP, if the LP solve frequency is set to 0
4125 * - solve the root LP, if there are continuous variables present
4126 * - don't solve the node if its cut off by the pseudo objective value anyway
4127 */
4128 focusnodehaslp = (set->lp_solvedepth == -1 || actdepth <= set->lp_solvedepth);
4129 focusnodehaslp = focusnodehaslp && (set->lp_solvefreq >= 1 && actdepth % set->lp_solvefreq == 0);
4130 focusnodehaslp = focusnodehaslp || (actdepth == 0 && set->lp_solvefreq == 0);
4131 focusnodehaslp = focusnodehaslp && SCIPsetIsLT(set, SCIPlpGetPseudoObjval(lp, set, transprob), primal->cutoffbound);
4132 focusnodehaslp = set->reopt_enable ? focusnodehaslp && SCIPreoptGetSolveLP(reopt, set, focusnode) : focusnodehaslp;
4133 SCIPtreeSetFocusNodeLP(tree, focusnodehaslp);
4134
4135 /* external node solving loop:
4136 * - propagate domains
4137 * - solve SCIP_LP
4138 * - enforce constraints
4139 * if a constraint handler adds constraints to enforce its own constraints, both, propagation and LP solving
4140 * is applied again (if applicable on current node); however, if the new constraints don't have the enforce flag set,
4141 * it is possible, that the current infeasible solution is not cut off; in this case, we have to declare the solution
4142 * infeasible and perform a branching
4143 */
4145 lastlpcount = stat->lpcount;
4149 nlperrors = 0;
4150 stat->npricerounds = 0;
4151 stat->nseparounds = 0;
4157 nloops = 0;
4158
4159 while( !(*cutoff) && !(*postpone) && (solverelaxagain || solvelpagain || propagateagain) && nlperrors < MAXNLPERRORS && !(*restart) )
4160 {
4161 SCIP_Bool lperror;
4162 SCIP_Bool solverelax;
4163 SCIP_Bool solvelp;
4164 SCIP_Bool propagate;
4165 SCIP_Bool forcedenforcement;
4166 SCIP_Bool relaxcalled;
4167
4168 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4169
4170 *unbounded = FALSE;
4171 *infeasible = FALSE;
4172 foundsol = FALSE;
4173
4174 nloops++;
4175 lperror = FALSE;
4176 lpsolved = FALSE;
4179 afterlpproplps = -1L;
4180
4182 || (afterlpproplps < stat->nnodelps && lpsolved) || relaxcalled) )
4183 {
4190
4191 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4192 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
4193 conflict, cliquetable, cutoff) );
4194
4195 /* propagate domains before lp solving and solve relaxation and lp */
4196 SCIPsetDebugMsg(set, " -> node solving loop: call propagators that are applicable before%s LP is solved\n",
4197 lpsolved ? " and after" : "");
4198 SCIP_CALL( propAndSolve(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp,
4199 relaxation, pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter,
4200 eventqueue, cliquetable, focusnode, actdepth, propagate, solvelp, solverelax, forcedlpsolve, initiallpsolved,
4204
4205 /* time or solution limit was hit and we already created a dummy child node to terminate fast */
4206 if( *stopped )
4207 {
4208 /* reset LP feastol to normal value, in case someone tightened it during node solving */
4210 return SCIP_OKAY;
4211 }
4212 }
4214
4215 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4217
4218 /* call primal heuristics that should be applied after the LP relaxation of the node was solved;
4219 * if this is the first loop of the root node, call also AFTERNODE heuristics already here, since they might help
4220 * to improve the primal bound, thereby producing additional reduced cost strengthenings and strong branching
4221 * bound fixings which also might lead to a restart
4222 */
4223 if( !(*postpone) && (!(*cutoff) || SCIPtreeGetNNodes(tree) > 0) )
4224 {
4225 if( actdepth == 0 && !(*afternodeheur) )
4226 {
4227 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL,
4229 *afternodeheur = TRUE; /* the AFTERNODE heuristics should not be called again after the node */
4230 }
4231 else if( lpsolved || SCIPrelaxationIsSolValid(relaxation) )
4232 {
4233 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_AFTERLPLOOP,
4234 *cutoff, &foundsol, unbounded) );
4235 }
4237
4238 /* heuristics might have found a solution or set the cutoff bound such that the current node is cut off */
4239 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4240 }
4241
4242 /* check if heuristics leave us with an invalid LP */
4243 if( lp->resolvelperror )
4244 {
4245 if( forcedlpsolve )
4246 {
4247 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4248 stat->nnodes, stat->nlps);
4249 return SCIP_LPERROR;
4250 }
4252 lp->resolvelperror = FALSE;
4253 nlperrors++;
4254 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4255 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4256 stat->nnodes, stat->nlps, nlperrors);
4257 }
4258
4260 {
4262
4263 /* if we just ran into the time limit this is not really a numerical trouble;
4264 * however, if this is not the case, we print messages about numerical troubles in the current LP
4265 */
4266 if( !SCIPsolveIsStopped(set, stat, FALSE) )
4267 {
4268 if( forcedlpsolve )
4269 {
4270 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4271 stat->nnodes, stat->nlps);
4272 return SCIP_LPERROR;
4273 }
4274 nlperrors++;
4275 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4276 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4277 stat->nnodes, stat->nlps, nlperrors);
4278 }
4279 }
4280
4281 /* if an improved solution was found, propagate and solve the relaxations again */
4282 if( foundsol && !(*cutoff) )
4283 {
4287 markRelaxsUnsolved(set, relaxation);
4288 }
4289
4290 /* check for immediate restart */
4291 *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart
4292 || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars)
4293 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4294
4295 /* enforce constraints */
4296 branched = FALSE;
4297 if( !(*postpone) && !(*restart) && !(*cutoff) && !solverelaxagain && !solvelpagain && !propagateagain )
4298 {
4299 /* if the solution changed since the last enforcement, we have to completely reenforce it; otherwise, we
4300 * only have to enforce the additional constraints added in the last enforcement, but keep the infeasible
4301 * flag TRUE in order to not declare the infeasible solution feasible due to disregarding the already
4302 * enforced constraints
4303 */
4304 if( lastdomchgcount != stat->domchgcount || lastlpcount != stat->lpcount )
4305 {
4307 lastlpcount = stat->lpcount;
4308 *infeasible = FALSE;
4309 }
4310
4311 /* call constraint enforcement */
4312 SCIP_CALL( enforceConstraints(blkmem, set, messagehdlr, stat, transprob, primal, tree, lp, relaxation, sepastore,
4313 branchcand, &branched, cutoff, infeasible, &propagateagain, &solvelpagain, &solverelaxagain,
4315 assert(branched == (tree->nchildren > 0));
4316 assert(!branched || (!(*cutoff) && *infeasible && !propagateagain && !solvelpagain));
4317 assert(!(*cutoff) || (!branched && *infeasible && !propagateagain && !solvelpagain));
4318 assert(*infeasible || (!branched && !(*cutoff) && !propagateagain && !solvelpagain));
4319 assert(!propagateagain || (!branched && !(*cutoff) && *infeasible));
4320 assert(!solvelpagain || (!branched && !(*cutoff) && *infeasible));
4321
4323
4324 /* apply found cuts */
4325 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4326 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain,
4328
4329 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4330 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4331
4332 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4334 }
4335 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4336
4337 /* The enforcement detected no infeasibility, so, no branching was performed,
4338 * but the pricing was aborted and the current feasible solution does not have to be the
4339 * best solution in the current subtree --> we have to do a pseudo branching,
4340 * so we set infeasible TRUE and add the current solution to the solution pool
4341 */
4342 if( pricingaborted && !(*infeasible) && !(*cutoff) && !(*postpone) && !(*restart) )
4343 {
4344 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
4345 SCIP_SOL* sol;
4346 SCIP_Bool stored;
4347
4348 /* in case the relaxation was enforced add this solution, otherwise decide between LP and pseudosol */
4350 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4351 {
4352 SCIP_SOL* relaxsol;
4353
4354 SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4355
4356 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4357 eventqueue, eventfilter, relaxsol, FALSE, FALSE, TRUE, TRUE, TRUE,
4358 &stored) );
4359
4360 SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
4361
4362 if( stored )
4363 {
4364 stat->nrelaxsolsfound++;
4365
4366 if( primal->nbestsolsfound != oldnbestsolsfound )
4367 {
4368 stat->nrelaxbestsolsfound++;
4370 }
4371 }
4372 }
4373 else
4374 {
4375 SCIP_CALL( SCIPsolCreateCurrentSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4376 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4377 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
4378
4379 if( stored )
4380 {
4381 stat->nlpsolsfound++;
4382
4383 if( primal->nbestsolsfound != oldnbestsolsfound )
4384 {
4385 stat->nlpbestsolsfound++;
4387 }
4388 }
4389 }
4390
4391 *infeasible = TRUE;
4392 }
4393
4394 /* if the node is infeasible, but no constraint handler could resolve the infeasibility
4395 * -> branch on LP, external candidates, or the pseudo solution
4396 * -> e.g. select non-fixed binary or integer variable x with value x', create three
4397 * sons: x <= x'-1, x = x', and x >= x'+1.
4398 * In the left and right branch, the current solution is cut off. In the middle
4399 * branch, the constraints can hopefully reduce domains of other variables to cut
4400 * off the current solution.
4401 * In LP branching, we cannot allow adding constraints, because this does not necessary change the LP and can
4402 * therefore lead to an infinite loop.
4403 */
4406 if( (*infeasible) && !(*cutoff) && !(*postpone) && !(*restart)
4407 && (!(*unbounded) || SCIPbranchcandGetNExternCands(branchcand) > 0 || SCIPbranchcandGetNPseudoCands(branchcand) > 0)
4409 {
4411 int nlpcands = 0;
4412
4413 if( SCIPtreeHasFocusNodeLP(tree) )
4414 {
4415 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpcands, NULL, NULL) );
4416 }
4417
4418 if ( nlpcands > 0 || SCIPbranchcandGetNExternCands(branchcand) > 0 )
4419 {
4420 /* If there are LP candidates and their maximal priority is at least the maximal priority of the external
4421 * candidates, then branch on the LP candidates. Note that due to implicit integer variables,
4422 * SCIPbranchcandGetLPMaxPrio(branchcand) might be finite and SCIPbranchcandGetNPrioLPCands(branchcand) > 0,
4423 * but nlpcands == 0. */
4424 if ( SCIPbranchcandGetLPMaxPrio(branchcand) >= SCIPbranchcandGetExternMaxPrio(branchcand) && nlpcands > 0 )
4425 {
4426 assert( SCIPbranchcandGetNPrioLPCands(branchcand) > 0 );
4427 assert( nlpcands > 0 );
4428
4429 /* branch on LP solution */
4430 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on LP solution with %d fractionals\n",
4431 SCIPnodeGetDepth(focusnode), nlpcands);
4432 SCIP_CALL( SCIPbranchExecLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4433 eventqueue, primal->cutoffbound, FALSE, &result) );
4436 }
4437 else
4438 {
4439 assert( SCIPbranchcandGetNPrioExternCands(branchcand) > 0 );
4440 assert( SCIPbranchcandGetNExternCands(branchcand) > 0 );
4441
4442 /* branch on external candidates */
4443 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on %d external branching candidates.\n",
4444 SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNExternCands(branchcand));
4445 SCIP_CALL( SCIPbranchExecExtern(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4446 eventqueue, primal->cutoffbound, TRUE, &result) );
4448 }
4449 }
4450
4452 {
4453 /* branch on pseudo solution */
4454 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on pseudo solution with %d unfixed integers\n",
4455 SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNPseudoCands(branchcand));
4456 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
4457 primal->cutoffbound, TRUE, &result) );
4459 }
4460
4461 /* SCIP cannot guarantee convergence if it is necessary to branch on unbounded variables */
4462 if( result == SCIP_BRANCHED )
4463 {
4464 SCIP_VAR* var = stat->lastbranchvar;
4465
4468 {
4469 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
4470 "Starting spatial branch-and-bound on unbounded variable <%s> ([%g,%g]) - cannot guarantee finite termination.\n",
4472 stat->branchedunbdvar = TRUE;
4473 }
4474 }
4475
4476 switch( result )
4477 {
4478 case SCIP_CUTOFF:
4479 assert(tree->nchildren == 0);
4480 *cutoff = TRUE;
4481 SCIPsetDebugMsg(set, " -> branching rule detected cutoff\n");
4482 break;
4483 case SCIP_CONSADDED:
4484 assert(tree->nchildren == 0);
4485 if( nlpcands > 0 )
4486 {
4487 SCIPerrorMessage("LP branching rule added constraint, which was not allowed this time\n");
4488 return SCIP_INVALIDRESULT;
4489 }
4493 markRelaxsUnsolved(set, relaxation);
4494 break;
4495 case SCIP_REDUCEDDOM:
4496 assert(tree->nchildren == 0);
4500 markRelaxsUnsolved(set, relaxation);
4501 break;
4502 case SCIP_SEPARATED:
4503 assert(tree->nchildren == 0);
4504 assert(SCIPsepastoreGetNCuts(sepastore) > 0);
4507 markRelaxsUnsolved(set, relaxation);
4508 break;
4509 case SCIP_BRANCHED:
4510 assert(tree->nchildren >= 1);
4511 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4512 branched = TRUE;
4513
4514 /* increase the number of internal nodes */
4515 stat->ninternalnodes++;
4516 stat->ntotalinternalnodes++;
4517 break;
4518 case SCIP_DIDNOTFIND: /*lint -fallthrough*/
4519 case SCIP_DIDNOTRUN:
4520 /* all integer variables in the infeasible solution are fixed,
4521 * - if no continuous variables exist and all variables are known, the infeasible pseudo solution is completely
4522 * fixed, and the node can be cut off
4523 * - if at least one continuous variable exists or we do not know all variables due to external pricers, we
4524 * cannot resolve the infeasibility by branching -> solve LP (and maybe price in additional variables)
4525 */
4526 assert(tree->nchildren == 0);
4527 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4528 assert(SCIPbranchcandGetNPseudoCands(branchcand) == 0);
4529
4530 if( transprob->ncontvars == 0 && set->nactivepricers == 0 )
4531 {
4532 *cutoff = TRUE;
4533 SCIPsetDebugMsg(set, " -> cutoff because all variables are fixed in current node\n");
4534 }
4535 else
4536 {
4537 /* feasible LP solutions with all integers fixed must be feasible
4538 * if also no external branching candidates were available
4539 */
4541
4543 {
4544 SCIP_NODE* node;
4545
4546 /* as we hit the time or iteration limit or another interrupt (e.g., gap limit), we do not want to solve the LP again.
4547 * in order to terminate correctly, we create a "branching" with only one child node
4548 * that is a copy of the focusnode
4549 */
4550 SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) );
4551 assert(tree->nchildren >= 1);
4552 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4553 branched = TRUE;
4554 }
4555 else
4556 {
4557 SCIP_VERBLEVEL verblevel;
4558
4559 if( pricingaborted )
4560 {
4561 SCIPerrorMessage("pricing was aborted, but no branching could be created!\n");
4562 return SCIP_INVALIDRESULT;
4563 }
4564
4565 if( wasforcedlpsolve )
4566 {
4568 SCIPerrorMessage("LP was solved, all integers fixed, some constraint still infeasible, but no branching could be created!\n");
4569 return SCIP_INVALIDRESULT;
4570 }
4571
4572 verblevel = SCIP_VERBLEVEL_FULL;
4573
4574 if( !tree->forcinglpmessage && set->disp_verblevel == SCIP_VERBLEVEL_HIGH )
4575 {
4576 verblevel = SCIP_VERBLEVEL_HIGH;
4577
4578 /* remember that the forcing LP solving message was posted and do only post it again if the
4579 * verblevel is SCIP_VERBLEVEL_FULL
4580 */
4581 tree->forcinglpmessage = TRUE;
4582 }
4583
4584 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel,
4585 "(node %" SCIP_LONGINT_FORMAT ") forcing the solution of an LP (last LP %" SCIP_LONGINT_FORMAT ")...\n", stat->nnodes, stat->nlps);
4586
4587 /* solve the LP in the next loop */
4590 forcedlpsolve = TRUE; /* this LP must be solved without error - otherwise we have to abort */
4591 }
4592 }
4593 break;
4594 default:
4595 SCIPerrorMessage("invalid result code <%d> from SCIPbranchLP(), SCIPbranchExt() or SCIPbranchPseudo()\n", result);
4596 return SCIP_INVALIDRESULT;
4597 } /*lint !e788*/
4598 assert(*cutoff || solvelpagain || propagateagain || branched); /* something must have been done */
4600 assert(!solvelpagain || (!(*cutoff) && !branched));
4601 assert(!propagateagain || (!(*cutoff) && !branched));
4603 assert(branched == (tree->nchildren > 0));
4604
4605 /* apply found cuts */
4606 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4607 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain,
4609
4610 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4611 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4612
4613 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4615 }
4616
4617 /* check for immediate restart */
4618 *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart
4619 || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars)
4620 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4621
4622 SCIPsetDebugMsg(set, "node solving iteration %d finished: cutoff=%u, postpone=%u, propagateagain=%u, solverelaxagain=%u, solvelpagain=%u, nlperrors=%d, restart=%u\n",
4624 }
4625 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4626 assert(*cutoff || SCIPconflictGetNConflicts(conflict) == 0);
4627
4628 /* flush the conflict set storage */
4629 SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable) );
4630
4631 /* check for too many LP errors */
4632 if( nlperrors >= MAXNLPERRORS )
4633 {
4634 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- aborting\n", stat->nnodes, stat->nlps);
4635 return SCIP_LPERROR;
4636 }
4637
4638 /* check for final restart */
4639 restartfac = set->presol_subrestartfac;
4640 if( actdepth == 0 )
4641 restartfac = MIN(restartfac, set->presol_restartfac);
4642 *restart = *restart || (restartAllowed(set, stat) && (stat->userrestart
4643 || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars)
4644 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4645
4646 /* remember the last root LP solution */
4647 if( actdepth == 0 && !(*cutoff) && !(*unbounded) && !(*postpone) )
4648 {
4649 /* the root pseudo objective value and pseudo objective value should be equal in the root node */
4651
4652 SCIPprobStoreRootSol(transprob, set, stat, lp, SCIPtreeHasFocusNodeLP(tree));
4653 }
4654
4655 /* check for cutoff */
4656 if( *cutoff )
4657 {
4658 SCIPsetDebugMsg(set, "node is cut off\n");
4659
4660 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
4661 *infeasible = TRUE;
4662 SCIP_CALL( SCIPdebugRemoveNode(blkmem, set, focusnode) ); /*lint !e506 !e774*/
4663
4664 /* the LP might have been unbounded but not enforced, because the node is cut off anyway */
4665 *unbounded = FALSE;
4666 }
4667 else if( !(*unbounded) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && lp->looseobjvalinf == 0 )
4668 {
4669 /* update the regression statistic nlpbranchcands and LP objective value */
4670 int nlpbranchcands;
4671 SCIP_Real lpobjval;
4672
4673 /* get number of LP candidate variables */
4674 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpbranchcands, NULL, NULL) );
4675
4676 /* get LP objective value */
4677 lpobjval = SCIPlpGetObjval(lp, set, transprob);
4678 assert(lpobjval != SCIP_INVALID); /*lint !e777*/
4679
4680 /* add the observation to the regression */
4682 }
4683
4684 /* reset LP feastol to normal value, in case someone tightened it during node solving */
4686
4687 return SCIP_OKAY;
4688}
4689
4690/** if feasible, adds current solution to the solution storage */
4691static
4693 BMS_BLKMEM* blkmem, /**< block memory buffers */
4694 SCIP_SET* set, /**< global SCIP settings */
4695 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4696 SCIP_STAT* stat, /**< dynamic problem statistics */
4697 SCIP_PROB* origprob, /**< original problem */
4698 SCIP_PROB* transprob, /**< transformed problem after presolve */
4699 SCIP_PRIMAL* primal, /**< primal data */
4700 SCIP_RELAXATION* relaxation, /**< global relaxation data */
4701 SCIP_TREE* tree, /**< branch and bound tree */
4702 SCIP_REOPT* reopt, /**< reoptimization data structure */
4703 SCIP_LP* lp, /**< LP data */
4704 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4705 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4706 SCIP_Bool checksol /**< should the solution be checked? */
4707 )
4708{
4709 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
4710 SCIP_SOL* sol;
4711 SCIP_Bool foundsol;
4712
4713 /* found a feasible solution */
4715 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4716 {
4717 /* start clock for relaxation solutions */
4719
4720 SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4721
4722 SCIPsetDebugMsg(set, "found relaxation solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4723
4724 if( checksol || set->misc_exactsolve )
4725 {
4726 /* if we want to solve exactly, we have to check the solution exactly again */
4727 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4728 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4729 }
4730 else
4731 {
4732 SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4733 eventqueue, eventfilter, &sol, &foundsol) );
4734 }
4735
4736 if( foundsol )
4737 {
4738 stat->nrelaxsolsfound++;
4739
4740 if( primal->nbestsolsfound != oldnbestsolsfound )
4741 {
4742 stat->nrelaxbestsolsfound++;
4744 }
4745 }
4746
4747 /* stop clock for relaxation solutions */
4749 }
4750 else if( SCIPtreeHasFocusNodeLP(tree) )
4751 {
4753
4754 /* start clock for LP solutions */
4756
4757 /* add solution to storage */
4758 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4759
4760 SCIPsetDebugMsg(set, "found lp solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4761
4762 if( checksol || set->misc_exactsolve )
4763 {
4764 /* if we want to solve exactly, we have to check the solution exactly again */
4765 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4766 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4767 }
4768 else
4769 {
4770 SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4771 eventqueue, eventfilter, &sol, &foundsol) );
4772 }
4773
4774 if( foundsol )
4775 {
4776 stat->nlpsolsfound++;
4777
4778 if( primal->nbestsolsfound != oldnbestsolsfound )
4779 {
4780 stat->nlpbestsolsfound++;
4782 }
4783 }
4784
4785 /* stop clock for LP solutions */
4786 SCIPclockStop(stat->lpsoltime, set);
4787 }
4788 else
4789 {
4790 /* start clock for pseudo solutions */
4792
4793 /* add solution to storage */
4794 SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4795
4796 SCIPsetDebugMsg(set, "found pseudo solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4797
4798 if( checksol || set->misc_exactsolve )
4799 {
4800 /* if we want to solve exactly, we have to check the solution exactly again */
4801 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4802 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4803 }
4804 else
4805 {
4806 SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4807 eventqueue, eventfilter, &sol, &foundsol) );
4808 }
4809
4810 /* stop clock for pseudo solutions */
4812
4813 if( foundsol )
4814 {
4815 stat->npssolsfound++;
4816
4817 if( primal->nbestsolsfound != oldnbestsolsfound )
4818 {
4819 stat->npsbestsolsfound++;
4821 }
4822 }
4823 }
4824
4825 return SCIP_OKAY;
4826}
4827
4828/** main solving loop */
4830 BMS_BLKMEM* blkmem, /**< block memory buffers */
4831 SCIP_SET* set, /**< global SCIP settings */
4832 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4833 SCIP_STAT* stat, /**< dynamic problem statistics */
4834 SCIP_MEM* mem, /**< block memory pools */
4835 SCIP_PROB* origprob, /**< original problem */
4836 SCIP_PROB* transprob, /**< transformed problem after presolve */
4837 SCIP_PRIMAL* primal, /**< primal data */
4838 SCIP_TREE* tree, /**< branch and bound tree */
4839 SCIP_REOPT* reopt, /**< reoptimization data structure */
4840 SCIP_LP* lp, /**< LP data */
4841 SCIP_RELAXATION* relaxation, /**< global relaxation data */
4842 SCIP_PRICESTORE* pricestore, /**< pricing storage */
4843 SCIP_SEPASTORE* sepastore, /**< separation storage */
4844 SCIP_CUTPOOL* cutpool, /**< global cut pool */
4845 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
4846 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4847 SCIP_CONFLICT* conflict, /**< conflict analysis data */
4848 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4849 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4850 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4851 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4852 SCIP_Bool* restart /**< should solving process be started again with presolving? */
4853 )
4854{
4855 SCIP_NODESEL* nodesel;
4856 SCIP_NODE* focusnode;
4859 SCIP_Real restartfac;
4860 SCIP_Real restartconfnum;
4861 int nnodes;
4862 int depth;
4863 SCIP_Bool cutoff;
4864 SCIP_Bool postpone;
4865 SCIP_Bool unbounded;
4866 SCIP_Bool infeasible;
4867 SCIP_Bool foundsol;
4868
4869 assert(set != NULL);
4870 assert(blkmem != NULL);
4871 assert(stat != NULL);
4872 assert(transprob != NULL);
4873 assert(tree != NULL);
4874 assert(lp != NULL);
4875 assert(pricestore != NULL);
4876 assert(sepastore != NULL);
4877 assert(branchcand != NULL);
4878 assert(cutpool != NULL);
4879 assert(delayedcutpool != NULL);
4880 assert(primal != NULL);
4881 assert(eventfilter != NULL);
4882 assert(eventqueue != NULL);
4883 assert(restart != NULL);
4884
4885 /* check for immediate restart (if problem solving marked to be restarted was aborted) */
4886 restartfac = set->presol_subrestartfac;
4887 if( SCIPtreeGetCurrentDepth(tree) == 0 )
4888 restartfac = MIN(restartfac, set->presol_restartfac);
4889 *restart = restartAllowed(set, stat) && (stat->userrestart
4890 || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars)
4891 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars)) );
4892
4893 /* calculate the number of successful conflict analysis calls that should trigger a restart */
4894 if( set->conf_restartnum > 0 )
4895 {
4896 int i;
4897
4898 restartconfnum = (SCIP_Real)set->conf_restartnum;
4899 for( i = 0; i < stat->nconfrestarts; ++i )
4900 restartconfnum *= set->conf_restartfac;
4901 }
4902 else
4904 assert(restartconfnum >= 0.0);
4905
4906 /* switch status to UNKNOWN */
4908
4909 focusnode = NULL;
4910 nextnode = NULL;
4911 unbounded = FALSE;
4912 postpone = FALSE;
4913
4914 while( !SCIPsolveIsStopped(set, stat, TRUE) && !(*restart) )
4915 {
4916 SCIP_Longint nsuccessconflicts;
4917 SCIP_Bool afternodeheur;
4918 SCIP_Bool stopped;
4919 SCIP_Bool branched;
4920
4922
4923 foundsol = FALSE;
4924 infeasible = FALSE;
4925
4926 do
4927 {
4928 /* update the memory saving flag, switch algorithms respectively */
4929 SCIPstatUpdateMemsaveMode(stat, set, messagehdlr, mem);
4930
4931 /* get the current node selector */
4932 nodesel = SCIPsetGetNodesel(set, stat);
4933
4934 /* inform tree about the current node selector */
4935 SCIP_CALL( SCIPtreeSetNodesel(tree, set, messagehdlr, stat, nodesel) );
4936
4937 /* the next node was usually already selected in the previous solving loop before the primal heuristics were
4938 * called, because they need to know, if the next node will be a child/sibling (plunging) or not;
4939 * if the heuristics found a new best solution that cut off some of the nodes, the node selector must be called
4940 * again, because the selected next node may be invalid due to cut off
4941 */
4942 if( nextnode == NULL )
4943 {
4944 /* select next node to process */
4945 SCIP_CALL( SCIPnodeselSelect(nodesel, set, &nextnode) );
4946 }
4947 focusnode = nextnode;
4948 nextnode = NULL;
4950
4951 /* start node activation timer */
4953
4954 /* focus selected node */
4955 SCIP_CALL( SCIPnodeFocus(&focusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt,
4956 lp, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, FALSE, FALSE) );
4957 if( cutoff )
4958 stat->ndelayedcutoffs++;
4959
4960 /* stop node activation timer */
4962
4964 }
4965 while( cutoff ); /* select new node, if the current one was located in a cut off subtree */
4966
4967 assert(SCIPtreeGetCurrentNode(tree) == focusnode);
4968 assert(SCIPtreeGetFocusNode(tree) == focusnode);
4969
4970 /* if no more node was selected, we finished optimization */
4971 if( focusnode == NULL )
4972 {
4973 assert(SCIPtreeGetNNodes(tree) == 0);
4974 break;
4975 }
4976
4977 /* update maxdepth and node count statistics */
4978 depth = SCIPnodeGetDepth(focusnode);
4979 stat->maxdepth = MAX(stat->maxdepth, depth);
4980 stat->maxtotaldepth = MAX(stat->maxtotaldepth, depth);
4981 stat->nnodes++;
4982 stat->ntotalnodes++;
4983
4984 /* update reference bound statistic, if available */
4985 if( SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), stat->referencebound) )
4986 stat->nnodesaboverefbound++;
4987
4988 /* issue NODEFOCUSED event */
4990 SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
4991 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
4992
4993 /* solve focus node */
4994 SCIP_CALL( solveNode(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation,
4995 pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter, eventqueue,
4996 cliquetable, &cutoff, &postpone, &unbounded, &infeasible, restart, &afternodeheur, &stopped) );
4997 assert(!cutoff || infeasible);
4999 assert(SCIPtreeGetCurrentNode(tree) == focusnode);
5000 assert(SCIPtreeGetFocusNode(tree) == focusnode);
5001
5002 branched = (tree->nchildren > 0);
5003
5004 if( stopped )
5005 break;
5006
5007 /* check for restart */
5008 if( !(*restart) && !postpone )
5009 {
5010 /* change color of node in visualization */
5011 SCIPvisualSolvedNode(stat->visual, set, stat, focusnode);
5012
5013 /* check, if the current solution is feasible */
5014 if( !infeasible )
5015 {
5016 SCIP_Bool feasible;
5017
5018 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
5019 assert(!cutoff);
5020
5021 /* in the unbounded case, we check the solution w.r.t. the original problem, because we do not want to rely
5022 * on the LP feasibility and integrality is not checked for unbounded solutions, anyway
5023 */
5024 if( unbounded )
5025 {
5026 SCIP_SOL* sol;
5027
5029 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
5030 {
5031 SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) );
5032 }
5033 else if( SCIPtreeHasFocusNodeLP(tree) )
5034 {
5035 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
5036 }
5037 else
5038 {
5039 SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
5040 }
5042
5043 SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) );
5044 }
5045 else
5046 feasible = TRUE;
5047
5048 /* node solution is feasible: add it to the solution store */
5049 if( feasible )
5050 {
5051 SCIP_CALL( addCurrentSolution(blkmem, set, messagehdlr, stat, origprob, transprob, primal, relaxation, tree, reopt,
5052 lp, eventqueue, eventfilter, FALSE) );
5053
5054 /* update the cutoff pointer if the new solution made the cutoff bound equal to the lower bound */
5055 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, &cutoff) );
5056
5057 /* increment number of feasible leaf nodes */
5058 stat->nfeasleaves++;
5059
5060 /* issue NODEFEASIBLE event */
5062 SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
5063 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
5064
5065 if( set->reopt_enable )
5066 {
5067 assert(reopt != NULL);
5068 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp,
5069 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5070 focusnode->lowerbound, tree->effectiverootdepth) );
5071 }
5072 }
5073 }
5074 else if( !unbounded || branched )
5075 {
5076 /* node solution is not feasible */
5077 if( !branched )
5078 {
5079 assert(tree->nchildren == 0);
5080
5081 /* change color of node in visualization output */
5082 SCIPvisualCutoffNode(stat->visual, set, stat, focusnode, TRUE);
5083
5084 /* issue NODEINFEASIBLE event */
5086
5087 /* we only increase the number of objective leaf nodes if we hit the LP objective limit; we might have also
5088 * hit the objective limit at a node that is actually infeasible, or a dual reduction led to an infeasibility prior
5089 * to LP solving such that the node will be marked as infeasible */
5091 stat->nobjleaves++;
5092 else
5093 stat->ninfeasleaves++;
5094
5095 if( set->reopt_enable )
5096 {
5097 assert(reopt != NULL);
5098 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEINFEASIBLE, lp,
5099 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5100 focusnode->lowerbound, tree->effectiverootdepth) );
5101 }
5102
5103 /* increase the cutoff counter of the branching variable */
5104 if( stat->lastbranchvar != NULL )
5105 {
5106 SCIP_CALL( SCIPvarIncCutoffSum(stat->lastbranchvar, blkmem, set, stat, stat->lastbranchdir, stat->lastbranchvalue, 1.0) );
5107 }
5108 /**@todo if last branching variable is unknown, retrieve it from the nodes' boundchg arrays */
5109 }
5110 else
5111 {
5112 assert(tree->nchildren > 0);
5113
5114 /* issue NODEBRANCHED event */
5116
5117 if( set->reopt_enable )
5118 {
5119 assert(reopt != NULL);
5120 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEBRANCHED, lp,
5121 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5122 focusnode->lowerbound, tree->effectiverootdepth) );
5123 }
5124 }
5125 SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
5126 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
5127 }
5129
5130 /* if no branching was created, the node was not cut off, but its lower bound is still smaller than
5131 * the cutoff bound, we have to branch on a non-fixed variable;
5132 * this can happen, if we want to solve exactly, the current solution was declared feasible by the
5133 * constraint enforcement, but in exact solution checking it was found out to be infeasible;
5134 * in this case, no branching would have been generated by the enforcement of constraints, but we
5135 * have to further investigate the current sub tree;
5136 * note that we must not check tree->nchildren > 0 here to determine whether we branched, we rather
5137 * check it directly after solveNode() and store the result, because an event handler might impose a
5138 * new cutoff bound (as is the case in ParaSCIP)
5139 */
5140 if( !cutoff && !unbounded && !branched && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound )
5141 {
5143
5144 assert(set->misc_exactsolve);
5145
5146 do
5147 {
5149 if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 )
5150 {
5151 if( transprob->ncontvars > 0 )
5152 {
5153 /**@todo call PerPlex */
5154 SCIPerrorMessage("cannot branch on all-fixed LP -- have to call PerPlex instead\n");
5155 }
5156 }
5157 else
5158 {
5159 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
5160 eventqueue, primal->cutoffbound, FALSE, &result) );
5162 }
5163 }
5164 while( result == SCIP_REDUCEDDOM );
5165 }
5167
5168 /* select node to process in next solving loop; the primal heuristics need to know whether a child/sibling
5169 * (plunging) will be selected as next node or not
5170 */
5171 SCIP_CALL( SCIPnodeselSelect(nodesel, set, &nextnode) );
5173
5174 /* call primal heuristics that should be applied after the node was solved */
5175 nnodes = SCIPtreeGetNNodes(tree);
5176 stopped = SCIPsolveIsStopped(set, stat, FALSE);
5177 if( !afternodeheur && (!cutoff || nnodes > 0) && !stopped )
5178 {
5179 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, nextnode, SCIP_HEURTIMING_AFTERNODE,
5180 cutoff, &foundsol, &unbounded) );
5182
5183 stopped = SCIPsolveIsStopped(set, stat, FALSE);
5184 }
5185
5186 /* if the heuristics found a new best solution that cut off some of the nodes, the node selector must be called
5187 * again, because the selected next node may be invalid due to cut off
5188 */
5189 assert(!tree->cutoffdelayed);
5190
5191 if( nnodes != SCIPtreeGetNNodes(tree) || stopped )
5192 nextnode = NULL;
5193 }
5194 else if( !infeasible && !postpone )
5195 {
5196 /* The current solution was not proven to be infeasible, but due to the restart, this does not mean that it is
5197 * feasible, we might just have skipped the check. Thus, we try to add it to the solution store, but check it
5198 * again.
5199 */
5200 SCIP_CALL( addCurrentSolution(blkmem, set, messagehdlr, stat, origprob, transprob, primal, relaxation, tree, reopt, lp,
5201 eventqueue, eventfilter, TRUE) );
5202
5203 if( set->reopt_enable )
5204 {
5205 assert(reopt != NULL);
5206 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp,
5207 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode, focusnode->lowerbound,
5208 tree->effectiverootdepth) );
5209 }
5210 }
5211 /* we want to put the focusnode back into the leaf queue if it was postponed */
5212 else if( postpone )
5213 {
5215
5216 /* @todo should we re-install the old focus node in order to somehow set the forks more clever? */
5217 SCIP_CALL( SCIPnodeFocus(&newfocusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
5218 branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, TRUE, FALSE) );
5219 }
5220 /* compute number of successfully applied conflicts */
5224
5225 /* trigger restart due to conflicts and the restart parameters allow another restart */
5227 {
5228 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
5229 "(run %d, node %" SCIP_LONGINT_FORMAT ") restarting after %" SCIP_LONGINT_FORMAT " successful conflict analysis calls\n",
5230 stat->nruns, stat->nnodes, nsuccessconflicts);
5231 *restart = TRUE;
5232
5233 stat->nconfrestarts++;
5234 }
5235
5236 /* restart if the userrestart was set to true, we have still some nodes left and the restart parameters allow
5237 * another restart
5238 */
5239 *restart = *restart || (stat->userrestart && SCIPtreeGetNNodes(tree) > 0 && restartAllowed(set, stat));
5240 if( restartAllowed(set, stat) && set->limit_autorestartnodes == stat->nnodes && stat->ntotalnodes - stat->nruns + 1 == set->limit_autorestartnodes )
5241 {
5242 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
5243 "(run %d, node %" SCIP_LONGINT_FORMAT ") restarting: triggering parameter controlled restart)\n",
5244 stat->nruns, stat->nnodes);
5245 *restart = TRUE;
5246 }
5247 /* if restart limit was exceeded, change the status; if status is different from unknown, ie some other limit was
5248 * hit, leave it unchanged
5249 */
5250 if( *restart && stat->status == SCIP_STATUS_UNKNOWN && set->limit_restarts >= 0 && stat->nruns > set->limit_restarts )
5251 {
5252 *restart = FALSE;
5254 }
5255
5256 /* display node information line */
5257 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, (SCIPnodeGetDepth(focusnode) == 0) && infeasible && !foundsol, TRUE) );
5258
5259 SCIPsetDebugMsg(set, "Processing of node %" SCIP_LONGINT_FORMAT " in depth %d finished. %d siblings, %d children, %d leaves left\n",
5260 stat->nnodes, SCIPnodeGetDepth(focusnode), tree->nsiblings, tree->nchildren, SCIPtreeGetNLeaves(tree));
5261 SCIPsetDebugMsg(set, "**********************************************************************\n");
5262 }
5263
5264 /* update the primal-dual integral if node or time limits were hit or an interruption signal was called */
5265 if( SCIPsolveIsStopped(set, stat, TRUE) )
5266 {
5268 }
5269
5271
5272 SCIPsetDebugMsg(set, "Problem solving finished with status %d (restart=%u, userrestart=%u)\n", stat->status, *restart, stat->userrestart);
5273
5274 /* cuts off nodes with lower bound is not better than given cutoff bound, manually; this necessary to ensure that
5275 * SCIP terminates with a proper solve stage
5276 */
5277 SCIP_CALL( SCIPtreeCutoff(tree, reopt, blkmem, set, stat, eventfilter, eventqueue, lp, primal->cutoffbound) );
5278
5279 /* if the current node is the only remaining node, and if its lower bound exceeds the upper bound, we have
5280 * to delete it manually in order to get to the SOLVED stage instead of thinking, that only the gap limit
5281 * was reached (this may happen, if the current node is the one defining the global lower bound and a
5282 * feasible solution with the same value was found at this node)
5283 */
5284 if( tree->focusnode != NULL && SCIPtreeGetNNodes(tree) == 0
5285 && SCIPsetIsGE(set, tree->focusnode->lowerbound, primal->cutoffbound) )
5286 {
5287 if( set->reopt_enable )
5288 {
5289 assert(reopt != NULL);
5291 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode, tree->focusnode->lowerbound,
5292 tree->effectiverootdepth) );
5293 }
5294
5295 focusnode = NULL;
5296 SCIP_CALL( SCIPnodeFocus(&focusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
5297 branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, FALSE, FALSE) );
5298 }
5299
5300 /* check whether we finished solving */
5301 if( SCIPtreeGetNNodes(tree) == 0 && SCIPtreeGetCurrentNode(tree) == NULL )
5302 {
5303 /* no restart necessary */
5304 *restart = FALSE;
5305
5306 /* set the solution status */
5308 {
5309 if( primal->nsols > 0 )
5310 {
5311 /* switch status to UNBOUNDED */
5313 }
5314 else
5315 {
5316 /* switch status to INFORUNB */
5318 }
5319 }
5320 else if( primal->nlimsolsfound == 0 )
5321 {
5322 assert(primal->nsols == 0 || SCIPsetIsGT(set, SCIPsolGetObj(primal->sols[0], set, transprob, origprob),
5323 SCIPprobInternObjval(transprob, origprob, set, SCIPprobGetObjlim(transprob, set))));
5324
5325 /* switch status to INFEASIBLE */
5327 }
5328 else
5329 {
5330 /* switch status to OPTIMAL */
5332 }
5333 }
5334
5335 return SCIP_OKAY;
5336}
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:2747
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:2616
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:2514
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:287
int SCIPgetNConcurrentSolvers(SCIP *scip)
Definition concurrent.c:116
helper functions for concurrent scip solvers
int SCIPconflictGetNConflicts(SCIP_CONFLICT *conflict)
Definition conflict.c:3781
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)
Definition conflict.c:3572
SCIP_Longint SCIPconflictGetNInfeasibleLPSuccess(SCIP_CONFLICT *conflict)
Definition conflict.c:8868
SCIP_Longint SCIPconflictGetNBoundexceedingLPSuccess(SCIP_CONFLICT *conflict)
Definition conflict.c:8948
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)
Definition conflict.c:9424
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)
Definition conflict.c:8701
SCIP_Longint SCIPconflictGetNPseudoSuccess(SCIP_CONFLICT *conflict)
Definition conflict.c:9596
SCIP_Longint SCIPconflictGetNPropSuccess(SCIP_CONFLICT *conflict)
Definition conflict.c:5771
SCIP_Longint SCIPconflictGetNStrongbranchSuccess(SCIP_CONFLICT *conflict)
Definition conflict.c:9352
internal methods for conflict analysis
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:2860
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:3146
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:3017
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:3334
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:2753
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:3805
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:3539
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 SCIP_Longint
Definition def.h:171
#define SCIP_REAL_MAX
Definition def.h:187
#define SCIP_INVALID
Definition def.h:206
#define SCIP_Real
Definition def.h:186
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIPABORT()
Definition def.h:360
#define SCIP_REAL_MIN
Definition def.h:188
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
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:11096
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
Definition lp.c:17115
SCIP_PROPTIMING SCIPconshdlrGetPropTiming(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5209
SCIP_Bool SCIPconshdlrWasSolSeparationDelayed(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5169
int SCIPconshdlrGetSepaPriority(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5059
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4180
SCIP_Bool SCIPconshdlrWasLPSeparationDelayed(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5159
SCIP_Bool SCIPconshdlrWasPropagationDelayed(SCIP_CONSHDLR *conshdlr)
Definition cons.c:5179
int SCIPheurGetPriority(SCIP_HEUR *heur)
Definition heur.c:1511
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1450
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:3448
SCIP_RETCODE SCIPprintRay(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:2178
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:17442
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition var.c:17611
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17590
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition var.c:18274
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
SCIP_BDCHGINFO * SCIPvarGetBdchgInfoLb(SCIP_VAR *var, int pos)
Definition var.c:18300
int SCIPvarGetNBdchgInfosUb(SCIP_VAR *var)
Definition var.c:18332
SCIP_BDCHGINFO * SCIPvarGetBdchgInfoUb(SCIP_VAR *var, int pos)
Definition var.c:18320
int SCIPvarGetNBdchgInfosLb(SCIP_VAR *var)
Definition var.c:18312
void SCIPregressionAddObservation(SCIP_REGRESSION *regression, SCIP_Real x, SCIP_Real y)
Definition misc.c:380
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:1260
SCIP_Bool SCIPheurShouldBeExecuted(SCIP_HEUR *heur, int depth, int lpstateforkdepth, SCIP_HEURTIMING heurtiming, SCIP_Bool *delayed)
Definition heur.c:1198
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
#define NULL
Definition lpi_spx1.cpp:161
size_t BMSgetNUsedBufferMemory(BMS_BUFMEM *buffer)
Definition memory.c:3123
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:132
struct BMS_BlkMem BMS_BLKMEM
Definition memory.h:439
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:1570
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:1500
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:1276
internal methods for collecting primal CIP solutions and primal informations
SCIP_Real SCIPprobGetObjlim(SCIP_PROB *prob, SCIP_SET *set)
Definition prob.c:2321
SCIP_Real SCIPprobExternObjval(SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_SET *set, SCIP_Real objval)
Definition prob.c:2116
void SCIPprobStoreRootSol(SCIP_PROB *prob, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_Bool roothaslp)
Definition prob.c:1737
SCIP_Bool SCIPprobAllColsInLP(SCIP_PROB *prob, SCIP_SET *set, SCIP_LP *lp)
Definition prob.c:2309
void SCIPprobUpdateBestRootSol(SCIP_PROB *prob, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition prob.c:1764
SCIP_Real SCIPprobInternObjval(SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_SET *set, SCIP_Real objval)
Definition prob.c:2138
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:6227
int SCIPsetGetSepaMaxcuts(SCIP_SET *set, SCIP_Bool root)
Definition set.c:5851
SCIP_Bool SCIPsetIsFeasEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6531
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6191
void SCIPsetSortRelaxs(SCIP_SET *set)
Definition set.c:4144
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6155
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6553
void SCIPsetSortPricers(SCIP_SET *set)
Definition set.c:3691
void SCIPsetSortSepas(SCIP_SET *set)
Definition set.c:4218
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition set.c:5998
void SCIPsetSortProps(SCIP_SET *set)
Definition set.c:4353
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6173
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition set.c:6133
void SCIPsetSortHeurs(SCIP_SET *set)
Definition set.c:4573
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6209
int SCIPsetGetPriceMaxvars(SCIP_SET *set, SCIP_Bool root)
Definition set.c:5837
SCIP_NODESEL * SCIPsetGetNodesel(SCIP_SET *set, SCIP_STAT *stat)
Definition set.c:4771
internal methods for global SCIP settings
#define SCIPsetFreeBufferArray(set, ptr)
Definition set.h:1741
#define SCIPsetAllocBufferArray(set, ptr, num)
Definition set.h:1734
#define SCIPsetDebugMsg
Definition set.h:1770
#define SCIPsetReallocBufferArray(set, ptr, num)
Definition set.h:1738
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:1672
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:2230
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:3267
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:2845
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:4829
#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:1817
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:3614
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:3657
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:2923
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:3167
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:3558
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:2013
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:4692
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:2261
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:4027
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:2905
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:1960
static SCIP_Bool restartAllowed(SCIP_SET *set, SCIP_STAT *stat)
Definition solve.c:4008
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
union SCIP_Node::@18 data
SCIP_DOMCHG * domchg
SCIP_FORK * fork
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:74
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:237
the function declarations for the synchronization store
#define MAX(x, y)
Definition tclique_def.h:92
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:14466
SCIP_RETCODE SCIPvarUpdatePseudocost(SCIP_VAR *var, SCIP_SET *set, SCIP_STAT *stat, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition var.c:14368
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:15604
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)