nlhdlr_convex.c
Go to the documentation of this file.
54 #define INITLPMAXVARVAL 1000.0 /**< maximal absolute value of variable for still generating a linearization cut at that point in initlp */
71 int nleafs; /**< number of distinct leafs of nlexpr, i.e., number of distinct (auxiliary) variables handled */
72 SCIP_EXPR** leafexprs; /**< distinct leaf expressions (excluding value-expressions), thus variables */
78 SCIP_Bool isnlhdlrconvex; /**< whether this data is used for the convex nlhdlr (TRUE) or the concave one (FALSE) */
83 SCIP_Bool detectsum; /**< whether to run detection when the root of an expression is a non-quadratic sum */
84 SCIP_Bool extendedform; /**< whether to create extended formulations instead of looking for maximal possible subexpression */
90 SCIP_Bool handletrivial; /**< whether to handle trivial expressions, i.e., those where all children are variables */
93 /** data struct to be be passed on to vertexpoly-evalfunction (see SCIPcomputeFacetVertexPolyhedralNonlinear) */
101 /** stack used in constructExpr to store expressions that need to be investigated ("to do list") */
112 SCIP_Bool isrootexpr, /**< whether nlexpr is the root from where detection has been started */ \
114 SCIP_HASHMAP* nlexpr2origexpr, /**< mapping from our expression copy to original expression */ \
116 SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */ \
175 SCIP_EXPRCURV* childrencurv /**< curvature required for children, or NULL if to set to UNKNOWN */
231 SCIP_CALL_ABORT( SCIPevalExpr(evaldata->scip, evaldata->nlhdlrexprdata->nlexpr, evaldata->evalsol, 0L) );
287 exprstack->stacksize = SCIPcalcMemGrowSize(scip, exprstack->stackpos+1 + nexprs); /*lint !e644*/
291 memcpy(exprstack->stack + (exprstack->stackpos+1), exprs, nexprs * sizeof(SCIP_EXPR*)); /*lint !e679*/ /*lint !e737*/
323 * Hence, not using this for a simple square term, as curvCheckExprhdlr may provide a better condition on argument curvature then.
369 /* if only single square term (+linear), then give up here (let curvCheckExprhdlr handle this) */
373 /* if root expression is only sum of squares (+linear) and detectsum is disabled, then give up here, too */
378 * TODO as we know what curvature we want, we could first do some simple checks like computing xQx for a random x
380 SCIP_CALL( SCIPcomputeExprQuadraticCurvature(scip, expr, &presentcurv, assumevarfixed, FALSE) );
431 /* square term that isn't lonely, i.e., orig-version of child is a square-expr and nadjbilin>0 */
436 else if( SCIPisExprProduct(scip, child) && SCIPexprGetNChildren(SCIPexprGetChildren(expr)[i]) == 2 )
447 * if we want extended formulations, then require linearity, so an auxvar will be introduced if it is nonlinear
449 * thus, if the coef is negative, then the child needs to have the curvature opposite to "wantedcurv"
465 /** looks whether top of given expression looks like a signomial that can have a given curvature
469 * unfortunately, doesn't work for tls, because i) it's originally sqrt(x*y), and ii) it is expanded into some sqrt(z*y+y);
526 if( !SCIPexprcurvMonomialInv(SCIPexprcurvMultiply(SCIPgetCoefExprProduct(expr), SCIPexprGetCurvature(nlexpr)),
539 * unless they are linear, an auxvar will be introduced for them and thus they will be handled as var here
577 /** looks for \f$f(c h(x)+d) h(x) \cdot \text{constant}\f$ and tries to conclude conditions on curvature
581 * - Second derivative is \f{align}{&f''(c h + d) c h' c h' h + f'(c h + d) (c h'' h + c h' h') + f'(c h + d) c h' h' + f(c h + d) h'' \\
583 * Remove always positive factors leaves \f[f''(c h + d) h,\quad f'(c h + d) c h'' h,\quad f'(c h + d) c,\quad f(c h + d) h''.\f]
584 * For convexity we want all these terms to be nonnegative. For concavity we want all of them to be nonpositive.
586 * - Thus, \f$f(c h(x) + d)h(x)\f$ is convex if \f$cf\f$ is monotonically increasing \f$(c f' \geq 0)\f$ and either
587 * - \f$f\f$ is convex \f$(f'' \geq 0)\f$ and \f$h\f$ is nonnegative \f$(h \geq 0)\f$ and \f$h\f$ is convex \f$(h'' \geq 0)\f$ and [\f$f\f$ is nonnegative \f$(f \geq 0)\f$ or \f$h\f$ is linear \f$(h''=0)\f$], or
588 * - \f$f\f$ is concave \f$(f'' \leq 0)\f$ and \f$h\f$ is nonpositive \f$(h \leq 0)\f$ and \f$h\f$ is concave \f$(h'' \leq 0)\f$ and [\f$f\f$ is nonpositive \f$(f \leq 0)\f$ or \f$h\f$ is linear \f$(h''=0)\f$].
589 * - Further, \f$f(c h(x) + d)h(x)\f$ is concave if \f$cf\f$ is monotonically decreasing \f$(c f' \leq 0)\f$ and either
590 * - f is convex \f$(f'' \geq 0)\f$ and \f$h\f$ is nonpositive \f$(h \leq 0)\f$ and \f$h\f$ is concave \f$(h'' \leq 0)\f$ and [\f$f\f$ is nonnegative \f$(f \geq 0)\f$ or \f$h\f$ is linear \f$(h''=0)\f$], or
591 * - f is concave \f$(f'' \leq 0)\f$ and \f$h\f$ is nonnegative \f$(h >= 0)\f$ and \f$h\f$ is convex \f$(h'' \geq 0)\f$ and [\f$f\f$ is nonpositive \f$(f \leq 0)\f$ or \f$h\f$ is linear \f$(h''=0)\f$].
593 * This should hold also for multivariate and linear \f$h\f$, as things are invariant under linear transformations.
594 * Similar to signomial, I'll assume that this will also hold for other multivariate \f$h\f$ (someone has a formal proof?).
648 assert(c != 1.0 || SCIPgetConstantExprSum(ch) != 0.0); /* we could handle this, but it should have been simplified away */
652 /* can assume that duplicate subexpressions have been identified and comparing pointer is sufficient */
655 /* called from unittest -> duplicate subexpressions were not identified -> compare more expensively */
664 SCIPinfoMessage(scip, NULL, "f(c*h+d)*h with f = %s, c = %g, d = %g, h = ", SCIPexprhdlrGetName(SCIPexprGetHdlr(f)),
688 desiredcurv = SCIPexprcurvMultiply(SCIPgetCoefExprProduct(nlexpr), SCIPexprGetCurvature(nlexpr));
694 * - f is convex (f'' >= 0) and h is nonnegative (h >= 0) and h is convex (h'' >= 0) and [f is nonnegative (f >= 0) or h is linear (h''=0)], or
695 * - f is concave (f'' <= 0) and h is nonpositive (h <= 0) and h is concave (h'' <= 0) and [f is nonpositive (f <= 0) or h is linear (h''=0)]
696 * as the curvature requirements on f are on f only and not the composition f(h), we can ignore the requirements returned by SCIPcallExprCurvature (last arg)
698 if( (c > 0.0 && fmonotonicity != SCIP_MONOTONE_INC) || (c < 0.0 && fmonotonicity != SCIP_MONOTONE_DEC) )
701 /* check whether f can be convex (h>=0) or concave (h<=0), resp., and derive requirements for h */
726 * - f is convex (f'' >= 0) and h is nonpositive (h <= 0) and h is concave (h'' <= 0) and [f is nonnegative (f >= 0) or h is linear (h''=0)], or
727 * - f is concave (f'' <= 0) and h is nonnegative (h >= 0) and h is convex (h'' >= 0) and [f is nonpositive (f <= 0) or h is linear (h''=0)]
728 * as the curvature requirements on f are on f only and not the composition f(h), we can ignore the requirements returned by SCIPcallExprCurvature (last arg)
730 if( (c > 0.0 && fmonotonicity != SCIP_MONOTONE_DEC) || (c < 0.0 && fmonotonicity != SCIP_MONOTONE_INC) )
733 /* check whether f can be convex (h<=0) or concave (h>=0), resp., and derive requirements for h */
759 /* add immediate children (f and ch) to nlexpr; we set required curvature for h further below */
763 /* copy of f (and h) should have same child position in nlexpr as f (and h) has on expr (resp) */
764 assert(SCIPhashmapGetImage(nlexpr2origexpr, (void*)SCIPexprGetChildren(nlexpr)[fidx]) == (void*)f);
766 assert(SCIPhashmapGetImage(nlexpr2origexpr, (void*)SCIPexprGetChildren(nlexpr)[1-fidx]) == (void*)h);
781 SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, SCIPexprGetChildren(nlexpr)[fidx], NULL) );
783 assert(SCIPhashmapGetImage(nlexpr2origexpr, (void*)SCIPexprGetChildren(SCIPexprGetChildren(nlexpr)[fidx])[0]) == (void*)ch);
801 /** use expression handlers curvature callback to check whether given curvature can be achieved */
823 SCIP_CALL( SCIPcallExprCurvature(scip, origexpr, SCIPexprGetCurvature(nlexpr), success, NULL) );
830 * NOTE: this means that for something like 1+f(x), even if f is a trivial convex expression, we would handle 1+f(x)
831 * with this nlhdlr, instead of formulating this as 1+z and handling z=f(x) with the default nlhdlr, i.e., the exprhdlr
840 SCIP_CALL( SCIPcallExprCurvature(scip, origexpr, SCIPexprGetCurvature(nlexpr), success, childcurv) );
843 SCIPinfoMessage(scip, NULL, " is %s? %d\n", SCIPexprcurvGetName(SCIPexprGetCurvature(nlexpr)), *success);
848 /* if origexpr can have curvature curv, then don't treat it as leaf, but include its children */
854 * Unless they are, auxvars will be introduced and they will be handles as variables, which can be an
880 * some day this could be plugins added by users at runtime, but for now we have a fixed list here
883 static DECL_CURVCHECK((*CURVCHECKS[])) = { curvCheckProductComposite, curvCheckSignomial, curvCheckQuadratic, curvCheckExprhdlr };
887 /** checks whether expression is a sum with more than one child and each child being a variable or going to be a variable if `expr` is a nlhdlr-specific copy
889 * Within constructExpr(), we can have an expression of any type which is a copy of an original expression,
890 * but without children. At the end of constructExpr() (after the loop with the stack), these expressions
891 * will remain as leafs and will eventually be turned into variables in collectLeafs(). Thus, we treat
892 * every child that has no children as if it were a variable. Theoretically, there is still the possibility
921 /** constructs a subexpression (as nlhdlr-expression) of maximal size that has a given curvature
937 SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */
938 SCIP_Bool assumecurvature, /**< whether to assume that desired curvature is given (skips curvature checks) */
944 EXPRSTACK stack; /* to do list: expressions where to check whether they can have the desired curvature when taking their children into account */
975 /* if bwdiff is not implemented, then we could not generate cuts in the convex nlhdlr, so "stop" (treat nlexpr as variable) */
977 else if( !nlhdlrdata->isnlhdlrconvex && exprIsMultivarLinear(scip, (SCIP_EXPR*)SCIPhashmapGetImage(nlexpr2origexpr, (void*)nlexpr)) )
979 /* if we are in the concave handler, we would like to treat linear multivariate subexpressions by a new auxvar always,
980 * e.g., handle log(x+y) as log(z), z=x+y, because the estimation problem will be smaller then without making the estimator worse
983 * however, it isn't unlikely that we will have sums that become linear after we add auxvars for some children
985 * for now, the check is performed on the original expression since there is not enough information in nlexpr yet
994 /* if we are here, either convexity or concavity is required; try to check for this curvature */
1001 SCIP_CALL( CURVCHECKS[method](scip, nlexpr, isrootexpr, &stack, nlexpr2origexpr, nlhdlrdata, assumevarfixed, &success) );
1015 SCIP_CALL( exprstackPush(scip, &stack, SCIPexprGetNChildren(nlexpr), SCIPexprGetChildren(nlexpr)) );
1017 assert(stack.stackpos >= oldstackpos); /* none of the methods above should have removed something from the stack */
1023 * or because the desired curvature could not be achieved, so it will be handled as variables, thus a leaf
1039 /* remove multivariate linear subexpressions, that is, change some f(z1+z2) into f(z3) (z3=z1+z2 will be done by nlhdlr_default)
1040 * this handles the case that was not covered by the above check, which could recognize f(x+y) for x, y original variables
1055 /* We want to change some f(x+y+z) into just f(), where f is the expression the iterator points to
1056 * and x+y+z is child. A child of a child, e.g., z, may not be a variable yet (these are added in collectLeafs later),
1066 SCIPinfoMessage(scip, NULL, "... is a multivariate linear sum that we'll treat as auxvar instead (postprocess)\n");
1091 /* if handletrivial is enabled, then only require that rootnlexpr itself has required curvature (so has children; see below) and
1092 * that we are not a trivial sum (because the previous implementation of this nlhdlr didn't allow this, either)
1096 /* if all children do not have children, i.e., are variables, or will be replaced by auxvars, then free
1109 else if( SCIPexprGetNChildren(*rootnlexpr) > 0 ) /* if handletrivial, then just require children */
1121 /** collects (non-value) leaf expressions and ensure that they correspond to a variable (original or auxiliary)
1123 * For children where we could not achieve the desired curvature, get the auxvar and replace the child by a
1155 for( nlexpr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); nlexpr = SCIPexpriterGetNext(it) )
1164 /* if the to-be-visited child has children, then it doesn't need to be replaced by a new expression (representing the auxvar) */
1177 /* having a child that had children in original but not in copy means that we could not achieve the desired curvature
1184 SCIP_CALL( SCIPcreateExprVar(scip, &newchild, var, NULL, NULL) ); /* this captures newchild once */
1187 SCIP_CALL( SCIPreplaceExprChild(scip, nlexpr, childidx, newchild) ); /* this captures newchild again */
1189 /* do not remove child->origexpr from hashmap, as child may appear again due to common subexprs
1195 SCIP_CALL( SCIPhashmapSetImage(nlhdlrexprdata->nlexpr2origexpr, (void*)newchild, (void*)origexpr) );
1204 SCIP_CALL( SCIPreleaseExpr(scip, &newchild) ); /* because it was captured by both create and replace */
1216 /* update integrality flag for future leaf expressions: convex nlhdlr may use this information */
1224 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(nlhdlrexprdata->leafexprs), nlhdlrexprdata->nleafs) );
1295 /* check whether to-be-visited child needs to be replaced by a new expression (representing the auxvar)
1297 * if child has no children, but also corresponding origexpr has no chilren, then this is also not the case
1306 /* if child had children in original but not in copy means that we could not achieve the desired curvature
1307 * thus, we will later replace by a new child that points to the auxvar of the original expression
1308 * as we do not have the auxvar now, we will only register that we will need the auxvar later (if origexpr isn't a variable or constant)
1309 * if we are working for the concave nlhdlr, then we also indicate interest on the exprs activity for estimate (distinguish below or above)
1325 SCIPinfoMessage(scip, NULL, " (%p) is handled as %s\n", SCIPhashmapGetImage(nlexpr2origexpr, (void*)nlexpr),
1329 /* If we don't work on the extended formulation, then set curvature also in original expression
1331 * This doesn't ensure that every convex or concave original expression is actually marked here.
1333 * prefer extended formulations (in nlhdlr_convex), or introduce auxvars for linear subexpressions
1356 SCIP_Real targetvalue, /**< a target value to achieve; if not reachable, then can give up early */
1378 /* caller is responsible to have checked whether we can estimate, i.e., expression curvature and overestimate flag match */
1379 assert( overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONCAVE); /* if underestimate, then must be concave */
1380 assert(!overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONVEX); /* if overestimate, then must be convex */
1392 usemidpoint ? 0.5 * (SCIPvarGetLbLocal(var) + SCIPvarGetUbLocal(var)) : SCIPgetSolVal(scip, sol, var),
1444 /* SCIPcomputeFacetVertexPolyhedralNonlinear prints a warning and does not succeed if all is fixed */
1451 SCIP_CALL( SCIPcomputeFacetVertexPolyhedralNonlinear(scip, conshdlr, overestimate, nlhdlrExprEvalConcave, (void*)&evaldata,
1452 xstar, box, nlhdlrexprdata->nleafs, targetvalue, success, SCIProwprepGetCoefs(rowprep), &facetconstant) );
1464 SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetVarExprVar(nlhdlrexprdata->leafexprs[i]), SCIProwprepGetCoefs(rowprep)[i]) );
1513 SCIPdebugMsg(scip, "evaluation error / too large value (%g) for %p\n", auxvalue, (void*)nlexpr);
1517 /* compute gradient (TODO: this also re-evaluates (soltag=0), which shouldn't be necessary unless we tried ConvexSecant before) */
1567 /** adds an estimator generated by putting a secant through the coordinates given by the two closest integer points */
1646 SCIPdebugMsg(scip, "evaluation error / too large value (%g) for %p\n", SCIPexprGetEvalValue(nlexpr), (void*)nlexpr);
1657 SCIPdebugMsg(scip, "evaluation error / too large value (%g) for %p\n", SCIPexprGetEvalValue(nlexpr), (void*)nlexpr);
1736 /** checks whether expression (or -expression) is convex, possibly after introducing auxiliary variables */
1768 * when expressions will be allowed to store "user"data, we could get rid of this hashmap (TODO)
1782 SCIPdebugMsg(scip, "detected expr %p to be convex -> can enforce expr <= auxvar\n", (void*)expr);
1790 if( (*enforcing & SCIP_NLHDLR_METHOD_SEPAABOVE) == 0 && nlexpr == NULL ) /* if no separation above and not convex */
1800 SCIPdebugMsg(scip, "detected expr %p to be concave -> can enforce expr >= auxvar\n", (void*)expr);
1817 SCIP_CALL( createNlhdlrExprData(scip, nlhdlrdata, nlhdlrexprdata, expr, nlexpr, nlexpr2origexpr, nleafs, *participating) );
1873 /* linearizes at 5 different points obtained as convex combination of the lower and upper bound of the variables
1874 * present in the convex expression; whether more weight is given to the lower or upper bound of a variable depends
1901 /* in the case when ub < -maxabsbnd or lb > maxabsbnd, we still want to at least make bounds finite */
1913 SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, TRUE) );
1936 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_gradient%p_initsepa_%d",
1971 assert(SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, (void*)nlhdlrexprdata->nlexpr) == expr);
1976 assert(!overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONCAVE);
1984 assert(auxvalue == SCIPexprGetEvalValue(nlhdlrexprdata->nlexpr)); /* given value (originally from
1987 SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, TRUE) );
1993 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_convexsecant%p_%s%" SCIP_LONGINT_FORMAT,
2005 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_convexgradient%p_%s%" SCIP_LONGINT_FORMAT,
2052 CONVEX_NLHDLR_DETECTPRIORITY, CONVEX_NLHDLR_ENFOPRIORITY, nlhdlrDetectConvex, nlhdlrEvalAuxConvexConcave, nlhdlrdata) );
2109 /** checks whether expression (or -expression) is concave, possibly after introducing auxiliary variables */
2141 * when expressions will be allowed to store "user"data, we could get rid of this hashmap (TODO)
2152 SCIPdebugMsg(scip, "Too many variables (%d) in constructed expression. Will not be able to estimate. Rejecting.\n", nleafs);
2162 SCIPdebugMsg(scip, "detected expr %p to be concave -> can enforce expr <= auxvar\n", (void*)expr);
2170 if( (*enforcing & SCIP_NLHDLR_METHOD_SEPAABOVE) == 0 && nlexpr == NULL ) /* if no separation above and not concave */
2177 SCIPdebugMsg(scip, "Too many variables (%d) in constructed expression. Will not be able to estimate. Rejecting.\n", nleafs);
2187 SCIPdebugMsg(scip, "detected expr %p to be convex -> can enforce expr >= auxvar\n", (void*)expr);
2204 SCIP_CALL( createNlhdlrExprData(scip, nlhdlrdata, nlhdlrexprdata, expr, nlexpr, nlexpr2origexpr, nleafs, *participating) );
2241 SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, TRUE) );
2242 SCIP_CALL( estimateVertexPolyhedral(scip, conshdlr, nlhdlr, nlhdlrexprdata, NULL, TRUE, overestimate,
2261 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_concave%p_initsepa",
2293 assert(SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, (void*)nlhdlrexprdata->nlexpr) == expr);
2299 assert( overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONCAVE);
2304 SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, TRUE) );
2306 SCIP_CALL( estimateVertexPolyhedral(scip, conshdlr, nlhdlr, nlhdlrexprdata, sol, FALSE, overestimate, targetvalue, rowprep, success) );
2312 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_concave%p_%s%" SCIP_LONGINT_FORMAT,
2342 * if we underestimate, then we enforce expr <= auxval, so violation is (positive part of) auxvalue - auxval
2343 * if we overestimate, then we enforce expr >= auxval, so violation is (positive part of) auxval - auxvalue
2352 /* add violation as branching-score to expressions; the core will take care distributing this onto variables */
2356 e = (SCIP_EXPR*)SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, nlhdlrexprdata->leafexprs[0]);
2369 exprs[c] = (SCIP_EXPR*)SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, nlhdlrexprdata->leafexprs[c]);
2371 SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, exprs, nlhdlrexprdata->nleafs, violation, sol, addedbranchscores) );
2409 CONCAVE_NLHDLR_DETECTPRIORITY, CONCAVE_NLHDLR_ENFOPRIORITY, nlhdlrDetectConcave, nlhdlrEvalAuxConvexConcave, nlhdlrdata) );
2446 * This function uses the methods that are used in the detection algorithm of the convex nonlinear handler.
2452 SCIP_Bool* success, /**< buffer to store whether expression has curvature curv (w.r.t. original variables) */
2453 SCIP_HASHMAP* assumevarfixed /**< hashmap containing variables that should be assumed to be fixed, or NULL */
2478 SCIP_CALL( constructExpr(scip, &nlhdlrdata, &rootnlexpr, nlexpr2origexpr, &nleafs, expr, curv, assumevarfixed, FALSE, success) );
static SCIP_RETCODE estimateConvexSecant(SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
Definition: nlhdlr_convex.c:1569
Definition: nlhdlr_convex.c:94
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)
Definition: expr.c:4057
static SCIP_Bool exprstackIsEmpty(EXPRSTACK *exprstack)
Definition: nlhdlr_convex.c:311
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:491
SCIP_RETCODE SCIPduplicateExprShallow(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1291
Definition: intervalarith.h:44
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1476
Definition: struct_scip.h:59
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:1149
SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
Definition: scip_expr.c:2549
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1706
Definition: type_expr.h:59
Definition: type_expr.h:52
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEEXPRDATA((*freeexprdata)))
Definition: nlhdlr.c:85
SCIP_NLHDLREXPRDATA * nlhdlrexprdata
Definition: nlhdlr_convex.c:96
SCIP_RETCODE SCIPcleanupRowprep2(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefbound, SCIP_Bool *success)
Definition: misc_rowprep.c:1344
SCIP_EXPR * SCIPexpriterSkipDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:920
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
Definition: misc_rowprep.c:769
Definition: struct_misc.h:140
Definition: struct_var.h:198
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3500
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
Definition: cons_nonlinear.c:12920
SCIP_Bool SCIPassumeConvexNonlinear(SCIP_CONSHDLR *conshdlr)
Definition: cons_nonlinear.c:11756
SCIP_RETCODE SCIPcheckExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
Definition: scip_expr.c:2340
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
void SCIPexprSetCurvature(SCIP_EXPR *expr, SCIP_EXPRCURV curvature)
Definition: expr.c:4006
void SCIPnlhdlrSetFreeHdlrData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEHDLRDATA((*freehdlrdata)))
Definition: nlhdlr.c:74
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3699
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
Definition: type_expr.h:53
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3757
static SCIP_RETCODE estimateVertexPolyhedral(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_NLHDLR *nlhdlr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_Bool usemidpoint, SCIP_Bool overestimate, SCIP_Real targetvalue, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
Definition: nlhdlr_convex.c:1348
Definition: type_lp.h:55
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_RETCODE SCIPincludeNlhdlrConvex(SCIP *scip)
Definition: nlhdlr_convex.c:2038
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
Definition: type_expr.h:61
SCIP_RETCODE SCIPcreateExprVar(SCIP *scip, SCIP_EXPR **expr, SCIP_VAR *var, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_var.c:381
defines macros for basic operations in double-double arithmetic giving roughly twice the precision of...
variable expression handler
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
Definition: misc_rowprep.c:855
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:673
Definition: struct_nlhdlr.h:34
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1656
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalAuxConvexConcave)
Definition: nlhdlr_convex.c:1824
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1454
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
Definition: misc_rowprep.c:1646
SCIP_RETCODE SCIPevalExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1623
Definition: struct_sol.h:64
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: scip_expr.c:1723
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:624
Definition: struct_misc.h:128
static SCIP_RETCODE exprstackInit(SCIP *scip, EXPRSTACK *exprstack, int initsize)
Definition: nlhdlr_convex.c:238
static SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateConvex)
Definition: nlhdlr_convex.c:1960
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3489
SCIP_RETCODE SCIPcomputeFacetVertexPolyhedralNonlinear(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool overestimate, SCIP_DECL_VERTEXPOLYFUN((*function)), void *fundata, SCIP_Real *xstar, SCIP_Real *box, int nallvars, SCIP_Real targetvalue, SCIP_Bool *success, SCIP_Real *facetcoefs, SCIP_Real *facetconstant)
Definition: cons_nonlinear.c:12059
Definition: type_expr.h:51
Definition: struct_cons.h:117
static SCIP_RETCODE estimateGradient(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_Real auxvalue, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
Definition: nlhdlr_convex.c:1481
Definition: type_expr.h:691
Definition: type_lp.h:47
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3730
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)
Definition: cons_nonlinear.c:13687
public functions to work with algebraic expressions
Definition: type_expr.h:50
void SCIPexprGetQuadraticQuadTerm(SCIP_EXPR *quadexpr, int termidx, SCIP_EXPR **expr, SCIP_Real *lincoef, SCIP_Real *sqrcoef, int *nadjbilin, int **adjbilin, SCIP_EXPR **sqrexpr)
Definition: expr.c:4104
static SCIP_RETCODE collectLeafs(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
Definition: nlhdlr_convex.c:1128
Definition: type_retcode.h:33
SCIP_RETCODE SCIPreplaceExprChild(SCIP *scip, SCIP_EXPR *expr, int childidx, SCIP_EXPR *newchild)
Definition: scip_expr.c:1238
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:558
int SCIPexpriterGetChildIdxDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:697
static SCIP_Bool exprIsMultivarLinear(SCIP *scip, SCIP_EXPR *expr)
Definition: nlhdlr_convex.c:896
static SCIP_DECL_VERTEXPOLYFUN(nlhdlrExprEvalConcave)
Definition: nlhdlr_convex.c:209
Definition: struct_expr.h:193
SCIP_RETCODE SCIPhasExprCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV curv, SCIP_Bool *success, SCIP_HASHMAP *assumevarfixed)
Definition: nlhdlr_convex.c:2448
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
static SCIP_RETCODE nlhdlrExprGrowChildren(SCIP *scip, SCIP_HASHMAP *nlexpr2origexpr, SCIP_EXPR *nlhdlrexpr, SCIP_EXPRCURV *childrencurv)
Definition: nlhdlr_convex.c:171
static SCIP_DECL_NLHDLRDETECT(nlhdlrDetectConvex)
Definition: nlhdlr_convex.c:1738
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2300
SCIP_Real SCIPgetCoefExprProduct(SCIP_EXPR *expr)
Definition: expr_product.c:2146
nonlinear handlers for convex and concave expressions, respectively
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)), SCIP_DECL_NLHDLREXITSEPA((*exitsepa)))
Definition: nlhdlr.c:123
Definition: struct_expr.h:95
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
static SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrConvex)
Definition: nlhdlr_convex.c:2026
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: misc_rowprep.c:728
Definition: struct_misc.h:121
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
constraint handler for nonlinear constraints specified by algebraic expressions
static SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaConvex)
Definition: nlhdlr_convex.c:1838
SCIP_Bool SCIPexprcurvMonomialInv(SCIP_EXPRCURV monomialcurv, int nfactors, SCIP_Real *exponents, SCIP_INTERVAL *factorbounds, SCIP_EXPRCURV *factorcurv)
Definition: exprcurv.c:447
Definition: struct_lp.h:192
SCIP_RETCODE SCIPappendExprChild(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child)
Definition: scip_expr.c:1220
Definition: nlhdlr_convex.c:102
SCIP_RETCODE SCIPcomputeExprIntegrality(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1988
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:848
SCIP_EXPR * SCIPexpriterGetChildExprDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:711
static void exprstackFree(SCIP *scip, EXPRSTACK *exprstack)
Definition: nlhdlr_convex.c:257
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition: expriter.c:654
Definition: type_expr.h:60
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3740
SCIP_RETCODE SCIPhashmapSetImage(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3263
void SCIPnlhdlrSetInitExit(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINIT((*init)), SCIP_DECL_NLHDLREXIT((*exit_)))
Definition: nlhdlr.c:97
SCIP_RETCODE SCIPaddExprsViolScoreNonlinear(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Real violscore, SCIP_SOL *sol, SCIP_Bool *success)
Definition: cons_nonlinear.c:13414
Definition: type_lp.h:56
int SCIPhashmapEntryGetImageInt(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3520
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
static SCIP_RETCODE nlhdlrExprCreate(SCIP *scip, SCIP_HASHMAP *nlexpr2origexpr, SCIP_EXPR **nlhdlrexpr, SCIP_EXPR *origexpr, SCIP_EXPRCURV curv)
Definition: nlhdlr_convex.c:129
static SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrfreeExprDataConvexConcave)
Definition: nlhdlr_convex.c:1704
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
Definition: misc_rowprep.c:538
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
Definition: misc_rowprep.c:881
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:102
SCIP_EXPRCURV SCIPexprcurvMultiply(SCIP_Real factor, SCIP_EXPRCURV curvature)
Definition: exprcurv.c:78
static SCIP_RETCODE exprstackPush(SCIP *scip, EXPRSTACK *exprstack, int nexprs, SCIP_EXPR **exprs)
Definition: nlhdlr_convex.c:270
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12778
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3096
static SCIP_RETCODE createNlhdlrExprData(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_EXPR *expr, SCIP_EXPR *nlexpr, SCIP_HASHMAP *nlexpr2origexpr, int nleafs, SCIP_NLHDLR_METHOD participating)
Definition: nlhdlr_convex.c:1255
static SCIP_RETCODE constructExpr(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_EXPR **rootnlexpr, SCIP_HASHMAP *nlexpr2origexpr, int *nleafs, SCIP_EXPR *rootexpr, SCIP_EXPRCURV curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool assumecurvature, SCIP_Bool *curvsuccess)
Definition: nlhdlr_convex.c:929
SCIPallocBlockMemory(scip, subsol))
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
Definition: misc_rowprep.c:748
public functions of nonlinear handlers of nonlinear constraints
SCIP_RETCODE SCIPincludeNlhdlrConcave(SCIP *scip)
Definition: nlhdlr_convex.c:2395
Definition: objbenders.h:33
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
static SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrfreeHdlrDataConvexConcave)
Definition: nlhdlr_convex.c:1690
preparation of a linear inequality to become a SCIP_ROW
SCIP_RETCODE SCIPremoveExprChildren(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1257
SCIP_RETCODE SCIPsetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx, void *val)
Definition: scip_datastructures.c:565
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)
Definition: scip_param.c:48
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
Definition: struct_misc.h:277
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRCOPYHDLR((*copy)))
Definition: nlhdlr.c:63