nonlinear handlers for convex and concave expressions
Definition in file nlhdlr_convex.c.
#include <string.h>
#include "scip/nlhdlr_convex.h"
#include "scip/pub_nlhdlr.h"
#include "scip/scip_expr.h"
#include "scip/cons_nonlinear.h"
#include "scip/expr_var.h"
#include "scip/expr_abs.h"
#include "scip/pub_misc_rowprep.h"
#include "scip/dbldblarith.h"
Go to the source code of this file.
Data Structures | |
struct | VERTEXPOLYFUN_EVALDATA |
struct | EXPRSTACK |
Macros | |
#define | CONVEX_NLHDLR_NAME "convex" |
#define | CONVEX_NLHDLR_DESC "handler that identifies and estimates convex expressions" |
#define | CONVEX_NLHDLR_DETECTPRIORITY 50 |
#define | CONVEX_NLHDLR_ENFOPRIORITY 50 |
#define | CONCAVE_NLHDLR_NAME "concave" |
#define | CONCAVE_NLHDLR_DESC "handler that identifies and estimates concave expressions" |
#define | CONCAVE_NLHDLR_DETECTPRIORITY 40 |
#define | CONCAVE_NLHDLR_ENFOPRIORITY 40 |
#define | DEFAULT_DETECTSUM FALSE |
#define | DEFAULT_EXTENDEDFORM TRUE |
#define | DEFAULT_CVXQUADRATIC_CONVEX TRUE |
#define | DEFAULT_CVXQUADRATIC_CONCAVE FALSE |
#define | DEFAULT_CVXSIGNOMIAL TRUE |
#define | DEFAULT_CVXPRODCOMP TRUE |
#define | DEFAULT_HANDLETRIVIAL FALSE |
#define | DEFAULT_MAXPERTURB 0.01 |
#define | INITLPMAXVARVAL 1000.0 |
#define | RANDNUMINITSEED 220802 |
#define | DECL_CURVCHECK(x) |
Functions | |
static SCIP_RETCODE | nlhdlrExprCreate (SCIP *scip, SCIP_HASHMAP *nlexpr2origexpr, SCIP_EXPR **nlhdlrexpr, SCIP_EXPR *origexpr, SCIP_EXPRCURV curv) |
static SCIP_RETCODE | nlhdlrExprGrowChildren (SCIP *scip, SCIP_HASHMAP *nlexpr2origexpr, SCIP_EXPR *nlhdlrexpr, SCIP_EXPRCURV *childrencurv) |
static | SCIP_DECL_VERTEXPOLYFUN (nlhdlrExprEvalConcave) |
static SCIP_RETCODE | exprstackInit (SCIP *scip, EXPRSTACK *exprstack, int initsize) |
static void | exprstackFree (SCIP *scip, EXPRSTACK *exprstack) |
static SCIP_RETCODE | exprstackPush (SCIP *scip, EXPRSTACK *exprstack, int nexprs, SCIP_EXPR **exprs) |
static SCIP_EXPR * | exprstackPop (EXPRSTACK *exprstack) |
static SCIP_Bool | exprstackIsEmpty (EXPRSTACK *exprstack) |
static | DECL_CURVCHECK (curvCheckQuadratic) |
static | DECL_CURVCHECK (curvCheckSignomial) |
static | DECL_CURVCHECK (curvCheckProductComposite) |
static | DECL_CURVCHECK (curvCheckExprhdlr) |
static | DECL_CURVCHECK ((*CURVCHECKS[])) |
static SCIP_Bool | exprIsMultivarLinear (SCIP *scip, SCIP_EXPR *expr) |
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) |
static SCIP_RETCODE | collectLeafs (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata) |
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) |
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) |
static SCIP_RETCODE | estimateGradientInner (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *success) |
static SCIP_RETCODE | estimateGradient (SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *success) |
static SCIP_RETCODE | estimateConvexSecant (SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *success) |
static | SCIP_DECL_NLHDLRFREEHDLRDATA (nlhdlrfreeHdlrDataConvexConcave) |
static | SCIP_DECL_NLHDLRFREEEXPRDATA (nlhdlrfreeExprDataConvexConcave) |
static | SCIP_DECL_NLHDLREXIT (nlhdlrExitConvex) |
static | SCIP_DECL_NLHDLRDETECT (nlhdlrDetectConvex) |
static | SCIP_DECL_NLHDLREVALAUX (nlhdlrEvalAuxConvexConcave) |
static | SCIP_DECL_NLHDLRINITSEPA (nlhdlrInitSepaConvex) |
static | SCIP_DECL_NLHDLRESTIMATE (nlhdlrEstimateConvex) |
static | SCIP_DECL_NLHDLRSOLLINEARIZE (nlhdlrSollinearizeConvex) |
static | SCIP_DECL_NLHDLRCOPYHDLR (nlhdlrCopyhdlrConvex) |
SCIP_RETCODE | SCIPincludeNlhdlrConvex (SCIP *scip) |
static | SCIP_DECL_NLHDLREXIT (nlhdlrExitConcave) |
static | SCIP_DECL_NLHDLRDETECT (nlhdlrDetectConcave) |
static | SCIP_DECL_NLHDLRINITSEPA (nlhdlrInitSepaConcave) |
static | SCIP_DECL_NLHDLRESTIMATE (nlhdlrEstimateConcave) |
static | SCIP_DECL_NLHDLRCOPYHDLR (nlhdlrCopyhdlrConcave) |
SCIP_RETCODE | SCIPincludeNlhdlrConcave (SCIP *scip) |
SCIP_RETCODE | SCIPhasExprCurvature (SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV curv, SCIP_Bool *success, SCIP_HASHMAP *assumevarfixed) |
Variables | |
static const int | NCURVCHECKS = sizeof(CURVCHECKS) / sizeof(void*) |
#define CONVEX_NLHDLR_NAME "convex" |
Definition at line 44 of file nlhdlr_convex.c.
Referenced by SCIP_DECL_NLHDLRCOPYHDLR(), and SCIPincludeNlhdlrConvex().
#define CONVEX_NLHDLR_DESC "handler that identifies and estimates convex expressions" |
Definition at line 45 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConvex().
#define CONVEX_NLHDLR_DETECTPRIORITY 50 |
Definition at line 46 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConvex().
#define CONVEX_NLHDLR_ENFOPRIORITY 50 |
Definition at line 47 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConvex().
#define CONCAVE_NLHDLR_NAME "concave" |
Definition at line 49 of file nlhdlr_convex.c.
Referenced by SCIP_DECL_NLHDLRCOPYHDLR(), and SCIPincludeNlhdlrConcave().
#define CONCAVE_NLHDLR_DESC "handler that identifies and estimates concave expressions" |
Definition at line 50 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConcave().
#define CONCAVE_NLHDLR_DETECTPRIORITY 40 |
Definition at line 51 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConcave().
#define CONCAVE_NLHDLR_ENFOPRIORITY 40 |
Definition at line 52 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConcave().
#define DEFAULT_DETECTSUM FALSE |
Definition at line 54 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().
#define DEFAULT_EXTENDEDFORM TRUE |
Definition at line 55 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConvex().
#define DEFAULT_CVXQUADRATIC_CONVEX TRUE |
Definition at line 56 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConvex().
#define DEFAULT_CVXQUADRATIC_CONCAVE FALSE |
Definition at line 57 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConcave().
#define DEFAULT_CVXSIGNOMIAL TRUE |
Definition at line 58 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().
#define DEFAULT_CVXPRODCOMP TRUE |
Definition at line 59 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().
#define DEFAULT_HANDLETRIVIAL FALSE |
Definition at line 60 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().
#define DEFAULT_MAXPERTURB 0.01 |
Definition at line 61 of file nlhdlr_convex.c.
Referenced by SCIPincludeNlhdlrConvex().
#define INITLPMAXVARVAL 1000.0 |
maximal absolute value of variable for still generating a linearization cut at that point in initlp
Definition at line 63 of file nlhdlr_convex.c.
Referenced by SCIP_DECL_NLHDLRINITSEPA().
#define RANDNUMINITSEED 220802 |
initial seed for random number generator for point perturbation
Definition at line 64 of file nlhdlr_convex.c.
Referenced by estimateGradient().
#define DECL_CURVCHECK | ( | x | ) |
Definition at line 121 of file nlhdlr_convex.c.
|
static |
create nlhdlr-expression
does not create children, i.e., assumes that this will be a leaf
scip | SCIP data structure |
nlexpr2origexpr | mapping from copied to original expression |
nlhdlrexpr | buffer to store created expr |
origexpr | original expression to be copied |
curv | curvature to achieve |
Definition at line 141 of file nlhdlr_convex.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcaptureExpr(), SCIPduplicateExprShallow(), SCIPexprGetNChildren(), SCIPexprSetCurvature(), SCIPhashmapExists(), and SCIPhashmapInsert().
Referenced by constructExpr(), and nlhdlrExprGrowChildren().
|
static |
expand nlhdlr-expression by adding children according to original expression
scip | SCIP data structure |
nlexpr2origexpr | mapping from copied to original expression |
nlhdlrexpr | expression for which to create children |
childrencurv | curvature required for children, or NULL if to set to UNKNOWN |
Definition at line 183 of file nlhdlr_convex.c.
References assert(), i, nlhdlrExprCreate(), NULL, SCIP_CALL, SCIP_EXPRCURV_UNKNOWN, SCIP_OKAY, SCIPappendExprChild(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPhashmapGetImage(), and SCIPreleaseExpr().
Referenced by constructExpr(), DECL_CURVCHECK(), DECL_CURVCHECK(), DECL_CURVCHECK(), and DECL_CURVCHECK().
|
static |
evaluate expression at solution w.r.t. auxiliary variables
Definition at line 221 of file nlhdlr_convex.c.
References assert(), VERTEXPOLYFUN_EVALDATA::evalsol, i, VERTEXPOLYFUN_EVALDATA::nlhdlrexprdata, NULL, VERTEXPOLYFUN_EVALDATA::scip, SCIP_CALL_ABORT, SCIPdebugMsg, SCIPevalExpr(), SCIPexprGetEvalValue(), SCIPgetVarExprVar(), SCIPsetSolVal(), and SCIPvarGetName().
|
static |
initialize expression stack
scip | SCIP data structure |
exprstack | stack to initialize |
initsize | initial size |
Definition at line 250 of file nlhdlr_convex.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, EXPRSTACK::stack, EXPRSTACK::stackpos, and EXPRSTACK::stacksize.
Referenced by constructExpr().
free expression stack
scip | SCIP data structure |
exprstack | free expression stack |
Definition at line 269 of file nlhdlr_convex.c.
References assert(), NULL, SCIPfreeBufferArray, and EXPRSTACK::stack.
Referenced by constructExpr().
|
static |
add expressions to expression stack
scip | SCIP data structure |
exprstack | expression stack |
nexprs | number of expressions to push |
exprs | expressions to push |
Definition at line 282 of file nlhdlr_convex.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPreallocBufferArray, EXPRSTACK::stack, EXPRSTACK::stackpos, and EXPRSTACK::stacksize.
Referenced by constructExpr(), DECL_CURVCHECK(), DECL_CURVCHECK(), DECL_CURVCHECK(), and DECL_CURVCHECK().
gives expression from top of expression stack and removes it from stack
exprstack | expression stack |
Definition at line 311 of file nlhdlr_convex.c.
References assert(), NULL, EXPRSTACK::stack, and EXPRSTACK::stackpos.
Referenced by constructExpr().
indicate whether expression stack is empty
exprstack | expression stack |
Definition at line 323 of file nlhdlr_convex.c.
References assert(), NULL, SCIP_Bool, and EXPRSTACK::stackpos.
Referenced by constructExpr().
|
static |
looks whether given expression is (proper) quadratic and has a given curvature
If having a given curvature, currently require all arguments of quadratic to be linear. Hence, not using this for a simple square term, as curvCheckExprhdlr may provide a better condition on argument curvature then. Also we wouldn't do anything useful for a single bilinear term. Thus, run on sum's only.
Definition at line 340 of file nlhdlr_convex.c.
References assert(), exprstackPush(), FALSE, i, nlhdlrExprGrowChildren(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIPblkmem(), SCIPcheckExprQuadratic(), SCIPcomputeExprQuadraticCurvature(), SCIPexprcurvMultiply(), SCIPexprGetChildren(), SCIPexprGetCurvature(), SCIPexprGetNChildren(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPexprSetCurvature(), SCIPgetCoefsExprSum(), SCIPgetExponentExprPow(), SCIPhashmapGetImage(), SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetInsert(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprSum(), and TRUE.
|
static |
looks whether top of given expression looks like a signomial that can have a given curvature
e.g., sqrt(x)*sqrt(y) is convex if x,y >= 0 and x and y are convex
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); but works for cvxnonsep_nsig
Definition at line 485 of file nlhdlr_convex.c.
References assert(), exprstackPush(), FALSE, i, nlhdlrExprGrowChildren(), NULL, SCIP_CALL, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPevalExprActivity(), SCIPexprcurvMonomialInv(), SCIPexprcurvMultiply(), SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetCurvature(), SCIPexprGetNChildren(), SCIPexprSetCurvature(), SCIPfreeBufferArray, SCIPgetCoefExprProduct(), SCIPgetExponentExprPow(), SCIPhashmapGetImage(), SCIPinfoMessage(), SCIPisExprPower(), SCIPisExprProduct(), SCIPprintExpr(), and TRUE.
|
static |
looks for \(f(c h(x)+d) h(x) \cdot \text{constant}\) and tries to conclude conditions on curvature
Assume \(h\) is univariate:
\begin{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'' \\ =& f''(c h + d) c^2 h'^2 h + f'(c h + d) c h'' h + 2 f'(c h + d) c h'^2 + f(c h + d) h''.\end{align}
Remove always positive factors leaves\[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''.\]
For convexity we want all these terms to be nonnegative. For concavity we want all of them to be nonpositive. Note, that in each term either both \(f'(c h + d)\) and \(c\) occur, or none of them.This should hold also for multivariate and linear \(h\), as things are invariant under linear transformations. Similar to signomial, I'll assume that this will also hold for other multivariate \(h\) (someone has a formal proof?).
Definition at line 609 of file nlhdlr_convex.c.
References assert(), c, exprstackPush(), FALSE, h, SCIP_Interval::inf, nlhdlrExprGrowChildren(), NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_MONOTONE_DEC, SCIP_MONOTONE_INC, SCIP_MONOTONE_UNKNOWN, SCIP_OKAY, SCIP_Real, SCIPappendExprChild(), SCIPcompareExpr(), SCIPevalExprActivity(), SCIPexprcurvMultiply(), SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetCurvature(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), SCIPexprSetCurvature(), SCIPgetCoefExprProduct(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPhashmapGetImage(), SCIPinfoMessage(), SCIPisExprAbs(), SCIPisExprProduct(), SCIPisExprSum(), SCIPisZero(), SCIPprintExpr(), and SCIP_Interval::sup.
|
static |
use expression handlers curvature callback to check whether given curvature can be achieved
Definition at line 826 of file nlhdlr_convex.c.
References assert(), exprstackPush(), i, nlhdlrExprGrowChildren(), NULL, SCIP_CALL, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIPallocBufferArray, SCIPexprcurvGetName(), SCIPexprGetChildren(), SCIPexprGetCurvature(), SCIPexprGetNChildren(), SCIPexprSetCurvature(), SCIPfreeBufferArray, SCIPhashmapGetImage(), SCIPinfoMessage(), SCIPisExprSum(), and SCIPprintExpr().
|
static |
curvature check and expression-growing methods
some day this could be plugins added by users at runtime, but for now we have a fixed list here
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
Within constructExpr(), we can have an expression of any type which is a copy of an original expression, but without children. At the end of constructExpr() (after the loop with the stack), these expressions will remain as leafs and will eventually be turned into variables in collectLeafs(). Thus, we treat every child that has no children as if it were a variable. Theoretically, there is still the possibility that it could be a constant (value-expression), but simplify should have removed these.
scip | SCIP data structure |
expr | expression to check |
Definition at line 919 of file nlhdlr_convex.c.
References assert(), c, FALSE, NULL, SCIP_Bool, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPisExprSum(), and TRUE.
Referenced by constructExpr().
|
static |
constructs a subexpression (as nlhdlr-expression) of maximal size that has a given curvature
If the curvature cannot be achieved for an expression in the original expression graph, then this expression becomes a leaf in the nlhdlr-expression.
Sets *rootnlexpr to NULL if failed.
scip | SCIP data structure |
nlhdlrdata | nonlinear handler data |
rootnlexpr | buffer to store created expression |
nlexpr2origexpr | mapping from our expression copy to original expression |
nleafs | number of leafs in constructed expression |
rootexpr | expression |
curv | curvature to achieve |
assumevarfixed | hashmap containing variables that should be assumed to be fixed, or NULL |
assumecurvature | whether to assume that desired curvature is given (skips curvature checks) |
curvsuccess | pointer to store whether the curvature could be achieved w.r.t. the original variables (might be NULL) |
Definition at line 952 of file nlhdlr_convex.c.
References assert(), exprIsMultivarLinear(), exprstackFree(), exprstackInit(), exprstackIsEmpty(), exprstackPop(), exprstackPush(), FALSE, i, NCURVCHECKS, nlhdlrExprCreate(), nlhdlrExprGrowChildren(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_UNKNOWN, SCIP_EXPRITER_DFS, SCIP_EXPRITER_VISITINGCHILD, SCIP_OKAY, SCIPcreateExpriter(), SCIPexprGetChildren(), SCIPexprGetCurvature(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrHasBwdiff(), SCIPexpriterGetChildExprDFS(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPexpriterSkipDFS(), SCIPfreeExpriter(), SCIPhashmapGetImage(), SCIPinfoMessage(), SCIPisExprSum(), SCIPisExprValue(), SCIPisExprVar(), SCIPprintExpr(), SCIPreleaseExpr(), SCIPremoveExprChildren(), EXPRSTACK::stackpos, and TRUE.
Referenced by SCIP_DECL_NLHDLRDETECT(), SCIP_DECL_NLHDLRDETECT(), and SCIPhasExprCurvature().
|
static |
collects (non-value) leaf expressions and ensure that they correspond to a variable (original or auxiliary)
For children where we could not achieve the desired curvature, get the auxvar and replace the child by a var-expression that points to this auxvar. Collect all leaf expressions (if not a value-expression) and index them.
scip | SCIP data structure |
nlhdlrexprdata | nlhdlr expression data |
Definition at line 1151 of file nlhdlr_convex.c.
References assert(), FALSE, i, NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_VISITINGCHILD, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcomputeExprIntegrality(), SCIPcreateExpriter(), SCIPcreateExprVar(), SCIPdebugMsg, SCIPexprGetNChildren(), SCIPexpriterGetChildExprDFS(), SCIPexpriterGetChildIdxDFS(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfreeExpriter(), SCIPgetExprAuxVarNonlinear(), SCIPgetVarExprVar(), SCIPhashmapCreate(), SCIPhashmapEntryGetImageInt(), SCIPhashmapEntryGetOrigin(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetEntry(), SCIPhashmapGetImage(), SCIPhashmapGetNEntries(), SCIPhashmapInsertInt(), SCIPhashmapSetImage(), SCIPisExprVar(), SCIPreleaseExpr(), SCIPreplaceExprChild(), SCIPvarGetName(), and var.
Referenced by SCIP_DECL_NLHDLRINITSEPA(), and SCIP_DECL_NLHDLRINITSEPA().
|
static |
creates nonlinear handler expression data structure and registers expr usage
scip | SCIP data structure |
nlhdlrdata | nlhdlr data |
nlhdlrexprdata | pointer to store nlhdlr expression data |
expr | original expression |
nlexpr | our copy of expression |
nlexpr2origexpr | mapping of expression copy to original |
nleafs | number of leafs as counted by constructExpr |
participating | the enfo methods in which we plan to participate |
Definition at line 1278 of file nlhdlr_convex.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_VISITINGCHILD, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_OKAY, SCIPallocClearBlockMemory, SCIPcreateExpriter(), SCIPexprcurvGetName(), SCIPexprGetChildren(), SCIPexprGetCurvature(), SCIPexprGetNChildren(), SCIPexpriterGetChildExprDFS(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPexprSetCurvature(), SCIPfreeExpriter(), SCIPhashmapGetImage(), SCIPinfoMessage(), SCIPprintExpr(), SCIPregisterExprUsageNonlinear(), and TRUE.
Referenced by SCIP_DECL_NLHDLRDETECT(), and SCIP_DECL_NLHDLRDETECT().
|
static |
adds an estimator for a vertex-polyhedral (e.g., concave) function to a given rowprep
Calls SCIPcomputeFacetVertexPolyhedralNonlinear() for given function and box set to local bounds of auxiliary variables.
scip | SCIP data structure |
conshdlr | nonlinear constraint handler |
nlhdlr | nonlinear handler |
nlhdlrexprdata | nonlinear handler expression data |
sol | solution to use, unless usemidpoint is TRUE |
usemidpoint | whether to use the midpoint of the domain instead of sol |
overestimate | whether over- or underestimating |
targetvalue | a target value to achieve; if not reachable, then can give up early |
rowprep | rowprep where to store estimator |
success | buffer to store whether successful |
Definition at line 1371 of file nlhdlr_convex.c.
References assert(), VERTEXPOLYFUN_EVALDATA::evalsol, FALSE, i, VERTEXPOLYFUN_EVALDATA::nlhdlrexprdata, NULL, VERTEXPOLYFUN_EVALDATA::scip, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPallocBufferArray, SCIPcomputeFacetVertexPolyhedralNonlinear(), SCIPcreateSol(), SCIPdebugMsg, SCIPensureRowprepSize(), SCIPexprGetCurvature(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPinfoMessage(), SCIPisInfinity(), SCIPisRelEQ(), SCIPnlhdlrGetData(), SCIPprintExpr(), SCIPprintRowprep(), SCIProwprepAddConstant(), SCIProwprepGetCoefs(), SCIProwprepSetLocal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), sol, TRUE, and var.
Referenced by SCIP_DECL_NLHDLRESTIMATE(), and SCIP_DECL_NLHDLRINITSEPA().
|
static |
adds an estimator computed via a gradient to a given rowprep
scip | SCIP data structure |
nlhdlrexprdata | nonlinear handler expression data |
sol | solution to use |
rowprep | rowprep where to store estimator |
success | buffer to store whether successful |
Definition at line 1504 of file nlhdlr_convex.c.
References assert(), FALSE, i, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPdebugMsg, SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexprGetDiffTag(), SCIPexprGetEvalValue(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPquadprecSumQD, SCIProwprepAddConstant(), SCIProwprepSetLocal(), SCIPvarGetName(), sol, TRUE, and var.
Referenced by estimateGradient().
|
static |
adds an estimator computed via a gradient to a given rowprep, possibly perturbing solution
scip | SCIP data structure |
nlhdlr | nonlinear handler |
nlhdlrexprdata | nonlinear handler expression data |
sol | solution to use |
rowprep | rowprep where to store estimator |
success | buffer to store whether successful |
Definition at line 1576 of file nlhdlr_convex.c.
References assert(), estimateGradientInner(), FALSE, i, MAX, MIN, NULL, RANDNUMINITSEED, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPcreateSol(), SCIPdebugMsg, SCIPepsilon(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPinfoMessage(), SCIPisZero(), SCIPnlhdlrGetData(), SCIPprintExpr(), SCIPrandomGetReal(), SCIPsetSolVal(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), sol, TRUE, and var.
Referenced by SCIP_DECL_NLHDLRESTIMATE(), SCIP_DECL_NLHDLRINITSEPA(), and SCIP_DECL_NLHDLRSOLLINEARIZE().
|
static |
adds an estimator generated by putting a secant through the coordinates given by the two closest integer points
scip | SCIP data structure |
nlhdlr | nonlinear handler |
nlhdlrexprdata | nonlinear handler expression data |
sol | solution to use, unless usemidpoint is TRUE |
rowprep | rowprep where to store estimator |
success | buffer to store whether successful |
Definition at line 1675 of file nlhdlr_convex.c.
References assert(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPceil(), SCIPcreateSol(), SCIPdebugMsg, SCIPepsilon(), SCIPevalExpr(), SCIPexprGetEvalValue(), SCIPfloor(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPinfoMessage(), SCIPisEQ(), SCIPisInfinity(), SCIPisIntegral(), SCIPisZero(), SCIPnlhdlrGetData(), SCIPprintExpr(), SCIPround(), SCIProwprepAddConstant(), SCIProwprepSetLocal(), SCIPsetSolVal(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), sol, TRUE, var, and x.
Referenced by SCIP_DECL_NLHDLRESTIMATE(), and SCIP_DECL_NLHDLRSOLLINEARIZE().
|
static |
free handler data of convex or concave nlhdlr
Definition at line 1796 of file nlhdlr_convex.c.
References assert(), NULL, SCIP_OKAY, and SCIPfreeBlockMemory.
|
static |
callback to free expression specific data
Definition at line 1811 of file nlhdlr_convex.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPhashmapFree(), and SCIPreleaseExpr().
|
static |
deinitialization of problem-specific data
Definition at line 1828 of file nlhdlr_convex.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeRandom(), SCIPfreeSol(), and SCIPnlhdlrGetData().
|
static |
checks whether expression (or -expression) is convex, possibly after introducing auxiliary variables
Definition at line 1848 of file nlhdlr_convex.c.
References assert(), constructExpr(), createNlhdlrExprData(), NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIPassumeConvexNonlinear(), SCIPblkmem(), SCIPdebugMsg, SCIPexprGetNChildren(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapRemoveAll(), and SCIPnlhdlrGetData().
|
static |
auxiliary evaluation callback
Definition at line 1934 of file nlhdlr_convex.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPevalExpr(), SCIPexprGetEvalValue(), and sol.
|
static |
init sepa callback that initializes LP
Definition at line 1948 of file nlhdlr_convex.c.
References assert(), collectLeafs(), estimateGradient(), FALSE, i, INITLPMAXVARVAL, MAX, MIN, NULL, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPaddRow(), SCIPaddRowprepTerm(), SCIPcleanupRowprep2(), SCIPcreateRowprep(), SCIPcreateSol(), SCIPdebugMsg, SCIPexprGetCurvature(), SCIPfreeRowprep(), SCIPfreeSol(), SCIPgetExprAuxVarNonlinear(), SCIPgetHugeValue(), SCIPgetRowprepRowCons(), SCIPgetVarExprVar(), SCIPhashmapGetImage(), SCIPinfoMessage(), SCIPisInfinity(), SCIPprintRow(), SCIPreleaseRow(), SCIProwprepGetName(), SCIPsetSolVal(), SCIPsnprintf(), SCIPvarGetBestBoundType(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), sol, TRUE, and var.
|
static |
estimator callback
Definition at line 2068 of file nlhdlr_convex.c.
References assert(), estimateConvexSecant(), estimateGradient(), FALSE, NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_INVALID, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPcreateRowprep(), SCIPexprGetCurvature(), SCIPexprGetEvalValue(), SCIPexprIsIntegral(), SCIPfreeRowprep(), SCIPgetNLPs(), SCIPhashmapGetImage(), SCIProwprepGetName(), SCIPsetPtrarrayVal(), SCIPsnprintf(), SCIPsolGetIndex(), sol, and TRUE.
|
static |
solution notification callback
Definition at line 2134 of file nlhdlr_convex.c.
References assert(), estimateConvexSecant(), estimateGradient(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPaddPoolCut(), SCIPaddRowprepTerm(), SCIPcleanupRowprep2(), SCIPcreateRowprep(), SCIPevalExpr(), SCIPexprGetCurvature(), SCIPexprIsIntegral(), SCIPfreeRowprep(), SCIPgetExprAuxVarNonlinear(), SCIPgetHugeValue(), SCIPgetRowprepRowCons(), SCIPhashmapGetImage(), SCIPreleaseRow(), SCIProwprepGetName(), SCIProwprepIsLocal(), SCIPsnprintf(), SCIPsolGetIndex(), sol, and TRUE.
|
static |
include nlhdlr in another scip instance
Definition at line 2199 of file nlhdlr_convex.c.
References assert(), CONVEX_NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrConvex(), and SCIPnlhdlrGetName().
|
static |
deinitialization of problem-specific data
Definition at line 2273 of file nlhdlr_convex.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), and SCIPnlhdlrGetData().
|
static |
checks whether expression (or -expression) is concave, possibly after introducing auxiliary variables
Definition at line 2291 of file nlhdlr_convex.c.
References assert(), constructExpr(), createNlhdlrExprData(), FALSE, NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_MAXVERTEXPOLYDIM, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIPblkmem(), SCIPdebugMsg, SCIPexprGetNChildren(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapRemoveAll(), SCIPnlhdlrGetData(), and SCIPreleaseExpr().
|
static |
init sepa callback that initializes LP
Definition at line 2391 of file nlhdlr_convex.c.
References assert(), collectLeafs(), estimateVertexPolyhedral(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPaddRow(), SCIPaddRowprepTerm(), SCIPcleanupRowprep2(), SCIPcreateRowprep(), SCIPdebugMsg, SCIPexprGetCurvature(), SCIPfreeRowprep(), SCIPgetExprAuxVarNonlinear(), SCIPgetHugeValue(), SCIPgetRowprepRowCons(), SCIPhashmapGetImage(), SCIPinfinity(), SCIPinfoMessage(), SCIPprintRow(), SCIPreleaseRow(), SCIProwprepGetName(), SCIPsnprintf(), and TRUE.
|
static |
estimator callback
Definition at line 2462 of file nlhdlr_convex.c.
References assert(), c, estimateVertexPolyhedral(), FALSE, MAX, NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_INVALID, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPaddExprsViolScoreNonlinear(), SCIPallocBufferArray, SCIPcreateRowprep(), SCIPexprGetCurvature(), SCIPfreeBufferArray, SCIPfreeRowprep(), SCIPgetExprAuxVarNonlinear(), SCIPgetNLPs(), SCIPgetSolVal(), SCIPhashmapGetImage(), SCIPinfinity(), SCIProwprepGetName(), SCIPsetPtrarrayVal(), SCIPsnprintf(), SCIPsolGetIndex(), sol, and TRUE.
|
static |
includes nonlinear handler in another scip instance
Definition at line 2562 of file nlhdlr_convex.c.
References assert(), CONCAVE_NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrConcave(), and SCIPnlhdlrGetName().
|
static |
number of curvcheck methods
Definition at line 908 of file nlhdlr_convex.c.
Referenced by constructExpr().