Scippy

SCIP

Solving Constraint Integer Programs

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
nlhdlrnonlinear handler

Definition at line 1518 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
nlhdlrnonlinear handler

◆ SCIPgetNExprsBilinear()

int SCIPgetNExprsBilinear ( SCIP_NLHDLR nlhdlr)

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

Parameters
nlhdlrnonlinear handler

Definition at line 1534 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
scipSCIP data structure
nlhdlrnonlinear handler
exprproduct expression
xcoefx coefficient
ycoefy coefficient
constantconstant part
successbuffer to store whether inequality has been accepted

Definition at line 1550 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
scipSCIP data structure
bilincoefcoefficient of bilinear term
refpointxpoint where to linearize first variable
refpointypoint where to linearize second variable
lincoefxbuffer to add coefficient of first variable in linearization
lincoefybuffer to add coefficient of second variable in linearization
linconstantbuffer to add constant of linearization
successbuffer to set to FALSE if linearization has failed due to large numbers

Definition at line 1705 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
scipSCIP data structure
bilincoefcoefficient of bilinear term
lbxlower bound on first variable
ubxupper bound on first variable
refpointxreference point for first variable
lbylower bound on second variable
ubyupper bound on second variable
refpointyreference point for second variable
overestimatewhether to compute an overestimator instead of an underestimator
lincoefxbuffer to add coefficient of first variable in linearization
lincoefybuffer to add coefficient of second variable in linearization
linconstantbuffer to add constant of linearization
successbuffer to set to FALSE if linearization has failed due to large numbers

Definition at line 1752 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
scipSCIP data structure
bilincoefcoefficient of bilinear term
lbxlower bound on first variable
ubxupper bound on first variable
refpointxreference point for first variable
lbylower bound on second variable
ubyupper bound on second variable
refpointyreference point for second variable
overestimatewhether to compute an overestimator instead of an underestimator
xcoefx coefficient of linear inequality; must be in {-1,0,1}
ycoefy coefficient of linear inequality
constantconstant of linear inequality
lincoefxbuffer to store coefficient of first variable in linearization
lincoefybuffer to store coefficient of second variable in linearization
linconstantbuffer to store constant of linearization
successbuffer to store whether linearization was successful

Definition at line 1960 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
scipSCIP data structure
bilincoefcoefficient of bilinear term
lbxlower bound on first variable
ubxupper bound on first variable
refpointxreference point for first variable
lbylower bound on second variable
ubyupper bound on second variable
refpointyreference point for second variable
overestimatewhether to compute an overestimator instead of an underestimator
xcoef1x coefficient of linear inequality; must be in {-1,0,1}
ycoef1y coefficient of linear inequality
constant1constant of linear inequality
xcoef2x coefficient of linear inequality; must be in {-1,0,1}
ycoef2y coefficient of linear inequality
constant2constant of linear inequality
lincoefxbuffer to store coefficient of first variable in linearization
lincoefybuffer to store coefficient of second variable in linearization
linconstantbuffer to store constant of linearization
successbuffer to store whether linearization was successful

Definition at line 2184 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
scipSCIP data structure
exprexpression
curvcurvature to check for
successbuffer to store whether expression has curvature curv (w.r.t. original variables)
assumevarfixedhashmap containing variables that should be assumed to be fixed, or NULL

Definition at line 2448 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
scipSCIP data structure
consnonlinear constraint
compeigenvalueswhether eigenvalues should be computed to detect complex cases
successpointer to store whether SOC structure has been detected
sidetypepointer to store which side of cons is SOC representable; only valid when success is TRUE
varsvariables (x) that appear on both sides; no duplicates are allowed
offsetsoffsets of both sides (beta_i)
transcoefsnon-zeros of linear transformation vectors (v_i)
transcoefsidxmapping of transformation coefficients to variable indices in vars
termbeginsstarting indices of transcoefs for each term
nvarstotal number of variables appearing (i.e. size of vars)
ntermsnumber of summands in the SQRT +1 for RHS (n+1)

Definition at line 2724 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
scipSCIP data structure
varsvariables that appear on both sides (x)
offsetsoffsets of both sides (beta_i)
transcoefsnon-zeros of linear transformation vectors (v_i)
transcoefsidxmapping of transformation coefficients to variable indices in vars
termbeginsstarting indices of transcoefs for each term
nvarstotal number of variables appearing
ntermsnumber of summands in the SQRT +1 for RHS (n+1)

Definition at line 2814 of file nlhdlr_soc.c.

References nterms, NULL, and SCIPfreeBlockMemoryArray.