Detailed Description

dynamic cut selector

Author: Christoph Graczyk

#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_dynamic.h"

Go to the source code of this file.

Macros
#define	CUTSEL_NAME "dynamic"

#define	CUTSEL_DESC "dynamic orthogonality for hybrid cutsel"

#define	CUTSEL_PRIORITY 7000

#define	RANDSEED 0x5EED

#define	DEFAULT_EFFICACYWEIGHT 1.0

#define	DEFAULT_DIRCUTOFFDISTWEIGHT 0.0

#define	DEFAULT_OBJPARALWEIGHT 0.0

#define	DEFAULT_INTSUPPORTWEIGHT 0.0

#define	DEFAULT_MINORTHO 0.9

#define	DEFAULT_MINGAIN 0.01

#define	DEFAULT_MAXDEPTH (-1)

#define	DEFAULT_FILTERMODE 'd'

Functions
static void	scoring (SCIP scip, SCIP_ROW cuts, SCIP_RANDNUMGEN randnumgen, SCIP_Real dircutoffdistweight, SCIP_Real efficacyweight, SCIP_Real objparalweight, SCIP_Real intsupportweight, int currentncuts, SCIP_Real scores)

static SCIP_RETCODE	computeProjectionScore (SCIP scip, SCIP_ROW bestcut, SCIP_ROW cut, SCIP_Real score)

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

static int	filterWithDynamicParallelism (SCIP scip, SCIP_ROW bestcut, SCIP_ROW *cuts, SCIP_Real scores, SCIP_Real mingain, SCIP_Real maxparall, int ncuts)

static	SCIP_DECL_CUTSELCOPY (cutselCopyDynamic)

static	SCIP_DECL_CUTSELFREE (cutselFreeDynamic)

static	SCIP_DECL_CUTSELINIT (cutselInitDynamic)

static	SCIP_DECL_CUTSELEXIT (cutselExitDynamic)

static	SCIP_DECL_CUTSELSELECT (cutselSelectDynamic)

SCIP_RETCODE	SCIPincludeCutselDynamic (SCIP *scip)

SCIP_RETCODE	SCIPselectCutsDynamic (SCIP scip, SCIP_ROW cuts, SCIP_ROW forcedcuts, SCIP_RANDNUMGEN randnumgen, char filtermode, SCIP_Real mingain, SCIP_Real maxparall, SCIP_Real dircutoffdistweight, SCIP_Real efficacyweight, SCIP_Real objparalweight, SCIP_Real intsupportweight, int ncuts, int nforcedcuts, int maxselectedcuts, int *nselectedcuts)

Macro Definition Documentation

◆ CUTSEL_NAME

#define CUTSEL_NAME "dynamic"

Definition at line 43 of file cutsel_dynamic.c.

Referenced by SCIP_DECL_CUTSELCOPY(), and SCIPincludeCutselDynamic().

◆ CUTSEL_DESC

#define CUTSEL_DESC "dynamic orthogonality for hybrid cutsel"

Definition at line 44 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

◆ CUTSEL_PRIORITY

#define CUTSEL_PRIORITY 7000

Definition at line 45 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

◆ RANDSEED

#define RANDSEED 0x5EED

Definition at line 47 of file cutsel_dynamic.c.

Referenced by SCIP_DECL_CUTSELINIT().

◆ DEFAULT_EFFICACYWEIGHT

#define DEFAULT_EFFICACYWEIGHT 1.0

weight of efficacy in score calculation

Definition at line 49 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

◆ DEFAULT_DIRCUTOFFDISTWEIGHT

#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0

weight of directed cutoff distance in score calculation

Definition at line 50 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

◆ DEFAULT_OBJPARALWEIGHT

#define DEFAULT_OBJPARALWEIGHT 0.0

weight of objective parallelism in score calculation

Definition at line 51 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

◆ DEFAULT_INTSUPPORTWEIGHT

#define DEFAULT_INTSUPPORTWEIGHT 0.0

weight of integral support in cut score calculation

Definition at line 52 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

◆ DEFAULT_MINORTHO

#define DEFAULT_MINORTHO 0.9

minimal orthogonality in percent for a cut to enter the LP

Definition at line 53 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

◆ DEFAULT_MINGAIN

#define DEFAULT_MINGAIN 0.01

minimal efficacy gain for a cut to enter the LP

Definition at line 54 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

◆ DEFAULT_MAXDEPTH

#define DEFAULT_MAXDEPTH (-1)

maximum depth at which this cutselector is used (-1 : all nodes)

Definition at line 55 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

◆ DEFAULT_FILTERMODE

#define DEFAULT_FILTERMODE 'd'

filtering strategy during cut selection ( 'd'ynamic- and 'f'ull dynamic parallelism)

Definition at line 56 of file cutsel_dynamic.c.

Referenced by SCIPincludeCutselDynamic().

Function Documentation

◆ scoring()

static void scoring	(	SCIP *	scip,
		SCIP_ROW **	cuts,
		SCIP_RANDNUMGEN *	randnumgen,
		SCIP_Real	dircutoffdistweight,
		SCIP_Real	efficacyweight,
		SCIP_Real	objparalweight,
		SCIP_Real	intsupportweight,
		int *	currentncuts,
		SCIP_Real *	scores
	)

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
randnumgen	random number generator for tie-breaking, or NULL
dircutoffdistweight	weight of directed cutoff distance in cut score calculation
efficacyweight	weight of efficacy in cut score calculation
objparalweight	weight of objective parallelism in cut score calculation
intsupportweight	weight of integral support in cut score calculation
currentncuts	current number of cuts in cuts array
scores	array to store the score of cuts or NULL

Definition at line 88 of file cutsel_dynamic.c.

References computeProjectionScore(), MAX, NULL, SCIP_Real, SCIPgetBestSol(), SCIPgetCutEfficacy(), SCIPgetCutLPSolCutoffDistance(), SCIPgetRowNumIntCols(), SCIPgetRowObjParallelism(), SCIPisLE(), SCIPrandomGetReal(), SCIProwGetNNonz(), SCIProwIsInGlobalCutpool(), SCIProwIsLocal(), SCIPswapPointers(), and SCIPswapReals().

Referenced by SCIPselectCutsDynamic().

◆ computeProjectionScore()

static SCIP_RETCODE computeProjectionScore	(	SCIP *	scip,
		SCIP_ROW *	bestcut,
		SCIP_ROW *	cut,
		SCIP_Real *	score
	)

static

compute projectioncut score for cuts from a given bestcut.

Parameters

scip	SCIP data structure
bestcut	cut to filter orthogonality with
cut	cut to perform scoring on
score	score for cut

Definition at line 224 of file cutsel_dynamic.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetCutEfficacy(), SCIPinfinity(), SCIPisEQ(), SCIProwGetName(), SCIProwGetParallelism(), and selectBestCut().

Referenced by SCIPselectCutsDynamic(), and scoring().

◆ 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 258 of file cutsel_dynamic.c.

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

Referenced by computeProjectionScore(), and SCIPselectCutsDynamic().

◆ filterWithDynamicParallelism()

static int filterWithDynamicParallelism	(	SCIP *	scip,
		SCIP_ROW *	bestcut,
		SCIP_ROW **	cuts,
		SCIP_Real *	scores,
		SCIP_Real	mingain,
		SCIP_Real	maxparall,
		int	ncuts
	)

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

scip	SCIP data structure
bestcut	cut to filter orthogonality with
cuts	array with cuts to perform selection algorithm
scores	array with scores of cuts to perform selection algorithm
mingain	minimum gain enforced on the two-cut efficacy
maxparall	maximal parallelism for all cuts that are not good
ncuts	number of cuts in given array