SCIP
Solving Constraint Integer Programs
nlhdlr_quotient.c File Reference
Detailed Description
quotient nonlinear handler
Definition in file nlhdlr_quotient.c.
#include <string.h>#include "scip/nlhdlr_quotient.h"#include "scip/cons_nonlinear.h"#include "scip/pub_misc_rowprep.h"#include "scip/nlhdlr.h"#include "scip/nlhdlr_bilinear.h"Go to the source code of this file.
Macros | |
| #define | NLHDLR_NAME "quotient" |
| #define | NLHDLR_DESC "nonlinear handler for quotient expressions" |
| #define | NLHDLR_DETECTPRIORITY 20 |
| #define | NLHDLR_ENFOPRIORITY 20 |
| #define | infty2infty(infty1, infty2, val) ((val) >= (infty1) ? (infty2) : (val)) |
Macro Definition Documentation
◆ NLHDLR_NAME
| #define NLHDLR_NAME "quotient" |
Definition at line 44 of file nlhdlr_quotient.c.
Referenced by SCIP_DECL_NLHDLRCOPYHDLR(), and SCIPincludeNlhdlrQuotient().
◆ NLHDLR_DESC
| #define NLHDLR_DESC "nonlinear handler for quotient expressions" |
Definition at line 45 of file nlhdlr_quotient.c.
Referenced by SCIPincludeNlhdlrQuotient().
◆ NLHDLR_DETECTPRIORITY
| #define NLHDLR_DETECTPRIORITY 20 |
Definition at line 46 of file nlhdlr_quotient.c.
Referenced by SCIPincludeNlhdlrQuotient().
◆ NLHDLR_ENFOPRIORITY
| #define NLHDLR_ENFOPRIORITY 20 |
Definition at line 47 of file nlhdlr_quotient.c.
Referenced by SCIPincludeNlhdlrQuotient().
◆ infty2infty
| #define infty2infty | ( | infty1, | |
| infty2, | |||
| val | |||
| ) | ((val) >= (infty1) ? (infty2) : (val)) |
translate from one value of infinity to another
if val is ≥ infty1, then give infty2, else give val
Definition at line 53 of file nlhdlr_quotient.c.
Referenced by estimateBivariateQuotient(), and estimateUnivariateQuotient().
Function Documentation
◆ exprdataCreate()
|
static |
helper method to create nonlinear handler expression data
- Parameters
-
scip SCIP data structure nlhdlrexprdata nonlinear handler expression data numexpr expression of the numerator numcoef coefficient of the numerator numconst constant of the numerator denomexpr expression of the denominator denomcoef coefficient of the denominator denomconst constant of the denominator constant constant
Definition at line 79 of file nlhdlr_quotient.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPcaptureExpr(), and SCIPisZero().
Referenced by detectExpr().
◆ exprdataFree()
|
static |
helper method to free nonlinear handler expression data
- Parameters
-
scip SCIP data structure nlhdlrexprdata nonlinear handler expression data
Definition at line 118 of file nlhdlr_quotient.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPreleaseExpr().
Referenced by SCIP_DECL_NLHDLRFREEEXPRDATA().
◆ transformExpr()
|
static |
helper method to transform an expression g(x) into a*f(x) + b
- Parameters
-
scip SCIP data structure expr expression target pointer to store the expression f(x) coef pointer to store the coefficient constant pointer to store the constant
Definition at line 140 of file nlhdlr_quotient.c.
References NULL, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), and SCIPisExprSum().
Referenced by detectExpr().
◆ detectExpr()
|
static |
helper method to detect an expression of the form (a*x + b) / (c*y + d) + e
Due to the expansion of products, there are two types of expressions that can be detected:
- prod(f(x), pow(g(y),-1))
- sum(prod(f(x),pow(g(y),-1)), pow(g(y),-1))
- Parameters
-
scip SCIP data structure expr expression nlhdlrexprdata pointer to store nonlinear handler expression data success pointer to store whether nonlinear handler should be called for this expression
Definition at line 179 of file nlhdlr_quotient.c.
References a, b, exprdataCreate(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetExponentExprPow(), SCIPgetExprNAuxvarUsesNonlinear(), SCIPinfoMessage(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprSum(), SCIPprintExpr(), SCIPregisterExprUsageNonlinear(), transformExpr(), and TRUE.
Referenced by SCIP_DECL_NLHDLRDETECT().
◆ intEvalQuotient()
|
static |
helper method to compute interval for (a x + b) / (c x + d) + e
- Parameters
-
scip SCIP data structure bnds bounds on x a coefficient in numerator b constant in numerator c coefficient in denominator d constant in denominator e constant
Definition at line 354 of file nlhdlr_quotient.c.
References SCIP_Interval::inf, NULL, REALABS, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPintervalAddScalar(), SCIPintervalDiv(), SCIPintervalDivScalar(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetEmpty(), SCIPintervalSetEntire(), SCIPintervalUnify(), SCIPisInfinity(), and SCIP_Interval::sup.
Referenced by SCIP_DECL_NLHDLRINTEVAL().
◆ reversepropQuotient()
|
static |
helper method to compute reverse propagation for (a x + b) / (c x + d) + e
- Parameters
-
bnds bounds on (a x + b) / (c x + d) + e a coefficient in numerator b constant in numerator c coefficient in denominator d constant in denominator e constant
Definition at line 438 of file nlhdlr_quotient.c.
References SCIP_Interval::inf, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPintervalAddScalar(), SCIPintervalDiv(), SCIPintervalIsEmpty(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetEmpty(), SCIPintervalSetEntire(), SCIPintervalSubScalar(), SCIPintervalUnify(), and SCIP_Interval::sup.
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
◆ createRowprep()
|
static |
adds data to given rowprep; the generated estimator is always locally valid
- Note
- the constant is moved to the left- or right-hand side
- other than the name of this function may indicate, it does not create a rowprep
- Parameters
-
scip SCIP data structure rowprep a rowprep where to store the estimator vars variables coefs coefficients constant constant nlinvars total number of variables
Definition at line 500 of file nlhdlr_quotient.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPaddRowprepTerms(), SCIPensureRowprepSize(), and SCIProwprepAddSide().
Referenced by estimateBivariateQuotient(), and estimateUnivariateQuotient().
◆ estimateUnivariate()
|
static |
computes an estimator at a given point for the univariate case (ax + b) / (cx + d) + e
Depending on the reference point, the estimator is a tangent or a secant on the graph. It depends on whether we are under- or overestimating, whether we are on the left or on the right side of the singularity at -d/c, and whether it is the monotone increasing (ad - bc > 0) or decreasing part (ad - bc < 0). Together, there are 8 cases:
- mon. incr. + overestimate + left hand side –> secant
- mon. incr. + overestimate + right hand side –> tangent
- mon. incr. + understimate + left hand side –> tangent
- mon. incr. + understimate + right hand side –> secant
- mon. decr. + overestimate + left hand side –> tangent
- mon. decr. + overestimate + right hand side –> secant
- mon. decr. + understimate + left hand side –> secant
- mon. decr. + understimate + right hand side –> tangent
- Parameters
-
scip SCIP data structure lbx local lower bound of x ubx local upper bound of x gllbx global lower bound of x glubx global upper bound of x solx solution value of x a coefficient in numerator b constant in numerator c coefficient in denominator d constant in denominator e constant coef pointer to store the coefficient constant pointer to store the constant overestimate whether the expression should be overestimated local pointer to store whether the estimate is locally valid branchinguseful pointer to store whether branching on the expression would improve the estimator success buffer to store whether separation was successful
Definition at line 541 of file nlhdlr_quotient.c.
References b, FALSE, NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisHugeValue(), SCIPisInfinity(), SCIPisLE(), and TRUE.
Referenced by estimateUnivariateQuotient().
◆ estimateUnivariateQuotient()
|
static |
helper method to compute estimator for the univariate case; the estimator is stored in a given rowprep
- Parameters
-
scip SCIP data structure sol solution point (or NULL for the LP solution) xexpr argument expression a coefficient in numerator b constant in numerator c coefficient in denominator d constant in denominator e constant overestimate whether the expression should be overestimated rowprep a rowprep where to store the estimator branchinguseful pointer to store whether branching on the expression would improve the estimator success buffer to store whether separation was successful
Definition at line 633 of file nlhdlr_quotient.c.
References createRowprep(), estimateUnivariate(), FALSE, SCIP_Interval::inf, infty2infty, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPepsilon(), SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPgetExprAuxVarNonlinear(), SCIPgetNLPs(), SCIPgetSolVal(), SCIPinfinity(), SCIPintervalIntersectEps(), SCIPintervalSetBounds(), SCIPisEQ(), SCIProwprepGetName(), SCIProwprepSetLocal(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIP_Interval::sup, and x.
Referenced by SCIP_DECL_NLHDLRESTIMATE().
◆ hcGradCut()
|
static |
helper method to compute a gradient cut for
\[ h^c(x,y) := \frac{1}{y} \left(\frac{x + \sqrt{\text{lbx}\cdot\text{ubx}}}{\sqrt{\text{lbx}} + \sqrt{\text{ubx}}}\right)^2 \]
at a given reference point
See Zamora and Grossmann (1988) for more details.
- Parameters
-
lbx lower bound of x ubx upper bound of x solx solution value of x soly solution value of y coefx pointer to store the coefficient of x coefy pointer to store the coefficient of y constant pointer to store the constant
Definition at line 712 of file nlhdlr_quotient.c.
References NULL, and SCIP_Real.
Referenced by estimateBivariate().
◆ estimateBivariate()
|
static |
computes an over- or underestimator at a given point for the bivariate case x/y ≤/≥ z
There are the following cases for y > 0:
- lbx < 0 < ubx: Rewrite x / y = z as x = y * z and use McCormick to compute a valid inequality of the form x = y * z ≤ a * y + b * z + c. Note that b > 0 because of y > 0. The inequality is then transformed to x / b - a/b * y - c/b ≤ z, which results in a valid underestimator for x / y over the set {(x,y) | lbz ≤ x / y ≤ ubz}. Note that overestimating/underestimating the bilinear term with McCormick results in an underestimator/overestimator for x / y.
- lbx ≥ 0 or ubx ≤ 0:
- overestimation: use \(z \leq \frac{1}{\text{lby}\cdot\text{uby}} \min(\text{uby}\cdot x - \text{lbx}\cdot y + \text{lbx}\cdot\text{lby}, \text{lby}\cdot x - \text{ubx}\cdot y + \text{ubx}\cdot\text{uby})\)
- underestimation: use \(z \geq x/y \geq \frac{1}{y} \frac{x + \sqrt{\text{lbx}\cdot\text{ubx}}}{\sqrt{\text{lbx} + \sqrt{\text{ubx}}}}\) and build gradient cut
If y < 0, swap and negate its bounds and compute the respective opposite estimator (and negate it).
If 0 is in the interval of y, nothing is possible.
- Parameters
-
scip SCIP data structure lbx lower bound of x ubx upper bound of x lby lower bound of y uby upper bound of y lbz lower bound of z ubz lower bound of z solx reference point for x soly reference point for y solz reference point for z overestimate whether the expression should be overestimated coefx pointer to store the x coefficient coefy pointer to store the y coefficient constant pointer to store the constant branchingusefulx pointer to store whether branching on x would improve the estimator branchingusefuly pointer to store whether branching on y would improve the estimator success buffer to store whether computing the estimator was successful
Definition at line 761 of file nlhdlr_quotient.c.
References FALSE, hcGradCut(), NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPaddBilinMcCormick(), SCIPisGE(), SCIPisHugeValue(), SCIPisLE(), and TRUE.
Referenced by estimateBivariateQuotient().
◆ estimateBivariateQuotient()
|
static |
construct an estimator for a quotient expression of the form (ax + b) / (cy + d) + e
The resulting estimator is stored in a rowprep.
The method first computes an estimator for x' / y' with x := ax + b and y := cy + d and then transforms this estimator to one for the quotient (ax + b) / (cy + d) + e.
- Parameters
-
scip SCIP data structure xexpr numerator expression yexpr denominator expression auxvar auxiliary variable sol solution point (or NULL for the LP solution) a coefficient of numerator b constant of numerator c coefficient of denominator d constant of denominator e constant term overestimate whether the expression should be overestimated rowprep a rowprep where to store the estimator branchingusefulx pointer to store whether branching on x would improve the estimator branchingusefuly pointer to store whether branching on y would improve the estimator success buffer to store whether separation was successful
Definition at line 920 of file nlhdlr_quotient.c.
References a, createRowprep(), estimateBivariate(), FALSE, SCIP_Interval::inf, infty2infty, MAX, NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPepsilon(), SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPgetExprAuxVarNonlinear(), SCIPgetNLPs(), SCIPgetSolVal(), SCIPinfinity(), SCIPintervalIntersectEps(), SCIPintervalSetBounds(), SCIPisEQ(), SCIProwprepGetName(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and SCIP_Interval::sup.
Referenced by SCIP_DECL_NLHDLRESTIMATE().
◆ SCIP_DECL_NLHDLRCOPYHDLR()
|
static |
nonlinear handler copy callback
Definition at line 1031 of file nlhdlr_quotient.c.
References NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrQuotient(), and SCIPnlhdlrGetName().
◆ SCIP_DECL_NLHDLRFREEEXPRDATA()
|
static |
callback to free expression specific data
Definition at line 1045 of file nlhdlr_quotient.c.
References exprdataFree(), NULL, SCIP_CALL, and SCIP_OKAY.
◆ SCIP_DECL_NLHDLRDETECT()
|
static |
callback to detect structure in expression tree
Definition at line 1059 of file nlhdlr_quotient.c.
References detectExpr(), NULL, SCIP_Bool, SCIP_CALL, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, and SCIPgetExprNAuxvarUsesNonlinear().
◆ SCIP_DECL_NLHDLREVALAUX()
|
static |
auxiliary evaluation callback of nonlinear handler
! [SnippetNlhdlrEvalauxQuotient]
! [SnippetNlhdlrEvalauxQuotient]
Definition at line 1089 of file nlhdlr_quotient.c.
References NULL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPgetExprAuxVarNonlinear(), and SCIPgetSolVal().
◆ SCIP_DECL_NLHDLRESTIMATE()
|
static |
nonlinear handler under/overestimation callback
![SnippetNlhdlrEstimateQuotient]
![SnippetNlhdlrEstimateQuotient]
Definition at line 1129 of file nlhdlr_quotient.c.
References estimateBivariateQuotient(), estimateUnivariateQuotient(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPaddExprsViolScoreNonlinear(), SCIPcreateRowprep(), SCIPfreeRowprep(), SCIPgetExprAbsAuxViolationNonlinear(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprRelAuxViolationNonlinear(), SCIPsetPtrarrayVal(), and TRUE.
◆ SCIP_DECL_NLHDLRINTEVAL()
|
static |
nonlinear handler interval evaluation callback
! [SnippetNlhdlrIntevalQuotient]
! [SnippetNlhdlrIntevalQuotient]
Definition at line 1201 of file nlhdlr_quotient.c.
References intEvalQuotient(), NULL, SCIP_OKAY, and SCIPexprGetActivity().
◆ SCIP_DECL_NLHDLRREVERSEPROP()
|
static |
nonlinear handler callback for reverse propagation
! [SnippetNlhdlrReversepropQuotient]
! [SnippetNlhdlrReversepropQuotient]
Definition at line 1229 of file nlhdlr_quotient.c.
References SCIP_Interval::inf, NULL, reversepropQuotient(), SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetExprBoundsNonlinear(), SCIPtightenExprIntervalNonlinear(), and SCIP_Interval::sup.