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-2018 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 v;
1187 
1188  assert(set != NULL);
1189  assert(transprob != NULL);
1190  assert(lp != NULL);
1191  assert(cutoff != NULL);
1192 
1193  *cutoff = FALSE;
1194 
1195  /* at the root node, we have to add the initial variables as columns */
1196  if( root )
1197  {
1198  assert(SCIPlpGetNCols(lp) == 0);
1199  assert(SCIPlpGetNRows(lp) == 0);
1200  assert(lp->nremovablecols == 0);
1201  assert(lp->nremovablerows == 0);
1202 
1203  /* inform pricing storage, that LP is now filled with initial data */
1204  SCIPpricestoreStartInitialLP(pricestore);
1205 
1206  /* add all initial variables to LP */
1207  SCIPsetDebugMsg(set, "init LP: initial columns\n");
1208  for( v = 0; v < transprob->nvars && !(*cutoff); ++v )
1209  {
1210  var = transprob->vars[v];
1211  assert(SCIPvarGetProbindex(var) >= 0);
1212 
1213  if( SCIPvarIsInitial(var) )
1214  {
1215  SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, 0.0, TRUE) );
1216  }
1217 
1218  /* check for empty domains (necessary if no presolving was performed) */
1219  if( SCIPsetIsGT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1220  *cutoff = TRUE;
1221  }
1222  assert(lp->nremovablecols == 0);
1223  SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) );
1224 
1225  /* inform pricing storage, that initial LP setup is now finished */
1226  SCIPpricestoreEndInitialLP(pricestore);
1227  }
1228 
1229  if( *cutoff )
1230  return SCIP_OKAY;
1231 
1232  /* put all initial constraints into the LP */
1233  /* @todo check whether we jumped through the tree */
1234  SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
1235  eventfilter, cliquetable, root, TRUE, cutoff) );
1236 
1237  return SCIP_OKAY;
1238 }
1239 
1240 /** constructs the LP of the current node, but does not load the LP state and warmstart information */
1242  BMS_BLKMEM* blkmem, /**< block memory buffers */
1243  SCIP_SET* set, /**< global SCIP settings */
1244  SCIP_STAT* stat, /**< dynamic problem statistics */
1245  SCIP_PROB* transprob, /**< transformed problem */
1246  SCIP_PROB* origprob, /**< original problem */
1247  SCIP_TREE* tree, /**< branch and bound tree */
1248  SCIP_REOPT* reopt, /**< reoptimization data structure */
1249  SCIP_LP* lp, /**< LP data */
1250  SCIP_PRICESTORE* pricestore, /**< pricing storage */
1251  SCIP_SEPASTORE* sepastore, /**< separation storage */
1252  SCIP_CUTPOOL* cutpool, /**< global cutpool */
1253  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1254  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1255  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1256  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1257  SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
1258  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1259  )
1260 {
1261  SCIP_Bool initroot = FALSE;
1262 
1263  assert(tree != NULL);
1264  assert(cutoff != NULL);
1265 
1266  *cutoff = FALSE;
1267 
1269  {
1270  /* inform separation storage, that LP is now filled with initial data */
1271  SCIPsepastoreStartInitialLP(sepastore);
1272 
1273  if( tree->correctlpdepth >= 0 )
1274  {
1275  int i;
1276 
1277  for( i = tree->pathnlprows[tree->correctlpdepth]; i < lp->nrows; ++i )
1278  {
1279  /* keep all active global cuts that where applied in the previous node in the lp */
1280  if( !lp->rows[i]->local && lp->rows[i]->age == 0 )
1281  {
1282  SCIP_CALL( SCIPsepastoreAddCut(sepastore, blkmem, set, stat, eventqueue, eventfilter, lp, lp->rows[i], TRUE, (SCIPtreeGetCurrentDepth(tree) == 0), cutoff) );
1283  }
1284  }
1285  }
1286 
1287  if( !(*cutoff) )
1288  {
1289  /* load the LP into the solver and load the LP state */
1290  SCIPsetDebugMsg(set, "loading LP\n");
1291  SCIP_CALL( SCIPtreeLoadLP(tree, blkmem, set, eventqueue, eventfilter, lp, &initroot) );
1292  assert(initroot || SCIPnodeGetDepth(SCIPtreeGetFocusNode(tree)) > 0);
1293  assert(SCIPtreeIsFocusNodeLPConstructed(tree));
1294 
1295  /* apply cuts */
1296  SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
1297  eventqueue, eventfilter, cliquetable, (SCIPtreeGetCurrentDepth(tree) == 0), SCIP_EFFICIACYCHOICE_LP, cutoff) );
1298  }
1299  else
1300  {
1301  /* the current node will be cut off; we clear the sepastore */
1302  SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
1303  }
1304 
1305  /* inform separation storage, that initial LP setup is now finished */
1306  SCIPsepastoreEndInitialLP(sepastore);
1307 
1308  if( !(*cutoff) )
1309  {
1310  /* setup initial LP relaxation of node */
1311  SCIP_CALL( initLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, pricestore, sepastore, cutpool, branchcand,
1312  eventqueue, eventfilter, cliquetable, initroot, cutoff) );
1313  }
1314  }
1315  else if( newinitconss )
1316  {
1317  SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob,
1318  origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE,
1319  cutoff) );
1320  }
1321 
1322  return SCIP_OKAY;
1323 }
1324 
1325 /** updates the primal ray stored in primal data
1326  * clears previously stored primal ray, if existing and there was no LP error
1327  * stores current primal ray, if LP is unbounded and there has been no error
1328  */
1329 static
1331  BMS_BLKMEM* blkmem, /**< block memory buffers */
1332  SCIP_SET* set, /**< global SCIP settings */
1333  SCIP_STAT* stat, /**< dynamic problem statistics */
1334  SCIP_PROB* prob, /**< transformed problem after presolve */
1335  SCIP_PRIMAL* primal, /**< primal data */
1336  SCIP_TREE* tree, /**< branch and bound tree */
1337  SCIP_LP* lp, /**< LP data */
1338  SCIP_Bool lperror /**< has there been an LP error? */
1339  )
1340 {
1341  assert(blkmem != NULL);
1342  assert(set != NULL);
1343  assert(stat != NULL);
1344  assert(prob != NULL);
1345  assert(primal != NULL);
1346  assert(tree != NULL);
1347  assert(lp != NULL);
1348 
1349  if( lperror )
1350  return SCIP_OKAY;
1351 
1352  /* clear previously stored primal ray, if any */
1353  if( primal->primalray != NULL )
1354  {
1355  SCIP_CALL( SCIPsolFree(&primal->primalray, blkmem, primal) );
1356  }
1357 
1358  /* store unbounded ray, if LP is unbounded */
1360  {
1361  SCIP_VAR** vars;
1362  SCIP_Real* ray;
1363  int nvars;
1364  int i;
1365 
1366  SCIPsetDebugMsg(set, "LP is unbounded, store primal ray\n");
1367 
1368  vars = prob->vars;
1369  nvars = prob->nvars;
1370 
1371  /* get buffer memory for storing the ray and load the ray values into it */
1372  SCIP_CALL( SCIPsetAllocBufferArray(set, &ray, nvars) );
1373  BMSclearMemoryArray(ray, nvars);
1374  SCIP_CALL( SCIPlpGetPrimalRay(lp, set, ray) );
1375 
1376  /* create solution to store the primal ray in */
1377  assert(primal->primalray == NULL);
1378  SCIP_CALL( SCIPsolCreate(&primal->primalray, blkmem, set, stat, primal, tree, NULL) );
1379 
1380  /* set values of all active variable in the solution that represents the primal ray */
1381  for( i = 0; i < nvars; i++ )
1382  {
1383  SCIP_CALL( SCIPsolSetVal(primal->primalray, set, stat, tree, vars[i], ray[i]) );
1384  }
1385 
1386  SCIPdebug( SCIP_CALL( SCIPprintRay(set->scip, primal->primalray, NULL, FALSE) ) );
1387 
1388  /* free memory for buffering the ray values */
1389  SCIPsetFreeBufferArray(set, &ray);
1390  }
1391 
1392  return SCIP_OKAY;
1393 }
1394 
1395 /** load and solve the initial LP of a node */
1396 static
1398  BMS_BLKMEM* blkmem, /**< block memory buffers */
1399  SCIP_SET* set, /**< global SCIP settings */
1400  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1401  SCIP_STAT* stat, /**< dynamic problem statistics */
1402  SCIP_PROB* transprob, /**< transformed problem after presolve */
1403  SCIP_PROB* origprob, /**< original problem */
1404  SCIP_PRIMAL* primal, /**< primal data */
1405  SCIP_TREE* tree, /**< branch and bound tree */
1406  SCIP_REOPT* reopt, /**< reoptimization data structure */
1407  SCIP_LP* lp, /**< LP data */
1408  SCIP_PRICESTORE* pricestore, /**< pricing storage */
1409  SCIP_SEPASTORE* sepastore, /**< separation storage */
1410  SCIP_CUTPOOL* cutpool, /**< global cutpool */
1411  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1412  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1413  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1414  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1415  SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
1416  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
1417  SCIP_Bool* lperror /**< pointer to store whether an unresolved error in LP solving occured */
1418  )
1419 {
1420  /* initializing variables for compiler warnings, which are not correct */
1421  SCIP_Real starttime = 0.0;
1422  SCIP_Longint nlpiterations = 0;
1423  SCIP_NODE* focusnode;
1424 
1425  assert(stat != NULL);
1426  assert(tree != NULL);
1427  assert(lp != NULL);
1428  assert(cutoff != NULL);
1429  assert(lperror != NULL);
1430  assert(SCIPtreeGetFocusNode(tree) != NULL);
1432 
1433  *cutoff = FALSE;
1434  *lperror = FALSE;
1435 
1436  /* load the LP into the solver */
1437  SCIP_CALL( SCIPconstructCurrentLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, pricestore, sepastore, cutpool,
1438  branchcand, eventqueue, eventfilter, cliquetable, newinitconss, cutoff) );
1439 
1440  if( *cutoff )
1441  return SCIP_OKAY;
1442 
1443  /* load the LP state */
1444  SCIP_CALL( SCIPtreeLoadLPState(tree, blkmem, set, stat, eventqueue, lp) );
1445 
1446  focusnode = SCIPtreeGetFocusNode(tree);
1447 
1448  /* store current LP iteration count and solving time if we are at the root node */
1449  if( focusnode->depth == 0 )
1450  {
1451  nlpiterations = stat->nlpiterations;
1452  starttime = SCIPclockGetTime(stat->solvingtime);
1453  }
1454 
1455  /* solve initial LP */
1456  SCIPsetDebugMsg(set, "node: solve initial LP\n");
1457  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
1458  SCIPnodeGetDepth(SCIPtreeGetFocusNode(tree)) == 0 ? set->lp_rootiterlim : set->lp_iterlim, TRUE, TRUE, FALSE, lperror) );
1459  assert(lp->flushed);
1460  assert(lp->solved || *lperror);
1461 
1462  /* save time for very first LP in root node */
1463  if ( stat->nnodelps == 0 && focusnode->depth == 0 )
1464  {
1465  stat->firstlptime = SCIPclockGetTime(stat->solvingtime) - starttime;
1466  }
1467 
1468  /* remove previous primal ray, store new one if LP is unbounded */
1469  SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
1470 
1471  if( !(*lperror) )
1472  {
1473  /* cppcheck-suppress unassignedVariable */
1474  SCIP_EVENT event;
1475 
1477  {
1478  /* issue FIRSTLPSOLVED event */
1481  SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
1482  }
1483 
1484  /* update pseudo cost values for integer variables (always) and for continuous variables (if not delayed) */
1485  SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, TRUE, !set->branch_delaypscost) );
1486 
1487  /* update lower bound of current node w.r.t. initial lp */
1488  assert(!(*cutoff));
1491  && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
1492  {
1493  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
1494 
1495  /* if this is the first LP solved at the root, store its iteration count and solution value */
1496  if( stat->nnodelps == 0 && focusnode->depth == 0 )
1497  {
1498  SCIP_Real lowerbound;
1499 
1500  assert(stat->nrootfirstlpiterations == 0);
1501  stat->nrootfirstlpiterations = stat->nlpiterations - nlpiterations;
1502 
1503  if( set->misc_exactsolve )
1504  {
1505  SCIP_CALL( SCIPlpGetProvedLowerbound(lp, set, &lowerbound) );
1506  }
1507  else
1508  lowerbound = SCIPlpGetObjval(lp, set, transprob);
1509 
1510  stat->firstlpdualbound = SCIPprobExternObjval(transprob, origprob, set, lowerbound);
1511  }
1512  }
1513  }
1514 
1515  return SCIP_OKAY;
1516 }
1517 
1518 /** makes sure the LP is flushed and solved */
1519 static
1521  BMS_BLKMEM* blkmem, /**< block memory buffers */
1522  SCIP_SET* set, /**< global SCIP settings */
1523  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1524  SCIP_STAT* stat, /**< dynamic problem statistics */
1525  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1526  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1527  SCIP_PROB* prob, /**< transformed problem after presolve */
1528  SCIP_PRIMAL* primal, /**< primal data */
1529  SCIP_TREE* tree, /**< branch and bound tree */
1530  SCIP_LP* lp, /**< LP data */
1531  SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
1532  SCIP_Bool* mustsepa, /**< pointer to store TRUE if additional separation rounds should be performed */
1533  SCIP_Bool* mustprice /**< pointer to store TRUE if additional pricing rounds should be performed */
1534  )
1535 {
1536  assert(lp != NULL);
1537  assert(lperror != NULL);
1538  assert(mustsepa != NULL);
1539  assert(mustprice != NULL);
1540 
1541  /* if bound changes were applied in the separation round, we have to resolve the LP */
1542  if( !lp->flushed )
1543  {
1544  /* solve LP (with dual simplex) */
1545  SCIPsetDebugMsg(set, "separation: resolve LP\n");
1546  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, prob, set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
1547  assert(lp->flushed);
1548  assert(lp->solved || *lperror);
1549  *mustsepa = TRUE;
1550  *mustprice = TRUE;
1551 
1552  /* remove previous primal ray, store new one if LP is unbounded */
1553  SCIP_CALL( updatePrimalRay(blkmem, set, stat, prob, primal, tree, lp, *lperror) );
1554  }
1555 
1556  return SCIP_OKAY;
1557 }
1558 
1559 /** applies one round of LP separation */
1560 static
1562  BMS_BLKMEM* blkmem, /**< block memory buffers */
1563  SCIP_SET* set, /**< global SCIP settings */
1564  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1565  SCIP_STAT* stat, /**< dynamic problem statistics */
1566  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1567  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1568  SCIP_PROB* prob, /**< transformed problem after presolve */
1569  SCIP_PRIMAL* primal, /**< primal data */
1570  SCIP_TREE* tree, /**< branch and bound tree */
1571  SCIP_LP* lp, /**< LP data */
1572  SCIP_SEPASTORE* sepastore, /**< separation storage */
1573  int actdepth, /**< current depth in the tree */
1574  SCIP_Real bounddist, /**< current relative distance of local dual bound to global dual bound */
1575  SCIP_Bool allowlocal, /**< should the separators be asked to separate local cuts */
1576  SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
1577  SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
1578  SCIP_Bool* enoughcuts, /**< pointer to store whether enough cuts have been found this round */
1579  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
1580  SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
1581  SCIP_Bool* mustsepa, /**< pointer to store TRUE if additional separation rounds should be performed */
1582  SCIP_Bool* mustprice /**< pointer to store TRUE if additional pricing rounds should be performed */
1583  )
1584 {
1585  SCIP_RESULT result;
1586  int i;
1587  SCIP_Bool consadded;
1588  SCIP_Bool root;
1589 
1590  assert(set != NULL);
1591  assert(lp != NULL);
1592  assert(set->conshdlrs_sepa != NULL);
1593  assert(delayed != NULL);
1594  assert(enoughcuts != NULL);
1595  assert(cutoff != NULL);
1596  assert(lperror != NULL);
1597 
1598  root = (actdepth == 0);
1599  *delayed = FALSE;
1600  *enoughcuts = (SCIPsepastoreGetNCuts(sepastore) >= 2 * (SCIP_Longint)SCIPsetGetSepaMaxcuts(set, root));
1601  *lperror = FALSE;
1602  consadded = FALSE;
1603 
1604  SCIPsetDebugMsg(set, "calling separators on LP solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed);
1605 
1606  /* sort separators by priority */
1607  SCIPsetSortSepas(set);
1608 
1609  /* call LP separators with nonnegative priority */
1610  for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1612  ++i )
1613  {
1614 #ifndef NDEBUG
1615  size_t nusedbuffer = BMSgetNUsedBufferMemory(SCIPbuffer(set->scip));
1616 #endif
1617 
1618  if( SCIPsepaGetPriority(set->sepas[i]) < 0 )
1619  continue;
1620 
1621  if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) )
1622  continue;
1623 
1624  SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n",
1625  SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i]));
1626  SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) );
1627 #ifndef NDEBUG
1628  if( BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)) > nusedbuffer )
1629  {
1630  SCIPerrorMessage("Buffer not completely freed after executing separator <%s>\n", SCIPsepaGetName(set->sepas[i]));
1631  SCIPABORT();
1632  }
1633 #endif
1634  *cutoff = *cutoff || (result == SCIP_CUTOFF);
1635  consadded = consadded || (result == SCIP_CONSADDED);
1636  *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= 2 * (SCIP_Longint)SCIPsetGetSepaMaxcuts(set, root)) || (result == SCIP_NEWROUND);
1637  *delayed = *delayed || (result == SCIP_DELAYED);
1638 
1639  if( !(*cutoff) )
1640  {
1641  /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1642  SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1643  }
1644  else
1645  {
1646  SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1647  }
1648 
1649  /* if we work off the delayed separators, we stop immediately if a cut was found */
1650  if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1651  {
1652  SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i]));
1653  *delayed = TRUE;
1654  return SCIP_OKAY;
1655  }
1656  }
1657 
1658  /* try separating constraints of the constraint handlers */
1659  for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1661  ++i )
1662  {
1663  if( onlydelayed && !SCIPconshdlrWasLPSeparationDelayed(set->conshdlrs_sepa[i]) )
1664  continue;
1665 
1666  SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n",
1667  SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i]));
1668  SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed,
1669  &result) );
1670 
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, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[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 constraint handler <%s> found a cut\n",
1690  SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1691  *delayed = TRUE;
1692  return SCIP_OKAY;
1693  }
1694  }
1695 
1696  /* call LP separators with negative priority */
1697  for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1699  ++i )
1700  {
1701  if( SCIPsepaGetPriority(set->sepas[i]) >= 0 )
1702  continue;
1703 
1704  if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) )
1705  continue;
1706 
1707  SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n",
1708  SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i]));
1709  SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) );
1710 
1711  *cutoff = *cutoff || (result == SCIP_CUTOFF);
1712  consadded = consadded || (result == SCIP_CONSADDED);
1713  *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= 2 * (SCIP_Longint)SCIPsetGetSepaMaxcuts(set, root)) || (result == SCIP_NEWROUND);
1714  *delayed = *delayed || (result == SCIP_DELAYED);
1715 
1716  if( !(*cutoff) )
1717  {
1718  /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1719  SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1720  }
1721  else
1722  {
1723  SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1724  }
1725 
1726  /* if we work off the delayed separators, we stop immediately if a cut was found */
1727  if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1728  {
1729  SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i]));
1730  *delayed = TRUE;
1731  return SCIP_OKAY;
1732  }
1733  }
1734 
1735  /* process the constraints that were added during this separation round */
1736  while( consadded )
1737  {
1738  assert(!onlydelayed);
1739  consadded = FALSE;
1740 
1741  for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved
1743  ++i )
1744  {
1745  SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n",
1746  SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i]));
1747  SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed,
1748  &result) );
1749 
1750  *cutoff = *cutoff || (result == SCIP_CUTOFF);
1751  consadded = consadded || (result == SCIP_CONSADDED);
1752  *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= 2 * (SCIP_Longint)SCIPsetGetSepaMaxcuts(set, root)) || (result == SCIP_NEWROUND);
1753  *delayed = *delayed || (result == SCIP_DELAYED);
1754 
1755  if( !(*cutoff) )
1756  {
1757  /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */
1758  SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) );
1759  }
1760  else
1761  {
1762  SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1763  }
1764  }
1765  }
1766 
1767  SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, lpflushed=%u, cutoff=%u\n",
1768  *delayed, *enoughcuts, lp->flushed, *cutoff);
1769 
1770  return SCIP_OKAY;
1771 }
1772 
1773 /** applies one round of separation on the given primal solution */
1774 static
1776  BMS_BLKMEM* blkmem, /**< block memory buffers */
1777  SCIP_SET* set, /**< global SCIP settings */
1778  SCIP_STAT* stat, /**< dynamic problem statistics */
1779  SCIP_SEPASTORE* sepastore, /**< separation storage */
1780  SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
1781  int actdepth, /**< current depth in the tree */
1782  SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
1783  SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
1784  SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
1785  SCIP_Bool* enoughcuts, /**< pointer to store whether enough cuts have been found this round */
1786  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1787  )
1788 {
1789  SCIP_RESULT result;
1790  int i;
1791  SCIP_Bool consadded;
1792  SCIP_Bool root;
1793 
1794  assert(set != NULL);
1795  assert(set->conshdlrs_sepa != NULL);
1796  assert(delayed != NULL);
1797  assert(enoughcuts != NULL);
1798  assert(cutoff != NULL);
1799 
1800  *delayed = FALSE;
1801  *enoughcuts = FALSE;
1802  consadded = FALSE;
1803  root = (actdepth == 0);
1804 
1805  SCIPsetDebugMsg(set, "calling separators on primal solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed);
1806 
1807  /* sort separators by priority */
1808  SCIPsetSortSepas(set);
1809 
1810  /* call separators with nonnegative priority */
1811  for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1812  {
1813  if( SCIPsepaGetPriority(set->sepas[i]) < 0 )
1814  continue;
1815 
1816  if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) )
1817  continue;
1818 
1819  SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) );
1820  *cutoff = *cutoff || (result == SCIP_CUTOFF);
1821  consadded = consadded || (result == SCIP_CONSADDED);
1822  *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= 2 * (SCIP_Longint)SCIPsetGetSepaMaxcuts(set, root)) || (result == SCIP_NEWROUND);
1823  *delayed = *delayed || (result == SCIP_DELAYED);
1824  if( *cutoff )
1825  {
1826  SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1827  }
1828 
1829  /* if we work off the delayed separators, we stop immediately if a cut was found */
1830  if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1831  {
1832  *delayed = TRUE;
1833  return SCIP_OKAY;
1834  }
1835  }
1836 
1837  /* try separating constraints of the constraint handlers */
1838  for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1839  {
1840  if( onlydelayed && !SCIPconshdlrWasSolSeparationDelayed(set->conshdlrs_sepa[i]) )
1841  continue;
1842 
1843  SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed,
1844  &result) );
1845  *cutoff = *cutoff || (result == SCIP_CUTOFF);
1846  consadded = consadded || (result == SCIP_CONSADDED);
1847  *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= 2 * (SCIP_Longint)SCIPsetGetSepaMaxcuts(set, root)) || (result == SCIP_NEWROUND);
1848  *delayed = *delayed || (result == SCIP_DELAYED);
1849  if( *cutoff )
1850  {
1851  SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n",
1852  SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1853  }
1854 
1855  /* if we work off the delayed separators, we stop immediately if a cut was found */
1856  if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1857  {
1858  *delayed = TRUE;
1859  return SCIP_OKAY;
1860  }
1861  }
1862 
1863  /* call separators with negative priority */
1864  for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1865  {
1866  if( SCIPsepaGetPriority(set->sepas[i]) >= 0 )
1867  continue;
1868 
1869  if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) )
1870  continue;
1871 
1872  SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) );
1873  *cutoff = *cutoff || (result == SCIP_CUTOFF);
1874  consadded = consadded || (result == SCIP_CONSADDED);
1875  *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= 2 * (SCIP_Longint)SCIPsetGetSepaMaxcuts(set, root)) || (result == SCIP_NEWROUND);
1876  *delayed = *delayed || (result == SCIP_DELAYED);
1877  if( *cutoff )
1878  {
1879  SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i]));
1880  }
1881 
1882  /* if we work off the delayed separators, we stop immediately if a cut was found */
1883  if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) )
1884  {
1885  *delayed = TRUE;
1886  return SCIP_OKAY;
1887  }
1888  }
1889 
1890  /* process the constraints that were added during this separation round */
1891  while( consadded )
1892  {
1893  assert(!onlydelayed);
1894  consadded = FALSE;
1895 
1896  for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i )
1897  {
1898  SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed, &result) );
1899  *cutoff = *cutoff || (result == SCIP_CUTOFF);
1900  consadded = consadded || (result == SCIP_CONSADDED);
1901  *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= 2 * (SCIP_Longint)SCIPsetGetSepaMaxcuts(set, root)) || (result == SCIP_NEWROUND);
1902  *delayed = *delayed || (result == SCIP_DELAYED);
1903  if( *cutoff )
1904  {
1905  SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n",
1906  SCIPconshdlrGetName(set->conshdlrs_sepa[i]));
1907  }
1908  }
1909  }
1910 
1911  SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, cutoff=%u\n",
1912  *delayed, *enoughcuts, *cutoff);
1913 
1914  return SCIP_OKAY;
1915 }
1916 
1917 /** applies one round of separation on the given primal solution or on the LP solution */
1919  BMS_BLKMEM* blkmem, /**< block memory buffers */
1920  SCIP_SET* set, /**< global SCIP settings */
1921  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1922  SCIP_STAT* stat, /**< dynamic problem statistics */
1923  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1924  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1925  SCIP_PROB* prob, /**< transformed problem after presolve */
1926  SCIP_PRIMAL* primal, /**< primal data */
1927  SCIP_TREE* tree, /**< branch and bound tree */
1928  SCIP_LP* lp, /**< LP data */
1929  SCIP_SEPASTORE* sepastore, /**< separation storage */
1930  SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
1931  int actdepth, /**< current depth in the tree */
1932  SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
1933  SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
1934  SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
1935  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1936  )
1937 {
1938  SCIP_Bool enoughcuts;
1939 
1940  assert(delayed != NULL);
1941  assert(cutoff != NULL);
1942 
1943  *delayed = FALSE;
1944  *cutoff = FALSE;
1945  enoughcuts = FALSE;
1946 
1947  if( sol == NULL )
1948  {
1949  SCIP_Bool lperror;
1950  SCIP_Bool mustsepa;
1951  SCIP_Bool mustprice;
1952 
1953  /* apply a separation round on the LP solution */
1954  lperror = FALSE;
1955  mustsepa = FALSE;
1956  mustprice = FALSE;
1957  SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, sepastore, \
1958  actdepth, 0.0, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff, \
1959  &lperror, &mustsepa, &mustprice) );
1960  }
1961  else
1962  {
1963  /* apply a separation round on the given primal solution */
1964  SCIP_CALL( separationRoundSol(blkmem, set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff) );
1965  }
1966 
1967  return SCIP_OKAY;
1968 }
1969 
1970 /** solves the current LP completely with pricing in new variables */
1972  BMS_BLKMEM* blkmem, /**< block memory buffers */
1973  SCIP_SET* set, /**< global SCIP settings */
1974  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1975  SCIP_STAT* stat, /**< dynamic problem statistics */
1976  SCIP_PROB* transprob, /**< transformed problem */
1977  SCIP_PROB* origprob, /**< original problem */
1978  SCIP_PRIMAL* primal, /**< primal data */
1979  SCIP_TREE* tree, /**< branch and bound tree */
1980  SCIP_REOPT* reopt, /**< reoptimization data structure */
1981  SCIP_LP* lp, /**< LP data */
1982  SCIP_PRICESTORE* pricestore, /**< pricing storage */
1983  SCIP_SEPASTORE* sepastore, /**< separation storage */
1984  SCIP_CUTPOOL* cutpool, /**< global cutpool */
1985  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1986  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1987  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
1988  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1989  SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */
1990  SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */
1991  int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit);
1992  * a finite limit means that the LP might not be solved to optimality! */
1993  int* npricedcolvars, /**< pointer to store number of column variables after problem vars were priced */
1994  SCIP_Bool* mustsepa, /**< pointer to store TRUE if a separation round should follow */
1995  SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
1996  SCIP_Bool* aborted /**< pointer to store whether the pricing was aborted and the lower bound must
1997  * not be used */
1998  )
1999 {
2000  SCIP_NODE* currentnode;
2001  int npricerounds;
2002  SCIP_Bool mustprice;
2003  SCIP_Bool cutoff;
2004  SCIP_Bool unbounded;
2005 
2006  assert(transprob != NULL);
2007  assert(lp != NULL);
2008  assert(lp->flushed);
2009  assert(lp->solved);
2010  assert(npricedcolvars != NULL);
2011  assert(mustsepa != NULL);
2012  assert(lperror != NULL);
2013  assert(aborted != NULL);
2014 
2015  currentnode = SCIPtreeGetCurrentNode(tree);
2016  assert(currentnode == SCIPtreeGetFocusNode(tree) || SCIPtreeProbing(tree));
2017  *npricedcolvars = transprob->ncolvars;
2018  *lperror = FALSE;
2019  *aborted = FALSE;
2020 
2021  /* if the LP is unbounded, we don't need to price */
2022  mustprice = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL
2025 
2026  /* if all the variables are already in the LP, we don't need to price */
2027  mustprice = mustprice && !SCIPprobAllColsInLP(transprob, set, lp);
2028 
2029  /* check if infinite number of pricing rounds should be used */
2030  if( maxpricerounds == -1 )
2031  maxpricerounds = INT_MAX;
2032 
2033  /* pricing (has to be done completely to get a valid lower bound) */
2034  npricerounds = 0;
2035  while( !(*lperror) && mustprice && npricerounds < maxpricerounds )
2036  {
2037  SCIP_Bool enoughvars;
2038  SCIP_RESULT result;
2039  SCIP_Real lb;
2040  SCIP_Bool foundsol;
2041  SCIP_Bool stopearly;
2042  SCIP_Bool stoppricing;
2043  int p;
2044 
2045  assert(lp->flushed);
2046  assert(lp->solved);
2048 
2049  /* check if pricing loop should be aborted */
2050  if( SCIPsolveIsStopped(set, stat, FALSE) )
2051  {
2052  /* do not print the warning message if we stopped because the problem is solved */
2053  if( !SCIPsetIsLE(set, SCIPgetUpperbound(set->scip), SCIPgetLowerbound(set->scip)) )
2054  SCIPmessagePrintWarning(messagehdlr, "pricing has been interrupted -- LP of current node is invalid\n");
2055 
2056  *aborted = TRUE;
2057  break;
2058  }
2059 
2060  /* call primal heuristics which are callable during pricing */
2061  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGPRICINGLOOP,
2062  FALSE, &foundsol, &unbounded) );
2063 
2064  /* price problem variables */
2065  SCIPsetDebugMsg(set, "problem variable pricing\n");
2066  assert(SCIPpricestoreGetNVars(pricestore) == 0);
2067  assert(SCIPpricestoreGetNBoundResets(pricestore) == 0);
2068  SCIP_CALL( SCIPpricestoreAddProbVars(pricestore, blkmem, set, stat, transprob, tree, lp, branchcand, eventqueue) );
2069  *npricedcolvars = transprob->ncolvars;
2070 
2071  /* call external pricers to create additional problem variables */
2072  SCIPsetDebugMsg(set, "external variable pricing\n");
2073 
2074  /* sort pricer algorithms by priority */
2075  SCIPsetSortPricers(set);
2076 
2077  /* call external pricer algorithms, that are active for the current problem */
2078  enoughvars = (SCIPsetGetPriceMaxvars(set, pretendroot) == INT_MAX ?
2079  FALSE : SCIPpricestoreGetNVars(pricestore) >= SCIPsetGetPriceMaxvars(set, pretendroot) + 1);
2080  stoppricing = FALSE;
2081  for( p = 0; p < set->nactivepricers && !enoughvars; ++p )
2082  {
2083  SCIP_CALL( SCIPpricerExec(set->pricers[p], set, transprob, lp, pricestore, &lb, &stopearly, &result) );
2084  assert(result == SCIP_DIDNOTRUN || result == SCIP_SUCCESS);
2085  SCIPsetDebugMsg(set, "pricing: pricer %s returned result = %s, lowerbound = %f\n",
2086  SCIPpricerGetName(set->pricers[p]), (result == SCIP_DIDNOTRUN ? "didnotrun" : "success"), lb);
2087  enoughvars = enoughvars || (SCIPsetGetPriceMaxvars(set, pretendroot) == INT_MAX ?
2088  FALSE : SCIPpricestoreGetNVars(pricestore) >= SCIPsetGetPriceMaxvars(set, pretendroot) + 1);
2089  *aborted = ( (*aborted) || (result == SCIP_DIDNOTRUN) );
2090 
2091  /* set stoppricing to TRUE, of the first pricer wants to stop pricing */
2092  if( p == 0 && stopearly )
2093  stoppricing = TRUE;
2094 
2095  /* stoppricing only remains TRUE, if all other pricers want to stop pricing as well */
2096  if( stoppricing && !stopearly )
2097  stoppricing = FALSE;
2098 
2099  /* update lower bound w.r.t. the lower bound given by the pricer */
2100  SCIPnodeUpdateLowerbound(currentnode, stat, set, tree, transprob, origprob, lb);
2101  SCIPsetDebugMsg(set, " -> new lower bound given by pricer %s: %g\n", SCIPpricerGetName(set->pricers[p]), lb);
2102  }
2103 
2104  /* apply the priced variables to the LP */
2105  SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) );
2106  assert(SCIPpricestoreGetNVars(pricestore) == 0);
2107  assert(!lp->flushed || lp->solved);
2108  mustprice = !lp->flushed || (transprob->ncolvars != *npricedcolvars);
2109  *mustsepa = *mustsepa || !lp->flushed;
2110 
2111  /* after adding columns, the LP should be primal feasible such that the primal simplex is applicable;
2112  * if LP was infeasible, we have to use dual simplex
2113  */
2114  SCIPsetDebugMsg(set, "pricing: solve LP\n");
2115  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, TRUE, FALSE, lperror) );
2116  assert(lp->flushed);
2117  assert(lp->solved || *lperror);
2118 
2119  /* reset bounds temporarily set by pricer to their original values */
2120  SCIPsetDebugMsg(set, "pricing: reset bounds\n");
2121  SCIP_CALL( SCIPpricestoreResetBounds(pricestore, blkmem, set, stat, lp, branchcand, eventqueue) );
2122  assert(SCIPpricestoreGetNVars(pricestore) == 0);
2123  assert(SCIPpricestoreGetNBoundResets(pricestore) == 0);
2124  assert(!lp->flushed || lp->solved || *lperror);
2125 
2126  /* put all initial constraints into the LP */
2127  SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2128  eventfilter, cliquetable, FALSE, FALSE, &cutoff) );
2129  assert(cutoff == FALSE);
2130 
2131  mustprice = mustprice || !lp->flushed || (transprob->ncolvars != *npricedcolvars);
2132  *mustsepa = *mustsepa || !lp->flushed;
2133 
2134  /* if all pricers wanted to stop pricing, do not do another pricing round (LP value is no valid dual bound in this case) */
2135  if( stoppricing )
2136  {
2137  SCIPsetDebugMsg(set, "pricing: stop pricing and perform early branching\n");
2138  mustprice = FALSE;
2139  *aborted = TRUE;
2140  }
2141 
2142  /* solve LP again after resetting bounds and adding new initial constraints (with dual simplex) */
2143  SCIPsetDebugMsg(set, "pricing: solve LP after resetting bounds and adding new initial constraints\n");
2144  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) );
2145  assert(lp->flushed);
2146  assert(lp->solved || *lperror);
2147 
2148  /* remove previous primal ray, store new one if LP is unbounded */
2149  SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2150 
2151  /* increase pricing round counter */
2152  stat->npricerounds++;
2153  npricerounds++;
2154 
2155  /* display node information line */
2156  if( displayinfo && mustprice )
2157  {
2158  if( (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_FULL
2159  || ((SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH && npricerounds % 100 == 1) )
2160  {
2161  SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
2162  }
2163  }
2164 
2165  /* if the LP is unbounded, we can stop pricing */
2166  mustprice = mustprice &&
2170 
2171  /* if the lower bound is already higher than the cutoff bound, we can stop pricing */
2172  mustprice = mustprice && SCIPsetIsLT(set, SCIPnodeGetLowerbound(currentnode), primal->cutoffbound);
2173  }
2174  assert(lp->flushed);
2175  assert(lp->solved || *lperror);
2176 
2177  *aborted = ( (*aborted) || (*lperror) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_NOTSOLVED
2178  || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ERROR || npricerounds == maxpricerounds );
2179 
2180  /* set information, whether the current lp is a valid relaxation of the current problem */
2181  SCIPlpSetIsRelax(lp, !(*aborted));
2182 
2183  return SCIP_OKAY;
2184 }
2185 
2186 /** separates cuts of the cut pool */
2187 static
2189  SCIP_CUTPOOL* cutpool, /**< cut pool */
2190  BMS_BLKMEM* blkmem, /**< block memory */
2191  SCIP_SET* set, /**< global SCIP settings */
2192  SCIP_STAT* stat, /**< problem statistics data */
2193  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2194  SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
2195  SCIP_LP* lp, /**< current LP data */
2196  SCIP_SEPASTORE* sepastore, /**< separation storage */
2197  SCIP_Bool cutpoolisdelayed, /**< is the cutpool delayed (count cuts found)? */
2198  SCIP_Bool root, /**< are we at the root node? */
2199  int actdepth, /**< the depth of the focus node */
2200  SCIP_Bool* enoughcuts, /**< pointer to store if enough cuts were found in current separation round */
2201  SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
2202  )
2203 {
2204  if( (set->sepa_poolfreq == 0 && actdepth == 0)
2205  || (set->sepa_poolfreq > 0 && actdepth % set->sepa_poolfreq == 0) )
2206  {
2207  SCIP_RESULT result;
2208 
2209  SCIP_CALL( SCIPcutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, NULL, cutpoolisdelayed, root, &result) );
2210  *cutoff = *cutoff || (result == SCIP_CUTOFF);
2211  *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= 2 * (SCIP_Longint)SCIPsetGetSepaMaxcuts(set, root)) || (result == SCIP_NEWROUND);
2212  }
2213 
2214  return SCIP_OKAY;
2215 }
2216 
2217 /** solve the current LP of a node with a price-and-cut loop */
2218 static
2220  BMS_BLKMEM* blkmem, /**< block memory buffers */
2221  SCIP_SET* set, /**< global SCIP settings */
2222  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2223  SCIP_STAT* stat, /**< dynamic problem statistics */
2224  SCIP_MEM* mem, /**< block memory pools */
2225  SCIP_PROB* transprob, /**< transformed problem */
2226  SCIP_PROB* origprob, /**< original problem */
2227  SCIP_PRIMAL* primal, /**< primal data */
2228  SCIP_TREE* tree, /**< branch and bound tree */
2229  SCIP_REOPT* reopt, /**< reoptimization data structure */
2230  SCIP_LP* lp, /**< LP data */
2231  SCIP_PRICESTORE* pricestore, /**< pricing storage */
2232  SCIP_SEPASTORE* sepastore, /**< separation storage */
2233  SCIP_CUTPOOL* cutpool, /**< global cut pool */
2234  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
2235  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2236  SCIP_CONFLICT* conflict, /**< conflict analysis data */
2237  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2238  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
2239  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2240  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2241  SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
2242  SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
2243  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
2244  SCIP_Bool* unbounded, /**< pointer to store whether an unbounded ray was found in the LP */
2245  SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
2246  SCIP_Bool* pricingaborted /**< pointer to store whether the pricing was aborted and the lower bound must
2247  * not be used */
2248  )
2249 {
2250  SCIP_NODE* focusnode;
2251  /* cppcheck-suppress unassignedVariable */
2252  SCIP_EVENT event;
2253  SCIP_LPSOLSTAT stalllpsolstat;
2254  SCIP_Real loclowerbound;
2255  SCIP_Real glblowerbound;
2256  SCIP_Real bounddist;
2257  SCIP_Real stalllpobjval;
2258  SCIP_Bool separate;
2259  SCIP_Bool mustprice;
2260  SCIP_Bool mustsepa;
2261  SCIP_Bool delayedsepa;
2262  SCIP_Bool root;
2263  SCIP_Bool allowlocal;
2264  int maxseparounds;
2265  int nsepastallrounds;
2266  int maxnsepastallrounds;
2267  int stallnfracs;
2268  int actdepth;
2269  int npricedcolvars;
2270 
2271  assert(set != NULL);
2272  assert(blkmem != NULL);
2273  assert(stat != NULL);
2274  assert(transprob != NULL);
2275  assert(tree != NULL);
2276  assert(lp != NULL);
2277  assert(pricestore != NULL);
2278  assert(sepastore != NULL);
2279  assert(cutpool != NULL);
2280  assert(delayedcutpool != NULL);
2281  assert(primal != NULL);
2282  assert(cutoff != NULL);
2283  assert(unbounded != NULL);
2284  assert(lperror != NULL);
2285 
2286  focusnode = SCIPtreeGetFocusNode(tree);
2287  assert(focusnode != NULL);
2288  assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
2289  actdepth = SCIPnodeGetDepth(focusnode);
2290  root = (actdepth == 0);
2291 
2292  /* check, if we want to separate at this node */
2293  loclowerbound = SCIPnodeGetLowerbound(focusnode);
2294  glblowerbound = SCIPtreeGetLowerbound(tree, set);
2295  assert(primal->cutoffbound > glblowerbound);
2296  bounddist = (loclowerbound - glblowerbound)/(primal->cutoffbound - glblowerbound);
2297  allowlocal = SCIPsetIsLE(set, bounddist, set->sepa_maxlocalbounddist);
2298  separate = (set->sepa_maxruns == -1 || stat->nruns <= set->sepa_maxruns);
2299 
2300  /* get maximal number of separation rounds */
2301  maxseparounds = (root ? set->sepa_maxroundsroot : set->sepa_maxrounds);
2302  if( maxseparounds == -1 )
2303  maxseparounds = INT_MAX;
2304  if( stat->nruns > 1 && root && set->sepa_maxroundsrootsubrun >= 0 )
2305  maxseparounds = MIN(maxseparounds, set->sepa_maxroundsrootsubrun);
2306  if( !fullseparation && set->sepa_maxaddrounds >= 0 )
2307  maxseparounds = MIN(maxseparounds, stat->nseparounds + set->sepa_maxaddrounds);
2308  maxnsepastallrounds = root ? set->sepa_maxstallroundsroot : set->sepa_maxstallrounds;
2309  if( maxnsepastallrounds == -1 )
2310  maxnsepastallrounds = INT_MAX;
2311 
2312  /* solve initial LP of price-and-cut loop */
2313  /* @todo check if LP is always already solved, because of calling solveNodeInitialLP() in solveNodeLP()? */
2314  SCIPsetDebugMsg(set, "node: solve LP with price and cut\n");
2315  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2316  set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2317  assert(lp->flushed);
2318  assert(lp->solved || *lperror);
2319 
2320  /* remove previous primal ray, store new one if LP is unbounded */
2321  SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2322 
2323  /* price-and-cut loop */
2324  npricedcolvars = transprob->ncolvars;
2325  mustprice = TRUE;
2326  mustsepa = separate;
2327  delayedsepa = FALSE;
2328  *cutoff = FALSE;
2329  *unbounded = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY);
2330  nsepastallrounds = 0;
2331  stalllpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
2332  stalllpobjval = SCIP_REAL_MIN;
2333  stallnfracs = INT_MAX;
2334  lp->installing = FALSE;
2335  while( !(*cutoff) && !(*unbounded) && !(*lperror) && (mustprice || mustsepa || delayedsepa) )
2336  {
2337  SCIPsetDebugMsg(set, "-------- node solving loop --------\n");
2338  assert(lp->flushed);
2339  assert(lp->solved);
2340 
2341  /* solve the LP with pricing in new variables */
2342  while( mustprice && !(*lperror) )
2343  {
2344  SCIP_CALL( SCIPpriceLoop(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
2345  pricestore, sepastore, cutpool, branchcand, eventqueue, eventfilter, cliquetable, root, root, -1, &npricedcolvars,
2346  &mustsepa, lperror, pricingaborted) );
2347 
2348  mustprice = FALSE;
2349 
2350  assert(lp->flushed);
2351  assert(lp->solved || *lperror);
2352 
2353  /* update lower bound w.r.t. the LP solution */
2354  if( !(*lperror) && !(*pricingaborted) && SCIPlpIsRelax(lp) )
2355  {
2356  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2357  SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2358  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2359 
2360  /* update node estimate */
2361  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2362 
2363  if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2364  SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2365  }
2366  else
2367  {
2368  SCIPsetDebugMsg(set, " -> error solving LP or pricing aborted. keeping old bound: %g\n", SCIPnodeGetLowerbound(focusnode));
2369  }
2370 
2371  /* display node information line for root node */
2372  if( root && (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH )
2373  {
2374  SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
2375  }
2376 
2377  if( !(*lperror) )
2378  {
2379  /* call propagators that are applicable during LP solving loop only if the node is not cut off */
2380  if( SCIPsetIsLT(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound) )
2381  {
2382  SCIP_Longint oldnboundchgs;
2383  SCIP_Longint oldninitconssadded;
2384  SCIP_Bool postpone;
2385 
2386  oldnboundchgs = stat->nboundchgs;
2387  oldninitconssadded = stat->ninitconssadded;
2388 
2389  SCIPsetDebugMsg(set, " -> LP solved: call propagators that are applicable during LP solving loop\n");
2390 
2391  SCIP_CALL( propagateDomains(blkmem, set, stat, primal, tree, SCIPtreeGetCurrentDepth(tree), 0, FALSE,
2392  SCIP_PROPTIMING_DURINGLPLOOP, cutoff, &postpone) );
2393  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2394  assert(!postpone);
2395 
2396  if( stat->ninitconssadded != oldninitconssadded )
2397  {
2398  SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n", oldninitconssadded, stat->ninitconssadded);
2399 
2400  SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2401  branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2402  }
2403 
2404  if( !(*cutoff) && !(*unbounded) )
2405  {
2406  /* if we found something, solve LP again */
2407  if( !lp->flushed )
2408  {
2409  SCIPsetDebugMsg(set, " -> found reduction: resolve LP\n");
2410 
2411  /* in the root node, remove redundant rows permanently from the LP */
2412  if( root )
2413  {
2414  SCIP_CALL( SCIPlpFlush(lp, blkmem, set, eventqueue) );
2415  SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2416  }
2417 
2418  /* resolve LP */
2419  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2420  set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2421  assert(lp->flushed);
2422  assert(lp->solved || *lperror);
2423 
2424  /* remove previous primal ray, store new one if LP is unbounded */
2425  SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2426 
2427  mustprice = TRUE;
2428  *propagateagain = TRUE;
2429  }
2430  /* propagation might have changed the best bound of loose variables, thereby changing the loose objective
2431  * value which is added to the LP value; because of the loose status, the LP might not be reoptimized,
2432  * but the lower bound of the node needs to be updated
2433  */
2434  else if( stat->nboundchgs > oldnboundchgs )
2435  {
2436  *propagateagain = TRUE;
2437 
2438  if( lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2439  {
2440  assert(lp->flushed);
2441  assert(lp->solved);
2442 
2443  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2444  SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2445  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2446 
2447  /* update node estimate */
2448  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2449 
2450  if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2451  SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2452  }
2453  }
2454  }
2455  }
2456  }
2457 
2458  /* call primal heuristics that are applicable during node LP solving loop */
2459  if( !*cutoff && !(*unbounded) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2460  {
2461  SCIP_Bool foundsol;
2462 
2463  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGLPLOOP,
2464  FALSE, &foundsol, unbounded) );
2465  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2466 
2467  *lperror = *lperror || lp->resolvelperror;
2468  }
2469  }
2470  assert(lp->flushed || *cutoff || *unbounded);
2471  assert(lp->solved || *lperror || *cutoff || *unbounded);
2472 
2473  /* check, if we exceeded the separation round limit */
2474  mustsepa = mustsepa
2475  && stat->nseparounds < maxseparounds
2476  && nsepastallrounds < maxnsepastallrounds
2477  && !(*cutoff);
2478 
2479  /* if separators were delayed, we want to apply a final separation round with the delayed separators */
2480  delayedsepa = delayedsepa && !mustsepa && !(*cutoff); /* if regular separation applies, we ignore delayed separators */
2481  mustsepa = mustsepa || delayedsepa;
2482 
2483  if( mustsepa )
2484  {
2485  /* if the LP is infeasible, unbounded, exceeded the objective limit or a global performance limit was reached,
2486  * we don't need to separate cuts
2487  * (the global limits are only checked at the root node in order to not query system time too often)
2488  */
2489  if( !separate || (*cutoff) || (*unbounded)
2491  || SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)
2492  || (root && SCIPsolveIsStopped(set, stat, FALSE)) )
2493  {
2494  mustsepa = FALSE;
2495  delayedsepa = FALSE;
2496  }
2497  else
2498  assert(!(*lperror));
2499  }
2500 
2501  /* separation (needs not to be done completely, because we just want to increase the lower bound) */
2502  if( mustsepa )
2503  {
2504  SCIP_Longint olddomchgcount;
2505  SCIP_Longint oldninitconssadded;
2506  SCIP_Bool enoughcuts;
2507 
2508  assert(lp->flushed);
2509  assert(lp->solved);
2511 
2512  olddomchgcount = stat->domchgcount;
2513  oldninitconssadded = stat->ninitconssadded;
2514 
2515  mustsepa = FALSE;
2516  enoughcuts = (SCIPsetGetSepaMaxcuts(set, root) == 0);
2517 
2518  /* global cut pool separation */
2519  if( !enoughcuts && !delayedsepa )
2520  {
2521  SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2522  actdepth, &enoughcuts, cutoff) );
2523 
2524  if( *cutoff )
2525  {
2526  SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2527  }
2528  }
2529  assert(lp->flushed);
2530  assert(lp->solved);
2532 
2533  /* constraint separation */
2534  SCIPsetDebugMsg(set, "constraint separation\n");
2535 
2536  /* separate constraints and LP */
2537  if( !(*cutoff) && !(*lperror) && !enoughcuts && lp->solved )
2538  {
2539  /* apply a separation round */
2540  SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal, tree,
2541  lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2542  &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) );
2543  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2544 
2545  /* if we are close to the stall round limit, also call the delayed separators */
2546  if( !(*cutoff) && !(*lperror) && !enoughcuts && lp->solved
2548  && nsepastallrounds >= maxnsepastallrounds-1 && delayedsepa )
2549  {
2550  SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal,
2551  tree, lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2552  &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) );
2553  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2554  }
2555  }
2556 
2557  /* call global cut pool separation again since separators may add cuts to the pool instead of the sepastore */
2558  if( !(*cutoff) && !(*lperror) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && !enoughcuts && lp->solved )
2559  {
2560  SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2561  actdepth, &enoughcuts, cutoff) );
2562 
2563  if( *cutoff )
2564  {
2565  SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2566  }
2567  }
2568 
2569  /* delayed global cut pool separation */
2570  if( !(*cutoff) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && SCIPsepastoreGetNCuts(sepastore) == 0 )
2571  {
2572  assert( !(*lperror) );
2573 
2574  SCIP_CALL( cutpoolSeparate(delayedcutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, TRUE,
2575  root, actdepth, &enoughcuts, cutoff) );
2576 
2577  if( *cutoff )
2578  {
2579  SCIPsetDebugMsg(set, " -> delayed global cut pool detected cutoff\n");
2580  }
2582  assert(lp->flushed);
2583  assert(lp->solved);
2584  }
2585 
2586  assert(*cutoff || *lperror || SCIPlpIsSolved(lp));
2587  assert(!SCIPlpIsSolved(lp)
2594 
2595  if( *cutoff || *lperror
2598  {
2599  /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
2600  SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
2601  }
2602  else
2603  {
2604  /* apply found cuts */
2605  SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2606  branchcand, eventqueue, eventfilter, cliquetable, root, SCIP_EFFICIACYCHOICE_LP, cutoff) );
2607 
2608  if( !(*cutoff) )
2609  {
2610  mustprice = mustprice || !lp->flushed || (transprob->ncolvars != npricedcolvars);
2611  mustsepa = mustsepa || !lp->flushed;
2612 
2613  /* if a new bound change (e.g. a cut with only one column) was found, propagate domains again */
2614  if( stat->domchgcount != olddomchgcount )
2615  {
2616  SCIPsetDebugMsg(set, " -> separation changed bound: propagate again\n");
2617 
2618  *propagateagain = TRUE;
2619 
2620  /* in the root node, remove redundant rows permanently from the LP */
2621  if( root )
2622  {
2623  SCIP_CALL( SCIPlpFlush(lp, blkmem, set, eventqueue) );
2624  SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2625  }
2626  }
2627 
2628  if( stat->ninitconssadded != oldninitconssadded )
2629  {
2630  SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n",
2631  oldninitconssadded, stat->ninitconssadded);
2632 
2633  SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2634  branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2635  }
2636 
2637  if( !(*cutoff) )
2638  {
2639  SCIP_Real lpobjval;
2640 
2641  /* solve LP (with dual simplex) */
2642  SCIPsetDebugMsg(set, "separation: solve LP\n");
2643  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2644  set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2645  assert(lp->flushed);
2646  assert(lp->solved || *lperror);
2647 
2648  /* remove previous primal ray, store new one if LP is unbounded */
2649  SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2650 
2651  if( !(*lperror) )
2652  {
2653  SCIP_Bool stalling;
2654 
2655  /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
2656  * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
2657  * bound of the node needs to be updated
2658  */
2659  if( stat->domchgcount != olddomchgcount && (!mustprice || mustsepa) && !(*cutoff)
2660  && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2661  {
2662  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2663  SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2664  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2665 
2666  /* update node estimate */
2667  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2668 
2669  if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2670  SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2671  }
2672 
2673  /* check if we are stalling
2674  * If we have an LP solution, then we are stalling if
2675  * we had an LP solution before and
2676  * the LP value did not improve and
2677  * the number of fractional variables did not decrease.
2678  * If we do not have an LP solution, then we are stalling if the solution status of the LP did not change.
2679  */
2681  {
2682  SCIP_Real objreldiff;
2683  int nfracs;
2684 
2685  SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nfracs, NULL,
2686  NULL) );
2687  lpobjval = SCIPlpGetObjval(lp, set, transprob);
2688 
2689  objreldiff = SCIPrelDiff(lpobjval, stalllpobjval);
2690  SCIPsetDebugMsg(set, " -> LP bound moved from %g to %g (reldiff: %g)\n",
2691  stalllpobjval, lpobjval, objreldiff);
2692 
2693  stalling = (stalllpsolstat == SCIP_LPSOLSTAT_OPTIMAL &&
2694  objreldiff <= 1e-04 &&
2695  nfracs >= (0.9 - 0.1 * nsepastallrounds) * stallnfracs);
2696 
2697  stalllpobjval = lpobjval;
2698  stallnfracs = nfracs;
2699  }
2700  else
2701  {
2702  stalling = (stalllpsolstat == SCIPlpGetSolstat(lp));
2703  }
2704 
2705  if( !stalling )
2706  {
2707  nsepastallrounds = 0;
2708  lp->installing = FALSE;
2709  }
2710  else
2711  {
2712  nsepastallrounds++;
2713  }
2714  stalllpsolstat = SCIPlpGetSolstat(lp);
2715 
2716  /* tell LP that we are (close to) stalling */
2717  if( nsepastallrounds >= maxnsepastallrounds-2 )
2718  lp->installing = TRUE;
2719  SCIPsetDebugMsg(set, " -> nsepastallrounds=%d/%d\n", nsepastallrounds, maxnsepastallrounds);
2720  }
2721  }
2722  }
2723  }
2724  assert(*cutoff || *lperror || (lp->flushed && lp->solved)); /* cutoff: LP may be unsolved due to bound changes */
2725 
2726  SCIPsetDebugMsg(set, "separation round %d/%d finished (%d/%d stall rounds): mustprice=%u, mustsepa=%u, delayedsepa=%u, propagateagain=%u\n",
2727  stat->nseparounds, maxseparounds, nsepastallrounds, maxnsepastallrounds, mustprice, mustsepa, delayedsepa, *propagateagain);
2728 
2729  /* increase separation round counter */
2730  stat->nseparounds++;
2731  }
2732  }
2733 
2734  if( root && nsepastallrounds >= maxnsepastallrounds )
2735  {
2736  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
2737  "Truncate separation round because of stalling (%d stall rounds).\n", maxnsepastallrounds);
2738  }
2739 
2740  if( !*lperror )
2741  {
2742  /* update pseudo cost values for continuous variables, if it should be delayed */
2743  SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, FALSE, set->branch_delaypscost) );
2744  }
2745 
2746  /* update lower bound w.r.t. the LP solution */
2747  if( *cutoff )
2748  {
2749  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
2750  }
2751  else if( !(*lperror) )
2752  {
2753  assert(lp->flushed);
2754  assert(lp->solved);
2755 
2756  if( SCIPlpIsRelax(lp) )
2757  {
2758  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2759  }
2760 
2761  /* update node estimate */
2762  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2763 
2764  /* issue LPSOLVED event */
2766  {
2768  SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
2769  SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
2770  }
2771 
2772  /* if the LP is a relaxation and we are not solving exactly, then we may analyze an infeasible or bound exceeding
2773  * LP (not necessary in the root node) and cut off the current node
2774  */
2775  if( !set->misc_exactsolve && !root && SCIPlpIsRelax(lp) && SCIPprobAllColsInLP(transprob, set, lp)
2777  {
2778  SCIP_CALL( SCIPconflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt,
2779  lp, branchcand, eventqueue, cliquetable, NULL) );
2780  *cutoff = TRUE;
2781  }
2782  }
2783  /* check for unboundedness */
2784  if( !(*lperror) )
2785  {
2786  *unbounded = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY);
2787  /* 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 */
2788  }
2789 
2790  lp->installing = FALSE;
2791 
2792  SCIPsetDebugMsg(set, " -> final lower bound: %g (LP status: %d, LP obj: %g)\n",
2793  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp),
2794  (*cutoff || *unbounded) ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
2795 
2796  return SCIP_OKAY;
2797 }
2798 
2799 /** updates the current lower bound with the pseudo objective value, cuts off node by bounding, and applies conflict
2800  * analysis if the pseudo objective lead to the cutoff
2801  */
2802 static
2804  BMS_BLKMEM* blkmem, /**< block memory buffers */
2805  SCIP_SET* set, /**< global SCIP settings */
2806  SCIP_STAT* stat, /**< dynamic problem statistics */
2807  SCIP_PROB* transprob, /**< tranformed problem after presolve */
2808  SCIP_PROB* origprob, /**< original problem */
2809  SCIP_PRIMAL* primal, /**< primal data */
2810  SCIP_TREE* tree, /**< branch and bound tree */
2811  SCIP_REOPT* reopt, /**< reoptimization data structure */
2812  SCIP_LP* lp, /**< LP data */
2813  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2814  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2815  SCIP_CONFLICT* conflict, /**< conflict analysis data */
2816  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2817  SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
2818  )
2819 {
2820  assert(transprob != NULL);
2821  assert(origprob != NULL);
2822  assert(primal != NULL);
2823  assert(cutoff != NULL);
2824 
2825  if( !(*cutoff) )
2826  {
2827  SCIP_NODE* focusnode;
2828  SCIP_Real pseudoobjval;
2829 
2830  /* get current focus node */
2831  focusnode = SCIPtreeGetFocusNode(tree);
2832 
2833  /* update lower bound w.r.t. the pseudo solution */
2834  pseudoobjval = SCIPlpGetPseudoObjval(lp, set, transprob);
2835  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, pseudoobjval);
2836  SCIPsetDebugMsg(set, " -> lower bound: %g [%g] (pseudoobj: %g [%g]), cutoff bound: %g [%g]\n",
2837  SCIPnodeGetLowerbound(focusnode), SCIPprobExternObjval(transprob, origprob, set, SCIPnodeGetLowerbound(focusnode)) + SCIPgetOrigObjoffset(set->scip),
2838  pseudoobjval, SCIPprobExternObjval(transprob, origprob, set, pseudoobjval) + SCIPgetOrigObjoffset(set->scip),
2839  primal->cutoffbound, SCIPprobExternObjval(transprob, origprob, set, primal->cutoffbound) + SCIPgetOrigObjoffset(set->scip));
2840 
2841  /* check for infeasible node by bounding */
2842  if( (set->misc_exactsolve && SCIPnodeGetLowerbound(focusnode) >= primal->cutoffbound)
2843  || (!set->misc_exactsolve && SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)) )
2844  {
2845  SCIPsetDebugMsg(set, "node is cut off by bounding (lower=%g, upper=%g)\n",
2846  SCIPnodeGetLowerbound(focusnode), primal->cutoffbound);
2847  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
2848  *cutoff = TRUE;
2849 
2850  /* call pseudo conflict analysis, if the node is cut off due to the pseudo objective value */
2851  if( pseudoobjval >= primal->cutoffbound && !SCIPsetIsInfinity(set, primal->cutoffbound) && !SCIPsetIsInfinity(set, -pseudoobjval) )
2852  {
2853  SCIP_CALL( SCIPconflictAnalyzePseudo(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, NULL) );
2854  }
2855  }
2856  }
2857 
2858  return SCIP_OKAY;
2859 }
2860 
2861 /** marks all relaxators to be unsolved */
2862 static
2864  SCIP_SET* set, /**< global SCIP settings */
2865  SCIP_RELAXATION* relaxation /**< global relaxation data */
2866  )
2867 {
2868  int r;
2869 
2870  assert(set != NULL);
2871  assert(relaxation != NULL);
2872 
2873  SCIPrelaxationSetSolValid(relaxation, FALSE, FALSE);
2874 
2875  for( r = 0; r < set->nrelaxs; ++r )
2876  SCIPrelaxMarkUnsolved(set->relaxs[r]);
2877 }
2878 
2879 /** solves the current node's LP in a price-and-cut loop */
2880 static
2882  BMS_BLKMEM* blkmem, /**< block memory buffers */
2883  SCIP_SET* set, /**< global SCIP settings */
2884  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2885  SCIP_STAT* stat, /**< dynamic problem statistics */
2886  SCIP_MEM* mem, /**< block memory pools */
2887  SCIP_PROB* origprob, /**< original problem */
2888  SCIP_PROB* transprob, /**< transformed problem after presolve */
2889  SCIP_PRIMAL* primal, /**< primal data */
2890  SCIP_TREE* tree, /**< branch and bound tree */
2891  SCIP_REOPT* reopt, /**< reoptimization data structure */
2892  SCIP_LP* lp, /**< LP data */
2893  SCIP_RELAXATION* relaxation, /**< relaxators */
2894  SCIP_PRICESTORE* pricestore, /**< pricing storage */
2895  SCIP_SEPASTORE* sepastore, /**< separation storage */
2896  SCIP_CUTPOOL* cutpool, /**< global cut pool */
2897  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
2898  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2899  SCIP_CONFLICT* conflict, /**< conflict analysis data */
2900  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2901  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
2902  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2903  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2904  SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
2905  SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
2906  SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
2907  SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
2908  SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
2909  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2910  SCIP_Bool* unbounded, /**< pointer to store TRUE, if an unbounded ray was found in the LP */
2911  SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
2912  SCIP_Bool* pricingaborted /**< pointer to store TRUE, if the pricing was aborted and the lower bound
2913  * must not be used */
2914  )
2915 {
2916  SCIP_Longint nlpiterations;
2917  SCIP_Longint nlps;
2918 
2919  assert(stat != NULL);
2920  assert(tree != NULL);
2921  assert(SCIPtreeHasFocusNodeLP(tree));
2922  assert(cutoff != NULL);
2923  assert(unbounded != NULL);
2924  assert(lperror != NULL);
2925  assert(*cutoff == FALSE);
2926  assert(*unbounded == FALSE);
2927  assert(*lperror == FALSE);
2928 
2929  nlps = stat->nlps;
2930  nlpiterations = stat->nlpiterations;
2931 
2932  if( !initiallpsolved )
2933  {
2934  /* load and solve the initial LP of the node */
2935  SCIP_CALL( solveNodeInitialLP(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
2936  pricestore, sepastore, cutpool, branchcand, eventfilter, eventqueue, cliquetable, newinitconss, cutoff, lperror) );
2937 
2938  assert(*cutoff || *lperror || (lp->flushed && lp->solved));
2939  SCIPsetDebugMsg(set, "price-and-cut-loop: initial LP status: %d, LP obj: %g\n",
2940  SCIPlpGetSolstat(lp),
2941  *cutoff ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
2942 
2943  /* update initial LP iteration counter */
2944  stat->ninitlps += stat->nlps - nlps;
2945  stat->ninitlpiterations += stat->nlpiterations - nlpiterations;
2946 
2947  /* In the root node, we try if the initial LP solution is feasible to avoid expensive setup of data structures in
2948  * separators; in case the root LP is aborted, e.g., by hitting the time limit, we do not check the LP solution
2949  * since the corresponding data structures have not been updated.
2950  */
2951  if( SCIPtreeGetCurrentDepth(tree) == 0 && !(*cutoff) && !(*lperror)
2953  && !SCIPsolveIsStopped(set, stat, FALSE) )
2954  {
2955  SCIP_Bool checklprows;
2956  SCIP_Bool stored;
2957  SCIP_SOL* sol;
2958  SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
2959 
2960  SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
2961 
2963  checklprows = FALSE;
2964  else
2965  checklprows = TRUE;
2966 
2967 #ifndef NDEBUG
2968  /* in the debug mode we want to explicitly check if the solution is feasible if it was stored */
2969  SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
2970  eventqueue, eventfilter, sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
2971 
2972  if( stored )
2973  {
2974  SCIP_Bool feasible;
2975 
2976  SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, FALSE, FALSE, TRUE, TRUE,
2977  checklprows, &feasible) );
2978  assert(feasible);
2979  }
2980 
2981  SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) );
2982 #else
2983  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
2984  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
2985 #endif
2986  if( stored )
2987  {
2988  stat->nlpsolsfound++;
2989 
2990  if( primal->nbestsolsfound != oldnbestsolsfound )
2991  {
2992  stat->nlpbestsolsfound++;
2993  SCIPstoreSolutionGap(set->scip);
2994  }
2995 
2996  if( set->reopt_enable )
2997  {
2998  assert(reopt != NULL);
2999  SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, tree->focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp,
3000  SCIPlpGetSolstat(lp), tree->root == tree->focusnode, TRUE, tree->focusnode->lowerbound,
3001  tree->effectiverootdepth) );
3002  }
3003  }
3004 
3006  *unbounded = TRUE;
3007  }
3008  }
3009  else
3010  {
3011  SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob,
3012  origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE,
3013  cutoff) );
3014  }
3015  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3016 
3017  /* check for infeasible node by bounding */
3018  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
3019 #ifdef SCIP_DEBUG
3020  if( *cutoff )
3021  {
3022  if( SCIPtreeGetCurrentDepth(tree) == 0 )
3023  {
3024  SCIPsetDebugMsg(set, "solution cuts off root node, stop solution process\n");
3025  }
3026  else
3027  {
3028  SCIPsetDebugMsg(set, "solution cuts off node\n");
3029  }
3030  }
3031 #endif
3032 
3033  if( !(*cutoff) && !(*lperror) )
3034  {
3035  SCIP_Longint oldninitconssadded;
3036  SCIP_Longint oldnboundchgs;
3037  SCIP_Longint olddomchgcount;
3038  int oldnpricedvars;
3039  int oldncutsapplied;
3040 
3041  oldnpricedvars = transprob->ncolvars;
3042  oldninitconssadded = stat->ninitconssadded;
3043  oldncutsapplied = SCIPsepastoreGetNCutsApplied(sepastore);
3044  oldnboundchgs = stat->nboundchgs;
3045  olddomchgcount = stat->domchgcount;
3046 
3047  /* solve the LP with price-and-cut*/
3048  SCIP_CALL( priceAndCutLoop(blkmem, set, messagehdlr, stat, mem, transprob, origprob, primal, tree, reopt, lp,
3049  pricestore, sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter,
3050  eventqueue, cliquetable, fullseparation, propagateagain, cutoff, unbounded, lperror, pricingaborted) );
3051 
3052  /* check if the problem was changed and the relaxation needs to be resolved */
3053  if( (transprob->ncolvars != oldnpricedvars) || (stat->ninitconssadded != oldninitconssadded) ||
3054  (SCIPsepastoreGetNCutsApplied(sepastore) != oldncutsapplied) || (stat->nboundchgs != oldnboundchgs) ||
3055  (stat->domchgcount != olddomchgcount) )
3056  {
3057  *solverelaxagain = TRUE;
3058  markRelaxsUnsolved(set, relaxation);
3059  }
3060  }
3061  assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3062 
3063  /* if there is no LP error, then *unbounded should be TRUE, iff the LP solution status is unboundedray */
3064  assert(*lperror || ((SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY) == *unbounded));
3065 
3066  /* 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,
3067  * 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
3068  * is not a feasible lower bound for the solutions in the current subtree.
3069  * In this case, the LP has to be solved to optimality by temporarily removing the cutoff bound.
3070  */
3071  if( (*pricingaborted) && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ITERLIMIT)
3072  && !(*cutoff) )
3073  {
3074  SCIP_Real tmpcutoff;
3075 
3076  /* temporarily disable cutoffbound, which also disables the objective limit */
3077  tmpcutoff = lp->cutoffbound;
3079 
3080  lp->solved = FALSE;
3081  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) );
3082 
3083  /* reinstall old cutoff bound */
3084  lp->cutoffbound = tmpcutoff;
3085 
3086  SCIPsetDebugMsg(set, "re-optimized LP without cutoff bound: LP status: %d, LP obj: %g\n",
3087  SCIPlpGetSolstat(lp), *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
3088 
3089  /* lp solstat should not be objlimit, since the cutoff bound was removed temporarily */
3091  /* lp solstat should not be unboundedray, since the lp was dual feasible */
3093  /* there should be no primal ray, since the lp was dual feasible */
3094  assert(primal->primalray == NULL);
3096  {
3097  *cutoff = TRUE;
3098  }
3099  }
3100 
3101  assert(!(*pricingaborted) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL /* cppcheck-suppress assertWithSideEffect */
3102  || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_NOTSOLVED || SCIPsolveIsStopped(set, stat, FALSE) || (*cutoff));
3103 
3104  assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3105 
3106  /* update node's LP iteration counter */
3107  stat->nnodelps += stat->nlps - nlps;
3108  stat->nnodelpiterations += stat->nlpiterations - nlpiterations;
3109 
3110  /* update number of root node LPs and iterations if the root node was processed */
3111  if( SCIPnodeGetDepth(tree->focusnode) == 0 )
3112  {
3113  stat->nrootlps += stat->nlps - nlps;
3114  stat->nrootlpiterations += stat->nlpiterations - nlpiterations;
3115  }
3116 
3117  return SCIP_OKAY;
3118 }
3119 
3120 /** calls relaxators */
3121 static
3123  SCIP_SET* set, /**< global SCIP settings */
3124  SCIP_STAT* stat, /**< dynamic problem statistics */
3125  SCIP_TREE* tree, /**< branch and bound tree */
3126  SCIP_RELAXATION* relaxation, /**< relaxators */
3127  SCIP_PROB* transprob, /**< transformed problem */
3128  SCIP_PROB* origprob, /**< original problem */
3129  int depth, /**< depth of current node */
3130  SCIP_Bool beforelp, /**< should the relaxators with non-negative or negative priority be called? */
3131  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3132  SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3133  SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3134  SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called
3135  * again */
3136  SCIP_Bool* relaxcalled /**< pointer to store TRUE, if at least one relaxator was called (unmodified
3137  * otherwise) */
3138  )
3139 {
3140  SCIP_RESULT result;
3141  SCIP_Real lowerbound;
3142  int r;
3143 
3144  assert(set != NULL);
3145  assert(relaxation != NULL);
3146  assert(cutoff != NULL);
3147  assert(solvelpagain != NULL);
3148  assert(propagateagain != NULL);
3149  assert(solverelaxagain != NULL);
3150  assert(relaxcalled != NULL);
3151  assert(!(*cutoff));
3152 
3153  /* sort by priority */
3154  SCIPsetSortRelaxs(set);
3155 
3156  for( r = 0; r < set->nrelaxs && !(*cutoff); ++r )
3157  {
3158  if( beforelp != (SCIPrelaxGetPriority(set->relaxs[r]) >= 0) )
3159  continue;
3160 
3161  *relaxcalled = TRUE;
3162 
3163  lowerbound = -SCIPsetInfinity(set);
3164 
3165  SCIP_CALL( SCIPrelaxExec(set->relaxs[r], set, stat, depth, &lowerbound, &result) );
3166 
3167  switch( result )
3168  {
3169  case SCIP_CUTOFF:
3170  *cutoff = TRUE;
3171  SCIPsetDebugMsg(set, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(set->relaxs[r]));
3172  /* @todo does it make sense to proceed if the node is proven to be infeasible? */
3173  return SCIP_OKAY;
3174 
3175  case SCIP_CONSADDED:
3176  *solvelpagain = TRUE; /* the separation for new constraints should be called */
3177  *propagateagain = TRUE; /* the propagation for new constraints should be called */
3178  break;
3179 
3180  case SCIP_REDUCEDDOM:
3181  *solvelpagain = TRUE;
3182  *propagateagain = TRUE;
3183  break;
3184 
3185  case SCIP_SEPARATED:
3186  *solvelpagain = TRUE;
3187  break;
3188 
3189  case SCIP_SUSPENDED:
3190  *solverelaxagain = TRUE;
3191  break;
3192 
3193  case SCIP_SUCCESS:
3194  case SCIP_DIDNOTRUN:
3195  break;
3196 
3197  default:
3198  SCIPerrorMessage("invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(set->relaxs[r]));
3199  return SCIP_INVALIDRESULT;
3200  } /*lint !e788*/
3201 
3202  if( result != SCIP_CUTOFF && result != SCIP_DIDNOTRUN && result != SCIP_SUSPENDED )
3203  {
3204  SCIP_NODE* focusnode;
3205 
3206  focusnode = SCIPtreeGetFocusNode(tree);
3207  assert(focusnode != NULL);
3208  assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
3209 
3210  /* update lower bound w.r.t. the lower bound given by the relaxator */
3211  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, lowerbound);
3212  SCIPsetDebugMsg(set, " -> new lower bound given by relaxator %s: %g\n",
3213  SCIPrelaxGetName(set->relaxs[r]), lowerbound);
3214  }
3215  }
3216 
3217  return SCIP_OKAY;
3218 }
3219 
3220 /** enforces constraints by branching, separation, or domain reduction */
3221 static
3223  BMS_BLKMEM* blkmem, /**< block memory buffers */
3224  SCIP_SET* set, /**< global SCIP settings */
3225  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3226  SCIP_STAT* stat, /**< dynamic problem statistics */
3227  SCIP_PROB* prob, /**< transformed problem after presolve */
3228  SCIP_PRIMAL* primal, /**< primal data */
3229  SCIP_TREE* tree, /**< branch and bound tree */
3230  SCIP_LP* lp, /**< LP data */
3231  SCIP_RELAXATION* relaxation, /**< global relaxation data */
3232  SCIP_SEPASTORE* sepastore, /**< separation storage */
3233  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3234  SCIP_Bool* branched, /**< pointer to store whether a branching was created */
3235  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3236  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the LP/pseudo solution is infeasible */
3237  SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3238  SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3239  SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
3240  SCIP_Bool forced /**< should enforcement of pseudo solution be forced? */
3241  )
3242 {
3243  SCIP_RESULT result;
3244  SCIP_SOL* relaxsol = NULL;
3245  SCIP_Real pseudoobjval;
3246  SCIP_Bool resolved;
3247  SCIP_Bool objinfeasible;
3248  SCIP_Bool enforcerelaxsol;
3249  int h;
3250 
3251  assert(set != NULL);
3252  assert(stat != NULL);
3253  assert(tree != NULL);
3254  assert(SCIPtreeGetFocusNode(tree) != NULL);
3255  assert(branched != NULL);
3256  assert(cutoff != NULL);
3257  assert(infeasible != NULL);
3258  assert(propagateagain != NULL);
3259  assert(solvelpagain != NULL);
3260  assert(solverelaxagain != NULL);
3261  assert(!(*cutoff));
3262  assert(!(*propagateagain));
3263  assert(!(*solvelpagain));
3264  assert(!(*solverelaxagain));
3265 
3266  *branched = FALSE;
3267  /**@todo avoid checking the same pseudosolution twice */
3268 
3269  /* enforce (best) relaxation solution if the LP has a worse objective value */
3270  enforcerelaxsol = SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree)
3271  || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, prob)));
3272 
3273  /* check if all constraint handlers implement the enforelax callback, otherwise enforce the LP solution */
3274  for( h = 0; h < set->nconshdlrs && enforcerelaxsol; ++h )
3275  {
3276  if( set->conshdlrs_enfo[h]->consenforelax == NULL && ((! set->conshdlrs_enfo[h]->needscons) ||
3277  (set->conshdlrs_enfo[h]->nconss > 0)) )
3278  {
3279  SCIP_VERBLEVEL verblevel;
3280 
3281  enforcerelaxsol = FALSE;
3282 
3283  verblevel = SCIP_VERBLEVEL_FULL;
3284 
3285  if( !stat->disableenforelaxmsg && set->disp_verblevel == SCIP_VERBLEVEL_HIGH )
3286  {
3287  verblevel = SCIP_VERBLEVEL_HIGH;
3288 
3289  /* remember that the disable relaxation enforcement message was posted and only post it again if the
3290  * verblevel is SCIP_VERBLEVEL_FULL
3291  */
3292  stat->disableenforelaxmsg = TRUE;
3293  }
3294  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel, "Disable enforcement of relaxation solutions"
3295  " since constraint handler %s does not implement enforelax-callback\n",
3296  SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3297  }
3298  }
3299 
3300  /* enforce constraints by branching, applying additional cutting planes (if LP is being processed),
3301  * introducing new constraints, or tighten the domains
3302  */
3303 #ifndef SCIP_NDEBUG
3304  if( enforcerelaxsol )
3305  {
3306  SCIPsetDebugMsg(set, "enforcing constraints on relaxation solution\n");
3307  }
3308  else
3309  {
3310  SCIPsetDebugMsg(set, "enforcing constraints on %s solution\n", SCIPtreeHasFocusNodeLP(tree) ? "LP" : "pseudo");
3311  }
3312 #endif
3313 
3314  /* check, if the solution is infeasible anyway due to it's objective value */
3315  if( SCIPtreeHasFocusNodeLP(tree) || enforcerelaxsol )
3316  objinfeasible = FALSE;
3317  else
3318  {
3319  pseudoobjval = SCIPlpGetPseudoObjval(lp, set, prob);
3320  objinfeasible = SCIPsetIsFeasLT(set, pseudoobjval, SCIPnodeGetLowerbound(SCIPtreeGetFocusNode(tree)));
3321  }
3322 
3323  /* during constraint enforcement, generated cuts should enter the LP in any case; otherwise, a constraint handler
3324  * would fail to enforce its constraints if it relies on the modification of the LP relaxation
3325  */
3326  SCIPsepastoreStartForceCuts(sepastore);
3327 
3328  /* enforce constraints until a handler resolved an infeasibility with cutting off the node, branching,
3329  * reducing a domain, or separating a cut
3330  * if a constraint handler introduced new constraints to enforce his constraints, the newly added constraints
3331  * have to be enforced themselves
3332  */
3333  resolved = FALSE;
3334 
3335  /* in case the relaxation solution should be enforced, we need to create the corresponding solution for the enforelax callbacks */
3336  if( enforcerelaxsol )
3337  {
3338  SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
3339  }
3340 
3341  for( h = 0; h < set->nconshdlrs && !resolved; ++h )
3342  {
3343  assert(SCIPsepastoreGetNCuts(sepastore) == 0); /* otherwise, the LP should have been resolved first */
3344 
3345  /* enforce LP, pseudo, or relaxation solution */
3346  if( enforcerelaxsol )
3347  {
3348  SCIPsetDebugMsg(set, "enforce relaxation solution with value %g\n", SCIPrelaxationGetSolObj(relaxation));
3349 
3350  SCIP_CALL( SCIPconshdlrEnforceRelaxSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore,
3351  relaxsol, *infeasible, &result) );
3352  }
3353  else if( SCIPtreeHasFocusNodeLP(tree) )
3354  {
3355  SCIPsetDebugMsg(set, "enforce LP solution with value %g\n", SCIPlpGetObjval(lp, set, prob));
3356 
3357  assert(lp->flushed);
3358  assert(lp->solved);
3360  SCIP_CALL( SCIPconshdlrEnforceLPSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore, *infeasible,
3361  &result) );
3362  }
3363  else
3364  {
3365  SCIP_CALL( SCIPconshdlrEnforcePseudoSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, branchcand, *infeasible,
3366  objinfeasible, forced, &result) );
3367  if( SCIPsepastoreGetNCuts(sepastore) != 0 )
3368  {
3369  SCIPerrorMessage("pseudo enforcing method of constraint handler <%s> separated cuts\n",
3370  SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3371  return SCIP_INVALIDRESULT;
3372  }
3373  }
3374  SCIPsetDebugMsg(set, "enforcing of <%s> returned result %d\n", SCIPconshdlrGetName(set->conshdlrs_enfo[h]), result);
3375 
3376  switch( result )
3377  {
3378  case SCIP_CUTOFF:
3379  assert(tree->nchildren == 0);
3380  *cutoff = TRUE;
3381  *infeasible = TRUE;
3382  resolved = TRUE;
3383  SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in enforcement\n",
3384  SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3385  break;
3386 
3387  case SCIP_CONSADDED:
3388  assert(tree->nchildren == 0);
3389  *infeasible = TRUE;
3390  *propagateagain = TRUE; /* the propagation for new constraints should be called */
3391  *solvelpagain = TRUE; /* the separation for new constraints should be called */
3392  *solverelaxagain = TRUE;
3393  markRelaxsUnsolved(set, relaxation);
3394  resolved = TRUE;
3395  break;
3396 
3397  case SCIP_REDUCEDDOM:
3398  assert(tree->nchildren == 0);
3399  *infeasible = TRUE;
3400  *propagateagain = TRUE;
3401  *solvelpagain = TRUE;
3402  *solverelaxagain = TRUE;
3403  markRelaxsUnsolved(set, relaxation);
3404  resolved = TRUE;
3405  break;
3406 
3407  case SCIP_SEPARATED:
3408  assert(tree->nchildren == 0);
3409  assert(SCIPsepastoreGetNCuts(sepastore) > 0);
3410  *infeasible = TRUE;
3411  *solvelpagain = TRUE;
3412  *solverelaxagain = TRUE;
3413  markRelaxsUnsolved(set, relaxation);
3414  resolved = TRUE;
3415  break;
3416 
3417  case SCIP_BRANCHED:
3418  assert(tree->nchildren >= 1);
3419  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3420  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3421  *infeasible = TRUE;
3422  *branched = TRUE;
3423  resolved = TRUE;
3424 
3425  /* increase the number of internal nodes */
3426  stat->ninternalnodes++;
3427  stat->ntotalinternalnodes++;
3428  break;
3429 
3430  case SCIP_SOLVELP:
3431  assert(!SCIPtreeHasFocusNodeLP(tree));
3432  assert(tree->nchildren == 0);
3433  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3434  *infeasible = TRUE;
3435  *solvelpagain = TRUE;
3436  resolved = TRUE;
3437  SCIPtreeSetFocusNodeLP(tree, TRUE); /* the node's LP must be solved */
3438  break;
3439 
3440  case SCIP_INFEASIBLE:
3441  assert(tree->nchildren == 0);
3442  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3443  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3444  *infeasible = TRUE;
3445  break;
3446 
3447  case SCIP_FEASIBLE:
3448  assert(tree->nchildren == 0);
3449  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3450  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3451  break;
3452 
3453  case SCIP_DIDNOTRUN:
3454  assert(tree->nchildren == 0);
3455  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3456  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3457  assert(objinfeasible);
3458  *infeasible = TRUE;
3459  break;
3460 
3461  default:
3462  SCIPerrorMessage("invalid result code <%d> from enforcing method of constraint handler <%s>\n",
3463  result, SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3464  return SCIP_INVALIDRESULT;
3465  } /*lint !e788*/
3466 
3467  /* the enforcement method may add a primal solution, after which the LP status could be set to
3468  * objective limit reached
3469  */
3471  {
3472  *cutoff = TRUE;
3473  *infeasible = TRUE;
3474  resolved = TRUE;
3475  SCIPsetDebugMsg(set, " -> LP exceeded objective limit\n");
3476 
3477  /* If we used the probing mode during branching, it might happen that we added a constraint or global bound
3478  * and returned SCIP_CONSADDED or SCIP_REDUCEDDOM, but when reoptimizing the LP after ending the probing mode,
3479  * this leads to hitting the objective limit. In this case, we do not need to propagate or solve the LP again.
3480  */
3481  *propagateagain = FALSE;
3482  *solvelpagain = FALSE;
3483  }
3484 
3485  assert(!(*branched) || (resolved && !(*cutoff) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3486  assert(!(*cutoff) || (resolved && !(*branched) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3487  assert(*infeasible || (!resolved && !(*branched) && !(*cutoff) && !(*propagateagain) && !(*solvelpagain)));
3488  assert(!(*propagateagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3489  assert(!(*solvelpagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3490  }
3491  assert(!objinfeasible || *infeasible);
3492  assert(resolved == (*branched || *cutoff || *propagateagain || *solvelpagain));
3493  assert(*cutoff || *solvelpagain || SCIPsepastoreGetNCuts(sepastore) == 0);
3494 
3495  /* in case the relaxation solution was enforced, free the created solution */
3496  if( enforcerelaxsol )
3497  {
3498  SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
3499  }
3500 
3501  /* deactivate the cut forcing of the constraint enforcement */
3502  SCIPsepastoreEndForceCuts(sepastore);
3503 
3504  SCIPsetDebugMsg(set, " -> enforcing result: branched=%u, cutoff=%u, infeasible=%u, propagateagain=%u, solvelpagain=%u, resolved=%u\n",
3505  *branched, *cutoff, *infeasible, *propagateagain, *solvelpagain, resolved);
3506 
3507  return SCIP_OKAY;
3508 }
3509 
3510 /** applies the cuts stored in the separation store, or clears the store if the node can be cut off */
3511 static
3513  BMS_BLKMEM* blkmem, /**< block memory buffers */
3514  SCIP_SET* set, /**< global SCIP settings */
3515  SCIP_STAT* stat, /**< dynamic problem statistics */
3516  SCIP_PROB* transprob, /**< transformed problem */
3517  SCIP_PROB* origprob, /**< original problem */
3518  SCIP_TREE* tree, /**< branch and bound tree */
3519  SCIP_REOPT* reopt, /**< reotimization data structure */
3520  SCIP_LP* lp, /**< LP data */
3521  SCIP_RELAXATION* relaxation, /**< relaxators */
3522  SCIP_SEPASTORE* sepastore, /**< separation storage */
3523  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3524  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3525  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3526  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3527  SCIP_Bool root, /**< is this the initial root LP? */
3528  SCIP_EFFICIACYCHOICE efficiacychoice, /**< type of solution to base efficiacy computation on */
3529  SCIP_Bool* cutoff, /**< pointer to whether the node can be cut off */
3530  SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3531  SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3532  SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if the node's relaxation has to be solved again */
3533  )
3534 {
3535  assert(stat != NULL);
3536  assert(cutoff != NULL);
3537  assert(propagateagain != NULL);
3538  assert(solvelpagain != NULL);
3539 
3540  if( *cutoff )
3541  {
3542  /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
3543  SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
3544  }
3545  else if( SCIPsepastoreGetNCuts(sepastore) > 0 )
3546  {
3547  SCIP_Longint olddomchgcount;
3548  int oldncutsapplied;
3549 
3550  olddomchgcount = stat->domchgcount;
3551  oldncutsapplied = SCIPsepastoreGetNCutsApplied(sepastore);
3552  SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
3553  eventqueue, eventfilter, cliquetable, root, efficiacychoice, cutoff) );
3554  *propagateagain = *propagateagain || (stat->domchgcount != olddomchgcount);
3555  *solvelpagain = TRUE;
3556  if( (stat->domchgcount != olddomchgcount) || (SCIPsepastoreGetNCutsApplied(sepastore) != oldncutsapplied) )
3557  {
3558  *solverelaxagain = TRUE;
3559  markRelaxsUnsolved(set, relaxation);
3560  }
3561  }
3562 
3563  return SCIP_OKAY;
3564 }
3565 
3566 /** updates the cutoff, propagateagain, and solverelaxagain status of the current solving loop */
3567 static
3569  SCIP_SET* set, /**< global SCIP settings */
3570  SCIP_STAT* stat, /**< dynamic problem statistics */
3571  SCIP_TREE* tree, /**< branch and bound tree */
3572  int depth, /**< depth of current node */
3573  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3574  SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3575  SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if at least one relaxator should be called again */
3576  )
3577 {
3578  SCIP_NODE* focusnode;
3579  int r;
3580 
3581  assert(set != NULL);
3582  assert(stat != NULL);
3583  assert(cutoff != NULL);
3584  assert(propagateagain != NULL);
3585  assert(solverelaxagain != NULL);
3586 
3587  /* check, if the path was cutoff */
3588  *cutoff = *cutoff || (tree->cutoffdepth <= depth);
3589 
3590  /* check if branching was already performed */
3591  if( tree->nchildren == 0 )
3592  {
3593  /* check, if the focus node should be repropagated */
3594  focusnode = SCIPtreeGetFocusNode(tree);
3595  *propagateagain = *propagateagain || SCIPnodeIsPropagatedAgain(focusnode);
3596 
3597  /* check, if one of the external relaxations should be solved again */
3598  for( r = 0; r < set->nrelaxs && !(*solverelaxagain); ++r )
3599  *solverelaxagain = *solverelaxagain || ( !SCIPrelaxIsSolved(set->relaxs[r], stat) );
3600  }
3601  else
3602  {
3603  /* if branching was performed, avoid another node loop iteration */
3604  *propagateagain = FALSE;
3605  *solverelaxagain = FALSE;
3606  }
3607 }
3608 
3609 /** propagate domains and solve relaxation and lp */
3610 static
3612  BMS_BLKMEM* blkmem, /**< block memory buffers */
3613  SCIP_SET* set, /**< global SCIP settings */
3614  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3615  SCIP_STAT* stat, /**< dynamic problem statistics */
3616  SCIP_MEM* mem, /**< block memory pools */
3617  SCIP_PROB* origprob, /**< original problem */
3618  SCIP_PROB* transprob, /**< transformed problem after presolve */
3619  SCIP_PRIMAL* primal, /**< primal data */
3620  SCIP_TREE* tree, /**< branch and bound tree */
3621  SCIP_REOPT* reopt, /**< reoptimization data structure */
3622  SCIP_LP* lp, /**< LP data */
3623  SCIP_RELAXATION* relaxation, /**< global relaxation data */
3624  SCIP_PRICESTORE* pricestore, /**< pricing storage */
3625  SCIP_SEPASTORE* sepastore, /**< separation storage */
3626  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3627  SCIP_CUTPOOL* cutpool, /**< global cut pool */
3628  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
3629  SCIP_CONFLICT* conflict, /**< conflict analysis data */
3630  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
3631  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3632  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3633  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3634  SCIP_NODE* focusnode, /**< focused node */
3635  int actdepth, /**< depth in the b&b tree */
3636  SCIP_Bool propagate, /**< should we propagate */
3637  SCIP_Bool solvelp, /**< should we solve the lp */
3638  SCIP_Bool solverelax, /**< should we solve the relaxation */
3639  SCIP_Bool forcedlpsolve, /**< is there a need for a solve lp */
3640  SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
3641  SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
3642  SCIP_Longint* afterlpproplps, /**< pointer to store the last LP count for which AFTERLP propagation was performed */
3643  SCIP_HEURTIMING* heurtiming, /**< timing for running heuristics after propagation call */
3644  int* nlperrors, /**< pointer to store the number of lp errors */
3645  SCIP_Bool* fullpropagation, /**< pointer to store whether we want to do a fullpropagation next time */
3646  SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
3647  SCIP_Bool* lpsolved, /**< pointer to store whether the lp was solved */
3648  SCIP_Bool* relaxcalled, /**< pointer to store whether a relaxator was called; initialized with last loop's result */
3649  SCIP_Bool* solvelpagain, /**< pointer to store whether we want to solve the lp again */
3650  SCIP_Bool* solverelaxagain, /**< pointer to store whether we want to solve the relaxation again */
3651  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
3652  SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
3653  SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
3654  SCIP_Bool* stopped, /**< pointer to store whether solving was interrupted */
3655  SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
3656  SCIP_Bool* pricingaborted, /**< pointer to store TRUE, if the pricing was aborted and the lower bound must not be used */
3657  SCIP_Bool* forcedenforcement /**< pointer to store whether the enforcement of pseudo solution should be forced */
3658  )
3659 {
3660  SCIP_Bool newinitconss;
3661 
3662  assert(set != NULL);
3663  assert(stat != NULL);
3664  assert(origprob != NULL);
3665  assert(transprob != NULL);
3666  assert(tree != NULL);
3667  assert(lp != NULL);
3668  assert(primal != NULL);
3669  assert(pricestore != NULL);
3670  assert(sepastore != NULL);
3671  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3672  assert(branchcand != NULL);
3673  assert(cutpool != NULL);
3674  assert(delayedcutpool != NULL);
3675  assert(conflict != NULL);
3676  assert(SCIPconflictGetNConflicts(conflict) == 0);
3677  assert(eventfilter != NULL);
3678  assert(eventqueue != NULL);
3679  assert(focusnode != NULL);
3680  assert(heurtiming != NULL);
3681  assert(nlperrors != NULL);
3682  assert(fullpropagation != NULL);
3683  assert(propagateagain != NULL);
3684  assert(afterlpproplps != NULL);
3685  assert(lpsolved != NULL);
3686  assert(solvelpagain != NULL);
3687  assert(solverelaxagain != NULL);
3688  assert(cutoff != NULL);
3689  assert(postpone != NULL);
3690  assert(unbounded != NULL);
3691  assert(lperror != NULL);
3692  assert(pricingaborted != NULL);
3693  assert(forcedenforcement != NULL);
3694 
3695  newinitconss = FALSE;
3696 
3697  if( !(*cutoff) && !(*postpone) )
3698  {
3699  SCIP_Longint oldninitconssadded;
3700  SCIP_Longint oldnboundchgs;
3701  SCIP_Bool lpwasflushed;
3702 
3703  lpwasflushed = lp->flushed;
3704  oldnboundchgs = stat->nboundchgs;
3705  oldninitconssadded = stat->ninitconssadded;
3706 
3707  /* call after LP propagators */
3708  if( ((*afterlpproplps) < stat->nnodelps && (*lpsolved)) || (*relaxcalled) )
3709  {
3710  SCIP_CALL( propagateDomains(blkmem, set, stat, primal, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3711  SCIP_PROPTIMING_AFTERLPLOOP, cutoff, postpone) );
3712  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3713 
3714  /* check, if the path was cutoff */
3715  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3716  *afterlpproplps = stat->nnodelps;
3717  propagate = propagate || (stat->nboundchgs > oldnboundchgs);
3718  }
3719 
3720  /* call before LP propagators */
3721  if( propagate && !(*cutoff) )
3722  {
3723  SCIP_CALL( propagateDomains(blkmem, set, stat, primal, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3724  SCIP_PROPTIMING_BEFORELP, cutoff, postpone) );
3725  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3726  }
3727 
3728  newinitconss = (stat->ninitconssadded != oldninitconssadded);
3729  *fullpropagation = FALSE;
3730 
3731  /* check, if the path was cutoff */
3732  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3733 
3734  /* if the LP was flushed and is now no longer flushed, a bound change occurred, and the LP has to be resolved;
3735  * we also have to solve the LP if new intial constraints were added which need to be added to the LP
3736  */
3737  solvelp = solvelp || (lpwasflushed && (!lp->flushed || newinitconss));
3738  solverelax = solverelax || newinitconss;
3739 
3740  /* the number of bound changes was increased by the propagation call, thus the relaxation should be solved again */
3741  if( stat->nboundchgs > oldnboundchgs )
3742  {
3743  /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
3744  * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
3745  * bound of the node needs to be updated
3746  */
3747  if( !solvelp && lp->flushed && lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
3748  {
3749  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
3750  SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
3751  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
3752 
3753  if( SCIPtreeHasFocusNodeLP(tree) )
3754  {
3755  /* update node estimate */
3756  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
3757 
3758  if( actdepth == 0 && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
3759  SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
3760  }
3761  }
3762 
3763  solverelax = TRUE;
3764  markRelaxsUnsolved(set, relaxation);
3765  }
3766 
3767  /* update lower bound with the pseudo objective value, and cut off node by bounding */
3768  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
3769  conflict, cliquetable, cutoff) );
3770  }
3771  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3772 
3773  if( *postpone )
3774  return SCIP_OKAY;
3775 
3776  /* call primal heuristics that are applicable after propagation loop before lp solve;
3777  * the first time we go here, we call the before node heuristics instead
3778  */
3779  if( !(*cutoff) && !SCIPtreeProbing(tree) )
3780  {
3781  /* if the heuristics find a new incumbent solution, propagate again */
3782  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, *heurtiming,
3783  FALSE, propagateagain, unbounded) );
3784  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3785 
3786  *heurtiming = SCIP_HEURTIMING_AFTERPROPLOOP;
3787 
3788  /* check if primal heuristics found a solution and we therefore reached a solution limit */
3789  if( SCIPsolveIsStopped(set, stat, FALSE) )
3790  {
3791  /* cppcheck-suppress unassignedVariable */
3792  SCIP_NODE* node;
3793 
3794  /* we reached a solution limit and do not want to continue the processing of the current node, but in order to
3795  * allow restarting the optimization process later, we need to create a "branching" with only one child node that
3796  * is a copy of the focusnode
3797  */
3799  SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) );
3800  assert(tree->nchildren >= 1);
3801  *stopped = TRUE;
3802  return SCIP_OKAY;
3803  }
3804 
3805  /* if diving produced an LP error, switch back to non-LP node */
3806  if( lp->resolvelperror )
3807  {
3809  lp->resolvelperror = FALSE;
3810  }
3811 
3812  if( *propagateagain )
3813  {
3814  *solvelpagain = solvelp;
3815  *solverelaxagain = solverelax;
3816 
3817  return SCIP_OKAY;
3818  }
3819  }
3820 
3821  /* solve external relaxations with non-negative priority */
3822  *relaxcalled = FALSE;
3823  if( solverelax && !(*cutoff) )
3824  {
3825  /* clear the storage of external branching candidates */
3826  SCIPbranchcandClearExternCands(branchcand);
3827 
3828  SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, TRUE,
3829  cutoff, propagateagain, solvelpagain, solverelaxagain, relaxcalled) );
3830  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3831 
3832  /* check, if the path was cutoff */
3833  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3834 
3835  /* apply found cuts */
3836  SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
3837  eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
3838  solvelpagain, solverelaxagain) );
3839 
3840  /* update lower bound with the pseudo objective value, and cut off node by bounding */
3841  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
3842  }
3843  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3844 
3845  /* check, if we want to solve the LP at this node */
3846  if( solvelp && !(*cutoff) && SCIPtreeHasFocusNodeLP(tree) )
3847  {
3848  *lperror = FALSE;
3849  *unbounded = FALSE;
3850 
3851  /* solve the node's LP */
3852  SCIP_CALL( solveNodeLP(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation, pricestore,
3853  sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable,
3854  initiallpsolved, fullseparation, newinitconss, propagateagain, solverelaxagain, cutoff, unbounded, lperror, pricingaborted) );
3855 
3856  *lpsolved = TRUE;
3857  *solvelpagain = FALSE;
3858  SCIPsetDebugMsg(set, " -> LP status: %d, LP obj: %g, iter: %" SCIP_LONGINT_FORMAT ", count: %" SCIP_LONGINT_FORMAT "\n",
3859  SCIPlpGetSolstat(lp),
3860  *cutoff ? SCIPsetInfinity(set) : (*lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob)),
3861  stat->nlpiterations, stat->lpcount);
3862 
3863  /* check, if the path was cutoff */
3864  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3865 
3866  /* if an error occured during LP solving, switch to pseudo solution */
3867  if( *lperror )
3868  {
3869  if( forcedlpsolve )
3870  {
3871  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
3872  stat->nnodes, stat->nlps);
3873  return SCIP_LPERROR;
3874  }
3876  ++(*nlperrors);
3877  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
3878  "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
3879  stat->nnodes, stat->nlps, *nlperrors);
3880  }
3881 
3883  {
3885  *forcedenforcement = TRUE;
3886 
3887  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
3888  "(node %" SCIP_LONGINT_FORMAT ") LP solver hit %s limit in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead\n",
3889  stat->nnodes, SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT ? "time" : "iteration", stat->nlps);
3890  }
3891 
3893  {
3894  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
3895  "(node %" SCIP_LONGINT_FORMAT ") LP relaxation is unbounded (LP %" SCIP_LONGINT_FORMAT ")\n", stat->nnodes, stat->nlps);
3896  }
3897 
3898  /* if we solve exactly, the LP claims to be infeasible but the infeasibility could not be proved,
3899  * we have to forget about the LP and use the pseudo solution instead
3900  */
3901  if( !(*cutoff) && !(*lperror) && (set->misc_exactsolve || *pricingaborted) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE
3902  && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound )
3903  {
3904  if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 && transprob->ncontvars > 0 )
3905  {
3906  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",
3907  stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, transprob->ncontvars);
3908  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") -> have to call PerPlex() (feature not yet implemented)\n", stat->nnodes);
3909  /**@todo call PerPlex */
3910  return SCIP_LPERROR;
3911  }
3912  else
3913  {
3915  *forcedenforcement = TRUE;
3916 
3917  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
3918  "(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",
3919  stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, SCIPbranchcandGetNPseudoCands(branchcand));
3920  }
3921  }
3922 
3923  /* update lower bound with the pseudo objective value, and cut off node by bounding */
3924  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
3925  cliquetable, cutoff) );
3926  }
3927  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3928  assert(*cutoff || !SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3929 
3930  /* reset solverelaxagain if no relaxations were solved up to this point (the LP-changes are already included in
3931  * relaxators called after the LP)
3932  */
3933  *solverelaxagain = *solverelaxagain && *relaxcalled;
3934 
3935  /* solve external relaxations with negative priority */
3936  if( solverelax && !(*cutoff) )
3937  {
3938  SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, FALSE, cutoff,
3939  propagateagain, solvelpagain, solverelaxagain, relaxcalled) );
3940  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3941 
3942  /* check, if the path was cutoff */
3943  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3944 
3945  /* apply found cuts */
3946  SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
3947  eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
3948  solvelpagain, solverelaxagain) );
3949 
3950  /* update lower bound with the pseudo objective value, and cut off node by bounding */
3951  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
3952  cliquetable, cutoff) );
3953  }
3954  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3955 
3956  return SCIP_OKAY;
3957 }
3958 
3959 /** check if a restart can be performed */
3960 #ifndef NDEBUG
3961 static
3963  SCIP_SET* set, /**< global SCIP settings */
3964  SCIP_STAT* stat /**< dynamic problem statistics */
3965  )
3966 {
3967  assert(set != NULL);
3968  assert(stat != NULL);
3969 
3970  return (set->nactivepricers == 0 && !set->reopt_enable
3971  && (set->presol_maxrestarts == -1 || stat->nruns <= set->presol_maxrestarts)
3972  && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts));
3973 }
3974 #else
3975 #define restartAllowed(set,stat) ((set)->nactivepricers == 0 && !set->reopt_enable && ((set)->presol_maxrestarts == -1 || (stat)->nruns <= (set)->presol_maxrestarts) \
3976  && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts))
3977 #endif
3978 
3979 /** solves the focus node */
3980 static
3982  BMS_BLKMEM* blkmem, /**< block memory buffers */
3983  SCIP_SET* set, /**< global SCIP settings */
3984  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3985  SCIP_STAT* stat, /**< dynamic problem statistics */
3986  SCIP_MEM* mem, /**< block memory pools */
3987  SCIP_PROB* origprob, /**< original problem */
3988  SCIP_PROB* transprob, /**< transformed problem after presolve */
3989  SCIP_PRIMAL* primal, /**< primal data */
3990  SCIP_TREE* tree, /**< branch and bound tree */
3991  SCIP_REOPT* reopt, /**< reoptimization data structure */
3992  SCIP_LP* lp, /**< LP data */
3993  SCIP_RELAXATION* relaxation, /**< global relaxation data */
3994  SCIP_PRICESTORE* pricestore, /**< pricing storage */
3995  SCIP_SEPASTORE* sepastore, /**< separation storage */
3996  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3997  SCIP_CUTPOOL* cutpool, /**< global cut pool */
3998  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
3999  SCIP_CONFLICT* conflict, /**< conflict analysis data */
4000  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4001  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4002  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4003  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4004  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
4005  SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
4006  SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
4007  SCIP_Bool* infeasible, /**< pointer to store whether the focus node's solution is infeasible */
4008  SCIP_Bool* restart, /**< should solving process be started again with presolving? */
4009  SCIP_Bool* afternodeheur, /**< pointer to store whether AFTERNODE heuristics were already called */
4010  SCIP_Bool* stopped /**< pointer to store whether solving was interrupted */
4011  )
4012 {
4013  SCIP_NODE* focusnode;
4014  SCIP_Longint lastdomchgcount;
4015  SCIP_Longint afterlpproplps;
4016  SCIP_Real restartfac;
4017  SCIP_Longint lastlpcount;
4018  SCIP_HEURTIMING heurtiming;
4019  int actdepth;
4020  int nlperrors;
4021  int nloops;
4022  SCIP_Bool foundsol = FALSE;
4023  SCIP_Bool focusnodehaslp;
4024  SCIP_Bool lpsolved;
4025  SCIP_Bool initiallpsolved;
4026  SCIP_Bool fullseparation;
4027  SCIP_Bool solverelaxagain;
4028  SCIP_Bool solvelpagain;
4029  SCIP_Bool propagateagain;
4030  SCIP_Bool fullpropagation;
4031  SCIP_Bool branched;
4032  SCIP_Bool forcedlpsolve;
4033  SCIP_Bool wasforcedlpsolve;
4034  SCIP_Bool pricingaborted;
4035 
4036  assert(set != NULL);
4037  assert(stat != NULL);
4038  assert(origprob != NULL);
4039  assert(transprob != NULL);
4040  assert(tree != NULL);
4041  assert(primal != NULL);
4042  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4043  assert(SCIPconflictGetNConflicts(conflict) == 0);
4044  assert(cutoff != NULL);
4045  assert(postpone != NULL);
4046  assert(unbounded != NULL);
4047  assert(infeasible != NULL);
4048  assert(restart != NULL);
4049  assert(afternodeheur != NULL);
4050 
4051  *cutoff = FALSE;
4052  *postpone = FALSE;
4053  *unbounded = FALSE;
4054  *infeasible = FALSE;
4055  *restart = FALSE;
4056  *afternodeheur = FALSE;
4057  *stopped = FALSE;
4058  pricingaborted = FALSE;
4059 
4060  focusnode = SCIPtreeGetFocusNode(tree);
4061  assert(focusnode != NULL);
4062  assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
4063  actdepth = SCIPnodeGetDepth(focusnode);
4064 
4065  /* invalidate relaxation solution */
4066  SCIPrelaxationSetSolValid(relaxation, FALSE, FALSE);
4067 
4068  /* clear the storage of external branching candidates */
4069  SCIPbranchcandClearExternCands(branchcand);
4070 
4071  SCIPsetDebugMsg(set, "Processing node %" SCIP_LONGINT_FORMAT " in depth %d, %d siblings\n",
4072  stat->nnodes, actdepth, tree->nsiblings);
4073  SCIPsetDebugMsg(set, "current pseudosolution: obj=%g\n", SCIPlpGetPseudoObjval(lp, set, transprob));
4074  /*debug(SCIPprobPrintPseudoSol(transprob, set));*/
4075 
4076  /* check, if we want to solve the LP at the selected node:
4077  * - solve the LP, if the lp solve depth and frequency demand solving
4078  * - solve the root LP, if the LP solve frequency is set to 0
4079  * - solve the root LP, if there are continuous variables present
4080  * - don't solve the node if its cut off by the pseudo objective value anyway
4081  */
4082  focusnodehaslp = (set->lp_solvedepth == -1 || actdepth <= set->lp_solvedepth);
4083  focusnodehaslp = focusnodehaslp && (set->lp_solvefreq >= 1 && actdepth % set->lp_solvefreq == 0);
4084  focusnodehaslp = focusnodehaslp || (actdepth == 0 && set->lp_solvefreq == 0);
4085  focusnodehaslp = focusnodehaslp && SCIPsetIsLT(set, SCIPlpGetPseudoObjval(lp, set, transprob), primal->cutoffbound);
4086  focusnodehaslp = set->reopt_enable ? focusnodehaslp && SCIPreoptGetSolveLP(reopt, set, focusnode) : focusnodehaslp;
4087  SCIPtreeSetFocusNodeLP(tree, focusnodehaslp);
4088 
4089  /* external node solving loop:
4090  * - propagate domains
4091  * - solve SCIP_LP
4092  * - enforce constraints
4093  * if a constraint handler adds constraints to enforce its own constraints, both, propagation and LP solving
4094  * is applied again (if applicable on current node); however, if the new constraints don't have the enforce flag set,
4095  * it is possible, that the current infeasible solution is not cut off; in this case, we have to declare the solution
4096  * infeasible and perform a branching
4097  */
4098  lastdomchgcount = stat->domchgcount;
4099  lastlpcount = stat->lpcount;
4100  initiallpsolved = FALSE;
4101  fullseparation = TRUE;
4102  heurtiming = SCIP_HEURTIMING_BEFORENODE;
4103  nlperrors = 0;
4104  stat->npricerounds = 0;
4105  stat->nseparounds = 0;
4106  solverelaxagain = TRUE;
4107  solvelpagain = TRUE;
4108  propagateagain = TRUE;
4109  fullpropagation = TRUE;
4110  forcedlpsolve = FALSE;
4111  nloops = 0;
4112 
4113  while( !(*cutoff) && !(*postpone) && (solverelaxagain || solvelpagain || propagateagain) && nlperrors < MAXNLPERRORS && !(*restart) )
4114  {
4115  SCIP_Bool lperror;
4116  SCIP_Bool solverelax;
4117  SCIP_Bool solvelp;
4118  SCIP_Bool propagate;
4119  SCIP_Bool forcedenforcement;
4120  SCIP_Bool relaxcalled;
4121 
4122  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4123 
4124  *unbounded = FALSE;
4125  *infeasible = FALSE;
4126  foundsol = FALSE;
4127 
4128  nloops++;
4129  lperror = FALSE;
4130  lpsolved = FALSE;
4131  relaxcalled = FALSE;
4132  forcedenforcement = FALSE;
4133  afterlpproplps = -1L;
4134 
4135  while( !lperror && !(*cutoff) && (propagateagain || solvelpagain || solverelaxagain
4136  || (afterlpproplps < stat->nnodelps && lpsolved) || relaxcalled) )
4137  {
4138  solverelax = solverelaxagain;
4139  solverelaxagain = FALSE;
4140  solvelp = solvelpagain;
4141  solvelpagain = FALSE;
4142  propagate = propagateagain;
4143  propagateagain = FALSE;
4144 
4145  /* update lower bound with the pseudo objective value, and cut off node by bounding */
4146  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
4147  conflict, cliquetable, cutoff) );
4148 
4149  /* propagate domains before lp solving and solve relaxation and lp */
4150  SCIPsetDebugMsg(set, " -> node solving loop: call propagators that are applicable before%s LP is solved\n",
4151  lpsolved ? " and after" : "");
4152  SCIP_CALL( propAndSolve(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp,
4153  relaxation, pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter,
4154  eventqueue, cliquetable, focusnode, actdepth, propagate, solvelp, solverelax, forcedlpsolve, initiallpsolved,
4155  fullseparation, &afterlpproplps, &heurtiming, &nlperrors, &fullpropagation, &propagateagain, &lpsolved, &relaxcalled,
4156  &solvelpagain, &solverelaxagain, cutoff, postpone, unbounded, stopped, &lperror, &pricingaborted, &forcedenforcement) );
4157  initiallpsolved |= lpsolved;
4158 
4159  /* time or solution limit was hit and we already created a dummy child node to terminate fast */
4160  if( *stopped )
4161  return SCIP_OKAY;
4162  }
4163  fullseparation = FALSE;
4164 
4165  /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4166  updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain);
4167 
4168  /* call primal heuristics that should be applied after the LP relaxation of the node was solved;
4169  * if this is the first loop of the root node, call also AFTERNODE heuristics already here, since they might help
4170  * to improve the primal bound, thereby producing additional reduced cost strengthenings and strong branching
4171  * bound fixings which also might lead to a restart
4172  */
4173  if( !(*postpone) && (!(*cutoff) || SCIPtreeGetNNodes(tree) > 0) )
4174  {
4175  if( actdepth == 0 && !(*afternodeheur) )
4176  {
4177  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL,
4178  SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE, *cutoff, &foundsol, unbounded) );
4179  *afternodeheur = TRUE; /* the AFTERNODE heuristics should not be called again after the node */
4180  }
4181  else if( lpsolved || SCIPrelaxationIsSolValid(relaxation) )
4182  {
4183  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_AFTERLPLOOP,
4184  *cutoff, &foundsol, unbounded) );
4185  }
4186  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4187 
4188  /* heuristics might have found a solution or set the cutoff bound such that the current node is cut off */
4189  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4190  }
4191 
4192  /* check if heuristics leave us with an invalid LP */
4193  if( lp->resolvelperror )
4194  {
4195  if( forcedlpsolve )
4196  {
4197  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4198  stat->nnodes, stat->nlps);
4199  return SCIP_LPERROR;
4200  }
4202  lp->resolvelperror = FALSE;
4203  nlperrors++;
4204  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4205  "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4206  stat->nnodes, stat->nlps, nlperrors);
4207  }
4208 
4209  if( pricingaborted && !(*cutoff) && SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL )
4210  {
4212 
4213  /* if we just ran into the time limit this is not really a numerical trouble;
4214  * however, if this is not the case, we print messages about numerical troubles in the current LP
4215  */
4216  if( !SCIPsolveIsStopped(set, stat, FALSE) )
4217  {
4218  if( forcedlpsolve )
4219  {
4220  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4221  stat->nnodes, stat->nlps);
4222  return SCIP_LPERROR;
4223  }
4224  nlperrors++;
4225  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4226  "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4227  stat->nnodes, stat->nlps, nlperrors);
4228  }
4229  }
4230 
4231  /* if an improved solution was found, propagate and solve the relaxations again */
4232  if( foundsol )
4233  {
4234  propagateagain = TRUE;
4235  solvelpagain = TRUE;
4236  solverelaxagain = TRUE;
4237  markRelaxsUnsolved(set, relaxation);
4238  }
4239 
4240  /* enforce constraints */
4241  branched = FALSE;
4242  if( !(*postpone) && !(*cutoff) && !solverelaxagain && !solvelpagain && !propagateagain )
4243  {
4244  /* if the solution changed since the last enforcement, we have to completely reenforce it; otherwise, we
4245  * only have to enforce the additional constraints added in the last enforcement, but keep the infeasible
4246  * flag TRUE in order to not declare the infeasible solution feasible due to disregarding the already
4247  * enforced constraints
4248  */
4249  if( lastdomchgcount != stat->domchgcount || lastlpcount != stat->lpcount )
4250  {
4251  lastdomchgcount = stat->domchgcount;
4252  lastlpcount = stat->lpcount;
4253  *infeasible = FALSE;
4254  }
4255 
4256  /* call constraint enforcement */
4257  SCIP_CALL( enforceConstraints(blkmem, set, messagehdlr, stat, transprob, primal, tree, lp, relaxation, sepastore,
4258  branchcand, &branched, cutoff, infeasible, &propagateagain, &solvelpagain, &solverelaxagain,
4259  forcedenforcement) );
4260  assert(branched == (tree->nchildren > 0));
4261  assert(!branched || (!(*cutoff) && *infeasible && !propagateagain && !solvelpagain));
4262  assert(!(*cutoff) || (!branched && *infeasible && !propagateagain && !solvelpagain));
4263  assert(*infeasible || (!branched && !(*cutoff) && !propagateagain && !solvelpagain));
4264  assert(!propagateagain || (!branched && !(*cutoff) && *infeasible));
4265  assert(!solvelpagain || (!branched && !(*cutoff) && *infeasible));
4266 
4267  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4268 
4269  /* apply found cuts */
4270  SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4271  eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain,
4272  &solvelpagain, &solverelaxagain) );
4273 
4274  /* update lower bound with the pseudo objective value, and cut off node by bounding */
4275  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4276 
4277  /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4278  updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain);
4279  }
4280  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4281 
4282  /* The enforcement detected no infeasibility, so, no branching was performed,
4283  * but the pricing was aborted and the current feasible solution does not have to be the
4284  * best solution in the current subtree --> we have to do a pseudo branching,
4285  * so we set infeasible TRUE and add the current solution to the solution pool
4286  */
4287  if( pricingaborted && !(*infeasible) && !(*cutoff) && !(*postpone) )
4288  {
4289  SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
4290  SCIP_SOL* sol;
4291  SCIP_Bool stored;
4292 
4293  /* in case the relaxation was enforced add this solution, otherwise decide between LP and pseudosol */
4294  if( SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree)
4295  || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4296  {
4297  SCIP_SOL* relaxsol;
4298 
4299  SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4300 
4301  SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4302  eventqueue, eventfilter, relaxsol, FALSE, FALSE, TRUE, TRUE, TRUE,
4303  &stored) );
4304 
4305  SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
4306 
4307  if( stored )
4308  {
4309  stat->nrelaxsolsfound++;
4310 
4311  if( primal->nbestsolsfound != oldnbestsolsfound )
4312  {
4313  stat->nrelaxbestsolsfound++;
4314  SCIPstoreSolutionGap(set->scip);
4315  }
4316  }
4317  }
4318  else
4319  {
4320  SCIP_CALL( SCIPsolCreateCurrentSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4321  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4322  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
4323 
4324  if( stored )
4325  {
4326  stat->nlpsolsfound++;
4327 
4328  if( primal->nbestsolsfound != oldnbestsolsfound )
4329  {
4330  stat->nlpbestsolsfound++;
4331  SCIPstoreSolutionGap(set->scip);
4332  }
4333  }
4334  }
4335 
4336  *infeasible = TRUE;
4337  }
4338 
4339  /* if the node is infeasible, but no constraint handler could resolve the infeasibility
4340  * -> branch on LP, external candidates, or the pseudo solution
4341  * -> e.g. select non-fixed binary or integer variable x with value x', create three
4342  * sons: x <= x'-1, x = x', and x >= x'+1.
4343  * In the left and right branch, the current solution is cut off. In the middle
4344  * branch, the constraints can hopefully reduce domains of other variables to cut
4345  * off the current solution.
4346  * In LP branching, we cannot allow adding constraints, because this does not necessary change the LP and can
4347  * therefore lead to an infinite loop.
4348  */
4349  wasforcedlpsolve = forcedlpsolve;
4350  forcedlpsolve = FALSE;
4351  if( (*infeasible) && !(*cutoff) && !(*postpone)
4352  && (!(*unbounded) || SCIPbranchcandGetNExternCands(branchcand) > 0 || SCIPbranchcandGetNPseudoCands(branchcand) > 0)
4353  && !solverelaxagain && !solvelpagain && !propagateagain && !branched )
4354  {
4355  SCIP_RESULT result = SCIP_DIDNOTRUN;
4356  int nlpcands = 0;
4357 
4358  if( SCIPtreeHasFocusNodeLP(tree) )
4359  {
4360  SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpcands, NULL, NULL) );
4361  }
4362 
4363  if ( nlpcands > 0 || SCIPbranchcandGetNExternCands(branchcand) > 0 )
4364  {
4365  /* If there are LP candidates and their maximal priority is at least the maximal priority of the external
4366  * candidates, then branch on the LP candidates. Note that due to implicit integer variables,
4367  * SCIPbranchcandGetLPMaxPrio(branchcand) might be finite and SCIPbranchcandGetNPrioLPCands(branchcand) > 0,
4368  * but nlpcands == 0. */
4369  if ( SCIPbranchcandGetLPMaxPrio(branchcand) >= SCIPbranchcandGetExternMaxPrio(branchcand) && nlpcands > 0 )
4370  {
4371  assert( SCIPbranchcandGetNPrioLPCands(branchcand) > 0 );
4372  assert( nlpcands > 0 );
4373 
4374  /* branch on LP solution */
4375  SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on LP solution with %d fractionals\n",
4376  SCIPnodeGetDepth(focusnode), nlpcands);
4377  SCIP_CALL( SCIPbranchExecLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4378  eventqueue, primal->cutoffbound, FALSE, &result) );
4379  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4380  assert(result != SCIP_DIDNOTRUN && result != SCIP_DIDNOTFIND);
4381  }
4382  else
4383  {
4384  assert( SCIPbranchcandGetNPrioExternCands(branchcand) > 0 );
4385  assert( SCIPbranchcandGetNExternCands(branchcand) > 0 );
4386 
4387  /* branch on external candidates */
4388  SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on %d external branching candidates.\n",
4389  SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNExternCands(branchcand));
4390  SCIP_CALL( SCIPbranchExecExtern(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4391  eventqueue, primal->cutoffbound, TRUE, &result) );
4392  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4393  }
4394  }
4395 
4396  if( result == SCIP_DIDNOTRUN || result == SCIP_DIDNOTFIND )
4397  {
4398  /* branch on pseudo solution */
4399  SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on pseudo solution with %d unfixed integers\n",
4400  SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNPseudoCands(branchcand));
4401  SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
4402  primal->cutoffbound, TRUE, &result) );
4403  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4404  }
4405 
4406  /* SCIP cannot guarantee convergence if it is necessary to branch on unbounded variables */
4407  if( result == SCIP_BRANCHED )
4408  {
4409  SCIP_VAR* var = stat->lastbranchvar;
4410 
4411  if( var != NULL && !stat->branchedunbdvar && SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS
4413  {
4414  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
4415  "Starting spatial branch-and-bound on unbounded variable <%s> ([%g,%g]) - cannot guarantee finite termination.\n",
4417  stat->branchedunbdvar = TRUE;
4418  }
4419  }
4420 
4421  switch( result )
4422  {
4423  case SCIP_CUTOFF:
4424  assert(tree->nchildren == 0);
4425  *cutoff = TRUE;
4426  SCIPsetDebugMsg(set, " -> branching rule detected cutoff\n");
4427  break;
4428  case SCIP_CONSADDED:
4429  assert(tree->nchildren == 0);
4430  if( nlpcands > 0 )
4431  {
4432  SCIPerrorMessage("LP branching rule added constraint, which was not allowed this time\n");
4433  return SCIP_INVALIDRESULT;
4434  }
4435  propagateagain = TRUE;
4436  solvelpagain = TRUE;
4437  solverelaxagain = TRUE;
4438  markRelaxsUnsolved(set, relaxation);
4439  break;
4440  case SCIP_REDUCEDDOM:
4441  assert(tree->nchildren == 0);
4442  propagateagain = TRUE;
4443  solvelpagain = TRUE;
4444  solverelaxagain = TRUE;
4445  markRelaxsUnsolved(set, relaxation);
4446  break;
4447  case SCIP_SEPARATED:
4448  assert(tree->nchildren == 0);
4449  assert(SCIPsepastoreGetNCuts(sepastore) > 0);
4450  solvelpagain = TRUE;
4451  solverelaxagain = TRUE;
4452  markRelaxsUnsolved(set, relaxation);
4453  break;
4454  case SCIP_BRANCHED:
4455  assert(tree->nchildren >= 1);
4456  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4457  branched = TRUE;
4458 
4459  /* increase the number of internal nodes */
4460  stat->ninternalnodes++;
4461  stat->ntotalinternalnodes++;
4462  break;
4463  case SCIP_DIDNOTFIND: /*lint -fallthrough*/
4464  case SCIP_DIDNOTRUN:
4465  /* all integer variables in the infeasible solution are fixed,
4466  * - if no continuous variables exist and all variables are known, the infeasible pseudo solution is completely
4467  * fixed, and the node can be cut off
4468  * - if at least one continuous variable exists or we do not know all variables due to external pricers, we
4469  * cannot resolve the infeasibility by branching -> solve LP (and maybe price in additional variables)
4470  */
4471  assert(tree->nchildren == 0);
4472  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4473  assert(SCIPbranchcandGetNPseudoCands(branchcand) == 0);
4474 
4475  if( transprob->ncontvars == 0 && set->nactivepricers == 0 )
4476  {
4477  *cutoff = TRUE;
4478  SCIPsetDebugMsg(set, " -> cutoff because all variables are fixed in current node\n");
4479  }
4480  else
4481  {
4482  /* feasible LP solutions with all integers fixed must be feasible
4483  * if also no external branching candidates were available
4484  */
4485  assert(!SCIPtreeHasFocusNodeLP(tree) || pricingaborted);
4486 
4488  {
4489  SCIP_NODE* node;
4490 
4491  /* as we hit the time or iteration limit or another interrupt (e.g., gap limit), we do not want to solve the LP again.
4492  * in order to terminate correctly, we create a "branching" with only one child node
4493  * that is a copy of the focusnode
4494  */
4495  SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) );
4496  assert(tree->nchildren >= 1);
4497  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4498  branched = TRUE;
4499  }
4500  else
4501  {
4502  SCIP_VERBLEVEL verblevel;
4503 
4504  if( pricingaborted )
4505  {
4506  SCIPerrorMessage("pricing was aborted, but no branching could be created!\n");
4507  return SCIP_INVALIDRESULT;
4508  }
4509 
4510  if( wasforcedlpsolve )
4511  {
4512  assert(SCIPtreeHasFocusNodeLP(tree));
4513  SCIPerrorMessage("LP was solved, all integers fixed, some constraint still infeasible, but no branching could be created!\n");
4514  return SCIP_INVALIDRESULT;
4515  }
4516 
4517  verblevel = SCIP_VERBLEVEL_FULL;
4518 
4519  if( !tree->forcinglpmessage && set->disp_verblevel == SCIP_VERBLEVEL_HIGH )
4520  {
4521  verblevel = SCIP_VERBLEVEL_HIGH;
4522 
4523  /* remember that the forcing LP solving message was posted and do only post it again if the
4524  * verblevel is SCIP_VERBLEVEL_FULL
4525  */
4526  tree->forcinglpmessage = TRUE;
4527  }
4528 
4529  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel,
4530  "(node %" SCIP_LONGINT_FORMAT ") forcing the solution of an LP (last LP %" SCIP_LONGINT_FORMAT ")...\n", stat->nnodes, stat->nlps);
4531 
4532  /* solve the LP in the next loop */
4534  solvelpagain = TRUE;
4535  forcedlpsolve = TRUE; /* this LP must be solved without error - otherwise we have to abort */
4536  }
4537  }
4538  break;
4539  default:
4540  SCIPerrorMessage("invalid result code <%d> from SCIPbranchLP(), SCIPbranchExt() or SCIPbranchPseudo()\n", result);
4541  return SCIP_INVALIDRESULT;
4542  } /*lint !e788*/
4543  assert(*cutoff || solvelpagain || propagateagain || branched); /* something must have been done */
4544  assert(!(*cutoff) || (!solvelpagain && !propagateagain && !branched));
4545  assert(!solvelpagain || (!(*cutoff) && !branched));
4546  assert(!propagateagain || (!(*cutoff) && !branched));
4547  assert(!branched || (!solvelpagain && !propagateagain));
4548  assert(branched == (tree->nchildren > 0));
4549 
4550  /* apply found cuts */
4551  SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4552  eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain,
4553  &solvelpagain, &solverelaxagain) );
4554 
4555  /* update lower bound with the pseudo objective value, and cut off node by bounding */
4556  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4557 
4558  /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4559  updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain);
4560  }
4561 
4562  /* check for immediate restart */
4563  *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart
4564  || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars)
4565  && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4566 
4567  SCIPsetDebugMsg(set, "node solving iteration %d finished: cutoff=%u, postpone=%u, propagateagain=%u, solverelaxagain=%u, solvelpagain=%u, nlperrors=%d, restart=%u\n",
4568  nloops, *cutoff, *postpone, propagateagain, solverelaxagain, solvelpagain, nlperrors, *restart);
4569  }
4570  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4571  assert(*cutoff || SCIPconflictGetNConflicts(conflict) == 0);
4572 
4573  /* flush the conflict set storage */
4574  SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable) );
4575 
4576  /* check for too many LP errors */
4577  if( nlperrors >= MAXNLPERRORS )
4578  {
4579  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- aborting\n", stat->nnodes, stat->nlps);
4580  return SCIP_LPERROR;
4581  }
4582 
4583  /* check for final restart */
4584  restartfac = set->presol_subrestartfac;
4585  if( actdepth == 0 )
4586  restartfac = MIN(restartfac, set->presol_restartfac);
4587  *restart = *restart || (restartAllowed(set, stat) && (stat->userrestart
4588  || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars)
4589  && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4590 
4591  /* remember the last root LP solution */
4592  if( actdepth == 0 && !(*cutoff) && !(*unbounded) && !(*postpone) )
4593  {
4594  /* the root pseudo objective value and pseudo objective value should be equal in the root node */
4595  assert(SCIPsetIsFeasEQ(set, SCIPlpGetGlobalPseudoObjval(lp, set, transprob), SCIPlpGetPseudoObjval(lp, set, transprob)));
4596 
4597  SCIPprobStoreRootSol(transprob, set, stat, lp, SCIPtreeHasFocusNodeLP(tree));
4598  }
4599 
4600  /* check for cutoff */
4601  if( *cutoff )
4602  {
4603  SCIPsetDebugMsg(set, "node is cut off\n");
4604 
4605  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
4606  *infeasible = TRUE;
4607  SCIP_CALL( SCIPdebugRemoveNode(blkmem, set, focusnode) ); /*lint !e506 !e774*/
4608  }
4609  else if( !(*unbounded) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && lp->looseobjvalinf == 0 )
4610  {
4611  /* update the regression statistic nlpbranchcands and LP objective value */
4612  int nlpbranchcands;
4613  SCIP_Real lpobjval;
4614 
4615  /* get number of LP candidate variables */
4616  SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpbranchcands, NULL, NULL) );
4617 
4618  /* get LP objective value */
4619  lpobjval = SCIPlpGetObjval(lp, set, transprob);
4620  assert(lpobjval != SCIP_INVALID); /*lint !e777*/
4621 
4622  /* add the observation to the regression */
4623  SCIPregressionAddObservation(stat->regressioncandsobjval, (SCIP_Real)nlpbranchcands, lpobjval);
4624  }
4625 
4626  return SCIP_OKAY;
4627 }
4628 
4629 /** if feasible, adds current solution to the solution storage */
4630 static
4632  BMS_BLKMEM* blkmem, /**< block memory buffers */
4633  SCIP_SET* set, /**< global SCIP settings */
4634  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4635  SCIP_STAT* stat, /**< dynamic problem statistics */
4636  SCIP_PROB* origprob, /**< original problem */
4637  SCIP_PROB* transprob, /**< transformed problem after presolve */
4638  SCIP_PRIMAL* primal, /**< primal data */
4639  SCIP_RELAXATION* relaxation, /**< global relaxation data */
4640  SCIP_TREE* tree, /**< branch and bound tree */
4641  SCIP_REOPT* reopt, /**< reoptimization data structure */
4642  SCIP_LP* lp, /**< LP data */
4643  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4644  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4645  SCIP_Bool checksol /**< should the solution be checked? */
4646  )
4647 {
4648  SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
4649  SCIP_SOL* sol;
4650  SCIP_Bool foundsol;
4651 
4652  /* found a feasible solution */
4653  if( SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree)
4654  || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4655  {
4656  /* start clock for relaxation solutions */
4657  SCIPclockStart(stat->relaxsoltime, set);
4658 
4659  SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4660 
4661  SCIPsetDebugMsg(set, "found relaxation solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4662 
4663  if( checksol || set->misc_exactsolve )
4664  {
4665  /* if we want to solve exactly, we have to check the solution exactly again */
4666  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4667  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4668  }
4669  else
4670  {
4671  SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4672  eventqueue, eventfilter, &sol, &foundsol) );
4673  }
4674 
4675  if( foundsol )
4676  {
4677  stat->nrelaxsolsfound++;
4678 
4679  if( primal->nbestsolsfound != oldnbestsolsfound )
4680  {
4681  stat->nrelaxbestsolsfound++;
4682  SCIPstoreSolutionGap(set->scip);
4683  }
4684  }
4685 
4686  /* stop clock for relaxation solutions */
4687  SCIPclockStop(stat->relaxsoltime, set);
4688  }
4689  else if( SCIPtreeHasFocusNodeLP(tree) )
4690  {
4691  assert(lp->primalfeasible);
4692 
4693  /* start clock for LP solutions */
4694  SCIPclockStart(stat->lpsoltime, set);
4695 
4696  /* add solution to storage */
4697  SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4698 
4699  SCIPsetDebugMsg(set, "found lp solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4700 
4701  if( checksol || set->misc_exactsolve )
4702  {
4703  /* if we want to solve exactly, we have to check the solution exactly again */
4704  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4705  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4706  }
4707  else
4708  {
4709  SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4710  eventqueue, eventfilter, &sol, &foundsol) );
4711  }
4712 
4713  if( foundsol )
4714  {
4715  stat->nlpsolsfound++;
4716 
4717  if( primal->nbestsolsfound != oldnbestsolsfound )
4718  {
4719  stat->nlpbestsolsfound++;
4720  SCIPstoreSolutionGap(set->scip);
4721  }
4722  }
4723 
4724  /* stop clock for LP solutions */
4725  SCIPclockStop(stat->lpsoltime, set);
4726  }
4727  else
4728  {
4729  /* start clock for pseudo solutions */
4730  SCIPclockStart(stat->pseudosoltime, set);
4731 
4732  /* add solution to storage */
4733  SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4734 
4735  SCIPsetDebugMsg(set, "found pseudo solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4736 
4737  if( checksol || set->misc_exactsolve )
4738  {
4739  /* if we want to solve exactly, we have to check the solution exactly again */
4740  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4741  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4742  }
4743  else
4744  {
4745  SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4746  eventqueue, eventfilter, &sol, &foundsol) );
4747  }
4748 
4749  /* stop clock for pseudo solutions */
4750  SCIPclockStop(stat->pseudosoltime, set);
4751 
4752  if( foundsol )
4753  {
4754  stat->npssolsfound++;
4755 
4756  if( primal->nbestsolsfound != oldnbestsolsfound )
4757  {
4758  stat->npsbestsolsfound++;
4759  SCIPstoreSolutionGap(set->scip);
4760  }
4761  }
4762  }
4763 
4764  return SCIP_OKAY;
4765 }
4766 
4767 /** main solving loop */
4769  BMS_BLKMEM* blkmem, /**< block memory buffers */
4770  SCIP_SET* set, /**< global SCIP settings */
4771  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4772  SCIP_STAT* stat, /**< dynamic problem statistics */
4773  SCIP_MEM* mem, /**< block memory pools */
4774  SCIP_PROB* origprob, /**< original problem */
4775  SCIP_PROB* transprob, /**< transformed problem after presolve */
4776  SCIP_PRIMAL* primal, /**< primal data */
4777  SCIP_TREE* tree, /**< branch and bound tree */
4778  SCIP_REOPT* reopt, /**< reoptimization data structure */
4779  SCIP_LP* lp, /**< LP data */
4780  SCIP_RELAXATION* relaxation, /**< global relaxation data */
4781  SCIP_PRICESTORE* pricestore, /**< pricing storage */
4782  SCIP_SEPASTORE* sepastore, /**< separation storage */
4783  SCIP_CUTPOOL* cutpool, /**< global cut pool */
4784  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
4785  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4786  SCIP_CONFLICT* conflict, /**< conflict analysis data */
4787  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4788  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4789  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4790  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4791  SCIP_Bool* restart /**< should solving process be started again with presolving? */
4792  )
4793 {
4794  SCIP_NODESEL* nodesel;
4795  SCIP_NODE* focusnode;
4796  SCIP_NODE* nextnode;
4797  SCIP_EVENT event;
4798  SCIP_Real restartfac;
4799  SCIP_Real restartconfnum;
4800  int nnodes;
4801  int depth;
4802  SCIP_Bool cutoff;
4803  SCIP_Bool postpone;
4804  SCIP_Bool unbounded;
4805  SCIP_Bool infeasible;
4806  SCIP_Bool foundsol;
4807 
4808  assert(set != NULL);
4809  assert(blkmem != NULL);
4810  assert(stat != NULL);
4811  assert(transprob != NULL);
4812  assert(tree != NULL);
4813  assert(lp != NULL);
4814  assert(pricestore != NULL);
4815  assert(sepastore != NULL);
4816  assert(branchcand != NULL);
4817  assert(cutpool != NULL);
4818  assert(delayedcutpool != NULL);
4819  assert(primal != NULL);
4820  assert(eventfilter != NULL);
4821  assert(eventqueue != NULL);
4822  assert(restart != NULL);
4823 
4824  /* check for immediate restart (if problem solving marked to be restarted was aborted) */
4825  restartfac = set->presol_subrestartfac;
4826  if( SCIPtreeGetCurrentDepth(tree) == 0 )
4827  restartfac = MIN(restartfac, set->presol_restartfac);
4828  *restart = restartAllowed(set, stat) && (stat->userrestart
4829  || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars)
4830  && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars)) );
4831 
4832  /* calculate the number of successful conflict analysis calls that should trigger a restart */
4833  if( set->conf_restartnum > 0 )
4834  {
4835  int i;
4836 
4837  restartconfnum = (SCIP_Real)set->conf_restartnum;
4838  for( i = 0; i < stat->nconfrestarts; ++i )
4839  restartconfnum *= set->conf_restartfac;
4840  }
4841  else
4842  restartconfnum = SCIP_REAL_MAX;
4843  assert(restartconfnum >= 0.0);
4844 
4845  /* switch status to UNKNOWN */
4846  stat->status = SCIP_STATUS_UNKNOWN;
4847 
4848  focusnode = NULL;
4849  nextnode = NULL;
4850  unbounded = FALSE;
4851  postpone = FALSE;
4852 
4853  while( !SCIPsolveIsStopped(set, stat, TRUE) && !(*restart) )
4854  {
4855  SCIP_Longint nsuccessconflicts;
4856  SCIP_Bool afternodeheur;
4857  SCIP_Bool stopped;
4858  SCIP_Bool branched;
4859 
4860  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4861 
4862  foundsol = FALSE;
4863  infeasible = FALSE;
4864 
4865  do
4866  {
4867  /* update the memory saving flag, switch algorithms respectively */
4868  SCIPstatUpdateMemsaveMode(stat, set, messagehdlr, mem);
4869 
4870  /* get the current node selector */
4871  nodesel = SCIPsetGetNodesel(set, stat);
4872 
4873  /* inform tree about the current node selector */
4874  SCIP_CALL( SCIPtreeSetNodesel(tree, set, messagehdlr, stat, nodesel) );
4875 
4876  /* the next node was usually already selected in the previous solving loop before the primal heuristics were
4877  * called, because they need to know, if the next node will be a child/sibling (plunging) or not;
4878  * if the heuristics found a new best solution that cut off some of the nodes, the node selector must be called
4879  * again, because the selected next node may be invalid due to cut off
4880  */
4881  if( nextnode == NULL )
4882  {
4883  /* select next node to process */
4884  SCIP_CALL( SCIPnodeselSelect(nodesel, set, &nextnode) );
4885  }
4886  focusnode = nextnode;
4887  nextnode = NULL;
4888  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4889 
4890  /* start node activation timer */
4891  SCIPclockStart(stat->nodeactivationtime, set);
4892 
4893  /* focus selected node */
4894  SCIP_CALL( SCIPnodeFocus(&focusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt,
4895  lp, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, FALSE, FALSE) );
4896  if( cutoff )
4897  stat->ndelayedcutoffs++;
4898 
4899  /* stop node activation timer */
4900  SCIPclockStop(stat->nodeactivationtime, set);
4901 
4902  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4903  }
4904  while( cutoff ); /* select new node, if the current one was located in a cut off subtree */
4905 
4906  assert(SCIPtreeGetCurrentNode(tree) == focusnode);
4907  assert(SCIPtreeGetFocusNode(tree) == focusnode);
4908 
4909  /* if no more node was selected, we finished optimization */
4910  if( focusnode == NULL )
4911  {
4912  assert(SCIPtreeGetNNodes(tree) == 0);
4913  break;
4914  }
4915 
4916  /* update maxdepth and node count statistics */
4917  depth = SCIPnodeGetDepth(focusnode);
4918  stat->maxdepth = MAX(stat->maxdepth, depth);
4919  stat->maxtotaldepth = MAX(stat->maxtotaldepth, depth);
4920  stat->nnodes++;
4921  stat->ntotalnodes++;
4922 
4923  /* update reference bound statistic, if available */
4924  if( SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), stat->referencebound) )
4925  stat->nnodesaboverefbound++;
4926 
4927  /* issue NODEFOCUSED event */
4929  SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
4930  SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
4931 
4932  /* solve focus node */
4933  SCIP_CALL( solveNode(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation,
4934  pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter, eventqueue,
4935  cliquetable, &cutoff, &postpone, &unbounded, &infeasible, restart, &afternodeheur, &stopped) );
4936  assert(!cutoff || infeasible);
4937  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4938  assert(SCIPtreeGetCurrentNode(tree) == focusnode);
4939  assert(SCIPtreeGetFocusNode(tree) == focusnode);
4940 
4941  branched = (tree->nchildren > 0);
4942 
4943  if( stopped )
4944  break;
4945 
4946  /* check for restart */
4947  if( !(*restart) && !postpone )
4948  {
4949  /* change color of node in visualization */
4950  SCIPvisualSolvedNode(stat->visual, set, stat, focusnode);
4951 
4952  /* check, if the current solution is feasible */
4953  if( !infeasible )
4954  {
4955  SCIP_Bool feasible;
4956 
4957  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
4958  assert(!cutoff);
4959 
4960  /* in the unbounded case, we check the solution w.r.t. the original problem, because we do not want to rely
4961  * on the LP feasibility and integrality is not checked for unbounded solutions, anyway
4962  */
4963  if( unbounded )
4964  {
4965  SCIP_SOL* sol;
4966 
4967  if( SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree)
4968  || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4969  {
4970  SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4971  }
4972  else if( SCIPtreeHasFocusNodeLP(tree) )
4973  {
4974  SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4975  }
4976  else
4977  {
4978  SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4979  }
4980  SCIP_CALL( SCIPcheckSolOrig(set->scip, sol, &feasible, FALSE, FALSE) );
4981 
4982  SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) );
4983  }
4984  else
4985  feasible = TRUE;
4986 
4987  /* node solution is feasible: add it to the solution store */
4988  if( feasible )
4989  {
4990  SCIP_CALL( addCurrentSolution(blkmem, set, messagehdlr, stat, origprob, transprob, primal, relaxation, tree, reopt,
4991  lp, eventqueue, eventfilter, FALSE) );
4992 
4993  /* update the cutoff pointer if the new solution made the cutoff bound equal to the lower bound */
4994  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, &cutoff) );
4995 
4996  /* increment number of feasible leaf nodes */
4997  stat->nfeasleaves++;
4998 
4999  /* issue NODEFEASIBLE event */
5001  SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
5002  SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
5003 
5004  if( set->reopt_enable )
5005  {
5006  assert(reopt != NULL);
5007  SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp,
5008  SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5009  focusnode->lowerbound, tree->effectiverootdepth) );
5010  }
5011  }
5012  }
5013  else if( !unbounded )
5014  {
5015  /* node solution is not feasible */
5016  if( !branched )
5017  {
5018  assert(tree->nchildren == 0);
5019 
5020  /* change color of node in visualization output */
5021  SCIPvisualCutoffNode(stat->visual, set, stat, focusnode, TRUE);
5022 
5023  /* issue NODEINFEASIBLE event */
5025 
5026  /* we only increase the number of objective leaf nodes if we hit the LP objective limit; we might have also
5027  * hit the objective limit at a node that is actually infeasible, or a dual reduction led to an infeasibility prior
5028  * to LP solving such that the node will be marked as infeasible */
5030  stat->nobjleaves++;
5031  else
5032  stat->ninfeasleaves++;
5033 
5034  if( set->reopt_enable )
5035  {
5036  assert(reopt != NULL);
5037  SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEINFEASIBLE, lp,
5038  SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5039  focusnode->lowerbound, tree->effectiverootdepth) );
5040  }
5041 
5042  /* increase the cutoff counter of the branching variable */
5043  if( stat->lastbranchvar != NULL )
5044  {
5045  SCIP_CALL( SCIPvarIncCutoffSum(stat->lastbranchvar, blkmem, set, stat, stat->lastbranchdir, stat->lastbranchvalue, 1.0) );
5046  }
5047  /**@todo if last branching variable is unknown, retrieve it from the nodes' boundchg arrays */
5048  }
5049  else
5050  {
5051  assert(tree->nchildren > 0);
5052 
5053  /* issue NODEBRANCHED event */
5055 
5056  if( set->reopt_enable )
5057  {
5058  assert(reopt != NULL);
5059  SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEBRANCHED, lp,
5060  SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5061  focusnode->lowerbound, tree->effectiverootdepth) );
5062  }
5063  }
5064  SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
5065  SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
5066  }
5067  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
5068 
5069  /* if no branching was created, the node was not cut off, but its lower bound is still smaller than
5070  * the cutoff bound, we have to branch on a non-fixed variable;
5071  * this can happen, if we want to solve exactly, the current solution was declared feasible by the
5072  * constraint enforcement, but in exact solution checking it was found out to be infeasible;
5073  * in this case, no branching would have been generated by the enforcement of constraints, but we
5074  * have to further investigate the current sub tree;
5075  * note that we must noch check tree->nchildren > 0 here to determine whether we branched, we rather
5076  * check it directly after solveNode() and store the result, because an event handler might impose a
5077  * new cutoff bound (as is the case in ParaSCIP)
5078  */
5079  if( !cutoff && !unbounded && !branched && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound )
5080  {
5081  SCIP_RESULT result;
5082 
5083  assert(set->misc_exactsolve);
5084 
5085  do
5086  {
5087  result = SCIP_DIDNOTRUN;
5088  if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 )
5089  {
5090  if( transprob->ncontvars > 0 )
5091  {
5092  /**@todo call PerPlex */
5093  SCIPerrorMessage("cannot branch on all-fixed LP -- have to call PerPlex instead\n");
5094  }
5095  }
5096  else
5097  {
5098  SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
5099  eventqueue, primal->cutoffbound, FALSE, &result) );
5100  assert(result != SCIP_DIDNOTRUN && result != SCIP_DIDNOTFIND);
5101  }
5102  }
5103  while( result == SCIP_REDUCEDDOM );
5104  }
5105  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
5106 
5107  /* select node to process in next solving loop; the primal heuristics need to know whether a child/sibling
5108  * (plunging) will be selected as next node or not
5109  */
5110  SCIP_CALL( SCIPnodeselSelect(nodesel, set, &nextnode) );
5111  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
5112 
5113  /* call primal heuristics that should be applied after the node was solved */
5114  nnodes = SCIPtreeGetNNodes(tree);
5115  stopped = SCIPsolveIsStopped(set, stat, FALSE);
5116  if( !afternodeheur && (!cutoff || nnodes > 0) && !stopped )
5117  {
5118  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, nextnode, SCIP_HEURTIMING_AFTERNODE,
5119  cutoff, &foundsol, &unbounded) );
5120  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
5121 
5122  stopped = SCIPsolveIsStopped(set, stat, FALSE);
5123  }
5124 
5125  /* if the heuristics found a new best solution that cut off some of the nodes, the node selector must be called
5126  * again, because the selected next node may be invalid due to cut off
5127  */
5128  assert(!tree->cutoffdelayed);
5129 
5130  if( nnodes != SCIPtreeGetNNodes(tree) || stopped )
5131  nextnode = NULL;
5132  }
5133  else if( !infeasible && !postpone )
5134  {
5135  /* The current solution was not proven to be infeasible, but due to the restart, this does not mean that it is
5136  * feasible, we might just have skipped the check. Thus, we try to add it to the solution store, but check it
5137  * again.
5138  */
5139  SCIP_CALL( addCurrentSolution(blkmem, set, messagehdlr, stat, origprob, transprob, primal, relaxation, tree, reopt, lp,
5140  eventqueue, eventfilter, TRUE) );
5141 
5142  if( set->reopt_enable )
5143  {