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) |
#define NLHDLR_NAME "quotient" |
Definition at line 44 of file nlhdlr_quotient.c.
#define NLHDLR_DESC "nonlinear handler for quotient expressions" |
Definition at line 45 of file nlhdlr_quotient.c.
#define NLHDLR_DETECTPRIORITY 20 |
Definition at line 46 of file nlhdlr_quotient.c.
#define NLHDLR_ENFOPRIORITY 20 |
Definition at line 47 of file nlhdlr_quotient.c.
#define infty2infty | ( | 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().
|
static |
helper method to create nonlinear handler expression data
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 assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPcaptureExpr(), and SCIPisZero().
Referenced by detectExpr().
|
static |
helper method to free nonlinear handler expression data
scip | SCIP data structure |
nlhdlrexprdata | nonlinear handler expression data |
Definition at line 118 of file nlhdlr_quotient.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPreleaseExpr().
Referenced by SCIP_DECL_NLHDLRFREEEXPRDATA().
|
static |
helper method to transform an expression g(x) into a*f(x) + b
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 assert(), NULL, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), and SCIPisExprSum().
Referenced by 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:
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, assert(), b, c, exprdataCreate(), FALSE, NULL, SCIP_Bool, 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().
|
static |
helper method to compute interval for (a x + b) / (c x + d) + e
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 a, assert(), b, c, i, SCIP_Interval::inf, NULL, REALABS, result, 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().
|
static |
helper method to compute reverse propagation for (a x + b) / (c x + d) + e
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 a, b, c, i, SCIP_Interval::inf, result, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPintervalAddScalar(), SCIPintervalDiv(), SCIPintervalIsEmpty(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetEmpty(), SCIPintervalSetEntire(), SCIPintervalSubScalar(), SCIPintervalUnify(), and SCIP_Interval::sup.
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
|
static |
adds data to given rowprep; the generated estimator is always locally valid
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 assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerms(), SCIPensureRowprepSize(), SCIProwprepAddSide(), and vars.
Referenced by estimateBivariateQuotient(), and estimateUnivariateQuotient().
|
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:
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 a, assert(), b, c, FALSE, NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisHugeValue(), SCIPisInfinity(), SCIPisLE(), SQR, and TRUE.
Referenced by estimateUnivariateQuotient(), and SCIP_DECL_NLHDLRSOLLINEARIZE().
|
static |
helper method to compute estimator for the univariate case; the estimator is stored in a given rowprep
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 a, assert(), b, c, createRowprep(), estimateUnivariate(), FALSE, SCIP_Interval::inf, infty2infty, MAX, MIN, 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(), sol, SCIP_Interval::sup, and x.
Referenced by SCIP_DECL_NLHDLRESTIMATE().
|
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.
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 assert(), NULL, SCIP_Real, and SQR.
Referenced by 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:
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.
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 assert(), FALSE, hcGradCut(), NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPaddBilinMcCormick(), SCIPisGE(), SCIPisHugeValue(), SCIPisLE(), and TRUE.
Referenced by 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.
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, assert(), b, c, createRowprep(), estimateBivariate(), FALSE, SCIP_Interval::inf, infty2infty, MAX, MIN, 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(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), sol, SCIP_Interval::sup, and vars.
Referenced by SCIP_DECL_NLHDLRESTIMATE().
|
static |
nonlinear handler copy callback
Definition at line 1031 of file nlhdlr_quotient.c.
References assert(), NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrQuotient(), and SCIPnlhdlrGetName().
|
static |
callback to free expression specific data
Definition at line 1045 of file nlhdlr_quotient.c.
References assert(), exprdataFree(), NULL, SCIP_CALL, and SCIP_OKAY.
|
static |
callback to detect structure in expression tree
Definition at line 1059 of file nlhdlr_quotient.c.
References assert(), detectExpr(), NULL, SCIP_Bool, SCIP_CALL, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, and SCIPgetExprNAuxvarUsesNonlinear().
|
static |
auxiliary evaluation callback of nonlinear handler
! [SnippetNlhdlrEvalauxQuotient]
! [SnippetNlhdlrEvalauxQuotient]
Definition at line 1089 of file nlhdlr_quotient.c.
References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), and sol.
|
static |
nonlinear handler under/overestimation callback
![SnippetNlhdlrEstimateQuotient]
![SnippetNlhdlrEstimateQuotient]
Definition at line 1129 of file nlhdlr_quotient.c.
References assert(), 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(), sol, and TRUE.
|
static |
nonlinear handler solution linearization callback
Definition at line 1200 of file nlhdlr_quotient.c.
References assert(), c, estimateUnivariate(), FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPaddPoolCut(), SCIPaddRowprepTerm(), SCIPcleanupRowprep2(), SCIPcreateRowprep(), SCIPfreeRowprep(), SCIPgetExprAuxVarNonlinear(), SCIPgetHugeValue(), SCIPgetRowprepRowCons(), SCIPgetSolVal(), SCIPreleaseRow(), SCIProwprepAddConstant(), SCIProwprepGetName(), SCIProwprepIsLocal(), SCIPsnprintf(), SCIPsolGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), sol, TRUE, and x.
|
static |
nonlinear handler interval evaluation callback
! [SnippetNlhdlrIntevalQuotient]
! [SnippetNlhdlrIntevalQuotient]
Definition at line 1266 of file nlhdlr_quotient.c.
References assert(), intEvalQuotient(), NULL, SCIP_OKAY, and SCIPexprGetActivity().
|
static |
nonlinear handler callback for reverse propagation
! [SnippetNlhdlrReversepropQuotient]
! [SnippetNlhdlrReversepropQuotient]
Definition at line 1294 of file nlhdlr_quotient.c.
References assert(), NULL, result, reversepropQuotient(), SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetExprBoundsNonlinear(), and SCIPtightenExprIntervalNonlinear().