expr_trig.c
Go to the documentation of this file.
40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
68 /** evaluates the function a*x + b - sin(x) for some coefficient a and constant b at a given point p
81 /** evaluates the derivative of a*x + b - sin(x) for some coefficient a and constant b at a given point p
94 /** evaluates the function sin(x) + (alpha - x)*cos(x) - sin(alpha) for some constant alpha at a given point p
107 /** evaluates the derivative of sin(x) + (alpha - x)*cos(x) - sin(alpha) for some constant alpha at a given point p
183 * right now, this function is only checking whether the tangent underestimates independently of the lower bound!
247 /* if the point is too far away from the bounds or is at a multiple of pi, then tangent is not underestimating */
272 intersection = SCIPcalcRootNewton(function1, derivative1, params, 2, startingpoints[i], NEWTON_PRECISION,
289 /** helper function to compute the secant between lower bound and some point of the graph such that it underestimates
331 /* for lb < 0 but close to zero, we may have sin(lb) = 0 but lbmodpi = pi, which gives a starting point too close to lb
343 tangentpoint = SCIPcalcRootNewton(function2, derivative2, &lb, 1, startingpoint, NEWTON_PRECISION,
367 /* if the bounds are too close to each other, it's possible that the underestimator is not valid */
371 SCIPdebugMsg(scip, "left secant: %g + %g*x <= sin(x) on [%g,%g]\n", *linconst, *lincoef, lb, ub);
376 /** helper function to compute the secant between upper bound and some point of the graph such that it underestimates
409 /* in [3*pi/2,2*pi] underestimating doesn't work; otherwise, take the midpoint of possible area */
418 /* for ub < 0 but close to zero, we may have sin(ub) = 0 but ubmodpi = pi, which gives a starting point too close to ub
430 tangentpoint = SCIPcalcRootNewton(function2, derivative2, &ub, 1, startingpoint, NEWTON_PRECISION,
454 /* if the bounds are to close to each other, it's possible that the underestimator is not valid */
484 /* l(x) and u(x) are lower/upper bound of child, l(s) and u(s) are lower/upper bound of sin expr
496 /* if sin(l(x)) > u(s), we are looking for k minimal s.t. pi - a + 2k*pi > l(x) where a = asin(u(s))
513 /* if sin(u(x)) > u(s), we are looking for k minimal s.t. a + 2k*pi > u(x) - 2*pi where a = asin(u(s))
523 /* if sin(u(x)) < l(s), we are looking for k minimal s.t. pi - a + 2k*pi > l(x) - 2*pi where a = asin(l(s))
547 /** helper function to compute coefficients and constant term of a linear estimator at a given point
555 * They are ordered such that a successful computation for one of them cannot be improved by following ones in terms
656 assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), "sin") == 0 || strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), "cos") == 0);
694 /* try generating a secant between lb (ub) and some point < ub (> lb); otherwise try with tangent at lb (ub)*/
700 /* try generating a secant between ub (lb) and some point > lb (< ub); otherwise try with tangent at ub (lb)*/
722 /* helper function that computes the curvature of a sine expression for given bounds and curvature of child */
745 /* if sine is monotone on the interval, the curvature depends on the child curvature and on the segment */
808 SCIP_CALL( SCIPcreateExprValue(scip, simplifiedexpr, sin(SCIPgetValueExprValue(child)), ownercreate,
815 /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
957 SCIP_CALL( computeInitialCutsTrig(scip, expr, childlb, childub, ! overestimate, coefs, constant, nreturned) );
1036 if( computeCurvatureSin(SCIP_EXPRCURV_CONVEX, childinterval.inf, childinterval.sup) == exprcurvature )
1038 else if( computeCurvatureSin(SCIP_EXPRCURV_CONCAVE, childinterval.inf, childinterval.sup) == exprcurvature )
1040 if( computeCurvatureSin(SCIP_EXPRCURV_LINEAR, childinterval.inf, childinterval.sup) == exprcurvature )
1079 /* check whether [inf,sup] are in containing in an interval for which the sine function is monotone */
1118 SCIP_CALL( SCIPcreateExprValue(scip, simplifiedexpr, cos(SCIPgetValueExprValue(child)), ownercreate,
1125 /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
1222 SCIP_CALL( computeInitialCutsTrig(scip, expr, childlb, childub, ! overestimate, coefs, constant, nreturned) );
1266 SCIPintervalAddScalar(SCIP_INTERVAL_INFINITY, &newbounds, newbounds, M_PI_2); /* TODO use bounds on Pi/2 instead of approximation of Pi/2 */
1278 SCIPintervalAddScalar(SCIP_INTERVAL_INFINITY, &childrenbounds[0], newbounds, -M_PI_2); /* TODO use bounds on Pi/2 instead of approximation of Pi/2 */
1320 if( computeCurvatureSin(SCIP_EXPRCURV_CONCAVE, childinterval.inf + M_PI_2, childinterval.sup + M_PI_2) == exprcurvature )
1322 else if( computeCurvatureSin(SCIP_EXPRCURV_CONVEX, childinterval.inf + M_PI_2, childinterval.sup + M_PI_2) == exprcurvature )
1324 else if( computeCurvatureSin(SCIP_EXPRCURV_LINEAR, childinterval.inf + M_PI_2, childinterval.sup + M_PI_2) == exprcurvature )
1363 /* check whether [inf,sup] are contained in an interval for which the cosine function is monotone */
1378 SCIP_CALL( SCIPincludeExprhdlr(scip, &exprhdlr, SINEXPRHDLR_NAME, SINEXPRHDLR_DESC, SINEXPRHDLR_PRECEDENCE, evalSin, NULL) );
1403 SCIP_CALL( SCIPincludeExprhdlr(scip, &exprhdlr, COSEXPRHDLR_NAME, COSEXPRHDLR_DESC, COSEXPRHDLR_PRECEDENCE, evalCos, NULL) );
1433 SCIP_CALL( SCIPcreateExpr(scip, expr, SCIPfindExprhdlr(scip, SINEXPRHDLR_NAME), NULL, 1, &child, ownercreate,
1453 SCIP_CALL( SCIPcreateExpr(scip, expr, SCIPfindExprhdlr(scip, COSEXPRHDLR_NAME), NULL, 1, &child, ownercreate,
void SCIPintervalCos(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2730
Definition: intervalarith.h:44
Definition: struct_scip.h:59
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:1149
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1706
Definition: type_expr.h:59
Definition: type_expr.h:52
void SCIPexprhdlrSetDiff(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)), SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)))
Definition: expr.c:464
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)
Definition: expr_trig.c:639
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
void SCIPexprhdlrSetParse(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPARSE((*parse)))
Definition: expr.c:398
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
Definition: struct_expr.h:34
static SCIP_Bool computeRightSecantSin(SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb, SCIP_Real ub)
Definition: expr_trig.c:381
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:705
static SCIP_Bool computeSolTangentSin(SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb, SCIP_Real ub, SCIP_Real solpoint)
Definition: expr_trig.c:219
Definition: type_expr.h:53
void SCIPexprhdlrSetHash(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRHASH((*hash)))
Definition: expr.c:442
static SCIP_RETCODE computeRevPropIntervalSin(SCIP *scip, SCIP_INTERVAL parentbounds, SCIP_INTERVAL childbounds, SCIP_INTERVAL *newbounds)
Definition: expr_trig.c:463
static SCIP_Bool computeLeftTangentSin(SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb)
Definition: expr_trig.c:157
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
Definition: type_expr.h:61
SCIP_EXPRHDLR * SCIPfindExprhdlr(SCIP *scip, const char *name)
Definition: scip_expr.c:859
SCIP_Real SCIPcalcRootNewton(SCIP_DECL_NEWTONEVAL((*function)), SCIP_DECL_NEWTONEVAL((*derivative)), SCIP_Real *params, int nparams, SCIP_Real x, SCIP_Real eps, int k)
Definition: misc.c:9760
SCIP_RETCODE SCIPcreateExpr(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, int nchildren, SCIP_EXPR **children, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:964
Definition: type_expr.h:51
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
Definition: intervalarith.c:446
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
Definition: intervalarith.c:435
static SCIP_DECL_EXPRREVERSEPROP(reversepropSin)
Definition: expr_trig.c:986
Definition: type_expr.h:50
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
Definition: intervalarith.c:393
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
Definition: intervalarith.c:401
Definition: type_retcode.h:33
static SCIP_DECL_EXPRMONOTONICITY(monotonicitySin)
Definition: expr_trig.c:1050
SCIP_RETCODE SCIPcreateExprValue(SCIP *scip, SCIP_EXPR **expr, SCIP_Real value, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_value.c:261
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
void SCIPexprhdlrSetCopyFreeHdlr(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)), SCIP_DECL_EXPRFREEHDLR((*freehdlr)))
Definition: expr.c:359
static SCIP_EXPRCURV computeCurvatureSin(SCIP_EXPRCURV childcurvature, SCIP_Real lb, SCIP_Real ub)
Definition: expr_trig.c:724
static SCIP_Bool computeRightTangentSin(SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real ub)
Definition: expr_trig.c:190
static SCIP_Bool computeLeftSecantSin(SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb, SCIP_Real ub)
Definition: expr_trig.c:294
static SCIP_DECL_EXPRINITESTIMATES(initEstimatesSin)
Definition: expr_trig.c:944
Definition: struct_expr.h:95
void SCIPexprhdlrSetMonotonicity(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRMONOTONICITY((*monotonicity)))
Definition: expr.c:420
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
handler for sin expressions
void SCIPexprhdlrSetReverseProp(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRREVERSEPROP((*reverseprop)))
Definition: expr.c:501
SCIP_RETCODE SCIPparseExpr(SCIP *scip, SCIP_EXPR **expr, const char *exprstr, const char **finalpos, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1370
constant value expression handler
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
void SCIPexprhdlrSetCurvature(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCURVATURE((*curvature)))
Definition: expr.c:409
Definition: type_expr.h:60
SCIP_RETCODE SCIPcreateExprSin(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_trig.c:1421
SCIP_RETCODE SCIPcreateExprCos(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_trig.c:1441
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
Definition: intervalarith.c:421
static SCIP_Bool computeSecantSin(SCIP *scip, SCIP_Real *lincoef, SCIP_Real *linconst, SCIP_Real lb, SCIP_Real ub)
Definition: expr_trig.c:125
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)
Definition: expr_trig.c:559
void SCIPexprhdlrSetEstimate(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINITESTIMATES((*initestimates)), SCIP_DECL_EXPRESTIMATE((*estimate)))
Definition: expr.c:512
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
Definition: objbenders.h:33
SCIP_RETCODE SCIPincludeExprhdlr(SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
Definition: scip_expr.c:814
void SCIPexprhdlrSetSimplify(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRSIMPLIFY((*simplify)))
Definition: expr.c:490
void SCIPintervalSin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2688
void SCIPexprhdlrSetIntEval(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEVAL((*inteval)))
Definition: expr.c:479