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 2466 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.