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