Detailed Description

principal minor separator

Author: Benjamin Mueller

Definition in file sepa_minor.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_minor.h"
#include "scip/cons_nonlinear.h"
#include "scip/nlpi_ipopt.h"

Go to the source code of this file.

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 33 of file sepa_minor.c.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaMinor().

◆ SEPA_DESC

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

Definition at line 34 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY 0

Definition at line 35 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ SEPA_FREQ

#define SEPA_FREQ 10

Definition at line 36 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 37 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 38 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

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

Definition at line 39 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ DEFAULT_MAXMINORSCONST

#define DEFAULT_MAXMINORSCONST 3000

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

Definition at line 41 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 42 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 43 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 157

default random seed

Definition at line 44 of file sepa_minor.c.

Referenced by SCIP_DECL_SEPAINIT().

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS 10

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

Definition at line 45 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT -1

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

Definition at line 46 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

◆ DEFAULT_IGNOREPACKINGCONSS

#define DEFAULT_IGNOREPACKINGCONSS TRUE

default for ignoring circle packing constraints during minor detection

Definition at line 47 of file sepa_minor.c.

Referenced by SCIPincludeSepaMinor().

Function Documentation

◆ sepadataAddMinor()

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

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 75 of file sepa_minor.c.

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

Referenced by detectMinors().

◆ sepadataClear()

static 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 129 of file sepa_minor.c.

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

Referenced by SCIP_DECL_SEPAEXITSOL().

◆ isPackingCons()

static 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 159 of file sepa_minor.c.

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

Referenced by detectMinors().

◆ getMinorVars()

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

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 259 of file sepa_minor.c.

References NULL, and SCIP_OKAY.

Referenced by separatePoint().

◆ detectMinors()

static 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 286 of file sepa_minor.c.

References FALSE, 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(), sepadataAddMinor(), TRUE, x, and y.

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ getEigenValues()

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

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 501 of file sepa_minor.c.

References FALSE, NULL, SCIP_OKAY, SCIPcallLapackDsyevIpopt(), SCIPdebugMsg, TRUE, x, and y.

Referenced by separatePoint().

◆ addCut()

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

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 542 of file sepa_minor.c.

References FALSE, NULL, 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(), x, and y.

Referenced by separatePoint().

◆ separatePoint()

static 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 628 of file sepa_minor.c.

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

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyMinor )

static

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

Definition at line 708 of file sepa_minor.c.

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

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeMinor )

static

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

Definition at line 723 of file sepa_minor.c.

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

◆ SCIP_DECL_SEPAINIT()

static SCIP_DECL_SEPAINIT ( sepaInitMinor )

static

initialization method of separator (called after problem was transformed)

Definition at line 743 of file sepa_minor.c.

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

◆ SCIP_DECL_SEPAEXIT()

static SCIP_DECL_SEPAEXIT ( sepaExitMinor )

static

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

Definition at line 761 of file sepa_minor.c.

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

◆ SCIP_DECL_SEPAINITSOL()

static SCIP_DECL_SEPAINITSOL ( sepaInitsolMinor )

static

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

Definition at line 779 of file sepa_minor.c.

References SCIP_OKAY.

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolMinor )

static

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

Definition at line 787 of file sepa_minor.c.

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

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpMinor )

static

LP solution separation method of separator

Definition at line 803 of file sepa_minor.c.

References detectMinors(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPisIpoptAvailableIpopt(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), and separatePoint().

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolMinor )

static

arbitrary primal solution separation method of separator

Definition at line 836 of file sepa_minor.c.

References detectMinors(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPisIpoptAvailableIpopt(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), and separatePoint().

SCIP

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()