handler for sine and cosine expressions
The estimator/separator code always computes underestimators for sin(x). For overestimators of cos(x), we first reduce to underestimators of sin(x).
Overestimator for sin(x): Assume that a*y+b <= sin(y) for y in [-ub,-lb]. Then we have a*(-y)-b >= -sin(y) = sin(-y) for y in [-ub,-lb]. Thus, a*x-b >= sin(x) for x in [lb,ub].
Underestimator for cos(x): Assume that a*y+b <= sin(y) for y in [lb+pi/2,ub+pi/2]. Then we have a*(x+pi/2) + b <= sin(x+pi/2) = cos(x) for x in [lb,ub]. Thus, a*x + (b+a*pi/2) <= cos(x) for x in [lb,ub].
Overestimator for cos(x): Assume that a*z+b <= sin(z) for z in [-(ub+pi/2),-(lb+pi/2)]. Then, a*y-b >= sin(y) for y in [lb+pi/2,ub+pi/2]. Then, a*x-b+a*pi/2 >= cos(x) for x in [lb,ub].
Definition in file expr_trig.c.
Go to the source code of this file.
Macros | |
#define | SINEXPRHDLR_NAME "sin" |
#define | SINEXPRHDLR_DESC "sine expression" |
#define | SINEXPRHDLR_PRECEDENCE 91000 |
#define | SINEXPRHDLR_HASHKEY SCIPcalcFibHash(82457.0) |
#define | COSEXPRHDLR_NAME "cos" |
#define | COSEXPRHDLR_DESC "cosine expression" |
#define | COSEXPRHDLR_PRECEDENCE 92000 |
#define | COSEXPRHDLR_HASHKEY SCIPcalcFibHash(82463.0) |
#define | MAXCHILDABSVAL 1e+6 |
#define | NEWTON_NITERATIONS 100 |
#define | NEWTON_PRECISION 1e-12 |
#define SINEXPRHDLR_NAME "sin" |
Definition at line 59 of file expr_trig.c.
Referenced by SCIP_DECL_EXPRESTIMATE(), SCIPcreateExprSin(), SCIPincludeExprhdlrSin(), and SCIPisExprSin().
#define SINEXPRHDLR_DESC "sine expression" |
Definition at line 60 of file expr_trig.c.
Referenced by SCIPincludeExprhdlrSin().
#define SINEXPRHDLR_PRECEDENCE 91000 |
Definition at line 61 of file expr_trig.c.
Referenced by SCIPincludeExprhdlrSin().
#define SINEXPRHDLR_HASHKEY SCIPcalcFibHash(82457.0) |
Definition at line 62 of file expr_trig.c.
Referenced by SCIP_DECL_EXPRHASH().
#define COSEXPRHDLR_NAME "cos" |
Definition at line 64 of file expr_trig.c.
Referenced by SCIP_DECL_EXPRESTIMATE(), SCIPcreateExprCos(), SCIPincludeExprhdlrCos(), and SCIPisExprCos().
#define COSEXPRHDLR_DESC "cosine expression" |
Definition at line 65 of file expr_trig.c.
Referenced by SCIPincludeExprhdlrCos().
#define COSEXPRHDLR_PRECEDENCE 92000 |
Definition at line 66 of file expr_trig.c.
Referenced by SCIPincludeExprhdlrCos().
#define COSEXPRHDLR_HASHKEY SCIPcalcFibHash(82463.0) |
Definition at line 67 of file expr_trig.c.
Referenced by SCIP_DECL_EXPRHASH().
#define MAXCHILDABSVAL 1e+6 |
maximum absolute value that is accepted for propagation
Definition at line 69 of file expr_trig.c.
Referenced by computeRevPropIntervalSin().
#define NEWTON_NITERATIONS 100 |
Definition at line 70 of file expr_trig.c.
Referenced by computeLeftSecantSin(), computeRightSecantSin(), and computeSolTangentSin().
#define NEWTON_PRECISION 1e-12 |
Definition at line 71 of file expr_trig.c.
Referenced by computeLeftSecantSin(), computeRightSecantSin(), and computeSolTangentSin().
|
static |
evaluates the function a*x + b - sin(x) for some coefficient a and constant b at a given point p
the constants a and b are expected to be stored in that order in params
Definition at line 82 of file expr_trig.c.
|
static |
evaluates the derivative of a*x + b - sin(x) for some coefficient a and constant b at a given point p
the constants a and b are expected to be stored in that order in params
Definition at line 95 of file expr_trig.c.
|
static |
evaluates the function sin(x) + (alpha - x)*cos(x) - sin(alpha) for some constant alpha at a given point p
the constant alpha is expected to be stored in params
Definition at line 108 of file expr_trig.c.
|
static |
evaluates the derivative of sin(x) + (alpha - x)*cos(x) - sin(alpha) for some constant alpha at a given point p
the constant alpha is expected to be stored in params
Definition at line 121 of file expr_trig.c.
|
static |
helper function to compute the secant if it is a valid underestimator
returns true if the estimator was computed successfully
scip | SCIP data structure |
lincoef | buffer to store linear coefficient of secant |
linconst | buffer to store linear constant of secant |
lb | lower bound of argument variable |
ub | upper bound of argument variable |
Definition at line 134 of file expr_trig.c.
References assert(), FALSE, M_PI, NULL, SCIP_Bool, SCIP_Real, and TRUE.
Referenced by computeEstimatorsTrig(), and computeInitialCutsTrig().
|
static |
helper function to compute the tangent at lower bound if it is underestimating
returns true if the underestimator was computed successfully
scip | SCIP data structure |
lincoef | buffer to store linear coefficient of tangent |
linconst | buffer to store linear constant of tangent |
lb | lower bound of argument variable |
Definition at line 166 of file expr_trig.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPisInfinity(), and TRUE.
Referenced by computeInitialCutsTrig().
|
static |
helper function to compute the tangent at upper bound if it is an underestimator
returns true if the underestimator was computed successfully
scip | SCIP data structure |
lincoef | buffer to store linear coefficient of tangent |
linconst | buffer to store linear constant of tangent |
ub | upper bound of argument variable |
Definition at line 199 of file expr_trig.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPisInfinity(), and TRUE.
Referenced by computeInitialCutsTrig().
|
static |
helper function to compute the tangent at solution point if it is an underestimator
returns true if the underestimator was computed successfully
scip | SCIP data structure |
lincoef | buffer to store linear coefficient of tangent |
linconst | buffer to store linear constant of tangent |
lb | lower bound of argument variable |
ub | upper bound of argument variable |
solpoint | solution point to be separated |
Definition at line 228 of file expr_trig.c.
References assert(), FALSE, i, M_PI, NEWTON_NITERATIONS, NEWTON_PRECISION, NULL, SCIP_Bool, SCIP_INVALID, SCIP_Real, SCIPcalcRootNewton(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisZero(), and TRUE.
Referenced by computeEstimatorsTrig().
|
static |
helper function to compute the secant between lower bound and some point of the graph such that it underestimates
returns true if the underestimator was computed successfully
scip | SCIP data structure |
lincoef | buffer to store linear coefficient of tangent |
linconst | buffer to store linear constant of tangent |
lb | lower bound of argument variable |
ub | upper bound of argument variable |
Definition at line 303 of file expr_trig.c.
References assert(), FALSE, M_PI, NEWTON_NITERATIONS, NEWTON_PRECISION, NULL, SCIP_Bool, SCIP_INVALID, SCIP_Real, SCIPcalcRootNewton(), SCIPdebugMsg, SCIPisEQ(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), and TRUE.
Referenced by computeEstimatorsTrig(), and computeInitialCutsTrig().
|
static |
helper function to compute the secant between upper bound and some point of the graph such that it underestimates
returns true if the underestimator was computed successfully
scip | SCIP data structure |
lincoef | buffer to store linear coefficient of tangent |
linconst | buffer to store linear constant of tangent |
lb | lower bound of argument variable |
ub | upper bound of argument variable |
Definition at line 390 of file expr_trig.c.
References assert(), FALSE, M_PI, NEWTON_NITERATIONS, NEWTON_PRECISION, NULL, SCIP_Bool, SCIP_INVALID, SCIP_Real, SCIPcalcRootNewton(), SCIPisEQ(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), and TRUE.
Referenced by computeEstimatorsTrig(), and computeInitialCutsTrig().
|
static |
helper function to compute the new interval for child in reverse propagation
scip | SCIP data structure |
parentbounds | bounds for sine expression |
childbounds | bounds for child expression |
newbounds | buffer to store new child bounds |
Definition at line 472 of file expr_trig.c.
References a, ABS, assert(), SCIP_Interval::inf, M_PI, MAXCHILDABSVAL, SCIP_OKAY, SCIP_Real, SCIPintervalSetBounds(), SCIPintervalSetEmpty(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), and SCIP_Interval::sup.
Referenced by SCIP_DECL_EXPRREVERSEPROP(), and SCIP_DECL_EXPRREVERSEPROP().
|
static |
helper function to compute coefficients and constant term of a linear estimator at a given point
The function will try to compute the following estimators in that order:
They are ordered such that a successful computation for one of them cannot be improved by following ones in terms of value at the reference point.
scip | SCIP data structure |
expr | sin or cos expression |
lincoef | buffer to store the linear coefficient |
linconst | buffer to store the constant term |
refpoint | point at which to underestimate (can be SCIP_INVALID) |
childlb | lower bound of child variable |
childub | upper bound of child variable |
underestimate | whether the estimator should be underestimating |
Definition at line 568 of file expr_trig.c.
References assert(), computeLeftSecantSin(), computeRightSecantSin(), computeSecantSin(), computeSolTangentSin(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), SCIPisEQ(), SCIPisLE(), and TRUE.
Referenced by SCIP_DECL_EXPRESTIMATE(), and SCIP_DECL_EXPRESTIMATE().
|
static |
helper function to create initial cuts for sine and cosine separation
The following 5 cuts can be generated:
scip | SCIP data structure |
expr | sin or cos expression |
childlb | lower bound of child variable |
childub | upper bound of child variable |
underestimate | whether the cuts should be underestimating |
coefs | buffer to store coefficients of computed estimators |
constant | buffer to store constant of computed estimators |
nreturned | buffer to store number of estimators that have been computed |
Definition at line 648 of file expr_trig.c.
References assert(), computeLeftSecantSin(), computeLeftTangentSin(), computeRightSecantSin(), computeRightTangentSin(), computeSecantSin(), i, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), SCIPisEQ(), and SCIPisLE().
Referenced by SCIP_DECL_EXPRINITESTIMATES(), and SCIP_DECL_EXPRINITESTIMATES().
|
static |
childcurvature | curvature of child |
lb | lower bound of child |
ub | upper bound of child |
Definition at line 733 of file expr_trig.c.
References M_PI, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_EXPRCURV_UNKNOWN, and SCIP_Real.
Referenced by SCIP_DECL_EXPRCURVATURE(), and SCIP_DECL_EXPRCURVATURE().
|
static |
expression handler copy callback
Definition at line 788 of file expr_trig.c.
References SCIP_CALL, SCIP_OKAY, and SCIPincludeExprhdlrSin().
|
static |
simplifies a sine expression
Evaluates the sine value function when its child is a value expression.
TODO: add further simplifications
Definition at line 802 of file expr_trig.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcaptureExpr(), SCIPcreateExprValue(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetValueExprValue(), and SCIPisExprValue().
|
static |
expression parse callback
Definition at line 833 of file expr_trig.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateExprSin(), SCIPparseExpr(), SCIPreleaseExpr(), and TRUE.
|
static |
expression (point-) evaluation callback
Definition at line 857 of file expr_trig.c.
References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetEvalValue(), and SCIPexprGetNChildren().
|
static |
expression derivative evaluation callback
Definition at line 870 of file expr_trig.c.
References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetEvalValue(), SCIPexprGetHdlr(), and SCIPexprhdlrGetName().
|
static |
derivative evaluation callback
Computes <gradient, children.dot>, that is, cos(child) dot(child).
Definition at line 892 of file expr_trig.c.
References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetDot(), SCIPexprGetEvalValue(), SCIPexprGetHdlr(), and SCIPexprhdlrGetName().
|
static |
expression backward forward derivative evaluation callback
Computes partial/partial child ( <gradient, children.dot> ), that is, -sin(child) dot(child).
Definition at line 914 of file expr_trig.c.
References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetDot(), SCIPexprGetEvalValue(), SCIPexprGetHdlr(), and SCIPexprhdlrGetName().
|
static |
expression interval evaluation callback
Definition at line 934 of file expr_trig.c.
References assert(), NULL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPintervalIsEmpty(), SCIPintervalSetEmpty(), and SCIPintervalSin().
|
static |
separation initialization callback
Definition at line 953 of file expr_trig.c.
References computeInitialCutsTrig(), SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPisRelEQ().
|
static |
expression estimator callback
Definition at line 973 of file expr_trig.c.
References assert(), computeEstimatorsTrig(), NULL, SCIP_OKAY, SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), SINEXPRHDLR_NAME, and TRUE.
|
static |
expression reverse propagation callback
Definition at line 995 of file expr_trig.c.
References assert(), computeRevPropIntervalSin(), NULL, SCIP_CALL, SCIP_OKAY, SCIPexprGetNChildren(), SCIPintervalGetInf(), and SCIPintervalGetSup().
|
static |
sine hash callback
Definition at line 1011 of file expr_trig.c.
References assert(), NULL, SCIP_OKAY, SCIPexprGetNChildren(), and SINEXPRHDLR_HASHKEY.
|
static |
expression curvature detection callback
Definition at line 1027 of file expr_trig.c.
References assert(), computeCurvatureSin(), FALSE, SCIP_Interval::inf, NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIP_Interval::sup, and TRUE.
|
static |
expression monotonicity detection callback
Definition at line 1059 of file expr_trig.c.
References assert(), M_PI, NULL, result, SCIP_CALL, SCIP_MONOTONE_DEC, SCIP_MONOTONE_INC, SCIP_MONOTONE_UNKNOWN, SCIP_OKAY, SCIP_Real, SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPisGE(), SCIPisGT(), and SCIPisLE().
|
static |
expression handler copy callback
Definition at line 1098 of file expr_trig.c.
References SCIP_CALL, SCIP_OKAY, and SCIPincludeExprhdlrCos().
|
static |
simplifies a cosine expression
Evaluates the cosine value function when its child is a value expression.
TODO: add further simplifications
Definition at line 1112 of file expr_trig.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcaptureExpr(), SCIPcreateExprValue(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetValueExprValue(), and SCIPisExprValue().
|
static |
expression parse callback
Definition at line 1143 of file expr_trig.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateExprCos(), SCIPparseExpr(), SCIPreleaseExpr(), and TRUE.
|
static |
expression (point-) evaluation callback
Definition at line 1167 of file expr_trig.c.
References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetEvalValue(), and SCIPexprGetNChildren().
|
static |
expression derivative evaluation callback
Definition at line 1180 of file expr_trig.c.
References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetEvalValue(), SCIPexprGetHdlr(), and SCIPexprhdlrGetName().
|
static |
expression interval evaluation callback
Definition at line 1199 of file expr_trig.c.
References assert(), NULL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPintervalCos(), SCIPintervalIsEmpty(), and SCIPintervalSetEmpty().
|
static |
separation initialization callback
Definition at line 1218 of file expr_trig.c.
References computeInitialCutsTrig(), SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPisRelEQ().
|
static |
expression estimator callback
Definition at line 1238 of file expr_trig.c.
References assert(), computeEstimatorsTrig(), COSEXPRHDLR_NAME, NULL, SCIP_OKAY, SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), and TRUE.
|
static |
expression reverse propagation callback
Definition at line 1260 of file expr_trig.c.
References assert(), computeRevPropIntervalSin(), NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPexprGetNChildren(), SCIPintervalAddScalar(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), and TRUE.
|
static |
cosine hash callback
Definition at line 1294 of file expr_trig.c.
References assert(), COSEXPRHDLR_HASHKEY, NULL, SCIP_OKAY, and SCIPexprGetNChildren().
|
static |
expression curvature detection callback
Definition at line 1310 of file expr_trig.c.
References assert(), computeCurvatureSin(), FALSE, SCIP_Interval::inf, NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_EXPRCURV_UNKNOWN, SCIP_OKAY, SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIP_Interval::sup, and TRUE.
|
static |
expression monotonicity detection callback
Definition at line 1343 of file expr_trig.c.
References assert(), M_PI, NULL, result, SCIP_CALL, SCIP_MONOTONE_DEC, SCIP_MONOTONE_INC, SCIP_MONOTONE_UNKNOWN, SCIP_OKAY, SCIP_Real, SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPisGE(), SCIPisGT(), and SCIPisLE().