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