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