Detailed Description

methods and files provided by the default nonlinear handlers of SCIP

Modules
	Inclusion methods
	methods to include specific nonlinear handlers into SCIP

Files
file	nlhdlr_bilinear.h
	bilinear nonlinear handler

file	nlhdlr_convex.h
	nonlinear handlers for convex and concave expressions, respectively

file	nlhdlr_default.h
	default nonlinear handler that calls expression handler methods

file	nlhdlr_perspective.h
	perspective nonlinear handler

file	nlhdlr_quadratic.h
	nonlinear handler to handle quadratic expressions

file	nlhdlr_quotient.h
	quotient nonlinear handler

file	nlhdlr_soc.h
	soc nonlinear handler

Bilinear nonlinear handler
This nonlinear handler detects and collects bilinear terms and provides specialized propagation and estimation functionality.
SCIP_EXPR **	SCIPgetExprsBilinear (SCIP_NLHDLR *nlhdlr)

SCIP_NLHDLREXPRDATA **	SCIPgetExprsdataBilinear (SCIP_NLHDLR *nlhdlr)

int	SCIPgetNExprsBilinear (SCIP_NLHDLR *nlhdlr)

SCIP_RETCODE	SCIPaddIneqBilinear (SCIP scip, SCIP_NLHDLR nlhdlr, SCIP_EXPR expr, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Bool success)

void	SCIPaddBilinLinearization (SCIP scip, SCIP_Real bilincoef, SCIP_Real refpointx, SCIP_Real refpointy, SCIP_Real lincoefx, SCIP_Real lincoefy, SCIP_Real linconstant, SCIP_Bool *success)

void	SCIPaddBilinMcCormick (SCIP scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real lincoefx, SCIP_Real lincoefy, SCIP_Real linconstant, SCIP_Bool *success)

void	SCIPcomputeBilinEnvelope1 (SCIP scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Real RESTRICT lincoefx, SCIP_Real RESTRICT lincoefy, SCIP_Real RESTRICT linconstant, SCIP_Bool *RESTRICT success)

void	SCIPcomputeBilinEnvelope2 (SCIP scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real alpha1, SCIP_Real beta1, SCIP_Real gamma1, SCIP_Real alpha2, SCIP_Real beta2, SCIP_Real gamma2, SCIP_Real RESTRICT lincoefx, SCIP_Real RESTRICT lincoefy, SCIP_Real RESTRICT linconstant, SCIP_Bool *RESTRICT success)

Convex and concave nonlinear handlers
These nonlinear handler detect convex and concave subexpressions and provide specialized estimation functionality.
SCIP_RETCODE	SCIPhasExprCurvature (SCIP scip, SCIP_EXPR expr, SCIP_EXPRCURV curv, SCIP_Bool success, SCIP_HASHMAP assumevarfixed)

SOC nonlinear handler
This nonlinear handler detects second-order cone constraints in the extended formulation and provides specialized separation functionality.
SCIP_RETCODE	SCIPisSOCNonlinear (SCIP scip, SCIP_CONS cons, SCIP_Bool compeigenvalues, SCIP_Bool success, SCIP_SIDETYPE sidetype, SCIP_VAR *vars, SCIP_Real offsets, SCIP_Real transcoefs, int transcoefsidx, int *termbegins, int nvars, int *nterms)

void	SCIPfreeSOCArraysNonlinear (SCIP scip, SCIP_VAR vars, SCIP_Real offsets, SCIP_Real transcoefs, int transcoefsidx, int **termbegins, int nvars, int nterms)

Function Documentation

◆ SCIPgetExprsBilinear()

SCIP_EXPR** SCIPgetExprsBilinear ( SCIP_NLHDLR * nlhdlr )

returns an array of expressions that have been detected by the bilinear nonlinear handler

Parameters

nlhdlr nonlinear handler

Definition at line 1527 of file nlhdlr_bilinear.c.

References NLHDLR_NAME, NULL, SCIPnlhdlrGetData(), and SCIPnlhdlrGetName().

◆ SCIPgetExprsdataBilinear()

SCIP_NLHDLREXPRDATA** SCIPgetExprsdataBilinear ( SCIP_NLHDLR * nlhdlr )

returns an array of nonlinear handler expressions data of expressions that have been detected by the bilinear nonlinear handler

Parameters

nlhdlr nonlinear handler

◆ SCIPgetNExprsBilinear()

int SCIPgetNExprsBilinear ( SCIP_NLHDLR * nlhdlr )

returns the total number of expressions that have been detected by the bilinear nonlinear handler

Parameters

nlhdlr nonlinear handler

Definition at line 1543 of file nlhdlr_bilinear.c.

References NLHDLR_NAME, NULL, SCIPnlhdlrGetData(), and SCIPnlhdlrGetName().

◆ SCIPaddIneqBilinear()

SCIP_RETCODE SCIPaddIneqBilinear	(	SCIP *	scip,
		SCIP_NLHDLR *	nlhdlr,
		SCIP_EXPR *	expr,
		SCIP_Real	xcoef,
		SCIP_Real	ycoef,
		SCIP_Real	constant,
		SCIP_Bool *	success
	)

adds a globally valid inequality of the form \(\text{xcoef}\cdot x \leq \text{ycoef} \cdot y + \text{constant}\) to a product expression of the form \(x\cdot y\)

Parameters

scip	SCIP data structure
nlhdlr	nonlinear handler
expr	product expression
xcoef	x coefficient
ycoef	y coefficient
constant	constant part
success	buffer to store whether inequality has been accepted

Definition at line 1559 of file nlhdlr_bilinear.c.

References FALSE, getIneqViol(), MAX, NLHDLR_NAME, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetExprAuxVarNonlinear(), SCIPgetNlhdlrExprDataNonlinear(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisGE(), SCIPisLT(), SCIPmarkExprPropagateNonlinear(), SCIPnlhdlrGetName(), SCIPvarGetName(), SCIPwarningMessage(), TRUE, x, and y.

◆ SCIPaddBilinLinearization()

void SCIPaddBilinLinearization	(	SCIP *	scip,
		SCIP_Real	bilincoef,
		SCIP_Real	refpointx,
		SCIP_Real	refpointy,
		SCIP_Real *	lincoefx,
		SCIP_Real *	lincoefy,
		SCIP_Real *	linconstant,
		SCIP_Bool *	success
	)

computes coefficients of linearization of a bilinear term in a reference point

Parameters

scip	SCIP data structure
bilincoef	coefficient of bilinear term
refpointx	point where to linearize first variable
refpointy	point where to linearize second variable
lincoefx	buffer to add coefficient of first variable in linearization
lincoefy	buffer to add coefficient of second variable in linearization
linconstant	buffer to add constant of linearization
success	buffer to set to FALSE if linearization has failed due to large numbers

Definition at line 1715 of file nlhdlr_bilinear.c.

References FALSE, NULL, REALABS, SCIP_Real, and SCIPisInfinity().

◆ SCIPaddBilinMcCormick()

void SCIPaddBilinMcCormick	(	SCIP *	scip,
		SCIP_Real	bilincoef,
		SCIP_Real	lbx,
		SCIP_Real	ubx,
		SCIP_Real	refpointx,
		SCIP_Real	lby,
		SCIP_Real	uby,
		SCIP_Real	refpointy,
		SCIP_Bool	overestimate,
		SCIP_Real *	lincoefx,
		SCIP_Real *	lincoefy,
		SCIP_Real *	linconstant,
		SCIP_Bool *	success
	)

computes coefficients of McCormick under- or overestimation of a bilinear term

Parameters

scip	SCIP data structure
bilincoef	coefficient of bilinear term
lbx	lower bound on first variable
ubx	upper bound on first variable
refpointx	reference point for first variable
lby	lower bound on second variable
uby	upper bound on second variable
refpointy	reference point for second variable
overestimate	whether to compute an overestimator instead of an underestimator
lincoefx	buffer to add coefficient of first variable in linearization
lincoefy	buffer to add coefficient of second variable in linearization
linconstant	buffer to add constant of linearization
success	buffer to set to FALSE if linearization has failed due to large numbers

Definition at line 1762 of file nlhdlr_bilinear.c.

References FALSE, MAX, NULL, REALABS, SCIP_Real, SCIPdebugMsg, SCIPisGE(), SCIPisInfinity(), SCIPisLE(), and SCIPisRelEQ().

Referenced by addBilinearTermToCut(), addRltTerm(), estimateBivariate(), SCIP_DECL_EXPRESTIMATE(), SCIP_DECL_EXPRINITESTIMATES(), SCIP_DECL_NLHDLRESTIMATE(), and separateMcCormickImplicit().

◆ SCIPcomputeBilinEnvelope1()

void SCIPcomputeBilinEnvelope1	(	SCIP *	scip,
		SCIP_Real	bilincoef,
		SCIP_Real	lbx,
		SCIP_Real	ubx,
		SCIP_Real	refpointx,
		SCIP_Real	lby,
		SCIP_Real	uby,
		SCIP_Real	refpointy,
		SCIP_Bool	overestimate,
		SCIP_Real	xcoef,
		SCIP_Real	ycoef,
		SCIP_Real	constant,
		SCIP_Real *RESTRICT	lincoefx,
		SCIP_Real *RESTRICT	lincoefy,
		SCIP_Real *RESTRICT	linconstant,
		SCIP_Bool *RESTRICT	success
	)

computes coefficients of linearization of a bilinear term in a reference point when given a linear inequality involving only the variables of the bilinear term

Note: the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems" by Marco Locatelli

Parameters

scip	SCIP data structure
bilincoef	coefficient of bilinear term
lbx	lower bound on first variable
ubx	upper bound on first variable
refpointx	reference point for first variable
lby	lower bound on second variable
uby	upper bound on second variable
refpointy	reference point for second variable
overestimate	whether to compute an overestimator instead of an underestimator
xcoef	x coefficient of linear inequality; must be in {-1,0,1}
ycoef	y coefficient of linear inequality
constant	constant of linear inequality
lincoefx	buffer to store coefficient of first variable in linearization
lincoefy	buffer to store coefficient of second variable in linearization
linconstant	buffer to store constant of linearization
success	buffer to store whether linearization was successful

Definition at line 1970 of file nlhdlr_bilinear.c.

References FALSE, NULL, QUAD, QUAD_SCALE, QUAD_TO_DBL, SCIP_INVALID, SCIP_Real, SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisZero(), SCIPquadprecDivDD, SCIPquadprecDivQQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSquareQ, SCIPquadprecSumDD, SCIPquadprecSumQD, and SCIPquadprecSumQQ.

Referenced by updateBilinearRelaxation().

◆ SCIPcomputeBilinEnvelope2()

void SCIPcomputeBilinEnvelope2	(	SCIP *	scip,
		SCIP_Real	bilincoef,
		SCIP_Real	lbx,
		SCIP_Real	ubx,
		SCIP_Real	refpointx,
		SCIP_Real	lby,
		SCIP_Real	uby,
		SCIP_Real	refpointy,
		SCIP_Bool	overestimate,
		SCIP_Real	xcoef1,
		SCIP_Real	ycoef1,
		SCIP_Real	constant1,
		SCIP_Real	xcoef2,
		SCIP_Real	ycoef2,
		SCIP_Real	constant2,
		SCIP_Real *RESTRICT	lincoefx,
		SCIP_Real *RESTRICT	lincoefy,
		SCIP_Real *RESTRICT	linconstant,
		SCIP_Bool *RESTRICT	success
	)

computes coefficients of linearization of a bilinear term in a reference point when given two linear inequalities involving only the variables of the bilinear term

Note: the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems" by Marco Locatelli

Parameters

scip	SCIP data structure
bilincoef	coefficient of bilinear term
lbx	lower bound on first variable
ubx	upper bound on first variable
refpointx	reference point for first variable
lby	lower bound on second variable
uby	upper bound on second variable
refpointy	reference point for second variable
overestimate	whether to compute an overestimator instead of an underestimator
xcoef1	x coefficient of linear inequality; must be in {-1,0,1}
ycoef1	y coefficient of linear inequality
constant1	constant of linear inequality
xcoef2	x coefficient of linear inequality; must be in {-1,0,1}
ycoef2	y coefficient of linear inequality
constant2	constant of linear inequality
lincoefx	buffer to store coefficient of first variable in linearization
lincoefy	buffer to store coefficient of second variable in linearization
linconstant	buffer to store constant of linearization
success	buffer to store whether linearization was successful

Definition at line 2194 of file nlhdlr_bilinear.c.

References computeBilinEnvelope2(), FALSE, NULL, SCIP_INVALID, SCIP_Real, SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), and SCIPisRelEQ().

Referenced by updateBilinearRelaxation().

◆ SCIPhasExprCurvature()

SCIP_RETCODE SCIPhasExprCurvature	(	SCIP *	scip,
		SCIP_EXPR *	expr,
		SCIP_EXPRCURV	curv,
		SCIP_Bool *	success,
		SCIP_HASHMAP *	assumevarfixed
	)

checks whether a given expression is convex or concave w.r.t. the original variables

This function uses the methods that are used in the detection algorithm of the convex nonlinear handler.

Parameters

scip	SCIP data structure
expr	expression
curv	curvature to check for
success	buffer to store whether expression has curvature curv (w.r.t. original variables)
assumevarfixed	hashmap containing variables that should be assumed to be fixed, or NULL

Definition at line 2455 of file nlhdlr_convex.c.

References constructExpr(), FALSE, NULL, SCIP_CALL, SCIP_EXPRCURV_UNKNOWN, SCIP_OKAY, SCIPblkmem(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPreleaseExpr(), and TRUE.

Referenced by checkSubproblemConvexity(), and initSolve().

◆ SCIPisSOCNonlinear()

SCIP_RETCODE SCIPisSOCNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Bool	compeigenvalues,
		SCIP_Bool *	success,
		SCIP_SIDETYPE *	sidetype,
		SCIP_VAR ***	vars,
		SCIP_Real **	offsets,
		SCIP_Real **	transcoefs,
		int **	transcoefsidx,
		int **	termbegins,
		int *	nvars,
		int *	nterms
	)

checks whether constraint is SOC representable in original variables and returns the SOC representation

The SOC representation has the form: \(\sqrt{\sum_{i=1}^{n} (v_i^T x + \beta_i)^2} - v_{n+1}^T x - \beta_{n+1} \lessgtr 0\), where \(n+1 = \text{nterms}\) and the inequality type is given by sidetype (SCIP_SIDETYPE_RIGHT if inequality is \(\leq\), SCIP_SIDETYPE_LEFT if \(\geq\)).

For each term (i.e. for each \(i\) in the above notation as well as \(n+1\)), the constant \(\beta_i\) is given by the corresponding element offsets[i-1] and termbegins[i-1] is the starting position of the term in arrays transcoefs and transcoefsidx. The overall number of nonzeros is termbegins[nterms].

Arrays transcoefs and transcoefsidx have size termbegins[nterms] and define the linear expressions \(v_i^T x\) for each term. For a term \(i\) in the above notation, the nonzeroes are given by elements termbegins[i-1]...termbegins[i] of transcoefs and transcoefsidx. There may be no nonzeroes for some term (i.e., constant terms are possible). transcoefs contains the coefficients \(v_i\) and transcoefsidx contains positions of variables in the vars array.

The vars array has size nvars and contains \(x\) variables; each variable is included at most once.

The arrays should be freed by calling SCIPfreeSOCArraysNonlinear().

This function uses the methods that are used in the detection algorithm of the SOC nonlinear handler.

Parameters

scip	SCIP data structure
cons	nonlinear constraint
compeigenvalues	whether eigenvalues should be computed to detect complex cases
success	pointer to store whether SOC structure has been detected
sidetype	pointer to store which side of cons is SOC representable; only valid when success is TRUE
vars	variables (x) that appear on both sides; no duplicates are allowed
offsets	offsets of both sides (beta_i)
transcoefs	non-zeros of linear transformation vectors (v_i)
transcoefsidx	mapping of transformation coefficients to variable indices in vars
termbegins	starting indices of transcoefs for each term
nvars	total number of variables appearing (i.e. size of vars)
nterms	number of summands in the SQRT +1 for RHS (n+1)

Definition at line 2733 of file nlhdlr_soc.c.

References detectSOC(), FALSE, freeNlhdlrExprData(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPallocBlockMemoryArray, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPgetExprNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPgetVarExprVar(), and SCIPisExprVar().

◆ SCIPfreeSOCArraysNonlinear()

void SCIPfreeSOCArraysNonlinear	(	SCIP *	scip,
		SCIP_VAR ***	vars,
		SCIP_Real **	offsets,
		SCIP_Real **	transcoefs,
		int **	transcoefsidx,
		int **	termbegins,
		int	nvars,
		int	nterms
	)

frees arrays created by SCIPisSOCNonlinear()

Parameters

scip	SCIP data structure
vars	variables that appear on both sides (x)
offsets	offsets of both sides (beta_i)
transcoefs	non-zeros of linear transformation vectors (v_i)
transcoefsidx	mapping of transformation coefficients to variable indices in vars
termbegins	starting indices of transcoefs for each term
nvars	total number of variables appearing
nterms	number of summands in the SQRT +1 for RHS (n+1)

Definition at line 2823 of file nlhdlr_soc.c.

References nterms, NULL, and SCIPfreeBlockMemoryArray.

SCIP

Detailed Description

Modules

Files

Bilinear nonlinear handler

Convex and concave nonlinear handlers

SOC nonlinear handler

Function Documentation

◆ SCIPgetExprsBilinear()

◆ SCIPgetExprsdataBilinear()

◆ SCIPgetNExprsBilinear()

◆ SCIPaddIneqBilinear()

◆ SCIPaddBilinLinearization()

◆ SCIPaddBilinMcCormick()

◆ SCIPcomputeBilinEnvelope1()

◆ SCIPcomputeBilinEnvelope2()

◆ SCIPhasExprCurvature()

◆ SCIPisSOCNonlinear()

◆ SCIPfreeSOCArraysNonlinear()