Scippy

SCIP

Solving Constraint Integer Programs

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/lapack_calls.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 42 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 43 of file sepa_minor.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   0

Definition at line 44 of file sepa_minor.c.

◆ SEPA_FREQ

#define SEPA_FREQ   10

Definition at line 45 of file sepa_minor.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 46 of file sepa_minor.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 47 of file sepa_minor.c.

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 48 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 50 of file sepa_minor.c.

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

◆ DEFAULT_MINCUTVIOL

#define DEFAULT_MINCUTVIOL   1e-4

default minimum required violation of a cut

Definition at line 52 of file sepa_minor.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   157

default random seed

Definition at line 53 of file sepa_minor.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS   10

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

Definition at line 54 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 55 of file sepa_minor.c.

◆ DEFAULT_IGNOREPACKINGCONSS

#define DEFAULT_IGNOREPACKINGCONSS   TRUE

default for ignoring circle packing constraints during minor detection

Definition at line 56 of file sepa_minor.c.

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
scipSCIP data structure
sepadataseparator data
xx variable
yy variable
auxvarxxauxiliary variable for x*x
auxvaryyauxiliary variable for y*y
auxvarxyauxiliary variable for x*y

Definition at line 84 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
scipSCIP data structure
sepadataseparator data

Definition at line 138 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
scipSCIP data structure
consnonlinear constraint

Definition at line 168 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
sepadataseparator data
idxindex of the stored minor
xpointer to store x variable
ypointer to store x variable
auxvarxxpointer to store auxiliary variable for x*x
auxvaryypointer to store auxiliary variable for y*y
auxvarxypointer to store auxiliary variable for x*y

Definition at line 268 of file sepa_minor.c.

References NULL, SCIP_OKAY, x, and y.

Referenced by separatePoint().

◆ detectMinors()

◆ 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
scipSCIP data structure
xsolution value of x
ysolution value of y
xxsolution value of x*x
yysolution value of y*y
xysolution value of x*y
eigenvalsarray to store eigenvalues (at least of size 3)
eigenvecsarray to store eigenvalues (at least of size 9)
successpointer to store whether eigenvalue computation was successful

Definition at line 510 of file sepa_minor.c.

References FALSE, NULL, SCIP_OKAY, SCIPbuffer(), SCIPdebugMsg, SCIPlapackComputeEigenvalues(), 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
scipSCIP data structure
sepaseparator
solsolution to separate (might be NULL)
xx variable
yy variable
xxauxiliary variable for x*x
yyauxiliary variable for y*y
xyauxiliary variable for x*y
eigenvecarray containing an eigenvector
eigenvaleigenvalue
mincutviolminimal required violation
resultpointer to update the result

Definition at line 551 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(), SQR, 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
scipSCIP data structure
sepaseparator
solprimal solution that should be separated, or NULL for LP solution
resultpointer to store the result of the separation call

Definition at line 637 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 717 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 732 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 752 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 770 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 788 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 796 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 812 of file sepa_minor.c.

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

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolMinor  )
static

arbitrary primal solution separation method of separator

Definition at line 845 of file sepa_minor.c.

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