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/struct_event.h"
43 #include "scip/struct_sepastore.h"
44 #include "scip/misc.h"
45 
46 
47 
48 /*
49  * dynamic memory arrays
50  */
51 
52 /** resizes cuts and score arrays to be able to store at least num entries */
53 static
55  SCIP_SEPASTORE* sepastore, /**< separation storage */
56  SCIP_SET* set, /**< global SCIP settings */
57  int num /**< minimal number of slots in array */
58  )
59 {
60  assert(sepastore != NULL);
61  assert(set != NULL);
62 
63  if( num > sepastore->cutssize )
64  {
65  int newsize;
66 
67  newsize = SCIPsetCalcMemGrowSize(set, num);
68  SCIP_ALLOC( BMSreallocMemoryArray(&sepastore->cuts, newsize) );
69  sepastore->cutssize = newsize;
70  }
71  assert(num <= sepastore->cutssize);
72 
73  return SCIP_OKAY;
74 }
75 
76 /** creates separation storage */
78  SCIP_SEPASTORE** sepastore, /**< pointer to store separation storage */
79  BMS_BLKMEM* blkmem, /**< block memory */
80  SCIP_SET* set /**< global SCIP settings */
81  )
82 {
83  assert(sepastore != NULL);
84 
85  SCIP_ALLOC( BMSallocMemory(sepastore) );
86 
87  (*sepastore)->cuts = NULL;
88  (*sepastore)->cutssize = 0;
89  (*sepastore)->ncuts = 0;
90  (*sepastore)->nforcedcuts = 0;
91  (*sepastore)->ncutsfound = 0;
92  (*sepastore)->ncutsfoundround = 0;
93  (*sepastore)->ncutsapplied = 0;
94  (*sepastore)->initiallp = FALSE;
95  (*sepastore)->forcecuts = FALSE;
96 
97  SCIP_CALL( SCIPrandomCreate(&(*sepastore)->randnumgen, blkmem, (unsigned int)SCIPsetInitializeRandomSeed(set, 0x5EED)) );
98 
99  return SCIP_OKAY;
100 }
101 
102 /** frees separation storage */
104  SCIP_SEPASTORE** sepastore, /**< pointer to store separation storage */
105  BMS_BLKMEM* blkmem /**< block memory */
106  )
107 {
108  assert(sepastore != NULL);
109  assert(*sepastore != NULL);
110  assert((*sepastore)->ncuts == 0);
111 
112  SCIPrandomFree(&(*sepastore)->randnumgen, blkmem);
113  BMSfreeMemoryArrayNull(&(*sepastore)->cuts);
114  BMSfreeMemory(sepastore);
115 
116  return SCIP_OKAY;
117 }
118 
119 /** informs separation storage that the setup of the initial LP starts now */
121  SCIP_SEPASTORE* sepastore /**< separation storage */
122  )
123 {
124  assert(sepastore != NULL);
125  assert(!sepastore->initiallp);
126  assert(sepastore->ncuts == 0);
127 
128  sepastore->initiallp = TRUE;
129 }
130 
131 /** informs separation storage that the setup of the initial LP is now finished */
133  SCIP_SEPASTORE* sepastore /**< separation storage */
134  )
135 {
136  assert(sepastore != NULL);
137  assert(sepastore->initiallp);
138  assert(sepastore->ncuts == 0);
139 
140  sepastore->initiallp = FALSE;
141 }
142 
143 /** informs separation storage that the following cuts should be used in any case */
145  SCIP_SEPASTORE* sepastore /**< separation storage */
146  )
147 {
148  assert(sepastore != NULL);
149  assert(!sepastore->forcecuts);
150 
151  sepastore->forcecuts = TRUE;
152 }
153 
154 /** informs separation storage that the following cuts should no longer be used in any case */
156  SCIP_SEPASTORE* sepastore /**< separation storage */
157  )
158 {
159  assert(sepastore != NULL);
160  assert(sepastore->forcecuts);
161 
162  sepastore->forcecuts = FALSE;
163 }
164 
165 /** checks cut for redundancy due to activity bounds */
166 static
168  SCIP_SEPASTORE* sepastore, /**< separation storage */
169  SCIP_SET* set, /**< global SCIP settings */
170  SCIP_STAT* stat, /**< problem statistics data */
171  SCIP_ROW* cut /**< separated cut */
172  )
173 {
174  SCIP_Real minactivity;
175  SCIP_Real maxactivity;
176  SCIP_Real lhs;
177  SCIP_Real rhs;
178 
179  assert(sepastore != NULL);
180  assert(cut != NULL);
181 
182  /* modifiable cuts cannot be declared redundant, since we don't know all coefficients */
183  if( SCIProwIsModifiable(cut) )
184  return FALSE;
185 
186  /* check for activity redundancy */
187  lhs = SCIProwGetLhs(cut);
188  rhs = SCIProwGetRhs(cut);
189  minactivity = SCIProwGetMinActivity(cut, set, stat);
190  maxactivity = SCIProwGetMaxActivity(cut, set, stat);
191 
192  if( (SCIPsetIsInfinity(set, -lhs) || SCIPsetIsLE(set, lhs, minactivity)) &&
193  (SCIPsetIsInfinity(set, rhs) || SCIPsetIsLE(set, maxactivity, rhs)) )
194  {
195  SCIPsetDebugMsg(set, "ignoring activity redundant cut <%s> (sides=[%g,%g], act=[%g,%g])\n",
196  SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
197  /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
198  return TRUE;
199  }
200 
201  return FALSE;
202 }
203 
204 /** checks cut for redundancy or infeasibility due to activity bounds */
205 static
207  SCIP_SEPASTORE* sepastore, /**< separation storage */
208  SCIP_SET* set, /**< global SCIP settings */
209  SCIP_STAT* stat, /**< problem statistics data */
210  SCIP_ROW* cut, /**< separated cut */
211  SCIP_Bool* infeasible /**< pointer to store whether the cut has been detected to be infeasible */
212  )
213 {
214  SCIP_Real minactivity;
215  SCIP_Real maxactivity;
216  SCIP_Real lhs;
217  SCIP_Real rhs;
218 
219  assert(sepastore != NULL);
220  assert(cut != NULL);
221  assert(infeasible != NULL);
222 
223  *infeasible = FALSE;
224 
225  /* modifiable cuts cannot be declared redundant or infeasible, since we don't know all coefficients */
226  if( SCIProwIsModifiable(cut) )
227  return FALSE;
228 
229  /* check for activity redundancy */
230  lhs = SCIProwGetLhs(cut);
231  rhs = SCIProwGetRhs(cut);
232  minactivity = SCIProwGetMinActivity(cut, set, stat);
233  maxactivity = SCIProwGetMaxActivity(cut, set, stat);
234 
235  if( (SCIPsetIsInfinity(set, -lhs) || SCIPsetIsLE(set, lhs, minactivity)) &&
236  (SCIPsetIsInfinity(set, rhs) || SCIPsetIsLE(set, maxactivity, rhs)) )
237  {
238  SCIPsetDebugMsg(set, "ignoring activity redundant cut <%s> (sides=[%g,%g], act=[%g,%g])\n",
239  SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
240  /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
241  return TRUE;
242  }
243 
244  if( (!SCIPsetIsInfinity(set, rhs) && SCIPsetIsFeasGT(set, minactivity, rhs)) ||
245  (!SCIPsetIsInfinity(set, -lhs) && SCIPsetIsFeasLT(set, maxactivity, lhs) ))
246  {
247  SCIPsetDebugMsg(set, "cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n",
248  SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
249  /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
250  *infeasible = TRUE;
251  return TRUE;
252  }
253 
254  return FALSE;
255 }
256 
257 /** checks whether a cut with only one variable can be applied as boundchange
258  *
259  * This is the case if the bound change would prove infeasibility (w.r.t feastol), or if the new bound is at least
260  * epsilon better than the old bound. In the latter case, also the opposite bound has to be taken into account.
261  */
262 static
264  SCIP_SET* set, /**< global SCIP settings */
265  SCIP_ROW* cut /**< cut with a single variable */
266  )
267 {
268  SCIP_COL** cols;
269  SCIP_Real* vals;
270  SCIP_VAR* var;
271  SCIP_Real lhs;
272  SCIP_Real rhs;
273  SCIP_Bool local;
274  SCIP_Real oldlb;
275  SCIP_Real oldub;
276 
277  assert(set != NULL);
278  assert(cut != NULL);
279  assert(!SCIProwIsModifiable(cut));
280  assert(SCIProwGetNNonz(cut) == 1);
281 
282  /* get the single variable and its coefficient of the cut */
283  cols = SCIProwGetCols(cut);
284  assert(cols != NULL);
285 
286  var = SCIPcolGetVar(cols[0]);
287  vals = SCIProwGetVals(cut);
288  assert(vals != NULL);
289  assert(!SCIPsetIsZero(set, vals[0]));
290 
291  /* if the coefficient is nearly zero, we better ignore this cut for numerical reasons */
292  if( SCIPsetIsFeasZero(set, vals[0]) )
293  return FALSE;
294 
295  local = SCIProwIsLocal(cut);
296 
297  oldlb = local ? SCIPvarGetLbLocal(var) : SCIPvarGetLbGlobal(var);
298  oldub = local ? SCIPvarGetUbLocal(var) : SCIPvarGetUbGlobal(var);
299 
300  /* get the left hand side of the cut and convert it to a bound */
301  lhs = SCIProwGetLhs(cut);
302  if( !SCIPsetIsInfinity(set, -lhs) )
303  {
304  lhs -= SCIProwGetConstant(cut);
305  if( vals[0] > 0.0 )
306  {
307  /* coefficient is positive -> lhs corresponds to lower bound */
308  SCIP_Real newlb;
309 
310  newlb = lhs/vals[0];
311  SCIPvarAdjustLb(var, set, &newlb);
312 
313  /* bound changes that improve the bound sufficiently are applicable */
314  if( SCIPsetIsFeasGT(set, newlb, oldub) || SCIPsetIsGT(set, MIN(newlb, oldub), oldlb) )
315  return TRUE;
316  }
317  else
318  {
319  /* coefficient is negative -> lhs corresponds to upper bound */
320  SCIP_Real newub;
321 
322  newub = lhs/vals[0];
323  SCIPvarAdjustUb(var, set, &newub);
324 
325  /* bound changes that improve the bound sufficiently are applicable */
326  if( SCIPsetIsFeasLT(set, newub, oldlb) || SCIPsetIsLT(set, MAX(newub, oldlb), oldub) )
327  return TRUE;
328  }
329  }
330 
331  /* get the right hand side of the cut and convert it to a bound */
332  rhs = SCIProwGetRhs(cut);
333  if( !SCIPsetIsInfinity(set, rhs) )
334  {
335  rhs -= SCIProwGetConstant(cut);
336  if( vals[0] > 0.0 )
337  {
338  /* coefficient is positive -> rhs corresponds to upper bound */
339  SCIP_Real newub;
340 
341  newub = rhs/vals[0];
342  SCIPvarAdjustUb(var, set, &newub);
343 
344  /* bound changes that improve the bound sufficiently are applicable */
345  if( SCIPsetIsFeasLT(set, newub, oldlb) || SCIPsetIsLT(set, MAX(newub, oldlb), oldub) )
346  return TRUE;
347  }
348  else
349  {
350  /* coefficient is negative -> rhs corresponds to lower bound */
351  SCIP_Real newlb;
352 
353  newlb = rhs/vals[0];
354  SCIPvarAdjustLb(var, set, &newlb);
355 
356  /* bound changes that improve the bound sufficiently are applicable */
357  if( SCIPsetIsFeasGT(set, newlb, oldub) || SCIPsetIsGT(set, MIN(newlb, oldub), oldlb) )
358  return TRUE;
359  }
360  }
361 
362  return FALSE;
363 }
364 
365 /** removes a non-forced cut from the separation storage */
366 static
368  SCIP_SEPASTORE* sepastore, /**< separation storage */
369  BMS_BLKMEM* blkmem, /**< block memory */
370  SCIP_SET* set, /**< global SCIP settings */
371  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
372  SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
373  SCIP_LP* lp, /**< LP data */
374  int pos /**< position of cut to delete */
375  )
376 {
377  assert(sepastore != NULL);
378  assert(sepastore->cuts != NULL);
379  assert(sepastore->nforcedcuts <= pos && pos < sepastore->ncuts);
380 
381  /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
382  if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 )
383  {
384  SCIP_EVENT* event;
385 
386  SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[pos]) );
387  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
388  }
389 
390  /* release the row */
391  SCIP_CALL( SCIProwRelease(&sepastore->cuts[pos], blkmem, set, lp) );
392 
393  /* move last cut to the empty position */
394  sepastore->cuts[pos] = sepastore->cuts[sepastore->ncuts-1];
395  sepastore->ncuts--;
396 
397  return SCIP_OKAY;
398 }
399 
400 /** adds cut to separation storage and captures it */
402  SCIP_SEPASTORE* sepastore, /**< separation storage */
403  BMS_BLKMEM* blkmem, /**< block memory */
404  SCIP_SET* set, /**< global SCIP settings */
405  SCIP_STAT* stat, /**< problem statistics data */
406  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
407  SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
408  SCIP_LP* lp, /**< LP data */
409  SCIP_ROW* cut, /**< separated cut */
410  SCIP_Bool forcecut, /**< should the cut be forced to enter the LP? */
411  SCIP_Bool root, /**< are we at the root node? */
412  SCIP_Bool* infeasible /**< pointer to store whether the cut is infeasible */
413  )
414 {
415  SCIP_Bool redundant;
416  int pos;
417 
418  assert(sepastore != NULL);
419  assert(sepastore->nforcedcuts <= sepastore->ncuts);
420  assert(set != NULL);
421  assert(cut != NULL);
422  assert(!SCIPsetIsInfinity(set, -SCIProwGetLhs(cut)) || !SCIPsetIsInfinity(set, SCIProwGetRhs(cut)));
423  assert(eventqueue != NULL);
424  assert(eventfilter != NULL);
425 
426  /* debug: check cut for feasibility */
427  SCIP_CALL( SCIPdebugCheckRow(set, cut) ); /*lint !e506 !e774*/
428 
429  /* update statistics of total number of found cuts */
430  if( !sepastore->initiallp )
431  {
432  sepastore->ncutsfound++;
433  sepastore->ncutsfoundround++;
434  }
435 
436  /* the cut will be forced to enter the LP if the dual must be collected and the initial LP is being constructed */
437  forcecut = forcecut || (set->lp_alwaysgetduals && sepastore->initiallp);
438 
439  /* in the root node, every local cut is a global cut, and global cuts are nicer in many ways ... */
440  if( root && SCIProwIsLocal(cut) )
441  {
442  SCIPsetDebugMsg(set, "change local flag of cut <%s> to FALSE due to addition in root node\n", SCIProwGetName(cut));
443 
445 
446  assert(!SCIProwIsLocal(cut));
447  }
448 
449  /* check cut for redundancy or infeasibility */
450  redundant = sepastoreIsCutRedundantOrInfeasible(sepastore, set, stat, cut, infeasible);
451  /* Note that we add infeasible rows in any case, since we cannot be sure whether the return values are handled
452  * correctly. In this way, the LP becomes infeasible. */
453 
454  /* in each separation round, make sure that at least one (even redundant) cut enters the LP to avoid cycling */
455  if( !forcecut && sepastore->ncuts > 0 && redundant )
456  return SCIP_OKAY;
457 
458  /* if only one cut is currently present in sepastore, it could be redundant; in this case, it can now be removed
459  * again, because now a non redundant cut enters the sepastore */
460  if( sepastore->ncuts == 1 && sepastoreIsCutRedundant(sepastore, set, stat, sepastore->cuts[0]) )
461  {
462  /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
463  if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 )
464  {
465  SCIP_EVENT* event;
466 
467  SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[0]) );
468  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
469  }
470 
471  SCIP_CALL( SCIProwRelease(&sepastore->cuts[0], blkmem, set, lp) );
472  sepastore->ncuts = 0;
473  sepastore->nforcedcuts = 0;
474  }
475 
476  /* a cut is forced to enter the LP if
477  * - we construct the initial LP, or
478  * - it has infinite score factor, or
479  * - it is a bound change that can be applied
480  * if it is a non-forced cut and no cuts should be added, abort
481  */
482  forcecut = forcecut || sepastore->initiallp || sepastore->forcecuts || (!SCIProwIsModifiable(cut) && SCIProwGetNNonz(cut) == 1 && sepastoreIsBdchgApplicable(set, cut));
483  if( !forcecut && SCIPsetGetSepaMaxcuts(set, root) == 0 )
484  return SCIP_OKAY;
485 
486  /* get enough memory to store the cut */
487  SCIP_CALL( sepastoreEnsureCutsMem(sepastore, set, sepastore->ncuts+1) );
488  assert(sepastore->ncuts < sepastore->cutssize);
489 
490  SCIPsetDebugMsg(set, "adding cut <%s> to separation storage of size %d (forcecut=%u, len=%d)\n",
491  SCIProwGetName(cut), sepastore->ncuts, forcecut, SCIProwGetNNonz(cut));
492  /*SCIP_CALL( SCIPprintRow(set->scip, cut, NULL) );*/
493 
494  /* capture the cut */
495  SCIProwCapture(cut);
496 
497  /* add cut to arrays */
498  if( forcecut )
499  {
500  /* make room at the beginning of the array for forced cut */
501  pos = sepastore->nforcedcuts;
502  sepastore->cuts[sepastore->ncuts] = sepastore->cuts[pos];
503  sepastore->nforcedcuts++;
504  }
505  else
506  pos = sepastore->ncuts;
507 
508  sepastore->cuts[pos] = cut;
509  sepastore->ncuts++;
510 
511  /* check, if the row addition to separation storage events are tracked if so, issue ROWADDEDSEPA event */
512  if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWADDEDSEPA) != 0 )
513  {
514  SCIP_EVENT* event;
515 
516  SCIP_CALL( SCIPeventCreateRowAddedSepa(&event, blkmem, cut) );
517  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
518  }
519 
520  /* If the duals need to be collected, then the infeasible flag is set to FALSE. This ensures that the LP is solved */
521  if( set->lp_alwaysgetduals && sepastore->initiallp )
522  (*infeasible) = FALSE;
523 
524  return SCIP_OKAY;
525 }
526 
527 /** applies a lower bound change */
528 static
530  SCIP_SEPASTORE* sepastore, /**< separation storage */
531  BMS_BLKMEM* blkmem, /**< block memory */
532  SCIP_SET* set, /**< global SCIP settings */
533  SCIP_STAT* stat, /**< problem statistics */
534  SCIP_PROB* transprob, /**< transformed problem */
535  SCIP_PROB* origprob, /**< original problem */
536  SCIP_TREE* tree, /**< branch and bound tree */
537  SCIP_REOPT* reopt, /**< reoptimization data structure */
538  SCIP_LP* lp, /**< LP data */
539  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
540  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
541  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
542  SCIP_VAR* var, /**< problem variable */
543  SCIP_Real bound, /**< new lower bound of variable */
544  SCIP_Bool local, /**< is it a local bound change? (otherwise global) */
545  SCIP_Bool* applied, /**< pointer to store whether the domain change was applied */
546  SCIP_Bool* cutoff /**< pointer to store TRUE, if an infeasibility has been detected */
547  )
548 {
549  assert(sepastore != NULL);
550  assert(cutoff != NULL);
551  assert(applied != NULL);
552 
553  /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */
554  SCIPvarAdjustLb(var, set, &bound);
555 
556  if( local )
557  {
558  /* apply the local bound change or detect a cutoff */
559  if( SCIPsetIsGT(set, bound, SCIPvarGetLbLocal(var)) )
560  {
561  SCIPsetDebugMsg(set, " -> applying bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
563 
564  /* changing the lower bound to a value >= SCIPinfinity should result in a cutoff,
565  * since "infinite" values in solutions are reserved for another meaning
566  */
567  if( !SCIPsetIsInfinity(set, bound) && SCIPsetIsFeasLE(set, bound, SCIPvarGetUbLocal(var)) )
568  {
569  SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree,
570  reopt, lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_LOWER, FALSE) );
571  }
572  else
573  *cutoff = TRUE;
574 
575  *applied = TRUE;
576  }
577  else
578  {
579  SCIPsetDebugMsg(set, " -> ignoring bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
581  }
582  }
583  else
584  {
585  /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */
586  if( SCIPsetIsGT(set, bound, SCIPvarGetLbGlobal(var)) )
587  {
588  SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
590 
591  /* changing the lower bound to a value >= SCIPinfinity should result in a cutoff,
592  * since "infinite" values in solutions are reserved for another meaning
593  */
594  if( !SCIPsetIsInfinity(set, bound) && SCIPsetIsFeasLE(set, bound, SCIPvarGetUbGlobal(var)) )
595  {
596  SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt,
597  lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_LOWER, FALSE) );
598  }
599  else
600  {
601  /* we are done with solving since a global bound change is infeasible */
602  SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
603  *cutoff = TRUE;
604  }
605 
606  *applied = TRUE;
607  }
608  else
609  {
610  SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
612  }
613  }
614 
615  return SCIP_OKAY;
616 }
617 
618 /** applies an upper bound change */
619 static
621  SCIP_SEPASTORE* sepastore, /**< separation storage */
622  BMS_BLKMEM* blkmem, /**< block memory */
623  SCIP_SET* set, /**< global SCIP settings */
624  SCIP_STAT* stat, /**< problem statistics */
625  SCIP_PROB* transprob, /**< transformed problem */
626  SCIP_PROB* origprob, /**< original problem */
627  SCIP_TREE* tree, /**< branch and bound tree */
628  SCIP_REOPT* reopt, /**< reoptimization data structure */
629  SCIP_LP* lp, /**< LP data */
630  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
631  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
632  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
633  SCIP_VAR* var, /**< problem variable */
634  SCIP_Real bound, /**< new upper bound of variable */
635  SCIP_Bool local, /**< is it a local bound change? (otherwise global) */
636  SCIP_Bool* applied, /**< pointer to store whether the domain change was applied */
637  SCIP_Bool* cutoff /**< pointer to store TRUE, if an infeasibility has been detected */
638  )
639 {
640  assert(sepastore != NULL);
641  assert(cutoff != NULL);
642  assert(applied != NULL);
643 
644  /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */
645  SCIPvarAdjustUb(var, set, &bound);
646 
647  if( local )
648  {
649  /* apply the local bound change or detect a cutoff */
650  if( SCIPsetIsLT(set, bound, SCIPvarGetUbLocal(var)) )
651  {
652  SCIPsetDebugMsg(set, " -> applying bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
654 
655  /* changing the upper bound to a value <= -SCIPinfinity should result in a cutoff,
656  * since "infinite" values in solutions are reserved for another meaning
657  */
658  if( !SCIPsetIsInfinity(set, -bound) && SCIPsetIsFeasGE(set, bound, SCIPvarGetLbLocal(var)) )
659  {
660  SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree,
661  reopt, lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_UPPER, FALSE) );
662  }
663  else
664  *cutoff = TRUE;
665 
666  *applied = TRUE;
667  }
668  else
669  {
670  SCIPsetDebugMsg(set, " -> ignoring bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
672  }
673  }
674  else
675  {
676  /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */
677  if( SCIPsetIsLT(set, bound, SCIPvarGetUbGlobal(var)) )
678  {
679  SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
681 
682  /* changing the upper bound to a value <= -SCIPinfinity should result in a cutoff,
683  * since "infinite" values in solutions are reserved for another meaning
684  */
685  if( !SCIPsetIsInfinity(set, -bound) && SCIPsetIsFeasGE(set, bound, SCIPvarGetLbGlobal(var)) )
686  {
687  SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt,
688  lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_UPPER, FALSE) );
689  }
690  else
691  {
692  /* we are done with solving since a global bound change is infeasible */
693  SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
694  *cutoff = TRUE;
695  }
696 
697  *applied = TRUE;
698  }
699  else
700  {
701  SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
703  }
704  }
705 
706  return SCIP_OKAY;
707 }
708 
709 /** applies a cut that is a bound change directly as bound change instead of adding it as row to the LP */
710 static
712  SCIP_SEPASTORE* sepastore, /**< separation storage */
713  BMS_BLKMEM* blkmem, /**< block memory */
714  SCIP_SET* set, /**< global SCIP settings */
715  SCIP_STAT* stat, /**< problem statistics */
716  SCIP_PROB* transprob, /**< transformed problem */
717  SCIP_PROB* origprob, /**< original problem */
718  SCIP_TREE* tree, /**< branch and bound tree */
719  SCIP_REOPT* reopt, /**< reoptimization data structure */
720  SCIP_LP* lp, /**< LP data */
721  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
722  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
723  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
724  SCIP_ROW* cut, /**< cut with a single variable */
725  SCIP_Bool* applied, /**< pointer to store whether the domain change was applied */
726  SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */
727  )
728 {
729  SCIP_COL** cols;
730  SCIP_Real* vals;
731  SCIP_VAR* var;
732  SCIP_Real lhs;
733  SCIP_Real rhs;
734  SCIP_Bool local;
735 
736  assert(sepastore != NULL);
737  assert(!SCIProwIsModifiable(cut));
738  assert(SCIProwGetNNonz(cut) == 1);
739  assert(cutoff != NULL);
740  assert(applied != NULL);
741 
742  *applied = FALSE;
743  *cutoff = FALSE;
744 
745  /* get the single variable and its coefficient of the cut */
746  cols = SCIProwGetCols(cut);
747  assert(cols != NULL);
748 
749  var = SCIPcolGetVar(cols[0]);
750  vals = SCIProwGetVals(cut);
751  assert(vals != NULL);
752  assert(!SCIPsetIsZero(set, vals[0]));
753 
754  /* if the coefficient is nearly zero, we better ignore this cut for numerical reasons */
755  if( SCIPsetIsFeasZero(set, vals[0]) )
756  return SCIP_OKAY;
757 
758  local = SCIProwIsLocal(cut);
759 
760  /* get the left hand side of the cut and convert it to a bound */
761  lhs = SCIProwGetLhs(cut);
762  if( !SCIPsetIsInfinity(set, -lhs) )
763  {
764  lhs -= SCIProwGetConstant(cut);
765  if( vals[0] > 0.0 )
766  {
767  /* coefficient is positive -> lhs corresponds to lower bound */
768  SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
769  cliquetable, var, lhs/vals[0], local, applied, cutoff) );
770  }
771  else
772  {
773  /* coefficient is negative -> lhs corresponds to upper bound */
774  SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
775  cliquetable, var, lhs/vals[0], local, applied, cutoff) );
776  }
777  }
778 
779  /* get the right hand side of the cut and convert it to a bound */
780  rhs = SCIProwGetRhs(cut);
781  if( !SCIPsetIsInfinity(set, rhs) )
782  {
783  rhs -= SCIProwGetConstant(cut);
784  if( vals[0] > 0.0 )
785  {
786  /* coefficient is positive -> rhs corresponds to upper bound */
787  SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
788  cliquetable, var, rhs/vals[0], local, applied, cutoff) );
789  }
790  else
791  {
792  /* coefficient is negative -> rhs corresponds to lower bound */
793  SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
794  cliquetable, var, rhs/vals[0], local, applied, cutoff) );
795  }
796  }
797 
798  /* count the bound change as applied cut */
799  if( *applied && !sepastore->initiallp )
800  sepastore->ncutsapplied++;
801 
802  return SCIP_OKAY;
803 }
804 
805 /** applies the given cut to the LP and updates the orthogonalities and scores of remaining cuts */
806 static
808  SCIP_SEPASTORE* sepastore, /**< separation storage */
809  BMS_BLKMEM* blkmem, /**< block memory */
810  SCIP_SET* set, /**< global SCIP settings */
811  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
812  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
813  SCIP_LP* lp, /**< LP data */
814  SCIP_ROW* cut, /**< cut to apply to the LP */
815  int depth, /**< depth of current node */
816  int* ncutsapplied /**< pointer to count the number of applied cuts */
817  )
818 {
819  assert(sepastore != NULL);
820  assert(ncutsapplied != NULL);
821 
822  /* a row could have been added twice to the separation store; add it only once! */
823  if( !SCIProwIsInLP(cut) )
824  {
825  /* add cut to the LP and capture it */
826  SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, cut, depth) );
827 
828  /* update statistics -> only if we are not in the initial lp (cuts are only counted if added during run) */
829  if( !sepastore->initiallp )
830  {
831  sepastore->ncutsapplied++;
832 
833  /* increase count of applied cuts for origins of row */
834  switch ( cut->origintype )
835  {
837  assert( cut->origin != NULL );
839  break;
841  assert( cut->origin != NULL );
843  break;
845  assert( cut->origin != NULL );
847  break;
850  /* do nothing - cannot update statistics */
851  break;
852  default:
853  SCIPerrorMessage("unkown type of row origin.\n");
854  return SCIP_INVALIDDATA;
855  }
856  }
857 
858  (*ncutsapplied)++;
859  }
860 
861  return SCIP_OKAY;
862 }
863 
864 /** adds cuts to the LP and clears separation storage */
866  SCIP_SEPASTORE* sepastore, /**< separation storage */
867  BMS_BLKMEM* blkmem, /**< block memory */
868  SCIP_SET* set, /**< global SCIP settings */
869  SCIP_STAT* stat, /**< problem statistics */
870  SCIP_PROB* transprob, /**< transformed problem */
871  SCIP_PROB* origprob, /**< original problem */
872  SCIP_TREE* tree, /**< branch and bound tree */
873  SCIP_REOPT* reopt, /**< reoptimization data structure */
874  SCIP_LP* lp, /**< LP data */
875  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
876  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
877  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
878  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
879  SCIP_Bool root, /**< are we at the root node? */
880  SCIP_EFFICIACYCHOICE efficiacychoice, /**< type of solution to base efficiacy computation on */
881  SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */
882  )
883 {
884  SCIP_NODE* node;
885  SCIP_Real maxparall;
886  SCIP_Real goodmaxparall;
887  int maxsepacuts;
888  int ncutsapplied;
889  int nselectedcuts;
890  int depth;
891  int i;
892 
893  assert(sepastore != NULL);
894  assert(set != NULL);
895  assert(tree != NULL);
896  assert(lp != NULL);
897  assert(cutoff != NULL);
898 
899  SCIP_UNUSED(efficiacychoice);
900 
901  *cutoff = FALSE;
902 
903  SCIPsetDebugMsg(set, "applying %d cuts\n", sepastore->ncuts);
904 
905  node = SCIPtreeGetCurrentNode(tree);
906  assert(node != NULL);
907 
908  /* get maximal number of cuts to add to the LP */
909  maxsepacuts = SCIPsetGetSepaMaxcuts(set, root);
910  ncutsapplied = 0;
911 
912  /* get depth of current node */
913  depth = SCIPnodeGetDepth(node);
914 
915  if( root )
916  {
917  maxparall = 1.0 - set->sepa_minorthoroot;
918  goodmaxparall = MAX(0.5, 1.0 - set->sepa_minorthoroot);
919  }
920  else
921  {
922  maxparall = 1.0 - set->sepa_minortho;
923  goodmaxparall = MAX(0.5, 1.0 - set->sepa_minortho);
924  }
925 
926  /* call cut selection algorithm */
927  SCIP_CALL( SCIPselectCuts(set->scip, sepastore->cuts, sepastore->randnumgen, 0.9, 0.0, goodmaxparall, maxparall,
928  set->sepa_dircutoffdistfac, set->sepa_efficacyfac, set->sepa_objparalfac, set->sepa_intsupportfac,
929  sepastore->ncuts, sepastore->nforcedcuts, maxsepacuts, &nselectedcuts) );
930 
931  /* apply all selected cuts */
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 SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17265
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5987
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:529
internal methods for managing events
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6045
SCIP_Bool SCIPsetIsFeasZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6495
void * origin
Definition: struct_lp.h:216
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:140
internal methods for branch and bound tree
unsigned int SCIPsetInitializeRandomSeed(SCIP_SET *set, unsigned int initialseedvalue)
Definition: set.c:7169
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:711
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
void SCIPsepaIncNAppliedCuts(SCIP_SEPA *sepa)
Definition: sepa.c:864
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:17077
void SCIProwCapture(SCIP_ROW *row)
Definition: lp.c:5327
void SCIPsepastoreStartForceCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:144
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17122
int SCIPsepastoreGetNCutsApplied(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1121
#define FALSE
Definition: def.h:73
methods for the aggregation rows
datastructures for managing events
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7448
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6099
#define TRUE
Definition: def.h:72
#define SCIPdebugCheckRow(set, row)
Definition: debug.h:260
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:6796
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5580
#define SCIP_UNUSED(x)
Definition: def.h:424
SCIP_Real SCIProwGetNLPEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6952
static SCIP_Bool sepastoreIsCutRedundant(SCIP_SEPASTORE *sepastore, SCIP_SET *set, SCIP_STAT *stat, SCIP_ROW *cut)
Definition: sepastore.c:167
#define BMSfreeMemory(ptr)
Definition: memory.h:137
void SCIPvarAdjustLb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *lb)
Definition: var.c:6326
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17275
internal methods for LP management
Definition: heur_padm.c:125
int SCIPsetGetSepaMaxcuts(SCIP_SET *set, SCIP_Bool root)
Definition: set.c:5719
SCIP_ROW ** cuts
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17387
SCIP_Bool SCIPsetIsEfficacious(SCIP_SET *set, SCIP_Bool root, SCIP_Real efficacy)
Definition: set.c:6849
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_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:6027
SCIP_Bool SCIPsepastoreIsCutApplicable(SCIP_SET *set, SCIP_ROW *cut)
Definition: sepastore.c:1072
#define SCIP_EVENTTYPE_ROWADDEDSEPA
Definition: type_event.h:99
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
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:807
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17102
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPsepastoreCreate(SCIP_SEPASTORE **sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set)
Definition: sepastore.c:77
SCIP_EVENTTYPE eventmask
Definition: struct_event.h:189
SCIP_RETCODE SCIProwChgLocal(SCIP_ROW *row, SCIP_Bool local)
Definition: lp.c:5718
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17112
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
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:9495
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem)
Definition: misc.c:9943
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:370
SCIP_Bool SCIPsetIsFeasGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6473
internal methods for storing separated cuts
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6429
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:367
SCIP_RETCODE SCIProwRelease(SCIP_ROW **row, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: lp.c:5340
data structures and methods for collecting reoptimization information
internal methods for problem variables
#define SCIP_Bool
Definition: def.h:70
static SCIP_Bool sepastoreIsCutRedundantOrInfeasible(SCIP_SEPASTORE *sepastore, SCIP_SET *set, SCIP_STAT *stat, SCIP_ROW *cut, SCIP_Bool *infeasible)
Definition: sepastore.c:206
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
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:620
#define MAX(x, y)
Definition: tclique_def.h:83
void SCIPconshdlrIncNAppliedCuts(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4866
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17156
methods for debugging
#define SCIPsetDebugMsg
Definition: set.h:1721
#define SCIP_EVENTTYPE_ROWDELETEDSEPA
Definition: type_event.h:100
static SCIP_RETCODE sepastoreEnsureCutsMem(SCIP_SEPASTORE *sepastore, SCIP_SET *set, int num)
Definition: sepastore.c:54
static SCIP_Bool sepastoreIsBdchgApplicable(SCIP_SET *set, SCIP_ROW *cut)
Definition: sepastore.c:263
void SCIPsepastoreEndInitialLP(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:132
SCIP_Real SCIProwGetRelaxEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6912
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6407
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
void SCIPsepastoreStartInitialLP(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:120
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16906
SCIP_Real SCIProwGetMaxActivity(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6607
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIP_RANDNUMGEN * randnumgen
int SCIPsepastoreGetNCutsFound(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1101
SCIP_Real SCIProwGetMinActivity(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6586
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
Definition: tree.c:8448
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_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8381
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:865
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:2509
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6063
#define SCIP_Real
Definition: def.h:163
internal methods for problem statistics
SCIP_Bool SCIPsetIsFeasPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6506
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8097
int SCIPsepastoreGetNCutsFoundRound(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1111
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17215
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:9927
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:119
internal methods for constraints and constraint handlers
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6451
void SCIPvarAdjustUb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *ub)
Definition: var.c:6343
SCIP_Bool initiallp
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17166
datastructures for storing conflicts
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:429
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:381
SCIP_Bool forcecuts
void SCIPsepastoreEndForceCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:155
SCIP_RETCODE SCIPsepastoreFree(SCIP_SEPASTORE **sepastore, BMS_BLKMEM *blkmem)
Definition: sepastore.c:103
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:401
SCIP callable library.
SCIP_RETCODE SCIPeventCreateRowAddedSepa(SCIP_EVENT **event, BMS_BLKMEM *blkmem, SCIP_ROW *row)
Definition: event.c:847