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  /* @todo check if LP is always already solved, because of calling solveNodeInitialLP() in solveNodeLP()? */
2345  SCIPsetDebugMsg(set, "node: solve LP with price and cut\n");
2346  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2347  set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2348  assert(lp->flushed);
2349  assert(lp->solved || *lperror);
2350 
2351  /* remove previous primal ray, store new one if LP is unbounded */
2352  SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2353 
2354  /* price-and-cut loop */
2355  npricedcolvars = transprob->ncolvars;
2356  mustprice = TRUE;
2357  mustsepa = separate;
2358  delayedsepa = FALSE;
2359  *cutoff = FALSE;
2360  *unbounded = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY);
2361  nsepastallrounds = 0;
2362  stalllpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
2363  stalllpobjval = SCIP_REAL_MIN;
2364  stallnfracs = INT_MAX;
2365  lp->installing = FALSE;
2366  while( !(*cutoff) && !(*unbounded) && !(*lperror) && (mustprice || mustsepa || delayedsepa) )
2367  {
2368  SCIPsetDebugMsg(set, "-------- node solving loop --------\n");
2369  assert(lp->flushed);
2370  assert(lp->solved);
2371 
2372  /* solve the LP with pricing in new variables */
2373  while( mustprice && !(*lperror) )
2374  {
2375  SCIP_CALL( SCIPpriceLoop(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
2376  pricestore, sepastore, cutpool, branchcand, eventqueue, eventfilter, cliquetable, root, root, -1, &npricedcolvars,
2377  &mustsepa, lperror, pricingaborted) );
2378 
2379  mustprice = FALSE;
2380 
2381  assert(lp->flushed);
2382  assert(lp->solved || *lperror);
2383 
2384  /* update lower bound w.r.t. the LP solution */
2385  if( !(*lperror) && !(*pricingaborted) && SCIPlpIsRelax(lp) )
2386  {
2387  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2388  SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2389  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2390 
2391  /* update node estimate */
2392  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2393 
2394  if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2395  SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2396  }
2397  else
2398  {
2399  SCIPsetDebugMsg(set, " -> error solving LP or pricing aborted. keeping old bound: %g\n", SCIPnodeGetLowerbound(focusnode));
2400  }
2401 
2402  /* display node information line for root node */
2403  if( root && (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH )
2404  {
2405  SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
2406  }
2407 
2408  if( !(*lperror) )
2409  {
2410  /* call propagators that are applicable during LP solving loop only if the node is not cut off */
2411  if( SCIPsetIsLT(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound) )
2412  {
2413  SCIP_Longint oldnboundchgs;
2414  SCIP_Longint oldninitconssadded;
2415  SCIP_Bool postpone;
2416 
2417  oldnboundchgs = stat->nboundchgs;
2418  oldninitconssadded = stat->ninitconssadded;
2419 
2420  SCIPsetDebugMsg(set, " -> LP solved: call propagators that are applicable during LP solving loop\n");
2421 
2422  SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, FALSE,
2423  SCIP_PROPTIMING_DURINGLPLOOP, cutoff, &postpone) );
2424  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2425  assert(!postpone);
2426 
2427  if( stat->ninitconssadded != oldninitconssadded )
2428  {
2429  SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n", oldninitconssadded, stat->ninitconssadded);
2430 
2431  SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2432  branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2433  }
2434 
2435  if( !(*cutoff) && !(*unbounded) )
2436  {
2437  /* if we found something, solve LP again */
2438  if( !lp->flushed )
2439  {
2440  SCIPsetDebugMsg(set, " -> found reduction: resolve LP\n");
2441 
2442  /* in the root node, remove redundant rows permanently from the LP */
2443  if( root )
2444  {
2445  SCIP_CALL( SCIPlpFlush(lp, blkmem, set, eventqueue) );
2446  SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2447  }
2448 
2449  /* resolve LP */
2450  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2451  set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2452  assert(lp->flushed);
2453  assert(lp->solved || *lperror);
2454 
2455  /* remove previous primal ray, store new one if LP is unbounded */
2456  SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2457 
2458  mustprice = TRUE;
2459  *propagateagain = TRUE;
2460  }
2461  /* propagation might have changed the best bound of loose variables, thereby changing the loose objective
2462  * value which is added to the LP value; because of the loose status, the LP might not be reoptimized,
2463  * but the lower bound of the node needs to be updated
2464  */
2465  else if( stat->nboundchgs > oldnboundchgs )
2466  {
2467  *propagateagain = TRUE;
2468 
2469  if( lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2470  {
2471  assert(lp->flushed);
2472  assert(lp->solved);
2473 
2474  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2475  SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2476  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2477 
2478  /* update node estimate */
2479  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2480 
2481  if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2482  SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2483  }
2484  }
2485  }
2486  }
2487  }
2488 
2489  /* call primal heuristics that are applicable during node LP solving loop */
2490  if( !*cutoff && !(*unbounded) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2491  {
2492  SCIP_Bool foundsol;
2493 
2494  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGLPLOOP,
2495  FALSE, &foundsol, unbounded) );
2496  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2497 
2498  *lperror = *lperror || lp->resolvelperror;
2499  } /*lint !e438*/
2500  }
2501  assert(lp->flushed || *cutoff || *unbounded);
2502  assert(lp->solved || *lperror || *cutoff || *unbounded);
2503 
2504  /* check, if we exceeded the separation round limit */
2505  mustsepa = mustsepa
2506  && stat->nseparounds < maxseparounds
2507  && nsepastallrounds < maxnsepastallrounds
2508  && !(*cutoff);
2509 
2510  /* if separators were delayed, we want to apply a final separation round with the delayed separators */
2511  delayedsepa = delayedsepa && !mustsepa && !(*cutoff); /* if regular separation applies, we ignore delayed separators */
2512  mustsepa = mustsepa || delayedsepa;
2513 
2514  if( mustsepa )
2515  {
2516  /* if the LP is infeasible, unbounded, exceeded the objective limit or a global performance limit was reached,
2517  * we don't need to separate cuts
2518  * (the global limits are only checked at the root node in order to not query system time too often)
2519  */
2520  if( !separate || (*cutoff) || (*unbounded)
2522  || SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)
2523  || (root && SCIPsolveIsStopped(set, stat, FALSE)) )
2524  {
2525  mustsepa = FALSE;
2526  delayedsepa = FALSE;
2527  }
2528  else
2529  assert(!(*lperror));
2530  }
2531 
2532  /* separation (needs not to be done completely, because we just want to increase the lower bound) */
2533  if( mustsepa )
2534  {
2535  SCIP_Longint olddomchgcount;
2536  SCIP_Longint oldninitconssadded;
2537  SCIP_Bool enoughcuts;
2538 
2539  assert(lp->flushed);
2540  assert(lp->solved);
2542 
2543  olddomchgcount = stat->domchgcount;
2544  oldninitconssadded = stat->ninitconssadded;
2545 
2546  mustsepa = FALSE;
2547  enoughcuts = (SCIPsetGetSepaMaxcuts(set, root) == 0);
2548 
2549  /* global cut pool separation */
2550  if( !enoughcuts && !delayedsepa )
2551  {
2552  SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2553  actdepth, &enoughcuts, cutoff) );
2554 
2555  if( *cutoff )
2556  {
2557  SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2558  }
2559  }
2560  assert(lp->flushed);
2561  assert(lp->solved);
2563 
2564  /* constraint separation */
2565  SCIPsetDebugMsg(set, "constraint separation\n");
2566 
2567  /* separate constraints and LP */
2568  if( !(*cutoff) && !(*lperror) && !enoughcuts && lp->solved )
2569  {
2570  /* apply a separation round */
2571  SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal, tree,
2572  lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2573  &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) );
2574  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2575 
2576  /* if we are close to the stall round limit, also call the delayed separators */
2577  if( !(*cutoff) && !(*lperror) && !enoughcuts && lp->solved
2579  && nsepastallrounds >= maxnsepastallrounds-1 && delayedsepa )
2580  {
2581  SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal,
2582  tree, lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa,
2583  &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) );
2584  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
2585  }
2586  }
2587 
2588  /* call global cut pool separation again since separators may add cuts to the pool instead of the sepastore */
2589  if( !(*cutoff) && !(*lperror) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && !enoughcuts && lp->solved )
2590  {
2591  SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root,
2592  actdepth, &enoughcuts, cutoff) );
2593 
2594  if( *cutoff )
2595  {
2596  SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n");
2597  }
2598  }
2599 
2600  /* delayed global cut pool separation */
2601  if( !(*cutoff) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && SCIPsepastoreGetNCuts(sepastore) == 0 )
2602  {
2603  assert( !(*lperror) );
2604 
2605  SCIP_CALL( cutpoolSeparate(delayedcutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, TRUE,
2606  root, actdepth, &enoughcuts, cutoff) );
2607 
2608  if( *cutoff )
2609  {
2610  SCIPsetDebugMsg(set, " -> delayed global cut pool detected cutoff\n");
2611  }
2613  assert(lp->flushed);
2614  assert(lp->solved);
2615  }
2616 
2617  assert(*cutoff || *lperror || SCIPlpIsSolved(lp));
2618  assert(!SCIPlpIsSolved(lp)
2625 
2626  if( *cutoff || *lperror
2629  {
2630  /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
2631  SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
2632  }
2633  else
2634  {
2635  /* apply found cuts */
2636  SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2637  branchcand, eventqueue, eventfilter, cliquetable, root, SCIP_EFFICIACYCHOICE_LP, cutoff) );
2638 
2639  if( !(*cutoff) )
2640  {
2641  mustprice = mustprice || !lp->flushed || (transprob->ncolvars != npricedcolvars);
2642  mustsepa = mustsepa || !lp->flushed;
2643 
2644  /* if a new bound change (e.g. a cut with only one column) was found, propagate domains again */
2645  if( stat->domchgcount != olddomchgcount )
2646  {
2647  SCIPsetDebugMsg(set, " -> separation changed bound: propagate again\n");
2648 
2649  *propagateagain = TRUE;
2650 
2651  /* in the root node, remove redundant rows permanently from the LP */
2652  if( root )
2653  {
2654  SCIP_CALL( SCIPlpFlush(lp, blkmem, set, eventqueue) );
2655  SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) );
2656  }
2657  }
2658 
2659  if( stat->ninitconssadded != oldninitconssadded )
2660  {
2661  SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n",
2662  oldninitconssadded, stat->ninitconssadded);
2663 
2664  SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp,
2665  branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) );
2666  }
2667 
2668  if( !(*cutoff) )
2669  {
2670  SCIP_Real lpobjval;
2671 
2672  /* solve LP (with dual simplex) */
2673  SCIPsetDebugMsg(set, "separation: solve LP\n");
2674  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob,
2675  set->lp_iterlim, FALSE, TRUE, FALSE, lperror) );
2676  assert(lp->flushed);
2677  assert(lp->solved || *lperror);
2678 
2679  /* remove previous primal ray, store new one if LP is unbounded */
2680  SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) );
2681 
2682  if( !(*lperror) )
2683  {
2684  SCIP_Bool stalling;
2685 
2686  /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
2687  * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
2688  * bound of the node needs to be updated
2689  */
2690  if( stat->domchgcount != olddomchgcount && (!mustprice || mustsepa) && !(*cutoff)
2691  && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
2692  {
2693  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2694  SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
2695  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
2696 
2697  /* update node estimate */
2698  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2699 
2700  if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
2701  SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
2702  }
2703 
2704  /* check if we are stalling
2705  * If we have an LP solution, then we are stalling if
2706  * we had an LP solution before and
2707  * the LP value did not improve and
2708  * the number of fractional variables did not decrease.
2709  * If we do not have an LP solution, then we are stalling if the solution status of the LP did not change.
2710  */
2712  {
2713  SCIP_Real objreldiff;
2714  int nfracs;
2715 
2716  SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nfracs, NULL,
2717  NULL) );
2718  lpobjval = SCIPlpGetObjval(lp, set, transprob);
2719 
2720  objreldiff = SCIPrelDiff(lpobjval, stalllpobjval);
2721  SCIPsetDebugMsg(set, " -> LP bound moved from %g to %g (reldiff: %g)\n",
2722  stalllpobjval, lpobjval, objreldiff);
2723 
2724  stalling = (stalllpsolstat == SCIP_LPSOLSTAT_OPTIMAL &&
2725  objreldiff <= 1e-04 &&
2726  nfracs >= (0.9 - 0.1 * nsepastallrounds) * stallnfracs);
2727 
2728  stalllpobjval = lpobjval;
2729  stallnfracs = nfracs;
2730  } /*lint !e438*/
2731  else
2732  {
2733  stalling = (stalllpsolstat == SCIPlpGetSolstat(lp));
2734  }
2735 
2736  if( !stalling )
2737  {
2738  nsepastallrounds = 0;
2739  lp->installing = FALSE;
2740  }
2741  else
2742  {
2743  nsepastallrounds++;
2744  }
2745  stalllpsolstat = SCIPlpGetSolstat(lp);
2746 
2747  /* tell LP that we are (close to) stalling */
2748  if( nsepastallrounds >= maxnsepastallrounds-2 )
2749  lp->installing = TRUE;
2750  SCIPsetDebugMsg(set, " -> nsepastallrounds=%d/%d\n", nsepastallrounds, maxnsepastallrounds);
2751  }
2752  }
2753  }
2754  }
2755  assert(*cutoff || *lperror || (lp->flushed && lp->solved)); /* cutoff: LP may be unsolved due to bound changes */
2756 
2757  SCIPsetDebugMsg(set, "separation round %d/%d finished (%d/%d stall rounds): mustprice=%u, mustsepa=%u, delayedsepa=%u, propagateagain=%u\n",
2758  stat->nseparounds, maxseparounds, nsepastallrounds, maxnsepastallrounds, mustprice, mustsepa, delayedsepa, *propagateagain);
2759 
2760  /* increase separation round counter */
2761  stat->nseparounds++;
2762  }
2763  }
2764 
2765  if( root && nsepastallrounds >= maxnsepastallrounds )
2766  {
2767  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
2768  "Truncate separation round because of stalling (%d stall rounds).\n", maxnsepastallrounds);
2769  }
2770 
2771  if( !*lperror )
2772  {
2773  /* update pseudo cost values for continuous variables, if it should be delayed */
2774  SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, FALSE, set->branch_delaypscost) );
2775  }
2776 
2777  /* update lower bound w.r.t. the LP solution */
2778  if( *cutoff )
2779  {
2780  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
2781  }
2782  else if( !(*lperror) )
2783  {
2784  assert(lp->flushed);
2785  assert(lp->solved);
2786 
2787  if( SCIPlpIsRelax(lp) )
2788  {
2789  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
2790  }
2791 
2792  /* update node estimate */
2793  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
2794 
2795  /* issue LPSOLVED event */
2797  {
2799  SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
2800  SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
2801  }
2802 
2803  /* if the LP is a relaxation and we are not solving exactly, then we may analyze an infeasible or bound exceeding
2804  * LP (not necessary in the root node) and cut off the current node
2805  */
2806  if( !set->misc_exactsolve && !root && SCIPlpIsRelax(lp) && SCIPprobAllColsInLP(transprob, set, lp)
2808  {
2809  SCIP_CALL( SCIPconflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt,
2810  lp, branchcand, eventqueue, cliquetable, NULL) );
2811  *cutoff = TRUE;
2812  }
2813  }
2814  /* check for unboundedness */
2815  if( !(*lperror) )
2816  {
2817  *unbounded = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY);
2818  /* 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 */
2819  }
2820 
2821  lp->installing = FALSE;
2822 
2823  SCIPsetDebugMsg(set, " -> final lower bound: %g (LP status: %d, LP obj: %g)\n",
2824  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp),
2825  (*cutoff || *unbounded) ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
2826 
2827  return SCIP_OKAY; /*lint !e438*/
2828 }
2829 
2830 /** updates the current lower bound with the pseudo objective value, cuts off node by bounding, and applies conflict
2831  * analysis if the pseudo objective lead to the cutoff
2832  */
2833 static
2835  BMS_BLKMEM* blkmem, /**< block memory buffers */
2836  SCIP_SET* set, /**< global SCIP settings */
2837  SCIP_STAT* stat, /**< dynamic problem statistics */
2838  SCIP_PROB* transprob, /**< tranformed problem after presolve */
2839  SCIP_PROB* origprob, /**< original problem */
2840  SCIP_PRIMAL* primal, /**< primal data */
2841  SCIP_TREE* tree, /**< branch and bound tree */
2842  SCIP_REOPT* reopt, /**< reoptimization data structure */
2843  SCIP_LP* lp, /**< LP data */
2844  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2845  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2846  SCIP_CONFLICT* conflict, /**< conflict analysis data */
2847  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2848  SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
2849  )
2850 {
2851  assert(transprob != NULL);
2852  assert(origprob != NULL);
2853  assert(primal != NULL);
2854  assert(cutoff != NULL);
2855 
2856  if( !(*cutoff) )
2857  {
2858  SCIP_NODE* focusnode;
2859  SCIP_Real pseudoobjval;
2860 
2861  /* get current focus node */
2862  focusnode = SCIPtreeGetFocusNode(tree);
2863 
2864  /* update lower bound w.r.t. the pseudo solution */
2865  pseudoobjval = SCIPlpGetPseudoObjval(lp, set, transprob);
2866  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, pseudoobjval);
2867  SCIPsetDebugMsg(set, " -> lower bound: %g [%g] (pseudoobj: %g [%g]), cutoff bound: %g [%g]\n",
2868  SCIPnodeGetLowerbound(focusnode), SCIPprobExternObjval(transprob, origprob, set, SCIPnodeGetLowerbound(focusnode)) + SCIPgetOrigObjoffset(set->scip),
2869  pseudoobjval, SCIPprobExternObjval(transprob, origprob, set, pseudoobjval) + SCIPgetOrigObjoffset(set->scip),
2870  primal->cutoffbound, SCIPprobExternObjval(transprob, origprob, set, primal->cutoffbound) + SCIPgetOrigObjoffset(set->scip));
2871 
2872  /* check for infeasible node by bounding */
2873  if( (set->misc_exactsolve && SCIPnodeGetLowerbound(focusnode) >= primal->cutoffbound)
2874  || (!set->misc_exactsolve && SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)) )
2875  {
2876  SCIPsetDebugMsg(set, "node is cut off by bounding (lower=%g, upper=%g)\n",
2877  SCIPnodeGetLowerbound(focusnode), primal->cutoffbound);
2878  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
2879  *cutoff = TRUE;
2880 
2881  /* call pseudo conflict analysis, if the node is cut off due to the pseudo objective value */
2882  if( pseudoobjval >= primal->cutoffbound && !SCIPsetIsInfinity(set, primal->cutoffbound) && !SCIPsetIsInfinity(set, -pseudoobjval) )
2883  {
2884  SCIP_CALL( SCIPconflictAnalyzePseudo(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, NULL) );
2885  }
2886  }
2887  }
2888 
2889  return SCIP_OKAY;
2890 }
2891 
2892 /** marks all relaxators to be unsolved */
2893 static
2895  SCIP_SET* set, /**< global SCIP settings */
2896  SCIP_RELAXATION* relaxation /**< global relaxation data */
2897  )
2898 {
2899  int r;
2900 
2901  assert(set != NULL);
2902  assert(relaxation != NULL);
2903 
2904  SCIPrelaxationSetSolValid(relaxation, FALSE, FALSE);
2905 
2906  for( r = 0; r < set->nrelaxs; ++r )
2907  SCIPrelaxMarkUnsolved(set->relaxs[r]);
2908 }
2909 
2910 /** solves the current node's LP in a price-and-cut loop */
2911 static
2913  BMS_BLKMEM* blkmem, /**< block memory buffers */
2914  SCIP_SET* set, /**< global SCIP settings */
2915  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2916  SCIP_STAT* stat, /**< dynamic problem statistics */
2917  SCIP_MEM* mem, /**< block memory pools */
2918  SCIP_PROB* origprob, /**< original problem */
2919  SCIP_PROB* transprob, /**< transformed problem after presolve */
2920  SCIP_PRIMAL* primal, /**< primal data */
2921  SCIP_TREE* tree, /**< branch and bound tree */
2922  SCIP_REOPT* reopt, /**< reoptimization data structure */
2923  SCIP_LP* lp, /**< LP data */
2924  SCIP_RELAXATION* relaxation, /**< relaxators */
2925  SCIP_PRICESTORE* pricestore, /**< pricing storage */
2926  SCIP_SEPASTORE* sepastore, /**< separation storage */
2927  SCIP_CUTPOOL* cutpool, /**< global cut pool */
2928  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
2929  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2930  SCIP_CONFLICT* conflict, /**< conflict analysis data */
2931  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2932  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
2933  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2934  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2935  SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
2936  SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
2937  SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
2938  SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
2939  SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
2940  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2941  SCIP_Bool* unbounded, /**< pointer to store TRUE, if an unbounded ray was found in the LP */
2942  SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
2943  SCIP_Bool* pricingaborted /**< pointer to store TRUE, if the pricing was aborted and the lower bound
2944  * must not be used */
2945  )
2946 {
2947  SCIP_Longint nlpiterations;
2948  SCIP_Longint nlps;
2949  SCIP_Longint nzeroitlps;
2950 
2951  assert(stat != NULL);
2952  assert(tree != NULL);
2953  assert(SCIPtreeHasFocusNodeLP(tree));
2954  assert(cutoff != NULL);
2955  assert(unbounded != NULL);
2956  assert(lperror != NULL);
2957  assert(*cutoff == FALSE);
2958  assert(*unbounded == FALSE);
2959  assert(*lperror == FALSE);
2960 
2961  nlps = stat->nlps;
2962  nzeroitlps = stat->ndualzeroitlps + stat->nprimalzeroitlps + stat->nbarrierzeroitlps;
2963  nlpiterations = stat->nlpiterations;
2964 
2965  if( !initiallpsolved )
2966  {
2967  /* load and solve the initial LP of the node */
2968  SCIP_CALL( solveNodeInitialLP(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp,
2969  pricestore, sepastore, cutpool, branchcand, eventfilter, eventqueue, cliquetable, newinitconss, cutoff, lperror) );
2970 
2971  assert(*cutoff || *lperror || (lp->flushed && lp->solved));
2972  SCIPsetDebugMsg(set, "price-and-cut-loop: initial LP status: %d, LP obj: %g\n",
2973  SCIPlpGetSolstat(lp),
2974  *cutoff ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
2975 
2976  /* update initial LP iteration counter */
2977  stat->ninitlps += stat->nlps - nlps;
2978  stat->ninitlpiterations += stat->nlpiterations - nlpiterations;
2979 
2980  /* In the root node, we try if the initial LP solution is feasible to avoid expensive setup of data structures in
2981  * separators; in case the root LP is aborted, e.g., by hitting the time limit, we do not check the LP solution
2982  * since the corresponding data structures have not been updated.
2983  */
2984  if( SCIPtreeGetCurrentDepth(tree) == 0 && !(*cutoff) && !(*lperror)
2986  && !SCIPsolveIsStopped(set, stat, FALSE) )
2987  {
2988  SCIP_Bool checklprows;
2989  SCIP_Bool stored;
2990  SCIP_SOL* sol;
2991  SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
2992 
2993  SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
2994 
2996  checklprows = FALSE;
2997  else
2998  checklprows = TRUE;
2999 
3000 #ifndef NDEBUG
3001  /* in the debug mode we want to explicitly check if the solution is feasible if it was stored */
3002  SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
3003  eventqueue, eventfilter, sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
3004 
3005  if( stored )
3006  {
3007  SCIP_Bool feasible;
3008 
3009  SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, FALSE, FALSE, TRUE, TRUE,
3010  checklprows, &feasible) );
3011  assert(feasible);
3012  }
3013 
3014  SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) );
3015 #else
3016  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
3017  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) );
3018 #endif
3019  if( stored )
3020  {
3021  stat->nlpsolsfound++;
3022 
3023  if( primal->nbestsolsfound != oldnbestsolsfound )
3024  {
3025  stat->nlpbestsolsfound++;
3026  SCIPstoreSolutionGap(set->scip);
3027  }
3028 
3029  if( set->reopt_enable )
3030  {
3031  assert(reopt != NULL);
3032  SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, tree->focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp,
3033  SCIPlpGetSolstat(lp), tree->root == tree->focusnode, TRUE, tree->focusnode->lowerbound,
3034  tree->effectiverootdepth) );
3035  }
3036  }
3037 
3039  *unbounded = TRUE;
3040  }
3041  }
3042  else
3043  {
3044  SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob,
3045  origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE,
3046  cutoff) );
3047  }
3048  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3049 
3050  /* check for infeasible node by bounding */
3051  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
3052 #ifdef SCIP_DEBUG
3053  if( *cutoff )
3054  {
3055  if( SCIPtreeGetCurrentDepth(tree) == 0 )
3056  {
3057  SCIPsetDebugMsg(set, "solution cuts off root node, stop solution process\n");
3058  }
3059  else
3060  {
3061  SCIPsetDebugMsg(set, "solution cuts off node\n");
3062  }
3063  }
3064 #endif
3065 
3066  if( !(*cutoff) && !(*lperror) )
3067  {
3068  SCIP_Longint oldninitconssadded;
3069  SCIP_Longint oldnboundchgs;
3070  SCIP_Longint olddomchgcount;
3071  int oldnpricedvars;
3072  int oldncutsapplied;
3073 
3074  oldnpricedvars = transprob->ncolvars;
3075  oldninitconssadded = stat->ninitconssadded;
3076  oldncutsapplied = SCIPsepastoreGetNCutsApplied(sepastore);
3077  oldnboundchgs = stat->nboundchgs;
3078  olddomchgcount = stat->domchgcount;
3079 
3080  /* solve the LP with price-and-cut*/
3081  SCIP_CALL( priceAndCutLoop(blkmem, set, messagehdlr, stat, mem, transprob, origprob, primal, tree, reopt, lp,
3082  pricestore, sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter,
3083  eventqueue, cliquetable, fullseparation, propagateagain, cutoff, unbounded, lperror, pricingaborted) );
3084 
3085  /* check if the problem was changed and the relaxation needs to be resolved */
3086  if( (transprob->ncolvars != oldnpricedvars) || (stat->ninitconssadded != oldninitconssadded) ||
3087  (SCIPsepastoreGetNCutsApplied(sepastore) != oldncutsapplied) || (stat->nboundchgs != oldnboundchgs) ||
3088  (stat->domchgcount != olddomchgcount) )
3089  {
3090  *solverelaxagain = TRUE;
3091  markRelaxsUnsolved(set, relaxation);
3092  }
3093  }
3094  assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3095 
3096  /* if there is no LP error, then *unbounded should be TRUE, iff the LP solution status is unboundedray */
3097  assert(*lperror || ((SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY) == *unbounded));
3098 
3099  /* 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,
3100  * 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
3101  * is not a feasible lower bound for the solutions in the current subtree.
3102  * In this case, the LP has to be solved to optimality by temporarily removing the cutoff bound.
3103  */
3104  if( (*pricingaborted) && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ITERLIMIT)
3105  && !(*cutoff) )
3106  {
3107  SCIP_Real tmpcutoff;
3108 
3109  /* temporarily disable cutoffbound, which also disables the objective limit */
3110  tmpcutoff = lp->cutoffbound;
3112 
3113  lp->solved = FALSE;
3114  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) );
3115 
3116  /* reinstall old cutoff bound */
3117  lp->cutoffbound = tmpcutoff;
3118 
3119  SCIPsetDebugMsg(set, "re-optimized LP without cutoff bound: LP status: %d, LP obj: %g\n",
3120  SCIPlpGetSolstat(lp), *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob));
3121 
3122  /* lp solstat should not be objlimit, since the cutoff bound was removed temporarily */
3124  /* lp solstat should not be unboundedray, since the lp was dual feasible */
3126  /* there should be no primal ray, since the lp was dual feasible */
3127  assert(primal->primalray == NULL);
3129  {
3130  *cutoff = TRUE;
3131  }
3132  }
3133 
3134  assert(!(*pricingaborted) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL /* cppcheck-suppress assertWithSideEffect */
3135  || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_NOTSOLVED || SCIPsolveIsStopped(set, stat, FALSE) || (*cutoff));
3136 
3137  assert(*cutoff || *lperror || (lp->flushed && lp->solved));
3138 
3139  /* update node's LP iteration counter */
3140  stat->nnodelps += stat->nlps - nlps;
3141  stat->nnodezeroitlps += stat->ndualzeroitlps + stat->nprimalzeroitlps + stat->nbarrierzeroitlps - nzeroitlps;
3142  stat->nnodelpiterations += stat->nlpiterations - nlpiterations;
3143 
3144  /* update number of root node LPs and iterations if the root node was processed */
3145  if( SCIPnodeGetDepth(tree->focusnode) == 0 )
3146  {
3147  stat->nrootlps += stat->nlps - nlps;
3148  stat->nrootlpiterations += stat->nlpiterations - nlpiterations;
3149  }
3150 
3151  return SCIP_OKAY;
3152 }
3153 
3154 /** calls relaxators */
3155 static
3157  SCIP_SET* set, /**< global SCIP settings */
3158  SCIP_STAT* stat, /**< dynamic problem statistics */
3159  SCIP_TREE* tree, /**< branch and bound tree */
3160  SCIP_RELAXATION* relaxation, /**< relaxators */
3161  SCIP_PROB* transprob, /**< transformed problem */
3162  SCIP_PROB* origprob, /**< original problem */
3163  int depth, /**< depth of current node */
3164  SCIP_Bool beforelp, /**< should the relaxators with non-negative or negative priority be called? */
3165  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3166  SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3167  SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3168  SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called
3169  * again */
3170  SCIP_Bool* relaxcalled /**< pointer to store TRUE, if at least one relaxator was called (unmodified
3171  * otherwise) */
3172  )
3173 {
3174  SCIP_RESULT result;
3175  SCIP_Real lowerbound;
3176  int r;
3177 
3178  assert(set != NULL);
3179  assert(relaxation != NULL);
3180  assert(cutoff != NULL);
3181  assert(solvelpagain != NULL);
3182  assert(propagateagain != NULL);
3183  assert(solverelaxagain != NULL);
3184  assert(relaxcalled != NULL);
3185  assert(!(*cutoff));
3186 
3187  /* sort by priority */
3188  SCIPsetSortRelaxs(set);
3189 
3190  for( r = 0; r < set->nrelaxs && !(*cutoff); ++r )
3191  {
3192  if( beforelp != (SCIPrelaxGetPriority(set->relaxs[r]) >= 0) )
3193  continue;
3194 
3195  *relaxcalled = TRUE;
3196 
3197  lowerbound = -SCIPsetInfinity(set);
3198 
3199  SCIP_CALL( SCIPrelaxExec(set->relaxs[r], set, tree, stat, depth, &lowerbound, &result) );
3200 
3201  switch( result )
3202  {
3203  case SCIP_CUTOFF:
3204  *cutoff = TRUE;
3205  SCIPsetDebugMsg(set, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(set->relaxs[r]));
3206  /* @todo does it make sense to proceed if the node is proven to be infeasible? */
3207  return SCIP_OKAY;
3208 
3209  case SCIP_CONSADDED:
3210  *solvelpagain = TRUE; /* the separation for new constraints should be called */
3211  *propagateagain = TRUE; /* the propagation for new constraints should be called */
3212  break;
3213 
3214  case SCIP_REDUCEDDOM:
3215  *solvelpagain = TRUE;
3216  *propagateagain = TRUE;
3217  break;
3218 
3219  case SCIP_SEPARATED:
3220  *solvelpagain = TRUE;
3221  break;
3222 
3223  case SCIP_SUSPENDED:
3224  *solverelaxagain = TRUE;
3225  break;
3226 
3227  case SCIP_SUCCESS:
3228  case SCIP_DIDNOTRUN:
3229  break;
3230 
3231  default:
3232  SCIPerrorMessage("invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(set->relaxs[r]));
3233  return SCIP_INVALIDRESULT;
3234  } /*lint !e788*/
3235 
3236  if( result != SCIP_CUTOFF && result != SCIP_DIDNOTRUN && result != SCIP_SUSPENDED )
3237  {
3238  SCIP_NODE* focusnode;
3239 
3240  focusnode = SCIPtreeGetFocusNode(tree);
3241  assert(focusnode != NULL);
3242  assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
3243 
3244  /* update lower bound w.r.t. the lower bound given by the relaxator */
3245  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, lowerbound);
3246  SCIPsetDebugMsg(set, " -> new lower bound given by relaxator %s: %g\n",
3247  SCIPrelaxGetName(set->relaxs[r]), lowerbound);
3248  }
3249  }
3250 
3251  return SCIP_OKAY;
3252 }
3253 
3254 /** enforces constraints by branching, separation, or domain reduction */
3255 static
3257  BMS_BLKMEM* blkmem, /**< block memory buffers */
3258  SCIP_SET* set, /**< global SCIP settings */
3259  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3260  SCIP_STAT* stat, /**< dynamic problem statistics */
3261  SCIP_PROB* prob, /**< transformed problem after presolve */
3262  SCIP_PRIMAL* primal, /**< primal data */
3263  SCIP_TREE* tree, /**< branch and bound tree */
3264  SCIP_LP* lp, /**< LP data */
3265  SCIP_RELAXATION* relaxation, /**< global relaxation data */
3266  SCIP_SEPASTORE* sepastore, /**< separation storage */
3267  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3268  SCIP_Bool* branched, /**< pointer to store whether a branching was created */
3269  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3270  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the LP/pseudo solution is infeasible */
3271  SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3272  SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3273  SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */
3274  SCIP_Bool forced /**< should enforcement of pseudo solution be forced? */
3275  )
3276 {
3277  SCIP_RESULT result;
3278  SCIP_SOL* relaxsol = NULL;
3279  SCIP_Real pseudoobjval;
3280  SCIP_Bool resolved;
3281  SCIP_Bool objinfeasible;
3282  SCIP_Bool enforcerelaxsol;
3283  int h;
3284 
3285  assert(set != NULL);
3286  assert(stat != NULL);
3287  assert(tree != NULL);
3288  assert(SCIPtreeGetFocusNode(tree) != NULL);
3289  assert(branched != NULL);
3290  assert(cutoff != NULL);
3291  assert(infeasible != NULL);
3292  assert(propagateagain != NULL);
3293  assert(solvelpagain != NULL);
3294  assert(solverelaxagain != NULL);
3295  assert(!(*cutoff));
3296  assert(!(*propagateagain));
3297  assert(!(*solvelpagain));
3298  assert(!(*solverelaxagain));
3299 
3300  *branched = FALSE;
3301  /**@todo avoid checking the same pseudosolution twice */
3302 
3303  /* enforce (best) relaxation solution if the LP has a worse objective value */
3304  enforcerelaxsol = SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree)
3305  || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, prob)));
3306 
3307  /* check if all constraint handlers implement the enforelax callback, otherwise enforce the LP solution */
3308  for( h = 0; h < set->nconshdlrs && enforcerelaxsol; ++h )
3309  {
3310  if( set->conshdlrs_enfo[h]->consenforelax == NULL && ((! set->conshdlrs_enfo[h]->needscons) ||
3311  (set->conshdlrs_enfo[h]->nconss > 0)) )
3312  {
3313  SCIP_VERBLEVEL verblevel;
3314 
3315  enforcerelaxsol = FALSE;
3316 
3317  verblevel = SCIP_VERBLEVEL_FULL;
3318 
3319  if( !stat->disableenforelaxmsg && set->disp_verblevel == SCIP_VERBLEVEL_HIGH )
3320  {
3321  verblevel = SCIP_VERBLEVEL_HIGH;
3322 
3323  /* remember that the disable relaxation enforcement message was posted and only post it again if the
3324  * verblevel is SCIP_VERBLEVEL_FULL
3325  */
3326  stat->disableenforelaxmsg = TRUE;
3327  }
3328  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel, "Disable enforcement of relaxation solutions"
3329  " since constraint handler %s does not implement enforelax-callback\n",
3330  SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3331  }
3332  }
3333 
3334  /* enforce constraints by branching, applying additional cutting planes (if LP is being processed),
3335  * introducing new constraints, or tighten the domains
3336  */
3337 #ifndef SCIP_NDEBUG
3338  if( enforcerelaxsol )
3339  {
3340  SCIPsetDebugMsg(set, "enforcing constraints on relaxation solution\n");
3341  }
3342  else
3343  {
3344  SCIPsetDebugMsg(set, "enforcing constraints on %s solution\n", SCIPtreeHasFocusNodeLP(tree) ? "LP" : "pseudo");
3345  }
3346 #endif
3347 
3348  /* check, if the solution is infeasible anyway due to it's objective value */
3349  if( SCIPtreeHasFocusNodeLP(tree) || enforcerelaxsol )
3350  objinfeasible = FALSE;
3351  else
3352  {
3353  pseudoobjval = SCIPlpGetPseudoObjval(lp, set, prob);
3354  objinfeasible = SCIPsetIsFeasLT(set, pseudoobjval, SCIPnodeGetLowerbound(SCIPtreeGetFocusNode(tree)));
3355  }
3356 
3357  /* during constraint enforcement, generated cuts should enter the LP in any case; otherwise, a constraint handler
3358  * would fail to enforce its constraints if it relies on the modification of the LP relaxation
3359  */
3360  SCIPsepastoreStartForceCuts(sepastore);
3361 
3362  /* enforce constraints until a handler resolved an infeasibility with cutting off the node, branching,
3363  * reducing a domain, or separating a cut
3364  * if a constraint handler introduced new constraints to enforce his constraints, the newly added constraints
3365  * have to be enforced themselves
3366  */
3367  resolved = FALSE;
3368 
3369  /* in case the relaxation solution should be enforced, we need to create the corresponding solution for the enforelax callbacks */
3370  if( enforcerelaxsol )
3371  {
3372  SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
3373  }
3374 
3375  for( h = 0; h < set->nconshdlrs && !resolved; ++h )
3376  {
3377  assert(SCIPsepastoreGetNCuts(sepastore) == 0); /* otherwise, the LP should have been resolved first */
3378 
3379  /* enforce LP, pseudo, or relaxation solution */
3380  if( enforcerelaxsol )
3381  {
3382  SCIPsetDebugMsg(set, "enforce relaxation solution with value %g\n", SCIPrelaxationGetSolObj(relaxation));
3383 
3384  SCIP_CALL( SCIPconshdlrEnforceRelaxSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore,
3385  relaxsol, *infeasible, &result) );
3386  }
3387  else if( SCIPtreeHasFocusNodeLP(tree) )
3388  {
3389  SCIPsetDebugMsg(set, "enforce LP solution with value %g\n", SCIPlpGetObjval(lp, set, prob));
3390 
3391  assert(lp->flushed);
3392  assert(lp->solved);
3394  SCIP_CALL( SCIPconshdlrEnforceLPSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore, *infeasible,
3395  &result) );
3396  }
3397  else
3398  {
3399  SCIP_CALL( SCIPconshdlrEnforcePseudoSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, branchcand, *infeasible,
3400  objinfeasible, forced, &result) );
3401  if( SCIPsepastoreGetNCuts(sepastore) != 0 )
3402  {
3403  SCIPerrorMessage("pseudo enforcing method of constraint handler <%s> separated cuts\n",
3404  SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3405  return SCIP_INVALIDRESULT;
3406  }
3407  }
3408  SCIPsetDebugMsg(set, "enforcing of <%s> returned result %d\n", SCIPconshdlrGetName(set->conshdlrs_enfo[h]), result);
3409 
3410  switch( result )
3411  {
3412  case SCIP_CUTOFF:
3413  assert(tree->nchildren == 0);
3414  *cutoff = TRUE;
3415  *infeasible = TRUE;
3416  resolved = TRUE;
3417  SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in enforcement\n",
3418  SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3419  break;
3420 
3421  case SCIP_CONSADDED:
3422  assert(tree->nchildren == 0);
3423  *infeasible = TRUE;
3424  *propagateagain = TRUE; /* the propagation for new constraints should be called */
3425  *solvelpagain = TRUE; /* the separation for new constraints should be called */
3426  *solverelaxagain = TRUE;
3427  markRelaxsUnsolved(set, relaxation);
3428  resolved = TRUE;
3429  break;
3430 
3431  case SCIP_REDUCEDDOM:
3432  assert(tree->nchildren == 0);
3433  *infeasible = TRUE;
3434  *propagateagain = TRUE;
3435  *solvelpagain = TRUE;
3436  *solverelaxagain = TRUE;
3437  markRelaxsUnsolved(set, relaxation);
3438  resolved = TRUE;
3439  break;
3440 
3441  case SCIP_SEPARATED:
3442  assert(tree->nchildren == 0);
3443  assert(SCIPsepastoreGetNCuts(sepastore) > 0);
3444  *infeasible = TRUE;
3445  *solvelpagain = TRUE;
3446  *solverelaxagain = TRUE;
3447  markRelaxsUnsolved(set, relaxation);
3448  resolved = TRUE;
3449  break;
3450 
3451  case SCIP_BRANCHED:
3452  assert(tree->nchildren >= 1);
3453  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3454  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3455  *infeasible = TRUE;
3456  *branched = TRUE;
3457  resolved = TRUE;
3458 
3459  /* increase the number of internal nodes */
3460  stat->ninternalnodes++;
3461  stat->ntotalinternalnodes++;
3462  break;
3463 
3464  case SCIP_SOLVELP:
3465  /* either LP was not solved, or it is not solved anymore (e.g., because feastol has been tightened by some constraint handler) */
3466  assert(!SCIPtreeHasFocusNodeLP(tree) || !lp->solved);
3467  assert(tree->nchildren == 0);
3468  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3469  *infeasible = TRUE;
3470  *solvelpagain = TRUE;
3471  resolved = TRUE;
3472  SCIPtreeSetFocusNodeLP(tree, TRUE); /* the node's LP must be solved */
3473  break;
3474 
3475  case SCIP_INFEASIBLE:
3476  assert(tree->nchildren == 0);
3477  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3478  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3479  *infeasible = TRUE;
3480  break;
3481 
3482  case SCIP_FEASIBLE:
3483  assert(tree->nchildren == 0);
3484  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3485  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3486  break;
3487 
3488  case SCIP_DIDNOTRUN:
3489  assert(tree->nchildren == 0);
3490  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3491  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3492  assert(objinfeasible);
3493  *infeasible = TRUE;
3494  break;
3495 
3496  default:
3497  SCIPerrorMessage("invalid result code <%d> from enforcing method of constraint handler <%s>\n",
3498  result, SCIPconshdlrGetName(set->conshdlrs_enfo[h]));
3499  return SCIP_INVALIDRESULT;
3500  } /*lint !e788*/
3501 
3502  /* the enforcement method may add a primal solution, after which the LP status could be set to
3503  * objective limit reached
3504  */
3506  {
3507  *cutoff = TRUE;
3508  *infeasible = TRUE;
3509  resolved = TRUE;
3510  SCIPsetDebugMsg(set, " -> LP exceeded objective limit\n");
3511 
3512  /* If we used the probing mode during branching, it might happen that we added a constraint or global bound
3513  * and returned SCIP_CONSADDED or SCIP_REDUCEDDOM, but when reoptimizing the LP after ending the probing mode,
3514  * this leads to hitting the objective limit. In this case, we do not need to propagate or solve the LP again.
3515  */
3516  *propagateagain = FALSE;
3517  *solvelpagain = FALSE;
3518  }
3519 
3520  assert(!(*branched) || (resolved && !(*cutoff) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3521  assert(!(*cutoff) || (resolved && !(*branched) && *infeasible && !(*propagateagain) && !(*solvelpagain)));
3522  assert(*infeasible || (!resolved && !(*branched) && !(*cutoff) && !(*propagateagain) && !(*solvelpagain)));
3523  assert(!(*propagateagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3524  assert(!(*solvelpagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible));
3525  }
3526  assert(!objinfeasible || *infeasible);
3527  assert(resolved == (*branched || *cutoff || *propagateagain || *solvelpagain));
3528  assert(*cutoff || *solvelpagain || SCIPsepastoreGetNCuts(sepastore) == 0);
3529 
3530  /* in case the relaxation solution was enforced, free the created solution */
3531  if( enforcerelaxsol )
3532  {
3533  SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
3534  }
3535 
3536  /* deactivate the cut forcing of the constraint enforcement */
3537  SCIPsepastoreEndForceCuts(sepastore);
3538 
3539  SCIPsetDebugMsg(set, " -> enforcing result: branched=%u, cutoff=%u, infeasible=%u, propagateagain=%u, solvelpagain=%u, resolved=%u\n",
3540  *branched, *cutoff, *infeasible, *propagateagain, *solvelpagain, resolved);
3541 
3542  return SCIP_OKAY;
3543 }
3544 
3545 /** applies the cuts stored in the separation store, or clears the store if the node can be cut off */
3546 static
3548  BMS_BLKMEM* blkmem, /**< block memory buffers */
3549  SCIP_SET* set, /**< global SCIP settings */
3550  SCIP_STAT* stat, /**< dynamic problem statistics */
3551  SCIP_PROB* transprob, /**< transformed problem */
3552  SCIP_PROB* origprob, /**< original problem */
3553  SCIP_TREE* tree, /**< branch and bound tree */
3554  SCIP_REOPT* reopt, /**< reotimization data structure */
3555  SCIP_LP* lp, /**< LP data */
3556  SCIP_RELAXATION* relaxation, /**< relaxators */
3557  SCIP_SEPASTORE* sepastore, /**< separation storage */
3558  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3559  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3560  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3561  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3562  SCIP_Bool root, /**< is this the initial root LP? */
3563  SCIP_EFFICIACYCHOICE efficiacychoice, /**< type of solution to base efficiacy computation on */
3564  SCIP_Bool* cutoff, /**< pointer to whether the node can be cut off */
3565  SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3566  SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */
3567  SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if the node's relaxation has to be solved again */
3568  )
3569 {
3570  assert(stat != NULL);
3571  assert(cutoff != NULL);
3572  assert(propagateagain != NULL);
3573  assert(solvelpagain != NULL);
3574 
3575  if( *cutoff )
3576  {
3577  /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */
3578  SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
3579  }
3580  else if( SCIPsepastoreGetNCuts(sepastore) > 0 )
3581  {
3582  SCIP_Longint olddomchgcount;
3583  int oldncutsapplied;
3584 
3585  olddomchgcount = stat->domchgcount;
3586  oldncutsapplied = SCIPsepastoreGetNCutsApplied(sepastore);
3587  SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
3588  eventqueue, eventfilter, cliquetable, root, efficiacychoice, cutoff) );
3589  *propagateagain = *propagateagain || (stat->domchgcount != olddomchgcount);
3590  *solvelpagain = TRUE;
3591  if( (stat->domchgcount != olddomchgcount) || (SCIPsepastoreGetNCutsApplied(sepastore) != oldncutsapplied) )
3592  {
3593  *solverelaxagain = TRUE;
3594  markRelaxsUnsolved(set, relaxation);
3595  }
3596  }
3597 
3598  return SCIP_OKAY;
3599 }
3600 
3601 /** updates the cutoff, propagateagain, and solverelaxagain status of the current solving loop */
3602 static
3604  SCIP_SET* set, /**< global SCIP settings */
3605  SCIP_STAT* stat, /**< dynamic problem statistics */
3606  SCIP_TREE* tree, /**< branch and bound tree */
3607  int depth, /**< depth of current node */
3608  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
3609  SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */
3610  SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if at least one relaxator should be called again */
3611  )
3612 {
3613  SCIP_NODE* focusnode;
3614  int r;
3615 
3616  assert(set != NULL);
3617  assert(stat != NULL);
3618  assert(cutoff != NULL);
3619  assert(propagateagain != NULL);
3620  assert(solverelaxagain != NULL);
3621 
3622  /* check, if the path was cutoff */
3623  *cutoff = *cutoff || (tree->cutoffdepth <= depth);
3624 
3625  /* check if branching was already performed */
3626  if( tree->nchildren == 0 )
3627  {
3628  /* check, if the focus node should be repropagated */
3629  focusnode = SCIPtreeGetFocusNode(tree);
3630  *propagateagain = *propagateagain || SCIPnodeIsPropagatedAgain(focusnode);
3631 
3632  /* check, if one of the external relaxations should be solved again */
3633  for( r = 0; r < set->nrelaxs && !(*solverelaxagain); ++r )
3634  *solverelaxagain = *solverelaxagain || ( !SCIPrelaxIsSolved(set->relaxs[r], stat) );
3635  }
3636  else
3637  {
3638  /* if branching was performed, avoid another node loop iteration */
3639  *propagateagain = FALSE;
3640  *solverelaxagain = FALSE;
3641  }
3642 }
3643 
3644 /** propagate domains and solve relaxation and lp */
3645 static
3647  BMS_BLKMEM* blkmem, /**< block memory buffers */
3648  SCIP_SET* set, /**< global SCIP settings */
3649  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3650  SCIP_STAT* stat, /**< dynamic problem statistics */
3651  SCIP_MEM* mem, /**< block memory pools */
3652  SCIP_PROB* origprob, /**< original problem */
3653  SCIP_PROB* transprob, /**< transformed problem after presolve */
3654  SCIP_PRIMAL* primal, /**< primal data */
3655  SCIP_TREE* tree, /**< branch and bound tree */
3656  SCIP_REOPT* reopt, /**< reoptimization data structure */
3657  SCIP_LP* lp, /**< LP data */
3658  SCIP_RELAXATION* relaxation, /**< global relaxation data */
3659  SCIP_PRICESTORE* pricestore, /**< pricing storage */
3660  SCIP_SEPASTORE* sepastore, /**< separation storage */
3661  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3662  SCIP_CUTPOOL* cutpool, /**< global cut pool */
3663  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
3664  SCIP_CONFLICT* conflict, /**< conflict analysis data */
3665  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
3666  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3667  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3668  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3669  SCIP_NODE* focusnode, /**< focused node */
3670  int actdepth, /**< depth in the b&b tree */
3671  SCIP_Bool propagate, /**< should we propagate */
3672  SCIP_Bool solvelp, /**< should we solve the lp */
3673  SCIP_Bool solverelax, /**< should we solve the relaxation */
3674  SCIP_Bool forcedlpsolve, /**< is there a need for a solve lp */
3675  SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */
3676  SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */
3677  SCIP_Longint* afterlpproplps, /**< pointer to store the last LP count for which AFTERLP propagation was performed */
3678  SCIP_HEURTIMING* heurtiming, /**< timing for running heuristics after propagation call */
3679  int* nlperrors, /**< pointer to store the number of lp errors */
3680  SCIP_Bool* fullpropagation, /**< pointer to store whether we want to do a fullpropagation next time */
3681  SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */
3682  SCIP_Bool* lpsolved, /**< pointer to store whether the lp was solved */
3683  SCIP_Bool* relaxcalled, /**< pointer to store whether a relaxator was called; initialized with last loop's result */
3684  SCIP_Bool* solvelpagain, /**< pointer to store whether we want to solve the lp again */
3685  SCIP_Bool* solverelaxagain, /**< pointer to store whether we want to solve the relaxation again */
3686  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
3687  SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
3688  SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
3689  SCIP_Bool* stopped, /**< pointer to store whether solving was interrupted */
3690  SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */
3691  SCIP_Bool* pricingaborted, /**< pointer to store TRUE, if the pricing was aborted and the lower bound must not be used */
3692  SCIP_Bool* forcedenforcement /**< pointer to store whether the enforcement of pseudo solution should be forced */
3693  )
3694 {
3695  SCIP_Bool newinitconss;
3696 
3697  assert(set != NULL);
3698  assert(stat != NULL);
3699  assert(origprob != NULL);
3700  assert(transprob != NULL);
3701  assert(tree != NULL);
3702  assert(lp != NULL);
3703  assert(primal != NULL);
3704  assert(pricestore != NULL);
3705  assert(sepastore != NULL);
3706  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3707  assert(branchcand != NULL);
3708  assert(cutpool != NULL);
3709  assert(delayedcutpool != NULL);
3710  assert(conflict != NULL);
3711  assert(SCIPconflictGetNConflicts(conflict) == 0);
3712  assert(eventfilter != NULL);
3713  assert(eventqueue != NULL);
3714  assert(focusnode != NULL);
3715  assert(heurtiming != NULL);
3716  assert(nlperrors != NULL);
3717  assert(fullpropagation != NULL);
3718  assert(propagateagain != NULL);
3719  assert(afterlpproplps != NULL);
3720  assert(lpsolved != NULL);
3721  assert(solvelpagain != NULL);
3722  assert(solverelaxagain != NULL);
3723  assert(cutoff != NULL);
3724  assert(postpone != NULL);
3725  assert(unbounded != NULL);
3726  assert(lperror != NULL);
3727  assert(pricingaborted != NULL);
3728  assert(forcedenforcement != NULL);
3729 
3730  newinitconss = FALSE;
3731 
3732  if( !(*cutoff) && !(*postpone) )
3733  {
3734  SCIP_Longint oldninitconssadded;
3735  SCIP_Longint oldnboundchgs;
3736  SCIP_Bool lpwasflushed;
3737 
3738  lpwasflushed = lp->flushed;
3739  oldnboundchgs = stat->nboundchgs;
3740  oldninitconssadded = stat->ninitconssadded;
3741 
3742  /* call after LP propagators */
3743  if( ((*afterlpproplps) < stat->nnodelps && (*lpsolved)) || (*relaxcalled) )
3744  {
3745  SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3746  SCIP_PROPTIMING_AFTERLPLOOP, cutoff, postpone) );
3747  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3748 
3749  /* check, if the path was cutoff */
3750  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3751  *afterlpproplps = stat->nnodelps;
3752  propagate = propagate || (stat->nboundchgs > oldnboundchgs);
3753  }
3754 
3755  /* call before LP propagators */
3756  if( propagate && !(*cutoff) )
3757  {
3758  SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation,
3759  SCIP_PROPTIMING_BEFORELP, cutoff, postpone) );
3760  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3761  }
3762 
3763  newinitconss = (stat->ninitconssadded != oldninitconssadded);
3764  *fullpropagation = FALSE;
3765 
3766  /* check, if the path was cutoff */
3767  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3768 
3769  /* if the LP was flushed and is now no longer flushed, a bound change occurred, and the LP has to be resolved;
3770  * we also have to solve the LP if new intial constraints were added which need to be added to the LP
3771  */
3772  solvelp = solvelp || (lpwasflushed && (!lp->flushed || newinitconss));
3773  solverelax = solverelax || newinitconss;
3774 
3775  /* the number of bound changes was increased by the propagation call, thus the relaxation should be solved again */
3776  if( stat->nboundchgs > oldnboundchgs )
3777  {
3778  /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value
3779  * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower
3780  * bound of the node needs to be updated
3781  */
3782  if( !solvelp && lp->flushed && lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) )
3783  {
3784  SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) );
3785  SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n",
3786  SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob));
3787 
3788  if( SCIPtreeHasFocusNodeLP(tree) )
3789  {
3790  /* update node estimate */
3791  SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) );
3792 
3793  if( actdepth == 0 && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL )
3794  SCIPprobUpdateBestRootSol(transprob, set, stat, lp);
3795  }
3796  }
3797 
3798  solverelax = TRUE;
3799  markRelaxsUnsolved(set, relaxation);
3800  }
3801 
3802  /* update lower bound with the pseudo objective value, and cut off node by bounding */
3803  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
3804  conflict, cliquetable, cutoff) );
3805  }
3806  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3807 
3808  if( *postpone )
3809  return SCIP_OKAY;
3810 
3811  /* call primal heuristics that are applicable after propagation loop before lp solve;
3812  * the first time we go here, we call the before node heuristics instead
3813  */
3814  if( !(*cutoff) && !SCIPtreeProbing(tree) )
3815  {
3816  /* if the heuristics find a new incumbent solution, propagate again */
3817  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, *heurtiming,
3818  FALSE, propagateagain, unbounded) );
3819  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3820 
3821  *heurtiming = SCIP_HEURTIMING_AFTERPROPLOOP;
3822 
3823  /* check if primal heuristics found a solution and we therefore reached a solution limit */
3824  if( SCIPsolveIsStopped(set, stat, FALSE) )
3825  {
3826  /* cppcheck-suppress unassignedVariable */
3827  SCIP_NODE* node;
3828 
3829  /* we reached a solution limit and do not want to continue the processing of the current node, but in order to
3830  * allow restarting the optimization process later, we need to create a "branching" with only one child node that
3831  * is a copy of the focusnode
3832  */
3834  SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) );
3835  assert(tree->nchildren >= 1);
3836  *stopped = TRUE;
3837  return SCIP_OKAY;
3838  }
3839 
3840  /* if diving produced an LP error, switch back to non-LP node */
3841  if( lp->resolvelperror )
3842  {
3844  lp->resolvelperror = FALSE;
3845  }
3846 
3847  if( *propagateagain )
3848  {
3849  *solvelpagain = solvelp;
3850  *solverelaxagain = solverelax;
3851 
3852  return SCIP_OKAY;
3853  }
3854  }
3855 
3856  /* solve external relaxations with non-negative priority */
3857  *relaxcalled = FALSE;
3858  if( solverelax && !(*cutoff) )
3859  {
3860  /* clear the storage of external branching candidates */
3861  SCIPbranchcandClearExternCands(branchcand);
3862 
3863  SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, TRUE,
3864  cutoff, propagateagain, solvelpagain, solverelaxagain, relaxcalled) );
3865  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3866 
3867  /* check, if the path was cutoff */
3868  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3869 
3870  /* apply found cuts */
3871  SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
3872  eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
3873  solvelpagain, solverelaxagain) );
3874 
3875  /* update lower bound with the pseudo objective value, and cut off node by bounding */
3876  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
3877  }
3878  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3879 
3880  /* check, if we want to solve the LP at this node */
3881  if( solvelp && !(*cutoff) && SCIPtreeHasFocusNodeLP(tree) )
3882  {
3883  *lperror = FALSE;
3884  *unbounded = FALSE;
3885 
3886  /* solve the node's LP */
3887  SCIP_CALL( solveNodeLP(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation, pricestore,
3888  sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable,
3889  initiallpsolved, fullseparation, newinitconss, propagateagain, solverelaxagain, cutoff, unbounded, lperror, pricingaborted) );
3890 
3891  *lpsolved = TRUE;
3892  *solvelpagain = FALSE;
3893  SCIPsetDebugMsg(set, " -> LP status: %d, LP obj: %g, iter: %" SCIP_LONGINT_FORMAT ", count: %" SCIP_LONGINT_FORMAT "\n",
3894  SCIPlpGetSolstat(lp),
3895  *cutoff ? SCIPsetInfinity(set) : (*lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob)),
3896  stat->nlpiterations, stat->lpcount);
3897 
3898  /* check, if the path was cutoff */
3899  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3900 
3901  /* if an error occured during LP solving, switch to pseudo solution */
3902  if( *lperror )
3903  {
3904  if( forcedlpsolve )
3905  {
3906  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
3907  stat->nnodes, stat->nlps);
3908  return SCIP_LPERROR;
3909  }
3911  ++(*nlperrors);
3912  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
3913  "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
3914  stat->nnodes, stat->nlps, *nlperrors);
3915  }
3916 
3918  {
3920  *forcedenforcement = TRUE;
3921 
3922  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL,
3923  "(node %" SCIP_LONGINT_FORMAT ") LP solver hit %s limit in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead\n",
3924  stat->nnodes, SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT ? "time" : "iteration", stat->nlps);
3925  }
3926 
3928  {
3929  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
3930  "(node %" SCIP_LONGINT_FORMAT ") LP relaxation is unbounded (LP %" SCIP_LONGINT_FORMAT ")\n", stat->nnodes, stat->nlps);
3931  }
3932 
3933  /* if we solve exactly, the LP claims to be infeasible but the infeasibility could not be proved,
3934  * we have to forget about the LP and use the pseudo solution instead
3935  */
3936  if( !(*cutoff) && !(*lperror) && (set->misc_exactsolve || *pricingaborted) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE
3937  && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound )
3938  {
3939  if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 && transprob->ncontvars > 0 )
3940  {
3941  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",
3942  stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, transprob->ncontvars);
3943  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") -> have to call PerPlex() (feature not yet implemented)\n", stat->nnodes);
3944  /**@todo call PerPlex */
3945  return SCIP_LPERROR;
3946  }
3947  else
3948  {
3950  *forcedenforcement = TRUE;
3951 
3952  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
3953  "(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",
3954  stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, SCIPbranchcandGetNPseudoCands(branchcand));
3955  }
3956  }
3957 
3958  /* update lower bound with the pseudo objective value, and cut off node by bounding */
3959  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
3960  cliquetable, cutoff) );
3961  }
3962  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3963  assert(*cutoff || !SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
3964 
3965  /* reset solverelaxagain if no relaxations were solved up to this point (the LP-changes are already included in
3966  * relaxators called after the LP)
3967  */
3968  *solverelaxagain = *solverelaxagain && *relaxcalled;
3969 
3970  /* solve external relaxations with negative priority */
3971  if( solverelax && !(*cutoff) )
3972  {
3973  SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, FALSE, cutoff,
3974  propagateagain, solvelpagain, solverelaxagain, relaxcalled) );
3975  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
3976 
3977  /* check, if the path was cutoff */
3978  *cutoff = *cutoff || (tree->cutoffdepth <= actdepth);
3979 
3980  /* apply found cuts */
3981  SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
3982  eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain,
3983  solvelpagain, solverelaxagain) );
3984 
3985  /* update lower bound with the pseudo objective value, and cut off node by bounding */
3986  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict,
3987  cliquetable, cutoff) );
3988  }
3989  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
3990 
3991  return SCIP_OKAY;
3992 }
3993 
3994 /** check if a restart can be performed */
3995 #ifndef NDEBUG
3996 static
3998  SCIP_SET* set, /**< global SCIP settings */
3999  SCIP_STAT* stat /**< dynamic problem statistics */
4000  )
4001 {
4002  assert(set != NULL);
4003  assert(stat != NULL);
4004 
4005  return (set->nactivepricers == 0 && !set->reopt_enable
4006  && (set->presol_maxrestarts == -1 || stat->nruns <= set->presol_maxrestarts)
4007  && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts));
4008 }
4009 #else
4010 #define restartAllowed(set,stat) ((set)->nactivepricers == 0 && !set->reopt_enable && ((set)->presol_maxrestarts == -1 || (stat)->nruns <= (set)->presol_maxrestarts) \
4011  && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts))
4012 #endif
4013 
4014 /** solves the focus node */
4015 static
4017  BMS_BLKMEM* blkmem, /**< block memory buffers */
4018  SCIP_SET* set, /**< global SCIP settings */
4019  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4020  SCIP_STAT* stat, /**< dynamic problem statistics */
4021  SCIP_MEM* mem, /**< block memory pools */
4022  SCIP_PROB* origprob, /**< original problem */
4023  SCIP_PROB* transprob, /**< transformed problem after presolve */
4024  SCIP_PRIMAL* primal, /**< primal data */
4025  SCIP_TREE* tree, /**< branch and bound tree */
4026  SCIP_REOPT* reopt, /**< reoptimization data structure */
4027  SCIP_LP* lp, /**< LP data */
4028  SCIP_RELAXATION* relaxation, /**< global relaxation data */
4029  SCIP_PRICESTORE* pricestore, /**< pricing storage */
4030  SCIP_SEPASTORE* sepastore, /**< separation storage */
4031  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4032  SCIP_CUTPOOL* cutpool, /**< global cut pool */
4033  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
4034  SCIP_CONFLICT* conflict, /**< conflict analysis data */
4035  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4036  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4037  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4038  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4039  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
4040  SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */
4041  SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */
4042  SCIP_Bool* infeasible, /**< pointer to store whether the focus node's solution is infeasible */
4043  SCIP_Bool* restart, /**< should solving process be started again with presolving? */
4044  SCIP_Bool* afternodeheur, /**< pointer to store whether AFTERNODE heuristics were already called */
4045  SCIP_Bool* stopped /**< pointer to store whether solving was interrupted */
4046  )
4047 {
4048  SCIP_NODE* focusnode;
4049  SCIP_Longint lastdomchgcount;
4050  SCIP_Longint afterlpproplps;
4051  SCIP_Real restartfac;
4052  SCIP_Longint lastlpcount;
4053  SCIP_HEURTIMING heurtiming;
4054  int actdepth;
4055  int nlperrors;
4056  int nloops;
4057  SCIP_Bool foundsol;
4058  SCIP_Bool focusnodehaslp;
4059  SCIP_Bool lpsolved;
4060  SCIP_Bool initiallpsolved;
4061  SCIP_Bool fullseparation;
4062  SCIP_Bool solverelaxagain;
4063  SCIP_Bool solvelpagain;
4064  SCIP_Bool propagateagain;
4065  SCIP_Bool fullpropagation;
4066  SCIP_Bool branched;
4067  SCIP_Bool forcedlpsolve;
4068  SCIP_Bool wasforcedlpsolve;
4069  SCIP_Bool pricingaborted;
4070 
4071  assert(set != NULL);
4072  assert(stat != NULL);
4073  assert(origprob != NULL);
4074  assert(transprob != NULL);
4075  assert(tree != NULL);
4076  assert(primal != NULL);
4077  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4078  assert(SCIPconflictGetNConflicts(conflict) == 0);
4079  assert(cutoff != NULL);
4080  assert(postpone != NULL);
4081  assert(unbounded != NULL);
4082  assert(infeasible != NULL);
4083  assert(restart != NULL);
4084  assert(afternodeheur != NULL);
4085 
4086  *cutoff = FALSE;
4087  *postpone = FALSE;
4088  *unbounded = FALSE;
4089  *infeasible = FALSE;
4090  *restart = FALSE;
4091  *afternodeheur = FALSE;
4092  *stopped = FALSE;
4093  pricingaborted = FALSE;
4094 
4095  focusnode = SCIPtreeGetFocusNode(tree);
4096  assert(focusnode != NULL);
4097  assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
4098  actdepth = SCIPnodeGetDepth(focusnode);
4099 
4100  /* invalidate relaxation solution */
4101  SCIPrelaxationSetSolValid(relaxation, FALSE, FALSE);
4102 
4103  /* clear the storage of external branching candidates */
4104  SCIPbranchcandClearExternCands(branchcand);
4105 
4106  SCIPsetDebugMsg(set, "Processing node %" SCIP_LONGINT_FORMAT " in depth %d, %d siblings\n",
4107  stat->nnodes, actdepth, tree->nsiblings);
4108  SCIPsetDebugMsg(set, "current pseudosolution: obj=%g\n", SCIPlpGetPseudoObjval(lp, set, transprob));
4109  /*debug(SCIPprobPrintPseudoSol(transprob, set));*/
4110 
4111  /* check, if we want to solve the LP at the selected node:
4112  * - solve the LP, if the lp solve depth and frequency demand solving
4113  * - solve the root LP, if the LP solve frequency is set to 0
4114  * - solve the root LP, if there are continuous variables present
4115  * - don't solve the node if its cut off by the pseudo objective value anyway
4116  */
4117  focusnodehaslp = (set->lp_solvedepth == -1 || actdepth <= set->lp_solvedepth);
4118  focusnodehaslp = focusnodehaslp && (set->lp_solvefreq >= 1 && actdepth % set->lp_solvefreq == 0);
4119  focusnodehaslp = focusnodehaslp || (actdepth == 0 && set->lp_solvefreq == 0);
4120  focusnodehaslp = focusnodehaslp && SCIPsetIsLT(set, SCIPlpGetPseudoObjval(lp, set, transprob), primal->cutoffbound);
4121  focusnodehaslp = set->reopt_enable ? focusnodehaslp && SCIPreoptGetSolveLP(reopt, set, focusnode) : focusnodehaslp;
4122  SCIPtreeSetFocusNodeLP(tree, focusnodehaslp);
4123 
4124  /* external node solving loop:
4125  * - propagate domains
4126  * - solve SCIP_LP
4127  * - enforce constraints
4128  * if a constraint handler adds constraints to enforce its own constraints, both, propagation and LP solving
4129  * is applied again (if applicable on current node); however, if the new constraints don't have the enforce flag set,
4130  * it is possible, that the current infeasible solution is not cut off; in this case, we have to declare the solution
4131  * infeasible and perform a branching
4132  */
4133  lastdomchgcount = stat->domchgcount;
4134  lastlpcount = stat->lpcount;
4135  initiallpsolved = FALSE;
4136  fullseparation = TRUE;
4137  heurtiming = SCIP_HEURTIMING_BEFORENODE;
4138  nlperrors = 0;
4139  stat->npricerounds = 0;
4140  stat->nseparounds = 0;
4141  solverelaxagain = TRUE;
4142  solvelpagain = TRUE;
4143  propagateagain = TRUE;
4144  fullpropagation = TRUE;
4145  forcedlpsolve = FALSE;
4146  nloops = 0;
4147 
4148  while( !(*cutoff) && !(*postpone) && (solverelaxagain || solvelpagain || propagateagain) && nlperrors < MAXNLPERRORS && !(*restart) )
4149  {
4150  SCIP_Bool lperror;
4151  SCIP_Bool solverelax;
4152  SCIP_Bool solvelp;
4153  SCIP_Bool propagate;
4154  SCIP_Bool forcedenforcement;
4155  SCIP_Bool relaxcalled;
4156 
4157  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4158 
4159  *unbounded = FALSE;
4160  *infeasible = FALSE;
4161  foundsol = FALSE;
4162 
4163  nloops++;
4164  lperror = FALSE;
4165  lpsolved = FALSE;
4166  relaxcalled = FALSE;
4167  forcedenforcement = FALSE;
4168  afterlpproplps = -1L;
4169 
4170  while( !lperror && !(*cutoff) && (propagateagain || solvelpagain || solverelaxagain
4171  || (afterlpproplps < stat->nnodelps && lpsolved) || relaxcalled) )
4172  {
4173  solverelax = solverelaxagain;
4174  solverelaxagain = FALSE;
4175  solvelp = solvelpagain;
4176  solvelpagain = FALSE;
4177  propagate = propagateagain;
4178  propagateagain = FALSE;
4179 
4180  /* update lower bound with the pseudo objective value, and cut off node by bounding */
4181  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
4182  conflict, cliquetable, cutoff) );
4183 
4184  /* propagate domains before lp solving and solve relaxation and lp */
4185  SCIPsetDebugMsg(set, " -> node solving loop: call propagators that are applicable before%s LP is solved\n",
4186  lpsolved ? " and after" : "");
4187  SCIP_CALL( propAndSolve(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp,
4188  relaxation, pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter,
4189  eventqueue, cliquetable, focusnode, actdepth, propagate, solvelp, solverelax, forcedlpsolve, initiallpsolved,
4190  fullseparation, &afterlpproplps, &heurtiming, &nlperrors, &fullpropagation, &propagateagain, &lpsolved, &relaxcalled,
4191  &solvelpagain, &solverelaxagain, cutoff, postpone, unbounded, stopped, &lperror, &pricingaborted, &forcedenforcement) );
4192  initiallpsolved |= lpsolved;
4193 
4194  /* time or solution limit was hit and we already created a dummy child node to terminate fast */
4195  if( *stopped )
4196  {
4197  /* reset LP feastol to normal value, in case someone tightened it during node solving */
4198  SCIPlpResetFeastol(lp, set);
4199  return SCIP_OKAY;
4200  }
4201  }
4202  fullseparation = FALSE;
4203 
4204  /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4205  updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain);
4206 
4207  /* call primal heuristics that should be applied after the LP relaxation of the node was solved;
4208  * if this is the first loop of the root node, call also AFTERNODE heuristics already here, since they might help
4209  * to improve the primal bound, thereby producing additional reduced cost strengthenings and strong branching
4210  * bound fixings which also might lead to a restart
4211  */
4212  if( !(*postpone) && (!(*cutoff) || SCIPtreeGetNNodes(tree) > 0) )
4213  {
4214  if( actdepth == 0 && !(*afternodeheur) )
4215  {
4216  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL,
4217  SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE, *cutoff, &foundsol, unbounded) );
4218  *afternodeheur = TRUE; /* the AFTERNODE heuristics should not be called again after the node */
4219  }
4220  else if( lpsolved || SCIPrelaxationIsSolValid(relaxation) )
4221  {
4222  SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_AFTERLPLOOP,
4223  *cutoff, &foundsol, unbounded) );
4224  }
4225  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4226 
4227  /* heuristics might have found a solution or set the cutoff bound such that the current node is cut off */
4228  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4229  }
4230 
4231  /* check if heuristics leave us with an invalid LP */
4232  if( lp->resolvelperror )
4233  {
4234  if( forcedlpsolve )
4235  {
4236  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4237  stat->nnodes, stat->nlps);
4238  return SCIP_LPERROR;
4239  }
4241  lp->resolvelperror = FALSE;
4242  nlperrors++;
4243  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4244  "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4245  stat->nnodes, stat->nlps, nlperrors);
4246  }
4247 
4248  if( pricingaborted && !(*cutoff) && SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL )
4249  {
4251 
4252  /* if we just ran into the time limit this is not really a numerical trouble;
4253  * however, if this is not the case, we print messages about numerical troubles in the current LP
4254  */
4255  if( !SCIPsolveIsStopped(set, stat, FALSE) )
4256  {
4257  if( forcedlpsolve )
4258  {
4259  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n",
4260  stat->nnodes, stat->nlps);
4261  return SCIP_LPERROR;
4262  }
4263  nlperrors++;
4264  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4265  "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n",
4266  stat->nnodes, stat->nlps, nlperrors);
4267  }
4268  }
4269 
4270  /* if an improved solution was found, propagate and solve the relaxations again */
4271  if( foundsol && !(*cutoff) )
4272  {
4273  propagateagain = TRUE;
4274  solvelpagain = TRUE;
4275  solverelaxagain = TRUE;
4276  markRelaxsUnsolved(set, relaxation);
4277  }
4278 
4279  /* check for immediate restart */
4280  *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart
4281  || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars)
4282  && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4283 
4284  /* enforce constraints */
4285  branched = FALSE;
4286  if( !(*postpone) && !(*restart) && !(*cutoff) && !solverelaxagain && !solvelpagain && !propagateagain )
4287  {
4288  /* if the solution changed since the last enforcement, we have to completely reenforce it; otherwise, we
4289  * only have to enforce the additional constraints added in the last enforcement, but keep the infeasible
4290  * flag TRUE in order to not declare the infeasible solution feasible due to disregarding the already
4291  * enforced constraints
4292  */
4293  if( lastdomchgcount != stat->domchgcount || lastlpcount != stat->lpcount )
4294  {
4295  lastdomchgcount = stat->domchgcount;
4296  lastlpcount = stat->lpcount;
4297  *infeasible = FALSE;
4298  }
4299 
4300  /* call constraint enforcement */
4301  SCIP_CALL( enforceConstraints(blkmem, set, messagehdlr, stat, transprob, primal, tree, lp, relaxation, sepastore,
4302  branchcand, &branched, cutoff, infeasible, &propagateagain, &solvelpagain, &solverelaxagain,
4303  forcedenforcement) );
4304  assert(branched == (tree->nchildren > 0));
4305  assert(!branched || (!(*cutoff) && *infeasible && !propagateagain && !solvelpagain));
4306  assert(!(*cutoff) || (!branched && *infeasible && !propagateagain && !solvelpagain));
4307  assert(*infeasible || (!branched && !(*cutoff) && !propagateagain && !solvelpagain));
4308  assert(!propagateagain || (!branched && !(*cutoff) && *infeasible));
4309  assert(!solvelpagain || (!branched && !(*cutoff) && *infeasible));
4310 
4311  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4312 
4313  /* apply found cuts */
4314  SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4315  eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain,
4316  &solvelpagain, &solverelaxagain) );
4317 
4318  /* update lower bound with the pseudo objective value, and cut off node by bounding */
4319  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4320 
4321  /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4322  updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain);
4323  }
4324  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4325 
4326  /* The enforcement detected no infeasibility, so, no branching was performed,
4327  * but the pricing was aborted and the current feasible solution does not have to be the
4328  * best solution in the current subtree --> we have to do a pseudo branching,
4329  * so we set infeasible TRUE and add the current solution to the solution pool
4330  */
4331  if( pricingaborted && !(*infeasible) && !(*cutoff) && !(*postpone) && !(*restart) )
4332  {
4333  SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
4334  SCIP_SOL* sol;
4335  SCIP_Bool stored;
4336 
4337  /* in case the relaxation was enforced add this solution, otherwise decide between LP and pseudosol */
4338  if( SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree)
4339  || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4340  {
4341  SCIP_SOL* relaxsol;
4342 
4343  SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4344 
4345  SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4346  eventqueue, eventfilter, relaxsol, FALSE, FALSE, TRUE, TRUE, TRUE,
4347  &stored) );
4348 
4349  SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) );
4350 
4351  if( stored )
4352  {
4353  stat->nrelaxsolsfound++;
4354 
4355  if( primal->nbestsolsfound != oldnbestsolsfound )
4356  {
4357  stat->nrelaxbestsolsfound++;
4358  SCIPstoreSolutionGap(set->scip);
4359  }
4360  }
4361  }
4362  else
4363  {
4364  SCIP_CALL( SCIPsolCreateCurrentSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4365  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4366  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
4367 
4368  if( stored )
4369  {
4370  stat->nlpsolsfound++;
4371 
4372  if( primal->nbestsolsfound != oldnbestsolsfound )
4373  {
4374  stat->nlpbestsolsfound++;
4375  SCIPstoreSolutionGap(set->scip);
4376  }
4377  }
4378  }
4379 
4380  *infeasible = TRUE;
4381  }
4382 
4383  /* if the node is infeasible, but no constraint handler could resolve the infeasibility
4384  * -> branch on LP, external candidates, or the pseudo solution
4385  * -> e.g. select non-fixed binary or integer variable x with value x', create three
4386  * sons: x <= x'-1, x = x', and x >= x'+1.
4387  * In the left and right branch, the current solution is cut off. In the middle
4388  * branch, the constraints can hopefully reduce domains of other variables to cut
4389  * off the current solution.
4390  * In LP branching, we cannot allow adding constraints, because this does not necessary change the LP and can
4391  * therefore lead to an infinite loop.
4392  */
4393  wasforcedlpsolve = forcedlpsolve;
4394  forcedlpsolve = FALSE;
4395  if( (*infeasible) && !(*cutoff) && !(*postpone) && !(*restart)
4396  && (!(*unbounded) || SCIPbranchcandGetNExternCands(branchcand) > 0 || SCIPbranchcandGetNPseudoCands(branchcand) > 0)
4397  && !solverelaxagain && !solvelpagain && !propagateagain && !branched )
4398  {
4399  SCIP_RESULT result = SCIP_DIDNOTRUN;
4400  int nlpcands = 0;
4401 
4402  if( SCIPtreeHasFocusNodeLP(tree) )
4403  {
4404  SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpcands, NULL, NULL) );
4405  }
4406 
4407  if ( nlpcands > 0 || SCIPbranchcandGetNExternCands(branchcand) > 0 )
4408  {
4409  /* If there are LP candidates and their maximal priority is at least the maximal priority of the external
4410  * candidates, then branch on the LP candidates. Note that due to implicit integer variables,
4411  * SCIPbranchcandGetLPMaxPrio(branchcand) might be finite and SCIPbranchcandGetNPrioLPCands(branchcand) > 0,
4412  * but nlpcands == 0. */
4413  if ( SCIPbranchcandGetLPMaxPrio(branchcand) >= SCIPbranchcandGetExternMaxPrio(branchcand) && nlpcands > 0 )
4414  {
4415  assert( SCIPbranchcandGetNPrioLPCands(branchcand) > 0 );
4416  assert( nlpcands > 0 );
4417 
4418  /* branch on LP solution */
4419  SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on LP solution with %d fractionals\n",
4420  SCIPnodeGetDepth(focusnode), nlpcands);
4421  SCIP_CALL( SCIPbranchExecLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4422  eventqueue, primal->cutoffbound, FALSE, &result) );
4423  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4424  assert(result != SCIP_DIDNOTRUN && result != SCIP_DIDNOTFIND);
4425  }
4426  else
4427  {
4428  assert( SCIPbranchcandGetNPrioExternCands(branchcand) > 0 );
4429  assert( SCIPbranchcandGetNExternCands(branchcand) > 0 );
4430 
4431  /* branch on external candidates */
4432  SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on %d external branching candidates.\n",
4433  SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNExternCands(branchcand));
4434  SCIP_CALL( SCIPbranchExecExtern(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand,
4435  eventqueue, primal->cutoffbound, TRUE, &result) );
4436  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4437  }
4438  }
4439 
4440  if( result == SCIP_DIDNOTRUN || result == SCIP_DIDNOTFIND )
4441  {
4442  /* branch on pseudo solution */
4443  SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on pseudo solution with %d unfixed integers\n",
4444  SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNPseudoCands(branchcand));
4445  SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
4446  primal->cutoffbound, TRUE, &result) );
4447  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4448  }
4449 
4450  /* SCIP cannot guarantee convergence if it is necessary to branch on unbounded variables */
4451  if( result == SCIP_BRANCHED )
4452  {
4453  SCIP_VAR* var = stat->lastbranchvar;
4454 
4455  if( var != NULL && !stat->branchedunbdvar && SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS
4457  {
4458  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
4459  "Starting spatial branch-and-bound on unbounded variable <%s> ([%g,%g]) - cannot guarantee finite termination.\n",
4461  stat->branchedunbdvar = TRUE;
4462  }
4463  }
4464 
4465  switch( result )
4466  {
4467  case SCIP_CUTOFF:
4468  assert(tree->nchildren == 0);
4469  *cutoff = TRUE;
4470  SCIPsetDebugMsg(set, " -> branching rule detected cutoff\n");
4471  break;
4472  case SCIP_CONSADDED:
4473  assert(tree->nchildren == 0);
4474  if( nlpcands > 0 )
4475  {
4476  SCIPerrorMessage("LP branching rule added constraint, which was not allowed this time\n");
4477  return SCIP_INVALIDRESULT;
4478  }
4479  propagateagain = TRUE;
4480  solvelpagain = TRUE;
4481  solverelaxagain = TRUE;
4482  markRelaxsUnsolved(set, relaxation);
4483  break;
4484  case SCIP_REDUCEDDOM:
4485  assert(tree->nchildren == 0);
4486  propagateagain = TRUE;
4487  solvelpagain = TRUE;
4488  solverelaxagain = TRUE;
4489  markRelaxsUnsolved(set, relaxation);
4490  break;
4491  case SCIP_SEPARATED:
4492  assert(tree->nchildren == 0);
4493  assert(SCIPsepastoreGetNCuts(sepastore) > 0);
4494  solvelpagain = TRUE;
4495  solverelaxagain = TRUE;
4496  markRelaxsUnsolved(set, relaxation);
4497  break;
4498  case SCIP_BRANCHED:
4499  assert(tree->nchildren >= 1);
4500  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4501  branched = TRUE;
4502 
4503  /* increase the number of internal nodes */
4504  stat->ninternalnodes++;
4505  stat->ntotalinternalnodes++;
4506  break;
4507  case SCIP_DIDNOTFIND: /*lint -fallthrough*/
4508  case SCIP_DIDNOTRUN:
4509  /* all integer variables in the infeasible solution are fixed,
4510  * - if no continuous variables exist and all variables are known, the infeasible pseudo solution is completely
4511  * fixed, and the node can be cut off
4512  * - if at least one continuous variable exists or we do not know all variables due to external pricers, we
4513  * cannot resolve the infeasibility by branching -> solve LP (and maybe price in additional variables)
4514  */
4515  assert(tree->nchildren == 0);
4516  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4517  assert(SCIPbranchcandGetNPseudoCands(branchcand) == 0);
4518 
4519  if( transprob->ncontvars == 0 && set->nactivepricers == 0 )
4520  {
4521  *cutoff = TRUE;
4522  SCIPsetDebugMsg(set, " -> cutoff because all variables are fixed in current node\n");
4523  }
4524  else
4525  {
4526  /* feasible LP solutions with all integers fixed must be feasible
4527  * if also no external branching candidates were available
4528  */
4529  assert(!SCIPtreeHasFocusNodeLP(tree) || pricingaborted);
4530 
4532  {
4533  SCIP_NODE* node;
4534 
4535  /* as we hit the time or iteration limit or another interrupt (e.g., gap limit), we do not want to solve the LP again.
4536  * in order to terminate correctly, we create a "branching" with only one child node
4537  * that is a copy of the focusnode
4538  */
4539  SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) );
4540  assert(tree->nchildren >= 1);
4541  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4542  branched = TRUE;
4543  }
4544  else
4545  {
4546  SCIP_VERBLEVEL verblevel;
4547 
4548  if( pricingaborted )
4549  {
4550  SCIPerrorMessage("pricing was aborted, but no branching could be created!\n");
4551  return SCIP_INVALIDRESULT;
4552  }
4553 
4554  if( wasforcedlpsolve )
4555  {
4556  assert(SCIPtreeHasFocusNodeLP(tree));
4557  SCIPerrorMessage("LP was solved, all integers fixed, some constraint still infeasible, but no branching could be created!\n");
4558  return SCIP_INVALIDRESULT;
4559  }
4560 
4561  verblevel = SCIP_VERBLEVEL_FULL;
4562 
4563  if( !tree->forcinglpmessage && set->disp_verblevel == SCIP_VERBLEVEL_HIGH )
4564  {
4565  verblevel = SCIP_VERBLEVEL_HIGH;
4566 
4567  /* remember that the forcing LP solving message was posted and do only post it again if the
4568  * verblevel is SCIP_VERBLEVEL_FULL
4569  */
4570  tree->forcinglpmessage = TRUE;
4571  }
4572 
4573  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel,
4574  "(node %" SCIP_LONGINT_FORMAT ") forcing the solution of an LP (last LP %" SCIP_LONGINT_FORMAT ")...\n", stat->nnodes, stat->nlps);
4575 
4576  /* solve the LP in the next loop */
4578  solvelpagain = TRUE;
4579  forcedlpsolve = TRUE; /* this LP must be solved without error - otherwise we have to abort */
4580  }
4581  }
4582  break;
4583  default:
4584  SCIPerrorMessage("invalid result code <%d> from SCIPbranchLP(), SCIPbranchExt() or SCIPbranchPseudo()\n", result);
4585  return SCIP_INVALIDRESULT;
4586  } /*lint !e788*/
4587  assert(*cutoff || solvelpagain || propagateagain || branched); /* something must have been done */
4588  assert(!(*cutoff) || (!solvelpagain && !propagateagain && !branched));
4589  assert(!solvelpagain || (!(*cutoff) && !branched));
4590  assert(!propagateagain || (!(*cutoff) && !branched));
4591  assert(!branched || (!solvelpagain && !propagateagain));
4592  assert(branched == (tree->nchildren > 0));
4593 
4594  /* apply found cuts */
4595  SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand,
4596  eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain,
4597  &solvelpagain, &solverelaxagain) );
4598 
4599  /* update lower bound with the pseudo objective value, and cut off node by bounding */
4600  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) );
4601 
4602  /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */
4603  updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain);
4604  }
4605 
4606  /* check for immediate restart */
4607  *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart
4608  || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars)
4609  && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4610 
4611  SCIPsetDebugMsg(set, "node solving iteration %d finished: cutoff=%u, postpone=%u, propagateagain=%u, solverelaxagain=%u, solvelpagain=%u, nlperrors=%d, restart=%u\n",
4612  nloops, *cutoff, *postpone, propagateagain, solverelaxagain, solvelpagain, nlperrors, *restart);
4613  }
4614  assert(SCIPsepastoreGetNCuts(sepastore) == 0);
4615  assert(*cutoff || SCIPconflictGetNConflicts(conflict) == 0);
4616 
4617  /* flush the conflict set storage */
4618  SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable) );
4619 
4620  /* check for too many LP errors */
4621  if( nlperrors >= MAXNLPERRORS )
4622  {
4623  SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- aborting\n", stat->nnodes, stat->nlps);
4624  return SCIP_LPERROR;
4625  }
4626 
4627  /* check for final restart */
4628  restartfac = set->presol_subrestartfac;
4629  if( actdepth == 0 )
4630  restartfac = MIN(restartfac, set->presol_restartfac);
4631  *restart = *restart || (restartAllowed(set, stat) && (stat->userrestart
4632  || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars)
4633  && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) );
4634 
4635  /* remember the last root LP solution */
4636  if( actdepth == 0 && !(*cutoff) && !(*unbounded) && !(*postpone) )
4637  {
4638  /* the root pseudo objective value and pseudo objective value should be equal in the root node */
4639  assert(SCIPsetIsFeasEQ(set, SCIPlpGetGlobalPseudoObjval(lp, set, transprob), SCIPlpGetPseudoObjval(lp, set, transprob)));
4640 
4641  SCIPprobStoreRootSol(transprob, set, stat, lp, SCIPtreeHasFocusNodeLP(tree));
4642  }
4643 
4644  /* check for cutoff */
4645  if( *cutoff )
4646  {
4647  SCIPsetDebugMsg(set, "node is cut off\n");
4648 
4649  SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set));
4650  *infeasible = TRUE;
4651  SCIP_CALL( SCIPdebugRemoveNode(blkmem, set, focusnode) ); /*lint !e506 !e774*/
4652 
4653  /* the LP might have been unbounded but not enforced, because the node is cut off anyway */
4654  *unbounded = FALSE;
4655  }
4656  else if( !(*unbounded) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && lp->looseobjvalinf == 0 )
4657  {
4658  /* update the regression statistic nlpbranchcands and LP objective value */
4659  int nlpbranchcands;
4660  SCIP_Real lpobjval;
4661 
4662  /* get number of LP candidate variables */
4663  SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpbranchcands, NULL, NULL) );
4664 
4665  /* get LP objective value */
4666  lpobjval = SCIPlpGetObjval(lp, set, transprob);
4667  assert(lpobjval != SCIP_INVALID); /*lint !e777*/
4668 
4669  /* add the observation to the regression */
4670  SCIPregressionAddObservation(stat->regressioncandsobjval, (SCIP_Real)nlpbranchcands, lpobjval);
4671  }
4672 
4673  /* reset LP feastol to normal value, in case someone tightened it during node solving */
4674  SCIPlpResetFeastol(lp, set);
4675 
4676  return SCIP_OKAY;
4677 }
4678 
4679 /** if feasible, adds current solution to the solution storage */
4680 static
4682  BMS_BLKMEM* blkmem, /**< block memory buffers */
4683  SCIP_SET* set, /**< global SCIP settings */
4684  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4685  SCIP_STAT* stat, /**< dynamic problem statistics */
4686  SCIP_PROB* origprob, /**< original problem */
4687  SCIP_PROB* transprob, /**< transformed problem after presolve */
4688  SCIP_PRIMAL* primal, /**< primal data */
4689  SCIP_RELAXATION* relaxation, /**< global relaxation data */
4690  SCIP_TREE* tree, /**< branch and bound tree */
4691  SCIP_REOPT* reopt, /**< reoptimization data structure */
4692  SCIP_LP* lp, /**< LP data */
4693  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4694  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4695  SCIP_Bool checksol /**< should the solution be checked? */
4696  )
4697 {
4698  SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound;
4699  SCIP_SOL* sol;
4700  SCIP_Bool foundsol;
4701 
4702  /* found a feasible solution */
4703  if( SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree)
4704  || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
4705  {
4706  /* start clock for relaxation solutions */
4707  SCIPclockStart(stat->relaxsoltime, set);
4708 
4709  SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) );
4710 
4711  SCIPsetDebugMsg(set, "found relaxation solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4712 
4713  if( checksol || set->misc_exactsolve )
4714  {
4715  /* if we want to solve exactly, we have to check the solution exactly again */
4716  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4717  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4718  }
4719  else
4720  {
4721  SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4722  eventqueue, eventfilter, &sol, &foundsol) );
4723  }
4724 
4725  if( foundsol )
4726  {
4727  stat->nrelaxsolsfound++;
4728 
4729  if( primal->nbestsolsfound != oldnbestsolsfound )
4730  {
4731  stat->nrelaxbestsolsfound++;
4732  SCIPstoreSolutionGap(set->scip);
4733  }
4734  }
4735 
4736  /* stop clock for relaxation solutions */
4737  SCIPclockStop(stat->relaxsoltime, set);
4738  }
4739  else if( SCIPtreeHasFocusNodeLP(tree) )
4740  {
4741  assert(lp->primalfeasible);
4742 
4743  /* start clock for LP solutions */
4744  SCIPclockStart(stat->lpsoltime, set);
4745 
4746  /* add solution to storage */
4747  SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4748 
4749  SCIPsetDebugMsg(set, "found lp solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4750 
4751  if( checksol || set->misc_exactsolve )
4752  {
4753  /* if we want to solve exactly, we have to check the solution exactly again */
4754  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4755  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4756  }
4757  else
4758  {
4759  SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4760  eventqueue, eventfilter, &sol, &foundsol) );
4761  }
4762 
4763  if( foundsol )
4764  {
4765  stat->nlpsolsfound++;
4766 
4767  if( primal->nbestsolsfound != oldnbestsolsfound )
4768  {
4769  stat->nlpbestsolsfound++;
4770  SCIPstoreSolutionGap(set->scip);
4771  }
4772  }
4773 
4774  /* stop clock for LP solutions */
4775  SCIPclockStop(stat->lpsoltime, set);
4776  }
4777  else
4778  {
4779  /* start clock for pseudo solutions */
4780  SCIPclockStart(stat->pseudosoltime, set);
4781 
4782  /* add solution to storage */
4783  SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
4784 
4785  SCIPsetDebugMsg(set, "found pseudo solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob));
4786 
4787  if( checksol || set->misc_exactsolve )
4788  {
4789  /* if we want to solve exactly, we have to check the solution exactly again */
4790  SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4791  eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) );
4792  }
4793  else
4794  {
4795  SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp,
4796  eventqueue, eventfilter, &sol, &foundsol) );
4797  }
4798 
4799  /* stop clock for pseudo solutions */
4800  SCIPclockStop(stat->pseudosoltime, set);
4801 
4802  if( foundsol )
4803  {
4804  stat->npssolsfound++;
4805 
4806  if( primal->nbestsolsfound != oldnbestsolsfound )
4807  {
4808  stat->npsbestsolsfound++;
4809  SCIPstoreSolutionGap(set->scip);
4810  }
4811  }
4812  }
4813 
4814  return SCIP_OKAY;
4815 }
4816 
4817 /** main solving loop */
4819  BMS_BLKMEM* blkmem, /**< block memory buffers */
4820  SCIP_SET* set, /**< global SCIP settings */
4821  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4822  SCIP_STAT* stat, /**< dynamic problem statistics */
4823  SCIP_MEM* mem, /**< block memory pools */
4824  SCIP_PROB* origprob, /**< original problem */
4825  SCIP_PROB* transprob, /**< transformed problem after presolve */
4826  SCIP_PRIMAL* primal, /**< primal data */
4827  SCIP_TREE* tree, /**< branch and bound tree */
4828  SCIP_REOPT* reopt, /**< reoptimization data structure */
4829  SCIP_LP* lp, /**< LP data */
4830  SCIP_RELAXATION* relaxation, /**< global relaxation data */
4831  SCIP_PRICESTORE* pricestore, /**< pricing storage */
4832  SCIP_SEPASTORE* sepastore, /**< separation storage */
4833  SCIP_CUTPOOL* cutpool, /**< global cut pool */
4834  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
4835  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4836  SCIP_CONFLICT* conflict, /**< conflict analysis data */
4837  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4838  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4839  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4840  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4841  SCIP_Bool* restart /**< should solving process be started again with presolving? */
4842  )
4843 {
4844  SCIP_NODESEL* nodesel;
4845  SCIP_NODE* focusnode;
4846  SCIP_NODE* nextnode;
4847  SCIP_EVENT event;
4848  SCIP_Real restartfac;
4849  SCIP_Real restartconfnum;
4850  int nnodes;
4851  int depth;
4852  SCIP_Bool cutoff;
4853  SCIP_Bool postpone;
4854  SCIP_Bool unbounded;
4855  SCIP_Bool infeasible;
4856  SCIP_Bool foundsol;
4857 
4858  assert(set != NULL);
4859  assert(blkmem != NULL);
4860  assert(stat != NULL);
4861  assert(transprob != NULL);
4862  assert(tree != NULL);
4863  assert(lp != NULL);
4864  assert(pricestore != NULL);
4865  assert(sepastore != NULL);
4866  assert(branchcand != NULL);
4867  assert(cutpool != NULL);
4868  assert(delayedcutpool != NULL);
4869  assert(primal != NULL);
4870  assert(eventfilter != NULL);
4871  assert(eventqueue != NULL);
4872  assert(restart != NULL);
4873 
4874  /* check for immediate restart (if problem solving marked to be restarted was aborted) */
4875  restartfac = set->presol_subrestartfac;
4876  if( SCIPtreeGetCurrentDepth(tree) == 0 )
4877  restartfac = MIN(restartfac, set->presol_restartfac);
4878  *restart = restartAllowed(set, stat) && (stat->userrestart
4879  || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars)
4880  && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars)) );
4881 
4882  /* calculate the number of successful conflict analysis calls that should trigger a restart */
4883  if( set->conf_restartnum > 0 )
4884  {
4885  int i;
4886 
4887  restartconfnum = (SCIP_Real)set->conf_restartnum;
4888  for( i = 0; i < stat->nconfrestarts; ++i )
4889  restartconfnum *= set->conf_restartfac;
4890  }
4891  else
4892  restartconfnum = SCIP_REAL_MAX;
4893  assert(restartconfnum >= 0.0);
4894 
4895  /* switch status to UNKNOWN */
4896  stat->status = SCIP_STATUS_UNKNOWN;
4897 
4898  focusnode = NULL;
4899  nextnode = NULL;
4900  unbounded = FALSE;
4901  postpone = FALSE;
4902 
4903  while( !SCIPsolveIsStopped(set, stat, TRUE) && !(*restart) )
4904  {
4905  SCIP_Longint nsuccessconflicts;
4906  SCIP_Bool afternodeheur;
4907  SCIP_Bool stopped;
4908  SCIP_Bool branched;
4909 
4910  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4911 
4912  foundsol = FALSE;
4913  infeasible = FALSE;
4914 
4915  do
4916  {
4917  /* update the memory saving flag, switch algorithms respectively */
4918  SCIPstatUpdateMemsaveMode(stat, set, messagehdlr, mem);
4919 
4920  /* get the current node selector */
4921  nodesel = SCIPsetGetNodesel(set, stat);
4922 
4923  /* inform tree about the current node selector */
4924  SCIP_CALL( SCIPtreeSetNodesel(tree, set, messagehdlr, stat, nodesel) );
4925 
4926  /* the next node was usually already selected in the previous solving loop before the primal heuristics were
4927  * called, because they need to know, if the next node will be a child/sibling (plunging) or not;
4928  * if the heuristics found a new best solution that cut off some of the nodes, the node selector must be called
4929  * again, because the selected next node may be invalid due to cut off
4930  */
4931  if( nextnode == NULL )
4932  {
4933  /* select next node to process */
4934  SCIP_CALL( SCIPnodeselSelect(nodesel, set, &nextnode) );
4935  }
4936  focusnode = nextnode;
4937  nextnode = NULL;
4938  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4939 
4940  /* start node activation timer */
4941  SCIPclockStart(stat->nodeactivationtime, set);
4942 
4943  /* focus selected node */
4944  SCIP_CALL( SCIPnodeFocus(&focusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt,
4945  lp, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, FALSE, FALSE) );
4946  if( cutoff )
4947  stat->ndelayedcutoffs++;
4948 
4949  /* stop node activation timer */
4950  SCIPclockStop(stat->nodeactivationtime, set);
4951 
4952  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4953  }
4954  while( cutoff ); /* select new node, if the current one was located in a cut off subtree */
4955 
4956  assert(SCIPtreeGetCurrentNode(tree) == focusnode);
4957  assert(SCIPtreeGetFocusNode(tree) == focusnode);
4958 
4959  /* if no more node was selected, we finished optimization */
4960  if( focusnode == NULL )
4961  {
4962  assert(SCIPtreeGetNNodes(tree) == 0);
4963  break;
4964  }
4965 
4966  /* update maxdepth and node count statistics */
4967  depth = SCIPnodeGetDepth(focusnode);
4968  stat->maxdepth = MAX(stat->maxdepth, depth);
4969  stat->maxtotaldepth = MAX(stat->maxtotaldepth, depth);
4970  stat->nnodes++;
4971  stat->ntotalnodes++;
4972 
4973  /* update reference bound statistic, if available */
4974  if( SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), stat->referencebound) )
4975  stat->nnodesaboverefbound++;
4976 
4977  /* issue NODEFOCUSED event */
4979  SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
4980  SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
4981 
4982  /* solve focus node */
4983  SCIP_CALL( solveNode(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation,
4984  pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter, eventqueue,
4985  cliquetable, &cutoff, &postpone, &unbounded, &infeasible, restart, &afternodeheur, &stopped) );
4986  assert(!cutoff || infeasible);
4987  assert(BMSgetNUsedBufferMemory(mem->buffer) == 0);
4988  assert(SCIPtreeGetCurrentNode(tree) == focusnode);
4989  assert(SCIPtreeGetFocusNode(tree) == focusnode);
4990 
4991  branched = (tree->nchildren > 0);
4992 
4993  if( stopped )
4994  break;
4995 
4996  /* check for restart */
4997  if( !(*restart) && !postpone )
4998  {
4999  /* change color of node in visualization */
5000  SCIPvisualSolvedNode(stat->visual, set, stat, focusnode);
5001 
5002  /* check, if the current solution is feasible */
5003  if( !infeasible )
5004  {
5005  SCIP_Bool feasible;
5006 
5007  assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved));
5008  assert(!cutoff);
5009 
5010  /* in the unbounded case, we check the solution w.r.t. the original problem, because we do not want to rely
5011  * on the LP feasibility and integrality is not checked for unbounded solutions, anyway
5012  */
5013  if( unbounded )
5014  {
5015  SCIP_SOL* sol;
5016 
5017  if( SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree)
5018  || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) )
5019  {
5020  SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) );
5021  }
5022  else if( SCIPtreeHasFocusNodeLP(tree) )
5023  {
5024  SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
5025  }
5026  else
5027  {
5028  SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) );
5029  }
5030  SCIP_CALL( SCIPcheckSolOrig(set->scip, sol, &feasible, FALSE, FALSE) );
5031 
5032  SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) );
5033  }
5034  else
5035  feasible = TRUE;
5036 
5037  /* node solution is feasible: add it to the solution store */
5038  if( feasible )
5039  {
5040  SCIP_CALL( addCurrentSolution(blkmem, set, messagehdlr, stat, origprob, transprob, primal, relaxation, tree, reopt,
5041  lp, eventqueue, eventfilter, FALSE) );
5042 
5043  /* update the cutoff pointer if the new solution made the cutoff bound equal to the lower bound */
5044  SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, &cutoff) );
5045 
5046  /* increment number of feasible leaf nodes */
5047  stat->nfeasleaves++;
5048 
5049  /* issue NODEFEASIBLE event */
5051  SCIP_CALL( SCIPeventChgNode(&event, focusnode) );
5052  SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
5053 
5054  if( set->reopt_enable )
5055  {
5056  assert(reopt != NULL);
5057  SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp,
5058  SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5059  focusnode->lowerbound, tree->effectiverootdepth) );
5060  }
5061  }
5062  }
5063  else if( !unbounded || branched )
5064  {
5065  /* node solution is not feasible */
5066  if( !branched )
5067  {
5068  assert(tree->nchildren == 0);
5069 
5070  /* change color of node in visualization output */
5071  SCIPvisualCutoffNode(stat->visual, set, stat, focusnode, TRUE);
5072 
5073  /* issue NODEINFEASIBLE event */
5075 
5076  /* we only increase the number of objective leaf nodes if we hit the LP objective limit; we might have also
5077  * hit the objective limit at a node that is actually infeasible, or a dual reduction led to an infeasibility prior
5078  * to LP solving such that the node will be marked as infeasible */
5080  stat->nobjleaves++;
5081  else
5082  stat->ninfeasleaves++;
5083 
5084  if( set->reopt_enable )
5085  {
5086  assert(reopt != NULL);
5087  SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEINFEASIBLE, lp,
5088  SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode,
5089  focusnode->lowerbound, tree->effectiverootdepth) );
5090  }
5091 
5092  /* increase the cutoff counter of the branching variable */
5093  if( stat->lastbranchvar != NULL )
5094  {
5095