Scippy

SCIP

Solving Constraint Integer Programs

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