44#ifdef INTERCUTS_VERBOSE
49#define INTERLOG(x) if( SCIPgetSubscipDepth(scip) == 0 && SCIPgetVerbLevel(scip) >= SCIP_VERBLEVEL_NORMAL ) { x }
66#define NLHDLR_NAME "quadratic"
67#define NLHDLR_DESC "handler for quadratic expressions"
68#define NLHDLR_DETECTPRIORITY 1
69#define NLHDLR_ENFOPRIORITY 100
72#define TABLE_NAME_QUADRATIC "nlhdlr_quadratic"
73#define TABLE_DESC_QUADRATIC "quadratic nlhdlr statistics table"
74#define TABLE_POSITION_QUADRATIC 14700
75#define TABLE_EARLIEST_STAGE_QUADRATIC SCIP_STAGE_TRANSFORMED
78#define INTERCUTS_MINVIOL 1e-4
79#define DEFAULT_USEINTERCUTS FALSE
80#define DEFAULT_USESTRENGTH FALSE
81#define DEFAULT_USEBOUNDS FALSE
82#define BINSEARCH_MAXITERS 120
83#define DEFAULT_NCUTSROOT 20
84#define DEFAULT_NCUTS 2
91struct SCIP_NlhdlrExprData
100 SCIP_Real minquadfiniteact;
102 SCIP_Real maxquadfiniteact;
104 int nneginfinityquadact;
105 int nposinfinityquadact;
108 SCIP_Longint activitiestag;
111 SCIP_Bool separating;
118struct SCIP_NlhdlrData
122 SCIP_Longint lastnodenumber;
126 SCIP_Bool useintersectioncuts;
127 SCIP_Bool usestrengthening;
128 SCIP_Bool useboundsasrays;
132 SCIP_Real mincutviolation;
133 SCIP_Real minviolation;
137 SCIP_Real cutcoefsum;
138 SCIP_Bool ignorebadrayrestriction;
139 SCIP_Bool ignorehighre;
142 int ncouldimprovedcoef;
143 int nbadrayrestriction;
150 SCIP_Real densitysum;
188 SCIPinfoMessage(
scip, file,
"Quadratic Nlhdlr : %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s \n",
"GenCuts",
"AddCuts",
"CouldImpr",
"NLargeRE",
189 "AbrtBadRay",
"AbrtPosPhi",
"AbrtNonBas",
"NStrength",
"AveCutcoef",
"AveDensity",
"AveBCutsFrac");
224#ifdef DEBUG_INTERCUTS_NUMERICS
268#ifdef DEBUG_INTERCUTS_NUMERICS
298 for(
i = 0;
i < nnonz;
i++ )
323 for(
i = 0;
i < nrows; ++
i )
352 qexpr = nlhdlrexprdata->qexpr;
356 for(
i = 0;
i < nquadexprs; ++
i )
373 for(
i = 0;
i < nlinexprs; ++
i )
453 for(
i = 0;
i < ncols; ++
i )
459 for( ;
i < ncols + nrows; ++
i )
511 for(
i = 0;
i < ncols; ++
i )
515 qexpr = nlhdlrexprdata->qexpr;
520 for(
i = 0;
i < nquadexprs; ++
i )
536 for(
i = 0;
i < nlinexprs; ++
i )
563#ifdef DEBUG_INTERSECTIONCUT
564 for(
i = 0;
i < ncols; ++
i )
596 (*rays)->raysbegin[0] = 0;
620 (*rays)->raysbegin[0] = 0;
622 (*rays)->rayssize = size;
692 qexpr = nlhdlrexprdata->qexpr;
696 for(
i = 0;
i < nquadexprs; ++
i )
705 for(
i = 0;
i < nlinexprs; ++
i )
708 map[lppos] = nquadexprs +
i;
714 map[lppos] = nquadexprs + nlinexprs;
767#ifdef DEBUG_INTERSECTIONCUT
788#ifdef DEBUG_INTERSECTIONCUT
797 rays->raysbegin[
rays->nrays + 1] = *nnonz;
799#ifdef DEBUG_INTERSECTIONCUT
801 for(
i =
rays->raysbegin[
rays->nrays];
i < *nnonz; ++
i )
875 SCIPdebugMsg(
scip,
"failed to store sparse rays: there is a var with base status zero\n");
888 for(
i = 0;
i < ncols; ++
i )
902 for(
i = 0;
i < ncols; ++
i )
923#ifdef DEBUG_INTERSECTIONCUT
924 SCIPinfoMessage(
scip,
NULL,
"looked at ray of var %s with basestat %d, it has %d nonzeros\n-----------------\n",
929#ifdef DEBUG_INTERSECTIONCUT
930 SCIPdebugMsg(
scip,
"nonzero ray associated with variable <%s> has base status zero -> abort storing rays\n",
948 for(
i = 0;
i < nrows; ++
i )
970#ifdef DEBUG_INTERSECTIONCUT
1060 SCIP_Real* eigenvectors;
1061 SCIP_Real* eigenvalues;
1062 SCIP_Real* lincoefs;
1072 qexpr = nlhdlrexprdata->qexpr;
1079 if( nlhdlrexprdata->cons !=
NULL )
1089 for(
i = 0;
i < nquadexprs; ++
i )
1100 for(
j = 0;
j < nquadexprs; ++
j )
1108#ifdef INTERCUT_MOREDEBUG
1109 printf(
"vdotb: offset %d, eigenvector %d = %g, lincoef quad %g\n",
offset,
j,
1110 eigenvectors[
offset +
j], lincoef);
1125 for(
j = 0;
j < nquadexprs; ++
j )
1137 for(
i = 0;
i < nlinexprs; ++
i )
1141 if( auxvar !=
NULL )
1146#ifdef DEBUG_INTERSECTIONCUT
1149 for(
i = 0;
i < nquadexprs; ++
i )
1198 SCIP_Real* lincoefs;
1206#ifdef INTERCUT_MOREDEBUG
1207 printf(
"Computing w(ray) \n");
1212 qexpr = nlhdlrexprdata->qexpr;
1218#ifdef INTERCUT_MOREDEBUG
1232#ifdef INTERCUT_MOREDEBUG
1276 SCIP_Real* eigenvectors;
1277 SCIP_Real* eigenvalues;
1288 qexpr = nlhdlrexprdata->qexpr;
1291#ifdef DEBUG_INTERSECTIONCUT
1322 for(
i = 0;
i < nquadexprs; ++
i )
1324 SCIP_Real dot = 0.0;
1343#ifdef INTERCUT_MOREDEBUG
1353#ifdef INTERCUT_MOREDEBUG
1354 printf(
"Positive eigenvalue: computing D: v^T ray %g, v^T( zlp + b/theta ) %g and theta %g \n",
vdotray, dot, (
sidefactor * eigenvalues[
i]));
1364#ifdef INTERCUT_MOREDEBUG
1387 if(
SQRT( *
c ) - *
e >= 0 )
1459#ifdef DEBUG_INTERSECTIONCUT
1462 SCIPinfoMessage(
scip,
NULL,
"Restriction yields case 1,2 or 3: a,b,c,d,e %g %g %g %g %g\n",
coefs1234a[0],
coefs1234a[1],
coefs1234a[2],
1469 SCIPinfoMessage(
scip,
NULL,
" Case 4b: a,b,c,d,e %g %g %g %g %g\n",
coefs4b[0],
coefs4b[1],
coefs4b[2],
1501#ifdef INTERCUTS_DBLDBL
1505 SCIP_Real
QUAD(root);
1542 return SQRT(
a * t * t +
b * t +
c ) - (
d * t +
e );
1580 SCIP_Real ub = *
sol;
1588 curr = (lb + ub) / 2.0;
1590#ifdef INTERCUT_MOREDEBUG
1591 printf(
"%d: lb,ub %.10f, %.10f. curr = %g -> phi at curr %g -> phi at lb %g \n",
i, lb, ub, curr,
phival,
evalPhiAtRay(lb,
a,
b,
c,
d,
e));
1622 SCIP_Real
a = coefs[0];
1623 SCIP_Real
b = coefs[1];
1624 SCIP_Real
c = coefs[2];
1625 SCIP_Real
d = coefs[3];
1626 SCIP_Real
e = coefs[4];
1644 e, -(
c -
e *
e), bounds);
1649#ifdef INTERCUT_MOREDEBUG
1665#ifdef INTERCUT_MOREDEBUG
1667 printf(
"don't do bin search\n");
1674#ifdef INTERCUT_MOREDEBUG
1728#ifdef DEBUG_INTERSECTIONCUT
1738#ifdef DEBUG_INTERSECTIONCUT
1758#ifdef DEBUG_INTERSECTIONCUT
1808 for(
j = 0;
j < 3; ++
j )
1821 INTERLOG(
printf(
"Bad numerics 1 2 3 or 4a: max(A,B,C)/min(A,B,C) is too large (%g)\n",
max /
min); )
1830 for(
j = 0;
j < 3; ++
j )
1884 for(
i = 0;
i <
rays->nrays; ++
i )
1910#ifdef DEBUG_INTERSECTIONCUT
1922 lppos =
rays->lpposray[
i];
2160 for(
i = 0;
i <
rays->nrays; ++
i )
2178 &
rays->raysidx[
rays->raysbegin[idx]],
rays->raysbegin[idx + 1] -
rays->raysbegin[idx], &coef) )
2201 alpha = (lb + ub) / 2.0;
2240 if( *
rho < -10
e+06 )
2290 SCIP_CALL(
computeIntercut(
scip,
nlhdlrdata, nlhdlrexprdata,
rays,
sidefactor,
iscase4,
vb,
vzlp,
wcoefs,
wzlp,
kappa,
2302 for(
i = 0;
i <
rays->nrays; ++
i )
2316 SCIP_CALL(
findRho(
scip,
nlhdlrdata, nlhdlrexprdata,
rays,
i,
sidefactor,
iscase4,
vb,
vzlp,
wcoefs,
wzlp,
kappa,
2333 lppos =
rays->lpposray[
i];
2436 qexpr = nlhdlrexprdata->qexpr;
2439 raylength = (auxvar ==
NULL) ? nquadexprs + nlinexprs : nquadexprs + nlinexprs + 1;
2449 for(
i = 0;
i < nquadexprs; ++
i )
2466 for(
i = 0;
i < nlinexprs; ++
i )
2468 rays->raysbegin[
i + nquadexprs] =
i + nquadexprs;
2469 rays->raysidx[
i + nquadexprs] =
i + nquadexprs;
2480 if( auxvar !=
NULL )
2482 rays->raysbegin[nquadexprs + nlinexprs] = nquadexprs + nlinexprs;
2483 rays->raysidx[nquadexprs + nlinexprs] = nquadexprs + nlinexprs;
2509 SCIP_Real* lincoefs;
2517 qexpr = nlhdlrexprdata->qexpr;
2524 for(
i = 0;
i < nquadexprs;
i++ )
2536 val += sqrcoef *
SQR(solval);
2556 for(
i = 0;
i < nlinexprs;
i++ )
2562 if( auxvar !=
NULL )
2575 if( val <= constant )
2591 SCIP_Bool overestimate,
2614 qexpr = nlhdlrexprdata->qexpr;
2617#ifdef DEBUG_INTERSECTIONCUT
2644 INTERLOG(
printf(
"Failed to get rays: there is a var with base status ZERO!\n"); )
2654 if( auxvar !=
NULL )
2668 INTERLOG(
printf(
"Failed to use bounds as rays: variable is unbounded!\n"); )
2679 INTERLOG(
printf(
"Failed to use bounds as rays: nearest vertex is not violated!\n"); )
2696 if( nlinexprs == 0 && auxvar ==
NULL )
2698 for(
i = 0;
i < nquadexprs; ++
i )
2702 if(
i == nquadexprs )
2723 SCIP_CALL(
computeIntercut(
scip,
nlhdlrdata, nlhdlrexprdata,
rays,
sidefactor,
iscase4,
vb,
vzlp,
wcoefs,
wzlp,
kappa,
2758 for(
i = 0;
i < nquadexprs; ++
i )
2766 if( (lincoef != 0.0) + (sqrcoef != 0.0) + nadjbilin >= 2 )
2793 return (lincoef != 0.0) + (sqrcoef != 0.0) + nadjbilin >= 2;
2806 SCIP_Bool* infeasible,
2856 SCIP_Bool* infeasible,
2935 if(
a >= 0.0 ||
c <= 0.0 )
3021 SCIP_Real* lincoefs,
3024 SCIP_Bool* infeasible,
3032 if( nlinexprs == 0 )
3038 for(
i = 0;
i < nlinexprs; ++
i )
3044 if( *nreductions > 0 && !*infeasible )
3048 for(
i = 0;
i < nlinexprs && ! (*infeasible); ++
i )
3072 if( (*nlhdlrexprdata)->quadactivities !=
NULL )
3136 SCIP_Real* eigenvalues;
3176 SCIPdebugMsg(
scip,
"expr %p is not quadratic -> abort detect\n", (
void*)expr);
3185 SCIPdebugMsg(
scip,
"expr %p is not propagable and in presolving -> abort detect\n", (
void*)expr);
3194 SCIPdebugMsg(
scip,
"expr %p is not propagable -> abort detect\n", (
void*)expr);
3225 for(
i = 0;
i < nlinexprs; ++
i )
3228 for(
i = 0;
i < nquadexprs; ++
i )
3252 if( sqrexpr !=
NULL )
3292 for(
j = 0;
j < nquadexprs; ++
j )
3296 if( expr1 ==
exprj )
3327 SCIPdebugMsg(
scip,
"expr %p is quadratic and propagable -> propagate\n", (
void*)expr);
3373 for(
i = 0;
i < nlinexprs; ++
i )
3377 for(
i = 0;
i < nquadexprs; ++
i )
3384 SCIPdebugMsg(
scip,
"expr %p is quadratic and propagable -> propagate and separate\n", (
void*)expr);
3390 SCIPdebugMsg(
scip,
"expr %p is quadratic and propagable -> propagate only\n", (
void*)expr);
3412 SCIP_Real* lincoefs;
3418 assert(nlhdlrexprdata->separating);
3419 assert(nlhdlrexprdata->qexpr == expr);
3422 if( nlhdlrexprdata->origvars )
3435 *auxvalue = constant;
3437 for(
i = 0;
i < nlinexprs; ++
i )
3440 for(
i = 0;
i < nquadexprs; ++
i )
3450 *auxvalue += (lincoef + sqrcoef * solval) * solval;
3477 SCIP_Longint nodenumber;
3478 SCIP_Real* eigenvalues;
3482 assert(nlhdlrexprdata->qexpr == expr);
3527 if(
nlhdlrdata->lastnodenumber != nodenumber )
3536 nlhdlrexprdata->ncutsadded >=
nlhdlrdata->ncutslimitroot) )
3544 if( eigenvalues ==
NULL )
3551 if( cons != nlhdlrexprdata->cons )
3571 if( nlhdlrexprdata->cons !=
NULL && cons != nlhdlrexprdata->cons )
3573 INTERLOG(
printf(
"WARNING!! expr is root of one constraint and subexpr of another!\n"); )
3583 INTERLOG(
printf(
"We are actually feasible for the sides of the constraint\n"); )
3587#ifdef DEBUG_INTERSECTIONCUT
3589 if( cons == nlhdlrexprdata->cons )
3617 nlhdlrexprdata->ncutsadded += 1;
3630 SCIP_Bool infeasible;
3637 overestimate ?
"over" :
"under",
3720 SCIP_Real* lincoefs;
3729 assert(nlhdlrexprdata->quadactivities !=
NULL);
3730 assert(nlhdlrexprdata->qexpr == expr);
3745 for(
i = 0;
i < nlinexprs; ++
i )
3760 SCIPdebugMsg(
scip,
"Activity of linear part is [%g, %g]\n", nlhdlrexprdata->linactivity.inf,
3761 nlhdlrexprdata->linactivity.sup);
3772 nlhdlrexprdata->nneginfinityquadact = 0;
3773 nlhdlrexprdata->nposinfinityquadact = 0;
3774 nlhdlrexprdata->minquadfiniteact = 0.0;
3775 nlhdlrexprdata->maxquadfiniteact = 0.0;
3778 for(
i = 0;
i < nquadexprs; ++
i )
3801 if( sqrcoef != 0.0 )
3831 if( expr1 == qexpr )
3878 for(
j = 0;
j < nadjbilin; ++
j )
3887 if( expr1 != qexpr )
3922 SCIPinfoMessage(
scip,
NULL,
"Computing activity for quadratic term %g <expr>^2 + [%g,%g] <expr>, where <expr> is: ", sqrcoef,
b.inf,
b.sup);
3935 nlhdlrexprdata->nneginfinityquadact++;
3943 nlhdlrexprdata->minquadfiniteact +=
quadlb;
3948 nlhdlrexprdata->nposinfinityquadact++;
3956 nlhdlrexprdata->maxquadfiniteact +=
quadub;
3962 SCIPdebugMsg(
scip,
"Activity of quadratic part is [%g, %g]\n", nlhdlrexprdata->quadactivity.inf, nlhdlrexprdata->quadactivity.sup);
3984 SCIP_Real* lincoefs;
3993 SCIPdebugMsg(
scip,
"Reverse propagation of quadratic expr given bounds = [%g,%g]\n", bounds.inf, bounds.sup);
4000 assert(nlhdlrexprdata->quadactivities !=
NULL);
4001 assert(nlhdlrexprdata->qexpr == expr);
4084 for(
i = 0;
i < nquadexprs; ++
i )
4109 nlhdlrexprdata->nposinfinityquadact == 0 )
4120 nlhdlrexprdata->nposinfinityquadact == 1 )
4121 rest_i.sup = nlhdlrexprdata->maxquadfiniteact;
4127 nlhdlrexprdata->nneginfinityquadact == 0 )
4138 nlhdlrexprdata->nneginfinityquadact == 1 )
4139 rest_i.inf = nlhdlrexprdata->minquadfiniteact;
4143#ifdef SCIP_DISABLED_CODE
4171 if( sqrcoef != 0.0 )
4195 if( expr1 == qexpr )
4216 for(
j = 0;
j < nadjbilin; ++
j )
4223 if( expr1 != qexpr )
4249 if(
nbilin > 0 && !*infeasible )
4271 infeasible, &
nreds) );
4274 *nreductions +=
nreds;
4340 "whether to use intersection cuts for quadratic constraints to separate",
4344 "whether the strengthening should be used",
4348 "use bounds of variables in quadratic as rays for intersection cuts",
4352 "limit for number of cuts generated consecutively",
4356 "limit for number of cuts generated at root node",
4360 "maximal rank a slackvar can have",
4364 "minimal cut violation the generated cuts must fulfill to be added to the LP",
4368 "minimal violation the constraint must fulfill such that a cut is generated",
4372 "determines at which nodes cut is used (if it's -1, it's used only at the root node, if it's n >= 0, it's used at every multiple of n",
4376 "limit for number of rays we do the strengthening for",
4380 "should cut be generated even with bad numerics when restricting to ray?",
4384 "should cut be added even when range / efficacy is large?",
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
power and signed power expression handlers
product expression handler
variable expression handler
SCIP_Longint SCIPgetCurBoundsTagNonlinear(SCIP_CONSHDLR *conshdlr)
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
SCIP_RETCODE SCIPtightenExprIntervalNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_INTERVAL newbounds, SCIP_Bool *cutoff, int *ntightenings)
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
SCIP_INTERVAL SCIPgetExprBoundsNonlinear(SCIP *scip, SCIP_EXPR *expr)
SCIP_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)
int SCIPgetSubscipDepth(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPincludeNlhdlrQuadratic(SCIP *scip)
SCIP_Real SCIPnextafter(SCIP_Real from, SCIP_Real to)
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 SCIPswapReals(SCIP_Real *value1, SCIP_Real *value2)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
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_RETCODE SCIPprintExprQuadratic(SCIP *scip, SCIP_EXPR *expr)
void SCIPexprGetQuadraticBilinTerm(SCIP_EXPR *expr, int termidx, SCIP_EXPR **expr1, SCIP_EXPR **expr2, SCIP_Real *coef, int *pos2, SCIP_EXPR **prodexpr)
void SCIPexprSetCurvature(SCIP_EXPR *expr, SCIP_EXPRCURV curvature)
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
SCIP_Bool SCIPexprAreQuadraticExprsVariables(SCIP_EXPR *expr)
void SCIPexprGetQuadraticData(SCIP_EXPR *expr, SCIP_Real *constant, int *nlinexprs, SCIP_EXPR ***linexprs, SCIP_Real **lincoefs, int *nquadexprs, int *nbilinexprs, SCIP_Real **eigenvalues, SCIP_Real **eigenvectors)
SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
SCIP_Longint SCIPexprGetActivityTag(SCIP_EXPR *expr)
SCIP_RETCODE SCIPcheckExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
void SCIPexprGetQuadraticQuadTerm(SCIP_EXPR *quadexpr, int termidx, SCIP_EXPR **expr, SCIP_Real *lincoef, SCIP_Real *sqrcoef, int *nadjbilin, int **adjbilin, SCIP_EXPR **sqrexpr)
void SCIPintervalSetRoundingModeUpwards(void)
void SCIPintervalSetRoundingModeDownwards(void)
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
SCIP_Real SCIPintervalQuadUpperBound(SCIP_Real infinity, SCIP_Real a, SCIP_INTERVAL b_, SCIP_INTERVAL x)
SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
void SCIPintervalSquareRoot(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void)
void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode)
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalDivScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
void SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_Real lincoeff, SCIP_Real rhs, SCIP_INTERVAL xbnds)
SCIP_Real SCIPintervalNegateReal(SCIP_Real x)
int SCIPintervalPropagateWeightedSum(SCIP_Real infinity, int noperands, SCIP_INTERVAL *operands, SCIP_Real *weights, SCIP_Real constant, SCIP_INTERVAL rhs, SCIP_INTERVAL *resultants, SCIP_Bool *infeasible)
void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
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_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
int SCIPgetNLPCols(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
#define SCIPfreeBuffer(scip, ptr)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBlockMemory(scip, ptr)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPallocBuffer(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_NLHDLRDATA * SCIPnlhdlrGetData(SCIP_NLHDLR *nlhdlr)
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr,)
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
SCIP_NLHDLR * SCIPfindNlhdlrNonlinear(SCIP_CONSHDLR *conshdlr, const char *name)
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)),)
void SCIPnlhdlrSetFreeHdlrData(SCIP_NLHDLR *nlhdlr,)
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr,)
SCIP_RETCODE SCIPincludeNlhdlrNonlinear(SCIP *scip, SCIP_NLHDLR **nlhdlr, const char *name, const char *desc, int detectpriority, int enfopriority, SCIP_DECL_NLHDLRDETECT((*detect)), SCIP_DECL_NLHDLREVALAUX((*evalaux)), SCIP_NLHDLRDATA *nlhdlrdata)
void SCIPnlhdlrSetProp(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINTEVAL((*inteval)),)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
int SCIPnodeGetDepth(SCIP_NODE *node)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, 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_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
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 SCIPprintTransSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_TABLE * SCIPfindTable(SCIP *scip, const char *name)
SCIP_RETCODE SCIPincludeTable(SCIP *scip, const char *name, const char *desc, SCIP_Bool active, SCIP_DECL_TABLECOPY((*tablecopy)), SCIP_DECL_TABLEFREE((*tablefree)), SCIP_DECL_TABLEINIT((*tableinit)), SCIP_DECL_TABLEEXIT((*tableexit)), SCIP_DECL_TABLEINITSOL((*tableinitsol)), SCIP_DECL_TABLEEXITSOL((*tableexitsol)), SCIP_DECL_TABLEOUTPUT((*tableoutput)), SCIP_TABLEDATA *tabledata, int position, SCIP_STAGE earlieststage)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisSumRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIProwprepGetSide(SCIP_ROWPREP *rowprep)
void SCIPmergeRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep)
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
void SCIProwprepSetSidetype(SCIP_ROWPREP *rowprep, SCIP_SIDETYPE sidetype)
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
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)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
#define BMSclearMemory(ptr)
#define BMSclearMemoryArray(ptr, num)
static SCIP_Bool raysAreDependent(SCIP *scip, SCIP_Real *raycoefs1, int *rayidx1, int raynnonz1, SCIP_Real *raycoefs2, int *rayidx2, int raynnonz2, SCIP_Real *coef)
#define NLHDLR_DETECTPRIORITY
#define DEFAULT_USEBOUNDS
#define DEFAULT_USESTRENGTH
static SCIP_Real computeMaxBoundaryForBilinearProp(SCIP_Real a, SCIP_Real c, SCIP_Real x1, SCIP_Real x2)
static SCIP_RETCODE setVarToNearestBound(SCIP *scip, SCIP_SOL *sol, SCIP_SOL *vertex, SCIP_VAR *var, SCIP_Real *factor, SCIP_Bool *success)
static void computeRangeForBilinearProp(SCIP_INTERVAL exprdom, SCIP_Real coef, SCIP_INTERVAL rhs, SCIP_INTERVAL *range)
static SCIP_RETCODE computeIntercut(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_ROWPREP *rowprep, SCIP_Real *interpoints, SCIP_SOL *sol, SCIP_Bool *success)
#define NLHDLR_ENFOPRIORITY
static SCIP_RETCODE computeRestrictionToRay(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *raycoefs, int *rayidx, int raynnonz, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real *coefs1234a, SCIP_Real *coefs4b, SCIP_Real *coefscondition, SCIP_Bool *success)
static SCIP_RETCODE findRho(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, int idx, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real *interpoints, SCIP_Real *rho, SCIP_Bool *success)
static SCIP_RETCODE createAndStoreSparseRays(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, RAYS **raysptr, SCIP_Bool *success)
static SCIP_RETCODE insertRayEntry(SCIP *scip, RAYS *rays, SCIP_Real coef, int coefidx, int coefpos)
static SCIP_RETCODE propagateBoundsQuadExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_Real sqrcoef, SCIP_INTERVAL b, SCIP_INTERVAL rhs, SCIP_Bool *infeasible, int *nreductions)
static SCIP_RETCODE createBoundRays(SCIP *scip, RAYS **rays, int size)
#define TABLE_DESC_QUADRATIC
static void freeRays(SCIP *scip, RAYS **rays)
static void combineRays(SCIP_Real *raycoefs1, int *rayidx1, int raynnonz1, SCIP_Real *raycoefs2, int *rayidx2, int raynnonz2, SCIP_Real *newraycoefs, int *newrayidx, int *newraynnonz, SCIP_Real coef1, SCIP_Real coef2)
static SCIP_Real computeEigenvecDotRay(SCIP_Real *eigenvec, int nquadvars, SCIP_Real *raycoefs, int *rayidx, int raynnonz)
static SCIP_Bool isPropagableTerm(SCIP_EXPR *qexpr, int idx)
static SCIP_Real computeWRayLinear(SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real sidefactor, SCIP_Real *raycoefs, int *rayidx, int raynnonz)
#define DEFAULT_NCUTSROOT
static SCIP_RETCODE storeDenseTableauRow(SCIP *scip, SCIP_COL *col, int *basicvarpos2tableaurow, int nbasiccol, int raylength, SCIP_Real *binvrow, SCIP_Real *binvarow, SCIP_Real *tableaurows)
static SCIP_RETCODE addRowToCut(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real cutcoef, SCIP_ROW *row, SCIP_Bool *success)
static SCIP_Real computeIntersectionPoint(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_Bool iscase4, SCIP_Real *coefs1234a, SCIP_Real *coefs4b, SCIP_Real *coefscondition)
static SCIP_Real isCase4a(SCIP_Real tsol, SCIP_Real *coefs4a, SCIP_Real *coefscondition)
static SCIP_Real computeMaxForBilinearProp(SCIP_Real a, SCIP_Real c, SCIP_INTERVAL dom)
#define DEFAULT_USEINTERCUTS
static void constructLPPos2ConsPosMap(SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, int *map)
static SCIP_Real computeRoot(SCIP *scip, SCIP_Real *coefs)
static SCIP_Bool isQuadConsViolated(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, SCIP_SOL *sol, SCIP_Real sidefactor)
static SCIP_Bool areCoefsNumericsGood(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_Real *coefs1234a, SCIP_Real *coefs4b, SCIP_Bool iscase4)
static SCIP_RETCODE intercutsComputeCommonQuantities(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, SCIP_Real sidefactor, SCIP_SOL *sol, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real *wzlp, SCIP_Real *kappa)
static SCIP_Real evalPhiAtRay(SCIP_Real t, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e)
#define TABLE_POSITION_QUADRATIC
static SCIP_RETCODE insertRayEntries(SCIP *scip, RAYS *rays, SCIP_Real *densetableaucols, int *rayentry2conspos, int raylength, int nray, int conspos, SCIP_Real factor, int *nnonz, SCIP_Bool *success)
static SCIP_RETCODE computeStrengthenedIntercut(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *strengthsuccess)
#define TABLE_NAME_QUADRATIC
#define INTERCUTS_MINVIOL
static SCIP_RETCODE propagateBoundsLinExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_Real b, SCIP_INTERVAL rhs, SCIP_Bool *infeasible, int *nreductions)
static SCIP_RETCODE createRays(SCIP *scip, RAYS **rays)
#define BINSEARCH_MAXITERS
static int countBasicVars(SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, SCIP_Bool *nozerostat)
static SCIP_RETCODE findVertexAndGetRays(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_SOL *vertex, SCIP_VAR *auxvar, RAYS **raysptr, SCIP_Bool *success)
static SCIP_RETCODE reversePropagateLinearExpr(SCIP *scip, SCIP_EXPR **linexprs, int nlinexprs, SCIP_Real *lincoefs, SCIP_Real constant, SCIP_INTERVAL rhs, SCIP_Bool *infeasible, int *nreductions)
static SCIP_Bool isPropagable(SCIP_EXPR *qexpr)
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 storeDenseTableauRowsByColumns(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, int raylength, SCIP_VAR *auxvar, SCIP_Real *tableaurows, int *rayentry2conspos)
#define TABLE_EARLIEST_STAGE_QUADRATIC
static SCIP_RETCODE constructBasicVars2TableauRowMap(SCIP *scip, int *map)
static SCIP_RETCODE rayInRecessionCone(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, int j, int i, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real alpha, SCIP_Bool *inreccone, SCIP_Bool *success)
static SCIP_RETCODE generateIntercut(SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool overestimate, SCIP_Bool *success)
static SCIP_RETCODE addColToCut(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real cutcoef, SCIP_COL *col)
nonlinear handler to handle quadratic expressions
preparation of a linear inequality to become a SCIP_ROW
public functions of nonlinear handlers of nonlinear constraints
#define SCIP_NLHDLR_METHOD_SEPAABOVE
#define SCIP_DECL_NLHDLREVALAUX(x)
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
#define SCIP_NLHDLR_METHOD_SEPABOTH
#define SCIP_DECL_NLHDLRCOPYHDLR(x)
#define SCIP_NLHDLR_METHOD_ACTIVITY
#define SCIP_DECL_NLHDLRFREEEXPRDATA(x)
#define SCIP_DECL_NLHDLRDETECT(x)
#define SCIP_NLHDLR_METHOD_NONE
#define SCIP_DECL_NLHDLRFREEHDLRDATA(x)
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
#define SCIP_DECL_NLHDLRREVERSEPROP(x)
#define SCIP_NLHDLR_METHOD_ALL
#define SCIP_DECL_NLHDLRENFO(x)
#define SCIP_DECL_NLHDLRINTEVAL(x)
#define SCIP_NLHDLR_METHOD_SEPABELOW
enum SCIP_Retcode SCIP_RETCODE
#define SCIP_DECL_TABLEOUTPUT(x)