76#define SEPA_NAME "aggregation"
77#define SEPA_DESC "aggregation heuristic for complemented mixed integer rounding cuts and flowcover cuts"
78#define SEPA_PRIORITY -3000
80#define SEPA_MAXBOUNDDIST 1.0
81#define SEPA_USESSUBSCIP FALSE
82#define SEPA_DELAY FALSE
84#define DEFAULT_MAXROUNDS -1
85#define DEFAULT_MAXROUNDSROOT -1
86#define DEFAULT_MAXTRIES 200
88#define DEFAULT_MAXTRIESROOT -1
90#define DEFAULT_MAXFAILS 20
91#define DEFAULT_MAXFAILSROOT 100
93#define DEFAULT_MAXAGGRS 3
94#define DEFAULT_MAXAGGRSROOT 6
95#define DEFAULT_MAXSEPACUTS 100
96#define DEFAULT_MAXSEPACUTSROOT 500
97#define DEFAULT_MAXSLACK 0.0
98#define DEFAULT_MAXSLACKROOT 0.1
99#define DEFAULT_DENSITYSCORE 1e-4
100#define DEFAULT_SLACKSCORE 1e-3
101#define DEFAULT_MAXAGGDENSITY 0.20
102#define DEFAULT_MAXROWDENSITY 0.05
103#define DEFAULT_DENSITYOFFSET 100
104#define DEFAULT_MAXROWFAC 1e+4
105#define DEFAULT_MAXTESTDELTA -1
106#define DEFAULT_AGGRTOL 1e-2
110#define DEFAULT_TRYNEGSCALING TRUE
111#define DEFAULT_FIXINTEGRALRHS TRUE
112#define DEFAULT_DYNAMICCUTS TRUE
114#define BOUNDSWITCH 0.5
115#define POSTPROCESS TRUE
119#define MAKECONTINTEGRAL FALSE
120#define IMPLINTSARECONT
131 SCIP_Real maxslackroot;
132 SCIP_Real densityscore;
133 SCIP_Real slackscore;
134 SCIP_Real maxaggdensity;
135 SCIP_Real maxrowdensity;
154 SCIP_Bool trynegscaling;
155 SCIP_Bool fixintegralrhs;
156 SCIP_Bool dynamiccuts;
157 SCIP_Bool sepflowcover;
158 SCIP_Bool sepknapsackcover;
193 SCIP_Bool makeintegral,
257 makeintegral =
FALSE;
277 SCIPdebugMsg(
scip,
" -> found %s cut <%s>: rhs=%f, eff=%f, rank=%d, min=%f, max=%f (range=%g)\n",
315 SCIP_Bool allowlocal,
387 bounddist =
MAX(bounddist, 0.0);
471 if(
aggrdata->nbadvarsinrow[lppos] == 1 &&
597 for(
i = 0;
i < nnz; ++
i )
607 if( bounddist == 0.0 )
726 for(
k = 0;
k < nrows; ++
k )
792 SCIP_Bool allowlocal,
883 while(
naggrs <= maxaggrs )
941 SCIP_CALL(
SCIPcutGenerationHeuristicCMIR(
scip,
sol,
POSTPROCESS,
BOUNDSWITCH,
USEVBDS, allowlocal, maxtestdelta,
NULL,
NULL,
MINFRAC,
MAXFRAC,
989 for(
i = 0;
i < nrows; ++
i )
1010 SCIPdebugMsg(
scip,
" -> abort aggregation: maximal number of aggregations reached\n");
1023 SCIPdebugMsg(
scip,
" -> current aggregation has %d/%d nonzeros and consists of %d/%d rows\n",
1064 SCIP_Bool allowlocal,
1072 SCIP_Real* varsolvals;
1151#ifdef IMPLINTSARECONT
1192 for( ; v <
nvars; ++v )
1243 maxsepacuts =
sepadata->maxsepacutsroot;
1251 maxsepacuts =
sepadata->maxsepacuts;
1261 for(
r = 0;
r < nrows;
r++ )
1297 rownorm =
MAX(rownorm, 0.1);
1302 slack = (activity - lhs)/rownorm;
1314 slack = (rhs - activity)/rownorm;
1392 if( ncuts == oldncuts )
1420 else if ( ncuts > 0 )
1575 "maximal number of cmir separation rounds per node (-1: unlimited)",
1578 "separating/" SEPA_NAME "/maxroundsroot",
1579 "maximal number of cmir separation rounds in the root node (-1: unlimited)",
1583 "maximal number of rows to start aggregation with per separation round (-1: unlimited)",
1586 "separating/" SEPA_NAME "/maxtriesroot",
1587 "maximal number of rows to start aggregation with per separation round in the root node (-1: unlimited)",
1591 "maximal number of consecutive unsuccessful aggregation tries (-1: unlimited)",
1594 "separating/" SEPA_NAME "/maxfailsroot",
1595 "maximal number of consecutive unsuccessful aggregation tries in the root node (-1: unlimited)",
1599 "maximal number of aggregations for each row per separation round",
1602 "separating/" SEPA_NAME "/maxaggrsroot",
1603 "maximal number of aggregations for each row per separation round in the root node",
1607 "maximal number of cmir cuts separated per separation round",
1610 "separating/" SEPA_NAME "/maxsepacutsroot",
1611 "maximal number of cmir cuts separated per separation round in the root node",
1615 "maximal slack of rows to be used in aggregation",
1618 "separating/" SEPA_NAME "/maxslackroot",
1619 "maximal slack of rows to be used in aggregation in the root node",
1622 "separating/" SEPA_NAME "/densityscore",
1623 "weight of row density in the aggregation scoring of the rows",
1627 "weight of slack in the aggregation scoring of the rows",
1630 "separating/" SEPA_NAME "/maxaggdensity",
1631 "maximal density of aggregated row",
1634 "separating/" SEPA_NAME "/maxrowdensity",
1635 "maximal density of row to be used in aggregation",
1638 "separating/" SEPA_NAME "/densityoffset",
1639 "additional number of variables allowed in row on top of density",
1643 "maximal row aggregation factor",
1646 "separating/" SEPA_NAME "/maxtestdelta",
1647 "maximal number of different deltas to try (-1: unlimited)",
1651 "tolerance for bound distances used to select continuous variable in current aggregated constraint to be eliminated",
1654 "separating/" SEPA_NAME "/trynegscaling",
1655 "should negative values also be tested in scaling?",
1658 "separating/" SEPA_NAME "/fixintegralrhs",
1659 "should an additional variable be complemented if f0 = 0?",
1663 "should generated cuts be removed from the LP if they are no longer tight?",
methods for the aggregation rows
#define SCIP_LONGINT_FORMAT
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_Real SCIPgetObjNorm(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
void SCIPswapPointers(void **pointer1, void **pointer2)
void SCIPswapReals(SCIP_Real *value1, SCIP_Real *value2)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
int SCIPcolGetNLPNonz(SCIP_COL *col)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPaggrRowHasRowBeenAdded(SCIP_AGGRROW *aggrrow, SCIP_ROW *row)
SCIP_RETCODE SCIPcutGenerationHeuristicCMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxtestdelta, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_RETCODE SCIPcalcKnapsackCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
void SCIPaggrRowClear(SCIP_AGGRROW *aggrrow)
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
int SCIPaggrRowGetNRows(SCIP_AGGRROW *aggrrow)
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
int * SCIPaggrRowGetInds(SCIP_AGGRROW *aggrrow)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
void SCIPaggrRowRemoveZeros(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid)
int SCIPaggrRowGetNNz(SCIP_AGGRROW *aggrrow)
SCIP_RETCODE SCIPaggrRowAddRow(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype)
static INLINE SCIP_Real SCIPaggrRowGetProbvarValue(SCIP_AGGRROW *aggrrow, int probindex)
int * SCIPaggrRowGetRowInds(SCIP_AGGRROW *aggrrow)
SCIP_RETCODE SCIPaggrRowAddObjectiveFunction(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale)
SCIP_RETCODE SCIPcalcFlowCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
int SCIPgetNLPCols(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
int SCIProwGetNLPNonz(SCIP_ROW *row)
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
int SCIProwGetRank(SCIP_ROW *row)
void SCIProwChgRank(SCIP_ROW *row, int rank)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
int SCIPsepaGetFreq(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
void SCIPsetSepaIsParentsepa(SCIP *scip, SCIP_SEPA *sepa)
void SCIPsetSepaParentsepa(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
int SCIPgetNSepaRounds(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPgetVarClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvub, int *closestvubidx)
int SCIPvarGetProbindex(SCIP_VAR *var)
SCIP_RETCODE SCIPgetVarClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvlb, int *closestvlbidx)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
SCIP_RETCODE SCIPincludeSepaAggregation(SCIP *scip)
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_Real negate(SCIP_Real x)
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for separator plugins
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
struct AggregationData AGGREGATIONDATA
#define DEFAULT_SLACKSCORE
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)
#define DEFAULT_DYNAMICCUTS
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)
#define DEFAULT_MAXSLACKROOT
#define DEFAULT_MAXFAILSROOT
#define DEFAULT_MAXAGGRSROOT
#define DEFAULT_MAXROUNDSROOT
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)
#define DEFAULT_TRYNEGSCALING
#define DEFAULT_MAXTRIESROOT
#define DEFAULT_MAXROWFAC
#define DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_DENSITYSCORE
#define DEFAULT_DENSITYOFFSET
#define DEFAULT_FIXINTEGRALRHS
static SCIP_RETCODE setupAggregationData(SCIP *scip, SCIP_SOL *sol, SCIP_Bool allowlocal, AGGREGATIONDATA *aggrdata)
#define DEFAULT_MAXTESTDELTA
#define SEPA_MAXBOUNDDIST
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXAGGDENSITY
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)
#define DEFAULT_MAXROUNDS
static void destroyAggregationData(SCIP *scip, AGGREGATIONDATA *aggrdata)
#define DEFAULT_MAXROWDENSITY
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, int depth, SCIP_RESULT *result)
flow cover and complemented mixed integer rounding cuts separator (Marchand's version)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAEXECSOL(x)
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPAFREE(x)
#define SCIP_DECL_SEPACOPY(x)