methods for storing separated cuts
Definition in file sepastore.c.
#include <assert.h>
#include "scip/def.h"
#include "scip/set.h"
#include "scip/stat.h"
#include "scip/lp.h"
#include "scip/var.h"
#include "scip/tree.h"
#include "scip/reopt.h"
#include "scip/sepastore.h"
#include "scip/event.h"
#include "scip/sepa.h"
#include "scip/cons.h"
#include "scip/debug.h"
#include "scip/scip.h"
#include "scip/cuts.h"
#include "scip/cutsel.h"
#include "scip/struct_event.h"
#include "scip/struct_sepastore.h"
#include "scip/misc.h"
Go to the source code of this file.
|
static |
resizes cuts and score arrays to be able to store at least num entries
sepastore | separation storage |
set | global SCIP settings |
num | minimal number of slots in array |
Definition at line 64 of file sepastore.c.
References assert(), BMSreallocMemoryArray, SCIP_SepaStore::cuts, SCIP_SepaStore::cutssize, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIPsetCalcMemGrowSize().
Referenced by SCIPsepastoreAddCut().
SCIP_RETCODE SCIPsepastoreCreate | ( | SCIP_SEPASTORE ** | sepastore, |
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set ) |
creates separation storage
sepastore | pointer to store separation storage |
blkmem | block memory |
set | global SCIP settings |
Definition at line 87 of file sepastore.c.
References assert(), BMSallocMemory, FALSE, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIPrandomCreate(), and SCIPsetInitializeRandomSeed().
Referenced by initSolve().
SCIP_RETCODE SCIPsepastoreFree | ( | SCIP_SEPASTORE ** | sepastore, |
BMS_BLKMEM * | blkmem ) |
frees separation storage
sepastore | pointer to store separation storage |
blkmem | block memory |
Definition at line 115 of file sepastore.c.
References assert(), BMSfreeMemory, BMSfreeMemoryArrayNull, NULL, SCIP_OKAY, and SCIPrandomFree().
Referenced by freeReoptSolve(), and freeSolve().
void SCIPsepastoreStartInitialLP | ( | SCIP_SEPASTORE * | sepastore | ) |
informs separation storage that the setup of the initial LP starts now
sepastore | separation storage |
Definition at line 132 of file sepastore.c.
References assert(), SCIP_SepaStore::initiallp, SCIP_SepaStore::ncuts, NULL, and TRUE.
Referenced by SCIPconstructCurrentLP(), and SCIPinitConssLP().
void SCIPsepastoreEndInitialLP | ( | SCIP_SEPASTORE * | sepastore | ) |
informs separation storage that the setup of the initial LP is now finished
sepastore | separation storage |
Definition at line 144 of file sepastore.c.
References assert(), FALSE, SCIP_SepaStore::initiallp, SCIP_SepaStore::ncuts, and NULL.
Referenced by SCIPconstructCurrentLP(), and SCIPinitConssLP().
void SCIPsepastoreStartForceCuts | ( | SCIP_SEPASTORE * | sepastore | ) |
informs separation storage that the following cuts should be used in any case
sepastore | separation storage |
Definition at line 156 of file sepastore.c.
References assert(), SCIP_SepaStore::forcecuts, NULL, and TRUE.
Referenced by enforceConstraints().
void SCIPsepastoreEndForceCuts | ( | SCIP_SEPASTORE * | sepastore | ) |
informs separation storage that the following cuts should no longer be used in any case
sepastore | separation storage |
Definition at line 167 of file sepastore.c.
References assert(), FALSE, SCIP_SepaStore::forcecuts, and NULL.
Referenced by enforceConstraints().
|
static |
checks cut for redundancy due to activity bounds
sepastore | separation storage |
set | global SCIP settings |
stat | problem statistics data |
cut | separated cut |
Definition at line 179 of file sepastore.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIProwGetLhs(), SCIProwGetMaxActivity(), SCIProwGetMinActivity(), SCIProwGetName(), SCIProwGetRhs(), SCIProwIsModifiable(), SCIPsetDebugMsg, SCIPsetIsInfinity(), SCIPsetIsLE(), and TRUE.
Referenced by SCIPsepastoreAddCut().
|
static |
checks cut for redundancy or infeasibility due to activity bounds
sepastore | separation storage |
set | global SCIP settings |
stat | problem statistics data |
cut | separated cut |
infeasible | pointer to store whether the cut has been detected to be infeasible |
Definition at line 218 of file sepastore.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIProwGetLhs(), SCIProwGetMaxActivity(), SCIProwGetMinActivity(), SCIProwGetName(), SCIProwGetRhs(), SCIProwIsModifiable(), SCIPsetDebugMsg, SCIPsetIsFeasNegative(), SCIPsetIsFeasPositive(), SCIPsetIsInfinity(), SCIPsetIsLE(), and TRUE.
Referenced by SCIPsepastoreAddCut().
checks whether a cut with only one variable can be applied as boundchange
This is the case if the bound change would prove infeasibility (w.r.t feastol), or if the new bound is at least epsilon better than the old bound. In the latter case, also the opposite bound has to be taken into account.
set | global SCIP settings |
cut | cut with a single variable |
Definition at line 275 of file sepastore.c.
References assert(), FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_Real, SCIPcolGetVar(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsetIsFeasGT(), SCIPsetIsFeasLT(), SCIPsetIsFeasZero(), SCIPsetIsGT(), SCIPsetIsInfinity(), SCIPsetIsLT(), SCIPsetIsZero(), SCIPvarAdjustLb(), SCIPvarAdjustUb(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by SCIPsepastoreAddCut(), SCIPsepastoreApplyCuts(), and SCIPsepastoreIsCutApplicable().
|
static |
removes a non-forced cut from the separation storage
sepastore | separation storage |
blkmem | block memory |
set | global SCIP settings |
eventqueue | event queue |
eventfilter | event filter for global events |
lp | LP data |
pos | position of cut to delete |
Definition at line 379 of file sepastore.c.
References assert(), SCIP_SepaStore::cuts, SCIP_EventFilter::eventmask, SCIP_Row::fromcutpool, SCIP_SepaStore::initiallp, SCIP_EventFilter::len, SCIP_SepaStore::ncuts, SCIP_SepaStore::ncutsadded, SCIP_SepaStore::ncutsaddeddirect, SCIP_SepaStore::ncutsaddedviapool, SCIP_SepaStore::nforcedcuts, NULL, SCIP_Row::origintype, SCIP_CALL, SCIP_EVENTTYPE_ROWDELETEDSEPA, SCIP_OKAY, SCIP_ROWORIGINTYPE_SEPA, SCIPeventCreateRowDeletedSepa(), SCIPeventqueueAdd(), SCIProwGetOriginSepa(), SCIProwRelease(), and SCIPsepaDecNCutsAdded().
Referenced by SCIPsepastoreRemoveInefficaciousCuts().
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 ) |
adds cut to separation storage and captures it
sepastore | separation storage |
blkmem | block memory |
set | global SCIP settings |
stat | problem statistics data |
eventqueue | event queue |
eventfilter | event filter for global events |
lp | LP data |
cut | separated cut |
forcecut | should the cut be forced to enter the LP? |
root | are we at the root node? |
infeasible | pointer to store whether the cut is infeasible |
Definition at line 428 of file sepastore.c.
References assert(), SCIP_SepaStore::cuts, SCIP_SepaStore::cutssize, SCIP_EventFilter::eventmask, FALSE, SCIP_SepaStore::forcecuts, SCIP_Row::fromcutpool, SCIP_SepaStore::initiallp, SCIP_EventFilter::len, SCIP_SepaStore::ncuts, SCIP_SepaStore::ncutsadded, SCIP_SepaStore::ncutsaddeddirect, SCIP_SepaStore::ncutsaddedviapool, SCIP_SepaStore::ncutsfoundround, SCIP_SepaStore::nforcedcuts, NULL, SCIP_Row::origintype, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_ROWADDEDSEPA, SCIP_EVENTTYPE_ROWDELETEDSEPA, SCIP_OKAY, SCIP_ROWORIGINTYPE_SEPA, SCIPdebugCheckRow, SCIPeventCreateRowAddedSepa(), SCIPeventCreateRowDeletedSepa(), SCIPeventqueueAdd(), SCIProwCapture(), SCIProwChgLocal(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetOriginSepa(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIProwRelease(), SCIPsepaDecNCutsAdded(), SCIPsepaIncNCutsAdded(), SCIPsetDebugMsg, SCIPsetGetSepaMaxcuts(), SCIPsetIsInfinity(), sepastoreEnsureCutsMem(), sepastoreIsBdchgApplicable(), sepastoreIsCutRedundant(), and sepastoreIsCutRedundantOrInfeasible().
Referenced by SCIPaddRow(), SCIPconstructCurrentLP(), SCIPcutpoolSeparate(), and SCIPreoptApplyCuts().
|
static |
applies a lower bound change
sepastore | separation storage |
blkmem | block memory |
set | global SCIP settings |
stat | problem statistics |
transprob | transformed problem |
origprob | original problem |
tree | branch and bound tree |
reopt | reoptimization data structure |
lp | LP data |
branchcand | branching candidate storage |
eventqueue | event queue |
cliquetable | clique table data structure |
var | problem variable |
bound | new lower bound of variable |
local | is it a local bound change? (otherwise global) |
applied | pointer to store whether the domain change was applied |
cutoff | pointer to store TRUE, if an infeasibility has been detected |
Definition at line 584 of file sepastore.c.
References assert(), bound, cutoff, FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPnodeAddBoundchg(), SCIPnodeCutoff(), SCIPsetDebugMsg, SCIPsetIsFeasLE(), SCIPsetIsGT(), SCIPsetIsInfinity(), SCIPtreeGetCurrentNode(), SCIPtreeGetRootNode(), SCIPvarAdjustLb(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by sepastoreApplyBdchg().
|
static |
applies an upper bound change
sepastore | separation storage |
blkmem | block memory |
set | global SCIP settings |
stat | problem statistics |
transprob | transformed problem |
origprob | original problem |
tree | branch and bound tree |
reopt | reoptimization data structure |
lp | LP data |
branchcand | branching candidate storage |
eventqueue | event queue |
cliquetable | clique table data structure |
var | problem variable |
bound | new upper bound of variable |
local | is it a local bound change? (otherwise global) |
applied | pointer to store whether the domain change was applied |
cutoff | pointer to store TRUE, if an infeasibility has been detected |
Definition at line 675 of file sepastore.c.
References assert(), bound, cutoff, FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPnodeAddBoundchg(), SCIPnodeCutoff(), SCIPsetDebugMsg, SCIPsetIsFeasGE(), SCIPsetIsInfinity(), SCIPsetIsLT(), SCIPtreeGetCurrentNode(), SCIPtreeGetRootNode(), SCIPvarAdjustUb(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by sepastoreApplyBdchg().
|
static |
applies a cut that is a bound change directly as bound change instead of adding it as row to the LP
sepastore | separation storage |
blkmem | block memory |
set | global SCIP settings |
stat | problem statistics |
transprob | transformed problem |
origprob | original problem |
tree | branch and bound tree |
reopt | reoptimization data structure |
lp | LP data |
branchcand | branching candidate storage |
eventqueue | event queue |
cliquetable | clique table data structure |
cut | cut with a single variable |
applied | pointer to store whether the domain change was applied |
cutoff | pointer to store whether an empty domain was created |
Definition at line 766 of file sepastore.c.
References assert(), cutoff, FALSE, SCIP_SepaStore::initiallp, SCIP_SepaStore::ncutsapplied, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetVar(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsetIsFeasZero(), SCIPsetIsInfinity(), SCIPsetIsZero(), sepastoreApplyLb(), sepastoreApplyUb(), and var.
Referenced by SCIPsepastoreApplyCuts().
|
static |
applies the given cut to the LP and updates the orthogonalities and scores of remaining cuts
sepastore | separation storage |
blkmem | block memory |
set | global SCIP settings |
eventqueue | event queue |
eventfilter | global event filter |
lp | LP data |
cut | cut to apply to the LP |
depth | depth of current node |
ncutsapplied | pointer to count the number of applied cuts |
Definition at line 862 of file sepastore.c.
References assert(), depth, SCIP_Row::fromcutpool, SCIP_SepaStore::initiallp, SCIP_SepaStore::ncutsapplied, NULL, SCIP_Row::origin, SCIP_Row::origintype, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_ROWORIGINTYPE_CONS, SCIP_ROWORIGINTYPE_CONSHDLR, SCIP_ROWORIGINTYPE_REOPT, SCIP_ROWORIGINTYPE_SEPA, SCIP_ROWORIGINTYPE_UNSPEC, SCIPconsGetHdlr(), SCIPconshdlrIncNAppliedCuts(), SCIPerrorMessage, SCIPlpAddRow(), SCIProwIsInLP(), and SCIPsepaIncNCutsApplied().
Referenced by SCIPsepastoreApplyCuts().
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 ) |
adds cuts to the LP and clears separation storage
sepastore | separation storage |
blkmem | block memory |
set | global SCIP settings |
stat | problem statistics |
transprob | transformed problem |
origprob | original problem |
tree | branch and bound tree |
reopt | reoptimization data structure |
lp | LP data |
branchcand | branching candidate storage |
eventqueue | event queue |
eventfilter | global event filter |
cliquetable | clique table data structure |
root | are we at the root node? |
efficiacychoice | type of solution to base efficiacy computation on |
cutoff | pointer to store whether an empty domain was created |
Definition at line 921 of file sepastore.c.
References assert(), cutoff, SCIP_SepaStore::cuts, depth, FALSE, i, SCIP_SepaStore::initiallp, MIN, SCIP_SepaStore::ncuts, SCIP_SepaStore::nforcedcuts, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_UNUSED, SCIPcutselsSelect(), SCIPnodeGetDepth(), SCIProwGetLPEfficacy(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwIsModifiable(), SCIPsepastoreClearCuts(), SCIPsetDebugMsg, SCIPsetGetSepaMaxcuts(), SCIPsetIsFeasPositive(), SCIPtreeGetCurrentNode(), sepastoreApplyBdchg(), sepastoreApplyCut(), and sepastoreIsBdchgApplicable().
Referenced by applyCuts(), priceAndCutLoop(), SCIPapplyCutsProbing(), SCIPconstructCurrentLP(), and SCIPinitConssLP().
SCIP_RETCODE SCIPsepastoreClearCuts | ( | SCIP_SEPASTORE * | sepastore, |
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set, | ||
SCIP_EVENTQUEUE * | eventqueue, | ||
SCIP_EVENTFILTER * | eventfilter, | ||
SCIP_LP * | lp ) |
clears the separation storage without adding the cuts to the LP
sepastore | separation storage |
blkmem | block memory |
set | global SCIP settings |
eventqueue | event queue |
eventfilter | event filter for global events |
lp | LP data |
Definition at line 1027 of file sepastore.c.
References assert(), BMSfreeMemoryArrayNull, c, SCIP_SepaStore::cuts, SCIP_SepaStore::cutssize, SCIP_EventFilter::eventmask, SCIP_SepaStore::initiallp, SCIP_EventFilter::len, SCIP_SepaStore::ncuts, SCIP_SepaStore::ncutsfoundround, SCIP_SepaStore::nforcedcuts, NULL, SCIP_CALL, SCIP_EVENTTYPE_ROWDELETEDSEPA, SCIP_OKAY, SCIPeventCreateRowDeletedSepa(), SCIPeventqueueAdd(), SCIProwRelease(), and SCIPsetDebugMsg.
Referenced by applyCuts(), priceAndCutLoop(), SCIPclearCuts(), SCIPconstructCurrentLP(), SCIPinitConssLP(), and SCIPsepastoreApplyCuts().
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 ) |
removes cuts that are inefficacious w.r.t. the current LP solution from separation storage without adding the cuts to the LP
sepastore | separation storage |
blkmem | block memory |
set | global SCIP settings |
stat | problem statistics data |
eventqueue | event queue |
eventfilter | event filter for global events |
lp | LP data |
root | are we at the root node? |
efficiacychoice | type of solution to base efficiacy computation on |
Definition at line 1073 of file sepastore.c.
References assert(), c, SCIP_SepaStore::cuts, SCIP_SepaStore::nforcedcuts, NULL, SCIP_Bool, SCIP_CALL, SCIP_EFFICIACYCHOICE_LP, SCIP_EFFICIACYCHOICE_NLP, SCIP_EFFICIACYCHOICE_RELAX, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIProwGetLPEfficacy(), SCIProwGetNLPEfficacy(), SCIProwGetRelaxEfficacy(), SCIPsetDebugMsg, SCIPsetIsEfficacious(), and sepastoreDelCut().
Referenced by SCIPremoveInefficaciousCuts().
indicates whether a cut is applicable
A cut is applicable if it is modifiable, not a bound change, or a bound change that changes bounds by at least epsilon.
set | global SCIP settings |
cut | cut to check |
Definition at line 1130 of file sepastore.c.
References SCIP_Bool, SCIProwGetNNonz(), SCIProwIsModifiable(), and sepastoreIsBdchgApplicable().
Referenced by SCIPisCutApplicable().
SCIP_ROW ** SCIPsepastoreGetCuts | ( | SCIP_SEPASTORE * | sepastore | ) |
get cuts in the separation storage
sepastore | separation storage |
Definition at line 1139 of file sepastore.c.
References assert(), SCIP_SepaStore::cuts, and NULL.
Referenced by SCIPgetCuts().
int SCIPsepastoreGetNCuts | ( | SCIP_SEPASTORE * | sepastore | ) |
get number of cuts in the separation storage
sepastore | separation storage |
Definition at line 1149 of file sepastore.c.
References assert(), SCIP_SepaStore::ncuts, and NULL.
Referenced by applyCuts(), cutpoolSeparate(), enforceConstraints(), priceAndCutLoop(), propAndSolve(), SCIPbranchruleExecExternSol(), SCIPbranchruleExecLPSol(), SCIPconshdlrEnforceLPSol(), SCIPconshdlrEnforceRelaxSol(), SCIPconshdlrSeparateLP(), SCIPconshdlrSeparateSol(), SCIPcutpoolSeparate(), SCIPendProbing(), SCIPgetNCuts(), SCIPsepaExecLP(), SCIPsepaExecSol(), separationRoundLP(), separationRoundSol(), solveNode(), and solveNodeLP().
int SCIPsepastoreGetNCutsAdded | ( | SCIP_SEPASTORE * | sepastore | ) |
gets the total number of cutting planes added to the separation storage; this is equal to the sum of added cuts directly and via the pool.
sepastore | separation storage |
Definition at line 1160 of file sepastore.c.
References assert(), SCIP_SepaStore::ncutsadded, and NULL.
Referenced by SCIPcutpoolSeparate(), and SCIPgetNCutsFound().
int SCIPsepastoreGetNCutsAddedViaPool | ( | SCIP_SEPASTORE * | sepastore | ) |
gets the number of cutting planes added to the separation storage from the cut pool
sepastore | separation storage |
Definition at line 1170 of file sepastore.c.
References assert(), SCIP_SepaStore::ncutsaddedviapool, and NULL.
int SCIPsepastoreGetNCutsAddedDirect | ( | SCIP_SEPASTORE * | sepastore | ) |
gets the number of cutting planes added to the separation storage directly
sepastore | separation storage |
Definition at line 1180 of file sepastore.c.
References assert(), SCIP_SepaStore::ncutsaddeddirect, and NULL.
int SCIPsepastoreGetNCutsFoundRound | ( | SCIP_SEPASTORE * | sepastore | ) |
get number of cuts found so far in current separation round
sepastore | separation storage |
Definition at line 1190 of file sepastore.c.
References assert(), SCIP_SepaStore::ncutsfoundround, and NULL.
Referenced by SCIPgetNCutsFoundRound().
int SCIPsepastoreGetNCutsApplied | ( | SCIP_SEPASTORE * | sepastore | ) |
gets the total number of cutting planes applied to the LP
sepastore | separation storage |
Definition at line 1200 of file sepastore.c.
References assert(), SCIP_SepaStore::ncutsapplied, and NULL.
Referenced by applyCuts(), SCIPgetNCutsApplied(), and solveNodeLP().