nlhdlr_convex.c File Reference

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/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	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_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	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 46 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 47 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

CONVEX_NLHDLR_DETECTPRIORITY

#define CONVEX_NLHDLR_DETECTPRIORITY   50

Definition at line 48 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

CONVEX_NLHDLR_ENFOPRIORITY

#define CONVEX_NLHDLR_ENFOPRIORITY   50

Definition at line 49 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

CONCAVE_NLHDLR_NAME

#define CONCAVE_NLHDLR_NAME   "concave"

Definition at line 51 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 52 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

CONCAVE_NLHDLR_DETECTPRIORITY

#define CONCAVE_NLHDLR_DETECTPRIORITY   40

Definition at line 53 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

CONCAVE_NLHDLR_ENFOPRIORITY

#define CONCAVE_NLHDLR_ENFOPRIORITY   40

Definition at line 54 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

DEFAULT_DETECTSUM

#define DEFAULT_DETECTSUM   FALSE

Definition at line 56 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

DEFAULT_EXTENDEDFORM

#define DEFAULT_EXTENDEDFORM   TRUE

Definition at line 57 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

DEFAULT_CVXQUADRATIC_CONVEX

#define DEFAULT_CVXQUADRATIC_CONVEX   TRUE

Definition at line 58 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

DEFAULT_CVXQUADRATIC_CONCAVE

#define DEFAULT_CVXQUADRATIC_CONCAVE   FALSE

Definition at line 59 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

DEFAULT_CVXSIGNOMIAL

#define DEFAULT_CVXSIGNOMIAL   TRUE

Definition at line 60 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

DEFAULT_CVXPRODCOMP

#define DEFAULT_CVXPRODCOMP   TRUE

Definition at line 61 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

DEFAULT_HANDLETRIVIAL

#define DEFAULT_HANDLETRIVIAL   FALSE

Definition at line 62 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 64 of file nlhdlr_convex.c.

Referenced by SCIP_DECL_NLHDLRINITSEPA().

DECL_CURVCHECK

#define DECL_CURVCHECK

(

x

)

Value:

SCIP_RETCODE x( \
   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 */ \
   )

Definition at line 119 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

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 139 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

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 181 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

evaluate expression at solution w.r.t. auxiliary variables

Definition at line 219 of file nlhdlr_convex.c.

References VERTEXPOLYFUN_EVALDATA::evalsol, VERTEXPOLYFUN_EVALDATA::nlhdlrexprdata, NULL, VERTEXPOLYFUN_EVALDATA::scip, SCIP_CALL_ABORT, SCIPdebugMsg, SCIPevalExpr(), SCIPexprGetEvalValue(), SCIPgetVarExprVar(), SCIPsetSolVal(), and SCIPvarGetName().

exprstackInit()

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

static

initialize expression stack

Parameters

scip	SCIP data structure
exprstack	stack to initialize
initsize	initial size

Definition at line 248 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

scip	SCIP data structure
exprstack	free expression stack

Definition at line 267 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

scip	SCIP data structure
exprstack	expression stack
nexprs	number of expressions to push
exprs	expressions to push

Definition at line 280 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

exprstack

expression stack

Definition at line 309 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

exprstack

expression stack

Definition at line 321 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 338 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(), SCIPexprcurvMultiply(), SCIPexprGetChildren(), SCIPexprGetCurvature(), SCIPexprGetNChildren(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPexprSetCurvature(), SCIPgetCoefsExprSum(), 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 483 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 607 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(), SCIPisExprAbs(), SCIPisExprProduct(), SCIPisExprSum(), SCIPisZero(), SCIPprintExpr(), and SCIP_Interval::sup.

DECL_CURVCHECK() [4/5]

static DECL_CURVCHECK ( curvCheckExprhdlr  )

static

use expression handlers curvature callback to check whether given curvature can be achieved

Definition at line 824 of file nlhdlr_convex.c.

References DECL_CURVCHECK, exprstackPush(), nlhdlrExprGrowChildren(), NULL, SCIP_CALL, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIPallocBufferArray, SCIPexprcurvGetName(), SCIPexprGetChildren(), SCIPexprGetCurvature(), SCIPexprGetNChildren(), SCIPexprSetCurvature(), SCIPfreeBufferArray, SCIPhashmapGetImage(), SCIPinfoMessage(), SCIPisExprSum(), and SCIPprintExpr().

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

scip	SCIP data structure
expr	expression to check

Definition at line 917 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

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 950 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

scip	SCIP data structure
nlhdlrexprdata	nlhdlr expression data

Definition at line 1149 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

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 1276 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

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 1369 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

scip	SCIP data structure
nlhdlrexprdata	nonlinear handler expression data
sol	solution to use
auxvalue	value of nlexpr in sol - we may not be able to take this value from nlexpr if it was evaluated at a different sol recently
rowprep	rowprep where to store estimator
success	buffer to store whether successful

Definition at line 1502 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

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 1590 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 1711 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 1725 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 1742 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

checks whether expression (or -expression) is convex, possibly after introducing auxiliary variables

Definition at line 1759 of file nlhdlr_convex.c.

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

SCIP_DECL_NLHDLREVALAUX()

static SCIP_DECL_NLHDLREVALAUX ( nlhdlrEvalAuxConvexConcave  )

static

auxiliary evaluation callback

Definition at line 1845 of file nlhdlr_convex.c.

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

SCIP_DECL_NLHDLRINITSEPA() [1/2]

static SCIP_DECL_NLHDLRINITSEPA ( nlhdlrInitSepaConvex  )

static

init sepa callback that initializes LP

Definition at line 1859 of file nlhdlr_convex.c.

References collectLeafs(), estimateGradient(), FALSE, INITLPMAXVARVAL, MAX, 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(), and TRUE.

SCIP_DECL_NLHDLRESTIMATE() [1/2]

static SCIP_DECL_NLHDLRESTIMATE ( nlhdlrEstimateConvex  )

static

estimator callback

Definition at line 1979 of file nlhdlr_convex.c.

References estimateConvexSecant(), estimateGradient(), FALSE, NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPcreateRowprep(), SCIPexprGetCurvature(), SCIPexprGetEvalValue(), SCIPexprIsIntegral(), SCIPfreeRowprep(), SCIPgetNLPs(), SCIPhashmapGetImage(), SCIProwprepGetName(), SCIPsetPtrarrayVal(), SCIPsnprintf(), SCIPsolGetIndex(), and TRUE.

SCIP_DECL_NLHDLRCOPYHDLR() [1/2]

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrConvex  )

static

include nlhdlr in another scip instance

Definition at line 2045 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 2113 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

checks whether expression (or -expression) is concave, possibly after introducing auxiliary variables

Definition at line 2130 of file nlhdlr_convex.c.

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

SCIP_DECL_NLHDLRINITSEPA() [2/2]

static SCIP_DECL_NLHDLRINITSEPA ( nlhdlrInitSepaConcave  )

static

init sepa callback that initializes LP

Definition at line 2230 of file nlhdlr_convex.c.

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

SCIP_DECL_NLHDLRESTIMATE() [2/2]

static SCIP_DECL_NLHDLRESTIMATE ( nlhdlrEstimateConcave  )

static

estimator callback

Definition at line 2301 of file nlhdlr_convex.c.

References estimateVertexPolyhedral(), FALSE, MAX, NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_INVALID, SCIP_Longint, 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(), and TRUE.

SCIP_DECL_NLHDLRCOPYHDLR() [2/2]

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrConcave  )

static

includes nonlinear handler in another scip instance

Definition at line 2401 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 906 of file nlhdlr_convex.c.

Referenced by constructExpr().