principal minor separator
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 |
#define SEPA_NAME "minor" |
Definition at line 42 of file sepa_minor.c.
#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.
#define SEPA_PRIORITY 0 |
Definition at line 44 of file sepa_minor.c.
#define SEPA_FREQ 10 |
Definition at line 45 of file sepa_minor.c.
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 46 of file sepa_minor.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 47 of file sepa_minor.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 48 of file sepa_minor.c.
#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.
Referenced by SCIPincludeSepaMinor().
#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.
Referenced by SCIPincludeSepaMinor().
#define DEFAULT_MINCUTVIOL 1e-4 |
default minimum required violation of a cut
Definition at line 52 of file sepa_minor.c.
#define DEFAULT_RANDSEED 157 |
default random seed
Definition at line 53 of file sepa_minor.c.
#define DEFAULT_MAXROUNDS 10 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 54 of file sepa_minor.c.
#define DEFAULT_MAXROUNDSROOT -1 |
maximal number of separation rounds in the root node (-1: unlimited)
Definition at line 55 of file sepa_minor.c.
#define DEFAULT_IGNOREPACKINGCONSS TRUE |
default for ignoring circle packing constraints during minor detection
Definition at line 56 of file sepa_minor.c.
Referenced by SCIPincludeSepaMinor().
|
static |
helper method to store a 2x2 minor in the separation data
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 84 of file sepa_minor.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPcaptureVar(), SCIPdebugMsg, SCIPreallocBlockMemoryArray, SCIPvarGetName(), sepadata, x, and y.
Referenced by detectMinors().
|
static |
helper method to clear separation data
scip | SCIP data structure |
sepadata | separator data |
Definition at line 138 of file sepa_minor.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemoryArrayNull, SCIPreleaseVar(), and sepadata.
Referenced by SCIP_DECL_SEPAEXITSOL().
helper method to identify non-overlapping constraints in circle packing
scip | SCIP data structure |
cons | nonlinear constraint |
Definition at line 168 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().
|
static |
helper method to get the variables associated to a minor
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 268 of file sepa_minor.c.
References assert(), NULL, SCIP_OKAY, sepadata, x, and y.
Referenced by separatePoint().
|
static |
method to detect and store principal minors
scip | SCIP data structure |
sepadata | separator data |
Definition at line 295 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().
|
static |
helper method to compute eigenvectors and eigenvalues
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 510 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().
|
static |
generate and add a cut
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 551 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().
|
static |
separates cuts for stored principal minors
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 637 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().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 717 of file sepa_minor.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaMinor(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 732 of file sepa_minor.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaSetData(), and sepadata.
|
static |
initialization method of separator (called after problem was transformed)
Definition at line 752 of file sepa_minor.c.
References assert(), DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), sepadata, and TRUE.
|
static |
deinitialization method of separator (called before transformed problem is freed)
Definition at line 770 of file sepa_minor.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeRandom(), SCIPsepaGetData(), and sepadata.
|
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.
|
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 assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), sepadata, and sepadataClear().
|
static |
LP solution separation method of separator
Definition at line 812 of file sepa_minor.c.
References assert(), depth, detectMinors(), ncalls, NULL, result, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPlapackIsAvailable(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), sepadata, and separatePoint().
|
static |
arbitrary primal solution separation method of separator
Definition at line 845 of file sepa_minor.c.
References assert(), depth, detectMinors(), ncalls, NULL, result, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPlapackIsAvailable(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), sepadata, separatePoint(), and sol.