45#define CUTSEL_NAME "ensemble"
46#define CUTSEL_DESC "weighted sum of many terms with optional filtering and penalties"
47#define CUTSEL_PRIORITY 7000
49#define RANDSEED 0x5EED
51#define DEFAULT_MINSCORE 0.0
52#define DEFAULT_EFFICACYWEIGHT 0.75
53#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0
54#define DEFAULT_OBJPARALWEIGHT 0.25
55#define DEFAULT_INTSUPPORTWEIGHT 0.45
56#define DEFAULT_EXPIMPROVWEIGHT 0.1
57#define DEFAULT_PSCOSTWEIGHT 0.75
58#define DEFAULT_NLOCKSWEIGHT 0.25
59#define DEFAULT_MAXSPARSITYBONUS 0.5
60#define DEFAULT_SPARSITYENDBONUS 0.2
61#define DEFAULT_GOODNUMERICBONUS 0.0
62#define DEFAULT_MAXCOEFRATIOBONUS 10000
63#define DEFAULT_PENALISELOCKS TRUE
64#define DEFAULT_PENALISEOBJPARAL TRUE
65#define DEFAULT_FILTERPARALCUTS FALSE
66#define DEFAULT_MAXPARAL 0.95
67#define DEFAULT_PENALISEPARALCUTS TRUE
68#define DEFAULT_PARALPENALTY 0.25
69#define DEFAULT_FILTERDENSECUTS TRUE
70#define DEFAULT_MAXCUTDENSITY 0.425
71#define DEFAULT_MAXNONZEROROOTROUND 4.5
72#define DEFAULT_MAXNONZEROTREEROUND 9.5
73#define DEFAULT_MAXCUTS 200
74#define DEFAULT_MAXNUMVARS 50000
85 SCIP_Real objparalweight;
86 SCIP_Real efficacyweight;
87 SCIP_Real dircutoffdistweight;
88 SCIP_Real expimprovweight;
89 SCIP_Real intsupportweight;
90 SCIP_Real pscostweight;
91 SCIP_Real locksweight;
92 SCIP_Real maxsparsitybonus;
93 SCIP_Real goodnumericsbonus;
94 SCIP_Real endsparsitybonus;
96 SCIP_Real paralpenalty;
97 SCIP_Real maxcutdensity;
98 SCIP_Real maxnonzerorootround;
99 SCIP_Real maxnonzerotreeround;
100 SCIP_Bool filterparalcuts;
101 SCIP_Bool penaliseparalcuts;
102 SCIP_Bool filterdensecuts;
103 SCIP_Bool penaliselocks;
104 SCIP_Bool penaliseobjparal;
105 int maxcoefratiobonus;
129 SCIP_Real* cutdensities;
133 SCIP_Real maxdcd = 0.0;
134 SCIP_Real maxeff = 0.0;
135 SCIP_Real maxexp = 0.0;
136 SCIP_Real maxpscost = 0.0;
137 SCIP_Real maxlocks = 0.0;
153 for (
int i = 0;
i < ncuts; ++
i )
157 SCIP_Real sqrcutnorm;
166 cutdensities[
i] = ncutcols / ncols;
170 for (
int j = 0; j < (int) ncutcols; ++j )
189 l1dist =
ABS(colval - (cutalpha * cutvals[j]));
192 cutlocks[
i] = cutlocks[
i] / ncutcols;
194 if( cutlocks[
i] > maxlocks )
195 maxlocks = cutlocks[
i];
197 if( pscosts[
i] > maxpscost )
198 maxpscost = pscosts[
i];
203 maxlocks =
MAX(maxlocks, 1);
205 for (
int i = 0;
i < ncuts;
i++ )
207 cutlocks[
i] = cutlocks[
i] / maxlocks;
209 if( cutseldata->penaliselocks )
210 cutlocks[
i] = 1 - cutlocks[
i];
211 pscosts[
i] = pscosts[
i] / maxpscost;
217 for (
int i = 0;
i < ncuts;
i++ )
220 maxdcd =
MAX(maxdcd, dcds[
i]);
224 for (
int i = 0;
i < ncuts; ++
i )
228 maxeff =
MAX(maxeff, effs[
i]);
229 maxexp =
MAX(maxexp, exps[
i]);
233 for (
int i = 0;
i < ncuts; ++
i )
239 SCIP_Real objparallelism;
240 SCIP_Real intsupport;
250 intsupport *= cutseldata->intsupportweight;
253 if( ! cutseldata->penaliseobjparal )
259 density = (cutseldata->maxsparsitybonus / cutseldata->endsparsitybonus) * -1 * cutdensities[
i];
260 density += cutseldata->maxsparsitybonus;
267 pscost = cutseldata->pscostweight * pscosts[
i];
268 cutlock = cutseldata->locksweight * cutlocks[
i];
273 mincutval = mincutval > 0.0 ? mincutval : 1.0;
274 dynamism = cutseldata->maxcoefratiobonus >= maxcutval / mincutval ? cutseldata->goodnumericsbonus : 0.0;
282 scaleddcd = cutseldata->dircutoffdistweight *
SQR(
LOG1P(dcds[
i]) /
LOG1P(maxdcd));
292 scaledexp = cutseldata->expimprovweight *
SQR(
LOG1P(exps[
i]) /
LOG1P(maxexp));
301 scaledeff = cutseldata->efficacyweight *
SQR(
LOG1P(effs[
i]) /
LOG1P(maxeff));
303 scaledeff = (cutseldata->efficacyweight + cutseldata->dircutoffdistweight) *
SQR(
LOG1P(effs[
i]) /
LOG1P(maxeff));
307 score = scaledeff + scaleddcd + scaledexp + objparallelism + intsupport +
density + dynamism + pscost + cutlock;
340 bestscore = scores[0];
343 for(
int i = 1;
i < ncuts; ++
i )
345 if( scores[
i] > bestscore )
348 bestscore = scores[
i];
364 SCIP_Real maxparallel
371 for(
int i = ncuts - 1;
i >= 0; --
i )
373 SCIP_Real thisparallel;
377 if( thisparallel > maxparallel )
396 SCIP_Real maxparallel,
397 SCIP_Real paralpenalty
404 for(
int i = ncuts - 1;
i >= 0; --
i )
406 SCIP_Real thisparallel;
417 else if( thisparallel > maxparallel )
419 scores[
i] -= paralpenalty;
432 SCIP_Real maxdensity,
442 for(
int i = ncuts - 1;
i >= 0; --
i )
448 if( maxdensity < nvals / ncols )
536 if( ncuts > cutseldata->maxcuts ||
SCIPgetNVars(
scip) > cutseldata->maxnumvars )
545 maxnselectedcuts, nselectedcuts) );
585 "cutoff distance in cut score calculation", &cutseldata->dircutoffdistweight,
FALSE,
616 "(ratio of coefficients) in cut score calculation", &cutseldata->goodnumericsbonus,
FALSE,
634 "applied cuts (root). multiple num LP cols.", &cutseldata->maxnonzerorootround,
FALSE,
638 "applied cuts (tree). multiple num LP cols.", &cutseldata->maxnonzerotreeround,
FALSE,
694 SCIP_Real* origscoresptr;
695 SCIP_Real nonzerobudget;
696 SCIP_Real budgettaken = 0.0;
700 assert(forcedcuts !=
NULL || nforcedcuts == 0);
707 if( cutseldata->filterdensecuts )
716 origscoresptr = scores;
726 if( cutseldata->filterparalcuts )
728 else if( cutseldata->penaliseparalcuts )
733 nonzerobudget = root ? cutseldata->maxnonzerorootround : cutseldata->maxnonzerotreeround;
741 selectedcut = cuts[0];
744 if( scores[0] < cutseldata->minscore )
750 if( *nselectedcuts == maxselectedcuts )
761 if( cutseldata->filterparalcuts && ncuts > 0)
763 else if( cutseldata->penaliseparalcuts && ncuts > 0 )
767 if( nonzerobudget - budgettaken < 1 && ncuts > 0 )
#define DEFAULT_SPARSITYENDBONUS
#define DEFAULT_EFFICACYWEIGHT
#define DEFAULT_MAXNONZEROTREEROUND
#define DEFAULT_OBJPARALWEIGHT
#define DEFAULT_FILTERDENSECUTS
#define DEFAULT_MAXSPARSITYBONUS
#define DEFAULT_PARALPENALTY
#define DEFAULT_PENALISEPARALCUTS
#define DEFAULT_GOODNUMERICBONUS
#define DEFAULT_PENALISELOCKS
#define DEFAULT_NLOCKSWEIGHT
static SCIP_RETCODE scoring(SCIP *scip, SCIP_ROW **cuts, SCIP_CUTSELDATA *cutseldata, SCIP_Real *scores, SCIP_Bool root, int ncuts)
static void selectBestCut(SCIP_ROW **cuts, SCIP_Real *scores, int ncuts)
static int filterWithDensity(SCIP *scip, SCIP_ROW **cuts, SCIP_Real maxdensity, int ncuts)
static int penaliseWithParallelism(SCIP *scip, SCIP_ROW *cut, SCIP_ROW **cuts, SCIP_Real *scores, int ncuts, SCIP_Real maxparallel, SCIP_Real paralpenalty)
static int filterWithParallelism(SCIP_ROW *cut, SCIP_ROW **cuts, SCIP_Real *scores, int ncuts, SCIP_Real maxparallel)
#define DEFAULT_EXPIMPROVWEIGHT
#define DEFAULT_MAXCOEFRATIOBONUS
#define DEFAULT_DIRCUTOFFDISTWEIGHT
#define DEFAULT_MAXCUTDENSITY
#define DEFAULT_MAXNONZEROROOTROUND
#define DEFAULT_PENALISEOBJPARAL
#define DEFAULT_MAXNUMVARS
#define DEFAULT_PSCOSTWEIGHT
#define DEFAULT_FILTERPARALCUTS
#define DEFAULT_INTSUPPORTWEIGHT
static const SCIP_Real density
SCIP_RETCODE SCIPselectCutsEnsemble(SCIP *scip, SCIP_ROW **cuts, SCIP_ROW **forcedcuts, SCIP_CUTSELDATA *cutseldata, SCIP_Bool root, int ncuts, int nforcedcuts, int maxselectedcuts, int *nselectedcuts)
SCIP_RETCODE SCIPincludeCutselEnsemble(SCIP *scip)
int SCIPgetNVars(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)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Real SCIPgetCutLPSolCutoffDistance(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPsetCutselInit(SCIP *scip, SCIP_CUTSEL *cutsel,)
SCIP_RETCODE SCIPincludeCutselBasic(SCIP *scip, SCIP_CUTSEL **cutsel, const char *name, const char *desc, int priority, SCIP_DECL_CUTSELSELECT((*cutselselect)), SCIP_CUTSELDATA *cutseldata)
SCIP_RETCODE SCIPsetCutselCopy(SCIP *scip, SCIP_CUTSEL *cutsel,)
SCIP_RETCODE SCIPsetCutselExit(SCIP *scip, SCIP_CUTSEL *cutsel,)
SCIP_CUTSELDATA * SCIPcutselGetData(SCIP_CUTSEL *cutsel)
void SCIPcutselSetData(SCIP_CUTSEL *cutsel, SCIP_CUTSELDATA *cutseldata)
const char * SCIPcutselGetName(SCIP_CUTSEL *cutsel)
SCIP_RETCODE SCIPsetCutselFree(SCIP *scip, SCIP_CUTSEL *cutsel,)
int SCIPgetNLPCols(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(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_Real SCIPgetRowFeasibility(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)
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
SCIP_Real SCIPgetRowObjParallelism(SCIP *scip, SCIP_ROW *row)
int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisSumLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
SCIP_Real SCIPgetVarPseudocostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
#define BMSclearMemory(ptr)
public methods for cuts and aggregation rows
public methods for cut selector plugins
public methods for the LP relaxation, rows and columns
public methods for random numbers
#define SCIP_DECL_CUTSELEXIT(x)
#define SCIP_DECL_CUTSELSELECT(x)
#define SCIP_DECL_CUTSELFREE(x)
struct SCIP_CutselData SCIP_CUTSELDATA
#define SCIP_DECL_CUTSELINIT(x)
#define SCIP_DECL_CUTSELCOPY(x)
enum SCIP_Retcode SCIP_RETCODE