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