sepastore.c
Go to the documentation of this file.
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
97 SCIP_CALL( SCIPrandomCreate(&(*sepastore)->randnumgen, blkmem, (unsigned int)SCIPsetInitializeRandomSeed(set, 0x5EED)) );
211 SCIP_Bool* infeasible /**< pointer to store whether the cut has been detected to be infeasible */
225 /* modifiable cuts cannot be declared redundant or infeasible, since we don't know all coefficients */
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.
381 /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
422 assert(!SCIPsetIsInfinity(set, -SCIProwGetLhs(cut)) || !SCIPsetIsInfinity(set, SCIProwGetRhs(cut)));
436 /* the cut will be forced to enter the LP if the dual must be collected and the initial LP is being constructed */
439 /* in the root node, every local cut is a global cut, and global cuts are nicer in many ways ... */
442 SCIPsetDebugMsg(set, "change local flag of cut <%s> to FALSE due to addition in root node\n", SCIProwGetName(cut));
451 /* Note that we add infeasible rows in any case, since we cannot be sure whether the return values are handled
454 /* in each separation round, make sure that at least one (even redundant) cut enters the LP to avoid cycling */
458 /* if only one cut is currently present in sepastore, it could be redundant; in this case, it can now be removed
460 if( sepastore->ncuts == 1 && sepastoreIsCutRedundant(sepastore, set, stat, sepastore->cuts[0]) )
462 /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
482 forcecut = forcecut || sepastore->initiallp || sepastore->forcecuts || (!SCIProwIsModifiable(cut) && SCIProwGetNNonz(cut) == 1 && sepastoreIsBdchgApplicable(set, cut));
490 SCIPsetDebugMsg(set, "adding cut <%s> to separation storage of size %d (forcecut=%u, len=%d)\n",
511 /* check, if the row addition to separation storage events are tracked if so, issue ROWADDEDSEPA event */
520 /* If the duals need to be collected, then the infeasible flag is set to FALSE. This ensures that the LP is solved */
553 /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */
562 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bound, SCIPvarGetUbLocal(var));
569 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree,
580 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bound, SCIPvarGetUbLocal(var));
585 /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */
588 SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
589 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), bound, SCIPvarGetUbGlobal(var));
596 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt,
602 SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
610 SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
611 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), bound, SCIPvarGetUbGlobal(var));
644 /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */
653 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var), bound);
660 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree,
671 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var), bound);
676 /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */
679 SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
680 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), SCIPvarGetLbGlobal(var), bound);
687 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt,
693 SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
701 SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
702 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), SCIPvarGetLbGlobal(var), bound);
709 /** applies a cut that is a bound change directly as bound change instead of adding it as row to the LP */
768 SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
774 SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
787 SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
793 SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
805 /** applies the given cut to the LP and updates the orthogonalities and scores of remaining cuts */
828 /* update statistics -> only if we are not in the initial lp (cuts are only counted if added during run) */
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,
938 if( i < sepastore->nforcedcuts || SCIPsetIsFeasPositive(set, SCIProwGetLPEfficacy(cut, set, stat, lp)) )
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 */
946 SCIP_CALL( sepastoreApplyBdchg(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
955 SCIPsetDebugMsg(set, " -> applying%s cut <%s>\n", (i < sepastore->nforcedcuts) ? " forced" : "", SCIProwGetName(cut));
957 SCIP_CALL( sepastoreApplyCut(sepastore, blkmem, set, eventqueue, eventfilter, lp, cut, depth, &ncutsapplied) );
987 /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
1004 /* if we have just finished the initial LP construction, free the (potentially large) cuts array */
1014 /** removes cuts that are inefficacious w.r.t. the current LP solution from separation storage without adding the cuts to the LP */
1070 * A cut is applicable if it is modifiable, not a bound change, or a bound change that changes bounds by at least epsilon.
1077 return SCIProwIsModifiable(cut) || SCIProwGetNNonz(cut) != 1 || sepastoreIsBdchgApplicable(set, cut);
internal methods for separators
Definition: type_lp.h:65
static SCIP_RETCODE sepastoreApplyLb(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real bound, SCIP_Bool local, SCIP_Bool *applied, SCIP_Bool *cutoff)
Definition: sepastore.c:529
internal methods for managing events
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6038
internal methods for branch and bound tree
Definition: type_sepastore.h:33
unsigned int SCIPsetInitializeRandomSeed(SCIP_SET *set, unsigned int initialseedvalue)
Definition: set.c:7162
static SCIP_RETCODE sepastoreApplyBdchg(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_ROW *cut, SCIP_Bool *applied, SCIP_Bool *cutoff)
Definition: sepastore.c:711
SCIP_RETCODE SCIPeventqueueAdd(SCIP_EVENTQUEUE *eventqueue, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter, SCIP_EVENT **event)
Definition: event.c:2231
SCIP_ROW ** SCIPsepastoreGetCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1081
Definition: struct_var.h:198
void SCIPsepastoreStartForceCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:144
int SCIPsepastoreGetNCutsApplied(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1121
Definition: type_lp.h:64
Definition: struct_sepastore.h:39
methods for the aggregation rows
datastructures for managing events
Definition: struct_event.h:179
SCIP_Real SCIProwGetLPEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:6796
Definition: struct_prob.h:39
SCIP_Real SCIProwGetNLPEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6952
static SCIP_Bool sepastoreIsCutRedundant(SCIP_SEPASTORE *sepastore, SCIP_SET *set, SCIP_STAT *stat, SCIP_ROW *cut)
Definition: sepastore.c:167
Definition: struct_sepa.h:37
void SCIPvarAdjustLb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *lb)
Definition: var.c:6321
Definition: type_sepastore.h:35
Definition: type_lp.h:66
internal methods for LP management
Definition: heur_padm.c:125
Definition: struct_tree.h:132
Definition: struct_lp.h:126
Definition: struct_set.h:61
Definition: type_sepastore.h:34
SCIP_Bool SCIPsetIsEfficacious(SCIP_SET *set, SCIP_Bool root, SCIP_Real efficacy)
Definition: set.c:6842
Definition: type_lp.h:67
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:1176
SCIP_RETCODE SCIPeventCreateRowDeletedSepa(SCIP_EVENT **event, BMS_BLKMEM *blkmem, SCIP_ROW *row)
Definition: event.c:866
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6020
SCIP_Bool SCIPsepastoreIsCutApplicable(SCIP_SET *set, SCIP_ROW *cut)
Definition: sepastore.c:1072
static SCIP_RETCODE sepastoreApplyCut(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_ROW *cut, int depth, int *ncutsapplied)
Definition: sepastore.c:807
Definition: struct_cons.h:37
Definition: struct_cons.h:117
Definition: type_retcode.h:42
SCIP_RETCODE SCIPsepastoreCreate(SCIP_SEPASTORE **sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set)
Definition: sepastore.c:77
Definition: type_lp.h:47
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1091
SCIP_RETCODE SCIPsepastoreRemoveInefficaciousCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_Bool root, SCIP_EFFICIACYCHOICE efficiacychoice)
Definition: sepastore.c:1015
SCIP_RETCODE SCIPlpAddRow(SCIP_LP *lp, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_ROW *row, int depth)
Definition: lp.c:9495
internal miscellaneous methods
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem)
Definition: misc.c:9929
Definition: type_retcode.h:33
Definition: struct_event.h:152
internal methods for global SCIP settings
SCIP_Bool SCIPsetIsFeasGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6466
internal methods for storing separated cuts
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6422
static SCIP_RETCODE sepastoreDelCut(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, int pos)
Definition: sepastore.c:367
SCIP_RETCODE SCIProwRelease(SCIP_ROW **row, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: lp.c:5340
data structures and methods for collecting reoptimization information
internal methods for problem variables
static SCIP_Bool sepastoreIsCutRedundantOrInfeasible(SCIP_SEPASTORE *sepastore, SCIP_SET *set, SCIP_STAT *stat, SCIP_ROW *cut, SCIP_Bool *infeasible)
Definition: sepastore.c:206
static SCIP_RETCODE sepastoreApplyUb(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real bound, SCIP_Bool local, SCIP_Bool *applied, SCIP_Bool *cutoff)
Definition: sepastore.c:620
Definition: struct_lp.h:192
void SCIPconshdlrIncNAppliedCuts(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4878
methods for debugging
Definition: struct_reopt.h:130
static SCIP_RETCODE sepastoreEnsureCutsMem(SCIP_SEPASTORE *sepastore, SCIP_SET *set, int num)
Definition: sepastore.c:54
Definition: type_lp.h:63
static SCIP_Bool sepastoreIsBdchgApplicable(SCIP_SET *set, SCIP_ROW *cut)
Definition: sepastore.c:263
void SCIPsepastoreEndInitialLP(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:132
SCIP_Real SCIProwGetRelaxEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6912
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6400
void SCIPsepastoreStartInitialLP(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:120
SCIP_Real SCIProwGetMaxActivity(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6607
int SCIPsepastoreGetNCutsFound(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1101
SCIP_Real SCIProwGetMinActivity(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6586
SCIP_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:2075
Definition: struct_lp.h:259
Definition: type_lp.h:48
SCIP_RETCODE SCIPsepastoreApplyCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool root, SCIP_EFFICIACYCHOICE efficiacychoice, SCIP_Bool *cutoff)
Definition: sepastore.c:865
Definition: struct_implics.h:88
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:2512
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6056
internal methods for problem statistics
SCIP_Bool SCIPsetIsFeasPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6499
int SCIPsepastoreGetNCutsFoundRound(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1111
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:9913
internal methods for constraints and constraint handlers
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6444
void SCIPvarAdjustUb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *ub)
Definition: var.c:6338
Definition: struct_stat.h:50
Definition: struct_tree.h:175
datastructures for storing conflicts
common defines and data types used in all packages of SCIP
Definition: struct_event.h:214
Definition: type_retcode.h:43
SCIP_RETCODE SCIPsepastoreClearCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp)
Definition: sepastore.c:969
Definition: struct_branch.h:37
void SCIPsepastoreEndForceCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:155
SCIP_RETCODE SCIPsepastoreFree(SCIP_SEPASTORE **sepastore, BMS_BLKMEM *blkmem)
Definition: sepastore.c:103
SCIP_RETCODE SCIPsepastoreAddCut(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool root, SCIP_Bool *infeasible)
Definition: sepastore.c:401
SCIP callable library.
SCIP_RETCODE SCIPeventCreateRowAddedSepa(SCIP_EVENT **event, BMS_BLKMEM *blkmem, SCIP_ROW *row)
Definition: event.c:847