Detailed Description

signomial nonlinear handler

Author: Liding Xu

#include "scip/nlhdlr_signomial.h"
#include "scip/cons_nonlinear.h"
#include "scip/pub_misc_rowprep.h"
#include "scip/pub_nlhdlr.h"
#include "scip/scip_expr.h"
#include "scip/expr_var.h"
#include "scip/expr_pow.h"

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

scip	SCIP data structure
nlhdlrexprdata	expression data
ispartial	free 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

scip	SCIP data structure
nlhdlrexprdata	expression data
rowprep	cut to be reformulated
mincutscale	min scaling factor for the cut in rowprep
success	pointer 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

scip	SCIP data structure
expr	expression
nlhdlrexprdata	expression 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

scip	SCIP data structure
nlhdlrexprdata	expression data
isboxsignomial	buffer 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

scip	SCIP data structure
nlhdlrexprdata	nonlinear handler expression data
sign	the sign of variables of the power function
multiplier	the multiplier of the estimator
overestimate	whether overestimate or underestimator the power function
sol	solution \( w' \) to use in estimation
rowprep	rowprep where to store estimator
isspecial	buffer to store whether this function is a special case
success	buffer 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

scip	SCIP data structure
conshdlr	nonlinear constraint handler
nlhdlr	nonlinear handler
nlhdlrexprdata	nonlinear handler expression data
sign	the sign of variables of the power function
multiplier	the multiplier of the estimator
sol	solution \( w' \) to use
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 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

scip	SCIP data structure
nlhdlrexprdata	nonlinear handler expression data
sign	the sign of variables of the power function
multiplier	the multiplier of the estimator
sol	solution to use
rowprep	rowprep where to store estimator
success	buffer 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()

static SCIP_DECL_NLHDLRESTIMATE ( nlhdlrEstimateSignomial )

static

nonlinear handler estimation callback

Definition at line 748 of file nlhdlr_signomial.c.

References checkSignomialBounds(), estimateSpecialPower(), FALSE, NULL, SCIP_RowPrep::nvars, overEstimatePower(), printSignomial(), reformRowprep(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPcreateRowprep(), SCIPensureRowprepSize(), SCIPfreeRowprep(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPnlhdlrGetData(), SCIPsetPtrarrayVal(), storeCaptureVars(), TRUE, and underEstimatePower().

◆ SCIP_DECL_NLHDLRDETECT()

static SCIP_DECL_NLHDLRDETECT ( nlhdlrDetectSignomial )

static

callback to detect structure in expression tree

Definition at line 885 of file nlhdlr_signomial.c.

References FALSE, freeExprDataMem(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemory, SCIPallocClearBlockMemoryArray, SCIPcaptureExpr(), SCIPdebugMsg, SCIPexprGetNChildren(), SCIPgetExprMonomialData(), SCIPgetStage(), SCIPgetSubscipDepth(), SCIPinfoMessage(), SCIPisEQ(), SCIPisExprProduct(), SCIPprintExpr(), SCIPregisterExprUsageNonlinear(), and TRUE.

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

SCIP

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ NLHDLR_NAME

◆ NLHDLR_DESC

◆ NLHDLR_DETECTPRIORITY

◆ NLHDLR_ENFOPRIORITY

◆ NLHDLR_MAXNUNDERVARS

◆ NLHDLR_MINCUTSCALE

Function Documentation

◆ freeExprDataMem()

◆ reformRowprep()

◆ storeCaptureVars()

◆ checkSignomialBounds()

◆ SCIP_DECL_VERTEXPOLYFUN()

◆ estimateSpecialPower()

◆ underEstimatePower()

◆ overEstimatePower()

◆ SCIP_DECL_NLHDLRESTIMATE()

◆ SCIP_DECL_NLHDLRDETECT()

◆ SCIP_DECL_NLHDLREVALAUX()

◆ SCIP_DECL_NLHDLRCOPYHDLR()

◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

◆ SCIP_DECL_NLHDLRFREEEXPRDATA()