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