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