Scippy

SCIP

Solving Constraint Integer Programs

sepastore.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepastore.c
17  * @ingroup OTHER_CFILES
18  * @brief methods for storing separated cuts
19  * @author Tobias Achterberg
20  * @author Marc Pfetsch
21  * @author Leona Gottwald
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include <assert.h>
27 
28 #include "scip/def.h"
29 #include "scip/set.h"
30 #include "scip/stat.h"
31 #include "scip/lp.h"
32 #include "scip/var.h"
33 #include "scip/tree.h"
34 #include "scip/reopt.h"
35 #include "scip/sepastore.h"
36 #include "scip/event.h"
37 #include "scip/sepa.h"
38 #include "scip/cons.h"
39 #include "scip/debug.h"
40 #include "scip/scip.h"
41 #include "scip/cuts.h"
42 #include "scip/cutsel.h"
43 #include "scip/struct_event.h"
44 #include "scip/struct_sepastore.h"
45 #include "scip/misc.h"
46 
47 
48 
49 /*
50  * dynamic memory arrays
51  */
52 
53 /** resizes cuts and score arrays to be able to store at least num entries */
54 static
56  SCIP_SEPASTORE* sepastore, /**< separation storage */
57  SCIP_SET* set, /**< global SCIP settings */
58  int num /**< minimal number of slots in array */
59  )
60 {
61  assert(sepastore != NULL);
62  assert(set != NULL);
63 
64  if( num > sepastore->cutssize )
65  {
66  int newsize;
67 
68  newsize = SCIPsetCalcMemGrowSize(set, num);
69  SCIP_ALLOC( BMSreallocMemoryArray(&sepastore->cuts, newsize) );
70  sepastore->cutssize = newsize;
71  }
72  assert(num <= sepastore->cutssize);
73 
74  return SCIP_OKAY;
75 }
76 
77 /** creates separation storage */
79  SCIP_SEPASTORE** sepastore, /**< pointer to store separation storage */
80  BMS_BLKMEM* blkmem, /**< block memory */
81  SCIP_SET* set /**< global SCIP settings */
82  )
83 {
84  assert(sepastore != NULL);
85 
86  SCIP_ALLOC( BMSallocMemory(sepastore) );
87 
88  (*sepastore)->cuts = NULL;
89  (*sepastore)->cutssize = 0;
90  (*sepastore)->ncuts = 0;
91  (*sepastore)->nforcedcuts = 0;
92  (*sepastore)->ncutsfound = 0;
93  (*sepastore)->ncutsfoundround = 0;
94  (*sepastore)->ncutsapplied = 0;
95  (*sepastore)->initiallp = FALSE;
96  (*sepastore)->forcecuts = FALSE;
97 
98  SCIP_CALL( SCIPrandomCreate(&(*sepastore)->randnumgen, blkmem, (unsigned int)SCIPsetInitializeRandomSeed(set, 0x5EED)) );
99 
100  return SCIP_OKAY;
101 }
102 
103 /** frees separation storage */
105  SCIP_SEPASTORE** sepastore, /**< pointer to store separation storage */
106  BMS_BLKMEM* blkmem /**< block memory */
107  )
108 {
109  assert(sepastore != NULL);
110  assert(*sepastore != NULL);
111  assert((*sepastore)->ncuts == 0);
112 
113  SCIPrandomFree(&(*sepastore)->randnumgen, blkmem);
114  BMSfreeMemoryArrayNull(&(*sepastore)->cuts);
115  BMSfreeMemory(sepastore);
116 
117  return SCIP_OKAY;
118 }
119 
120 /** informs separation storage that the setup of the initial LP starts now */
122  SCIP_SEPASTORE* sepastore /**< separation storage */
123  )
124 {
125  assert(sepastore != NULL);
126  assert(!sepastore->initiallp);
127  assert(sepastore->ncuts == 0);
128 
129  sepastore->initiallp = TRUE;
130 }
131 
132 /** informs separation storage that the setup of the initial LP is now finished */
134  SCIP_SEPASTORE* sepastore /**< separation storage */
135  )
136 {
137  assert(sepastore != NULL);
138  assert(sepastore->initiallp);
139  assert(sepastore->ncuts == 0);
140 
141  sepastore->initiallp = FALSE;
142 }
143 
144 /** informs separation storage that the following cuts should be used in any case */
146  SCIP_SEPASTORE* sepastore /**< separation storage */
147  )
148 {
149  assert(sepastore != NULL);
150  assert(!sepastore->forcecuts);
151 
152  sepastore->forcecuts = TRUE;
153 }
154 
155 /** informs separation storage that the following cuts should no longer be used in any case */
157  SCIP_SEPASTORE* sepastore /**< separation storage */
158  )
159 {
160  assert(sepastore != NULL);
161  assert(sepastore->forcecuts);
162 
163  sepastore->forcecuts = FALSE;
164 }
165 
166 /** checks cut for redundancy due to activity bounds */
167 static
169  SCIP_SEPASTORE* sepastore, /**< separation storage */
170  SCIP_SET* set, /**< global SCIP settings */
171  SCIP_STAT* stat, /**< problem statistics data */
172  SCIP_ROW* cut /**< separated cut */
173  )
174 {
175  SCIP_Real minactivity;
176  SCIP_Real maxactivity;
177  SCIP_Real lhs;
178  SCIP_Real rhs;
179 
180  assert(sepastore != NULL);
181  assert(cut != NULL);
182 
183  /* modifiable cuts cannot be declared redundant, since we don't know all coefficients */
184  if( SCIProwIsModifiable(cut) )
185  return FALSE;
186 
187  /* check for activity redundancy */
188  lhs = SCIProwGetLhs(cut);
189  rhs = SCIProwGetRhs(cut);
190  minactivity = SCIProwGetMinActivity(cut, set, stat);
191  maxactivity = SCIProwGetMaxActivity(cut, set, stat);
192 
193  if( (SCIPsetIsInfinity(set, -lhs) || SCIPsetIsLE(set, lhs, minactivity)) &&
194  (SCIPsetIsInfinity(set, rhs) || SCIPsetIsLE(set, maxactivity, rhs)) )
195  {
196  SCIPsetDebugMsg(set, "ignoring activity redundant cut <%s> (sides=[%g,%g], act=[%g,%g])\n",
197  SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
198  /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
199  return TRUE;
200  }
201 
202  return FALSE;
203 }
204 
205 /** checks cut for redundancy or infeasibility due to activity bounds */
206 static
208  SCIP_SEPASTORE* sepastore, /**< separation storage */
209  SCIP_SET* set, /**< global SCIP settings */
210  SCIP_STAT* stat, /**< problem statistics data */
211  SCIP_ROW* cut, /**< separated cut */
212  SCIP_Bool* infeasible /**< pointer to store whether the cut has been detected to be infeasible */
213  )
214 {
215  SCIP_Real minactivity;
216  SCIP_Real maxactivity;
217  SCIP_Real lhs;
218  SCIP_Real rhs;
219 
220  assert(sepastore != NULL);
221  assert(cut != NULL);
222  assert(infeasible != NULL);
223 
224  *infeasible = FALSE;
225 
226  /* modifiable cuts cannot be declared redundant or infeasible, since we don't know all coefficients */
227  if( SCIProwIsModifiable(cut) )
228  return FALSE;
229 
230  /* check for activity redundancy */
231  lhs = SCIProwGetLhs(cut);
232  rhs = SCIProwGetRhs(cut);
233  minactivity = SCIProwGetMinActivity(cut, set, stat);
234  maxactivity = SCIProwGetMaxActivity(cut, set, stat);
235 
236  if( (SCIPsetIsInfinity(set, -lhs) || SCIPsetIsLE(set, lhs, minactivity)) &&
237  (SCIPsetIsInfinity(set, rhs) || SCIPsetIsLE(set, maxactivity, rhs)) )
238  {
239  SCIPsetDebugMsg(set, "ignoring activity redundant cut <%s> (sides=[%g,%g], act=[%g,%g])\n",
240  SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
241  /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
242  return TRUE;
243  }
244 
245  if( (!SCIPsetIsInfinity(set, rhs) && SCIPsetIsFeasPositive(set, minactivity - rhs)) ||
246  (!SCIPsetIsInfinity(set, -lhs) && SCIPsetIsFeasNegative(set, maxactivity - lhs)) )
247  {
248  SCIPsetDebugMsg(set, "cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n",
249  SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
250  /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
251  *infeasible = TRUE;
252  return TRUE;
253  }
254 
255  return FALSE;
256 }
257 
258 /** checks whether a cut with only one variable can be applied as boundchange
259  *
260  * This is the case if the bound change would prove infeasibility (w.r.t feastol), or if the new bound is at least
261  * epsilon better than the old bound. In the latter case, also the opposite bound has to be taken into account.
262  */
263 static
265  SCIP_SET* set, /**< global SCIP settings */
266  SCIP_ROW* cut /**< cut with a single variable */
267  )
268 {
269  SCIP_COL** cols;
270  SCIP_Real* vals;
271  SCIP_VAR* var;
272  SCIP_Real lhs;
273  SCIP_Real rhs;
274  SCIP_Bool local;
275  SCIP_Real oldlb;
276  SCIP_Real oldub;
277 
278  assert(set != NULL);
279  assert(cut != NULL);
280  assert(!SCIProwIsModifiable(cut));
281  assert(SCIProwGetNNonz(cut) == 1);
282 
283  /* get the single variable and its coefficient of the cut */
284  cols = SCIProwGetCols(cut);
285  assert(cols != NULL);
286 
287  var = SCIPcolGetVar(cols[0]);
288  vals = SCIProwGetVals(cut);
289  assert(vals != NULL);
290  assert(!SCIPsetIsZero(set, vals[0]));
291 
292  /* if the coefficient is nearly zero, we better ignore this cut for numerical reasons */
293  if( SCIPsetIsFeasZero(set, vals[0]) )
294  return FALSE;
295 
296  local = SCIProwIsLocal(cut);
297 
298  oldlb = local ? SCIPvarGetLbLocal(var) : SCIPvarGetLbGlobal(var);
299  oldub = local ? SCIPvarGetUbLocal(var) : SCIPvarGetUbGlobal(var);
300 
301  /* get the left hand side of the cut and convert it to a bound */
302  lhs = SCIProwGetLhs(cut);
303  if( !SCIPsetIsInfinity(set, -lhs) )
304  {
305  lhs -= SCIProwGetConstant(cut);
306  if( vals[0] > 0.0 )
307  {
308  /* coefficient is positive -> lhs corresponds to lower bound */
309  SCIP_Real newlb;
310 
311  newlb = lhs/vals[0];
312  SCIPvarAdjustLb(var, set, &newlb);
313 
314  /* bound changes that improve the bound sufficiently are applicable */
315  if( SCIPsetIsFeasGT(set, newlb, oldub) || SCIPsetIsGT(set, MIN(newlb, oldub), oldlb) )
316  return TRUE;
317  }
318  else
319  {
320  /* coefficient is negative -> lhs corresponds to upper bound */
321  SCIP_Real newub;
322 
323  newub = lhs/vals[0];
324  SCIPvarAdjustUb(var, set, &newub);
325 
326  /* bound changes that improve the bound sufficiently are applicable */
327  if( SCIPsetIsFeasLT(set, newub, oldlb) || SCIPsetIsLT(set, MAX(newub, oldlb), oldub) )
328  return TRUE;
329  }
330  }
331 
332  /* get the right hand side of the cut and convert it to a bound */
333  rhs = SCIProwGetRhs(cut);
334  if( !SCIPsetIsInfinity(set, rhs) )
335  {
336  rhs -= SCIProwGetConstant(cut);
337  if( vals[0] > 0.0 )
338  {
339  /* coefficient is positive -> rhs corresponds to upper bound */
340  SCIP_Real newub;
341 
342  newub = rhs/vals[0];
343  SCIPvarAdjustUb(var, set, &newub);
344 
345  /* bound changes that improve the bound sufficiently are applicable */
346  if( SCIPsetIsFeasLT(set, newub, oldlb) || SCIPsetIsLT(set, MAX(newub, oldlb), oldub) )
347  return TRUE;
348  }
349  else
350  {
351  /* coefficient is negative -> rhs corresponds to lower bound */
352  SCIP_Real newlb;
353 
354  newlb = rhs/vals[0];
355  SCIPvarAdjustLb(var, set, &newlb);
356 
357  /* bound changes that improve the bound sufficiently are applicable */
358  if( SCIPsetIsFeasGT(set, newlb, oldub) || SCIPsetIsGT(set, MIN(newlb, oldub), oldlb) )
359  return TRUE;
360  }
361  }
362 
363  return FALSE;
364 }
365 
366 /** removes a non-forced cut from the separation storage */
367 static
369  SCIP_SEPASTORE* sepastore, /**< separation storage */
370  BMS_BLKMEM* blkmem, /**< block memory */
371  SCIP_SET* set, /**< global SCIP settings */
372  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
373  SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
374  SCIP_LP* lp, /**< LP data */
375  int pos /**< position of cut to delete */
376  )
377 {
378  assert(sepastore != NULL);
379  assert(sepastore->cuts != NULL);
380  assert(sepastore->nforcedcuts <= pos && pos < sepastore->ncuts);
381 
382  /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
383  if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 )
384  {
385  SCIP_EVENT* event;
386 
387  SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[pos]) );
388  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
389  }
390 
391  /* release the row */
392  SCIP_CALL( SCIProwRelease(&sepastore->cuts[pos], blkmem, set, lp) );
393 
394  /* move last cut to the empty position */
395  sepastore->cuts[pos] = sepastore->cuts[sepastore->ncuts-1];
396  sepastore->ncuts--;
397 
398  return SCIP_OKAY;
399 }
400 
401 /** adds cut to separation storage and captures it */
403  SCIP_SEPASTORE* sepastore, /**< separation storage */
404  BMS_BLKMEM* blkmem, /**< block memory */
405  SCIP_SET* set, /**< global SCIP settings */
406  SCIP_STAT* stat, /**< problem statistics data */
407  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
408  SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
409  SCIP_LP* lp, /**< LP data */
410  SCIP_ROW* cut, /**< separated cut */
411  SCIP_Bool forcecut, /**< should the cut be forced to enter the LP? */
412  SCIP_Bool root, /**< are we at the root node? */
413  SCIP_Bool* infeasible /**< pointer to store whether the cut is infeasible */
414  )
415 {
416  SCIP_Bool redundant;
417  int pos;
418 
419  assert(sepastore != NULL);
420  assert(sepastore->nforcedcuts <= sepastore->ncuts);
421  assert(set != NULL);
422  assert(cut != NULL);
423  assert(!SCIPsetIsInfinity(set, -SCIProwGetLhs(cut)) || !SCIPsetIsInfinity(set, SCIProwGetRhs(cut)));
424  assert(eventqueue != NULL);
425  assert(eventfilter != NULL);
426 
427  /* debug: check cut for feasibility */
428  SCIP_CALL( SCIPdebugCheckRow(set, cut) ); /*lint !e506 !e774*/
429 
430  /* update statistics of total number of found cuts */
431  if( !sepastore->initiallp )
432  {
433  sepastore->ncutsfound++;
434  sepastore->ncutsfoundround++;
435  }
436 
437  /* the cut will be forced to enter the LP if the dual must be collected and the initial LP is being constructed */
438  forcecut = forcecut || (set->lp_alwaysgetduals && sepastore->initiallp);
439 
440  /* in the root node, every local cut is a global cut, and global cuts are nicer in many ways ... */
441  if( root && SCIProwIsLocal(cut) )
442  {
443  SCIPsetDebugMsg(set, "change local flag of cut <%s> to FALSE due to addition in root node\n", SCIProwGetName(cut));
444 
446 
447  assert(!SCIProwIsLocal(cut));
448  }
449 
450  /* check cut for redundancy or infeasibility */
451  redundant = sepastoreIsCutRedundantOrInfeasible(sepastore, set, stat, cut, infeasible);
452  /* Note that we add infeasible rows in any case, since we cannot be sure whether the return values are handled
453  * correctly. In this way, the LP becomes infeasible. */
454 
455  /* in each separation round, make sure that at least one (even redundant) cut enters the LP to avoid cycling */
456  if( !forcecut && sepastore->ncuts > 0 && redundant )
457  return SCIP_OKAY;
458 
459  /* if only one cut is currently present in sepastore, it could be redundant; in this case, it can now be removed
460  * again, because now a non redundant cut enters the sepastore */
461  if( sepastore->ncuts == 1 && sepastoreIsCutRedundant(sepastore, set, stat, sepastore->cuts[0]) )
462  {
463  /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
464  if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 )
465  {
466  SCIP_EVENT* event;
467 
468  SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[0]) );
469  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
470  }
471 
472  SCIP_CALL( SCIProwRelease(&sepastore->cuts[0], blkmem, set, lp) );
473  sepastore->ncuts = 0;
474  sepastore->nforcedcuts = 0;
475  }
476 
477  /* a cut is forced to enter the LP if
478  * - we construct the initial LP, or
479  * - it has infinite score factor, or
480  * - it is a bound change that can be applied
481  * if it is a non-forced cut and no cuts should be added, abort
482  */
483  forcecut = forcecut || sepastore->initiallp || sepastore->forcecuts || (!SCIProwIsModifiable(cut) && SCIProwGetNNonz(cut) == 1 && sepastoreIsBdchgApplicable(set, cut));
484  if( !forcecut && SCIPsetGetSepaMaxcuts(set, root) == 0 )
485  return SCIP_OKAY;
486 
487  /* get enough memory to store the cut */
488  SCIP_CALL( sepastoreEnsureCutsMem(sepastore, set, sepastore->ncuts+1) );
489  assert(sepastore->ncuts < sepastore->cutssize);
490 
491  SCIPsetDebugMsg(set, "adding cut <%s> to separation storage of size %d (forcecut=%u, len=%d)\n",
492  SCIProwGetName(cut), sepastore->ncuts, forcecut, SCIProwGetNNonz(cut));
493  /*SCIP_CALL( SCIPprintRow(set->scip, cut, NULL) );*/
494 
495  /* capture the cut */
496  SCIProwCapture(cut);
497 
498  /* add cut to arrays */
499  if( forcecut )
500  {
501  /* make room at the beginning of the array for forced cut */
502  pos = sepastore->nforcedcuts;
503  sepastore->cuts[sepastore->ncuts] = sepastore->cuts[pos];
504  sepastore->nforcedcuts++;
505  }
506  else
507  pos = sepastore->ncuts;
508 
509  sepastore->cuts[pos] = cut;
510  sepastore->ncuts++;
511 
512  /* check, if the row addition to separation storage events are tracked if so, issue ROWADDEDSEPA event */
513  if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWADDEDSEPA) != 0 )
514  {
515  SCIP_EVENT* event;
516 
517  SCIP_CALL( SCIPeventCreateRowAddedSepa(&event, blkmem, cut) );
518  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
519  }
520 
521  /* If the duals need to be collected, then the infeasible flag is set to FALSE. This ensures that the LP is solved */
522  if( set->lp_alwaysgetduals && sepastore->initiallp )
523  (*infeasible) = FALSE;
524 
525  return SCIP_OKAY;
526 }
527 
528 /** applies a lower bound change */
529 static
531  SCIP_SEPASTORE* sepastore, /**< separation storage */
532  BMS_BLKMEM* blkmem, /**< block memory */
533  SCIP_SET* set, /**< global SCIP settings */
534  SCIP_STAT* stat, /**< problem statistics */
535  SCIP_PROB* transprob, /**< transformed problem */
536  SCIP_PROB* origprob, /**< original problem */
537  SCIP_TREE* tree, /**< branch and bound tree */
538  SCIP_REOPT* reopt, /**< reoptimization data structure */
539  SCIP_LP* lp, /**< LP data */
540  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
541  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
542  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
543  SCIP_VAR* var, /**< problem variable */
544  SCIP_Real bound, /**< new lower bound of variable */
545  SCIP_Bool local, /**< is it a local bound change? (otherwise global) */
546  SCIP_Bool* applied, /**< pointer to store whether the domain change was applied */
547  SCIP_Bool* cutoff /**< pointer to store TRUE, if an infeasibility has been detected */
548  )
549 {
550  assert(sepastore != NULL);
551  assert(cutoff != NULL);
552  assert(applied != NULL);
553 
554  /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */
555  SCIPvarAdjustLb(var, set, &bound);
556 
557  if( local )
558  {
559  /* apply the local bound change or detect a cutoff */
560  if( SCIPsetIsGT(set, bound, SCIPvarGetLbLocal(var)) )
561  {
562  SCIPsetDebugMsg(set, " -> applying bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
564 
565  /* changing the lower bound to a value >= SCIPinfinity should result in a cutoff,
566  * since "infinite" values in solutions are reserved for another meaning
567  */
568  if( !SCIPsetIsInfinity(set, bound) && SCIPsetIsFeasLE(set, bound, SCIPvarGetUbLocal(var)) )
569  {
570  SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree,
571  reopt, lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_LOWER, FALSE) );
572  }
573  else
574  *cutoff = TRUE;
575 
576  *applied = TRUE;
577  }
578  else
579  {
580  SCIPsetDebugMsg(set, " -> ignoring bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
582  }
583  }
584  else
585  {
586  /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */
587  if( SCIPsetIsGT(set, bound, SCIPvarGetLbGlobal(var)) )
588  {
589  SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
591 
592  /* changing the lower bound to a value >= SCIPinfinity should result in a cutoff,
593  * since "infinite" values in solutions are reserved for another meaning
594  */
595  if( !SCIPsetIsInfinity(set, bound) && SCIPsetIsFeasLE(set, bound, SCIPvarGetUbGlobal(var)) )
596  {
597  SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt,
598  lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_LOWER, FALSE) );
599  }
600  else
601  {
602  /* we are done with solving since a global bound change is infeasible */
603  SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
604  *cutoff = TRUE;
605  }
606 
607  *applied = TRUE;
608  }
609  else
610  {
611  SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
613  }
614  }
615 
616  return SCIP_OKAY;
617 }
618 
619 /** applies an upper bound change */
620 static
622  SCIP_SEPASTORE* sepastore, /**< separation storage */
623  BMS_BLKMEM* blkmem, /**< block memory */
624  SCIP_SET* set, /**< global SCIP settings */
625  SCIP_STAT* stat, /**< problem statistics */
626  SCIP_PROB* transprob, /**< transformed problem */
627  SCIP_PROB* origprob, /**< original problem */
628  SCIP_TREE* tree, /**< branch and bound tree */
629  SCIP_REOPT* reopt, /**< reoptimization data structure */
630  SCIP_LP* lp, /**< LP data */
631  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
632  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
633  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
634  SCIP_VAR* var, /**< problem variable */
635  SCIP_Real bound, /**< new upper bound of variable */
636  SCIP_Bool local, /**< is it a local bound change? (otherwise global) */
637  SCIP_Bool* applied, /**< pointer to store whether the domain change was applied */
638  SCIP_Bool* cutoff /**< pointer to store TRUE, if an infeasibility has been detected */
639  )
640 {
641  assert(sepastore != NULL);
642  assert(cutoff != NULL);
643  assert(applied != NULL);
644 
645  /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */
646  SCIPvarAdjustUb(var, set, &bound);
647 
648  if( local )
649  {
650  /* apply the local bound change or detect a cutoff */
651  if( SCIPsetIsLT(set, bound, SCIPvarGetUbLocal(var)) )
652  {
653  SCIPsetDebugMsg(set, " -> applying bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
655 
656  /* changing the upper bound to a value <= -SCIPinfinity should result in a cutoff,
657  * since "infinite" values in solutions are reserved for another meaning
658  */
659  if( !SCIPsetIsInfinity(set, -bound) && SCIPsetIsFeasGE(set, bound, SCIPvarGetLbLocal(var)) )
660  {
661  SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree,
662  reopt, lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_UPPER, FALSE) );
663  }
664  else
665  *cutoff = TRUE;
666 
667  *applied = TRUE;
668  }
669  else
670  {
671  SCIPsetDebugMsg(set, " -> ignoring bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
673  }
674  }
675  else
676  {
677  /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */
678  if( SCIPsetIsLT(set, bound, SCIPvarGetUbGlobal(var)) )
679  {
680  SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
682 
683  /* changing the upper bound to a value <= -SCIPinfinity should result in a cutoff,
684  * since "infinite" values in solutions are reserved for another meaning
685  */
686  if( !SCIPsetIsInfinity(set, -bound) && SCIPsetIsFeasGE(set, bound, SCIPvarGetLbGlobal(var)) )
687  {
688  SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt,
689  lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_UPPER, FALSE) );
690  }
691  else
692  {
693  /* we are done with solving since a global bound change is infeasible */
694  SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
695  *cutoff = TRUE;
696  }
697 
698  *applied = TRUE;
699  }
700  else
701  {
702  SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
704  }
705  }
706 
707  return SCIP_OKAY;
708 }
709 
710 /** applies a cut that is a bound change directly as bound change instead of adding it as row to the LP */
711 static
713  SCIP_SEPASTORE* sepastore, /**< separation storage */
714  BMS_BLKMEM* blkmem, /**< block memory */
715  SCIP_SET* set, /**< global SCIP settings */
716  SCIP_STAT* stat, /**< problem statistics */
717  SCIP_PROB* transprob, /**< transformed problem */
718  SCIP_PROB* origprob, /**< original problem */
719  SCIP_TREE* tree, /**< branch and bound tree */
720  SCIP_REOPT* reopt, /**< reoptimization data structure */
721  SCIP_LP* lp, /**< LP data */
722  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
723  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
724  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
725  SCIP_ROW* cut, /**< cut with a single variable */
726  SCIP_Bool* applied, /**< pointer to store whether the domain change was applied */
727  SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */
728  )
729 {
730  SCIP_COL** cols;
731  SCIP_Real* vals;
732  SCIP_VAR* var;
733  SCIP_Real lhs;
734  SCIP_Real rhs;
735  SCIP_Bool local;
736 
737  assert(sepastore != NULL);
738  assert(!SCIProwIsModifiable(cut));
739  assert(SCIProwGetNNonz(cut) == 1);
740  assert(cutoff != NULL);
741  assert(applied != NULL);
742 
743  *applied = FALSE;
744  *cutoff = FALSE;
745 
746  /* get the single variable and its coefficient of the cut */
747  cols = SCIProwGetCols(cut);
748  assert(cols != NULL);
749 
750  var = SCIPcolGetVar(cols[0]);
751  vals = SCIProwGetVals(cut);
752  assert(vals != NULL);
753  assert(!SCIPsetIsZero(set, vals[0]));
754 
755  /* if the coefficient is nearly zero, we better ignore this cut for numerical reasons */
756  if( SCIPsetIsFeasZero(set, vals[0]) )
757  return SCIP_OKAY;
758 
759  local = SCIProwIsLocal(cut);
760 
761  /* get the left hand side of the cut and convert it to a bound */
762  lhs = SCIProwGetLhs(cut);
763  if( !SCIPsetIsInfinity(set, -lhs) )
764  {
765  lhs -= SCIProwGetConstant(cut);
766  if( vals[0] > 0.0 )
767  {
768  /* coefficient is positive -> lhs corresponds to lower bound */
769  SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
770  cliquetable, var, lhs/vals[0], local, applied, cutoff) );
771  }
772  else
773  {
774  /* coefficient is negative -> lhs corresponds to upper bound */
775  SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
776  cliquetable, var, lhs/vals[0], local, applied, cutoff) );
777  }
778  }
779 
780  /* get the right hand side of the cut and convert it to a bound */
781  rhs = SCIProwGetRhs(cut);
782  if( !SCIPsetIsInfinity(set, rhs) )
783  {
784  rhs -= SCIProwGetConstant(cut);
785  if( vals[0] > 0.0 )
786  {
787  /* coefficient is positive -> rhs corresponds to upper bound */
788  SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
789  cliquetable, var, rhs/vals[0], local, applied, cutoff) );
790  }
791  else
792  {
793  /* coefficient is negative -> rhs corresponds to lower bound */
794  SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
795  cliquetable, var, rhs/vals[0], local, applied, cutoff) );
796  }
797  }
798 
799  /* count the bound change as applied cut */
800  if( *applied && !sepastore->initiallp )
801  sepastore->ncutsapplied++;
802 
803  return SCIP_OKAY;
804 }
805 
806 /** applies the given cut to the LP and updates the orthogonalities and scores of remaining cuts */
807 static
809  SCIP_SEPASTORE* sepastore, /**< separation storage */
810  BMS_BLKMEM* blkmem, /**< block memory */
811  SCIP_SET* set, /**< global SCIP settings */
812  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
813  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
814  SCIP_LP* lp, /**< LP data */
815  SCIP_ROW* cut, /**< cut to apply to the LP */
816  int depth, /**< depth of current node */
817  int* ncutsapplied /**< pointer to count the number of applied cuts */
818  )
819 {
820  assert(sepastore != NULL);
821  assert(ncutsapplied != NULL);
822 
823  /* a row could have been added twice to the separation store; add it only once! */
824  if( !SCIProwIsInLP(cut) )
825  {
826  /* add cut to the LP and capture it */
827  SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, cut, depth) );
828 
829  /* update statistics -> only if we are not in the initial lp (cuts are only counted if added during run) */
830  if( !sepastore->initiallp )
831  {
832  sepastore->ncutsapplied++;
833 
834  /* increase count of applied cuts for origins of row */
835  switch ( cut->origintype )
836  {
838  assert( cut->origin != NULL );
840  break;
842  assert( cut->origin != NULL );
844  break;
846  assert( cut->origin != NULL );
848  break;
851  /* do nothing - cannot update statistics */
852  break;
853  default:
854  SCIPerrorMessage("unkown type of row origin.\n");
855  return SCIP_INVALIDDATA;
856  }
857  }
858 
859  (*ncutsapplied)++;
860  }
861 
862  return SCIP_OKAY;
863 }
864 
865 /** adds cuts to the LP and clears separation storage */
867  SCIP_SEPASTORE* sepastore, /**< separation storage */
868  BMS_BLKMEM* blkmem, /**< block memory */
869  SCIP_SET* set, /**< global SCIP settings */
870  SCIP_STAT* stat, /**< problem statistics */
871  SCIP_PROB* transprob, /**< transformed problem */
872  SCIP_PROB* origprob, /**< original problem */
873  SCIP_TREE* tree, /**< branch and bound tree */
874  SCIP_REOPT* reopt, /**< reoptimization data structure */
875  SCIP_LP* lp, /**< LP data */
876  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
877  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
878  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
879  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
880  SCIP_Bool root, /**< are we at the root node? */
881  SCIP_EFFICIACYCHOICE efficiacychoice, /**< type of solution to base efficiacy computation on */
882  SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */
883  )
884 {
885  SCIP_NODE* node;
886  int maxsepacuts;
887  int ncutsapplied;
888  int nselectedcuts;
889  int depth;
890  int i;
891 
892  assert(sepastore != NULL);
893  assert(set != NULL);
894  assert(tree != NULL);
895  assert(lp != NULL);
896  assert(cutoff != NULL);
897 
898  SCIP_UNUSED(efficiacychoice);
899 
900  SCIPsetDebugMsg(set, "selecting from %d cuts\n", sepastore->ncuts);
901 
902  /* get maximal number of cuts to add to the LP */
903  maxsepacuts = SCIPsetGetSepaMaxcuts(set, root);
904 
905  /* if all cuts are forced cuts, no selection is required */
906  if( sepastore->nforcedcuts >= MIN(sepastore->ncuts, maxsepacuts) )
907  {
908  nselectedcuts = sepastore->nforcedcuts;
909  }
910  else
911  {
912  /* call cut selection algorithms */
913  nselectedcuts = 0;
914  SCIP_CALL( SCIPcutselsSelect(set, sepastore->cuts, sepastore->ncuts, sepastore->nforcedcuts, root, maxsepacuts,
915  &nselectedcuts) );
916  assert(nselectedcuts + sepastore->nforcedcuts <= maxsepacuts);
917  nselectedcuts += sepastore->nforcedcuts;
918  }
919 
920  /*
921  * apply all selected cuts
922  */
923  ncutsapplied = 0;
924  *cutoff = FALSE;
925 
926  node = SCIPtreeGetCurrentNode(tree);
927  assert(node != NULL);
928 
929  /* get depth of current node */
930  depth = SCIPnodeGetDepth(node);
931 
932  for( i = 0; i < nselectedcuts && !(*cutoff); i++ )
933  {
934  SCIP_ROW* cut;
935 
936  cut = sepastore->cuts[i];
937 
938  if( i < sepastore->nforcedcuts || SCIPsetIsFeasPositive(set, SCIProwGetLPEfficacy(cut, set, stat, lp)) )
939  {
940  SCIP_Bool applied = FALSE;
941 
942  /* if the cut is a bound change (i.e. a row with only one variable), add it as bound change instead of LP row */
943  if( !SCIProwIsModifiable(cut) && SCIProwGetNNonz(cut) == 1 )
944  {
945  SCIPsetDebugMsg(set, " -> applying forced cut <%s> as boundchange\n", SCIProwGetName(cut));
946  SCIP_CALL( sepastoreApplyBdchg(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
947  eventqueue, cliquetable, cut, &applied, cutoff) );
948 
949  assert(applied || !sepastoreIsBdchgApplicable(set, cut));
950  }
951 
952  if( !applied )
953  {
954  /* add cut to the LP and update orthogonalities */
955  SCIPsetDebugMsg(set, " -> applying%s cut <%s>\n", (i < sepastore->nforcedcuts) ? " forced" : "", SCIProwGetName(cut));
956  /*SCIPdebug( SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
957  SCIP_CALL( sepastoreApplyCut(sepastore, blkmem, set, eventqueue, eventfilter, lp, cut, depth, &ncutsapplied) );
958  }
959  }
960  }
961 
962  /* clear the separation storage and reset statistics for separation round */
963  SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
964 
965  return SCIP_OKAY;
966 }
967 
968 /** clears the separation storage without adding the cuts to the LP */
970  SCIP_SEPASTORE* sepastore, /**< separation storage */
971  BMS_BLKMEM* blkmem, /**< block memory */
972  SCIP_SET* set, /**< global SCIP settings */
973  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
974  SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
975  SCIP_LP* lp /**< LP data */
976  )
977 {
978  int c;
979 
980  assert(sepastore != NULL);
981 
982  SCIPsetDebugMsg(set, "clearing %d cuts\n", sepastore->ncuts);
983 
984  /* release cuts */
985  for( c = 0; c < sepastore->ncuts; ++c )
986  {
987  /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
988  if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 )
989  {
990  SCIP_EVENT* event;
991 
992  SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[c]) );
993  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
994  }
995 
996  SCIP_CALL( SCIProwRelease(&sepastore->cuts[c], blkmem, set, lp) );
997  }
998 
999  /* reset counters */
1000  sepastore->ncuts = 0;
1001  sepastore->nforcedcuts = 0;
1002  sepastore->ncutsfoundround = 0;
1003 
1004  /* if we have just finished the initial LP construction, free the (potentially large) cuts array */
1005  if( sepastore->initiallp )
1006  {
1007  BMSfreeMemoryArrayNull(&sepastore->cuts);
1008  sepastore->cutssize = 0;
1009  }
1010 
1011  return SCIP_OKAY;
1012 }
1013 
1014 /** removes cuts that are inefficacious w.r.t. the current LP solution from separation storage without adding the cuts to the LP */
1016  SCIP_SEPASTORE* sepastore, /**< separation storage */
1017  BMS_BLKMEM* blkmem, /**< block memory */
1018  SCIP_SET* set, /**< global SCIP settings */
1019  SCIP_STAT* stat, /**< problem statistics data */
1020  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1021  SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
1022  SCIP_LP* lp, /**< LP data */
1023  SCIP_Bool root, /**< are we at the root node? */
1024  SCIP_EFFICIACYCHOICE efficiacychoice /**< type of solution to base efficiacy computation on */
1025  )
1026 {
1027  int cnt = 0;
1028  int c;
1029 
1030  assert( sepastore != NULL );
1031 
1032  /* check non-forced cuts only */
1033  c = sepastore->nforcedcuts;
1034  while( c < sepastore->ncuts )
1035  {
1036  SCIP_Real cutefficacy;
1037 
1038  /* calculate cut's efficacy */
1039  switch ( efficiacychoice )
1040  {
1042  cutefficacy = SCIProwGetLPEfficacy(sepastore->cuts[c], set, stat, lp);
1043  break;
1045  cutefficacy = SCIProwGetRelaxEfficacy(sepastore->cuts[c], set, stat);
1046  break;
1048  cutefficacy = SCIProwGetNLPEfficacy(sepastore->cuts[c], set, stat);
1049  break;
1050  default:
1051  SCIPerrorMessage("Invalid efficiacy choice.\n");
1052  return SCIP_INVALIDCALL;
1053  }
1054 
1055  if( !SCIPsetIsEfficacious(set, root, cutefficacy) )
1056  {
1057  SCIP_CALL( sepastoreDelCut(sepastore, blkmem, set, eventqueue, eventfilter, lp, c) );
1058  ++cnt;
1059  }
1060  else
1061  ++c;
1062  }
1063  SCIPsetDebugMsg(set, "removed %d non-efficacious cuts\n", cnt);
1064 
1065  return SCIP_OKAY;
1066 }
1067 
1068 /** indicates whether a cut is applicable
1069  *
1070  * A cut is applicable if it is modifiable, not a bound change, or a bound change that changes bounds by at least epsilon.
1071  */
1073  SCIP_SET* set, /**< global SCIP settings */
1074  SCIP_ROW* cut /**< cut to check */
1075  )
1076 {
1077  return SCIProwIsModifiable(cut) || SCIProwGetNNonz(cut) != 1 || sepastoreIsBdchgApplicable(set, cut);
1078 }
1079 
1080 /** get cuts in the separation storage */
1082  SCIP_SEPASTORE* sepastore /**< separation storage */
1083  )
1084 {
1085  assert(sepastore != NULL);
1086 
1087  return sepastore->cuts;
1088 }
1089 
1090 /** get number of cuts in the separation storage */
1092  SCIP_SEPASTORE* sepastore /**< separation storage */
1093  )
1094 {
1095  assert(sepastore != NULL);
1096 
1097  return sepastore->ncuts;
1098 }
1099 
1100 /** get total number of cuts found so far */
1102  SCIP_SEPASTORE* sepastore /**< separation storage */
1103  )
1104 {
1105  assert(sepastore != NULL);
1106 
1107  return sepastore->ncutsfound;
1108 }
1109 
1110 /** get number of cuts found so far in current separation round */
1112  SCIP_SEPASTORE* sepastore /**< separation storage */
1113  )
1114 {
1115  assert(sepastore != NULL);
1116 
1117  return sepastore->ncutsfoundround;
1118 }
1119 
1120 /** get total number of cuts applied to the LPs */
1122  SCIP_SEPASTORE* sepastore /**< separation storage */
1123  )
1124 {
1125  assert(sepastore != NULL);
1126 
1127  return sepastore->ncutsapplied;
1128 }
internal methods for separators
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6200
static SCIP_RETCODE sepastoreApplyLb(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real bound, SCIP_Bool local, SCIP_Bool *applied, SCIP_Bool *cutoff)
Definition: sepastore.c:530
internal methods for managing events
SCIP_RETCODE SCIPcutselsSelect(SCIP_SET *set, SCIP_ROW **cuts, int ncuts, int nforcedcuts, SCIP_Bool root, int maxnselectedcuts, int *nselectedcuts)
Definition: cutsel.c:152
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6258
SCIP_Bool SCIPsetIsFeasZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6708
void * origin
Definition: struct_lp.h:216
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:141
internal methods for branch and bound tree
unsigned int SCIPsetInitializeRandomSeed(SCIP_SET *set, unsigned int initialseedvalue)
Definition: set.c:7394
enum SCIP_Efficiacychoice SCIP_EFFICIACYCHOICE
static SCIP_RETCODE sepastoreApplyBdchg(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_ROW *cut, SCIP_Bool *applied, SCIP_Bool *cutoff)
Definition: sepastore.c:712
SCIP_RETCODE SCIPeventqueueAdd(SCIP_EVENTQUEUE *eventqueue, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter, SCIP_EVENT **event)
Definition: event.c:2231
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
void SCIPsepaIncNAppliedCuts(SCIP_SEPA *sepa)
Definition: sepa.c:887
unsigned int origintype
Definition: struct_lp.h:255
SCIP_ROW ** SCIPsepastoreGetCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1081
static long bound
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17146
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
void SCIProwCapture(SCIP_ROW *row)
Definition: lp.c:5332
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17284
void SCIPsepastoreStartForceCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:145
int SCIPsepastoreGetNCutsApplied(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1121
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17225
#define FALSE
Definition: def.h:87
methods for the aggregation rows
datastructures for managing events
internal methods for cut selectors
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6312
#define TRUE
Definition: def.h:86
#define SCIPdebugCheckRow(set, row)
Definition: debug.h:266
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Real SCIProwGetLPEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:6801
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5779
#define SCIP_UNUSED(x)
Definition: def.h:438
SCIP_Real SCIProwGetNLPEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6957
static SCIP_Bool sepastoreIsCutRedundant(SCIP_SEPASTORE *sepastore, SCIP_SET *set, SCIP_STAT *stat, SCIP_ROW *cut)
Definition: sepastore.c:168
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7442
#define BMSfreeMemory(ptr)
Definition: memory.h:138
void SCIPvarAdjustLb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *lb)
Definition: var.c:6513
internal methods for LP management
Definition: heur_padm.c:123
int SCIPsetGetSepaMaxcuts(SCIP_SET *set, SCIP_Bool root)
Definition: set.c:5918
SCIP_ROW ** cuts
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17456
SCIP_Bool SCIPsetIsEfficacious(SCIP_SET *set, SCIP_Bool root, SCIP_Real efficacy)
Definition: set.c:7062
SCIP_RETCODE SCIPnodeCutoff(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, BMS_BLKMEM *blkmem)
Definition: tree.c:1179
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_RETCODE SCIPeventCreateRowDeletedSepa(SCIP_EVENT **event, BMS_BLKMEM *blkmem, SCIP_ROW *row)
Definition: event.c:866
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6240
SCIP_Bool SCIPsepastoreIsCutApplicable(SCIP_SET *set, SCIP_ROW *cut)
Definition: sepastore.c:1072
#define SCIP_EVENTTYPE_ROWADDEDSEPA
Definition: type_event.h:99
static SCIP_RETCODE sepastoreApplyCut(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_ROW *cut, int depth, int *ncutsapplied)
Definition: sepastore.c:808
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPsepastoreCreate(SCIP_SEPASTORE **sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set)
Definition: sepastore.c:78
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17334
SCIP_EVENTTYPE eventmask
Definition: struct_event.h:189
SCIP_RETCODE SCIProwChgLocal(SCIP_ROW *row, SCIP_Bool local)
Definition: lp.c:5723
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1091
SCIP_RETCODE SCIPsepastoreRemoveInefficaciousCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_Bool root, SCIP_EFFICIACYCHOICE efficiacychoice)
Definition: sepastore.c:1015
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
SCIP_RETCODE SCIPlpAddRow(SCIP_LP *lp, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_ROW *row, int depth)
Definition: lp.c:9500
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem)
Definition: misc.c:9987
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Bool SCIPsetIsFeasGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6686
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17235
internal methods for storing separated cuts
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17344
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6642
static SCIP_RETCODE sepastoreDelCut(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, int pos)
Definition: sepastore.c:368
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17171
SCIP_RETCODE SCIProwRelease(SCIP_ROW **row, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: lp.c:5345
data structures and methods for collecting reoptimization information
internal methods for problem variables
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17181
#define SCIP_Bool
Definition: def.h:84
static SCIP_Bool sepastoreIsCutRedundantOrInfeasible(SCIP_SEPASTORE *sepastore, SCIP_SET *set, SCIP_STAT *stat, SCIP_ROW *cut, SCIP_Bool *infeasible)
Definition: sepastore.c:207
static SCIP_RETCODE sepastoreApplyUb(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real bound, SCIP_Bool local, SCIP_Bool *applied, SCIP_Bool *cutoff)
Definition: sepastore.c:621
#define MAX(x, y)
Definition: tclique_def.h:83
void SCIPconshdlrIncNAppliedCuts(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4866
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8097
methods for debugging
#define SCIPsetDebugMsg
Definition: set.h:1755
#define SCIP_EVENTTYPE_ROWDELETEDSEPA
Definition: type_event.h:100
static SCIP_RETCODE sepastoreEnsureCutsMem(SCIP_SEPASTORE *sepastore, SCIP_SET *set, int num)
Definition: sepastore.c:55
static SCIP_Bool sepastoreIsBdchgApplicable(SCIP_SET *set, SCIP_ROW *cut)
Definition: sepastore.c:264
void SCIPsepastoreEndInitialLP(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:133
SCIP_Real SCIProwGetRelaxEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6917
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6620
void SCIPsepastoreStartInitialLP(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:121
SCIP_Real SCIProwGetMaxActivity(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6612
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17191
int SCIPsepastoreGetNCutsFound(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1101
SCIP_Real SCIProwGetMinActivity(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6591
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16975
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
Definition: tree.c:8442
SCIP_RETCODE SCIPnodeAddBoundchg(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool probingchange)
Definition: tree.c:2078
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8375
SCIP_RETCODE SCIPsepastoreApplyCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool root, SCIP_EFFICIACYCHOICE efficiacychoice, SCIP_Bool *cutoff)
Definition: sepastore.c:866
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6276
#define SCIP_Real
Definition: def.h:177
internal methods for problem statistics
SCIP_Bool SCIPsetIsFeasPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6719
int SCIPsepastoreGetNCutsFoundRound(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1111
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:9971
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:120
internal methods for constraints and constraint handlers
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6664
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
void SCIPvarAdjustUb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *ub)
Definition: var.c:6530
SCIP_Bool initiallp
datastructures for storing conflicts
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:430
SCIP_RETCODE SCIPsepastoreClearCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp)
Definition: sepastore.c:969
#define SCIP_ALLOC(x)
Definition: def.h:395
SCIP_Bool forcecuts
void SCIPsepastoreEndForceCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:156
SCIP_RETCODE SCIPsepastoreFree(SCIP_SEPASTORE **sepastore, BMS_BLKMEM *blkmem)
Definition: sepastore.c:104
SCIP_RETCODE SCIPsepastoreAddCut(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool root, SCIP_Bool *infeasible)
Definition: sepastore.c:402
SCIP callable library.
SCIP_Bool SCIPsetIsFeasNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6730
SCIP_RETCODE SCIPeventCreateRowAddedSepa(SCIP_EVENT **event, BMS_BLKMEM *blkmem, SCIP_ROW *row)
Definition: event.c:847