Detailed Description

principal minor separator

Author: Benjamin Mueller

Definition in file sepa_minor.c.

#include "scip/sepa_minor.h"
#include "scip/cons_nonlinear.h"
#include "scip/lapack_calls.h"

Macros
#define	SEPA_NAME "minor"
#define	SEPA_DESC "separator to ensure that 2x2 principal minors of X - xx' are positive semi-definite"
#define	SEPA_PRIORITY 0
#define	SEPA_FREQ 10
#define	SEPA_MAXBOUNDDIST 1.0
#define	SEPA_USESSUBSCIP FALSE
#define	SEPA_DELAY FALSE
#define	DEFAULT_MAXMINORSCONST 3000
#define	DEFAULT_MAXMINORSFAC 10.0
#define	DEFAULT_MINCUTVIOL 1e-4
#define	DEFAULT_RANDSEED 157
#define	DEFAULT_MAXROUNDS 10
#define	DEFAULT_MAXROUNDSROOT -1
#define	DEFAULT_IGNOREPACKINGCONSS TRUE

Functions
static SCIP_RETCODE	sepadataAddMinor (SCIP scip, SCIP_SEPADATA sepadata, SCIP_VAR x, SCIP_VAR y, SCIP_VAR auxvarxx, SCIP_VAR auxvaryy, SCIP_VAR *auxvarxy)
static SCIP_RETCODE	sepadataClear (SCIP scip, SCIP_SEPADATA sepadata)
static SCIP_Bool	isPackingCons (SCIP scip, SCIP_CONS cons)
static SCIP_RETCODE	getMinorVars (SCIP_SEPADATA sepadata, int idx, SCIP_VAR x, SCIP_VAR y, SCIP_VAR auxvarxx, SCIP_VAR auxvaryy, SCIP_VAR *auxvarxy)
static SCIP_RETCODE	detectMinors (SCIP scip, SCIP_SEPADATA sepadata)
static SCIP_RETCODE	getEigenValues (SCIP scip, SCIP_Real x, SCIP_Real y, SCIP_Real xx, SCIP_Real yy, SCIP_Real xy, SCIP_Real eigenvals, SCIP_Real eigenvecs, SCIP_Bool success)
static SCIP_RETCODE	addCut (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, SCIP_VAR x, SCIP_VAR y, SCIP_VAR xx, SCIP_VAR yy, SCIP_VAR xy, SCIP_Real eigenvec, SCIP_Real eigenval, SCIP_Real mincutviol, SCIP_RESULT result)
static SCIP_RETCODE	separatePoint (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, SCIP_RESULT result)
static	SCIP_DECL_SEPACOPY (sepaCopyMinor)
static	SCIP_DECL_SEPAFREE (sepaFreeMinor)
static	SCIP_DECL_SEPAINIT (sepaInitMinor)
static	SCIP_DECL_SEPAEXIT (sepaExitMinor)
static	SCIP_DECL_SEPAINITSOL (sepaInitsolMinor)
static	SCIP_DECL_SEPAEXITSOL (sepaExitsolMinor)
static	SCIP_DECL_SEPAEXECLP (sepaExeclpMinor)
static	SCIP_DECL_SEPAEXECSOL (sepaExecsolMinor)
SCIP_RETCODE	SCIPincludeSepaMinor (SCIP *scip)

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME "minor"

Definition at line 39 of file sepa_minor.c.

◆ SEPA_DESC

#define SEPA_DESC "separator to ensure that 2x2 principal minors of X - xx' are positive semi-definite"

Definition at line 40 of file sepa_minor.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY 0

Definition at line 41 of file sepa_minor.c.

◆ SEPA_FREQ

#define SEPA_FREQ 10

Definition at line 42 of file sepa_minor.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 43 of file sepa_minor.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 44 of file sepa_minor.c.

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 45 of file sepa_minor.c.

◆ DEFAULT_MAXMINORSCONST

#define DEFAULT_MAXMINORSCONST 3000

default constant for the maximum number of minors, i.e., max(const, fac * # quadratic terms)

Definition at line 47 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ DEFAULT_MAXMINORSFAC

#define DEFAULT_MAXMINORSFAC 10.0

default factor for the maximum number of minors, i.e., max(const, fac * # quadratic terms)

Definition at line 48 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ DEFAULT_MINCUTVIOL

#define DEFAULT_MINCUTVIOL 1e-4

default minimum required violation of a cut

Definition at line 49 of file sepa_minor.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 157

default random seed

Definition at line 50 of file sepa_minor.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS 10

maximal number of separation rounds per node (-1: unlimited)

Definition at line 51 of file sepa_minor.c.

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT -1

maximal number of separation rounds in the root node (-1: unlimited)

Definition at line 52 of file sepa_minor.c.

◆ DEFAULT_IGNOREPACKINGCONSS

#define DEFAULT_IGNOREPACKINGCONSS TRUE

default for ignoring circle packing constraints during minor detection

Definition at line 53 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

Function Documentation

◆ sepadataAddMinor()

SCIP_RETCODE sepadataAddMinor	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_VAR *	x,
		SCIP_VAR *	y,
		SCIP_VAR *	auxvarxx,
		SCIP_VAR *	auxvaryy,
		SCIP_VAR *	auxvarxy )

static

helper method to store a 2x2 minor in the separation data

Parameters

scip	SCIP data structure
sepadata	separator data
x	x variable
y	y variable
auxvarxx	auxiliary variable for x*x
auxvaryy	auxiliary variable for y*y
auxvarxy	auxiliary variable for x*y

Definition at line 81 of file sepa_minor.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPcaptureVar(), SCIPdebugMsg, SCIPreallocBlockMemoryArray, SCIPvarGetName(), sepadata, x, and y.

Referenced by detectMinors().

◆ sepadataClear()

SCIP_RETCODE sepadataClear	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata )

static

helper method to clear separation data

Parameters

scip	SCIP data structure
sepadata	separator data

Definition at line 135 of file sepa_minor.c.

References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemoryArrayNull, SCIPreleaseVar(), and sepadata.

Referenced by SCIP_DECL_SEPAEXITSOL().

◆ isPackingCons()

SCIP_Bool isPackingCons	(	SCIP *	scip,
		SCIP_CONS *	cons )

static

helper method to identify non-overlapping constraints in circle packing

Parameters

scip	SCIP data structure
cons	nonlinear constraint

Definition at line 165 of file sepa_minor.c.

References assert(), FALSE, i, NULL, SCIP_Bool, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetExponentExprPow(), SCIPgetExprNonlinear(), SCIPgetVarExprVar(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprSum(), SCIPisExprVar(), TRUE, x, and y.

Referenced by detectMinors().

◆ getMinorVars()

SCIP_RETCODE getMinorVars	(	SCIP_SEPADATA *	sepadata,
		int	idx,
		SCIP_VAR **	x,
		SCIP_VAR **	y,
		SCIP_VAR **	auxvarxx,
		SCIP_VAR **	auxvaryy,
		SCIP_VAR **	auxvarxy )

static

helper method to get the variables associated to a minor

Parameters

sepadata	separator data
idx	index of the stored minor
x	pointer to store x variable
y	pointer to store x variable
auxvarxx	pointer to store auxiliary variable for x*x
auxvaryy	pointer to store auxiliary variable for y*y
auxvarxy	pointer to store auxiliary variable for x*y

Definition at line 265 of file sepa_minor.c.

References assert(), NULL, SCIP_OKAY, sepadata, x, and y.

Referenced by separatePoint().

◆ detectMinors()

SCIP_RETCODE detectMinors	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata )

static

method to detect and store principal minors

Parameters

scip	SCIP data structure
sepadata	separator data

Definition at line 292 of file sepa_minor.c.

References assert(), c, FALSE, i, isPackingCons(), MAX, NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPexpriterSetStagesDFS(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeExpriter(), SCIPgetExponentExprPow(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprNonlinear(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetTotalTime(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPisExprPower(), SCIPisExprProduct(), SCIPrandomPermuteIntArray(), SCIPstatisticMessage, SCIPvarGetName(), SCIPvarIsBinary(), sepadata, sepadataAddMinor(), SQR, TRUE, x, and y.

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ getEigenValues()

SCIP_RETCODE getEigenValues	(	SCIP *	scip,
		SCIP_Real	x,
		SCIP_Real	y,
		SCIP_Real	xx,
		SCIP_Real	yy,
		SCIP_Real	xy,
		SCIP_Real *	eigenvals,
		SCIP_Real *	eigenvecs,
		SCIP_Bool *	success )

static

helper method to compute eigenvectors and eigenvalues

Parameters

scip	SCIP data structure
x	solution value of x
y	solution value of y
xx	solution value of x*x
yy	solution value of y*y
xy	solution value of x*y
eigenvals	array to store eigenvalues (at least of size 3)
eigenvecs	array to store eigenvalues (at least of size 9)
success	pointer to store whether eigenvalue computation was successful

Definition at line 507 of file sepa_minor.c.

References assert(), FALSE, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPbuffer(), SCIPdebugMsg, SCIPlapackComputeEigenvalues(), TRUE, x, and y.

Referenced by separatePoint().

◆ addCut()

SCIP_RETCODE addCut	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		SCIP_VAR *	x,
		SCIP_VAR *	y,
		SCIP_VAR *	xx,
		SCIP_VAR *	yy,
		SCIP_VAR *	xy,
		SCIP_Real *	eigenvec,
		SCIP_Real	eigenval,
		SCIP_Real	mincutviol,
		SCIP_RESULT *	result )

static

generate and add a cut

Parameters

scip	SCIP data structure
sepa	separator
sol	solution to separate (might be NULL)
x	x variable
y	y variable
xx	auxiliary variable for x*x
yy	auxiliary variable for y*y
xy	auxiliary variable for x*y
eigenvec	array containing an eigenvector
eigenval	eigenvalue
mincutviol	minimal required violation
result	pointer to update the result

Definition at line 548 of file sepa_minor.c.

References assert(), FALSE, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_SIDETYPE_LEFT, SCIPaddRow(), SCIPaddRowprepTerms(), SCIPcleanupRowprep(), SCIPcreateRowprep(), SCIPdebug, SCIPdebugMsg, SCIPfreeRowprep(), SCIPgetNLPs(), SCIPgetRowprepRowSepa(), SCIPgetRowprepViolation(), SCIPisFeasLT(), SCIPprintRowprep(), SCIPreleaseRow(), SCIProwprepAddConstant(), SCIProwprepGetName(), SCIPsnprintf(), SCIPvarGetName(), sol, SQR, vars, x, and y.

Referenced by separatePoint().

◆ separatePoint()

SCIP_RETCODE separatePoint	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result )

static

separates cuts for stored principal minors

Parameters

scip	SCIP data structure
sepa	separator
sol	primal solution that should be separated, or NULL for LP solution
result	pointer to store the result of the separation call

Definition at line 634 of file sepa_minor.c.

References addCut(), assert(), getEigenValues(), getMinorVars(), i, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetSolVal(), SCIPsepaGetData(), sepadata, sol, x, and y.

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ SCIP_DECL_SEPACOPY()

SCIP_DECL_SEPACOPY ( sepaCopyMinor )

static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 714 of file sepa_minor.c.

References assert(), NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_STRINGEQ, SCIPincludeSepaMinor(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

SCIP_DECL_SEPAFREE ( sepaFreeMinor )

static

destructor of separator to free user data (called when SCIP is exiting)

Definition at line 730 of file sepa_minor.c.

References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaSetData(), and sepadata.

◆ SCIP_DECL_SEPAINIT()

SCIP_DECL_SEPAINIT ( sepaInitMinor )

static

initialization method of separator (called after problem was transformed)

Definition at line 750 of file sepa_minor.c.

References assert(), DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), sepadata, and TRUE.

◆ SCIP_DECL_SEPAEXIT()

SCIP_DECL_SEPAEXIT ( sepaExitMinor )

static

deinitialization method of separator (called before transformed problem is freed)

Definition at line 768 of file sepa_minor.c.

References assert(), NULL, SCIP_OKAY, SCIPfreeRandom(), SCIPsepaGetData(), and sepadata.

◆ SCIP_DECL_SEPAINITSOL()

SCIP_DECL_SEPAINITSOL ( sepaInitsolMinor )

static

solving process initialization method of separator (called when branch and bound process is about to begin)

Definition at line 786 of file sepa_minor.c.

References SCIP_OKAY.

◆ SCIP_DECL_SEPAEXITSOL()

SCIP_DECL_SEPAEXITSOL ( sepaExitsolMinor )

static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 794 of file sepa_minor.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), sepadata, and sepadataClear().

◆ SCIP_DECL_SEPAEXECLP()

SCIP_DECL_SEPAEXECLP ( sepaExeclpMinor )

static

LP solution separation method of separator

Definition at line 810 of file sepa_minor.c.

References assert(), depth, detectMinors(), ncalls, NULL, result, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPlapackIsAvailable(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), sepadata, and separatePoint().

◆ SCIP_DECL_SEPAEXECSOL()

SCIP_DECL_SEPAEXECSOL ( sepaExecsolMinor )

static

arbitrary primal solution separation method of separator

Definition at line 843 of file sepa_minor.c.

References assert(), depth, detectMinors(), ncalls, NULL, result, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPlapackIsAvailable(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), sepadata, separatePoint(), and sol.

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_MAXMINORSCONST

◆ DEFAULT_MAXMINORSFAC

◆ DEFAULT_MINCUTVIOL

◆ DEFAULT_RANDSEED

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_IGNOREPACKINGCONSS

Function Documentation

◆ sepadataAddMinor()

◆ sepadataClear()

◆ isPackingCons()

◆ getMinorVars()

◆ detectMinors()

◆ getEigenValues()

◆ addCut()

◆ separatePoint()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAINIT()

◆ SCIP_DECL_SEPAEXIT()

◆ SCIP_DECL_SEPAINITSOL()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()

◆ SCIP_DECL_SEPAEXECSOL()