Scippy

SCIP

Solving Constraint Integer Programs

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-2025 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;
156 int nclockskips = MAXNCLOCKSKIPS;
157
158 avgisstoppedfreq = currtime / stat->nisstoppedcalls;
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
164 stat->nclockskipsleft = nclockskips;
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_primal != SCIP_INVALID && !SCIPsetIsPositive(set, (int)SCIPgetObjsense(set->scip) * (SCIPgetPrimalbound(set->scip) - set->limit_primal)) ) /*lint !e777*/
193 else if( set->limit_dual != SCIP_INVALID && !SCIPsetIsNegative(set, (int)SCIPgetObjsense(set->scip) * (SCIPgetDualbound(set->scip) - set->limit_dual)) ) /*lint !e777*/
195 else if( set->limit_solutions >= 0 && set->stage >= SCIP_STAGE_PRESOLVING
196 && SCIPgetNLimSolsFound(set->scip) >= set->limit_solutions )
198 else if( set->limit_bestsol >= 0 && set->stage >= SCIP_STAGE_PRESOLVING
199 && SCIPgetNBestSolsFound(set->scip) >= set->limit_bestsol )
201 else if( checknodelimits && set->limit_nodes >= 0 && stat->nnodes >= set->limit_nodes )
203 else if( checknodelimits && set->limit_totalnodes >= 0 && stat->ntotalnodes >= set->limit_totalnodes )
205 else if( checknodelimits && set->limit_stallnodes >= 0 && stat->nnodes >= stat->bestsolnode + set->limit_stallnodes )
207
208 /* If stat->status was initialized to SCIP_STATUS_NODELIMIT or SCIP_STATUS_STALLNODELIMIT due to a previous call to SCIPsolveIsStopped(,,TRUE),
209 * in the case of checknodelimits == FALSE, we do not want to report here that the solve will be stopped due to a nodelimit.
210 */
211 if( !checknodelimits )
213 else
215}
216
217/** calls primal heuristics */
219 SCIP_SET* set, /**< global SCIP settings */
220 SCIP_STAT* stat, /**< dynamic problem statistics */
221 SCIP_PROB* prob, /**< transformed problem after presolve */
222 SCIP_PRIMAL* primal, /**< primal data */
223 SCIP_TREE* tree, /**< branch and bound tree, or NULL if called during presolving */
224 SCIP_LP* lp, /**< LP data, or NULL if called during presolving or propagation */
225 SCIP_NODE* nextnode, /**< next node that will be processed, or NULL if no more nodes left
226 * (only needed when calling after node heuristics) */
227 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
228 SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */
229 SCIP_Bool* foundsol, /**< pointer to store whether a solution has been found */
230 SCIP_Bool* unbounded /**< pointer to store whether an unbounded ray was found in the LP */
231 )
232{ /*lint --e{715}*/
233 SCIP_RESULT result;
234 SCIP_Longint oldnbestsolsfound;
235 SCIP_Real lowerbound;
236 int ndelayedheurs;
237 int depth;
238 int lpstateforkdepth;
239 int h;
240#ifndef NDEBUG
241 SCIP_Bool inprobing;
242 SCIP_Bool indiving;
243#endif
244
245 assert(set != NULL);
246 assert(primal != NULL);
247 assert(tree != NULL || heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP);
248 assert(lp != NULL || heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP
249 || heurtiming == SCIP_HEURTIMING_AFTERPROPLOOP);
250 assert(heurtiming == SCIP_HEURTIMING_BEFORENODE || heurtiming == SCIP_HEURTIMING_DURINGLPLOOP
251 || heurtiming == SCIP_HEURTIMING_AFTERLPLOOP || heurtiming == SCIP_HEURTIMING_AFTERNODE
255 assert(heurtiming != SCIP_HEURTIMING_AFTERNODE || (nextnode == NULL) == (SCIPtreeGetNNodes(tree) == 0));
256 assert(foundsol != NULL);
257
258 *foundsol = FALSE;
259
260 /* nothing to do, if no heuristics are available, or if the branch-and-bound process is finished */
261 if( set->nheurs == 0 || (heurtiming == SCIP_HEURTIMING_AFTERNODE && nextnode == NULL) )
262 return SCIP_OKAY;
263
264 /* do not continue if we reached a time limit */
265 if( SCIPsolveIsStopped(set, stat, FALSE) )
266 return SCIP_OKAY;
267
268 /* sort heuristics by priority, but move the delayed heuristics to the front */
270
271 /* specialize the AFTERNODE timing flag */
273 {
274 SCIP_Bool plunging;
275 SCIP_Bool pseudonode;
276
277 /* clear the AFTERNODE flags and replace them by the right ones */
278 heurtiming &= ~SCIP_HEURTIMING_AFTERNODE;
279
280 /* we are in plunging mode iff the next node is a sibling or a child, and no leaf */
281 assert(nextnode == NULL
284 || SCIPnodeGetType(nextnode) == SCIP_NODETYPE_LEAF);
285 plunging = (nextnode != NULL && SCIPnodeGetType(nextnode) != SCIP_NODETYPE_LEAF);
286 pseudonode = !SCIPtreeHasFocusNodeLP(tree);
287 if( plunging && SCIPtreeGetCurrentDepth(tree) > 0 ) /* call plunging heuristics also at root node */
288 {
289 if( !pseudonode )
290 heurtiming |= SCIP_HEURTIMING_AFTERLPNODE;
291 else
293 }
294 else
295 {
296 if( !pseudonode )
298 else
300 }
301 }
302
303 /* initialize the tree related data, if we are not in presolving */
304 if( heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP )
305 {
306 depth = -1;
307 lpstateforkdepth = -1;
308
309 SCIPsetDebugMsg(set, "calling primal heuristics %s presolving\n",
310 heurtiming == SCIP_HEURTIMING_BEFOREPRESOL ? "before" : "during");
311 }
312 else
313 {
314 assert(tree != NULL); /* for lint */
315 depth = SCIPtreeGetFocusDepth(tree);
316 lpstateforkdepth = (tree->focuslpstatefork != NULL ? SCIPnodeGetDepth(tree->focuslpstatefork) : -1);
317
318 SCIPsetDebugMsg(set, "calling primal heuristics in depth %d (timing: %u)\n", depth, heurtiming);
319 }
320
321 /* call heuristics */
322 ndelayedheurs = 0;
323 oldnbestsolsfound = primal->nbestsolsfound;
324
325#ifndef NDEBUG
326 /* remember old probing and diving status */
327 inprobing = tree != NULL && SCIPtreeProbing(tree);
328 indiving = lp != NULL && SCIPlpDiving(lp);
329
330 /* heuristics should currently not be called in diving mode */
331 assert(!indiving);
332#endif
333
334 /* collect lower bound of current node */
335 if( tree != NULL )
336 {
337 assert(SCIPtreeGetFocusNode(tree) != NULL);
339 }
340 else if( lp != NULL )
341 lowerbound = SCIPlpGetPseudoObjval(lp, set, prob);
342 else
343 lowerbound = -SCIPsetInfinity(set);
344
345 for( h = 0; h < set->nheurs; ++h )
346 {
347#ifndef NDEBUG
348 size_t nusedbuffer = BMSgetNUsedBufferMemory(SCIPbuffer(set->scip));
349#endif
350 /* it might happen that a diving heuristic renders the previously solved node LP invalid
351 * such that additional calls to LP heuristics will fail; better abort the loop in this case
352 */
353 if( lp != NULL && lp->resolvelperror)
354 break;
355
356#ifdef SCIP_DEBUG
357 {
358 SCIP_Bool delayed;
359 if( SCIPheurShouldBeExecuted(set->heurs[h], depth, lpstateforkdepth, heurtiming, &delayed) )
360 {
361 SCIPsetDebugMsg(set, " -> executing heuristic <%s> with priority %d\n",
362 SCIPheurGetName(set->heurs[h]), SCIPheurGetPriority(set->heurs[h]));
363 }
364 }
365#endif
366
367 SCIP_CALL( SCIPheurExec(set->heurs[h], set, primal, depth, lpstateforkdepth, heurtiming, nodeinfeasible,
368 &ndelayedheurs, &result) );
369
370#ifndef NDEBUG
371 if( BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)) > nusedbuffer )
372 {
373 SCIPerrorMessage("Buffer not completely freed after executing heuristic <%s>\n", SCIPheurGetName(set->heurs[h]));
374 SCIPABORT();
375 }
376#endif
377
378 /* if the new solution cuts off the current node due to a new primal solution (via the cutoff bound) interrupt
379 * calling the remaining heuristics
380 */
381 if( SCIPsolveIsStopped(set, stat, FALSE) || ( result == SCIP_FOUNDSOL && SCIPsetIsGE(set, lowerbound, primal->cutoffbound) ) )
382 break;
383
384 /* check if the problem is proven to be unbounded, currently this happens only in reoptimization */
385 if( result == SCIP_UNBOUNDED )
386 {
387 *unbounded = TRUE;
388 break;
389 }
390
391 /* make sure that heuristic did not change probing or diving status */
392 assert(tree == NULL || inprobing == SCIPtreeProbing(tree));
393 assert(lp == NULL || indiving == SCIPlpDiving(lp));
394 }
395 assert(0 <= ndelayedheurs && ndelayedheurs <= set->nheurs);
396
397 *foundsol = (primal->nbestsolsfound > oldnbestsolsfound);
398
399 return SCIP_OKAY;
400}
401
402/** applies one round of propagation */
403static
405 BMS_BLKMEM* blkmem, /**< block memory buffers */
406 SCIP_SET* set, /**< global SCIP settings */
407 SCIP_STAT* stat, /**< dynamic problem statistics */
408 SCIP_TREE* tree, /**< branch and bound tree */
409 int depth, /**< depth level to use for propagator frequency checks */
410 SCIP_Bool fullpropagation, /**< should all constraints be propagated (or only new ones)? */
411 SCIP_Bool onlydelayed, /**< should only delayed propagators be called? */
412 SCIP_Bool* delayed, /**< pointer to store whether a propagator was delayed */
413 SCIP_Bool* propagain, /**< pointer to store whether propagation should be applied again */
414 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */
415 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
416 SCIP_Bool* postpone /**< pointer to store whether the node should be postponed */
417 )
418{ /*lint --e{715}*/
419 SCIP_RESULT result;
420 SCIP_Bool abortoncutoff;
421 int i;
422
423 assert(set != NULL);
424 assert(delayed != NULL);
425 assert(propagain != NULL);
426 assert(cutoff != NULL);
427 assert(postpone != NULL);
428
429 *delayed = FALSE;
430 *propagain = FALSE;
431
432 /* sort propagators */
434
435 /* 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
436 * anyway
437 */
438 abortoncutoff = set->prop_abortoncutoff || (set->stage != SCIP_STAGE_SOLVING);
439
440 /* call additional propagators with nonnegative priority */
441 for( i = 0; i < set->nprops && !(*postpone) && (!(*cutoff) || !abortoncutoff); ++i )
442 {
443#ifndef NDEBUG
444 size_t nusedbuffer = BMSgetNUsedBufferMemory(SCIPbuffer(set->scip));
445#endif
446 /* timing needs to fit */
447 if( (SCIPpropGetTimingmask(set->props[i]) & timingmask) == 0 )
448 continue;
449
450 if( SCIPpropGetPriority(set->props[i]) < 0 )
451 continue;
452
453 if( onlydelayed && !SCIPpropWasDelayed(set->props[i]) )
454 continue;
455
456 SCIPsetDebugMsg(set, "calling propagator <%s>\n", SCIPpropGetName(set->props[i]));
457
458 SCIP_CALL( SCIPpropExec(set->props[i], set, stat, depth, onlydelayed, tree->sbprobing, timingmask, &result) );
459
460#ifndef NDEBUG
461 if( BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)) > nusedbuffer )
462 {
463 SCIPerrorMessage("Buffer not completely freed after executing propagator <%s>\n", SCIPpropGetName(set->props[i]));
464 SCIPABORT();
465 }
466#endif
467
468 *delayed = *delayed || (result == SCIP_DELAYED);
469 *propagain = *propagain || (result == SCIP_REDUCEDDOM);
470
471 /* beside the result pointer of the propagator we have to check if an internal cutoff was detected; this can
472 * happen when a global bound change was applied which is globally valid and leads locally (for the current node
473 * and others) to an infeasible problem;
474 */
475 *cutoff = *cutoff || (result == SCIP_CUTOFF) || (tree->cutoffdepth <= SCIPtreeGetCurrentDepth(tree));
476 *postpone = (result == SCIP_DELAYNODE) && !(*cutoff);
477
478 if( result == SCIP_CUTOFF )
479 {
480 SCIPsetDebugMsg(set, " -> propagator <%s> detected cutoff\n", SCIPpropGetName(set->props[i]));
481 }
482
483 /* if we work off the delayed propagators, we stop immediately if a reduction was found */
484 if( onlydelayed && result == SCIP_REDUCEDDOM )
485 {
486 *delayed = TRUE;
487 return SCIP_OKAY;
488 }
489 }
490
491 /* propagate constraints */
492 for( i = 0; i < set->nconshdlrs && !(*postpone) && (!(*cutoff) || !abortoncutoff); ++i )
493 {
494 /* timing needs to fit */
495 if( (SCIPconshdlrGetPropTiming(set->conshdlrs[i]) & timingmask) == 0 )
496 continue;
497
498 if( onlydelayed && !SCIPconshdlrWasPropagationDelayed(set->conshdlrs[i]) )
499 continue;
500
501 SCIPsetDebugMsg(set, "calling propagation method of constraint handler <%s>\n", SCIPconshdlrGetName(set->conshdlrs[i]));
502
503 SCIP_CALL( SCIPconshdlrPropagate(set->conshdlrs[i], blkmem, set, stat, depth, fullpropagation, onlydelayed,
504 tree->sbprobing, timingmask, &result) );
505 *delayed = *delayed || (result == SCIP_DELAYED);
506 *propagain = *propagain || (result == SCIP_REDUCEDDOM);
507
508 /* beside the result pointer of the propagator we have to check if an internal cutoff was detected; this can
509 * happen when a global bound change was applied which is globally valid and leads locally (for the current node
510 * and others) to an infeasible problem;
511 */
512 *cutoff = *cutoff || (result == SCIP_CUTOFF) || (tree->cutoffdepth <= SCIPtreeGetCurrentDepth(tree));
513 *postpone = (result == SCIP_DELAYNODE) && !(*cutoff);
514
515 if( result == SCIP_CUTOFF )
516 {
517 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in propagation\n",
518 SCIPconshdlrGetName(set->conshdlrs[i]));
519 }
520
521 /* if we work off the delayed propagators, we stop immediately if a reduction was found */
522 if( onlydelayed && result == SCIP_REDUCEDDOM )
523 {
524 *delayed = TRUE;
525 return SCIP_OKAY;
526 }
527 }
528
529 /* call additional propagators with negative priority */
530 for( i = 0; i < set->nprops && !(*postpone) && (!(*cutoff) || !abortoncutoff); ++i )
531 {
532 /* timing needs to fit */
533 if( (SCIPpropGetTimingmask(set->props[i]) & timingmask) == 0 )
534 continue;
535
536 if( SCIPpropGetPriority(set->props[i]) >= 0 )
537 continue;
538
539 if( onlydelayed && !SCIPpropWasDelayed(set->props[i]) )
540 continue;
541
542 SCIPsetDebugMsg(set, "calling propagator <%s>\n", SCIPpropGetName(set->props[i]));
543
544 SCIP_CALL( SCIPpropExec(set->props[i], set, stat, depth, onlydelayed, tree->sbprobing, timingmask, &result) );
545 *delayed = *delayed || (result == SCIP_DELAYED);
546 *propagain = *propagain || (result == SCIP_REDUCEDDOM);
547
548 /* beside the result pointer of the propagator we have to check if an internal cutoff was detected; this can
549 * happen when a global bound change was applied which is globally valid and leads locally (for the current node
550 * and others) to an infeasible problem;
551 */
552 *cutoff = *cutoff || (result == SCIP_CUTOFF) || (tree->cutoffdepth <= SCIPtreeGetCurrentDepth(tree));
553 *postpone = (result == SCIP_DELAYNODE) && !(*cutoff);
554
555 if( result == SCIP_CUTOFF )
556 {
557 SCIPsetDebugMsg(set, " -> propagator <%s> detected cutoff\n", SCIPpropGetName(set->props[i]));
558 }
559
560 /* if we work off the delayed propagators, we stop immediately if a reduction was found */
561 if( onlydelayed && result == SCIP_REDUCEDDOM )
562 {
563 *delayed = TRUE;
564 return SCIP_OKAY;
565 }
566 }
567
568 return SCIP_OKAY;
569}
570
571/** applies domain propagation on current node */
572static
574 BMS_BLKMEM* blkmem, /**< block memory buffers */
575 SCIP_SET* set, /**< global SCIP settings */
576 SCIP_STAT* stat, /**< dynamic problem statistics */
577 SCIP_TREE* tree, /**< branch and bound tree */
578 int depth, /**< depth level to use for propagator frequency checks */
579 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
580 SCIP_Bool fullpropagation, /**< should all constraints be propagated (or only new ones)? */
581 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */
582 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
583 SCIP_Bool* postpone /**< pointer to store whether the node should be postponed */
584 )
585{
586 SCIP_NODE* node;
587 SCIP_Bool delayed;
588 SCIP_Bool propagain;
589 int propround;
590
591 assert(set != NULL);
592 assert(tree != NULL);
593 assert(depth >= 0);
594 assert(cutoff != NULL);
595
596 node = SCIPtreeGetCurrentNode(tree);
597 assert(node != NULL && SCIPnodeIsActive(node));
601
602 /* adjust maximal number of propagation rounds */
603 if( maxproprounds == 0 )
604 maxproprounds = (depth == 0 ? set->prop_maxroundsroot : set->prop_maxrounds);
605 if( maxproprounds == -1 )
606 maxproprounds = INT_MAX;
607
608 SCIPsetDebugMsg(set, "domain propagation of node %p in depth %d (using depth %d, maxrounds %d, proptiming %u)\n",
609 (void*)node, SCIPnodeGetDepth(node), depth, maxproprounds, timingmask);
610
611 /* propagate as long new bound changes were found and the maximal number of propagation rounds is not exceeded */
612 *cutoff = FALSE;
613 *postpone = FALSE;
614 propround = 0;
615 propagain = TRUE;
616 while( propagain && !(*cutoff) && !(*postpone) && propround < maxproprounds && !SCIPsolveIsStopped(set, stat, FALSE) )
617 {
618 propround++;
619
620 /* perform the propagation round by calling the propagators and constraint handlers */
621 SCIP_CALL( propagationRound(blkmem, set, stat, tree, depth, fullpropagation, FALSE, &delayed, &propagain, timingmask, cutoff, postpone) );
622
623 /* if the propagation will be terminated, call the delayed propagators */
624 while( delayed && (!propagain || propround >= maxproprounds) && !(*cutoff) )
625 {
626 /* call the delayed propagators and constraint handlers */
627 SCIP_CALL( propagationRound(blkmem, set, stat, tree, depth, fullpropagation, TRUE, &delayed, &propagain, timingmask, cutoff, postpone) );
628 }
629
630 /* if a reduction was found, we want to do another full propagation round (even if the propagator only claimed
631 * to have done a domain reduction without applying a domain change)
632 */
633 fullpropagation = TRUE;
634 }
635
636 /* mark the node to be completely propagated in the current repropagation subtree level */
637 SCIPnodeMarkPropagated(node, tree);
638
639 if( *cutoff )
640 {
641 SCIPsetDebugMsg(set, " --> domain propagation of node %p finished: cutoff!\n", (void*)node);
642 }
643
644 return SCIP_OKAY;
645}
646
647/** applies domain propagation on current node and flushes the conflict store afterwards */
649 BMS_BLKMEM* blkmem, /**< block memory buffers */
650 SCIP_SET* set, /**< global SCIP settings */
651 SCIP_STAT* stat, /**< dynamic problem statistics */
652 SCIP_PROB* transprob, /**< transformed problem */
653 SCIP_PROB* origprob, /**< original problem */
654 SCIP_TREE* tree, /**< branch and bound tree */
655 SCIP_REOPT* reopt, /**< reoptimization data structure */
656 SCIP_LP* lp, /**< LP data */
657 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
658 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
659 SCIP_CONFLICT* conflict, /**< conflict analysis data */
660 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
661 int depth, /**< depth level to use for propagator frequency checks */
662 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
663 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */
664 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
665 )
666{
667 SCIP_Bool postpone;
668
669 /* apply domain propagation */
670 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, depth, maxproprounds, TRUE, timingmask, cutoff, &postpone) );
671
672 /* flush the conflict set storage */
673 SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable) );
674
675 return SCIP_OKAY;
676}
677
678/** returns whether the given variable with the old LP solution value should lead to an update of the pseudo cost entry */
679static
681 SCIP_VAR* var, /**< problem variable */
682 SCIP_SET* set, /**< global SCIP settings */
683 SCIP_Real oldlpsolval, /**< solution value of variable in old LP */
684 SCIP_Bool updateintegers, /**< whether to update pseudo costs for integer variables */
685 SCIP_Bool updatecontinuous /**< whether to update pseudo costs for continuous variables */
686 )
687{
688 SCIP_Real newlpsolval;
689
690 assert(var != NULL);
691
692 if( !updatecontinuous && SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
693 return FALSE;
694
695 if( !updateintegers && SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
696 return FALSE;
697
698 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS && set->branch_lpgainnorm != 'l' )
699 {
700 /* if the variable is fixed at +/- infinity or it has an unbounded domain, then the domain-based update strategies will not work */
702 return FALSE;
703
704 /* @todo if set->branch_lpgainnorm == 's', then we would need to know then domain before branching
705 * since this is difficult to get, we don't check for unboundedness here and let the pscost update fail later
706 * however, this makes the weights used to spread a pseudo cost update over all domain changes inaccurate
707 */
708
709 return TRUE;
710 }
711
712 /* if the old LP solution value is unknown, the pseudo cost update cannot be performed */
713 if( oldlpsolval >= SCIP_INVALID )
714 return FALSE;
715
716 /* the bound change on the given variable was responsible for the gain in the dual bound, if the variable's
717 * old solution value is outside the current bounds, and the new solution value is equal to the bound
718 * closest to the old solution value
719 */
720
721 /* find out, which of the current bounds is violated by the old LP solution value */
722 if( SCIPsetIsLT(set, oldlpsolval, SCIPvarGetLbLocal(var)) )
723 {
724 newlpsolval = SCIPvarGetLPSol(var);
725 return SCIPsetIsEQ(set, newlpsolval, SCIPvarGetLbLocal(var));
726 }
727 else if( SCIPsetIsGT(set, oldlpsolval, SCIPvarGetUbLocal(var)) )
728 {
729 newlpsolval = SCIPvarGetLPSol(var);
730 return SCIPsetIsEQ(set, newlpsolval, SCIPvarGetUbLocal(var));
731 }
732 else
733 return FALSE;
734}
735
736/** pseudo cost flag stored in the variables to mark them for the pseudo cost update */
738{
739 PSEUDOCOST_NONE = 0, /**< variable's bounds were not changed */
740 PSEUDOCOST_IGNORE = 1, /**< bound changes on variable should be ignored for pseudo cost updates */
741 PSEUDOCOST_UPDATE = 2 /**< pseudo cost value of variable should be updated */
744
745/** updates the variable's pseudo cost values after the node's initial LP was solved */
746static
748 SCIP_SET* set, /**< global SCIP settings */
749 SCIP_STAT* stat, /**< dynamic problem statistics */
750 SCIP_PROB* prob, /**< transformed problem after presolve */
751 SCIP_TREE* tree, /**< branch and bound tree */
752 SCIP_LP* lp, /**< LP data */
753 SCIP_Bool updateintegers, /**< whether to update pseudo costs for integer variables */
754 SCIP_Bool updatecontinuous /**< whether to update pseudo costs for continuous variables */
755 )
756{
757 SCIP_NODE* focusnode;
758 int actdepth;
759
760 assert(lp != NULL);
761 assert(tree != NULL);
762 assert(tree->path != NULL);
763
764 focusnode = SCIPtreeGetFocusNode(tree);
765 assert(SCIPnodeIsActive(focusnode));
766 assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
767 actdepth = SCIPnodeGetDepth(focusnode);
768 assert(tree->path[actdepth] == focusnode);
769
770 if( (updateintegers || updatecontinuous) && lp->solved && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && tree->focuslpstatefork != NULL )
771 {
772 SCIP_BOUNDCHG** updates;
773 SCIP_NODE* node;
774 SCIP_VAR* var;
775 SCIP_Real weight;
776 SCIP_Real lpgain;
777 int nupdates;
778 int nvalidupdates;
779 int d;
780 int i;
781
782 assert(SCIPnodeIsActive(tree->focuslpstatefork));
783 assert(tree->path[tree->focuslpstatefork->depth] == tree->focuslpstatefork);
784
785 /* get a buffer for the collected bound changes; start with a size twice as large as the number of nodes between
786 * current node and LP fork
787 */
788 SCIP_CALL( SCIPsetAllocBufferArray(set, &updates, (int)(2*(actdepth - tree->focuslpstatefork->depth))) );
789 nupdates = 0;
790 nvalidupdates = 0;
791
792 /* search the nodes from LP fork down to current node for bound changes in between; move in this direction,
793 * because the bound changes closer to the LP fork are more likely to have a valid LP solution information
794 * attached; collect the bound changes for pseudo cost value updates and mark the corresponding variables such
795 * that they are not updated twice in case of more than one bound change on the same variable
796 */
797 for( d = tree->focuslpstatefork->depth+1; d <= actdepth; ++d )
798 {
799 node = tree->path[d];
800
801 if( node->domchg != NULL )
802 {
803 SCIP_BOUNDCHG* boundchgs;
804 int nboundchgs;
805
806 boundchgs = node->domchg->domchgbound.boundchgs;
807 nboundchgs = (int) node->domchg->domchgbound.nboundchgs;
808 for( i = 0; i < nboundchgs; ++i )
809 {
810 var = boundchgs[i].var;
811 assert(var != NULL);
812
813 /* we even collect redundant bound changes, since they were not redundant in the LP branching decision
814 * and therefore should be regarded in the pseudocost updates
815 *
816 * however, if the variable is continuous and we normalize the pseudo costs by the domain reduction,
817 * then getting the variable bound before the branching is not possible by looking at the variables branching information (since redundant branchings are not applied)
818 * thus, in this case we ignore the boundchange
819 */
820 if( (SCIP_BOUNDCHGTYPE)boundchgs[i].boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING &&
822 )
823 {
824 /* remember the bound change and mark the variable */
825 SCIP_CALL( SCIPsetReallocBufferArray(set, &updates, nupdates+1) );
826 updates[nupdates] = &boundchgs[i];
827 nupdates++;
828
829 /* check, if the bound change would lead to a valid pseudo cost update
830 * and see comment above (however, ...) */
831 if( isPseudocostUpdateValid(var, set, boundchgs[i].data.branchingdata.lpsolval, updateintegers, updatecontinuous) &&
832 (SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS || !boundchgs[i].redundant || set->branch_lpgainnorm != 'd')
833 )
834 {
835 var->pseudocostflag = PSEUDOCOST_UPDATE; /*lint !e641*/
836 nvalidupdates++;
837 }
838 else
839 var->pseudocostflag = PSEUDOCOST_IGNORE; /*lint !e641*/
840 }
841 }
842 }
843 }
844
845 /* update the pseudo cost values and reset the variables' flags; assume, that the responsibility for the dual gain
846 * is equally spread on all bound changes that lead to valid pseudo cost updates
847 */
849 weight = (nvalidupdates > 0 ? 1.0 / (SCIP_Real)nvalidupdates : 1.0);
850 lpgain = (SCIPlpGetObjval(lp, set, prob) - tree->focuslpstatefork->data.fork->lpobjval) * weight;
851 lpgain = MAX(lpgain, 0.0);
852
853 for( i = 0; i < nupdates; ++i )
854 {
855 assert((SCIP_BOUNDCHGTYPE)updates[i]->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING);
856
857 var = updates[i]->var;
858 assert(var != NULL);
860
862 {
863 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS || set->branch_lpgainnorm == 'l' )
864 {
865 SCIPsetDebugMsg(set, "updating pseudocosts of <%s>: sol: %g -> %g, LP: %e -> %e => solvaldelta = %g, gain=%g, weight: %g\n",
866 SCIPvarGetName(var), updates[i]->data.branchingdata.lpsolval, SCIPvarGetLPSol(var),
868 SCIPvarGetLPSol(var) - updates[i]->data.branchingdata.lpsolval, lpgain, weight);
870 SCIPvarGetLPSol(var) - updates[i]->data.branchingdata.lpsolval, lpgain, weight) );
871 }
872 else
873 {
874 /* set->branch_lpgainnorm == 'd':
875 * For continuous variables, we want to pseudocosts to be the average of the gain in the LP value
876 * if the domain is reduced from x% of its original width to y% of its original (e.g., global) width, i.e.,
877 * to be the average of LPgain / (oldwidth/origwidth - newwidth/origwidth) = LPgain * origwidth / (oldwidth - newwidth).
878 * Then an expected improvement in the LP value by a reduction of the domain width
879 * from x% to y% of its original width can be computed by pseudocost * (oldwidth - newwidth) / origwidth.
880 * Since the original width cancels out, we can also define the pseudocosts as average of LPgain / (oldwidth - newwidth)
881 * and compute the expected improvement as pseudocost * (oldwidth - newwidth).
882 *
883 * Let var have bounds [a,c] before the branching and assume we branched on some value b.
884 * b is given by updates[i]->newbound.
885 *
886 * If updates[i]->boundtype = upper, then node corresponds to the child [a,b].
887 * Thus, we have oldwidth = c-a, newwidth = b-a, and oldwidth - newwidth = c-b.
888 * To get c (the previous upper bound), we look into the var->ubchginfos array.
889 *
890 * If updates[i]->boundtype = lower, then node corresponds to the child [b,c].
891 * Thus, we have oldwidth = c-a, newwidth = c-b, and oldwidth - newwidth = b-a.
892 * To get c (the previous lower bound), we look into the var->lbchginfos array.
893 */
894 SCIP_BDCHGINFO* bdchginfo;
895 SCIP_Real oldbound;
896 SCIP_Real delta;
897 int j;
898 int nbdchginfos;
899
900 assert(set->branch_lpgainnorm == 'd' || set->branch_lpgainnorm == 's');
901
902 oldbound = SCIP_INVALID;
903
904 if( set->branch_lpgainnorm == 'd' )
905 {
906 assert(!updates[i]->redundant);
907
908 if( (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER )
909 {
910 nbdchginfos = SCIPvarGetNBdchgInfosUb(var);
911
912 /* walk backwards through bound change information array to find the bound change corresponding to branching in updates[i]
913 * usually it will be the first one we look at */
914 for( j = nbdchginfos-1; j >= 0; --j )
915 {
916 bdchginfo = SCIPvarGetBdchgInfoUb(var, j);
917
918 if( bdchginfo->oldbound > updates[i]->newbound )
919 {
920 /* first boundchange which upper bound is above the upper bound set by the branching in updates[i]
921 * if bdchginfo->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING, then this should be exactly the bound change that we are looking for
922 * 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
923 * 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
924 */
926 {
927 assert(bdchginfo->newbound == updates[i]->newbound); /*lint !e777*/
928 oldbound = bdchginfo->oldbound;
929 }
930 else
931 assert(updates[i]->redundant);
932
933 break;
934 }
935 }
936 /* 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
937 * if it is not redundant, then we should have found at least one corresponding boundchange */
938 assert(j >= 0 || updates[i]->redundant);
939 if( oldbound != SCIP_INVALID ) /*lint !e777*/
940 {
941 assert(!SCIPsetIsInfinity(set, -oldbound)); /* branching on a variable fixed to -infinity does not make sense */
942 assert(!SCIPsetIsInfinity(set, updates[i]->newbound)); /* branching to infinity does not make sense */
943
944 /* 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 */
945 if( SCIPsetIsInfinity(set, oldbound) || SCIPsetIsInfinity(set, -updates[i]->newbound) )
946 delta = SCIP_INVALID;
947 else
948 delta = updates[i]->newbound - oldbound;
949 }
950 else
951 delta = SCIP_INVALID;
952 }
953 else
954 {
955 assert((SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_LOWER);
956 nbdchginfos = SCIPvarGetNBdchgInfosLb(var);
957
958 /* walk backwards through bound change information array to find the bound change corresponding to branching in updates[i]
959 * usually it will be the first one we look at */
960 for( j = nbdchginfos-1; j >= 0; --j )
961 {
962 bdchginfo = SCIPvarGetBdchgInfoLb(var, j);
963
964 if( bdchginfo->oldbound < updates[i]->newbound )
965 {
966 /* first boundchange which lower bound is below the lower bound set by the branching in updates[i]
967 * if bdchginfo->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING, then this should be exactly the bound change that we are looking for
968 * 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
969 * 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
970 */
972 {
973 assert(bdchginfo->newbound == updates[i]->newbound); /*lint !e777*/
974 oldbound = bdchginfo->oldbound;
975 }
976 else
977 assert(updates[i]->redundant);
978
979 break;
980 }
981 }
982 /* 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
983 * if it is not redundant, then we should have found at least one corresponding boundchange */
984 assert(j >= 0 || updates[i]->redundant);
985 if( oldbound != SCIP_INVALID ) /*lint !e777*/
986 {
987 assert(!SCIPsetIsInfinity(set, oldbound)); /* branching on a variable fixed to +infinity does not make sense */
988 assert(!SCIPsetIsInfinity(set, -updates[i]->newbound)); /* branching to infinity does not make sense */
989
990 /* 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 */
991 if( SCIPsetIsInfinity(set, -oldbound) || SCIPsetIsInfinity(set, updates[i]->newbound) )
992 delta = SCIP_INVALID;
993 else
994 delta = updates[i]->newbound - oldbound;
995 }
996 else
997 delta = SCIP_INVALID;
998 }
999 }
1000 else
1001 {
1002 /* set->branch_lpgainnorm == 's':
1003 * Here, we divide the LPgain by the reduction in the sibling node.
1004 *
1005 * If updates[i]->boundtype = upper, then node corresponds to the child [a,b].
1006 * Thus, we have oldwidth = c-a, newwidth = c-b, and oldwidth - newwidth = b-a.
1007 * Conveniently, we just use the current lower bound for a (it may have been tightened, though).
1008 *
1009 * If updates[i]->boundtype = lower, then node corresponds to the child [b,a].
1010 * Thus, we have oldwidth = c-a, newwidth = b-a, and oldwidth - newwidth = c-b.
1011 * Conveniently, we just use the current upper bound for c (it may have been tightened, though).
1012 */
1013 if( (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER )
1014 {
1015 assert(!SCIPsetIsInfinity(set, updates[i]->newbound)); /* branching on a variable fixed to +infinity does not make sense */
1016 assert(!SCIPsetIsInfinity(set, SCIPvarGetLbLocal(var))); /* branching to infinity does not make sense */
1017 if( SCIPsetIsInfinity(set, -updates[i]->newbound) || SCIPsetIsInfinity(set, -SCIPvarGetLbLocal(var)) )
1018 delta = SCIP_INVALID;
1019 else
1020 delta = updates[i]->newbound - SCIPvarGetLbLocal(var);
1021 }
1022 else
1023 {
1024 assert((SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_LOWER);
1025 assert(!SCIPsetIsInfinity(set, -updates[i]->newbound)); /* branching on a variable fixed to -infinity does not make sense */
1026 assert(!SCIPsetIsInfinity(set, -SCIPvarGetUbLocal(var))); /* branching to -infinity does not make sense */
1027 if( SCIPsetIsInfinity(set, updates[i]->newbound) || SCIPsetIsInfinity(set, SCIPvarGetUbLocal(var)) )
1028 delta = SCIP_INVALID;
1029 else
1030 delta = -(SCIPvarGetUbLocal(var) - updates[i]->newbound);
1031 }
1032 }
1033
1034 if( delta != SCIP_INVALID ) /*lint !e777*/
1035 {
1036 SCIPsetDebugMsg(set, "updating pseudocosts of <%s> with strategy %c: domain: [%g,%g] -> [%g,%g], LP: %e -> %e => "
1037 "delta = %g, gain=%g, weight: %g\n",
1038 SCIPvarGetName(var), set->branch_lpgainnorm,
1039 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? SCIPvarGetLbLocal(var) : oldbound,
1040 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? oldbound : SCIPvarGetUbLocal(var),
1041 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? SCIPvarGetLbLocal(var) : updates[i]->newbound,
1042 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? updates[i]->newbound : SCIPvarGetUbLocal(var),
1044 delta, lpgain, weight);
1045
1046 SCIP_CALL( SCIPvarUpdatePseudocost(var, set, stat, delta, lpgain, weight) );
1047 }
1048 }
1049 }
1050 var->pseudocostflag = PSEUDOCOST_NONE; /*lint !e641*/
1051 }
1052
1053 /* free the buffer for the collected bound changes */
1054 SCIPsetFreeBufferArray(set, &updates);
1055 }
1056
1057 return SCIP_OKAY;
1058}
1059
1060/** updates the estimated value of a primal feasible solution for the focus node after the LP was solved */
1061static
1063 SCIP_SET* set, /**< global SCIP settings */
1064 SCIP_STAT* stat, /**< problem statistics */
1065 SCIP_TREE* tree, /**< branch and bound tree */
1066 SCIP_LP* lp, /**< current LP data */
1067 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
1068 )
1069{
1070 SCIP_NODE* focusnode;
1071 SCIP_VAR** lpcands;
1072 SCIP_Real* lpcandsfrac;
1073 SCIP_Real estimate;
1074 int nlpcands;
1075 int i;
1076
1077 /* estimate is only available if LP was solved to optimality */
1079 return SCIP_OKAY;
1080
1081 focusnode = SCIPtreeGetFocusNode(tree);
1082 assert(focusnode != NULL);
1083
1084 /* get the fractional variables */
1085 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, &lpcands, NULL, &lpcandsfrac, &nlpcands, NULL, NULL) );
1086
1087 /* calculate the estimate: lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) */
1088 estimate = SCIPnodeGetLowerbound(focusnode);
1089
1090 /* an infinite lower bound implies an infinite estimate */
1091 if( SCIPsetIsInfinity(set, estimate) )
1092 {
1093 SCIPnodeSetEstimate(focusnode, set, estimate);
1094 return SCIP_OKAY;
1095 }
1096
1097 for( i = 0; i < nlpcands; ++i )
1098 {
1099 SCIP_Real pscdown;
1100 SCIP_Real pscup;
1101
1102 pscdown = SCIPvarGetPseudocost(lpcands[i], stat, 0.0-lpcandsfrac[i]);
1103 pscup = SCIPvarGetPseudocost(lpcands[i], stat, 1.0-lpcandsfrac[i]);
1104 estimate += MIN(pscdown, pscup);
1105 }
1106 SCIPnodeSetEstimate(focusnode, set, estimate);
1107
1108 return SCIP_OKAY;
1109}
1110
1111/** puts all constraints with initial flag TRUE into the LP */
1113 BMS_BLKMEM* blkmem, /**< block memory buffers */
1114 SCIP_SET* set, /**< global SCIP settings */
1115 SCIP_SEPASTORE* sepastore, /**< separation storage */
1116 SCIP_CUTPOOL* cutpool, /**< global cutpool */
1117 SCIP_STAT* stat, /**< dynamic problem statistics */
1118 SCIP_PROB* transprob, /**< transformed problem */
1119 SCIP_PROB* origprob, /**< original problem */
1120 SCIP_TREE* tree, /**< branch and bound tree */
1121 SCIP_REOPT* reopt, /**< reoptimization data structure */
1122 SCIP_LP* lp, /**< LP data */
1123 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1124 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1125 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1126 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1127 SCIP_Bool root, /**< is this the initial root LP? */
1128 SCIP_Bool firstsubtreeinit, /**< is this the first call in the current subtree after jumping through the tree? */
1129 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1130 )
1131{
1132 int h;
1133
1134 assert(set != NULL);
1135 assert(lp != NULL);
1136 assert(cutoff != NULL);
1137
1138 *cutoff = FALSE;
1139
1140 /* inform separation storage, that LP is now filled with initial data */
1141 SCIPsepastoreStartInitialLP(sepastore);
1142
1143 /* add LP relaxations of all initial constraints to LP */
1144 SCIPsetDebugMsg(set, "init LP: initial rows\n");
1145 for( h = 0; h < set->nconshdlrs && !(*cutoff); ++h )
1146 {
1147 SCIP_CALL( SCIPconshdlrInitLP(set->conshdlrs[h], blkmem, set, stat, tree, firstsubtreeinit, cutoff) );
1148 }
1149
1150 if( set->reopt_enable && set->reopt_usecuts && firstsubtreeinit && !(*cutoff) )
1151 {
1152 /* add stored cuts from last reoptimization run */
1153 SCIP_CALL( SCIPreoptApplyCuts(reopt, tree->focusnode, sepastore, cutpool, blkmem, set, stat, eventqueue,
1154 eventfilter, lp, root) );
1155 }
1156
1157 if( !(*cutoff) )
1158 {
1159 /* apply cuts */
1160 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
1161 eventqueue, eventfilter, cliquetable, root, SCIP_EFFICIACYCHOICE_LP, cutoff) );
1162 }
1163 else
1164 {
1165 /* the current node will be cut off; we clear the sepastore */
1166 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
1167 }
1168
1169 /* inform separation storage, that initial LP setup is now finished */
1170 SCIPsepastoreEndInitialLP(sepastore);
1171
1172 return SCIP_OKAY;
1173}
1174
1175/** constructs the initial LP of the current node */
1176static
1178 BMS_BLKMEM* blkmem, /**< block memory buffers */
1179 SCIP_SET* set, /**< global SCIP settings */
1180 SCIP_STAT* stat, /**< dynamic problem statistics */
1181 SCIP_PROB* transprob, /**< transformed problem */
1182 SCIP_PROB* origprob, /**< original problem */
1183 SCIP_TREE* tree, /**< branch and bound tree */
1184 SCIP_REOPT* reopt, /**< reoptimization data structure */
1185 SCIP_LP* lp, /**< LP data */
1186 SCIP_PRICESTORE* pricestore, /**< pricing storage */
1187 SCIP_SEPASTORE* sepastore, /**< separation storage */
1188 SCIP_CUTPOOL* cutpool, /**< global cut pool */
1189 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1190 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1191 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1192 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1193 SCIP_Bool root, /**< is this the initial root LP? */
1194 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1195 )
1196{
1197 SCIP_VAR* var;
1198 int oldnvars = 0;
1199 int v;
1200
1201 assert(set != NULL);
1202 assert(transprob != NULL);
1203 assert(lp != NULL);
1204 assert(cutoff != NULL);
1205
1206 *cutoff = FALSE;
1207
1208 /* at the root node, we have to add the initial variables as columns */
1209 if( root )
1210 {
1211 assert(SCIPlpGetNCols(lp) == 0);
1212 assert(SCIPlpGetNRows(lp) == 0);
1213
1214 /* store number of variables for later */
1215 oldnvars = transprob->nvars;
1216
1217 /* inform pricing storage, that LP is now filled with initial data */
1218 SCIPpricestoreStartInitialLP(pricestore);
1219
1220 /* add all initial variables to LP */
1221 SCIPsetDebugMsg(set, "init LP: initial columns\n");
1222 for( v = 0; v < transprob->nvars; ++v )
1223 {
1224 var = transprob->vars[v];
1225 assert(SCIPvarGetProbindex(var) >= 0);
1226
1227 if( SCIPvarIsInitial(var) )
1228 {
1229 SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, 0.0, TRUE) );
1230
1231 /* check for empty domains (necessary if no presolving was performed) */
1233 {
1234 *cutoff = TRUE;
1235 break;
1236 }
1237 }
1238 }
1239
1240 assert(lp->nremovablecols == 0);
1241 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) );
1242 assert(lp->nremovablerows == 0);
1243
1244 /* inform pricing storage, that initial LP setup is now finished */
1245 SCIPpricestoreEndInitialLP(pricestore);
1246
1247 if( *cutoff )
1248 return SCIP_OKAY;
1249 }
1250
1251 /* put all initial constraints into the LP */
1252 /* @todo check whether we jumped through the tree */
1253 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
1254 eventfilter, cliquetable, root, TRUE, cutoff) );
1255
1256 if( *cutoff )
1257 return SCIP_OKAY;
1258
1259 /* putting all initial constraints into the LP might have added new variables */
1260 if( root && transprob->nvars > oldnvars )
1261 {
1262 /* inform pricing storage, that LP is now filled with initial data */
1263 SCIPpricestoreStartInitialLP(pricestore);
1264
1265 /* check all initial variables */
1266 for( v = 0; v < transprob->nvars; ++v )
1267 {
1268 var = transprob->vars[v];
1269 assert(SCIPvarGetProbindex(var) >= 0);
1270
1272 {
1273 SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, 0.0, TRUE) );
1274
1275 /* check for empty domains (necessary if no presolving was performed) */
1277 {
1278 *cutoff = TRUE;
1279 break;
1280 }
1281 }
1282 }
1283
1284 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) );
1285
1286 /* inform pricing storage, that initial LP setup is now finished */
1287 SCIPpricestoreEndInitialLP(pricestore);
1288 }
1289
1290 return SCIP_OKAY;
1291}
1292
1293/** constructs the LP of the current node, but does not load the LP state and warmstart information */
1295 BMS_BLKMEM* blkmem, /**< block memory buffers */
1296 SCIP_SET* set, /**< global SCIP settings */
1297 SCIP_STAT* stat, /**< dynamic problem statistics */
1298 SCIP_PROB* transprob, /**< transformed problem */
1299 SCIP_PROB* origprob, /**< original problem */
1300 SCIP_TREE* tree, /**< branch and bound tree */
1301 SCIP_REOPT* reopt, /**< reoptimization data structure */
1302 SCIP_LP* lp, /**< LP data */
1303 SCIP_PRICESTORE* pricestore, /**< pricing storage */
1304 SCIP_SEPASTORE* sepastore, /**< separation storage */
1305 SCIP_CUTPOOL* cutpool, /**< global cutpool */
1306 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1307 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1308 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1309 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1310 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
1311 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1312 )
1313{
1314 SCIP_Bool initroot = FALSE;
1315
1316 assert(tree != NULL);
1317 assert(cutoff != NULL);
1318
1319 *cutoff = FALSE;
1320
1322 {
1323 /* inform separation storage, that LP is now filled with initial data */
1324 SCIPsepastoreStartInitialLP(sepastore);
1325
1326 if( tree->correctlpdepth >= 0 )
1327 {
1328 int i;
1329
1330 for( i = tree->pathnlprows[tree->correctlpdepth]; i < lp->nrows; ++i )
1331 {
1332 /* keep all active global cuts that where applied in the previous node in the lp */
1333 if( !lp->rows[i]->local && lp->rows[i]->age == 0 )
1334 {
1335 lp->rows[i]->fromcutpool = TRUE; /* this has no effect inside initial LP, but is set for consistency */
1336 SCIP_CALL( SCIPsepastoreAddCut(sepastore, blkmem, set, stat, eventqueue, eventfilter, lp, lp->rows[i],
1337 TRUE, (SCIPtreeGetCurrentDepth(tree) == 0), cutoff) );
1338 }
1339 }
1340 }
1341
1342 if( !(*cutoff) )
1343 {
1344 /* load the LP into the solver and load the LP state */
1345 SCIPsetDebugMsg(set, "loading LP\n");
1346 SCIP_CALL( SCIPtreeLoadLP(tree, blkmem, set, eventqueue, eventfilter, lp, &initroot) );
1347 assert(initroot || SCIPnodeGetDepth(SCIPtreeGetFocusNode(tree)) > 0);
1349
1350 /* apply cuts */
1351 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
1352 eventqueue, eventfilter, cliquetable, (SCIPtreeGetCurrentDepth(tree) == 0), SCIP_EFFICIACYCHOICE_LP, cutoff) );
1353 }
1354 else
1355 {
1356 /* the current node will be cut off; we clear the sepastore */
1357 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
1358 }
1359
1360 /* inform separation storage, that initial LP setup is now finished */
1361 SCIPsepastoreEndInitialLP(sepastore);
1362
1363 if( !(*cutoff) )
1364 {
1365 /* setup initial LP relaxation of node */
1366 SCIP_CALL( initLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, pricestore, sepastore, cutpool, branchcand,
1367 eventqueue, eventfilter, cliquetable, initroot, cutoff) );
1368 }
1369 }
1370 else if( newinitconss )
1371 {
1372 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob,
1373 origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE,
1374 cutoff) );
1375 }
1376
1377 return SCIP_OKAY;
1378}
1379
1380/** updates the primal ray stored in primal data
1381 * clears previously stored primal ray, if existing and there was no LP error
1382 * stores current primal ray, if LP is unbounded and there has been no error
1383 */
1384static
1386 BMS_BLKMEM* blkmem, /**< block memory buffers */
1387 SCIP_SET* set, /**< global SCIP settings */
1388 SCIP_STAT* stat, /**< dynamic problem statistics */
1389 SCIP_PROB* prob, /**< transformed problem after presolve */
1390 SCIP_PRIMAL* primal, /**< primal data */
1391 SCIP_TREE* tree, /**< branch and bound tree */
1392 SCIP_LP* lp, /**< LP data */
1393 SCIP_Bool lperror /**< has there been an LP error? */
1394 )
1395{
1396 assert(blkmem != NULL);
1397 assert(set != NULL);
1398 assert(stat != NULL);
1399 assert(prob != NULL);
1400 assert(primal != NULL);
1401 assert(tree != NULL);
1402 assert(lp != NULL);
1403
1404 if( lperror )
1405 return SCIP_OKAY;
1406
1407 /* clear previously stored primal ray, if any */
1408 if( primal->primalray != NULL )
1409 {
1410 SCIP_CALL( SCIPsolFree(&primal->primalray, blkmem, primal) );
1411 }
1412
1413 /* store unbounded ray, if LP is unbounded */
1415 {
1416 SCIP_VAR** vars;
1417 SCIP_Real* ray;
1418 int nvars;
1419 int i;
1420
1421 SCIPsetDebugMsg(set, "LP is unbounded, store primal ray\n");
1422
1423 vars = prob->vars;
1424 nvars = prob->nvars;
1425
1426 /* get buffer memory for storing the ray and load the ray values into it */
1427 SCIP_CALL( SCIPsetAllocBufferArray(set, &ray, nvars) );
1428 BMSclearMemoryArray(ray, nvars);
1429 SCIP_CALL( SCIPlpGetPrimalRay(lp, set, ray) );
1430
1431 /* create solution to store the primal ray in */
1432 assert(primal->primalray == NULL);
1433 SCIP_CALL( SCIPsolCreate(&primal->primalray, blkmem, set, stat, primal, tree, NULL) );
1434
1435 /* set values of all active variable in the solution that represents the primal ray */
1436 for( i = 0; i < nvars; i++ )
1437 {
1438 SCIP_CALL( SCIPsolSetVal(primal->primalray, set, stat, tree, vars[i], ray[i]) );
1439 }
1440
1441 SCIPdebug( SCIP_CALL( SCIPprintRay(set->scip, primal->primalray, NULL, FALSE) ) );
1442
1443 /* free memory for buffering the ray values */
1445 }
1446
1447 return SCIP_OKAY;
1448}
1449
1450/** load and solve the initial LP of a node */
1451static
1453 BMS_BLKMEM* blkmem, /**< block memory buffers */
1454 SCIP_SET* set, /**< global SCIP settings */
1455 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1456 SCIP_STAT* stat, /**< dynamic problem statistics */
1457 SCIP_PROB* transprob, /**< transformed problem after presolve */
1458 SCIP_PROB* origprob, /**< original problem */
1459 SCIP_PRIMAL* primal, /**< primal data */
1460 SCIP_TREE* tree, /**< branch and bound tree */
1461 SCIP_REOPT* reopt, /**< reoptimization data structure */
1462 SCIP_LP* lp, /**< LP data */
1463 SCIP_PRICESTORE* pricestore, /**< pricing storage */
1464 SCIP_SEPASTORE* sepastore, /**< separation storage */
1465 SCIP_CUTPOOL* cutpool, /**< global cutpool */
1466 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1467 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1468 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1469 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1470 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
1471 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
1472 SCIP_Bool* lperror /**< pointer to store whether an unresolved error in LP solving occured */
1473 )
1474{
1475 /* initializing variables for compiler warnings, which are not correct */
1476 SCIP_Real starttime = 0.0;
1477 SCIP_Longint nlpiterations = 0;
1478 SCIP_NODE* focusnode;
1479
1480 assert(stat != NULL);
1481 assert(tree != NULL);
1482 assert(lp != NULL);
1483 assert(cutoff != NULL);
1484 assert(lperror != NULL);
1485 assert(SCIPtreeGetFocusNode(tree) != NULL);
1487
1488 *cutoff = FALSE;
1489 *lperror = FALSE;
1490
1491 /* load the LP into the solver */
1492 SCIP_CALL( SCIPconstructCurrentLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, pricestore, sepastore, cutpool,
1493 branchcand, eventqueue, eventfilter, cliquetable, newinitconss, cutoff) );
1494
1495 if( *cutoff )
1496 return SCIP_OKAY;
1497
1498 /* load the LP state */
1499 SCIP_CALL( SCIPtreeLoadLPState(tree, blkmem, set, transprob, stat, eventqueue, lp) );
1500
1501 focusnode = SCIPtreeGetFocusNode(tree);
1502
1503 /* store current LP iteration count and solving time if we are at the root node */
1504 if( focusnode->depth == 0 )
1505 {
1506 nlpiterations = stat->nlpiterations;
1507 starttime = SCIPclockGetTime(stat->solvingtime);
1508 }
1509
1510 /* solve initial LP */
1511 SCIPsetDebugMsg(set, "node: solve initial LP\n");
1512 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
1513 SCIPnodeGetDepth(SCIPtreeGetFocusNode(tree)) == 0 ? set->lp_rootiterlim : set->lp_iterlim, TRUE, TRUE, FALSE, lperror) );
1514 assert(lp->flushed);
1515 assert(lp->solved || *lperror);
1516
1517 /* save time for very first LP in root node */
1518 if ( stat->nnodelps == 0 && focusnode->depth == 0 )
1519 {
1520 stat->firstlptime = SCIPclockGetTime(stat->solvingtime) - starttime;
1521 }
1522
1523 /* remove previous primal ray, store new one if LP is unbounded */
1524 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
1525
1526 if( !(*lperror) )
1527 {
1528 /* cppcheck-suppress unassignedVariable */
1529 SCIP_EVENT event;
1530
1532 {
1533 /* issue FIRSTLPSOLVED event */
1536 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
1537 }
1538
1539 /* update pseudo cost values for integer variables (always) and for continuous variables (if not delayed) */
1540 SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, TRUE, !set->branch_delaypscost) );
1541
1542 /* update lower bound of current node w.r.t. initial lp */
1543 assert(!(*cutoff));
1546 && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
1547 {
1548 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
1549
1550 /* if this is the first LP solved at the root, store its iteration count and solution value */
1551 if( stat->nnodelps == 0 && focusnode->depth == 0 )
1552 {
1553 SCIP_Real lowerbound;
1554
1555 assert(stat->nrootfirstlpiterations == 0);
1556 stat->nrootfirstlpiterations = stat->nlpiterations - nlpiterations;
1557
1558 if( set->misc_exactsolve )
1559 {
1560 SCIP_CALL( SCIPlpGetProvedLowerbound(lp, set, &lowerbound) );
1561 }
1562 else
1563 lowerbound = SCIPlpGetObjval(lp, set, transprob);
1564
1565 stat->firstlpdualbound = SCIPprobExternObjval(transprob, origprob, set, lowerbound);
1566 }
1567 }
1568 }
1569
1570 return SCIP_OKAY;
1571}
1572
1573/** makes sure the LP is flushed and solved */
1574static
1576 BMS_BLKMEM* blkmem, /**< block memory buffers */
1577 SCIP_SET* set, /**< global SCIP settings */
1578 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1579 SCIP_STAT* stat, /**< dynamic problem statistics */
1580 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1581 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1582 SCIP_PROB* prob, /**< transformed problem after presolve */
1583 SCIP_PRIMAL* primal, /**< primal data */
1584 SCIP_TREE* tree, /**< branch and bound tree */
1585 SCIP_LP* lp, /**< LP data */
1586 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
1587 SCIP_Bool* mustsepa, /**< pointer to store TRUE if additional separation rounds should be performed */
1588 SCIP_Bool* mustprice /**< pointer to store TRUE if additional pricing rounds should be performed */
1589 )
1590{
1591 assert(lp != NULL);
1592 assert(lperror != NULL);
1593 assert(mustsepa != NULL);
1594 assert(mustprice != NULL);
1595
1596 /* if bound changes were applied in the separation round, we have to resolve the LP */
1597 if( !lp->flushed )
1598 {
1599 /* solve LP (with dual simplex) */
1600 SCIPsetDebugMsg(set, "separation: resolve LP\n");
1601 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, prob, set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
1602 assert(lp->flushed);
1603 assert(lp->solved || *lperror);
1604 *mustsepa = TRUE;
1605 *mustprice = TRUE;
1606
1607 /* remove previous primal ray, store new one if LP is unbounded */
1608 SCIP_CALL( updatePrimalRay(blkmem, set, stat, prob, primal, tree, lp, *lperror) );
1609 }
1610
1611 return SCIP_OKAY;
1612}
1613
1614/** applies one round of LP separation */
1615static
1617 BMS_BLKMEM* blkmem, /**< block memory buffers */
1618 SCIP_SET* set, /**< global SCIP settings */
1619 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1620 SCIP_STAT* stat, /**< dynamic problem statistics */
1621 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1622 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1623 SCIP_PROB* prob, /**< transformed problem after presolve */
1624 SCIP_PRIMAL* primal, /**< primal data */
1625 SCIP_TREE* tree, /**< branch and bound tree */
1626 SCIP_LP* lp, /**< LP data */
1627 SCIP_SEPASTORE* sepastore, /**< separation storage */
1628 int actdepth, /**< current depth in the tree */
1629 SCIP_Real bounddist, /**< current relative distance of local dual bound to global dual bound */
1630 SCIP_Bool allowlocal, /**< should the separators be asked to separate local cuts */
1631 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
1632 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
1633 SCIP_Bool* enoughcuts, /**< pointer to store whether enough cuts have been found this round */
1634 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
1635 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
1636 SCIP_Bool* mustsepa, /**< pointer to store TRUE if additional separation rounds should be performed */
1637 SCIP_Bool* mustprice /**< pointer to store TRUE if additional pricing rounds should be performed */
1638 )
1639{
1640 SCIP_RESULT result;
1641 int i;
1642 SCIP_Bool consadded;
1643 SCIP_Bool root;
1644
1645 assert(set != NULL);
1646 assert(lp != NULL);
1647 assert(set->conshdlrs_sepa != NULL);
1648 assert(delayed != NULL);
1649 assert(enoughcuts != NULL);
1650 assert(cutoff != NULL);
1651 assert(lperror != NULL);
1652
1653 root = (actdepth == 0);
1654 *delayed = FALSE;
1656 *enoughcuts = TRUE;
1658 *enoughcuts = FALSE;
1659 else
1660 *enoughcuts = (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
1662 *lperror = FALSE;
1663 consadded = FALSE;
1664
1665 SCIPsetDebugMsg(set, "calling separators on LP solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed);
1666
1667 /* sort separators by priority */
1669
1670 /* call LP separators with nonnegative priority */
1671 for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1673 ++i )
1674 {
1675#ifndef NDEBUG
1676 size_t nusedbuffer = BMSgetNUsedBufferMemory(SCIPbuffer(set->scip));
1677#endif
1678
1679 if( SCIPsepaGetPriority(set->sepas[i]) < 0 )
1680 continue;
1681
1682 if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) )
1683 continue;
1684
1685 SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n",
1686 SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i]));
1687 SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) );
1688#ifndef NDEBUG
1689 if( BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)) > nusedbuffer )
1690 {
1691 SCIPerrorMessage("Buffer not completely freed after executing separator <%s>\n", SCIPsepaGetName(set->sepas[i]));
1692 SCIPABORT();
1693 }
1694#endif
1695 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1696 consadded = consadded || (result == SCIP_CONSADDED);
1698 *enoughcuts = TRUE;
1700 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND);
1701 else
1702 {
1703 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
1705 || (result == SCIP_NEWROUND);
1706 }
1707 *delayed = *delayed || (result == SCIP_DELAYED);
1708
1709 if( !(*cutoff) )
1710 {
1711 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1712 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1713 }
1714 else
1715 {
1716 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1717 }
1718
1719 /* if we work off the delayed separators, we stop immediately if a cut was found */
1720 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1721 {
1722 SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i]));
1723 *delayed = TRUE;
1724 return SCIP_OKAY;
1725 }
1726 }
1727
1728 /* try separating constraints of the constraint handlers */
1729 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1731 ++i )
1732 {
1733 if( onlydelayed && !SCIPconshdlrWasLPSeparationDelayed(set->conshdlrs_sepa[i]) )
1734 continue;
1735
1736 SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n",
1737 SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i]));
1738 SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed,
1739 &result) );
1740
1741 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1742 consadded = consadded || (result == SCIP_CONSADDED);
1744 *enoughcuts = TRUE;
1746 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND);
1747 else
1748 {
1749 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
1751 || (result == SCIP_NEWROUND);
1752 }
1753 *delayed = *delayed || (result == SCIP_DELAYED);
1754
1755 if( !(*cutoff) )
1756 {
1757 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1758 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1759 }
1760 else
1761 {
1762 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1763 }
1764
1765 /* if we work off the delayed separators, we stop immediately if a cut was found */
1766 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1767 {
1768 SCIPsetDebugMsg(set, " -> delayed constraint handler <%s> found a cut\n",
1769 SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1770 *delayed = TRUE;
1771 return SCIP_OKAY;
1772 }
1773 }
1774
1775 /* call LP separators with negative priority */
1776 for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1778 ++i )
1779 {
1780 if( SCIPsepaGetPriority(set->sepas[i]) >= 0 )
1781 continue;
1782
1783 if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) )
1784 continue;
1785
1786 SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n",
1787 SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i]));
1788 SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) );
1789
1790 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1791 consadded = consadded || (result == SCIP_CONSADDED);
1793 *enoughcuts = TRUE;
1795 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND);
1796 else
1797 {
1798 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
1800 || (result == SCIP_NEWROUND);
1801 }
1802 *delayed = *delayed || (result == SCIP_DELAYED);
1803
1804 if( !(*cutoff) )
1805 {
1806 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1807 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1808 }
1809 else
1810 {
1811 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1812 }
1813
1814 /* if we work off the delayed separators, we stop immediately if a cut was found */
1815 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1816 {
1817 SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i]));
1818 *delayed = TRUE;
1819 return SCIP_OKAY;
1820 }
1821 }
1822
1823 /* process the constraints that were added during this separation round */
1824 while( consadded )
1825 {
1826 assert(!onlydelayed);
1827 consadded = FALSE;
1828
1829 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1831 ++i )
1832 {
1833 SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n",
1834 SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i]));
1835 SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed,
1836 &result) );
1837
1838 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1839 consadded = consadded || (result == SCIP_CONSADDED);
1841 *enoughcuts = TRUE;
1843 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND);
1844 else
1845 {
1846 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
1848 || (result == SCIP_NEWROUND);
1849 }
1850 *delayed = *delayed || (result == SCIP_DELAYED);
1851
1852 if( !(*cutoff) )
1853 {
1854 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1855 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1856 }
1857 else
1858 {
1859 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1860 }
1861 }
1862 }
1863
1864 SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, lpflushed=%u, cutoff=%u\n",
1865 *delayed, *enoughcuts, lp->flushed, *cutoff);
1866
1867 return SCIP_OKAY;
1868}
1869
1870/** applies one round of separation on the given primal solution */
1871static
1873 BMS_BLKMEM* blkmem, /**< block memory buffers */
1874 SCIP_SET* set, /**< global SCIP settings */
1875 SCIP_STAT* stat, /**< dynamic problem statistics */
1876 SCIP_SEPASTORE* sepastore, /**< separation storage */
1877 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
1878 int actdepth, /**< current depth in the tree */
1879 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
1880 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
1881 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
1882 SCIP_Bool* enoughcuts, /**< pointer to store whether enough cuts have been found this round */
1883 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1884 )
1885{
1886 SCIP_RESULT result;
1887 int i;
1888 SCIP_Bool consadded;
1889 SCIP_Bool root;
1890
1891 assert(set != NULL);
1892 assert(set->conshdlrs_sepa != NULL);
1893 assert(delayed != NULL);
1894 assert(enoughcuts != NULL);
1895 assert(cutoff != NULL);
1896
1897 *delayed = FALSE;
1898 *enoughcuts = FALSE;
1899 consadded = FALSE;
1900 root = (actdepth == 0);
1901
1902 SCIPsetDebugMsg(set, "calling separators on primal solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed);
1903
1904 /* sort separators by priority */
1906
1907 /* call separators with nonnegative priority */
1908 for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1909 {
1910 if( SCIPsepaGetPriority(set->sepas[i]) < 0 )
1911 continue;
1912
1913 if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) )
1914 continue;
1915
1916 SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) );
1917 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1918 consadded = consadded || (result == SCIP_CONSADDED);
1920 *enoughcuts = TRUE;
1922 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND);
1923 else
1924 {
1925 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
1927 || (result == SCIP_NEWROUND);
1928 }
1929 *delayed = *delayed || (result == SCIP_DELAYED);
1930 if( *cutoff )
1931 {
1932 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1933 }
1934
1935 /* if we work off the delayed separators, we stop immediately if a cut was found */
1936 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1937 {
1938 *delayed = TRUE;
1939 return SCIP_OKAY;
1940 }
1941 }
1942
1943 /* try separating constraints of the constraint handlers */
1944 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1945 {
1946 if( onlydelayed && !SCIPconshdlrWasSolSeparationDelayed(set->conshdlrs_sepa[i]) )
1947 continue;
1948
1949 SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed,
1950 &result) );
1951 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1952 consadded = consadded || (result == SCIP_CONSADDED);
1954 *enoughcuts = TRUE;
1956 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND);
1957 else
1958 {
1959 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
1961 || (result == SCIP_NEWROUND);
1962 }
1963 *delayed = *delayed || (result == SCIP_DELAYED);
1964 if( *cutoff )
1965 {
1966 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n",
1967 SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1968 }
1969
1970 /* if we work off the delayed separators, we stop immediately if a cut was found */
1971 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1972 {
1973 *delayed = TRUE;
1974 return SCIP_OKAY;
1975 }
1976 }
1977
1978 /* call separators with negative priority */
1979 for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1980 {
1981 if( SCIPsepaGetPriority(set->sepas[i]) >= 0 )
1982 continue;
1983
1984 if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) )
1985 continue;
1986
1987 SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) );
1988 *cutoff = *cutoff || (result == SCIP_CUTOFF);
1989 consadded = consadded || (result == SCIP_CONSADDED);
1991 *enoughcuts = TRUE;
1993 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND);
1994 else
1995 {
1996 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
1998 || (result == SCIP_NEWROUND);
1999 }
2000 *delayed = *delayed || (result == SCIP_DELAYED);
2001 if( *cutoff )
2002 {
2003 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
2004 }
2005
2006 /* if we work off the delayed separators, we stop immediately if a cut was found */
2007 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
2008 {
2009 *delayed = TRUE;
2010 return SCIP_OKAY;
2011 }
2012 }
2013
2014 /* process the constraints that were added during this separation round */
2015 while( consadded )
2016 {
2017 assert(!onlydelayed);
2018 consadded = FALSE;
2019
2020 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
2021 {
2022 SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed, &result) );
2023 *cutoff = *cutoff || (result == SCIP_CUTOFF);
2024 consadded = consadded || (result == SCIP_CONSADDED);
2026 *enoughcuts = TRUE;
2028 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND);
2029 else
2030 {
2031 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
2033 || (result == SCIP_NEWROUND);
2034 }
2035 *delayed = *delayed || (result == SCIP_DELAYED);
2036 if( *cutoff )
2037 {
2038 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n",
2039 SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
2040 }
2041 }
2042 }
2043
2044 SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, cutoff=%u\n",
2045 *delayed, *enoughcuts, *cutoff);
2046
2047 return SCIP_OKAY;
2048}
2049
2050/** applies one round of separation on the given primal solution or on the LP solution */
2052 BMS_BLKMEM* blkmem, /**< block memory buffers */
2053 SCIP_SET* set, /**< global SCIP settings */
2054 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2055 SCIP_STAT* stat, /**< dynamic problem statistics */
2056 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2057 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
2058 SCIP_PROB* prob, /**< transformed problem after presolve */
2059 SCIP_PRIMAL* primal, /**< primal data */
2060 SCIP_TREE* tree, /**< branch and bound tree */
2061 SCIP_LP* lp, /**< LP data */
2062 SCIP_SEPASTORE* sepastore, /**< separation storage */
2063 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
2064 int actdepth, /**< current depth in the tree */
2065 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
2066 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
2067 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
2068 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
2069 )
2070{
2071 SCIP_Bool enoughcuts;
2072
2073 assert(delayed != NULL);
2074 assert(cutoff != NULL);
2075
2076 *delayed = FALSE;
2077 *cutoff = FALSE;
2078 enoughcuts = FALSE;
2079
2080 if( sol == NULL )
2081 {
2082 SCIP_Bool lperror;
2083 SCIP_Bool mustsepa;
2084 SCIP_Bool mustprice;
2085
2086 /* apply a separation round on the LP solution */
2087 lperror = FALSE;
2088 mustsepa = FALSE;
2089 mustprice = FALSE;
2090 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, sepastore, \
2091 actdepth, 0.0, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff, \
2092 &lperror, &mustsepa, &mustprice) );
2093 }
2094 else
2095 {
2096 /* apply a separation round on the given primal solution */
2097 SCIP_CALL( separationRoundSol(blkmem, set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff) );
2098 }
2099
2100 return SCIP_OKAY;
2101}
2102
2103/** solves the current LP completely with pricing in new variables */
2105 BMS_BLKMEM* blkmem, /**< block memory buffers */
2106 SCIP_SET* set, /**< global SCIP settings */
2107 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2108 SCIP_STAT* stat, /**< dynamic problem statistics */
2109 SCIP_PROB* transprob, /**< transformed problem */
2110 SCIP_PROB* origprob, /**< original problem */
2111 SCIP_PRIMAL* primal, /**< primal data */
2112 SCIP_TREE* tree, /**< branch and bound tree */
2113 SCIP_REOPT* reopt, /**< reoptimization data structure */
2114 SCIP_LP* lp, /**< LP data */
2115 SCIP_PRICESTORE* pricestore, /**< pricing storage */
2116 SCIP_SEPASTORE* sepastore, /**< separation storage */
2117 SCIP_CUTPOOL* cutpool, /**< global cutpool */
2118 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2119 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2120 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
2121 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2122 SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */
2123 SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */
2124 int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit);
2125 * a finite limit means that the LP might not be solved to optimality! */
2126 int* npricedcolvars, /**< pointer to store number of column variables after problem vars were priced */
2127 SCIP_Bool* mustsepa, /**< pointer to store TRUE if a separation round should follow */
2128 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
2129 SCIP_Bool* aborted /**< pointer to store whether the pricing was aborted and the lower bound must
2130 * not be used */
2131 )
2132{
2133 SCIP_NODE* currentnode;
2134 int npricerounds;
2135 SCIP_Bool mustprice;
2136 SCIP_Bool cutoff;
2137 SCIP_Bool unbounded;
2138
2139 assert(transprob != NULL);
2140 assert(lp != NULL);
2141 assert(lp->flushed);
2142 assert(lp->solved);
2143 assert(npricedcolvars != NULL);
2144 assert(mustsepa != NULL);
2145 assert(lperror != NULL);
2146 assert(aborted != NULL);
2147
2148 currentnode = SCIPtreeGetCurrentNode(tree);
2149 assert(currentnode == SCIPtreeGetFocusNode(tree) || SCIPtreeProbing(tree));
2150 *npricedcolvars = transprob->ncolvars;
2151 *lperror = FALSE;
2152 *aborted = FALSE;
2153
2154 /* if the LP is unbounded, we don't need to price */
2155 mustprice = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL
2158
2159 /* if all the variables are already in the LP, we don't need to price */
2160 mustprice = mustprice && !SCIPprobAllColsInLP(transprob, set, lp);
2161
2162 /* check if infinite number of pricing rounds should be used */
2163 if( maxpricerounds == -1 )
2164 maxpricerounds = INT_MAX;
2165
2166 /* pricing (has to be done completely to get a valid lower bound) */
2167 npricerounds = 0;
2168 while( !(*lperror) && mustprice && npricerounds < maxpricerounds )
2169 {
2170 SCIP_Bool enoughvars;
2171 SCIP_RESULT result;
2172 SCIP_Real lb;
2173 SCIP_Bool foundsol;
2174 SCIP_Bool stopearly;
2175 SCIP_Bool stoppricing;
2176 int p;
2177
2178 assert(lp->flushed);
2179 assert(lp->solved);
2181
2182 /* check if pricing loop should be aborted */
2183 if( SCIPsolveIsStopped(set, stat, FALSE) )
2184 {
2185 /* do not print the warning message if we stopped because the problem is solved */
2187 SCIPmessagePrintWarning(messagehdlr, "pricing has been interrupted -- LP of current node is invalid\n");
2188
2189 *aborted = TRUE;
2190 break;
2191 }
2192
2193 /* call primal heuristics which are callable during pricing */
2194 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGPRICINGLOOP,
2195 FALSE, &foundsol, &unbounded) );
2196
2197 /* price problem variables */
2198 SCIPsetDebugMsg(set, "problem variable pricing\n");
2199 assert(SCIPpricestoreGetNVars(pricestore) == 0);
2200 assert(SCIPpricestoreGetNBoundResets(pricestore) == 0);
2201 SCIP_CALL( SCIPpricestoreAddProbVars(pricestore, blkmem, set, stat, transprob, tree, lp, branchcand, eventqueue) );
2202 *npricedcolvars = transprob->ncolvars;
2203
2204 /* call external pricers to create additional problem variables */
2205 SCIPsetDebugMsg(set, "external variable pricing\n");
2206
2207 /* sort pricer algorithms by priority */
2209
2210 /* call external pricer algorithms, that are active for the current problem */
2211 enoughvars = (SCIPsetGetPriceMaxvars(set, pretendroot) == INT_MAX ?
2212 FALSE : SCIPpricestoreGetNVars(pricestore) >= SCIPsetGetPriceMaxvars(set, pretendroot) + 1);
2213 stoppricing = FALSE;
2214 for( p = 0; p < set->nactivepricers && !enoughvars; ++p )
2215 {
2216 SCIP_CALL( SCIPpricerExec(set->pricers[p], set, transprob, lp, pricestore, &lb, &stopearly, &result) );
2217 assert(result == SCIP_DIDNOTRUN || result == SCIP_SUCCESS);
2218 SCIPsetDebugMsg(set, "pricing: pricer %s returned result = %s, lowerbound = %f\n",
2219 SCIPpricerGetName(set->pricers[p]), (result == SCIP_DIDNOTRUN ? "didnotrun" : "success"), lb);
2220 enoughvars = enoughvars || (SCIPsetGetPriceMaxvars(set, pretendroot) == INT_MAX ?
2221 FALSE : SCIPpricestoreGetNVars(pricestore) >= SCIPsetGetPriceMaxvars(set, pretendroot) + 1);
2222 *aborted = ( (*aborted) || (result == SCIP_DIDNOTRUN) );
2223
2224 /* set stoppricing to TRUE, if the first pricer wants to stop pricing */
2225 if( p == 0 && stopearly )
2226 stoppricing = TRUE;
2227
2228 /* stoppricing only remains TRUE, if all other pricers want to stop pricing as well */
2229 if( stoppricing && !stopearly )
2230 stoppricing = FALSE;
2231
2232 /* update lower bound w.r.t. the lower bound given by the pricer */
2233 SCIPnodeUpdateLowerbound(currentnode, stat, set, tree, transprob, origprob, lb);
2234 SCIPsetDebugMsg(set, " -> new lower bound given by pricer %s: %g\n", SCIPpricerGetName(set->pricers[p]), lb);
2235 }
2236
2237 /* apply the priced variables to the LP */
2238 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) );
2239 assert(SCIPpricestoreGetNVars(pricestore) == 0);
2240 assert(!lp->flushed || lp->solved);
2241 mustprice = !lp->flushed || (transprob->ncolvars != *npricedcolvars);
2242 *mustsepa = *mustsepa || !lp->flushed;
2243
2244 /* after adding columns, the LP should be primal feasible such that the primal simplex is applicable;
2245 * if LP was infeasible, we have to use dual simplex
2246 */
2247 SCIPsetDebugMsg(set, "pricing: solve LP\n");
2248 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, TRUE, FALSE, lperror) );
2249 assert(lp->flushed);
2250 assert(lp->solved || *lperror);
2251
2252 /* reset bounds temporarily set by pricer to their original values */
2253 SCIPsetDebugMsg(set, "pricing: reset bounds\n");
2254 SCIP_CALL( SCIPpricestoreResetBounds(pricestore, blkmem, set, stat, lp, branchcand, eventqueue) );
2255 assert(SCIPpricestoreGetNVars(pricestore) == 0);
2256 assert(SCIPpricestoreGetNBoundResets(pricestore) == 0);
2257 assert(!lp->flushed || lp->solved || *lperror);
2258
2259 /* put all initial constraints into the LP */
2260 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2261 eventfilter, cliquetable, FALSE, FALSE, &cutoff) );
2262 assert(cutoff == FALSE);
2263
2264 mustprice = mustprice || !lp->flushed || (transprob->ncolvars != *npricedcolvars);
2265 *mustsepa = *mustsepa || !lp->flushed;
2266
2267 /* if all pricers wanted to stop pricing, do not do another pricing round (LP value is no valid dual bound in this case) */
2268 if( stoppricing )
2269 {
2270 SCIPsetDebugMsg(set, "pricing: stop pricing and perform early branching\n");
2271 mustprice = FALSE;
2272 *aborted = TRUE;
2273 }
2274
2275 /* solve LP again after resetting bounds and adding new initial constraints (with dual simplex) */
2276 SCIPsetDebugMsg(set, "pricing: solve LP after resetting bounds and adding new initial constraints\n");
2277 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) );
2278 assert(lp->flushed);
2279 assert(lp->solved || *lperror);
2280
2281 /* remove previous primal ray, store new one if LP is unbounded */
2282 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2283
2284 /* increase pricing round counter */
2285 stat->npricerounds++;
2286 npricerounds++;
2287
2288 /* display node information line */
2289 if( displayinfo && mustprice )
2290 {
2291 if( (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_FULL
2292 || ((SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH && npricerounds % 100 == 1) )
2293 {
2294 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
2295 }
2296 }
2297
2298 /* if the LP is unbounded, we can stop pricing */
2299 mustprice = mustprice &&
2303
2304 /* if the lower bound is already higher than the cutoff bound, we can stop pricing */
2305 mustprice = mustprice && SCIPsetIsLT(set, SCIPnodeGetLowerbound(currentnode), primal->cutoffbound);
2306 } /*lint !e438*/
2307 assert(lp->flushed);
2308 assert(lp->solved || *lperror);
2309
2310 *aborted = ( (*aborted) || (*lperror) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_NOTSOLVED
2311 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ERROR || npricerounds == maxpricerounds );
2312
2313 /* set information, whether the current lp is a valid relaxation of the current problem */
2314 SCIPlpSetIsRelax(lp, !(*aborted));
2315
2316 return SCIP_OKAY; /*lint !e438*/
2317}
2318
2319/** separates cuts of the cut pool */
2320static
2322 SCIP_CUTPOOL* cutpool, /**< cut pool */
2323 BMS_BLKMEM* blkmem, /**< block memory */
2324 SCIP_SET* set, /**< global SCIP settings */
2325 SCIP_STAT* stat, /**< problem statistics data */
2326 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2327 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
2328 SCIP_LP* lp, /**< current LP data */
2329 SCIP_SEPASTORE* sepastore, /**< separation storage */
2330 SCIP_Bool cutpoolisdelayed, /**< is the cutpool delayed (count cuts found)? */
2331 SCIP_Bool root, /**< are we at the root node? */
2332 int actdepth, /**< the depth of the focus node */
2333 SCIP_Bool* enoughcuts, /**< pointer to store if enough cuts were found in current separation round */
2334 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
2335 )
2336{
2337 if( (set->sepa_poolfreq == 0 && actdepth == 0)
2338 || (set->sepa_poolfreq > 0 && actdepth % set->sepa_poolfreq == 0) )
2339 {
2340 SCIP_RESULT result;
2341
2342 SCIP_CALL( SCIPcutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, NULL, cutpoolisdelayed, root, &result) );
2343 *cutoff = *cutoff || (result == SCIP_CUTOFF);
2345 *enoughcuts = TRUE;
2347 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND);
2348 else
2349 {
2350 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set,
2352 || (result == SCIP_NEWROUND);
2353 }
2354 }
2355
2356 return SCIP_OKAY;
2357}
2358
2359/** solve the current LP of a node with a price-and-cut loop */
2360static
2362 BMS_BLKMEM* blkmem, /**< block memory buffers */
2363 SCIP_SET* set, /**< global SCIP settings */
2364 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2365 SCIP_STAT* stat, /**< dynamic problem statistics */
2366 SCIP_MEM* mem, /**< block memory pools */
2367 SCIP_PROB* transprob, /**< transformed problem */
2368 SCIP_PROB* origprob, /**< original problem */
2369 SCIP_PRIMAL* primal, /**< primal data */
2370 SCIP_TREE* tree, /**< branch and bound tree */
2371 SCIP_REOPT* reopt, /**< reoptimization data structure */
2372 SCIP_LP* lp, /**< LP data */
2373 SCIP_PRICESTORE* pricestore, /**< pricing storage */
2374 SCIP_SEPASTORE* sepastore, /**< separation storage */
2375 SCIP_CUTPOOL* cutpool, /**< global cut pool */
2376 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
2377 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2378 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2379 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2380 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
2381 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2382 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2383 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
2384 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
2385 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
2386 SCIP_Bool* unbounded, /**< pointer to store whether an unbounded ray was found in the LP */
2387 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
2388 SCIP_Bool* pricingaborted /**< pointer to store whether the pricing was aborted and the lower bound must
2389 * not be used */
2390 )
2391{
2392 SCIP_NODE* focusnode;
2393 /* cppcheck-suppress unassignedVariable */
2394 SCIP_EVENT event;
2395 SCIP_LPSOLSTAT stalllpsolstat;
2396 SCIP_Real loclowerbound;
2397 SCIP_Real glblowerbound;
2398 SCIP_Real bounddist;
2399 SCIP_Real stalllpobjval;
2400 SCIP_Bool separate;
2401 SCIP_Bool mustprice;
2402 SCIP_Bool mustsepa;
2403 SCIP_Bool delayedsepa;
2404 SCIP_Bool root;
2405 SCIP_Bool allowlocal;
2406 int maxseparounds;
2407 int maxsepapartialrounds;
2408 int nsepastallrounds;
2409 int maxsepastallrounds;
2410 int stallnfracs;
2411 int actdepth;
2412 int npricedcolvars;
2413
2414 assert(set != NULL);
2415 assert(blkmem != NULL);
2416 assert(stat != NULL);
2417 assert(transprob != NULL);
2418 assert(tree != NULL);
2419 assert(lp != NULL);
2420 assert(pricestore != NULL);
2421 assert(sepastore != NULL);
2422 assert(cutpool != NULL);
2423 assert(delayedcutpool != NULL);
2424 assert(primal != NULL);
2425 assert(cutoff != NULL);
2426 assert(unbounded != NULL);
2427 assert(lperror != NULL);
2428
2429 focusnode = SCIPtreeGetFocusNode(tree);
2430 assert(focusnode != NULL);
2431 assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
2432 actdepth = SCIPnodeGetDepth(focusnode);
2433 root = (actdepth == 0);
2434
2435 /* check, if we want to separate at this node */
2436 loclowerbound = SCIPnodeGetLowerbound(focusnode);
2437 glblowerbound = SCIPtreeGetLowerbound(tree, set);
2438 assert(primal->cutoffbound > glblowerbound);
2439 bounddist = (loclowerbound - glblowerbound)/(primal->cutoffbound - glblowerbound);
2440 allowlocal = SCIPsetIsLE(set, bounddist, set->sepa_maxlocalbounddist);
2441 separate = (set->sepa_maxruns == -1 || stat->nruns < set->sepa_maxruns);
2442
2443 /* determine maximal number of separation rounds */
2444 maxseparounds = (root ? set->sepa_maxroundsroot : set->sepa_maxrounds);
2445 if( maxseparounds == -1 )
2446 maxseparounds = INT_MAX;
2447 if( stat->nruns > 1 && root && set->sepa_maxroundsrootsubrun >= 0 )
2448 maxseparounds = MIN(maxseparounds, set->sepa_maxroundsrootsubrun);
2449
2450 /* determine maximal number of partial rounds excluding delayed round */
2451 maxsepapartialrounds = INT_MAX;
2452 if( !fullseparation && set->sepa_maxaddrounds >= 0 )
2453 maxsepapartialrounds = stat->nseparounds + set->sepa_maxaddrounds;
2454
2455 /* determine maximal number of stalling rounds */
2456 maxsepastallrounds = root ? set->sepa_maxstallroundsroot : set->sepa_maxstallrounds;
2457 if( maxsepastallrounds == -1 )
2458 maxsepastallrounds = INT_MAX;
2459
2460 /* solve initial LP of price-and-cut loop */
2461 SCIPsetDebugMsg(set, "node: solve LP with price and cut\n");
2462 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2463 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2464 assert(lp->flushed);
2465 assert(lp->solved || *lperror);
2466
2467 /* remove previous primal ray, store new one if LP is unbounded */
2468 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2469
2470 /* price-and-cut loop */
2471 npricedcolvars = transprob->ncolvars;
2472 mustprice = TRUE;
2473 mustsepa = separate;
2474 delayedsepa = FALSE;
2475 *cutoff = FALSE;
2476 *unbounded = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY);
2477 nsepastallrounds = 0;
2478 stalllpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
2479 stalllpobjval = SCIP_REAL_MIN;
2480 stallnfracs = INT_MAX;
2481 lp->installing = FALSE;
2482 while( !(*cutoff) && !(*unbounded) && !(*lperror) && ( mustprice || mustsepa ) )
2483 {
2484 SCIPsetDebugMsg(set, "-------- node solving loop --------\n");
2485 assert(lp->flushed);
2486 assert(lp->solved);
2487
2488 /* solve the LP with pricing in new variables */
2489 while( mustprice && !(*lperror) )
2490 {
2491 SCIP_CALL( SCIPpriceLoop(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
2492 pricestore, sepastore, cutpool, branchcand, eventqueue, eventfilter, cliquetable, root, root, -1, &npricedcolvars,
2493 &mustsepa, lperror, pricingaborted) );
2494
2495 mustprice = FALSE;
2496
2497 assert(lp->flushed);
2498 assert(lp->solved || *lperror);
2499
2500 /* update lower bound w.r.t. the LP solution */
2501 if( !(*lperror) && !(*pricingaborted) && SCIPlpIsRelax(lp) )
2502 {
2503 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2504 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2505 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2506
2507 /* update node estimate */
2508 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2509
2510 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2511 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2512 }
2513 else
2514 {
2515 SCIPsetDebugMsg(set, " -> error solving LP or pricing aborted. keeping old bound: %g\n", SCIPnodeGetLowerbound(focusnode));
2516 }
2517
2518 /* display node information line for root node */
2519 if( root && (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH )
2520 {
2521 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
2522 }
2523
2524 if( !(*lperror) )
2525 {
2526 /* call propagators that are applicable during LP solving loop only if the node is not cut off */
2527 if( SCIPsetIsLT(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound) )
2528 {
2529 SCIP_Longint oldnboundchgs;
2530 SCIP_Longint oldninitconssadded;
2531 SCIP_Bool postpone;
2532
2533 oldnboundchgs = stat->nboundchgs;
2534 oldninitconssadded = stat->ninitconssadded;
2535
2536 SCIPsetDebugMsg(set, " -> LP solved: call propagators that are applicable during LP solving loop\n");
2537
2538 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, FALSE,
2539 SCIP_PROPTIMING_DURINGLPLOOP, cutoff, &postpone) );
2540 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2541 assert(!postpone);
2542
2543 if( stat->ninitconssadded != oldninitconssadded )
2544 {
2545 SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n", oldninitconssadded, stat->ninitconssadded);
2546
2547 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2548 branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2549 }
2550
2551 if( !(*cutoff) && !(*unbounded) )
2552 {
2553 /* if we found something, solve LP again */
2554 if( !lp->flushed )
2555 {
2556 SCIPsetDebugMsg(set, " -> found reduction: resolve LP\n");
2557
2558 /* in the root node, remove redundant rows permanently from the LP */
2559 if( root )
2560 {
2561 SCIP_CALL( SCIPlpFlush(lp, blkmem, set, transprob, eventqueue) );
2562 SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2563 }
2564
2565 /* resolve LP */
2566 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2567 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2568 assert(lp->flushed);
2569 assert(lp->solved || *lperror);
2570
2571 /* remove previous primal ray, store new one if LP is unbounded */
2572 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2573
2574 mustprice = TRUE;
2575 *propagateagain = TRUE;
2576 }
2577 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective
2578 * value which is added to the LP value; because of the loose status, the LP might not be reoptimized,
2579 * but the lower bound of the node needs to be updated
2580 */
2581 else if( stat->nboundchgs > oldnboundchgs )
2582 {
2583 *propagateagain = TRUE;
2584
2585 if( lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2586 {
2587 assert(lp->flushed);
2588 assert(lp->solved);
2589
2590 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2591 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2592 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2593
2594 /* update node estimate */
2595 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2596
2597 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2598 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2599 }
2600 }
2601 }
2602 }
2603 }
2604
2605 /* call primal heuristics that are applicable during node LP solving loop */
2606 if( !*cutoff && !(*unbounded) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2607 {
2608 SCIP_Bool foundsol;
2609
2610 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGLPLOOP,
2611 FALSE, &foundsol, unbounded) );
2612 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2613
2614 *lperror = *lperror || lp->resolvelperror;
2615 } /*lint !e438*/
2616 }
2617 assert(lp->flushed || *cutoff || *unbounded);
2618 assert(lp->solved || *lperror || *cutoff || *unbounded);
2619
2620 /* if we are infeasible, unbounded, exceeded a separation round, the objective, or a global performance limit,
2621 * we don't need to separate cuts
2622 * (the global limits are only checked at the root node in order to not query system time too often)
2623 */
2624 mustsepa = mustsepa && separate && !(*cutoff) && !(*unbounded)
2625 && stat->nseparounds < maxseparounds
2626 && ( delayedsepa || stat->nseparounds < maxsepapartialrounds )
2627 && nsepastallrounds < maxsepastallrounds
2629 && SCIPsetIsLT(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)
2630 && ( !root || !SCIPsolveIsStopped(set, stat, FALSE) );
2631
2632 /* separation (needs not to be done completely, because we just want to increase the lower bound) */
2633 if( mustsepa )
2634 {
2635 SCIP_Longint olddomchgcount;
2636 SCIP_Longint oldninitconssadded;
2637 SCIP_Bool enoughcuts;
2638
2639 assert(lp->flushed);
2640 assert(lp->solved);
2642 assert(!(*lperror));
2643 assert(!(*cutoff));
2644
2645 olddomchgcount = stat->domchgcount;
2646 oldninitconssadded = stat->ninitconssadded;
2647
2648 mustsepa = FALSE;
2649 delayedsepa = delayedsepa && stat->nseparounds >= maxsepapartialrounds;
2651
2652 /* global cut pool separation */
2653 if( !enoughcuts && !delayedsepa )
2654 {
2655 SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2656 actdepth, &enoughcuts, cutoff) );
2657
2658 if( *cutoff )
2659 {
2660 SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2661 }
2662 }
2663 assert(lp->flushed);
2664 assert(lp->solved);
2666 assert(!(*lperror));
2667
2668 /* separate constraints and LP */
2669 if( !(*cutoff) && !enoughcuts )
2670 {
2671 /* constraint and LP separation */
2672 SCIPsetDebugMsg(set, "constraint and LP separation\n");
2673
2674 /* apply a separation round */
2675 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal, tree,
2676 lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2677 &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) );
2678 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2679
2680 /* if we are in the last separation or stall round, also call the delayed separators */
2681 if( !(*cutoff) && !(*lperror) && lp->solved && !enoughcuts && delayedsepa
2682 && ( stat->nseparounds + 1 >= maxseparounds || nsepastallrounds + 1 >= maxsepastallrounds )
2684 {
2685 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal,
2686 tree, lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2687 &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) );
2688 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2689 }
2690 }
2691
2692 /* call global cut pool separation again since separators may add cuts to the pool instead of the sepastore */
2693 if( !(*cutoff) && !(*lperror) && lp->solved && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && !enoughcuts )
2694 {
2695 SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2696 actdepth, &enoughcuts, cutoff) );
2697
2698 if( *cutoff )
2699 {
2700 SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2701 }
2702 }
2703
2704 /* delayed global cut pool separation */
2705 if( !(*cutoff) && !(*lperror) && lp->solved && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && SCIPsepastoreGetNCuts(sepastore) == 0 && !enoughcuts )
2706 {
2707 SCIP_CALL( cutpoolSeparate(delayedcutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, TRUE,
2708 root, actdepth, &enoughcuts, cutoff) );
2709
2710 if( *cutoff )
2711 {
2712 SCIPsetDebugMsg(set, " -> delayed global cut pool detected cutoff\n");
2713 }
2714 assert(lp->solved);
2716 assert(lp->flushed);
2717 }
2718
2719 /* delayed separation if no cuts where produced */
2720 if( !(*cutoff) && !(*lperror) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && SCIPsepastoreGetNCuts(sepastore) == 0 && delayedsepa )
2721 {
2722 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal,
2723 tree, lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2724 &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) );
2725 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2726
2727 /* call delayed cut pool separation again, since separators may add cuts to the pool instead of the sepastore */
2728 if( !(*cutoff) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2729 {
2730 assert( !(*lperror) );
2731
2732 SCIP_CALL( cutpoolSeparate(delayedcutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, TRUE,
2733 root, actdepth, &enoughcuts, cutoff) );
2734
2735 if( *cutoff )
2736 {
2737 SCIPsetDebugMsg(set, " -> delayed global cut pool detected cutoff\n");
2738 }
2740 assert(lp->flushed);
2741 assert(lp->solved);
2742 }
2743 }
2744
2745 assert(*cutoff || *lperror || SCIPlpIsSolved(lp));
2746 assert(!SCIPlpIsSolved(lp)
2753
2754 if( *cutoff || *lperror
2757 {
2758 /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
2759 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
2760 }
2761 else
2762 {
2763 /* apply found cuts */
2764 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2765 branchcand, eventqueue, eventfilter, cliquetable, root, SCIP_EFFICIACYCHOICE_LP, cutoff) );
2766
2767 if( !(*cutoff) )
2768 {
2769 mustprice = mustprice || !lp->flushed || (transprob->ncolvars != npricedcolvars);
2770 mustsepa = mustsepa || !lp->flushed;
2771
2772 /* if a new bound change (e.g. a cut with only one column) was found, propagate domains again */
2773 if( stat->domchgcount != olddomchgcount )
2774 {
2775 SCIPsetDebugMsg(set, " -> separation changed bound: propagate again\n");
2776
2777 *propagateagain = TRUE;
2778
2779 /* in the root node, remove redundant rows permanently from the LP */
2780 if( root )
2781 {
2782 SCIP_CALL( SCIPlpFlush(lp, blkmem, set, transprob, eventqueue) );
2783 SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2784 }
2785 }
2786
2787 if( stat->ninitconssadded != oldninitconssadded )
2788 {
2789 SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n",
2790 oldninitconssadded, stat->ninitconssadded);
2791
2792 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2793 branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2794 }
2795
2796 if( !(*cutoff) )
2797 {
2798 SCIP_Real lpobjval;
2799
2800 /* solve LP (with dual simplex) */
2801 SCIPsetDebugMsg(set, "separation: solve LP\n");
2802 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2803 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2804 assert(lp->flushed);
2805 assert(lp->solved || *lperror);
2806
2807 /* remove previous primal ray, store new one if LP is unbounded */
2808 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2809
2810 if( !(*lperror) )
2811 {
2812 SCIP_Bool stalling;
2813
2814 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
2815 * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
2816 * bound of the node needs to be updated
2817 */
2818 if( stat->domchgcount != olddomchgcount && (!mustprice || mustsepa) && !(*cutoff)
2819 && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2820 {
2821 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2822 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2823 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2824
2825 /* update node estimate */
2826 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2827
2828 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2829 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2830 }
2831
2832 /* check if we are stalling
2833 * If we have an LP solution, then we are stalling if
2834 * we had an LP solution before and
2835 * the LP value did not improve and
2836 * the number of fractional variables did not decrease.
2837 * If we do not have an LP solution, then we are stalling if the solution status of the LP did not change.
2838 */
2840 {
2841 SCIP_Real objreldiff;
2842 int nfracs;
2843
2844 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nfracs, NULL,
2845 NULL) );
2846 lpobjval = SCIPlpGetObjval(lp, set, transprob);
2847
2848 objreldiff = SCIPrelDiff(lpobjval, stalllpobjval);
2849 SCIPsetDebugMsg(set, " -> LP bound moved from %g to %g (reldiff: %g)\n",
2850 stalllpobjval, lpobjval, objreldiff);
2851
2852 stalling = (stalllpsolstat == SCIP_LPSOLSTAT_OPTIMAL &&
2853 objreldiff <= 1e-04 &&
2854 nfracs >= (0.9 - 0.1 * nsepastallrounds) * stallnfracs);
2855
2856 stalllpobjval = lpobjval;
2857 stallnfracs = nfracs;
2858 } /*lint !e438*/
2859 else
2860 {
2861 stalling = (stalllpsolstat == SCIPlpGetSolstat(lp));
2862 }
2863
2864 if( !stalling )
2865 {
2866 nsepastallrounds = 0;
2867 lp->installing = FALSE;
2868 }
2869 else
2870 {
2871 ++nsepastallrounds;
2872 }
2873 stalllpsolstat = SCIPlpGetSolstat(lp);
2874
2875 /* tell LP that we are stalling */
2876 if( nsepastallrounds + 1 >= maxsepastallrounds )
2877 lp->installing = TRUE;
2878
2879 SCIPsetDebugMsg(set, " -> nsepastallrounds=%d/%d\n", nsepastallrounds, maxsepastallrounds);
2880 }
2881 }
2882 }
2883 }
2884 assert(*cutoff || *lperror || (lp->flushed && lp->solved)); /* cutoff: LP may be unsolved due to bound changes */
2885
2886 /* increase separation round counter */
2887 ++stat->nseparounds;
2888
2889 SCIPsetDebugMsg(set, "separation round %d/%d finished (%d/%d stall rounds): mustprice=%u, mustsepa=%u, delayedsepa=%u, propagateagain=%u\n",
2890 stat->nseparounds, maxseparounds, nsepastallrounds, maxsepastallrounds, mustprice, mustsepa, delayedsepa, *propagateagain);
2891 }
2892 }
2893
2894 if( root && nsepastallrounds >= maxsepastallrounds )
2895 {
2896 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
2897 "Truncate separation round because of stalling (%d stall rounds).\n", maxsepastallrounds);
2898 }
2899
2900 if( !*lperror )
2901 {
2902 /* update pseudo cost values for continuous variables, if it should be delayed */
2903 SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, FALSE, set->branch_delaypscost) );
2904 }
2905
2906 /* update lower bound w.r.t. the LP solution */
2907 if( !(*cutoff) && !(*lperror) )
2908 {
2909 assert(lp->flushed);
2910 assert(lp->solved);
2911
2912 if( SCIPlpIsRelax(lp) )
2913 {
2914 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2915 }
2916
2917 /* update node estimate */
2918 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2919
2920 /* issue LPSOLVED event */
2922 {
2924 SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
2925 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
2926 }
2927
2928 /* if the LP is a relaxation and we are not solving exactly, then we may analyze an infeasible or bound exceeding
2929 * LP (not necessary in the root node) and cut off the current node
2930 */
2931 if( !set->misc_exactsolve && !root && SCIPlpIsRelax(lp) && SCIPprobAllColsInLP(transprob, set, lp)
2933 {
2934 SCIP_CALL( SCIPconflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt,
2935 lp, branchcand, eventqueue, cliquetable, NULL) );
2936 *cutoff = TRUE;
2937 }
2938 }
2939
2940 /* check for unboundedness */
2941 if( !(*lperror) )
2942 *unbounded = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY);
2943
2944 lp->installing = FALSE;
2945
2946 /* check for cutoff */
2947 if( *cutoff )
2948 {
2949 SCIP_CALL( SCIPnodeCutoff(focusnode, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2950 }
2951
2952 SCIPsetDebugMsg(set, " -> final lower bound: %g (LP status: %d, LP obj: %g)\n",
2954 (*cutoff || *unbounded) ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
2955
2956 return SCIP_OKAY; /*lint !e438*/
2957}
2958
2959/** updates the current lower bound with the pseudo objective value, cuts off node by bounding, and applies conflict
2960 * analysis if the pseudo objective lead to the cutoff
2961 */
2962static
2964 BMS_BLKMEM* blkmem, /**< block memory buffers */
2965 SCIP_SET* set, /**< global SCIP settings */
2966 SCIP_STAT* stat, /**< dynamic problem statistics */
2967 SCIP_PROB* transprob, /**< tranformed problem after presolve */
2968 SCIP_PROB* origprob, /**< original problem */
2969 SCIP_PRIMAL* primal, /**< primal data */
2970 SCIP_TREE* tree, /**< branch and bound tree */
2971 SCIP_REOPT* reopt, /**< reoptimization data structure */
2972 SCIP_LP* lp, /**< LP data */
2973 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2974 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2975 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2976 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2977 SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
2978 )
2979{
2980 assert(transprob != NULL);
2981 assert(origprob != NULL);
2982 assert(primal != NULL);
2983 assert(cutoff != NULL);
2984
2985 if( !(*cutoff) )
2986 {
2987 SCIP_NODE* focusnode;
2988 SCIP_Real pseudoobjval;
2989
2990 /* get current focus node */
2991 focusnode = SCIPtreeGetFocusNode(tree);
2992
2993 /* update lower bound w.r.t. the pseudo solution */
2994 pseudoobjval = SCIPlpGetPseudoObjval(lp, set, transprob);
2995 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, pseudoobjval);
2996 SCIPsetDebugMsg(set, " -> lower bound: %g [%g] (pseudoobj: %g [%g]), cutoff bound: %g [%g]\n",
2997 SCIPnodeGetLowerbound(focusnode), SCIPprobExternObjval(transprob, origprob, set, SCIPnodeGetLowerbound(focusnode)) + SCIPgetOrigObjoffset(set->scip),
2998 pseudoobjval, SCIPprobExternObjval(transprob, origprob, set, pseudoobjval) + SCIPgetOrigObjoffset(set->scip),
2999 primal->cutoffbound, SCIPprobExternObjval(transprob, origprob, set, primal->cutoffbound) + SCIPgetOrigObjoffset(set->scip));
3000
3001 /* check for infeasible node by bounding */
3002 if( (set->misc_exactsolve && SCIPnodeGetLowerbound(focusnode) >= primal->cutoffbound)
3003 || (!set->misc_exactsolve && SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)) )
3004 {
3005 /* call pseudo conflict analysis, if the node is cut off due to the pseudo objective value */
3006 if( !SCIPsetIsInfinity(set, -pseudoobjval) && !SCIPsetIsInfinity(set, primal->cutoffbound) && SCIPsetIsGE(set, pseudoobjval, primal->cutoffbound) )
3007 {
3008 SCIP_CALL( SCIPconflictAnalyzePseudo(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, NULL) );
3009 }
3010
3011 *cutoff = TRUE;
3012 }
3013 }
3014
3015 return SCIP_OKAY;
3016}
3017
3018/** marks all relaxators to be unsolved */
3019static
3021 SCIP_SET* set, /**< global SCIP settings */
3022 SCIP_RELAXATION* relaxation /**< global relaxation data */
3023 )
3024{
3025 int r;
3026
3027 assert(set != NULL);
3028 assert(relaxation != NULL);
3029
3031
3032 for( r = 0; r < set->nrelaxs; ++r )
3033 SCIPrelaxMarkUnsolved(set->relaxs[r]);
3034}
3035
3036/** solves the current node's LP in a price-and-cut loop */
3037static
3039 BMS_BLKMEM* blkmem, /**< block memory buffers */
3040 SCIP_SET* set, /**< global SCIP settings */
3041 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3042 SCIP_STAT* stat, /**< dynamic problem statistics */
3043 SCIP_MEM* mem, /**< block memory pools */
3044 SCIP_PROB* origprob, /**< original problem */
3045 SCIP_PROB* transprob, /**< transformed problem after presolve */
3046 SCIP_PRIMAL* primal, /**< primal data */
3047 SCIP_TREE* tree, /**< branch and bound tree */
3048 SCIP_REOPT* reopt, /**< reoptimization data structure */
3049 SCIP_LP* lp, /**< LP data */
3050 SCIP_RELAXATION* relaxation, /**< relaxators */
3051 SCIP_PRICESTORE* pricestore, /**< pricing storage */
3052 SCIP_SEPASTORE* sepastore, /**< separation storage */
3053 SCIP_CUTPOOL* cutpool, /**< global cut pool */
3054 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
3055 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3056 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3057 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
3058 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3059 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3060 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3061 SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
3062 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
3063 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
3064 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
3065 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
3066 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3067 SCIP_Bool* unbounded, /**< pointer to store TRUE, if an unbounded ray was found in the LP */
3068 SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
3069 SCIP_Bool* pricingaborted /**< pointer to store TRUE, if the pricing was aborted and the lower bound
3070 * must not be used */
3071 )
3072{
3073 SCIP_Longint nlpiterations;
3074 SCIP_Longint nlps;
3075 SCIP_Longint nzeroitlps;
3076
3077 assert(stat != NULL);
3078 assert(tree != NULL);
3079 assert(SCIPtreeHasFocusNodeLP(tree));
3080 assert(cutoff != NULL);
3081 assert(unbounded != NULL);
3082 assert(lperror != NULL);
3083 assert(*cutoff == FALSE);
3084 assert(*unbounded == FALSE);
3085 assert(*lperror == FALSE);
3086
3087 nlps = stat->nlps;
3088 nzeroitlps = stat->ndualzeroitlps + stat->nprimalzeroitlps + stat->nbarrierzeroitlps;
3089 nlpiterations = stat->nlpiterations;
3090
3091 if( !initiallpsolved )
3092 {
3093 /* load and solve the initial LP of the node */
3094 SCIP_CALL( solveNodeInitialLP(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
3095 pricestore, sepastore, cutpool, branchcand, eventfilter, eventqueue, cliquetable, newinitconss, cutoff, lperror) );
3096
3097 assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3098 SCIPsetDebugMsg(set, "price-and-cut-loop: initial LP status: %d, LP obj: %g\n",
3099 SCIPlpGetSolstat(lp),
3100 *cutoff ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
3101
3102 /* update initial LP iteration counter */
3103 stat->ninitlps += stat->nlps - nlps;
3104 stat->ninitlpiterations += stat->nlpiterations - nlpiterations;
3105
3106 /* In the root node, we try if the initial LP solution is feasible to avoid expensive setup of data structures in
3107 * separators; in case the root LP is aborted, e.g., by hitting the time limit, we do not check the LP solution
3108 * since the corresponding data structures have not been updated.
3109 */
3110 if( SCIPtreeGetCurrentDepth(tree) == 0 && !(*cutoff) && !(*lperror)
3112 && !SCIPsolveIsStopped(set, stat, FALSE) )
3113 {
3114 SCIP_Bool checklprows;
3115 SCIP_Bool stored;
3116 SCIP_SOL* sol;
3117 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
3118
3119 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
3120
3122 checklprows = FALSE;
3123 else
3124 checklprows = TRUE;
3125
3126#ifndef NDEBUG
3127 /* in the debug mode we want to explicitly check if the solution is feasible if it was stored */
3128 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
3129 eventqueue, eventfilter, sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
3130
3131 if( stored )
3132 {
3133 SCIP_Bool feasible;
3134
3135 SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, FALSE, FALSE, TRUE, TRUE,
3136 checklprows, &feasible) );
3137 assert(feasible);
3138 }
3139
3140 SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) );
3141#else
3142 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
3143 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
3144#endif
3145 if( stored )
3146 {
3147 stat->nlpsolsfound++;
3148
3149 if( primal->nbestsolsfound != oldnbestsolsfound )
3150 {
3151 stat->nlpbestsolsfound++;
3153 }
3154
3155 if( set->reopt_enable )
3156 {
3157 assert(reopt != NULL);
3159 SCIPlpGetSolstat(lp), tree->root == tree->focusnode, TRUE, tree->focusnode->lowerbound,
3160 tree->effectiverootdepth) );
3161 }
3162 }
3163
3165 *unbounded = TRUE;
3166 }
3167 }
3168 else
3169 {
3170 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob,
3171 origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE,
3172 cutoff) );
3173 }
3174 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3175
3176 /* check for infeasible node by bounding */
3177 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
3178#ifdef SCIP_DEBUG
3179 if( *cutoff )
3180 {
3181 if( SCIPtreeGetCurrentDepth(tree) == 0 )
3182 {
3183 SCIPsetDebugMsg(set, "solution cuts off root node, stop solution process\n");
3184 }
3185 else
3186 {
3187 SCIPsetDebugMsg(set, "solution cuts off node\n");
3188 }
3189 }
3190#endif
3191
3192 if( !(*cutoff) && !(*lperror) )
3193 {
3194 SCIP_Longint oldninitconssadded;
3195 SCIP_Longint oldnboundchgs;
3196 SCIP_Longint olddomchgcount;
3197 int oldnpricedvars;
3198 int oldncutsapplied;
3199
3200 oldnpricedvars = transprob->ncolvars;
3201 oldninitconssadded = stat->ninitconssadded;
3202 oldncutsapplied = SCIPsepastoreGetNCutsApplied(sepastore);
3203 oldnboundchgs = stat->nboundchgs;
3204 olddomchgcount = stat->domchgcount;
3205
3206 /* solve the LP with price-and-cut*/
3207 SCIP_CALL( priceAndCutLoop(blkmem, set, messagehdlr, stat, mem, transprob, origprob, primal, tree, reopt, lp,
3208 pricestore, sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter,
3209 eventqueue, cliquetable, fullseparation, propagateagain, cutoff, unbounded, lperror, pricingaborted) );
3210
3211 /* check if the problem was changed and the relaxation needs to be resolved */
3212 if( (transprob->ncolvars != oldnpricedvars) || (stat->ninitconssadded != oldninitconssadded) ||
3213 (SCIPsepastoreGetNCutsApplied(sepastore) != oldncutsapplied) || (stat->nboundchgs != oldnboundchgs) ||
3214 (stat->domchgcount != olddomchgcount) )
3215 {
3216 *solverelaxagain = TRUE;
3217 markRelaxsUnsolved(set, relaxation);
3218 }
3219 }
3220 assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3221
3222 /* if there is no LP error, then *unbounded should be TRUE, iff the LP solution status is unboundedray */
3223 assert(*lperror || ((SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY) == *unbounded));
3224
3225 /* 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,
3226 * 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
3227 * is not a feasible lower bound for the solutions in the current subtree.
3228 * In this case, the LP has to be solved to optimality by temporarily removing the cutoff bound.
3229 */
3230 if( (*pricingaborted) && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ITERLIMIT)
3231 && !(*cutoff) )
3232 {
3233 SCIP_Real tmpcutoff;
3234
3235 /* temporarily disable cutoffbound, which also disables the objective limit */
3236 tmpcutoff = lp->cutoffbound;
3238
3239 lp->solved = FALSE;
3240 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) );
3241
3242 /* reinstall old cutoff bound */
3243 lp->cutoffbound = tmpcutoff;
3244
3245 SCIPsetDebugMsg(set, "re-optimized LP without cutoff bound: LP status: %d, LP obj: %g\n",
3246 SCIPlpGetSolstat(lp), *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
3247
3248 /* lp solstat should not be objlimit, since the cutoff bound was removed temporarily */
3250 /* lp solstat should not be unboundedray, since the lp was dual feasible */
3252 /* there should be no primal ray, since the lp was dual feasible */
3253 assert(primal->primalray == NULL);
3255 {
3256 *cutoff = TRUE;
3257 }
3258 }
3259
3260 assert(!(*pricingaborted) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL /* cppcheck-suppress assertWithSideEffect */
3261 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_NOTSOLVED || SCIPsolveIsStopped(set, stat, FALSE) || (*cutoff));
3262
3263 assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3264
3265 /* update node's LP iteration counter */
3266 stat->nnodelps += stat->nlps - nlps;
3267 stat->nnodezeroitlps += stat->ndualzeroitlps + stat->nprimalzeroitlps + stat->nbarrierzeroitlps - nzeroitlps;
3268 stat->nnodelpiterations += stat->nlpiterations - nlpiterations;
3269
3270 /* update number of root node LPs and iterations if the root node was processed */
3271 if( SCIPnodeGetDepth(tree->focusnode) == 0 )
3272 {
3273 stat->nrootlps += stat->nlps - nlps;
3274 stat->nrootlpiterations += stat->nlpiterations - nlpiterations;
3275 }
3276
3277 return SCIP_OKAY;
3278}
3279
3280/** calls relaxators */
3281static
3283 SCIP_SET* set, /**< global SCIP settings */
3284 SCIP_STAT* stat, /**< dynamic problem statistics */
3285 SCIP_TREE* tree, /**< branch and bound tree */
3286 SCIP_RELAXATION* relaxation, /**< relaxators */
3287 SCIP_PROB* transprob, /**< transformed problem */
3288 SCIP_PROB* origprob, /**< original problem */
3289 int depth, /**< depth of current node */
3290 SCIP_Bool beforelp, /**< should the relaxators with non-negative or negative priority be called? */
3291 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3292 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3293 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3294 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called
3295 * again */
3296 SCIP_Bool* relaxcalled /**< pointer to store TRUE, if at least one relaxator was called (unmodified
3297 * otherwise) */
3298 )
3299{
3300 SCIP_RESULT result;
3301 SCIP_Real lowerbound;
3302 int r;
3303
3304 assert(set != NULL);
3305 assert(relaxation != NULL);
3306 assert(cutoff != NULL);
3307 assert(solvelpagain != NULL);
3308 assert(propagateagain != NULL);
3309 assert(solverelaxagain != NULL);
3310 assert(relaxcalled != NULL);
3311 assert(!(*cutoff));
3312
3313 /* sort by priority */
3315
3316 for( r = 0; r < set->nrelaxs && !(*cutoff); ++r )
3317 {
3318 if( beforelp != (SCIPrelaxGetPriority(set->relaxs[r]) >= 0) )
3319 continue;
3320
3321 *relaxcalled = TRUE;
3322
3323 lowerbound = -SCIPsetInfinity(set);
3324
3325 SCIP_CALL( SCIPrelaxExec(set->relaxs[r], set, tree, stat, depth, &lowerbound, &result) );
3326
3327 switch( result )
3328 {
3329 case SCIP_CUTOFF:
3330 *cutoff = TRUE;
3331 SCIPsetDebugMsg(set, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(set->relaxs[r]));
3332 /* @todo does it make sense to proceed if the node is proven to be infeasible? */
3333 return SCIP_OKAY;
3334
3335 case SCIP_CONSADDED:
3336 *solvelpagain = TRUE; /* the separation for new constraints should be called */
3337 *propagateagain = TRUE; /* the propagation for new constraints should be called */
3338 break;
3339
3340 case SCIP_REDUCEDDOM:
3341 *solvelpagain = TRUE;
3342 *propagateagain = TRUE;
3343 break;
3344
3345 case SCIP_SEPARATED:
3346 *solvelpagain = TRUE;
3347 break;
3348
3349 case SCIP_SUSPENDED:
3350 *solverelaxagain = TRUE;
3351 break;
3352
3353 case SCIP_SUCCESS:
3354 case SCIP_DIDNOTRUN:
3355 break;
3356
3357 default:
3358 SCIPerrorMessage("invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(set->relaxs[r]));
3359 return SCIP_INVALIDRESULT;
3360 } /*lint !e788*/
3361
3362 if( result != SCIP_CUTOFF && result != SCIP_DIDNOTRUN && result != SCIP_SUSPENDED )
3363 {
3364 SCIP_NODE* focusnode;
3365
3366 focusnode = SCIPtreeGetFocusNode(tree);
3367 assert(focusnode != NULL);
3368 assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
3369
3370 /* update lower bound w.r.t. the lower bound given by the relaxator */
3371 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, lowerbound);
3372 SCIPsetDebugMsg(set, " -> new lower bound given by relaxator %s: %g\n",
3373 SCIPrelaxGetName(set->relaxs[r]), lowerbound);
3374 }
3375 }
3376
3377 return SCIP_OKAY;
3378}
3379
3380/** enforces constraints by branching, separation, or domain reduction */
3381static
3383 BMS_BLKMEM* blkmem, /**< block memory buffers */
3384 SCIP_SET* set, /**< global SCIP settings */
3385 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3386 SCIP_STAT* stat, /**< dynamic problem statistics */
3387 SCIP_PROB* prob, /**< transformed problem after presolve */
3388 SCIP_PRIMAL* primal, /**< primal data */
3389 SCIP_TREE* tree, /**< branch and bound tree */
3390 SCIP_LP* lp, /**< LP data */
3391 SCIP_RELAXATION* relaxation, /**< global relaxation data */
3392 SCIP_SEPASTORE* sepastore, /**< separation storage */
3393 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3394 SCIP_Bool* branched, /**< pointer to store whether a branching was created */
3395 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3396 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the LP/pseudo solution is infeasible */
3397 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3398 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3399 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
3400 SCIP_Bool forced /**< should enforcement of pseudo solution be forced? */
3401 )
3402{
3403 SCIP_RESULT result;
3404 SCIP_SOL* relaxsol = NULL;
3405 SCIP_Real pseudoobjval;
3406 SCIP_Bool resolved;
3407 SCIP_Bool objinfeasible;
3408 SCIP_Bool enforcerelaxsol;
3409 int h;
3410
3411 assert(set != NULL);
3412 assert(stat != NULL);
3413 assert(tree != NULL);
3414 assert(SCIPtreeGetFocusNode(tree) != NULL);
3415 assert(branched != NULL);
3416 assert(cutoff != NULL);
3417 assert(infeasible != NULL);
3418 assert(propagateagain != NULL);
3419 assert(solvelpagain != NULL);
3420 assert(solverelaxagain != NULL);
3421 assert(!(*cutoff));
3422 assert(!(*propagateagain));
3423 assert(!(*solvelpagain));
3424 assert(!(*solverelaxagain));
3425
3426 *branched = FALSE;
3427 /**@todo avoid checking the same pseudosolution twice */
3428
3429 /* enforce (best) relaxation solution if the LP has a worse objective value */
3430 enforcerelaxsol = SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree)
3431 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, prob)));
3432
3433 /* check if all constraint handlers implement the enforelax callback, otherwise enforce the LP solution */
3434 for( h = 0; h < set->nconshdlrs && enforcerelaxsol; ++h )
3435 {
3436 if( set->conshdlrs_enfo[h]->consenforelax == NULL && ((! set->conshdlrs_enfo[h]->needscons) ||
3437 (set->conshdlrs_enfo[h]->nconss > 0)) )
3438 {
3439 SCIP_VERBLEVEL verblevel;
3440
3441 enforcerelaxsol = FALSE;
3442
3443 verblevel = SCIP_VERBLEVEL_FULL;
3444
3445 if( !stat->disableenforelaxmsg && set->disp_verblevel == SCIP_VERBLEVEL_HIGH )
3446 {
3447 verblevel = SCIP_VERBLEVEL_HIGH;
3448
3449 /* remember that the disable relaxation enforcement message was posted and only post it again if the
3450 * verblevel is SCIP_VERBLEVEL_FULL
3451 */
3452 stat->disableenforelaxmsg = TRUE;
3453 }
3454 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel, "Disable enforcement of relaxation solutions"
3455 " since constraint handler %s does not implement enforelax-callback\n",
3456 SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3457 }
3458 }
3459
3460 /* enforce constraints by branching, applying additional cutting planes (if LP is being processed),
3461 * introducing new constraints, or tighten the domains
3462 */
3463#ifndef SCIP_NDEBUG
3464 if( enforcerelaxsol )
3465 {
3466 SCIPsetDebugMsg(set, "enforcing constraints on relaxation solution\n");
3467 }
3468 else
3469 {
3470 SCIPsetDebugMsg(set, "enforcing constraints on %s solution\n", SCIPtreeHasFocusNodeLP(tree) ? "LP" : "pseudo");
3471 }
3472#endif
3473
3474 /* check, if the solution is infeasible anyway due to it's objective value */
3475 if( SCIPtreeHasFocusNodeLP(tree) || enforcerelaxsol )
3476 objinfeasible = FALSE;
3477 else
3478 {
3479 pseudoobjval = SCIPlpGetPseudoObjval(lp, set, prob);
3480 objinfeasible = SCIPsetIsDualfeasLT(set, pseudoobjval, SCIPnodeGetLowerbound(SCIPtreeGetFocusNode(tree)));
3481 }
3482
3483 /* during constraint enforcement, generated cuts should enter the LP in any case; otherwise, a constraint handler
3484 * would fail to enforce its constraints if it relies on the modification of the LP relaxation
3485 */
3486 SCIPsepastoreStartForceCuts(sepastore);
3487
3488 /* enforce constraints until a handler resolved an infeasibility with cutting off the node, branching,
3489 * reducing a domain, or separating a cut
3490 * if a constraint handler introduced new constraints to enforce his constraints, the newly added constraints
3491 * have to be enforced themselves
3492 */
3493 resolved = FALSE;
3494
3495 /* in case the relaxation solution should be enforced, we need to create the corresponding solution for the enforelax callbacks */
3496 if( enforcerelaxsol )
3497 {
3498 SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
3499 }
3500
3501 for( h = 0; h < set->nconshdlrs && !resolved; ++h )
3502 {
3503 assert(SCIPsepastoreGetNCuts(sepastore) == 0); /* otherwise, the LP should have been resolved first */
3504
3505 /* enforce LP, pseudo, or relaxation solution */
3506 if( enforcerelaxsol )
3507 {
3508 SCIPsetDebugMsg(set, "enforce relaxation solution with value %g\n", SCIPrelaxationGetSolObj(relaxation));
3509
3510 SCIP_CALL( SCIPconshdlrEnforceRelaxSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore,
3511 relaxsol, *infeasible, &result) );
3512 }
3513 else if( SCIPtreeHasFocusNodeLP(tree) )
3514 {
3515 SCIPsetDebugMsg(set, "enforce LP solution with value %g\n", SCIPlpGetObjval(lp, set, prob));
3516
3517 assert(lp->flushed);
3518 assert(lp->solved);
3520 SCIP_CALL( SCIPconshdlrEnforceLPSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore, *infeasible,
3521 &result) );
3522 }
3523 else
3524 {
3525 SCIP_CALL( SCIPconshdlrEnforcePseudoSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, branchcand, *infeasible,
3526 objinfeasible, forced, &result) );
3527 if( SCIPsepastoreGetNCuts(sepastore) != 0 )
3528 {
3529 SCIPerrorMessage("pseudo enforcing method of constraint handler <%s> separated cuts\n",
3530 SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3531 return SCIP_INVALIDRESULT;
3532 }
3533 }
3534 SCIPsetDebugMsg(set, "enforcing of <%s> returned result %d\n", SCIPconshdlrGetName(set->conshdlrs_enfo[h]), result);
3535
3536 switch( result )
3537 {
3538 case SCIP_CUTOFF:
3539 assert(tree->nchildren == 0);
3540 *cutoff = TRUE;
3541 *infeasible = TRUE;
3542 resolved = TRUE;
3543 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in enforcement\n",
3544 SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3545 break;
3546
3547 case SCIP_CONSADDED:
3548 assert(tree->nchildren == 0);
3549 *infeasible = TRUE;
3550 *propagateagain = TRUE; /* the propagation for new constraints should be called */
3551 *solvelpagain = TRUE; /* the separation for new constraints should be called */
3552 *solverelaxagain = TRUE;
3553 markRelaxsUnsolved(set, relaxation);
3554 resolved = TRUE;
3555 break;
3556
3557 case SCIP_REDUCEDDOM:
3558 assert(tree->nchildren == 0);
3559 *infeasible = TRUE;
3560 *propagateagain = TRUE;
3561 *solvelpagain = TRUE;
3562 *solverelaxagain = TRUE;
3563 markRelaxsUnsolved(set, relaxation);
3564 resolved = TRUE;
3565 break;
3566
3567 case SCIP_SEPARATED:
3568 assert(tree->nchildren == 0);
3569 assert(SCIPsepastoreGetNCuts(sepastore) > 0);
3570 *infeasible = TRUE;
3571 *solvelpagain = TRUE;
3572 *solverelaxagain = TRUE;
3573 markRelaxsUnsolved(set, relaxation);
3574 resolved = TRUE;
3575 break;
3576
3577 case SCIP_BRANCHED:
3578 assert(tree->nchildren >= 1);
3579 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3580 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3581 *infeasible = TRUE;
3582 *branched = TRUE;
3583 resolved = TRUE;
3584
3585 /* increase the number of internal nodes */
3586 stat->ninternalnodes++;
3587 stat->ntotalinternalnodes++;
3588 break;
3589
3590 case SCIP_SOLVELP:
3591 /* either LP was not solved, or it is not solved anymore (e.g., because feastol has been tightened by some constraint handler) */
3592 assert(!SCIPtreeHasFocusNodeLP(tree) || !lp->solved);
3593 assert(tree->nchildren == 0);
3594 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3595 *infeasible = TRUE;
3596 *solvelpagain = TRUE;
3597 resolved = TRUE;
3598 SCIPtreeSetFocusNodeLP(tree, TRUE); /* the node's LP must be solved */
3599 break;
3600
3601 case SCIP_INFEASIBLE:
3602 assert(tree->nchildren == 0);
3603 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3604 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3605 *infeasible = TRUE;
3606 break;
3607
3608 case SCIP_FEASIBLE:
3609 assert(tree->nchildren == 0);
3610 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3611 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3612 break;
3613
3614 case SCIP_DIDNOTRUN:
3615 assert(tree->nchildren == 0);
3616 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3617 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3618 assert(objinfeasible);
3619 *infeasible = TRUE;
3620 break;
3621
3622 default:
3623 SCIPerrorMessage("invalid result code <%d> from enforcing method of constraint handler <%s>\n",
3624 result, SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3625 return SCIP_INVALIDRESULT;
3626 } /*lint !e788*/
3627
3628 /* the enforcement method may add a primal solution, after which the LP status could be set to
3629 * objective limit reached
3630 */
3632 {
3633 *cutoff = TRUE;
3634 *infeasible = TRUE;
3635 resolved = TRUE;
3636 SCIPsetDebugMsg(set, " -> LP exceeded objective limit\n");
3637
3638 /* If we used the probing mode during branching, it might happen that we added a constraint or global bound
3639 * and returned SCIP_CONSADDED or SCIP_REDUCEDDOM, but when reoptimizing the LP after ending the probing mode,
3640 * this leads to hitting the objective limit. In this case, we do not need to propagate or solve the LP again.
3641 */
3642 *propagateagain = FALSE;
3643 *solvelpagain = FALSE;
3644 }
3645
3646 assert(!(*branched) || (resolved && !(*cutoff) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3647 assert(!(*cutoff) || (resolved && !(*branched) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3648 assert(*infeasible || (!resolved && !(*branched) && !(*cutoff) && !(*propagateagain) && !(*solvelpagain)));
3649 assert(!(*propagateagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3650 assert(!(*solvelpagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3651 }
3652 assert(!objinfeasible || *infeasible);
3653 assert(resolved == (*branched || *cutoff || *propagateagain || *solvelpagain));
3654 assert(*cutoff || *solvelpagain || SCIPsepastoreGetNCuts(sepastore) == 0);
3655
3656 /* in case the relaxation solution was enforced, free the created solution */
3657 if( enforcerelaxsol )
3658 {
3659 SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
3660 }
3661
3662 /* deactivate the cut forcing of the constraint enforcement */
3663 SCIPsepastoreEndForceCuts(sepastore);
3664
3665 SCIPsetDebugMsg(set, " -> enforcing result: branched=%u, cutoff=%u, infeasible=%u, propagateagain=%u, solvelpagain=%u, resolved=%u\n",
3666 *branched, *cutoff, *infeasible, *propagateagain, *solvelpagain, resolved);
3667
3668 return SCIP_OKAY;
3669}
3670
3671/** applies the cuts stored in the separation store, or clears the store if the node can be cut off */
3672static
3674 BMS_BLKMEM* blkmem, /**< block memory buffers */
3675 SCIP_SET* set, /**< global SCIP settings */
3676 SCIP_STAT* stat, /**< dynamic problem statistics */
3677 SCIP_PROB* transprob, /**< transformed problem */
3678 SCIP_PROB* origprob, /**< original problem */
3679 SCIP_TREE* tree, /**< branch and bound tree */
3680 SCIP_REOPT* reopt, /**< reotimization data structure */
3681 SCIP_LP* lp, /**< LP data */
3682 SCIP_RELAXATION* relaxation, /**< relaxators */
3683 SCIP_SEPASTORE* sepastore, /**< separation storage */
3684 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3685 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3686 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3687 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3688 SCIP_Bool root, /**< is this the initial root LP? */
3689 SCIP_EFFICIACYCHOICE efficiacychoice, /**< type of solution to base efficiacy computation on */
3690 SCIP_Bool* cutoff, /**< pointer to whether the node can be cut off */
3691 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3692 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3693 SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if the node's relaxation has to be solved again */
3694 )
3695{
3696 assert(stat != NULL);
3697 assert(cutoff != NULL);
3698 assert(propagateagain != NULL);
3699 assert(solvelpagain != NULL);
3700
3701 if( *cutoff )
3702 {
3703 /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
3704 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
3705 }
3706 else if( SCIPsepastoreGetNCuts(sepastore) > 0 )
3707 {
3708 SCIP_Longint olddomchgcount;
3709 int oldncutsapplied;
3710
3711 olddomchgcount = stat->domchgcount;
3712 oldncutsapplied = SCIPsepastoreGetNCutsApplied(sepastore);
3713 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
3714 eventqueue, eventfilter, cliquetable, root, efficiacychoice, cutoff) );
3715 *propagateagain = *propagateagain || (stat->domchgcount != olddomchgcount);
3716 *solvelpagain = TRUE;
3717 if( (stat->domchgcount != olddomchgcount) || (SCIPsepastoreGetNCutsApplied(sepastore) != oldncutsapplied) )
3718 {
3719 *solverelaxagain = TRUE;
3720 markRelaxsUnsolved(set, relaxation);
3721 }
3722 }
3723
3724 return SCIP_OKAY;
3725}
3726
3727/** updates the cutoff, propagateagain, and solverelaxagain status of the current solving loop */
3728static
3730 SCIP_SET* set, /**< global SCIP settings */
3731 SCIP_STAT* stat, /**< dynamic problem statistics */
3732 SCIP_TREE* tree, /**< branch and bound tree */
3733 int depth, /**< depth of current node */
3734 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3735 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3736 SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if at least one relaxator should be called again */
3737 )
3738{
3739 SCIP_NODE* focusnode;
3740 int r;
3741
3742 assert(set != NULL);
3743 assert(stat != NULL);
3744 assert(cutoff != NULL);
3745 assert(propagateagain != NULL);
3746 assert(solverelaxagain != NULL);
3747
3748 /* check, if the path was cutoff */
3749 *cutoff = *cutoff || (tree->cutoffdepth <= depth);
3750
3751 /* check if branching was already performed */
3752 if( tree->nchildren == 0 )
3753 {
3754 /* check, if the focus node should be repropagated */
3755 focusnode = SCIPtreeGetFocusNode(tree);
3756 *propagateagain = *propagateagain || SCIPnodeIsPropagatedAgain(focusnode);
3757
3758 /* check, if one of the external relaxations should be solved again */
3759 for( r = 0; r < set->nrelaxs && !(*solverelaxagain); ++r )
3760 *solverelaxagain = *solverelaxagain || ( !SCIPrelaxIsSolved(set->relaxs[r], stat) );
3761 }
3762 else
3763 {
3764 /* if branching was performed, avoid another node loop iteration */
3765 *propagateagain = FALSE;
3766 *solverelaxagain = FALSE;
3767 }
3768}
3769
3770/** propagate domains and solve relaxation and lp */
3771static
3773 BMS_BLKMEM* blkmem, /**< block memory buffers */
3774 SCIP_SET* set, /**< global SCIP settings */
3775 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3776 SCIP_STAT* stat, /**< dynamic problem statistics */
3777 SCIP_MEM* mem, /**< block memory pools */
3778 SCIP_PROB* origprob, /**< original problem */
3779 SCIP_PROB* transprob, /**< transformed problem after presolve */
3780 SCIP_PRIMAL* primal, /**< primal data */
3781 SCIP_TREE* tree, /**< branch and bound tree */
3782 SCIP_REOPT* reopt, /**< reoptimization data structure */
3783 SCIP_LP* lp, /**< LP data */
3784 SCIP_RELAXATION* relaxation, /**< global relaxation data */
3785 SCIP_PRICESTORE* pricestore, /**< pricing storage */
3786 SCIP_SEPASTORE* sepastore, /**< separation storage */
3787 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3788 SCIP_CUTPOOL* cutpool, /**< global cut pool */
3789 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
3790 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3791 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
3792 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3793 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3794 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3795 SCIP_NODE* focusnode, /**< focused node */
3796 int actdepth, /**< depth in the b&b tree */
3797 SCIP_Bool propagate, /**< should we propagate */
3798 SCIP_Bool solvelp, /**< should we solve the lp */
3799 SCIP_Bool solverelax, /**< should we solve the relaxation */
3800 SCIP_Bool forcedlpsolve, /**< is there a need for a solve lp */
3801 SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
3802 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
3803 SCIP_Longint* afterlpproplps, /**< pointer to store the last LP count for which AFTERLP propagation was performed */
3804 SCIP_HEURTIMING* heurtiming, /**< timing for running heuristics after propagation call */
3805 int* nlperrors, /**< pointer to store the number of lp errors */
3806 SCIP_Bool* fullpropagation, /**< pointer to store whether we want to do a fullpropagation next time */
3807 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
3808 SCIP_Bool* lpsolved, /**< pointer to store whether the lp was solved */
3809 SCIP_Bool* relaxcalled, /**< pointer to store whether a relaxator was called; initialized with last loop's result */
3810 SCIP_Bool* solvelpagain, /**< pointer to store whether we want to solve the lp again */
3811 SCIP_Bool* solverelaxagain, /**< pointer to store whether we want to solve the relaxation again */
3812 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
3813 SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
3814 SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
3815 SCIP_Bool* stopped, /**< pointer to store whether solving was interrupted */
3816 SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
3817 SCIP_Bool* pricingaborted, /**< pointer to store TRUE, if the pricing was aborted and the lower bound must not be used */
3818 SCIP_Bool* forcedenforcement /**< pointer to store whether the enforcement of pseudo solution should be forced */
3819 )
3820{
3821 SCIP_Bool newinitconss;
3822
3823 assert(set != NULL);
3824 assert(stat != NULL);
3825 assert(origprob != NULL);
3826 assert(transprob != NULL);
3827 assert(tree != NULL);
3828 assert(lp != NULL);
3829 assert(primal != NULL);
3830 assert(pricestore != NULL);
3831 assert(sepastore != NULL);
3832 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3833 assert(branchcand != NULL);
3834 assert(cutpool != NULL);
3835 assert(delayedcutpool != NULL);
3836 assert(conflict != NULL);
3837 assert(SCIPconflictGetNConflicts(conflict) == 0);
3838 assert(eventfilter != NULL);
3839 assert(eventqueue != NULL);
3840 assert(focusnode != NULL);
3841 assert(heurtiming != NULL);
3842 assert(nlperrors != NULL);
3843 assert(fullpropagation != NULL);
3844 assert(propagateagain != NULL);
3845 assert(afterlpproplps != NULL);
3846 assert(lpsolved != NULL);
3847 assert(solvelpagain != NULL);
3848 assert(solverelaxagain != NULL);
3849 assert(cutoff != NULL);
3850 assert(postpone != NULL);
3851 assert(unbounded != NULL);
3852 assert(lperror != NULL);
3853 assert(pricingaborted != NULL);
3854 assert(forcedenforcement != NULL);
3855
3856 newinitconss = FALSE;
3857
3858 if( !(*cutoff) && !(*postpone) )
3859 {
3860 SCIP_Longint oldninitconssadded;
3861 SCIP_Longint oldnboundchgs;
3862 SCIP_Bool lpwasflushed;
3863
3864 lpwasflushed = lp->flushed;
3865 oldnboundchgs = stat->nboundchgs;
3866 oldninitconssadded = stat->ninitconssadded;
3867
3868 /* call after LP propagators */
3869 if( ((*afterlpproplps) < stat->nnodelps && (*lpsolved)) || (*relaxcalled) )
3870 {
3871 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3872 SCIP_PROPTIMING_AFTERLPLOOP, cutoff, postpone) );
3873 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3874
3875 /* check, if the path was cutoff */
3876 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3877 *afterlpproplps = stat->nnodelps;
3878 propagate = propagate || (stat->nboundchgs > oldnboundchgs);
3879 }
3880
3881 /* call before LP propagators */
3882 if( propagate && !(*cutoff) )
3883 {
3884 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3885 SCIP_PROPTIMING_BEFORELP, cutoff, postpone) );
3886 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3887 }
3888
3889 newinitconss = (stat->ninitconssadded != oldninitconssadded);
3890 *fullpropagation = FALSE;
3891
3892 /* check, if the path was cutoff */
3893 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3894
3895 /* if the LP was flushed and is now no longer flushed, a bound change occurred, and the LP has to be resolved;
3896 * we also have to solve the LP if new intial constraints were added which need to be added to the LP
3897 */
3898 solvelp = solvelp || (lpwasflushed && (!lp->flushed || newinitconss));
3899 solverelax = solverelax || newinitconss;
3900
3901 /* the number of bound changes was increased by the propagation call, thus the relaxation should be solved again */
3902 if( stat->nboundchgs > oldnboundchgs )
3903 {
3904 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
3905 * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
3906 * bound of the node needs to be updated
3907 */
3908 if( !solvelp && lp->flushed && lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
3909 {
3910 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
3911 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
3912 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
3913
3914 if( SCIPtreeHasFocusNodeLP(tree) )
3915 {
3916 /* update node estimate */
3917 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
3918
3919 if( actdepth == 0 && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
3920 SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
3921 }
3922 }
3923
3924 solverelax = TRUE;
3925 markRelaxsUnsolved(set, relaxation);
3926 }
3927
3928 /* update lower bound with the pseudo objective value, and cut off node by bounding */
3929 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
3930 conflict, cliquetable, cutoff) );
3931 }
3932 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3933
3934 if( *postpone )
3935 return SCIP_OKAY;
3936
3937 /* call primal heuristics that are applicable after propagation loop before lp solve;
3938 * the first time we go here, we call the before node heuristics instead
3939 */
3940 if( !(*cutoff) && !SCIPtreeProbing(tree) )
3941 {
3942 /* if the heuristics find a new incumbent solution, propagate again */
3943 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, *heurtiming,
3944 FALSE, propagateagain, unbounded) );
3945 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3946
3947 *heurtiming = SCIP_HEURTIMING_AFTERPROPLOOP;
3948
3949 /* check if primal heuristics found a solution and we therefore reached a solution limit */
3950 if( SCIPsolveIsStopped(set, stat, FALSE) )
3951 {
3952 /* cppcheck-suppress unassignedVariable */
3953 SCIP_NODE* node;
3954
3955 /* we reached a solution limit and do not want to continue the processing of the current node, but in order to
3956 * allow restarting the optimization process later, we need to create a "branching" with only one child node that
3957 * is a copy of the focusnode
3958 */
3960 SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) );
3961 assert(tree->nchildren >= 1);
3962 *stopped = TRUE;
3963 return SCIP_OKAY;
3964 }
3965
3966 /* if diving produced an LP error, switch back to non-LP node */
3967 if( lp->resolvelperror )
3968 {
3970 lp->resolvelperror = FALSE;
3971 }
3972
3973 if( *propagateagain )
3974 {
3975 *solvelpagain = solvelp;
3976 *solverelaxagain = solverelax;
3977
3978 return SCIP_OKAY;
3979 }
3980 }
3981
3982 /* solve external relaxations with non-negative priority */
3983 *relaxcalled = FALSE;
3984 if( solverelax && !(*cutoff) )
3985 {
3986 /* clear the storage of external branching candidates */
3988
3989 SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, TRUE,
3990 cutoff, propagateagain, solvelpagain, solverelaxagain, relaxcalled) );
3991 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3992
3993 /* check, if the path was cutoff */
3994 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3995
3996 /* apply found cuts */
3997 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
3998 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
3999 solvelpagain, solverelaxagain) );
4000
4001 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4002 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4003 }
4004 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4005
4006 /* check, if we want to solve the LP at this node */
4007 if( solvelp && !(*cutoff) && SCIPtreeHasFocusNodeLP(tree) )
4008 {
4009 *lperror = FALSE;
4010 *unbounded = FALSE;
4011
4012 /* solve the node's LP */
4013 SCIP_CALL( solveNodeLP(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation, pricestore,
4014 sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable,
4015 initiallpsolved, fullseparation, newinitconss, propagateagain, solverelaxagain, cutoff, unbounded, lperror, pricingaborted) );
4016
4017 *lpsolved = TRUE;
4018 *solvelpagain = FALSE;
4019 SCIPsetDebugMsg(set, " -> LP status: %d, LP obj: %g, iter: %" SCIP_LONGINT_FORMAT ", count: %" SCIP_LONGINT_FORMAT "\n",
4020 SCIPlpGetSolstat(lp),
4021 *cutoff ? SCIPsetInfinity(set) : (*lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob)),
4022 stat->nlpiterations, stat->lpcount);
4023
4024 /* check, if the path was cutoff */
4025 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
4026
4027 /* if an error occured during LP solving, switch to pseudo solution */
4028 if( *lperror )
4029 {
4030 if( forcedlpsolve )
4031 {
4032 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4033 stat->nnodes, stat->nlps);
4034 return SCIP_LPERROR;
4035 }
4037 ++(*nlperrors);
4038 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
4039 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4040 stat->nnodes, stat->nlps, *nlperrors);
4041 }
4042
4044 {
4046 *forcedenforcement = TRUE;
4047
4048 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
4049 "(node %" SCIP_LONGINT_FORMAT ") LP solver hit %s limit in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead\n",
4050 stat->nnodes, SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT ? "time" : "iteration", stat->nlps);
4051 }
4052
4054 {
4055 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4056 "(node %" SCIP_LONGINT_FORMAT ") LP relaxation is unbounded (LP %" SCIP_LONGINT_FORMAT ")\n", stat->nnodes, stat->nlps);
4057 }
4058
4059 /* if we solve exactly, the LP claims to be infeasible but the infeasibility could not be proved,
4060 * we have to forget about the LP and use the pseudo solution instead
4061 */
4062 if( !(*cutoff) && !(*lperror) && (set->misc_exactsolve || *pricingaborted) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE
4063 && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound )
4064 {
4065 if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 && transprob->ncontvars > 0 )
4066 {
4067 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",
4068 stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, transprob->ncontvars);
4069 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") -> have to call PerPlex() (feature not yet implemented)\n", stat->nnodes);
4070 /**@todo call PerPlex */
4071 return SCIP_LPERROR;
4072 }
4073 else
4074 {
4076 *forcedenforcement = TRUE;
4077
4078 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4079 "(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",
4080 stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, SCIPbranchcandGetNPseudoCands(branchcand));
4081 }
4082 }
4083
4084 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4085 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
4086 cliquetable, cutoff) );
4087 }
4088 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4089 assert(*cutoff || !SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
4090
4091 /* reset solverelaxagain if no relaxations were solved up to this point (the LP-changes are already included in
4092 * relaxators called after the LP)
4093 */
4094 *solverelaxagain = *solverelaxagain && *relaxcalled;
4095
4096 /* solve external relaxations with negative priority */
4097 if( solverelax && !(*cutoff) )
4098 {
4099 SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, FALSE, cutoff,
4100 propagateagain, solvelpagain, solverelaxagain, relaxcalled) );
4101 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4102
4103 /* check, if the path was cutoff */
4104 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
4105
4106 /* apply found cuts */
4107 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4108 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
4109 solvelpagain, solverelaxagain) );
4110
4111 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4112 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
4113 cliquetable, cutoff) );
4114 }
4115 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4116
4117 return SCIP_OKAY;
4118}
4119
4120/** check if a restart can be performed */
4121#ifndef NDEBUG
4122static
4124 SCIP_SET* set, /**< global SCIP settings */
4125 SCIP_STAT* stat /**< dynamic problem statistics */
4126 )
4127{
4128 assert(set != NULL);
4129 assert(stat != NULL);
4130
4131 return set->nactivepricers == 0 && !set->reopt_enable
4132 && ( set->presol_maxrestarts == -1 || stat->nruns <= set->presol_maxrestarts );
4133}
4134#else
4135#define restartAllowed(set,stat) ((set)->nactivepricers == 0 && !set->reopt_enable && ((set)->presol_maxrestarts == -1 || (stat)->nruns <= (set)->presol_maxrestarts))
4136#endif
4137
4138/** solves the focus node */
4139static
4141 BMS_BLKMEM* blkmem, /**< block memory buffers */
4142 SCIP_SET* set, /**< global SCIP settings */
4143 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4144 SCIP_STAT* stat, /**< dynamic problem statistics */
4145 SCIP_MEM* mem, /**< block memory pools */
4146 SCIP_PROB* origprob, /**< original problem */
4147 SCIP_PROB* transprob, /**< transformed problem after presolve */
4148 SCIP_PRIMAL* primal, /**< primal data */
4149 SCIP_TREE* tree, /**< branch and bound tree */
4150 SCIP_REOPT* reopt, /**< reoptimization data structure */
4151 SCIP_LP* lp, /**< LP data */
4152 SCIP_RELAXATION* relaxation, /**< global relaxation data */
4153 SCIP_PRICESTORE* pricestore, /**< pricing storage */
4154 SCIP_SEPASTORE* sepastore, /**< separation storage */
4155 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4156 SCIP_CUTPOOL* cutpool, /**< global cut pool */
4157 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
4158 SCIP_CONFLICT* conflict, /**< conflict analysis data */
4159 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4160 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4161 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4162 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4163 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
4164 SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
4165 SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
4166 SCIP_Bool* infeasible, /**< pointer to store whether the focus node's solution is infeasible */
4167 SCIP_Bool* restart, /**< should solving process be started again with presolving? */
4168 SCIP_Bool* afternodeheur, /**< pointer to store whether AFTERNODE heuristics were already called */
4169 SCIP_Bool* stopped /**< pointer to store whether solving was interrupted */
4170 )
4171{
4172 SCIP_NODE* focusnode;
4173 SCIP_Longint lastdomchgcount;
4174 SCIP_Longint afterlpproplps;
4175 SCIP_Real restartfac;
4176 SCIP_Longint lastlpcount;
4177 SCIP_HEURTIMING heurtiming;
4178 int actdepth;
4179 int nlperrors;
4180 int nloops;
4181 SCIP_Bool foundsol;
4182 SCIP_Bool focusnodehaslp;
4183 SCIP_Bool lpsolved;
4184 SCIP_Bool initiallpsolved;
4185 SCIP_Bool fullseparation;
4186 SCIP_Bool solverelaxagain;
4187 SCIP_Bool solvelpagain;
4188 SCIP_Bool propagateagain;
4189 SCIP_Bool fullpropagation;
4190 SCIP_Bool branched;
4191 SCIP_Bool forcedlpsolve;
4192 SCIP_Bool wasforcedlpsolve;
4193 SCIP_Bool pricingaborted;
4194
4195 assert(set != NULL);
4196 assert(stat != NULL);
4197 assert(origprob != NULL);
4198 assert(transprob != NULL);
4199 assert(tree != NULL);
4200 assert(primal != NULL);
4201 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4202 assert(SCIPconflictGetNConflicts(conflict) == 0);
4203 assert(cutoff != NULL);
4204 assert(postpone != NULL);
4205 assert(unbounded != NULL);
4206 assert(infeasible != NULL);
4207 assert(restart != NULL);
4208 assert(afternodeheur != NULL);
4209
4210 *cutoff = FALSE;
4211 *postpone = FALSE;
4212 *unbounded = FALSE;
4213 *infeasible = FALSE;
4214 *restart = FALSE;
4215 *afternodeheur = FALSE;
4216 *stopped = FALSE;
4217 pricingaborted = FALSE;
4218
4219 focusnode = SCIPtreeGetFocusNode(tree);
4220 assert(focusnode != NULL);
4221 assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
4222 actdepth = SCIPnodeGetDepth(focusnode);
4223
4224 /* invalidate relaxation solution */
4226
4227 /* clear the storage of external branching candidates */
4229
4230 SCIPsetDebugMsg(set, "Processing node %" SCIP_LONGINT_FORMAT " in depth %d, %d siblings\n",
4231 stat->nnodes, actdepth, tree->nsiblings);
4232 SCIPsetDebugMsg(set, "current pseudosolution: obj=%g\n", SCIPlpGetPseudoObjval(lp, set, transprob));
4233 /*debug(SCIPprobPrintPseudoSol(transprob, set));*/
4234
4235 /* check, if we want to solve the LP at the selected node:
4236 * - solve the LP, if the lp solve depth and frequency demand solving
4237 * - solve the root LP, if the LP solve frequency is set to 0
4238 * - solve the root LP, if there are continuous variables present
4239 * - don't solve the node if its cut off by the pseudo objective value anyway
4240 */
4241 focusnodehaslp = (set->lp_solvedepth == -1 || actdepth <= set->lp_solvedepth);
4242 focusnodehaslp = focusnodehaslp && (set->lp_solvefreq >= 1 && actdepth % set->lp_solvefreq == 0);
4243 focusnodehaslp = focusnodehaslp || (actdepth == 0 && set->lp_solvefreq == 0);
4244 focusnodehaslp = focusnodehaslp && SCIPsetIsLT(set, SCIPlpGetPseudoObjval(lp, set, transprob), primal->cutoffbound);
4245 focusnodehaslp = set->reopt_enable ? focusnodehaslp && SCIPreoptGetSolveLP(reopt, set, focusnode) : focusnodehaslp;
4246 SCIPtreeSetFocusNodeLP(tree, focusnodehaslp);
4247
4248 /* external node solving loop:
4249 * - propagate domains
4250 * - solve SCIP_LP
4251 * - enforce constraints
4252 * if a constraint handler adds constraints to enforce its own constraints, both, propagation and LP solving
4253 * is applied again (if applicable on current node); however, if the new constraints don't have the enforce flag set,
4254 * it is possible, that the current infeasible solution is not cut off; in this case, we have to declare the solution
4255 * infeasible and perform a branching
4256 */
4257 lastdomchgcount = stat->domchgcount;
4258 lastlpcount = stat->lpcount;
4259 initiallpsolved = FALSE;
4260 fullseparation = TRUE;
4261 heurtiming = SCIP_HEURTIMING_BEFORENODE;
4262 nlperrors = 0;
4263 stat->npricerounds = 0;
4264 stat->nseparounds = 0;
4265 solverelaxagain = TRUE;
4266 solvelpagain = TRUE;
4267 propagateagain = TRUE;
4268 fullpropagation = TRUE;
4269 forcedlpsolve = FALSE;
4270 nloops = 0;
4271
4272 while( !(*cutoff) && !(*postpone) && (solverelaxagain || solvelpagain || propagateagain) && nlperrors < MAXNLPERRORS && !(*restart) )
4273 {
4274 SCIP_Bool lperror;
4275 SCIP_Bool solverelax;
4276 SCIP_Bool solvelp;
4277 SCIP_Bool propagate;
4278 SCIP_Bool forcedenforcement;
4279 SCIP_Bool relaxcalled;
4280
4281 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4282
4283 *unbounded = FALSE;
4284 *infeasible = FALSE;
4285 foundsol = FALSE;
4286
4287 nloops++;
4288 lperror = FALSE;
4289 lpsolved = FALSE;
4290 relaxcalled = FALSE;
4291 forcedenforcement = FALSE;
4292 afterlpproplps = -1L;
4293
4294 while( !lperror && !(*cutoff) && (propagateagain || solvelpagain || solverelaxagain
4295 || (afterlpproplps < stat->nnodelps && lpsolved) || relaxcalled) )
4296 {
4297 solverelax = solverelaxagain;
4298 solverelaxagain = FALSE;
4299 solvelp = solvelpagain;
4300 solvelpagain = FALSE;
4301 propagate = propagateagain;
4302 propagateagain = FALSE;
4303
4304 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4305 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
4306 conflict, cliquetable, cutoff) );
4307
4308 /* propagate domains before lp solving and solve relaxation and lp */
4309 SCIPsetDebugMsg(set, " -> node solving loop: call propagators that are applicable before%s LP is solved\n",
4310 lpsolved ? " and after" : "");
4311 SCIP_CALL( propAndSolve(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp,
4312 relaxation, pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter,
4313 eventqueue, cliquetable, focusnode, actdepth, propagate, solvelp, solverelax, forcedlpsolve, initiallpsolved,
4314 fullseparation, &afterlpproplps, &heurtiming, &nlperrors, &fullpropagation, &propagateagain, &lpsolved, &relaxcalled,
4315 &solvelpagain, &solverelaxagain, cutoff, postpone, unbounded, stopped, &lperror, &pricingaborted, &forcedenforcement) );
4316 initiallpsolved |= lpsolved;
4317
4318 /* time or solution limit was hit and we already created a dummy child node to terminate fast */
4319 if( *stopped )
4320 {
4321 /* reset LP feastol to normal value, in case someone tightened it during node solving */
4323 return SCIP_OKAY;
4324 }
4325 }
4326 fullseparation = FALSE;
4327
4328 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4329 updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain);
4330
4331 /* call primal heuristics that should be applied after the LP relaxation of the node was solved;
4332 * if this is the first loop of the root node, call also AFTERNODE heuristics already here, since they might help
4333 * to improve the primal bound, thereby producing additional reduced cost strengthenings and strong branching
4334 * bound fixings which also might lead to a restart
4335 */
4336 if( !(*postpone) && (!(*cutoff) || SCIPtreeGetNNodes(tree) > 0) )
4337 {
4338 if( actdepth == 0 && !(*afternodeheur) )
4339 {
4340 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL,
4341 SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE, *cutoff, &foundsol, unbounded) );
4342 *afternodeheur = TRUE; /* the AFTERNODE heuristics should not be called again after the node */
4343 }
4344 else if( lpsolved || SCIPrelaxationIsSolValid(relaxation) )
4345 {
4346 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_AFTERLPLOOP,
4347 *cutoff, &foundsol, unbounded) );
4348 }
4349 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4350
4351 /* heuristics might have found a solution or set the cutoff bound such that the current node is cut off */
4352 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4353 }
4354
4355 /* check if heuristics leave us with an invalid LP */
4356 if( lp->resolvelperror )
4357 {
4358 if( forcedlpsolve )
4359 {
4360 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4361 stat->nnodes, stat->nlps);
4362 return SCIP_LPERROR;
4363 }
4365 lp->resolvelperror = FALSE;
4366 nlperrors++;
4367 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4368 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4369 stat->nnodes, stat->nlps, nlperrors);
4370 }
4371
4372 if( pricingaborted && !(*cutoff) && SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL )
4373 {
4375
4376 /* if we just ran into the time limit this is not really a numerical trouble;
4377 * however, if this is not the case, we print messages about numerical troubles in the current LP
4378 */
4379 if( !SCIPsolveIsStopped(set, stat, FALSE) )
4380 {
4381 if( forcedlpsolve )
4382 {
4383 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4384 stat->nnodes, stat->nlps);
4385 return SCIP_LPERROR;
4386 }
4387 nlperrors++;
4388 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4389 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4390 stat->nnodes, stat->nlps, nlperrors);
4391 }
4392 }
4393
4394 /* if an improved solution was found, propagate and solve the relaxations again */
4395 if( foundsol && !(*cutoff) )
4396 {
4397 propagateagain = TRUE;
4398 solvelpagain = TRUE;
4399 solverelaxagain = TRUE;
4400 markRelaxsUnsolved(set, relaxation);
4401 }
4402
4403 /* check for immediate restart */
4404 *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart
4405 || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars)
4406 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4407
4408 /* enforce constraints */
4409 branched = FALSE;
4410 if( !(*postpone) && !(*restart) && !(*cutoff) && !solverelaxagain && !solvelpagain && !propagateagain )
4411 {
4412 /* if the solution changed since the last enforcement, we have to completely reenforce it; otherwise, we
4413 * only have to enforce the additional constraints added in the last enforcement, but keep the infeasible
4414 * flag TRUE in order to not declare the infeasible solution feasible due to disregarding the already
4415 * enforced constraints
4416 */
4417 if( lastdomchgcount != stat->domchgcount || lastlpcount != stat->lpcount )
4418 {
4419 lastdomchgcount = stat->domchgcount;
4420 lastlpcount = stat->lpcount;
4421 *infeasible = FALSE;
4422 }
4423
4424 /* call constraint enforcement */
4425 SCIP_CALL( enforceConstraints(blkmem, set, messagehdlr, stat, transprob, primal, tree, lp, relaxation, sepastore,
4426 branchcand, &branched, cutoff, infeasible, &propagateagain, &solvelpagain, &solverelaxagain,
4427 forcedenforcement) );
4428 assert(branched == (tree->nchildren > 0));
4429 assert(!branched || (!(*cutoff) && *infeasible && !propagateagain && !solvelpagain));
4430 assert(!(*cutoff) || (!branched && *infeasible && !propagateagain && !solvelpagain));
4431 assert(*infeasible || (!branched && !(*cutoff) && !propagateagain && !solvelpagain));
4432 assert(!propagateagain || (!branched && !(*cutoff) && *infeasible));
4433 assert(!solvelpagain || (!branched && !(*cutoff) && *infeasible));
4434
4435 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4436
4437 /* apply found cuts */
4438 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4439 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain,
4440 &solvelpagain, &solverelaxagain) );
4441
4442 /* update lower bound with the pseudo objective value, and cut off node by bounding */
4443 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4444
4445 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4446 updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain);
4447 }
4448 assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4449
4450 /* The enforcement detected no infeasibility, so, no branching was performed,
4451 * but the pricing was aborted and the current feasible solution does not have to be the
4452 * best solution in the current subtree --> we have to do a pseudo branching,
4453 * so we set infeasible TRUE and add the current solution to the solution pool
4454 */
4455 if( pricingaborted && !(*infeasible) && !(*cutoff) && !(*postpone) && !(*restart) )
4456 {
4457 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
4458 SCIP_SOL* sol;
4459 SCIP_Bool stored;
4460
4461 /* in case the relaxation was enforced add this solution, otherwise decide between LP and pseudosol */
4463 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4464 {
4465 SCIP_SOL* relaxsol;
4466
4467 SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4468
4469 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4470 eventqueue, eventfilter, relaxsol, FALSE, FALSE, TRUE, TRUE, TRUE,
4471 &stored) );
4472
4473 SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
4474
4475 if( stored )
4476 {
4477 stat->nrelaxsolsfound++;
4478
4479 if( primal->nbestsolsfound != oldnbestsolsfound )
4480 {
4481 stat->nrelaxbestsolsfound++;
4483 }
4484 }
4485 }
4486 else
4487 {
4488 SCIP_CALL( SCIPsolCreateCurrentSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4489 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4490 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
4491
4492 if( stored )
4493 {
4494 stat->nlpsolsfound++;
4495
4496 if( primal->nbestsolsfound != oldnbestsolsfound )
4497 {
4498 stat->nlpbestsolsfound++;
4500 }
4501 }
4502 }
4503
4504 *infeasible = TRUE;
4505 }
4506
4507 /* if the node is infeasible, but no constraint handler could resolve the infeasibility
4508 * -> branch on LP, external candidates, or the pseudo solution
4509 * -> e.g. select non-fixed binary or integer variable x with value x', create three
4510 * sons: x <= x'-1, x = x', and x >= x'+1.
4511 * In the left and right branch, the current solution is cut off. In the middle
4512 * branch, the constraints can hopefully reduce domains of other variables to cut
4513 * off the current solution.
4514 * In LP branching, we cannot allow adding constraints, because this does not necessary change the LP and can
4515 * therefore lead to an infinite loop.
4516 */
4517 wasforcedlpsolve = forcedlpsolve;
4518 forcedlpsolve = FALSE;
4519 if( (*infeasible) && !(*cutoff) && !(*postpone) && !(*restart)
4520 && (!(*unbounded) || SCIPbranchcandGetNExternCands(branchcand) > 0 || SCIPbranchcandGetNPseudoCands(branchcand) > 0)
4521 && !solverelaxagain && !solvelpagain && !propagateagain && !branched )
4522 {
4523 SCIP_RESULT result = SCIP_DIDNOTRUN;
4524 int nlpcands = 0;
4525
4526 if( SCIPtreeHasFocusNodeLP(tree) )
4527 {
4528 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpcands, NULL, NULL) );
4529 }
4530
4531 if ( nlpcands > 0 || SCIPbranchcandGetNExternCands(branchcand) > 0 )
4532 {
4533 /* If there are LP candidates and their maximal priority is at least the maximal priority of the external
4534 * candidates, then branch on the LP candidates. Note that due to implicit integer variables,
4535 * SCIPbranchcandGetLPMaxPrio(branchcand) might be finite and SCIPbranchcandGetNPrioLPCands(branchcand) > 0,
4536 * but nlpcands == 0. */
4537 if ( SCIPbranchcandGetLPMaxPrio(branchcand) >= SCIPbranchcandGetExternMaxPrio(branchcand) && nlpcands > 0 )
4538 {
4539 assert( SCIPbranchcandGetNPrioLPCands(branchcand) > 0 );
4540 assert( nlpcands > 0 );
4541
4542 /* branch on LP solution */
4543 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on LP solution with %d fractionals\n",
4544 SCIPnodeGetDepth(focusnode), nlpcands);
4545 SCIP_CALL( SCIPbranchExecLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4546 eventqueue, primal->cutoffbound, FALSE, &result) );
4547 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4548 assert(result != SCIP_DIDNOTRUN && result != SCIP_DIDNOTFIND);
4549 }
4550 else
4551 {
4552 assert( SCIPbranchcandGetNPrioExternCands(branchcand) > 0 );
4553 assert( SCIPbranchcandGetNExternCands(branchcand) > 0 );
4554
4555 /* branch on external candidates */
4556 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on %d external branching candidates.\n",
4557 SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNExternCands(branchcand));
4558 SCIP_CALL( SCIPbranchExecExtern(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4559 eventqueue, primal->cutoffbound, TRUE, &result) );
4560 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4561 }
4562 }
4563
4564 if( result == SCIP_DIDNOTRUN || result == SCIP_DIDNOTFIND )
4565 {
4566 /* branch on pseudo solution */
4567 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on pseudo solution with %d unfixed integers\n",
4568 SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNPseudoCands(branchcand));
4569 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
4570 primal->cutoffbound, TRUE, &result) );
4571 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4572 }
4573
4574 /* SCIP cannot guarantee convergence if it is necessary to branch on unbounded variables */
4575 if( result == SCIP_BRANCHED )
4576 {
4577 SCIP_VAR* var = stat->lastbranchvar;
4578
4579 if( var != NULL && !stat->branchedunbdvar && SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS
4581 {
4582 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
4583 "Starting spatial branch-and-bound on unbounded variable <%s> ([%g,%g]) - cannot guarantee finite termination.\n",
4585 stat->branchedunbdvar = TRUE;
4586 }
4587 }
4588
4589 switch( result )
4590 {
4591 case SCIP_CUTOFF:
4592 assert(tree->nchildren == 0);
4593 *cutoff = TRUE;
4594 SCIPsetDebugMsg(set, " -> branching rule detected cutoff\n");
4595 break;
4596 case SCIP_CONSADDED:
4597 assert(tree->nchildren == 0);
4598 if( nlpcands > 0 )
4599 {
4600 SCIPerrorMessage("LP branching rule added constraint, which was not allowed this time\n");
4601 return SCIP_INVALIDRESULT;
4602 }
4603 propagateagain = TRUE;
4604 solvelpagain = TRUE;
4605 solverelaxagain = TRUE;
4606 markRelaxsUnsolved(set, relaxation);
4607 break;
4608 case SCIP_REDUCEDDOM:
4609 assert(tree->nchildren == 0);
4610 propagateagain = TRUE;
4611 solvelpagain = TRUE;
4612 solverelaxagain = TRUE;
4613 markRelaxsUnsolved(set, relaxation);
4614 break;
4615 case SCIP_SEPARATED:
4616 assert(tree->nchildren == 0);
4617 assert(SCIPsepastoreGetNCuts(sepastore) > 0);
4618 solvelpagain = TRUE;
4619 solverelaxagain = TRUE;
4620 markRelaxsUnsolved(set, relaxation);
4621 break;