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