Detailed Description

ensemble cut selector

Author: Mark Turner

#include <assert.h>
#include "scip/scip_cutsel.h"
#include "scip/scip_cut.h"
#include "scip/scip_lp.h"
#include "scip/scip_randnumgen.h"
#include "scip/cutsel_ensemble.h"

Go to the source code of this file.

Macros
#define	CUTSEL_NAME "ensemble"

#define	CUTSEL_DESC "weighted sum of many terms with optional filtering and penalties"

#define	CUTSEL_PRIORITY 7000

#define	RANDSEED 0x5EED

#define	DEFAULT_MINSCORE 0.0

#define	DEFAULT_EFFICACYWEIGHT 0.75

#define	DEFAULT_DIRCUTOFFDISTWEIGHT 0.0

#define	DEFAULT_OBJPARALWEIGHT 0.25

#define	DEFAULT_INTSUPPORTWEIGHT 0.45

#define	DEFAULT_EXPIMPROVWEIGHT 0.1

#define	DEFAULT_PSCOSTWEIGHT 0.75

#define	DEFAULT_NLOCKSWEIGHT 0.25

#define	DEFAULT_MAXSPARSITYBONUS 0.5

#define	DEFAULT_SPARSITYENDBONUS 0.2

#define	DEFAULT_GOODNUMERICBONUS 0.0

#define	DEFAULT_MAXCOEFRATIOBONUS 10000

#define	DEFAULT_PENALISELOCKS TRUE

#define	DEFAULT_PENALISEOBJPARAL TRUE

#define	DEFAULT_FILTERPARALCUTS FALSE

#define	DEFAULT_MAXPARAL 0.95

#define	DEFAULT_PENALISEPARALCUTS TRUE

#define	DEFAULT_PARALPENALTY 0.25

#define	DEFAULT_FILTERDENSECUTS TRUE

#define	DEFAULT_MAXCUTDENSITY 0.425

#define	DEFAULT_MAXNONZEROROOTROUND 4.5

#define	DEFAULT_MAXNONZEROTREEROUND 9.5

#define	DEFAULT_MAXCUTS 200

#define	DEFAULT_MAXNUMVARS 50000

Functions
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	filterWithParallelism (SCIP_ROW cut, SCIP_ROW cuts, SCIP_Real scores, int ncuts, SCIP_Real maxparallel)

static int	penaliseWithParallelism (SCIP scip, SCIP_ROW cut, SCIP_ROW *cuts, SCIP_Real scores, int ncuts, SCIP_Real maxparallel, SCIP_Real paralpenalty)

static int	filterWithDensity (SCIP scip, SCIP_ROW *cuts, SCIP_Real maxdensity, int ncuts)

static	SCIP_DECL_CUTSELCOPY (cutselCopyEnsemble)

static	SCIP_DECL_CUTSELFREE (cutselFreeEnsemble)

static	SCIP_DECL_CUTSELINIT (cutselInitEnsemble)

static	SCIP_DECL_CUTSELEXIT (cutselExitEnsemble)

static	SCIP_DECL_CUTSELSELECT (cutselSelectEnsemble)

SCIP_RETCODE	SCIPincludeCutselEnsemble (SCIP *scip)

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)

Macro Definition Documentation

◆ CUTSEL_NAME

#define CUTSEL_NAME "ensemble"

Definition at line 45 of file cutsel_ensemble.c.

◆ CUTSEL_DESC

#define CUTSEL_DESC "weighted sum of many terms with optional filtering and penalties"

Definition at line 46 of file cutsel_ensemble.c.

◆ CUTSEL_PRIORITY

#define CUTSEL_PRIORITY 7000

Definition at line 47 of file cutsel_ensemble.c.

◆ RANDSEED

#define RANDSEED 0x5EED

Definition at line 49 of file cutsel_ensemble.c.

◆ DEFAULT_MINSCORE

#define DEFAULT_MINSCORE 0.0

minimum score s.t. a cut can be selected

Definition at line 51 of file cutsel_ensemble.c.

◆ DEFAULT_EFFICACYWEIGHT

#define DEFAULT_EFFICACYWEIGHT 0.75

weight of normed-efficacy in score calculation

Definition at line 52 of file cutsel_ensemble.c.

◆ DEFAULT_DIRCUTOFFDISTWEIGHT

#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0

weight of normed-directed cutoff distance in score calculation

Definition at line 53 of file cutsel_ensemble.c.

◆ DEFAULT_OBJPARALWEIGHT

#define DEFAULT_OBJPARALWEIGHT 0.25

weight of objective parallelism in score calculation

Definition at line 54 of file cutsel_ensemble.c.

◆ DEFAULT_INTSUPPORTWEIGHT

#define DEFAULT_INTSUPPORTWEIGHT 0.45

weight of integral support in cut score calculation

Definition at line 55 of file cutsel_ensemble.c.

◆ DEFAULT_EXPIMPROVWEIGHT

#define DEFAULT_EXPIMPROVWEIGHT 0.1

weight of normed-expected improvement in cut score calculation

Definition at line 56 of file cutsel_ensemble.c.

◆ DEFAULT_PSCOSTWEIGHT

#define DEFAULT_PSCOSTWEIGHT 0.75

weight of normalised pseudo-costs in cut score calculation

Definition at line 57 of file cutsel_ensemble.c.

◆ DEFAULT_NLOCKSWEIGHT

#define DEFAULT_NLOCKSWEIGHT 0.25

weight of normalised number of locks in cut score calculation

Definition at line 58 of file cutsel_ensemble.c.

◆ DEFAULT_MAXSPARSITYBONUS

#define DEFAULT_MAXSPARSITYBONUS 0.5

score given to a cut with complete sparsity

Definition at line 59 of file cutsel_ensemble.c.

◆ DEFAULT_SPARSITYENDBONUS

#define DEFAULT_SPARSITYENDBONUS 0.2

the density at which a cut no longer receives additional score

Definition at line 60 of file cutsel_ensemble.c.

◆ DEFAULT_GOODNUMERICBONUS

#define DEFAULT_GOODNUMERICBONUS 0.0

bonus provided for good numerics

Definition at line 61 of file cutsel_ensemble.c.

◆ DEFAULT_MAXCOEFRATIOBONUS

#define DEFAULT_MAXCOEFRATIOBONUS 10000

maximum coefficient ratio of cut for which numeric bonus is given

Definition at line 62 of file cutsel_ensemble.c.

◆ DEFAULT_PENALISELOCKS

#define DEFAULT_PENALISELOCKS TRUE

whether having less locks should be rewarded instead of more

Definition at line 63 of file cutsel_ensemble.c.

◆ DEFAULT_PENALISEOBJPARAL

#define DEFAULT_PENALISEOBJPARAL TRUE

whether objective parallelism should be penalised not rewarded

Definition at line 64 of file cutsel_ensemble.c.

◆ DEFAULT_FILTERPARALCUTS

#define DEFAULT_FILTERPARALCUTS FALSE

should cuts be filtered so no two parallel cuts are added

Definition at line 65 of file cutsel_ensemble.c.

◆ DEFAULT_MAXPARAL

#define DEFAULT_MAXPARAL 0.95

threshold for when two cuts are considered parallel to each other

Definition at line 66 of file cutsel_ensemble.c.

◆ DEFAULT_PENALISEPARALCUTS

#define DEFAULT_PENALISEPARALCUTS TRUE

should two parallel cuts be penalised instead of outright filtered

Definition at line 67 of file cutsel_ensemble.c.

◆ DEFAULT_PARALPENALTY

#define DEFAULT_PARALPENALTY 0.25

penalty for weaker of two parallel cuts if penalising parallel cuts

Definition at line 68 of file cutsel_ensemble.c.

◆ DEFAULT_FILTERDENSECUTS

#define DEFAULT_FILTERDENSECUTS TRUE

should cuts over a given density threshold be filtered

Definition at line 69 of file cutsel_ensemble.c.

◆ DEFAULT_MAXCUTDENSITY

#define DEFAULT_MAXCUTDENSITY 0.425

max allowed cut density if filtering dense cuts

Definition at line 70 of file cutsel_ensemble.c.

◆ DEFAULT_MAXNONZEROROOTROUND

#define DEFAULT_MAXNONZEROROOTROUND 4.5

max nonzeros per round (root). Gets multiplied by num LP cols

Definition at line 71 of file cutsel_ensemble.c.

◆ DEFAULT_MAXNONZEROTREEROUND

#define DEFAULT_MAXNONZEROTREEROUND 9.5

max nonzeros per round (tree). Gets multiplied by num LP cols

Definition at line 72 of file cutsel_ensemble.c.

◆ DEFAULT_MAXCUTS

#define DEFAULT_MAXCUTS 200

maximum number of cuts that can be considered by this cut selector

Definition at line 73 of file cutsel_ensemble.c.

◆ DEFAULT_MAXNUMVARS

#define DEFAULT_MAXNUMVARS 50000

maximum number of variables that a problem can have while calling this cut selector

Definition at line 74 of file cutsel_ensemble.c.

Function Documentation

◆ scoring()

static SCIP_RETCODE scoring	(	SCIP *	scip,
		SCIP_ROW **	cuts,
		SCIP_CUTSELDATA *	cutseldata,
		SCIP_Real *	scores,
		SCIP_Bool	root,
		int	ncuts
	)

static

returns the maximum score of cuts; if scores is not NULL, then stores the individual score of each cut in scores

Parameters

scip	SCIP data structure
cuts	array with cuts to score
cutseldata	cut selector data
scores	array to store the score of cuts or NULL
root	whether we are at the root node or not
ncuts	number of cuts in cuts array

Definition at line 117 of file cutsel_ensemble.c.

References ABS, density, LOG1P, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPepsilon(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetCutEfficacy(), SCIPgetCutLPSolCutoffDistance(), SCIPgetNLPCols(), SCIPgetRowFeasibility(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetRowNumIntCols(), SCIPgetRowObjParallelism(), SCIPgetVarPseudocostScore(), SCIPisInfinity(), SCIPisSumLE(), SCIPrandomGetReal(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetNorm(), SCIProwGetRhs(), SCIProwGetVals(), SCIPsumepsilon(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), and SQR.

Referenced by SCIPselectCutsEnsemble().

◆ selectBestCut()

static void selectBestCut	(	SCIP_ROW **	cuts,
		SCIP_Real *	scores,
		int	ncuts
	)

static

move the cut with the highest score to the first position in the array; there must be at least one cut

Parameters

cuts	array with cuts to perform selection algorithm
scores	array with scores of cuts to perform selection algorithm
ncuts	number of cuts in given array

Definition at line 327 of file cutsel_ensemble.c.

References NULL, SCIP_Real, SCIPswapPointers(), and SCIPswapReals().

Referenced by SCIPselectCutsEnsemble().

◆ filterWithParallelism()

static int filterWithParallelism	(	SCIP_ROW *	cut,
		SCIP_ROW **	cuts,
		SCIP_Real *	scores,
		int	ncuts,
		SCIP_Real	maxparallel
	)

static

filters the given array of cuts to enforce a maximum parallelism constraint w.r.t the given cut; moves filtered cuts to the end of the array and returns number of selected cuts

Parameters

cut	cut to filter orthogonality with
cuts	array with cuts to perform selection algorithm
scores	array with scores of cuts to perform selection algorithm
ncuts	number of cuts in given array
maxparallel	maximal parallelism for all cuts that are not good

Definition at line 359 of file cutsel_ensemble.c.

References NULL, SCIP_Real, SCIProwGetParallelism(), SCIPswapPointers(), and SCIPswapReals().

Referenced by SCIPselectCutsEnsemble().

◆ penaliseWithParallelism()

static int penaliseWithParallelism	(	SCIP *	scip,
		SCIP_ROW *	cut,
		SCIP_ROW **	cuts,
		SCIP_Real *	scores,
		int	ncuts,
		SCIP_Real	maxparallel,
		SCIP_Real	paralpenalty
	)

static

penalises any cut too parallel to cut by reducing the parallel cut's score.

Parameters

scip	SCIP data structure
cut	cut to filter orthogonality with
cuts	array with cuts to perform selection algorithm
scores	array with scores of cuts to perform selection algorithm
ncuts	number of cuts in given array
maxparallel	maximal parallelism for all cuts that are not good
paralpenalty	penalty for weaker of two parallel cuts if penalising parallel cuts

Definition at line 390 of file cutsel_ensemble.c.

References NULL, SCIP_Real, SCIProwGetParallelism(), SCIPsumepsilon(), SCIPswapPointers(), and SCIPswapReals().

Referenced by SCIPselectCutsEnsemble().

◆ filterWithDensity()

static int filterWithDensity	(	SCIP *	scip,
		SCIP_ROW **	cuts,
		SCIP_Real	maxdensity,
		int	ncuts
	)

static

filters the given array of cuts to enforce a maximum density constraint, Moves filtered cuts to the end of the array and returns number of selected cuts

Parameters

scip	SCIP data structure
cuts	array with cuts to perform selection algorithm
maxdensity	maximum density s.t. a cut is not filtered
ncuts	number of cuts in given array

Definition at line 429 of file cutsel_ensemble.c.

References NULL, SCIP_Real, SCIPgetNLPCols(), SCIProwGetNNonz(), and SCIPswapPointers().

Referenced by SCIPselectCutsEnsemble().

◆ SCIP_DECL_CUTSELCOPY()

static SCIP_DECL_CUTSELCOPY ( cutselCopyEnsemble )

static

copy method for cut selector plugin (called when SCIP copies plugins)

Definition at line 466 of file cutsel_ensemble.c.

References CUTSEL_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPcutselGetName(), and SCIPincludeCutselEnsemble().

◆ SCIP_DECL_CUTSELFREE()

static SCIP_DECL_CUTSELFREE ( cutselFreeEnsemble )

static

destructor of cut selector to free user data (called when SCIP is exiting) ! [SnippetCutselFreeEnsemble]

Definition at line 481 of file cutsel_ensemble.c.

References NULL, SCIP_OKAY, SCIPcutselGetData(), SCIPcutselSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_CUTSELINIT()

static SCIP_DECL_CUTSELINIT ( cutselInitEnsemble )

static

! [SnippetCutselFreeEnsemble] initialization method of cut selector (called after problem was transformed)

Definition at line 497 of file cutsel_ensemble.c.

References NULL, RANDSEED, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPcutselGetData(), and TRUE.

◆ SCIP_DECL_CUTSELEXIT()

static SCIP_DECL_CUTSELEXIT ( cutselExitEnsemble )

static

deinitialization method of cut selector (called before transformed problem is freed)

Definition at line 511 of file cutsel_ensemble.c.

References NULL, SCIP_OKAY, SCIPcutselGetData(), and SCIPfreeRandom().

◆ SCIP_DECL_CUTSELSELECT()

static SCIP_DECL_CUTSELSELECT ( cutselSelectEnsemble )

static

cut selection method of cut selector

Definition at line 526 of file cutsel_ensemble.c.

References NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPcutselGetData(), SCIPgetNVars(), and SCIPselectCutsEnsemble().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ CUTSEL_NAME

◆ CUTSEL_DESC

◆ CUTSEL_PRIORITY

◆ RANDSEED

◆ DEFAULT_MINSCORE

◆ DEFAULT_EFFICACYWEIGHT

◆ DEFAULT_DIRCUTOFFDISTWEIGHT

◆ DEFAULT_OBJPARALWEIGHT

◆ DEFAULT_INTSUPPORTWEIGHT

◆ DEFAULT_EXPIMPROVWEIGHT

◆ DEFAULT_PSCOSTWEIGHT

◆ DEFAULT_NLOCKSWEIGHT

◆ DEFAULT_MAXSPARSITYBONUS

◆ DEFAULT_SPARSITYENDBONUS

◆ DEFAULT_GOODNUMERICBONUS

◆ DEFAULT_MAXCOEFRATIOBONUS

◆ DEFAULT_PENALISELOCKS

◆ DEFAULT_PENALISEOBJPARAL

◆ DEFAULT_FILTERPARALCUTS

◆ DEFAULT_MAXPARAL

◆ DEFAULT_PENALISEPARALCUTS

◆ DEFAULT_PARALPENALTY

◆ DEFAULT_FILTERDENSECUTS

◆ DEFAULT_MAXCUTDENSITY

◆ DEFAULT_MAXNONZEROROOTROUND

◆ DEFAULT_MAXNONZEROTREEROUND

◆ DEFAULT_MAXCUTS

◆ DEFAULT_MAXNUMVARS

Function Documentation

◆ scoring()

◆ selectBestCut()

◆ filterWithParallelism()

◆ penaliseWithParallelism()

◆ filterWithDensity()

◆ SCIP_DECL_CUTSELCOPY()

◆ SCIP_DECL_CUTSELFREE()

◆ SCIP_DECL_CUTSELINIT()

◆ SCIP_DECL_CUTSELEXIT()

◆ SCIP_DECL_CUTSELSELECT()