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