  # SCIP

Solving Constraint Integer Programs

expr_trig.c File Reference

## Detailed Description

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.

#include <string.h>
#include <math.h>
#include "scip/expr_trig.h"
#include "scip/expr_value.h"

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

## Functions

static SCIP_DECL_NEWTONEVAL (function1)

static SCIP_DECL_NEWTONEVAL (derivative1)

static SCIP_DECL_NEWTONEVAL (function2)

static SCIP_DECL_NEWTONEVAL (derivative2)

static SCIP_Bool computeSecantSin (SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb, SCIP_Real ub)

static SCIP_Bool computeLeftTangentSin (SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb)

static SCIP_Bool computeRightTangentSin (SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real ub)

static SCIP_Bool computeSolTangentSin (SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb, SCIP_Real ub, SCIP_Real solpoint)

static SCIP_Bool computeLeftSecantSin (SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb, SCIP_Real ub)

static SCIP_Bool computeRightSecantSin (SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb, SCIP_Real ub)

static SCIP_RETCODE computeRevPropIntervalSin (SCIP *scip, SCIP_INTERVAL parentbounds, SCIP_INTERVAL childbounds, SCIP_INTERVAL *newbounds)

static SCIP_Bool computeEstimatorsTrig (SCIP *scip, SCIP_EXPR *expr, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real refpoint, SCIP_Real childlb, SCIP_Real childub, SCIP_Bool underestimate)

static SCIP_RETCODE computeInitialCutsTrig (SCIP *scip, SCIP_EXPR *expr, SCIP_Real childlb, SCIP_Real childub, SCIP_Bool underestimate, SCIP_Real **coefs, SCIP_Real *constant, int *nreturned)

static SCIP_EXPRCURV computeCurvatureSin (SCIP_EXPRCURV childcurvature, SCIP_Real lb, SCIP_Real ub)

static SCIP_DECL_EXPRCOPYHDLR (copyhdlrSin)

static SCIP_DECL_EXPRSIMPLIFY (simplifySin)

static SCIP_DECL_EXPRPARSE (parseSin)

static SCIP_DECL_EXPREVAL (evalSin)

static SCIP_DECL_EXPRBWDIFF (bwdiffSin)

static SCIP_DECL_EXPRFWDIFF (fwdiffSin)

static SCIP_DECL_EXPRBWFWDIFF (bwfwdiffSin)

static SCIP_DECL_EXPRINTEVAL (intevalSin)

static SCIP_DECL_EXPRINITESTIMATES (initEstimatesSin)

static SCIP_DECL_EXPRESTIMATE (estimateSin)

static SCIP_DECL_EXPRREVERSEPROP (reversepropSin)

static SCIP_DECL_EXPRHASH (hashSin)

static SCIP_DECL_EXPRCURVATURE (curvatureSin)

static SCIP_DECL_EXPRMONOTONICITY (monotonicitySin)

static SCIP_DECL_EXPRCOPYHDLR (copyhdlrCos)

static SCIP_DECL_EXPRSIMPLIFY (simplifyCos)

static SCIP_DECL_EXPRPARSE (parseCos)

static SCIP_DECL_EXPREVAL (evalCos)

static SCIP_DECL_EXPRBWDIFF (bwdiffCos)

static SCIP_DECL_EXPRINTEVAL (intevalCos)

static SCIP_DECL_EXPRINITESTIMATES (initEstimatesCos)

static SCIP_DECL_EXPRESTIMATE (estimateCos)

static SCIP_DECL_EXPRREVERSEPROP (reversepropCos)

static SCIP_DECL_EXPRHASH (hashCos)

static SCIP_DECL_EXPRCURVATURE (curvatureCos)

static SCIP_DECL_EXPRMONOTONICITY (monotonicityCos)

SCIP_RETCODE SCIPincludeExprhdlrSin (SCIP *scip)

SCIP_RETCODE SCIPincludeExprhdlrCos (SCIP *scip)

SCIP_RETCODE SCIPcreateExprSin (SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)

SCIP_RETCODE SCIPcreateExprCos (SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)

SCIP_Bool SCIPisExprSin (SCIP *scip, SCIP_EXPR *expr)

SCIP_Bool SCIPisExprCos (SCIP *scip, SCIP_EXPR *expr)

## ◆ SINEXPRHDLR_NAME

 #define SINEXPRHDLR_NAME   "sin"

## ◆ SINEXPRHDLR_DESC

 #define SINEXPRHDLR_DESC   "sine expression"

Definition at line 60 of file expr_trig.c.

Referenced by SCIPincludeExprhdlrSin().

## ◆ SINEXPRHDLR_PRECEDENCE

 #define SINEXPRHDLR_PRECEDENCE   91000

Definition at line 61 of file expr_trig.c.

Referenced by SCIPincludeExprhdlrSin().

## ◆ SINEXPRHDLR_HASHKEY

 #define SINEXPRHDLR_HASHKEY   SCIPcalcFibHash(82457.0)

Definition at line 62 of file expr_trig.c.

Referenced by SCIP_DECL_EXPRHASH().

## ◆ COSEXPRHDLR_NAME

 #define COSEXPRHDLR_NAME   "cos"

## ◆ COSEXPRHDLR_DESC

 #define COSEXPRHDLR_DESC   "cosine expression"

Definition at line 65 of file expr_trig.c.

Referenced by SCIPincludeExprhdlrCos().

## ◆ COSEXPRHDLR_PRECEDENCE

 #define COSEXPRHDLR_PRECEDENCE   92000

Definition at line 66 of file expr_trig.c.

Referenced by SCIPincludeExprhdlrCos().

## ◆ COSEXPRHDLR_HASHKEY

 #define COSEXPRHDLR_HASHKEY   SCIPcalcFibHash(82463.0)

Definition at line 67 of file expr_trig.c.

Referenced by SCIP_DECL_EXPRHASH().

## ◆ MAXCHILDABSVAL

 #define MAXCHILDABSVAL   1e+6

maximum absolute value that is accepted for propagation

Definition at line 69 of file expr_trig.c.

Referenced by computeRevPropIntervalSin().

## ◆ NEWTON_NITERATIONS

 #define NEWTON_NITERATIONS   100

Definition at line 70 of file expr_trig.c.

Referenced by computeLeftSecantSin(), computeRightSecantSin(), and computeSolTangentSin().

## ◆ NEWTON_PRECISION

 #define NEWTON_PRECISION   1e-12

Definition at line 71 of file expr_trig.c.

Referenced by computeLeftSecantSin(), computeRightSecantSin(), and computeSolTangentSin().

## ◆ SCIP_DECL_NEWTONEVAL() [1/4]

 static SCIP_DECL_NEWTONEVAL ( function1 )
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.

References NULL.

## ◆ SCIP_DECL_NEWTONEVAL() [2/4]

 static SCIP_DECL_NEWTONEVAL ( derivative1 )
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.

References NULL.

## ◆ SCIP_DECL_NEWTONEVAL() [3/4]

 static SCIP_DECL_NEWTONEVAL ( function2 )
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.

References NULL.

## ◆ SCIP_DECL_NEWTONEVAL() [4/4]

 static SCIP_DECL_NEWTONEVAL ( derivative2 )
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.

References NULL.

## ◆ computeSecantSin()

 static SCIP_Bool computeSecantSin ( SCIP * scip, SCIP_Real * lincoef, SCIP_Real * linconst, SCIP_Real lb, SCIP_Real ub )
static

helper function to compute the secant if it is a valid underestimator

returns true if the estimator was computed successfully

Parameters
 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 FALSE, M_PI, NULL, and TRUE.

Referenced by computeEstimatorsTrig(), and computeInitialCutsTrig().

## ◆ computeLeftTangentSin()

 static SCIP_Bool computeLeftTangentSin ( SCIP * scip, SCIP_Real * lincoef, SCIP_Real * linconst, SCIP_Real lb )
static

helper function to compute the tangent at lower bound if it is underestimating

returns true if the underestimator was computed successfully

Parameters
 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 FALSE, NULL, SCIPisInfinity(), and TRUE.

Referenced by computeInitialCutsTrig().

## ◆ computeRightTangentSin()

 static SCIP_Bool computeRightTangentSin ( SCIP * scip, SCIP_Real * lincoef, SCIP_Real * linconst, SCIP_Real ub )
static

helper function to compute the tangent at upper bound if it is an underestimator

returns true if the underestimator was computed successfully

Parameters
 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 FALSE, NULL, SCIPisInfinity(), and TRUE.

Referenced by computeInitialCutsTrig().

## ◆ computeSolTangentSin()

 static SCIP_Bool computeSolTangentSin ( SCIP * scip, SCIP_Real * lincoef, SCIP_Real * linconst, SCIP_Real lb, SCIP_Real ub, SCIP_Real solpoint )
static

helper function to compute the tangent at solution point if it is an underestimator

returns true if the underestimator was computed successfully

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

Referenced by computeEstimatorsTrig().

## ◆ computeLeftSecantSin()

 static SCIP_Bool computeLeftSecantSin ( SCIP * scip, SCIP_Real * lincoef, SCIP_Real * linconst, SCIP_Real lb, SCIP_Real ub )
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

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

Referenced by computeEstimatorsTrig(), and computeInitialCutsTrig().

## ◆ computeRightSecantSin()

 static SCIP_Bool computeRightSecantSin ( SCIP * scip, SCIP_Real * lincoef, SCIP_Real * linconst, SCIP_Real lb, SCIP_Real ub )
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

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

Referenced by computeEstimatorsTrig(), and computeInitialCutsTrig().

## ◆ computeRevPropIntervalSin()

 static SCIP_RETCODE computeRevPropIntervalSin ( SCIP * scip, SCIP_INTERVAL parentbounds, SCIP_INTERVAL childbounds, SCIP_INTERVAL * newbounds )
static

helper function to compute the new interval for child in reverse propagation

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

Referenced by SCIP_DECL_EXPRREVERSEPROP().

## ◆ computeEstimatorsTrig()

 static SCIP_Bool computeEstimatorsTrig ( SCIP * scip, SCIP_EXPR * expr, SCIP_Real * lincoef, SCIP_Real * linconst, SCIP_Real refpoint, SCIP_Real childlb, SCIP_Real childub, SCIP_Bool underestimate )
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:

• soltangent: tangent at specified refpoint
• secant: secant between the points (lb,sin(lb)) and (ub,sin(ub))
• left secant: secant between lower bound and some point of the graph
• right secant: secant between upper bound and some point of the graph

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.

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

Referenced by SCIP_DECL_EXPRESTIMATE().

## ◆ computeInitialCutsTrig()

 static SCIP_RETCODE computeInitialCutsTrig ( SCIP * scip, SCIP_EXPR * expr, SCIP_Real childlb, SCIP_Real childub, SCIP_Bool underestimate, SCIP_Real ** coefs, SCIP_Real * constant, int * nreturned )
static

helper function to create initial cuts for sine and cosine separation

The following 5 cuts can be generated:

• secant: secant between the bounds (lb,sin(lb)) and (ub,sin(ub))
• left/right secant: secant between lower/upper bound and some point of the graph
• left/right tangent: tangents at the lower/upper bounds
Parameters
 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.

Referenced by SCIP_DECL_EXPRINITESTIMATES().

## ◆ computeCurvatureSin()

 static SCIP_EXPRCURV computeCurvatureSin ( SCIP_EXPRCURV childcurvature, SCIP_Real lb, SCIP_Real ub )
static
Parameters
 childcurvature curvature of child lb lower bound of child ub upper bound of child

Definition at line 733 of file expr_trig.c.

Referenced by SCIP_DECL_EXPRCURVATURE().

## ◆ SCIP_DECL_EXPRCOPYHDLR() [1/2]

 static SCIP_DECL_EXPRCOPYHDLR ( copyhdlrSin )
static

expression handler copy callback

Definition at line 788 of file expr_trig.c.

References SCIP_CALL, SCIP_OKAY, and SCIPincludeExprhdlrSin().

## ◆ SCIP_DECL_EXPRSIMPLIFY() [1/2]

 static SCIP_DECL_EXPRSIMPLIFY ( simplifySin )
static

simplifies a sine expression

Evaluates the sine value function when its child is a value expression.

Definition at line 802 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRPARSE() [1/2]

 static SCIP_DECL_EXPRPARSE ( parseSin )
static

expression parse callback

Definition at line 833 of file expr_trig.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateExprSin(), SCIPparseExpr(), SCIPreleaseExpr(), and TRUE.

## ◆ SCIP_DECL_EXPREVAL() [1/2]

 static SCIP_DECL_EXPREVAL ( evalSin )
static

expression (point-) evaluation callback

Definition at line 857 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRBWDIFF() [1/2]

 static SCIP_DECL_EXPRBWDIFF ( bwdiffSin )
static

expression derivative evaluation callback

Definition at line 870 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRFWDIFF()

 static SCIP_DECL_EXPRFWDIFF ( fwdiffSin )
static

derivative evaluation callback

Computes <gradient, children.dot>, that is, cos(child) dot(child).

Definition at line 892 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRBWFWDIFF()

 static SCIP_DECL_EXPRBWFWDIFF ( bwfwdiffSin )
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.

## ◆ SCIP_DECL_EXPRINTEVAL() [1/2]

 static SCIP_DECL_EXPRINTEVAL ( intevalSin )
static

expression interval evaluation callback

Definition at line 934 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRINITESTIMATES() [1/2]

 static SCIP_DECL_EXPRINITESTIMATES ( initEstimatesSin )
static

separation initialization callback

Definition at line 953 of file expr_trig.c.

References computeInitialCutsTrig(), SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPisRelEQ().

## ◆ SCIP_DECL_EXPRESTIMATE() [1/2]

 static SCIP_DECL_EXPRESTIMATE ( estimateSin )
static

expression estimator callback

Definition at line 973 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRREVERSEPROP() [1/2]

 static SCIP_DECL_EXPRREVERSEPROP ( reversepropSin )
static

expression reverse propagation callback

Definition at line 995 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRHASH() [1/2]

 static SCIP_DECL_EXPRHASH ( hashSin )
static

sine hash callback

Definition at line 1011 of file expr_trig.c.

References NULL, SCIP_OKAY, SCIPexprGetNChildren(), and SINEXPRHDLR_HASHKEY.

## ◆ SCIP_DECL_EXPRCURVATURE() [1/2]

 static SCIP_DECL_EXPRCURVATURE ( curvatureSin )
static

expression curvature detection callback

Definition at line 1027 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRMONOTONICITY() [1/2]

 static SCIP_DECL_EXPRMONOTONICITY ( monotonicitySin )
static

expression monotonicity detection callback

Definition at line 1059 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRCOPYHDLR() [2/2]

 static SCIP_DECL_EXPRCOPYHDLR ( copyhdlrCos )
static

expression handler copy callback

Definition at line 1098 of file expr_trig.c.

References SCIP_CALL, SCIP_OKAY, and SCIPincludeExprhdlrCos().

## ◆ SCIP_DECL_EXPRSIMPLIFY() [2/2]

 static SCIP_DECL_EXPRSIMPLIFY ( simplifyCos )
static

simplifies a cosine expression

Evaluates the cosine value function when its child is a value expression.

Definition at line 1112 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRPARSE() [2/2]

 static SCIP_DECL_EXPRPARSE ( parseCos )
static

expression parse callback

Definition at line 1143 of file expr_trig.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateExprCos(), SCIPparseExpr(), SCIPreleaseExpr(), and TRUE.

## ◆ SCIP_DECL_EXPREVAL() [2/2]

 static SCIP_DECL_EXPREVAL ( evalCos )
static

expression (point-) evaluation callback

Definition at line 1167 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRBWDIFF() [2/2]

 static SCIP_DECL_EXPRBWDIFF ( bwdiffCos )
static

expression derivative evaluation callback

Definition at line 1180 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRINTEVAL() [2/2]

 static SCIP_DECL_EXPRINTEVAL ( intevalCos )
static

expression interval evaluation callback

Definition at line 1199 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRINITESTIMATES() [2/2]

 static SCIP_DECL_EXPRINITESTIMATES ( initEstimatesCos )
static

separation initialization callback

Definition at line 1218 of file expr_trig.c.

References computeInitialCutsTrig(), SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPisRelEQ().

## ◆ SCIP_DECL_EXPRESTIMATE() [2/2]

 static SCIP_DECL_EXPRESTIMATE ( estimateCos )
static

expression estimator callback

Definition at line 1238 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRREVERSEPROP() [2/2]

 static SCIP_DECL_EXPRREVERSEPROP ( reversepropCos )
static

expression reverse propagation callback

Definition at line 1260 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRHASH() [2/2]

 static SCIP_DECL_EXPRHASH ( hashCos )
static

cosine hash callback

Definition at line 1294 of file expr_trig.c.

References COSEXPRHDLR_HASHKEY, NULL, SCIP_OKAY, and SCIPexprGetNChildren().

## ◆ SCIP_DECL_EXPRCURVATURE() [2/2]

 static SCIP_DECL_EXPRCURVATURE ( curvatureCos )
static

expression curvature detection callback

Definition at line 1310 of file expr_trig.c.

## ◆ SCIP_DECL_EXPRMONOTONICITY() [2/2]

 static SCIP_DECL_EXPRMONOTONICITY ( monotonicityCos )
static

expression monotonicity detection callback

Definition at line 1343 of file expr_trig.c.