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