Detailed Description
flow cover and complemented mixed integer rounding cuts separator (Marchand's version)
For an overview see:
Marchand, H., & Wolsey, L. A. (2001).
Aggregation and mixed integer rounding to solve MIPs.
Operations research, 49(3), 363-371.
Some remarks:
- In general, continuous variables are less prefered than integer variables, since their cut coefficient is worse.
- We seek for aggregations that project out continuous variables that are far away from their bound, since if it is at its bound then it doesn't contribute to the violation
- These aggregations are also useful for the flowcover separation, so after building an aggregation we try to generate a MIR cut and a flowcover cut.
- We only keep the best cut.
Definition in file sepa_aggregation.c.
#include "blockmemshell/memory.h"
#include "scip/cuts.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/sepa_aggregation.h"
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | AggregationData |
Typedefs | |
typedef struct AggregationData | AGGREGATIONDATA |
Functions | |
static SCIP_RETCODE | addCut (SCIP *scip, SCIP_SOL *sol, SCIP_SEPA *sepa, SCIP_Bool makeintegral, SCIP_Real *cutcoefs, int *cutinds, int cutnnz, SCIP_Real cutrhs, SCIP_Real cutefficacy, SCIP_Bool cutislocal, SCIP_Bool cutremovable, int cutrank, const char *cutclassname, SCIP_Bool *cutoff, int *ncuts, SCIP_ROW **thecut) |
static SCIP_RETCODE | setupAggregationData (SCIP *scip, SCIP_SOL *sol, SCIP_Bool allowlocal, AGGREGATIONDATA *aggrdata) |
static void | destroyAggregationData (SCIP *scip, AGGREGATIONDATA *aggrdata) |
static SCIP_Bool | getRowAggregationCandidates (AGGREGATIONDATA *aggrdata, int probvaridx, SCIP_ROW ***rows, SCIP_Real **rowvarcoefs, int *nrows, int *ngoodrows) |
static SCIP_Real | aggrdataGetBoundDist (AGGREGATIONDATA *aggrdata, int probvaridx) |
static SCIP_RETCODE | aggregateNextRow (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *rowlhsscores, SCIP_Real *rowrhsscores, AGGREGATIONDATA *aggrdata, SCIP_AGGRROW *aggrrow, int *naggrs, SCIP_Bool *success) |
static SCIP_RETCODE | aggregation (SCIP *scip, AGGREGATIONDATA *aggrdata, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_Real *rowlhsscores, SCIP_Real *rowrhsscores, int startrow, int maxaggrs, SCIP_Bool *wastried, SCIP_Bool *cutoff, int *cutinds, SCIP_Real *cutcoefs, SCIP_Bool negate, int *ncuts) |
static SCIP_Real | getRowFracActivity (SCIP_ROW *row, SCIP_Real *fractionalities) |
static SCIP_RETCODE | separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, int depth, SCIP_RESULT *result) |
static | SCIP_DECL_SEPACOPY (sepaCopyAggregation) |
static | SCIP_DECL_SEPAFREE (sepaFreeAggregation) |
static | SCIP_DECL_SEPAEXECLP (sepaExeclpAggregation) |
static | SCIP_DECL_SEPAEXECSOL (sepaExecsolAggregation) |
static | SCIP_DECL_SEPAEXECLP (sepaExeclpDummy) |
static | SCIP_DECL_SEPAEXECSOL (sepaExecsolDummy) |
SCIP_RETCODE | SCIPincludeSepaAggregation (SCIP *scip) |
Macro Definition Documentation
◆ SEPA_NAME
#define SEPA_NAME "aggregation" |
Definition at line 76 of file sepa_aggregation.c.
Referenced by separateCuts().
◆ SEPA_DESC
#define SEPA_DESC "aggregation heuristic for complemented mixed integer rounding cuts and flowcover cuts" |
Definition at line 77 of file sepa_aggregation.c.
◆ SEPA_PRIORITY
#define SEPA_PRIORITY -3000 |
Definition at line 78 of file sepa_aggregation.c.
◆ SEPA_FREQ
#define SEPA_FREQ 10 |
Definition at line 79 of file sepa_aggregation.c.
◆ SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 80 of file sepa_aggregation.c.
◆ SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 81 of file sepa_aggregation.c.
◆ SEPA_DELAY
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 82 of file sepa_aggregation.c.
◆ DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS -1 |
maximal number of cmir separation rounds per node (-1: unlimited)
Definition at line 84 of file sepa_aggregation.c.
◆ DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT -1 |
maximal number of cmir separation rounds in the root node (-1: unlimited)
Definition at line 85 of file sepa_aggregation.c.
◆ DEFAULT_MAXTRIES
#define DEFAULT_MAXTRIES 200 |
maximal number of rows to start aggregation with per separation round (-1: unlimited)
Definition at line 86 of file sepa_aggregation.c.
◆ DEFAULT_MAXTRIESROOT
#define DEFAULT_MAXTRIESROOT -1 |
maximal number of rows to start aggregation with per round in the root node (-1: unlimited)
Definition at line 89 of file sepa_aggregation.c.
◆ DEFAULT_MAXFAILS
#define DEFAULT_MAXFAILS 20 |
maximal number of consecutive unsuccessful aggregation tries (-1: unlimited)
Definition at line 92 of file sepa_aggregation.c.
◆ DEFAULT_MAXFAILSROOT
#define DEFAULT_MAXFAILSROOT 100 |
maximal number of consecutive unsuccessful aggregation tries in the root node (-1: unlimited)
Definition at line 93 of file sepa_aggregation.c.
◆ DEFAULT_MAXAGGRS
#define DEFAULT_MAXAGGRS 3 |
maximal number of aggregations for each row per separation round
Definition at line 96 of file sepa_aggregation.c.
◆ DEFAULT_MAXAGGRSROOT
#define DEFAULT_MAXAGGRSROOT 6 |
maximal number of aggregations for each row per round in the root node
Definition at line 97 of file sepa_aggregation.c.
◆ DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXSEPACUTS 100 |
maximal number of cmir cuts separated per separation round
Definition at line 98 of file sepa_aggregation.c.
◆ DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTSROOT 500 |
maximal number of cmir cuts separated per separation round in root node
Definition at line 99 of file sepa_aggregation.c.
◆ DEFAULT_MAXSLACK
#define DEFAULT_MAXSLACK 0.0 |
maximal slack of rows to be used in aggregation
Definition at line 100 of file sepa_aggregation.c.
◆ DEFAULT_MAXSLACKROOT
#define DEFAULT_MAXSLACKROOT 0.1 |
maximal slack of rows to be used in aggregation in the root node
Definition at line 101 of file sepa_aggregation.c.
◆ DEFAULT_DENSITYSCORE
#define DEFAULT_DENSITYSCORE 1e-4 |
weight of row density in the aggregation scoring of the rows
Definition at line 102 of file sepa_aggregation.c.
◆ DEFAULT_SLACKSCORE
#define DEFAULT_SLACKSCORE 1e-3 |
weight of slack in the aggregation scoring of the rows
Definition at line 103 of file sepa_aggregation.c.
◆ DEFAULT_MAXAGGDENSITY
#define DEFAULT_MAXAGGDENSITY 0.20 |
maximal density of aggregated row
Definition at line 104 of file sepa_aggregation.c.
◆ DEFAULT_MAXROWDENSITY
#define DEFAULT_MAXROWDENSITY 0.05 |
maximal density of row to be used in aggregation
Definition at line 105 of file sepa_aggregation.c.
◆ DEFAULT_DENSITYOFFSET
#define DEFAULT_DENSITYOFFSET 100 |
additional number of variables allowed in row on top of density
Definition at line 106 of file sepa_aggregation.c.
◆ DEFAULT_MAXROWFAC
#define DEFAULT_MAXROWFAC 1e+4 |
maximal row aggregation factor
Definition at line 107 of file sepa_aggregation.c.
◆ DEFAULT_MAXTESTDELTA
#define DEFAULT_MAXTESTDELTA -1 |
maximal number of different deltas to try (-1: unlimited)
Definition at line 108 of file sepa_aggregation.c.
◆ DEFAULT_AGGRTOL
#define DEFAULT_AGGRTOL 1e-2 |
aggregation heuristic: we try to delete continuous variables from the current aggregation, whose distance to its tightest bound is >= L - DEFAULT_AGGRTOL, where L is the largest of the distances between a continuous variable's value and its tightest bound in the current aggregation
Definition at line 109 of file sepa_aggregation.c.
◆ DEFAULT_TRYNEGSCALING
#define DEFAULT_TRYNEGSCALING TRUE |
should negative values also be tested in scaling?
Definition at line 116 of file sepa_aggregation.c.
◆ DEFAULT_FIXINTEGRALRHS
#define DEFAULT_FIXINTEGRALRHS TRUE |
should an additional variable be complemented if f0 = 0?
Definition at line 117 of file sepa_aggregation.c.
◆ DEFAULT_DYNAMICCUTS
#define DEFAULT_DYNAMICCUTS TRUE |
should generated cuts be removed from the LP if they are no longer tight?
Definition at line 118 of file sepa_aggregation.c.
◆ BOUNDSWITCH
#define BOUNDSWITCH 0.5 |
Definition at line 120 of file sepa_aggregation.c.
Referenced by aggregation().
◆ POSTPROCESS
#define POSTPROCESS TRUE |
Definition at line 121 of file sepa_aggregation.c.
Referenced by aggregation().
◆ USEVBDS
#define USEVBDS TRUE |
Definition at line 122 of file sepa_aggregation.c.
Referenced by aggregation().
◆ MINFRAC
#define MINFRAC 0.05 |
Definition at line 123 of file sepa_aggregation.c.
Referenced by aggregation().
◆ MAXFRAC
#define MAXFRAC 0.999 |
Definition at line 124 of file sepa_aggregation.c.
Referenced by aggregation().
◆ MAKECONTINTEGRAL
#define MAKECONTINTEGRAL FALSE |
Definition at line 125 of file sepa_aggregation.c.
Referenced by addCut().
◆ IMPLINTSARECONT
#define IMPLINTSARECONT |
Definition at line 126 of file sepa_aggregation.c.
Typedef Documentation
◆ AGGREGATIONDATA
typedef struct AggregationData AGGREGATIONDATA |
data used for aggregation of row
Function Documentation
◆ addCut()
|
static |
adds given cut to LP if violated
- Parameters
-
scip SCIP data structure sol the solution that should be separated, or NULL for LP solution sepa separator makeintegral should cut be scaled to integral coefficients if possible? cutcoefs coefficients of active variables in cut cutinds problem indices of variables in cut cutnnz number of non-zeros in cut cutrhs right hand side of cut cutefficacy efficacy of cut cutislocal is the cut only locally valid? cutremovable should the cut be removed from the LP due to aging or cleanup? cutrank rank of the cut cutclassname name of cut class to use for row names cutoff whether a cutoff has been detected ncuts pointer to count the number of added cuts thecut pointer to return cut if it was added
Definition at line 195 of file sepa_aggregation.c.
References FALSE, MAKECONTINTEGRAL, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPdebug, SCIPdebugMsg, SCIPepsilon(), SCIPflushRowExtensions(), SCIPgetNLPs(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetRowNumIntCols(), SCIPgetVars(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisCutNew(), SCIPisEfficacious(), SCIPisInfinity(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIPsnprintf(), SCIPsumepsilon(), and setupAggregationData().
Referenced by aggregation().
◆ setupAggregationData()
|
static |
setup data for aggregating rows
- Parameters
-
scip SCIP data structure sol solution to separate, NULL for LP solution allowlocal should local cuts be allowed aggrdata pointer to aggregation data to setup
Definition at line 318 of file sepa_aggregation.c.
References AggregationData::aggrrow, AggregationData::aggrrows, AggregationData::aggrrowscoef, AggregationData::aggrrowssize, AggregationData::aggrrowsstart, BMSclearMemoryArray, AggregationData::bounddist, AggregationData::bounddistinds, destroyAggregationData(), MAX, AggregationData::naggrrows, AggregationData::nbadvarsinrow, AggregationData::nbounddistvars, AggregationData::ngoodaggrrows, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPallocBufferArray, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPgetLPRowsData(), SCIPgetSolVal(), SCIPgetVarClosestVlb(), SCIPgetVarClosestVub(), SCIPgetVarsData(), SCIPisEQ(), SCIPisZero(), SCIPreallocBufferArray, SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPswapPointers(), SCIPswapReals(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and SCIPvarIsInLP().
Referenced by addCut(), and separateCuts().
◆ destroyAggregationData()
|
static |
free resources held in aggregation data
- Parameters
-
scip SCIP datastructure aggrdata pointer to ggregation data
Definition at line 503 of file sepa_aggregation.c.
Referenced by separateCuts(), and setupAggregationData().
◆ getRowAggregationCandidates()
|
static |
retrieves the candidate rows for canceling out the given variable, also returns the number of "good" rows which are the rows stored at the first ngoodrows positions. A row is good if its continuous variables are all at their bounds, except maybe the given continuous variable (in probvaridx)
- Parameters
-
aggrdata pointer to ggregation data probvaridx problem index of variables to retrieve candidates for rows pointer to store array to candidate rows rowvarcoefs pointer to store array of coefficients of given variable in the corresponding rows nrows pointer to return number of rows in returned arrays ngoodrows pointer to return number of "good" rows in the returned arrays
Definition at line 523 of file sepa_aggregation.c.
References aggrdataGetBoundDist(), AggregationData::aggrrows, AggregationData::aggrrowscoef, AggregationData::aggrrowsstart, AggregationData::bounddistinds, FALSE, AggregationData::nbounddistvars, AggregationData::ngoodaggrrows, SCIP_Real, SCIPsortedvecFindInt(), and TRUE.
Referenced by aggregateNextRow().
◆ aggrdataGetBoundDist()
|
static |
find the bound distance value in the aggregation data struct for the given variable problem index
- Parameters
-
aggrdata SCIP datastructure probvaridx problem index of variables to retrieve candidates for
Definition at line 547 of file sepa_aggregation.c.
Referenced by aggregateNextRow(), and getRowAggregationCandidates().
◆ aggregateNextRow()
|
static |
Aggregates the next row suitable for cancelling out an active continuous variable.
Equality rows that contain no other active continuous variables are preffered and apart from that the scores for the rows are used to determine which row is aggregated next
- Parameters
-
scip SCIP data structure sepadata separator data rowlhsscores aggregation scores for left hand sides of row rowrhsscores aggregation scores for right hand sides of row aggrdata aggregation data aggrrow current aggregation row naggrs pointer to increase counter if real aggregation took place success pointer to return whether another row was added to the aggregation row
Definition at line 566 of file sepa_aggregation.c.
References aggrdataGetBoundDist(), aggregation(), FALSE, getRowAggregationCandidates(), MAX, AggregationData::nbadvarsinrow, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPaggrRowAddRow(), SCIPaggrRowGetInds(), SCIPaggrRowGetNNz(), SCIPaggrRowGetProbvarValue(), SCIPaggrRowHasRowBeenAdded(), SCIPaggrRowRemoveZeros(), SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPisEQ(), SCIPisFeasZero(), SCIPisGT(), SCIPisInfinity(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), and SCIPsortDownRealInt().
Referenced by aggregation().
◆ aggregation()
|
static |
aggregates different single mixed integer constraints by taking linear combinations of the rows of the LP
- Parameters
-
scip SCIP data structure aggrdata pointer to aggregation data sepa separator sol the solution that should be separated, or NULL for LP solution allowlocal should local cuts be allowed rowlhsscores aggregation scores for left hand sides of row rowrhsscores aggregation scores for right hand sides of row startrow index of row to start aggregation; -1 for using the objective cutoff constraint maxaggrs maximal number of aggregations wastried pointer to store whether the given startrow was actually tried cutoff whether a cutoff has been detected cutinds buffer array to store temporarily cut cutcoefs buffer array to store temporarily cut negate should the start row be multiplied by -1 ncuts pointer to count the number of generated cuts
Definition at line 793 of file sepa_aggregation.c.
References addCut(), aggregateNextRow(), AggregationData::aggrrow, BOUNDSWITCH, FALSE, getRowFracActivity(), MAXFRAC, MINFRAC, NULL, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaggrRowAddObjectiveFunction(), SCIPaggrRowAddRow(), SCIPaggrRowClear(), SCIPaggrRowGetNNz(), SCIPaggrRowGetNRows(), SCIPaggrRowGetRowInds(), SCIPcalcFlowCover(), SCIPcalcKnapsackCover(), SCIPcutGenerationHeuristicCMIR(), SCIPdebugMsg, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPgetRowSolActivity(), SCIPgetUpperbound(), SCIPinfinity(), SCIPisObjIntegral(), SCIPreleaseRow(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetParallelism(), SCIProwGetRhs(), SCIPsepaGetData(), TRUE, and USEVBDS.
Referenced by aggregateNextRow(), and separateCuts().
◆ getRowFracActivity()
gives an estimate of how much the activity of this row is affected by fractionality in the current solution
- Parameters
-
row the LP row fractionalities array of fractionalities for each variable
Definition at line 1040 of file sepa_aggregation.c.
Referenced by aggregation(), and separateCuts().
◆ separateCuts()
|
static |
searches for and adds c-MIR cuts that separate the given primal solution
- Parameters
-
scip SCIP data structure sepa the c-MIR separator sol the solution that should be separated, or NULL for LP solution allowlocal should local cuts be allowed depth current depth result pointer to store the result
Definition at line 1066 of file sepa_aggregation.c.
References aggregation(), destroyAggregationData(), FALSE, getRowFracActivity(), MAX, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_SEPACOPY(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPdebugMsg, SCIPfeasFrac(), SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetLPRowsData(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNSepaRounds(), SCIPgetNVars(), SCIPgetObjNorm(), SCIPgetRowSolActivity(), SCIPgetSolVals(), SCIPgetVarClosestVlb(), SCIPgetVarClosestVub(), SCIPgetVars(), SCIPisEQ(), SCIPisInfinity(), SCIPisLE(), SCIPisPositive(), SCIPisStopped(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetNorm(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsepaGetData(), SCIPsepaGetFreq(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsortDownRealInt(), SCIPvarGetProbindex(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubVars(), SEPA_NAME, setupAggregationData(), and TRUE.
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 1438 of file sepa_aggregation.c.
Referenced by separateCuts().
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 1452 of file sepa_aggregation.c.
◆ SCIP_DECL_SEPAEXECLP() [1/2]
|
static |
LP solution separation method of separator
Definition at line 1469 of file sepa_aggregation.c.
◆ SCIP_DECL_SEPAEXECSOL() [1/2]
|
static |
arbitrary primal solution separation method of separator
Definition at line 1494 of file sepa_aggregation.c.
◆ SCIP_DECL_SEPAEXECLP() [2/2]
|
static |
LP solution separation method of dummy separator
Definition at line 1507 of file sepa_aggregation.c.
References NULL, and SCIP_DIDNOTRUN.
◆ SCIP_DECL_SEPAEXECSOL() [2/2]
|
static |
arbitrary primal solution separation method of dummy separator
Definition at line 1518 of file sepa_aggregation.c.