Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

nonlinear handlers for convex and concave expressions

Author
Benjamin Mueller
Stefan Vigerske

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_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 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*)
 

Macro Definition Documentation

◆ CONVEX_NLHDLR_NAME

#define CONVEX_NLHDLR_NAME   "convex"

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

Referenced by SCIPincludeNlhdlrConvex().

◆ CONVEX_NLHDLR_DETECTPRIORITY

#define CONVEX_NLHDLR_DETECTPRIORITY   50

Definition at line 46 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

◆ CONVEX_NLHDLR_ENFOPRIORITY

#define CONVEX_NLHDLR_ENFOPRIORITY   50

Definition at line 47 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

◆ CONCAVE_NLHDLR_NAME

#define CONCAVE_NLHDLR_NAME   "concave"

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

Referenced by SCIPincludeNlhdlrConcave().

◆ CONCAVE_NLHDLR_DETECTPRIORITY

#define CONCAVE_NLHDLR_DETECTPRIORITY   40

Definition at line 51 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

◆ CONCAVE_NLHDLR_ENFOPRIORITY

#define CONCAVE_NLHDLR_ENFOPRIORITY   40

Definition at line 52 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

◆ DEFAULT_DETECTSUM

#define DEFAULT_DETECTSUM   FALSE

Definition at line 54 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

◆ DEFAULT_EXTENDEDFORM

#define DEFAULT_EXTENDEDFORM   TRUE

Definition at line 55 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

◆ DEFAULT_CVXQUADRATIC_CONVEX

#define DEFAULT_CVXQUADRATIC_CONVEX   TRUE

Definition at line 56 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConvex().

◆ DEFAULT_CVXQUADRATIC_CONCAVE

#define DEFAULT_CVXQUADRATIC_CONCAVE   FALSE

Definition at line 57 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave().

◆ DEFAULT_CVXSIGNOMIAL

#define DEFAULT_CVXSIGNOMIAL   TRUE

Definition at line 58 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

◆ DEFAULT_CVXPRODCOMP

#define DEFAULT_CVXPRODCOMP   TRUE

Definition at line 59 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

◆ DEFAULT_HANDLETRIVIAL

#define DEFAULT_HANDLETRIVIAL   FALSE

Definition at line 60 of file nlhdlr_convex.c.

Referenced by SCIPincludeNlhdlrConcave(), and SCIPincludeNlhdlrConvex().

◆ DEFAULT_MAXPERTURB

#define DEFAULT_MAXPERTURB   0.01

Definition at line 61 of file nlhdlr_convex.c.

Referenced by 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 63 of file nlhdlr_convex.c.

Referenced by SCIP_DECL_NLHDLRINITSEPA().

◆ RANDNUMINITSEED

#define RANDNUMINITSEED   220802

initial seed for random number generator for point perturbation

Definition at line 64 of file nlhdlr_convex.c.

Referenced by estimateGradient().

◆ 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:63
SCIP_VAR ** x
Definition: circlepacking.c:63
#define SCIP_Bool
Definition: def.h:91
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
Definition: type_nlhdlr.h:442

Definition at line 121 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 141 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 183 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 250 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 269 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 282 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 311 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 323 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 340 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 485 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 609 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

◆ 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 919 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 952 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 1151 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 1278 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 1371 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().

◆ estimateGradientInner()

static SCIP_RETCODE estimateGradientInner ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_SOL sol,
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
rowpreprowprep where to store estimator
successbuffer to store whether successful

Definition at line 1504 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(), SCIPquadprecSumQD, SCIProwprepAddConstant(), SCIProwprepSetLocal(), SCIPvarGetName(), and TRUE.

Referenced by estimateGradient().

◆ estimateGradient()

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

adds an estimator computed via a gradient to a given rowprep, possibly perturbing solution

Parameters
scipSCIP data structure
nlhdlrnonlinear handler
nlhdlrexprdatanonlinear handler expression data
solsolution to use
rowpreprowprep where to store estimator
successbuffer to store whether successful

Definition at line 1576 of file nlhdlr_convex.c.

References estimateGradientInner(), FALSE, MAX, MIN, NULL, RANDNUMINITSEED, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPcreateSol(), SCIPdebugMsg, SCIPepsilon(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPinfoMessage(), SCIPisZero(), SCIPnlhdlrGetData(), SCIPprintExpr(), SCIPrandomGetReal(), SCIPsetSolVal(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by SCIP_DECL_NLHDLRESTIMATE(), SCIP_DECL_NLHDLRINITSEPA(), and SCIP_DECL_NLHDLRSOLLINEARIZE().

◆ 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 1675 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(), and SCIP_DECL_NLHDLRSOLLINEARIZE().

◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

static SCIP_DECL_NLHDLRFREEHDLRDATA ( nlhdlrfreeHdlrDataConvexConcave  )
static

free handler data of convex or concave nlhdlr

Definition at line 1796 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 1811 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 1828 of file nlhdlr_convex.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeRandom(), 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 1934 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_NLHDLRSOLLINEARIZE()

◆ SCIP_DECL_NLHDLRCOPYHDLR() [1/2]

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrConvex  )
static

include nlhdlr in another scip instance

Definition at line 2199 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 2273 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 2562 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 908 of file nlhdlr_convex.c.

Referenced by constructExpr().