50#define SEPA_NAME "interminor"
51#define SEPA_DESC "intersection cuts separator to ensure that 2x2 minors of X (= xx') have determinant 0"
52#define SEPA_PRIORITY 0
54#define SEPA_MAXBOUNDDIST 1.0
55#define SEPA_USESSUBSCIP FALSE
56#define SEPA_DELAY FALSE
58#define DEFAULT_MINCUTVIOL 1e-4
59#define DEFAULT_RANDSEED 157
60#define DEFAULT_MAXROUNDS 10
61#define DEFAULT_MAXROUNDSROOT -1
62#define BINSEARCH_MAXITERS 120
63#define DEFAULT_USESTRENGTHENING FALSE
64#define DEFAULT_USEBOUNDS FALSE
74 SCIP_Bool* isdiagonal;
79 SCIP_Bool detectedminors;
82 SCIP_Bool usestrengthening;
251 if(
arr->valssize <
arr->nvals + 1 )
523 for(
i = 0;
i < nrows; ++
i )
551 SCIP_Real eigenvectors[16] = {1.0, 1.0, 0.0, 0.0, 0.0, 0.0, -1.0, 1.0, -1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0};
552 SCIP_Real eigenvalues[4] = {0.5, 0.5, -0.5, -0.5};
553 SCIP_Real
eigencoef = 0.7071067811865475244008443621048490;
570 memset(coefs, 0, 5 *
sizeof(SCIP_Real));
583 for(
i = 0;
i < 4; ++
i )
593 for(
j = 0;
j < 4; ++
j )
599 if( eigenvalues[
i] > 0 )
666 for(
i = 0;
i < 3; ++
i )
679#ifdef DEBUG_INTERSECTIONCUT
680 printf(
"Bad numerics: max(A,B,C)/min(A,B,C) is too large (%g)\n",
max /
min);
691#ifdef DEBUG_INTERSECTIONCUT
692 SCIPinfoMessage(
scip,
NULL,
"Restriction yields: a,b,c,d,e %g %g %g %g %g\n", coefs[0], coefs[1], coefs[2], coefs[3], coefs[4]);
710#ifdef INTERCUTS_DBLDBL
714 SCIP_Real
QUAD(root);
751 return SQRT(
a * t * t +
b * t +
c ) - (
d * t +
e );
776 curr = (lb + ub) / 2.0;
778#ifdef INTERCUT_MOREDEBUG
779 printf(
"%d: lb,ub %.10f, %.10f. curr = %g -> phi at curr %g -> phi at lb %g \n",
i, lb, ub, curr,
phival,
evalPhiAtRay(
scip, lb,
a,
b,
c,
d,
e));
825 SCIP_Real
a = coefs[0];
826 SCIP_Real
b = coefs[1];
827 SCIP_Real
c = coefs[2];
828 SCIP_Real
d = coefs[3];
829 SCIP_Real
e = coefs[4];
848 e, -(
c -
e *
e), bounds);
860#ifdef INTERCUT_MOREDEBUG
862 printf(
"don't do bin search\n");
870#ifdef INTERCUT_MOREDEBUG
962#ifdef DEBUG_INTERCUTS_NUMERICS
1004#ifdef DEBUG_INTERCUTS_NUMERICS
1034 for(
i = 0;
i < nnonz;
i++ )
1065 for( v = 0; v < 4; ++v )
1119 SCIP_Bool usebounds,
1133 for(
i = 0;
i < ncols; ++
i )
1162 for( v = 0; v < 4; ++v )
1169 rays[(*nrays) * 4 + v] = -
factor;
1171 rays[(*nrays) * 4 + v] = 0.0;
1225 SCIP_Bool usebounds,
1242 for(
i = 0;
i < nrows; ++
i )
1271 for( v = 0; v < 4; ++v )
1282 rays[(*nrays) * 4 + v] = 0.0;
1337 for(
i = 0;
i < 4; ++
i )
1371 SCIP_Bool usebounds,
1383 for(
i = 0;
i < nrays; ++
i )
1414 alpha = (lb + ub) / 2.0;
1417 for(
k = 0;
k < 4; ++
k )
1475 SCIP_Bool usebounds,
1491 for(
i = 0;
i < nrays ; ++
i )
1565 SCIP_Real
ad[4] = {0.0, 0.0, 0.0, 0.0};
1623 SCIP_CALL(
addCols(
scip,
vars,
tableaurows,
rowprep, rays, &nrays,
rayslppos,
interpoints,
sepadata->usebounds,
ad, &
success) );
1629 SCIP_CALL(
addRows(
scip,
vars,
tableaurows,
rowprep, rays, &nrays,
rayslppos,
interpoints,
sepadata->usebounds,
ad, &
success) );
1652 SCIP_Bool infeasible;
1957 "separating/" SEPA_NAME "/usestrengthening",
1958 "whether to use strengthened intersection cuts to separate minors",
1963 "whether to also enforce nonegativity bounds of principle minors",
1968 "minimum required violation of a cut",
1973 "maximal number of separation rounds per node (-1: unlimited)",
1977 "separating/" SEPA_NAME "/maxroundsroot",
1978 "maximal number of separation rounds in the root node (-1: unlimited)",
constraint handler for nonlinear constraints specified by algebraic expressions
#define SCIPquadprecSqrtQ(r, a)
#define SCIPquadprecProdDD(r, a, b)
#define SCIPquadprecProdQD(r, a, b)
#define SCIPquadprecSumQD(r, a, b)
#define QUAD_ASSIGN(a, constant)
#define SCIPquadprecSquareD(r, a)
#define SCIPquadprecSumQQ(r, a, b)
#define SCIP_INTERVAL_INFINITY
private functions to work with algebraic expressions
power and signed power expression handlers
product expression handler
variable expression handler
void SCIPcomputeArraysIntersectionInt(int *array1, int narray1, int *array2, int narray2, int *intersectarray, int *nintersectarray)
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
const char * SCIPgetProbName(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_Bool SCIPisIpoptAvailableIpopt(void)
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)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
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_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
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_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)
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
void SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_Real lincoeff, SCIP_Real rhs, SCIP_INTERVAL xbnds)
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
int SCIPgetNLPRows(SCIP *scip)
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
int SCIPgetNLPCols(SCIP *scip)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
#define SCIPfreeBuffer(scip, ptr)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBuffer(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_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
int SCIProwGetNLPNonz(SCIP_ROW *row)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_BASESTAT SCIProwGetBasisStatus(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 SCIPgetTotalTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
void SCIPmergeRowprepTerms(SCIP *scip, 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 SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
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)
SCIP_RETCODE SCIPincludeSepaInterminor(SCIP *scip)
void SCIPsortInt(int *intarray, int len)
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
#define BMSclearMemory(ptr)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#define SCIPstatisticMessage
static SCIP_RETCODE insertIndex(SCIP *scip, SCIP_HASHMAP *rowmap, SCIP_VAR *row, SCIP_VAR *col, SCIP_VAR *auxvar, int *rowindices, int *nrows)
static SCIP_Real computeIntersectionPoint(SCIP *scip, SCIP_Bool usebounds, SCIP_Real *coefs, SCIP_Real *coefs4b, SCIP_Real *coefscondition)
#define DEFAULT_USEBOUNDS
#define DEFAULT_USESTRENGTHENING
static SCIP_RETCODE addRows(SCIP *scip, SCIP_VAR **vars, SCIP_Real **tableaurows, SCIP_ROWPREP *rowprep, SCIP_Real *rays, int *nrays, int *rayslppos, SCIP_Real *interpoints, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
static SCIP_RETCODE getMinorVars(SCIP_SEPADATA *sepadata, int idx, SCIP_VAR **auxvarxik, SCIP_VAR **auxvarxil, SCIP_VAR **auxvarxjk, SCIP_VAR **auxvarxjl, SCIP_Bool *isauxvarxikdiag, SCIP_Bool *isauxvarxildiag, SCIP_Bool *isauxvarxjkdiag, SCIP_Bool *isauxvarxjldiag)
static SCIP_RETCODE sepadataClear(SCIP *scip, SCIP_SEPADATA *sepadata)
static SCIP_RETCODE findRho(SCIP *scip, SCIP_Real *rays, int nrays, int idx, SCIP_Real *interpoints, SCIP_VAR **vars, SCIP_Real *rho, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
#define DEFAULT_MAXROUNDSROOT
static SCIP_RETCODE getTableauRows(SCIP *scip, SCIP_VAR **vars, int *basicvarpos2tableaurow, SCIP_HASHMAP *tableau, SCIP_Real **tableaurows, SCIP_Bool *success)
static SCIP_Real isCase4a(SCIP_Real tsol, SCIP_Real *coefs, SCIP_Real *coefscondition)
static SCIP_RETCODE addRowToCut(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real cutcoef, SCIP_ROW *row, SCIP_Bool *success)
static SCIP_RETCODE separateDeterminant(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_VAR *xik, SCIP_VAR *xil, SCIP_VAR *xjk, SCIP_VAR *xjl, SCIP_Bool *isxikdiag, SCIP_Bool *isxildiag, SCIP_Bool *isxjkdiag, SCIP_Bool *isxjldiag, int *basicvarpos2tableaurow, SCIP_HASHMAP *tableau, SCIP_RESULT *result)
static SCIP_Real computeRoot(SCIP *scip, SCIP_Real *coefs)
static SCIP_Real evalPhiAtRay(SCIP *scip, SCIP_Real t, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e)
#define DEFAULT_MINCUTVIOL
static SCIP_RETCODE detectMinors(SCIP *scip, SCIP_SEPADATA *sepadata)
static SCIP_RETCODE sepadataAddMinor(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR *auxvarxik, SCIP_VAR *auxvarxil, SCIP_VAR *auxvarxjk, SCIP_VAR *auxvarxjl, SCIP_Bool isauxvarxikdiag, SCIP_Bool isauxvarxildiag, SCIP_Bool isauxvarxjkdiag, SCIP_Bool isauxvarxjldiag)
#define SEPA_MAXBOUNDDIST
static SCIP_RETCODE addCols(SCIP *scip, SCIP_VAR **vars, SCIP_Real **tableaurows, SCIP_ROWPREP *rowprep, SCIP_Real *rays, int *nrays, int *rayslppos, SCIP_Real *interpoints, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
#define BINSEARCH_MAXITERS
#define DEFAULT_MAXROUNDS
static SCIP_RETCODE computeNegCutcoefs(SCIP *scip, SCIP_VAR **vars, SCIP_Real *rays, int nrays, int *rayslppos, SCIP_Real *interpoints, SCIP_ROWPREP *rowprep, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
static void doBinarySearch(SCIP *scip, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e, SCIP_Real *sol)
static SCIP_RETCODE addColToCut(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real cutcoef, SCIP_COL *col)
static SCIP_RETCODE constructBasicVars2TableauRowMap(SCIP *scip, int *map)
static SCIP_RETCODE computeRestrictionToRay(SCIP *scip, SCIP_Real *ray, SCIP_VAR **vars, SCIP_Real *coefs, SCIP_Real *coefs4b, SCIP_Real *coefscondition, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
static SCIP_Bool raysAreDependent(SCIP *scip, SCIP_Real *ray1, SCIP_Real *ray2, SCIP_Real *coef)
static SCIP_RETCODE separatePoint(SCIP *scip, SCIP_SEPA *sepa, SCIP_RESULT *result)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAINITSOL(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)