Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

nonlinear handlers for convex and concave expressions

Author
Benjamin Mueller
Stefan Vigerske

TODO convex: perturb reference point if separation fails due to too large numbers

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/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 INITLPMAXVARVAL   1000.0
 
#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_EXPRexprstackPop (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 estimateGradient (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_Real auxvalue, 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_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*)
 

Macro Definition Documentation

◆ CONVEX_NLHDLR_NAME

#define CONVEX_NLHDLR_NAME   "convex"

Definition at line 36 of file nlhdlr_convex.c.

Referenced by SCIP_DECL_NLHDLRCOPYHDLR(), and SCIPincludeNlhdlrConvex().

◆ CONVEX_NLHDLR_DESC

#define CONVEX_NLHDLR_DESC   "handler that identifies and estimates convex expressions"

Definition at line 37 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

◆ CONVEX_NLHDLR_DETECTPRIORITY

#define CONVEX_NLHDLR_DETECTPRIORITY   50

Definition at line 38 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

◆ CONVEX_NLHDLR_ENFOPRIORITY

#define CONVEX_NLHDLR_ENFOPRIORITY   50

Definition at line 39 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

◆ CONCAVE_NLHDLR_NAME

#define CONCAVE_NLHDLR_NAME   "concave"

Definition at line 41 of file nlhdlr_convex.c.

Referenced by SCIP_DECL_NLHDLRCOPYHDLR(), and SCIPincludeNlhdlrConcave().

◆ CONCAVE_NLHDLR_DESC

#define CONCAVE_NLHDLR_DESC   "handler that identifies and estimates concave expressions"

Definition at line 42 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

◆ CONCAVE_NLHDLR_DETECTPRIORITY

#define CONCAVE_NLHDLR_DETECTPRIORITY   40

Definition at line 43 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

◆ CONCAVE_NLHDLR_ENFOPRIORITY

#define CONCAVE_NLHDLR_ENFOPRIORITY   40

Definition at line 44 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

◆ DEFAULT_DETECTSUM

#define DEFAULT_DETECTSUM   FALSE

Definition at line 46 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

◆ DEFAULT_EXTENDEDFORM

#define DEFAULT_EXTENDEDFORM   TRUE

Definition at line 47 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

◆ DEFAULT_CVXQUADRATIC_CONVEX

#define DEFAULT_CVXQUADRATIC_CONVEX   TRUE

Definition at line 48 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

◆ DEFAULT_CVXQUADRATIC_CONCAVE

#define DEFAULT_CVXQUADRATIC_CONCAVE   FALSE

Definition at line 49 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

◆ DEFAULT_CVXSIGNOMIAL

#define DEFAULT_CVXSIGNOMIAL   TRUE

Definition at line 50 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

◆ DEFAULT_CVXPRODCOMP

#define DEFAULT_CVXPRODCOMP   TRUE

Definition at line 51 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

◆ DEFAULT_HANDLETRIVIAL

#define DEFAULT_HANDLETRIVIAL   FALSE

Definition at line 52 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

◆ INITLPMAXVARVAL

#define INITLPMAXVARVAL   1000.0

maximal absolute value of variable for still generating a linearization cut at that point in initlp

Definition at line 54 of file nlhdlr_convex.c.

Referenced by SCIP_DECL_NLHDLRINITSEPA().

◆ DECL_CURVCHECK

#define DECL_CURVCHECK (   x)
Value:
SCIP* scip, /**< SCIP data structure */ \
SCIP_EXPR* nlexpr, /**< nlhdlr-expr to check */ \
SCIP_Bool isrootexpr, /**< whether nlexpr is the root from where detection has been started */ \
EXPRSTACK* stack, /**< stack where to add generated leafs */ \
SCIP_HASHMAP* nlexpr2origexpr, /**< mapping from our expression copy to original expression */ \
SCIP_NLHDLRDATA* nlhdlrdata, /**< data of nlhdlr */ \
SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */ \
SCIP_Bool* success /**< whether we found something */ \
)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_VAR ** x
Definition: circlepacking.c:54
#define SCIP_Bool
Definition: def.h:84
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
Definition: type_nlhdlr.h:403

Definition at line 109 of file nlhdlr_convex.c.

Referenced by DECL_CURVCHECK().

Function Documentation

◆ nlhdlrExprCreate()

static SCIP_RETCODE nlhdlrExprCreate ( SCIP scip,
SCIP_HASHMAP nlexpr2origexpr,
SCIP_EXPR **  nlhdlrexpr,
SCIP_EXPR origexpr,
SCIP_EXPRCURV  curv 
)
static

create nlhdlr-expression

does not create children, i.e., assumes that this will be a leaf

Parameters
scipSCIP data structure
nlexpr2origexprmapping from copied to original expression
nlhdlrexprbuffer to store created expr
origexproriginal expression to be copied
curvcurvature to achieve

Definition at line 129 of file nlhdlr_convex.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcaptureExpr(), SCIPduplicateExprShallow(), SCIPexprGetNChildren(), SCIPexprSetCurvature(), SCIPhashmapExists(), and SCIPhashmapInsert().

Referenced by constructExpr(), and nlhdlrExprGrowChildren().

◆ nlhdlrExprGrowChildren()

static SCIP_RETCODE nlhdlrExprGrowChildren ( SCIP scip,
SCIP_HASHMAP nlexpr2origexpr,
SCIP_EXPR nlhdlrexpr,
SCIP_EXPRCURV childrencurv 
)
static

expand nlhdlr-expression by adding children according to original expression

Parameters
scipSCIP data structure
nlexpr2origexprmapping from copied to original expression
nlhdlrexprexpression for which to create children
childrencurvcurvature required for children, or NULL if to set to UNKNOWN

Definition at line 171 of file nlhdlr_convex.c.

References nlhdlrExprCreate(), NULL, SCIP_CALL, SCIP_EXPRCURV_UNKNOWN, SCIP_OKAY, SCIPappendExprChild(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPhashmapGetImage(), and SCIPreleaseExpr().

Referenced by constructExpr(), and DECL_CURVCHECK().

◆ SCIP_DECL_VERTEXPOLYFUN()

static SCIP_DECL_VERTEXPOLYFUN ( nlhdlrExprEvalConcave  )
static

◆ exprstackInit()

static SCIP_RETCODE exprstackInit ( SCIP scip,
EXPRSTACK exprstack,
int  initsize 
)
static

initialize expression stack

Parameters
scipSCIP data structure
exprstackstack to initialize
initsizeinitial size

Definition at line 238 of file nlhdlr_convex.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, EXPRSTACK::stack, EXPRSTACK::stackpos, and EXPRSTACK::stacksize.

Referenced by constructExpr().

◆ exprstackFree()

static void exprstackFree ( SCIP scip,
EXPRSTACK exprstack 
)
static

free expression stack

Parameters
scipSCIP data structure
exprstackfree expression stack

Definition at line 257 of file nlhdlr_convex.c.

References NULL, SCIPfreeBufferArray, and EXPRSTACK::stack.

Referenced by constructExpr().

◆ exprstackPush()

static SCIP_RETCODE exprstackPush ( SCIP scip,
EXPRSTACK exprstack,
int  nexprs,
SCIP_EXPR **  exprs 
)
static

add expressions to expression stack

Parameters
scipSCIP data structure
exprstackexpression stack
nexprsnumber of expressions to push
exprsexpressions to push

Definition at line 270 of file nlhdlr_convex.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPreallocBufferArray, EXPRSTACK::stack, EXPRSTACK::stackpos, and EXPRSTACK::stacksize.

Referenced by constructExpr(), and DECL_CURVCHECK().

◆ exprstackPop()

static SCIP_EXPR* exprstackPop ( EXPRSTACK exprstack)
static

gives expression from top of expression stack and removes it from stack

Parameters
exprstackexpression stack

Definition at line 299 of file nlhdlr_convex.c.

References NULL, EXPRSTACK::stack, and EXPRSTACK::stackpos.

Referenced by constructExpr().

◆ exprstackIsEmpty()

static SCIP_Bool exprstackIsEmpty ( EXPRSTACK exprstack)
static

indicate whether expression stack is empty

Parameters
exprstackexpression stack

Definition at line 311 of file nlhdlr_convex.c.

References NULL, and EXPRSTACK::stackpos.

Referenced by constructExpr().

◆ DECL_CURVCHECK() [1/5]

static DECL_CURVCHECK ( curvCheckQuadratic  )
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 328 of file nlhdlr_convex.c.

References exprstackPush(), FALSE, nlhdlrExprGrowChildren(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIPblkmem(), SCIPcheckExprQuadratic(), SCIPcomputeExprQuadraticCurvature(), SCIPexprGetChildren(), SCIPexprGetCurvature(), SCIPexprGetNChildren(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPexprSetCurvature(), SCIPgetExponentExprPow(), SCIPhashmapGetImage(), SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetInsert(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprSum(), and TRUE.

◆ DECL_CURVCHECK() [2/5]

static DECL_CURVCHECK ( curvCheckSignomial  )
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 466 of file nlhdlr_convex.c.

References exprstackPush(), FALSE, 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.

◆ DECL_CURVCHECK() [3/5]

static DECL_CURVCHECK ( curvCheckProductComposite  )
static

looks for \(f(c h(x)+d) h(x) \cdot \text{constant}\) and tries to conclude conditions on curvature

Assume \(h\) is univariate:

  • First derivative is \(f'(c h + d) c h' h + f(c h + d) h'\).
  • Second derivative is

    \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.
  • Thus, \(f(c h(x) + d)h(x)\) is convex if \(cf\) is monotonically increasing \((c f' \geq 0)\) and either
    • \(f\) is convex \((f'' \geq 0)\) and \(h\) is nonnegative \((h \geq 0)\) and \(h\) is convex \((h'' \geq 0)\) and [ \(f\) is nonnegative \((f \geq 0)\) or \(h\) is linear \((h''=0)\)], or
    • \(f\) is concave \((f'' \leq 0)\) and \(h\) is nonpositive \((h \leq 0)\) and \(h\) is concave \((h'' \leq 0)\) and [ \(f\) is nonpositive \((f \leq 0)\) or \(h\) is linear \((h''=0)\)].
  • Further, \(f(c h(x) + d)h(x)\) is concave if \(cf\) is monotonically decreasing \((c f' \leq 0)\) and either
    • f is convex \((f'' \geq 0)\) and \(h\) is nonpositive \((h \leq 0)\) and \(h\) is concave \((h'' \leq 0)\) and [ \(f\) is nonnegative \((f \geq 0)\) or \(h\) is linear \((h''=0)\)], or
    • f is concave \((f'' \leq 0)\) and \(h\) is nonnegative \((h >= 0)\) and \(h\) is convex \((h'' \geq 0)\) and [ \(f\) is nonpositive \((f \leq 0)\) or \(h\) is linear \((h''=0)\)].

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 590 of file nlhdlr_convex.c.

References 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(), SCIPisExprProduct(), SCIPisExprSum(), SCIPprintExpr(), and SCIP_Interval::sup.

◆ DECL_CURVCHECK() [4/5]

static DECL_CURVCHECK ( curvCheckExprhdlr  )
static

◆ DECL_CURVCHECK() [5/5]

static DECL_CURVCHECK ( *[]  CURVCHECKS)
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

Note
curvCheckExprhdlr should be last

◆ exprIsMultivarLinear()

static SCIP_Bool exprIsMultivarLinear ( SCIP scip,
SCIP_EXPR expr 
)
static

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.

Parameters
scipSCIP data structure
exprexpression to check

Definition at line 889 of file nlhdlr_convex.c.

References FALSE, NULL, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPisExprSum(), and TRUE.

Referenced by constructExpr().

◆ constructExpr()

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

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.

Parameters
scipSCIP data structure
nlhdlrdatanonlinear handler data
rootnlexprbuffer to store created expression
nlexpr2origexprmapping from our expression copy to original expression
nleafsnumber of leafs in constructed expression
rootexprexpression
curvcurvature to achieve
assumevarfixedhashmap containing variables that should be assumed to be fixed, or NULL
assumecurvaturewhether to assume that desired curvature is given (skips curvature checks)
curvsuccesspointer to store whether the curvature could be achieved w.r.t. the original variables (might be NULL)

Definition at line 922 of file nlhdlr_convex.c.

References exprIsMultivarLinear(), exprstackFree(), exprstackInit(), exprstackIsEmpty(), exprstackPop(), exprstackPush(), FALSE, 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(), and SCIPhasExprCurvature().

◆ collectLeafs()

static SCIP_RETCODE collectLeafs ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata 
)
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.

Parameters
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data

Definition at line 1121 of file nlhdlr_convex.c.

References FALSE, 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(), and SCIPvarGetName().

Referenced by SCIP_DECL_NLHDLRINITSEPA().

◆ createNlhdlrExprData()

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

creates nonlinear handler expression data structure and registers expr usage

Parameters
scipSCIP data structure
nlhdlrdatanlhdlr data
nlhdlrexprdatapointer to store nlhdlr expression data
exproriginal expression
nlexprour copy of expression
nlexpr2origexprmapping of expression copy to original
nleafsnumber of leafs as counted by constructExpr
participatingthe enfo methods in which we plan to participate

Definition at line 1248 of file nlhdlr_convex.c.

References 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().

◆ estimateVertexPolyhedral()

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

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.

Parameters
scipSCIP data structure
conshdlrnonlinear constraint handler
nlhdlrnonlinear handler
nlhdlrexprdatanonlinear handler expression data
solsolution to use, unless usemidpoint is TRUE
usemidpointwhether to use the midpoint of the domain instead of sol
overestimatewhether over- or underestimating
targetvaluea target value to achieve; if not reachable, then can give up early
rowpreprowprep where to store estimator
successbuffer to store whether successful

Definition at line 1341 of file nlhdlr_convex.c.

References VERTEXPOLYFUN_EVALDATA::evalsol, FALSE, 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(), and TRUE.

Referenced by SCIP_DECL_NLHDLRESTIMATE(), and SCIP_DECL_NLHDLRINITSEPA().

◆ estimateGradient()

static SCIP_RETCODE estimateGradient ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_SOL sol,
SCIP_Real  auxvalue,
SCIP_ROWPREP rowprep,
SCIP_Bool success 
)
static

adds an estimator computed via a gradient to a given rowprep

Parameters
scipSCIP data structure
nlhdlrexprdatanonlinear handler expression data
solsolution to use
auxvaluevalue of nlexpr in sol - we may not be able to take this value from nlexpr if it was evaluated at a different sol recently
rowpreprowprep where to store estimator
successbuffer to store whether successful

Definition at line 1474 of file nlhdlr_convex.c.

References FALSE, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPdebugMsg, SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexprGetDiffTag(), SCIPexprGetEvalValue(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPinfoMessage(), SCIPprintExpr(), SCIPquadprecSumQD, SCIProwprepAddConstant(), SCIProwprepSetLocal(), SCIPvarGetName(), and TRUE.

Referenced by SCIP_DECL_NLHDLRESTIMATE(), and SCIP_DECL_NLHDLRINITSEPA().

◆ estimateConvexSecant()

static SCIP_RETCODE estimateConvexSecant ( SCIP scip,
SCIP_NLHDLR nlhdlr,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_SOL sol,
SCIP_ROWPREP rowprep,
SCIP_Bool success 
)
static

adds an estimator generated by putting a secant through the coordinates given by the two closest integer points

Parameters
scipSCIP data structure
nlhdlrnonlinear handler
nlhdlrexprdatanonlinear handler expression data
solsolution to use, unless usemidpoint is TRUE
rowpreprowprep where to store estimator
successbuffer to store whether successful

Definition at line 1562 of file nlhdlr_convex.c.

References FALSE, NULL, REALABS, 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(), TRUE, and x.

Referenced by SCIP_DECL_NLHDLRESTIMATE().

◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

static SCIP_DECL_NLHDLRFREEHDLRDATA ( nlhdlrfreeHdlrDataConvexConcave  )
static

free handler data of convex or concave nlhdlr

Definition at line 1683 of file nlhdlr_convex.c.

References NULL, SCIP_OKAY, and SCIPfreeBlockMemory.

◆ SCIP_DECL_NLHDLRFREEEXPRDATA()

static SCIP_DECL_NLHDLRFREEEXPRDATA ( nlhdlrfreeExprDataConvexConcave  )
static

callback to free expression specific data

Definition at line 1697 of file nlhdlr_convex.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPhashmapFree(), and SCIPreleaseExpr().

◆ SCIP_DECL_NLHDLREXIT() [1/2]

static SCIP_DECL_NLHDLREXIT ( nlhdlrExitConvex  )
static

deinitialization of problem-specific data

Definition at line 1714 of file nlhdlr_convex.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), and SCIPnlhdlrGetData().

◆ SCIP_DECL_NLHDLRDETECT() [1/2]

static SCIP_DECL_NLHDLRDETECT ( nlhdlrDetectConvex  )
static

◆ SCIP_DECL_NLHDLREVALAUX()

static SCIP_DECL_NLHDLREVALAUX ( nlhdlrEvalAuxConvexConcave  )
static

auxiliary evaluation callback

Definition at line 1817 of file nlhdlr_convex.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPevalExpr(), and SCIPexprGetEvalValue().

◆ SCIP_DECL_NLHDLRINITSEPA() [1/2]

◆ SCIP_DECL_NLHDLRESTIMATE() [1/2]

◆ SCIP_DECL_NLHDLRCOPYHDLR() [1/2]

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrConvex  )
static

include nlhdlr in another scip instance

Definition at line 2019 of file nlhdlr_convex.c.

References CONVEX_NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrConvex(), and SCIPnlhdlrGetName().

◆ SCIP_DECL_NLHDLREXIT() [2/2]

static SCIP_DECL_NLHDLREXIT ( nlhdlrExitConcave  )
static

deinitialization of problem-specific data

Definition at line 2087 of file nlhdlr_convex.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), and SCIPnlhdlrGetData().

◆ SCIP_DECL_NLHDLRDETECT() [2/2]

static SCIP_DECL_NLHDLRDETECT ( nlhdlrDetectConcave  )
static

◆ SCIP_DECL_NLHDLRINITSEPA() [2/2]

◆ SCIP_DECL_NLHDLRESTIMATE() [2/2]

◆ SCIP_DECL_NLHDLRCOPYHDLR() [2/2]

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrConcave  )
static

includes nonlinear handler in another scip instance

Definition at line 2375 of file nlhdlr_convex.c.

References CONCAVE_NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrConcave(), and SCIPnlhdlrGetName().

Variable Documentation

◆ NCURVCHECKS

const int NCURVCHECKS = sizeof(CURVCHECKS) / sizeof(void*)
static

number of curvcheck methods

Definition at line 878 of file nlhdlr_convex.c.

Referenced by constructExpr().