42#define SEPA_NAME "minor"
43#define SEPA_DESC "separator to ensure that 2x2 principal minors of X - xx' are positive semi-definite"
44#define SEPA_PRIORITY 0
46#define SEPA_MAXBOUNDDIST 1.0
47#define SEPA_USESSUBSCIP FALSE
48#define SEPA_DELAY FALSE
50#define DEFAULT_MAXMINORSCONST 3000
51#define DEFAULT_MAXMINORSFAC 10.0
52#define DEFAULT_MINCUTVIOL 1e-4
53#define DEFAULT_RANDSEED 157
54#define DEFAULT_MAXROUNDS 10
55#define DEFAULT_MAXROUNDSROOT -1
56#define DEFAULT_IGNOREPACKINGCONSS TRUE
69 SCIP_Real maxminorsfac;
72 SCIP_Bool detectedminors;
75 SCIP_Bool ignorepackingconss;
101 assert(auxvarxx != auxvaryy);
102 assert(auxvarxx != auxvarxy);
103 assert(auxvaryy != auxvarxy);
192 for(
i = 0;
i < nchildren; ++
i )
215 quadvars[nquadvars++] =
x;
234 bilinvars[nbilinvars++] =
x;
235 bilinvars[nbilinvars++] =
y;
244 if( nbilinvars != 4 || nquadvars != 4 )
248 for(
i = 0;
i < nquadvars; ++
i )
253 for( j = 0; j < nbilinvars; ++j )
255 if( quadvars[
i] == bilinvars[j] )
279 assert(idx >= 0 && idx < sepadata->nminors);
286 *auxvarxx =
sepadata->minors[5 * idx + 2];
287 *auxvaryy =
sepadata->minors[5 * idx + 3];
288 *auxvarxy =
sepadata->minors[5 * idx + 4];
421 auxvars[nbilinterms] = auxvar;
440 if( maxminors < nbilinterms && maxminors <
SQR(nquadterms) )
444 for(
i = 0;
i < nbilinterms; ++
i )
452 for(
i = 0;
i < nbilinterms &&
sepadata->nminors < maxminors; ++
i )
462 auxvarxy = auxvars[
i];
468 auxvarxy = auxvars[perm[
i]];
517 SCIP_Real* eigenvals,
518 SCIP_Real* eigenvecs,
542 SCIPdebugMsg(
scip,
"Failed to compute eigenvalues and eigenvectors of augmented quadratic form matrix.\n");
562 SCIP_Real mincutviol,
578 assert(mincutviol >= 0.0);
593 constant =
SQR(eigenvec[0]);
594 coefs[0] = 2.0 * eigenvec[0] * eigenvec[1];
595 coefs[1] = 2.0 * eigenvec[0] * eigenvec[2];
596 coefs[2] =
SQR(eigenvec[1]);
597 coefs[3] =
SQR(eigenvec[2]);
598 coefs[4] = 2.0 * eigenvec[1] * eigenvec[2];
614 SCIP_Bool infeasible;
663 SCIP_Real eigenvals[3];
664 SCIP_Real eigenvecs[9];
692 SCIPdebugMsg(
scip,
"solution values (x,y,xx,yy,xy)=(%g,%g,%g,%g,%g)\n", solx, soly, solxx, solyy, solxy);
702 SCIPdebugMsg(
scip,
"eigenvalue = %g eigenvector = (%g,%g,%g)\n", eigenvals[k], eigenvecs[3*k], eigenvecs[3*k + 1], eigenvecs[3*k + 2]);
703 SCIP_CALL(
addCut(
scip, sepa,
sol,
x,
y, xx, yy, xy, &eigenvecs[3*k], eigenvals[k],
sepadata->mincutviol,
result) );
894 sepaExeclpMinor, sepaExecsolMinor,
909 "separating/" SEPA_NAME "/maxminorsconst",
910 "constant for the maximum number of minors, i.e., max(const, fac * # quadratic terms)",
915 "factor for the maximum number of minors, i.e., max(const, fac * # quadratic terms)",
920 "minimum required violation of a cut",
925 "maximal number of separation rounds per node (-1: unlimited)",
929 "separating/" SEPA_NAME "/maxroundsroot",
930 "maximal number of separation rounds in the root node (-1: unlimited)",
934 "separating/" SEPA_NAME "/ignorepackingconss",
935 "whether to ignore circle packing constraints during minor detection",
constraint handler for nonlinear constraints specified by algebraic expressions
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
const char * SCIPgetProbName(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
SCIP_EXPR * SCIPexpriterRestartDFS(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
BMS_BUFMEM * SCIPbuffer(SCIP *scip)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetTotalTime(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPgetRowprepViolation(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Bool *reliable)
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
SCIP_RETCODE SCIPgetRowprepRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_SEPA *sepa)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
SCIP_RETCODE SCIPcleanupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real minviol, SCIP_Real *viol, SCIP_Bool *success)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
SCIP_RETCODE SCIPincludeSepaMinor(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_Bool SCIPlapackIsAvailable(void)
SCIP_RETCODE SCIPlapackComputeEigenvalues(BMS_BUFMEM *bufmem, SCIP_Bool geteigenvectors, int N, SCIP_Real *a, SCIP_Real *w)
interface methods for lapack functions
#define BMSclearMemory(ptr)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#define SCIPstatisticMessage
static SCIP_RETCODE getMinorVars(SCIP_SEPADATA *sepadata, int idx, SCIP_VAR **x, SCIP_VAR **y, SCIP_VAR **auxvarxx, SCIP_VAR **auxvaryy, SCIP_VAR **auxvarxy)
#define DEFAULT_MAXMINORSFAC
static SCIP_RETCODE sepadataClear(SCIP *scip, SCIP_SEPADATA *sepadata)
#define DEFAULT_MAXROUNDSROOT
#define DEFAULT_IGNOREPACKINGCONSS
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)
#define DEFAULT_MAXMINORSCONST
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 separatePoint(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
#define DEFAULT_MINCUTVIOL
static SCIP_RETCODE detectMinors(SCIP *scip, SCIP_SEPADATA *sepadata)
#define SEPA_MAXBOUNDDIST
static SCIP_Bool isPackingCons(SCIP *scip, SCIP_CONS *cons)
#define DEFAULT_MAXROUNDS
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)
principal minor separator
#define SCIP_EXPRITER_ENTEREXPR
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAINITSOL(x)
#define SCIP_DECL_SEPAEXECSOL(x)
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPAFREE(x)
#define SCIP_DECL_SEPAEXITSOL(x)
#define SCIP_DECL_SEPAEXIT(x)
#define SCIP_DECL_SEPACOPY(x)
#define SCIP_DECL_SEPAINIT(x)