Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

signomial nonlinear handler

Author
Liding Xu

Definition in file nlhdlr_signomial.c.

Go to the source code of this file.

Data Structures

struct  VERTEXPOLYFUN_EVALDATA
 

Macros

#define NLHDLR_NAME   "signomial"
 
#define NLHDLR_DESC   "handler for signomial expressions"
 
#define NLHDLR_DETECTPRIORITY   30
 
#define NLHDLR_ENFOPRIORITY   30
 
#define NLHDLR_MAXNUNDERVARS   14
 
#define NLHDLR_MINCUTSCALE   1e-5
 

Functions

static void freeExprDataMem (SCIP *scip, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool ispartial)
 
static void reformRowprep (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_ROWPREP *rowprep, SCIP_Real mincutscale, SCIP_Bool *success)
 
static SCIP_RETCODE storeCaptureVars (SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
 
static void checkSignomialBounds (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool *isboxsignomial)
 
static SCIP_DECL_VERTEXPOLYFUN (nlhdlrExprEvalPower)
 
static SCIP_RETCODE estimateSpecialPower (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool sign, SCIP_Real multiplier, SCIP_Bool overestimate, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *isspecial, SCIP_Bool *success)
 
static SCIP_RETCODE underEstimatePower (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_NLHDLR *nlhdlr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool sign, SCIP_Real multiplier, SCIP_SOL *sol, SCIP_Real targetvalue, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
 
static SCIP_RETCODE overEstimatePower (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool sign, SCIP_Real multiplier, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
 
static SCIP_DECL_NLHDLRESTIMATE (nlhdlrEstimateSignomial)
 
static SCIP_DECL_NLHDLRDETECT (nlhdlrDetectSignomial)
 
static SCIP_DECL_NLHDLREVALAUX (nlhdlrEvalauxSignomial)
 
static SCIP_DECL_NLHDLRCOPYHDLR (nlhdlrCopyhdlrSignomial)
 
static SCIP_DECL_NLHDLRFREEHDLRDATA (nlhdlrFreehdlrDataSignomial)
 
static SCIP_DECL_NLHDLRFREEEXPRDATA (nlhdlrFreeExprDataSignomial)
 
SCIP_RETCODE SCIPincludeNlhdlrSignomial (SCIP *scip)
 

Macro Definition Documentation

◆ NLHDLR_NAME

#define NLHDLR_NAME   "signomial"

Definition at line 50 of file nlhdlr_signomial.c.

◆ NLHDLR_DESC

#define NLHDLR_DESC   "handler for signomial expressions"

Definition at line 51 of file nlhdlr_signomial.c.

◆ NLHDLR_DETECTPRIORITY

#define NLHDLR_DETECTPRIORITY   30

Definition at line 52 of file nlhdlr_signomial.c.

◆ NLHDLR_ENFOPRIORITY

#define NLHDLR_ENFOPRIORITY   30

Definition at line 53 of file nlhdlr_signomial.c.

◆ NLHDLR_MAXNUNDERVARS

#define NLHDLR_MAXNUNDERVARS   14

maximum number of variables when underestimating a concave power function (maximum: 14)

Definition at line 56 of file nlhdlr_signomial.c.

◆ NLHDLR_MINCUTSCALE

#define NLHDLR_MINCUTSCALE   1e-5

minimum scale factor when scaling a cut (minimum: 1e-6)

Definition at line 57 of file nlhdlr_signomial.c.

Function Documentation

◆ freeExprDataMem()

static void freeExprDataMem ( SCIP scip,
SCIP_NLHDLREXPRDATA **  nlhdlrexprdata,
SCIP_Bool  ispartial 
)
static

free the memory of expression data

Parameters
scipSCIP data structure
nlhdlrexprdataexpression data
ispartialfree the partially allocated memory or the fully allocated memory?

Definition at line 193 of file nlhdlr_signomial.c.

References NULL, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPfreeBlockMemoryArrayNull.

Referenced by SCIP_DECL_NLHDLRDETECT(), and SCIP_DECL_NLHDLRFREEEXPRDATA().

◆ reformRowprep()

static void reformRowprep ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_ROWPREP rowprep,
SCIP_Real  mincutscale,
SCIP_Bool success 
)
static

reforms a rowprep to a standard form for nonlinear handlers

The input rowprep is of the form \( a_u u + a_v v + b \). If in the overestimate mode, then we relax \( t \le x^a \), i.e., \( 0 \le u^f - v^g \). This implies that \( t \) is in \( v = (v',t) \). Therefore, the valid inequality is \( 0 \le a_u u + a_v v + b \). As overestimate mode requires that \( t \) is in the left hand side, the coefficients of \( t \) must be made negative while keeping the sign of the inequality, we can show that \( a_t \le 0 \), so it suffices to divide the both sides by \( -a_t \ge 0\), which yields \( t \le (a_u u + a_v' v' + b) / -a_t \). A rowprep in standard form only contains an estimator of the expression and no auxvar. If in the underestimate mode, then we relax \( x^a \le t \), i.e., \( u^f - v^g \le 0 \). This implies that \( t \) is in \( v = (v',t) \). Therefore, the valid inequality is \( a_u u + a_v v + b \le 0 \). As overestimate mode requires that \( t \) is in the left hand side, the coefficients of \( t \) must be made negative while keeping the sign of the inequality, we can show that \( a_t \le 0 \), so it suffices to divide the both sides by \( -a_t \ge 0 \), which yields \( (a_u u + a_v' v' + b) / -a_t \le t \). A rowprep in standard form only contains an estimator of the expression and no auxvar.

Parameters
scipSCIP data structure
nlhdlrexprdataexpression data
rowprepcut to be reformulated
mincutscalemin scaling factor for the cut in rowprep
successpointer to store whether the reformulating was successful

Definition at line 231 of file nlhdlr_signomial.c.

References FALSE, NULL, SCIP_Real, SCIPisGT(), SCIPisZero(), SCIProwprepAddSide(), SCIProwprepGetCoefs(), SCIProwprepGetNVars(), SCIProwprepGetSide(), and SCIProwprepGetVars().

Referenced by SCIP_DECL_NLHDLRESTIMATE().

◆ storeCaptureVars()

static SCIP_RETCODE storeCaptureVars ( SCIP scip,
SCIP_EXPR expr,
SCIP_NLHDLREXPRDATA nlhdlrexprdata 
)
static

store and capture variables associated with the expression and its subexpressions

Parameters
scipSCIP data structure
exprexpression
nlhdlrexprdataexpression data

Definition at line 291 of file nlhdlr_signomial.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcaptureVar(), SCIPgetExprAuxVarNonlinear(), and TRUE.

Referenced by SCIP_DECL_NLHDLRESTIMATE().

◆ checkSignomialBounds()

static void checkSignomialBounds ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_Bool isboxsignomial 
)
static

get bounds of variables x,t and check whether they are box constrained signomial variables

Parameters
scipSCIP data structure
nlhdlrexprdataexpression data
isboxsignomialbuffer to store whether variables are box constrained signomial variables

Definition at line 322 of file nlhdlr_signomial.c.

References FALSE, MAX, MIN, SCIP_Real, SCIPisEQ(), SCIPisInfinity(), SCIPisPositive(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by SCIP_DECL_NLHDLRESTIMATE().

◆ SCIP_DECL_VERTEXPOLYFUN()

static SCIP_DECL_VERTEXPOLYFUN ( nlhdlrExprEvalPower  )
static

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

Definition at line 365 of file nlhdlr_signomial.c.

References VERTEXPOLYFUN_EVALDATA::nlhdlrexprdata, VERTEXPOLYFUN_EVALDATA::nsignvars, NULL, VERTEXPOLYFUN_EVALDATA::scip, SCIP_Real, SCIPdebugMsg, and VERTEXPOLYFUN_EVALDATA::sign.

◆ estimateSpecialPower()

static SCIP_RETCODE estimateSpecialPower ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_Bool  sign,
SCIP_Real  multiplier,
SCIP_Bool  overestimate,
SCIP_SOL sol,
SCIP_ROWPREP rowprep,
SCIP_Bool isspecial,
SCIP_Bool success 
)
static

determine whether a power function \( w^h \) is special and add an overunderestimator or underestimator to a given rowprep

\( w^h \) is special, if all variables are fixed, or it is a constant to estimate, a univariate power to estimate, or a bivariate power to underestimate. The estimator is multiplied by the multiplier and stored in the rowprep.

Parameters
scipSCIP data structure
nlhdlrexprdatanonlinear handler expression data
signthe sign of variables of the power function
multiplierthe multiplier of the estimator
overestimatewhether overestimate or underestimator the power function
solsolution \( w' \) to use in estimation
rowpreprowprep where to store estimator
isspecialbuffer to store whether this function is a special case
successbuffer to store whether successful

Definition at line 404 of file nlhdlr_signomial.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPestimateRoot(), SCIPgetSolVal(), SCIPisRelEQ(), SCIProwprepAddConstant(), and TRUE.

Referenced by SCIP_DECL_NLHDLRESTIMATE().

◆ underEstimatePower()

static SCIP_RETCODE underEstimatePower ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_NLHDLR nlhdlr,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_Bool  sign,
SCIP_Real  multiplier,
SCIP_SOL sol,
SCIP_Real  targetvalue,
SCIP_ROWPREP rowprep,
SCIP_Bool success 
)
static

adds an underestimator for a multivariate concave power function \( w^h \) to a given rowprep

Calls SCIPcomputeFacetVertexPolyhedralNonlinear() for \( w^h \) and box set to local bounds of auxiliary variables. The estimator is multiplied by the multiplier and stored in the rowprep.

Parameters
scipSCIP data structure
conshdlrnonlinear constraint handler
nlhdlrnonlinear handler
nlhdlrexprdatanonlinear handler expression data
signthe sign of variables of the power function
multiplierthe multiplier of the estimator
solsolution \( w' \) to use
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 594 of file nlhdlr_signomial.c.

References FALSE, VERTEXPOLYFUN_EVALDATA::nlhdlrexprdata, VERTEXPOLYFUN_EVALDATA::nsignvars, NULL, VERTEXPOLYFUN_EVALDATA::scip, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPcomputeFacetVertexPolyhedralNonlinear(), SCIPdebugMsg, SCIPgetSolVal(), SCIProwprepAddConstant(), VERTEXPOLYFUN_EVALDATA::sign, and SCIP_RowPrep::vars.

Referenced by SCIP_DECL_NLHDLRESTIMATE().

◆ overEstimatePower()

static SCIP_RETCODE overEstimatePower ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_Bool  sign,
SCIP_Real  multiplier,
SCIP_SOL sol,
SCIP_ROWPREP rowprep,
SCIP_Bool success 
)
static

adds an overestimator for a concave power function \( w^h \) to a given rowprep

The estimator is multiplied by the multiplier and stored in the rowprep.

Parameters
scipSCIP data structure
nlhdlrexprdatanonlinear handler expression data
signthe sign of variables of the power function
multiplierthe multiplier of the estimator
solsolution to use
rowpreprowprep where to store estimator
successbuffer to store whether successful

Definition at line 681 of file nlhdlr_signomial.c.

References FALSE, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPgetSolVal(), SCIProwprepAddConstant(), and TRUE.

Referenced by SCIP_DECL_NLHDLRESTIMATE().

◆ SCIP_DECL_NLHDLRESTIMATE()

◆ SCIP_DECL_NLHDLRDETECT()

◆ SCIP_DECL_NLHDLREVALAUX()

static SCIP_DECL_NLHDLREVALAUX ( nlhdlrEvalauxSignomial  )
static

auxiliary evaluation callback of nonlinear handler

Definition at line 1016 of file nlhdlr_signomial.c.

References NULL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), and SCIPisPositive().

◆ SCIP_DECL_NLHDLRCOPYHDLR()

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrSignomial  )
static

nonlinear handler copy callback

Definition at line 1047 of file nlhdlr_signomial.c.

References NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrSignomial(), and SCIPnlhdlrGetName().

◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

static SCIP_DECL_NLHDLRFREEHDLRDATA ( nlhdlrFreehdlrDataSignomial  )
static

callback to free data of handler

Definition at line 1060 of file nlhdlr_signomial.c.

References NULL, SCIP_OKAY, and SCIPfreeBlockMemory.

◆ SCIP_DECL_NLHDLRFREEEXPRDATA()

static SCIP_DECL_NLHDLRFREEEXPRDATA ( nlhdlrFreeExprDataSignomial  )
static

callback to free expression specific data

Definition at line 1071 of file nlhdlr_signomial.c.

References FALSE, freeExprDataMem(), NULL, SCIP_CALL, SCIP_OKAY, SCIPreleaseExpr(), and SCIPreleaseVar().