nlhdlr_quotient.c
Go to the documentation of this file.
32 * @todo use the convex envelope for x/y described in Tawarmalani and Sahinidis (2002) if y has a finite upper bound
175 * @todo At the moment quotients like xy / z are not detected, because they are turned into a product expression
182 SCIP_NLHDLREXPRDATA** nlhdlrexprdata, /**< pointer to store nonlinear handler expression data */
183 SCIP_Bool* success /**< pointer to store whether nonlinear handler should be called for this expression */
219 if( SCIPisExprPower(scip, children[0]) && SCIPgetExponentExprPow(children[0]) == -1.0 ) /*lint !e777*/
224 else if( SCIPisExprPower(scip, children[1]) && SCIPgetExponentExprPow(children[1]) == -1.0 ) /*lint !e777*/
243 && SCIPisExprProduct(scip, children[1]) && SCIPexprGetNChildren(children[1]) == 2 ) /* lint !e777 */
264 && SCIPisExprProduct(scip, children[0]) && SCIPexprGetNChildren(children[0]) == 2 ) /* lint !e777 */
290 /* transform numerator and denominator to detect structures like (a * f(x) + b) / (c * f(x) + d) */
294 SCIPdebugMsg(scip, "detected numerator (%g * %p + %g) and denominator (%g * %p + %g)\n", a, (void*)xexpr, b,
297 /* detection is only be successful if the expression of the numerator an denominator are the same
298 * (so boundtightening can be stronger than default) or we are going to provide estimators (there will be an auxvar)
326 * if univariate, then we also do inteval and reverseprop, so mark that the activities will be used for inteval
344 SCIPdebugMsg(scip, "detected quotient expression (%g * %p + %g) / (%g * %p + %g) + %g\n", a, (void*)xexpr,
459 /* if the expression is constant or the limit lies inside the domain, nothing can be propagated */
557 SCIP_Bool* branchinguseful, /**< pointer to store whether branching on the expression would improve the estimator */
631 /** helper method to compute estimator for the univariate case; the estimator is stored in a given rowprep */
644 SCIP_Bool* branchinguseful, /**< pointer to store whether branching on the expression would improve the estimator */
690 SCIP_CALL( estimateUnivariate(scip, lbx, ubx, gllbx, glubx, solx, a, b, c, d, e, &coef, &constant, overestimate, &local, branchinguseful, success) );
695 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "quot_%s_%lld", SCIPvarGetName(x), SCIPgetNLPs(scip));
705 * h^c(x,y) := \frac{1}{y} \left(\frac{x + \sqrt{\text{lbx}\cdot\text{ubx}}}{\sqrt{\text{lbx}} + \sqrt{\text{ubx}}}\right)^2
747 * x = y * z ≤ a * y + b * z + c. Note that b > 0 because of y > 0. The inequality is then transformed
748 * to x / b - a/b * y - c/b ≤ z, which results in a valid underestimator for x / y over the set
749 * {(x,y) | lbz ≤ x / y ≤ ubz}. Note that overestimating/underestimating the bilinear term with McCormick
753 * - overestimation: use \f$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})\f$
754 * - underestimation: use \f$z \geq x/y \geq \frac{1}{y} \frac{x + \sqrt{\text{lbx}\cdot\text{ubx}}}{\sqrt{\text{lbx} + \sqrt{\text{ubx}}}}\f$ and build gradient cut
756 * If y < 0, swap and negate its bounds and compute the respective opposite estimator (and negate it).
776 SCIP_Bool* branchingusefulx, /**< pointer to store whether branching on x would improve the estimator */
777 SCIP_Bool* branchingusefuly, /**< pointer to store whether branching on y would improve the estimator */
827 /* as explained in the description of this method, overestimating/underestimating the bilinear term results in an
830 SCIPaddBilinMcCormick(scip, 1.0, lbz, ubz, solz, lby, uby, soly, !overestimate, &mccoefaux, &mccoefy, &mcconst,
891 /* if exactly one variable has been negated, then we have computed an underestimate/overestimate for the negated
933 SCIP_Bool* branchingusefulx, /**< pointer to store whether branching on x would improve the estimator */
934 SCIP_Bool* branchingusefuly, /**< pointer to store whether branching on y would improve the estimator */
1009 /* transform estimator Ax' + By'+ C = A(ax + b) + B (cy + d) + C = (Aa) x + (Bc) y + (C + Ab + Bd);
1017 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "quot_%s_%s_%lld", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]),
1144 SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, TRUE) );
1149 SCIP_CALL( estimateUnivariateQuotient(scip, sol, nlhdlrexprdata->numexpr, nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst,
1150 nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst, nlhdlrexprdata->constant, overestimate, rowprep,
1156 SCIP_CALL( estimateBivariateQuotient(scip, nlhdlrexprdata->numexpr, nlhdlrexprdata->denomexpr, SCIPgetExprAuxVarNonlinear(expr), sol,
1157 nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst, nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst,
1185 SCIP_CALL( SCIPgetExprRelAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
1187 SCIP_CALL( SCIPgetExprAbsAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
1191 SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, exprs, nexprs, violation, sol, addedbranchscores) );
1210 * we should not be called in this case, as we haven't said we would participate in this activity in detect
1238 * we should not be called in this case, as we haven't said we would participate in this activity in detect
1242 SCIPdebugMsg(scip, "call reverse propagation for expression (%g %p + %g) / (%g %p + %g) + %g bounds [%g,%g]\n",
1257 SCIP_CALL( SCIPtightenExprIntervalNonlinear(scip, nlhdlrexprdata->numexpr, result, infeasible, nreductions) );
1281 SCIP_CALL( SCIPincludeNlhdlrNonlinear(scip, &nlhdlr, NLHDLR_NAME, NLHDLR_DESC, NLHDLR_DETECTPRIORITY,
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
Definition: intervalarith.c:470
void SCIPintervalUnify(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:609
Definition: intervalarith.h:53
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1476
Definition: struct_scip.h:68
unsigned int SCIPgetExprNAuxvarUsesNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12915
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1708
static SCIP_DECL_NLHDLRDETECT(nlhdlrDetectQuotient)
Definition: nlhdlr_quotient.c:1059
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEEXPRDATA((*freeexprdata)))
Definition: nlhdlr.c:94
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
Definition: struct_var.h:207
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
Definition: cons_nonlinear.c:12938
static SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrQuotient)
Definition: nlhdlr_quotient.c:1031
void SCIPintervalIntersectEps(SCIP_INTERVAL *resultant, SCIP_Real eps, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:578
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:717
static void transformExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **target, SCIP_Real *coef, SCIP_Real *constant)
Definition: nlhdlr_quotient.c:140
static SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateQuotient)
Definition: nlhdlr_quotient.c:1129
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
Definition: intervalarith.c:421
Definition: type_lp.h:64
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
Definition: misc_rowprep.c:878
Definition: struct_nlhdlr.h:43
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
static SCIP_INTERVAL intEvalQuotient(SCIP *scip, SCIP_INTERVAL bnds, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e)
Definition: nlhdlr_quotient.c:354
static SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataQuotient)
Definition: nlhdlr_quotient.c:1045
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1454
bilinear nonlinear handler
Definition: struct_sol.h:73
static void hcGradCut(SCIP_Real lbx, SCIP_Real ubx, SCIP_Real solx, SCIP_Real soly, SCIP_Real *coefx, SCIP_Real *coefy, SCIP_Real *constant)
Definition: nlhdlr_quotient.c:712
void SCIPintervalDiv(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:1154
static SCIP_RETCODE estimateUnivariate(SCIP *scip, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real gllbx, SCIP_Real glubx, SCIP_Real solx, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e, SCIP_Real *coef, SCIP_Real *constant, SCIP_Bool overestimate, SCIP_Bool *local, SCIP_Bool *branchinguseful, SCIP_Bool *success)
Definition: nlhdlr_quotient.c:541
static SCIP_RETCODE exprdataFree(SCIP *scip, SCIP_NLHDLREXPRDATA **nlhdlrexprdata)
Definition: nlhdlr_quotient.c:118
static SCIP_RETCODE detectExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool *success)
Definition: nlhdlr_quotient.c:179
SCIP_RETCODE SCIPincludeNlhdlrQuotient(SCIP *scip)
Definition: nlhdlr_quotient.c:1269
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
Definition: intervalarith.c:458
SCIP_RETCODE SCIPincludeNlhdlrNonlinear(SCIP *scip, SCIP_NLHDLR **nlhdlr, const char *name, const char *desc, int detectpriority, int enfopriority, SCIP_DECL_NLHDLRDETECT((*detect)), SCIP_DECL_NLHDLREVALAUX((*evalaux)), SCIP_NLHDLRDATA *nlhdlrdata)
Definition: cons_nonlinear.c:13705
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
Definition: intervalarith.c:447
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
Definition: intervalarith.c:405
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
Definition: intervalarith.c:413
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1115
Definition: type_retcode.h:42
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:581
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
Definition: misc_rowprep.c:737
static SCIP_RETCODE estimateBivariate(SCIP *scip, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real lby, SCIP_Real uby, SCIP_Real lbz, SCIP_Real ubz, SCIP_Real solx, SCIP_Real soly, SCIP_Real solz, SCIP_Bool overestimate, SCIP_Real *coefx, SCIP_Real *coefy, SCIP_Real *constant, SCIP_Bool *branchingusefulx, SCIP_Bool *branchingusefuly, SCIP_Bool *success)
Definition: nlhdlr_quotient.c:761
quotient nonlinear handler
SCIP_Real SCIPgetCoefExprProduct(SCIP_EXPR *expr)
Definition: expr_product.c:2155
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)), SCIP_DECL_NLHDLREXITSEPA((*exitsepa)))
Definition: nlhdlr.c:132
Definition: struct_expr.h:104
static SCIP_RETCODE estimateUnivariateQuotient(SCIP *scip, SCIP_SOL *sol, SCIP_EXPR *xexpr, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e, SCIP_Bool overestimate, SCIP_ROWPREP *rowprep, SCIP_Bool *branchinguseful, SCIP_Bool *success)
Definition: nlhdlr_quotient.c:633
static SCIP_DECL_NLHDLRINTEVAL(nlhdlrIntevalQuotient)
Definition: nlhdlr_quotient.c:1201
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
constraint handler for nonlinear constraints specified by algebraic expressions
void SCIPnlhdlrSetProp(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINTEVAL((*inteval)), SCIP_DECL_NLHDLRREVERSEPROP((*reverseprop)))
Definition: nlhdlr.c:119
static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalauxQuotient)
Definition: nlhdlr_quotient.c:1089
void SCIPaddBilinMcCormick(SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
Definition: nlhdlr_bilinear.c:1762
void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:845
static SCIP_RETCODE createRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR **vars, SCIP_Real *coefs, SCIP_Real constant, int nlinvars)
Definition: nlhdlr_quotient.c:500
static SCIP_RETCODE exprdataCreate(SCIP *scip, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_EXPR *numexpr, SCIP_Real numcoef, SCIP_Real numconst, SCIP_EXPR *denomexpr, SCIP_Real denomcoef, SCIP_Real denomconst, SCIP_Real constant)
Definition: nlhdlr_quotient.c:79
SCIP_RETCODE SCIPtightenExprIntervalNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_INTERVAL newbounds, SCIP_Bool *cutoff, int *ntightenings)
Definition: cons_nonlinear.c:13187
static SCIP_INTERVAL reversepropQuotient(SCIP_INTERVAL bnds, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e)
Definition: nlhdlr_quotient.c:438
void SCIPintervalDivScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1208
SCIP_RETCODE SCIPgetExprAbsAuxViolationNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Real auxvalue, SCIP_SOL *sol, SCIP_Real *viol, SCIP_Bool *violunder, SCIP_Bool *violover)
Definition: cons_nonlinear.c:13063
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
Definition: intervalarith.c:433
SCIP_RETCODE SCIPaddExprsViolScoreNonlinear(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Real violscore, SCIP_SOL *sol, SCIP_Bool *success)
Definition: cons_nonlinear.c:13432
Definition: type_lp.h:65
SCIP_RETCODE SCIPgetExprRelAuxViolationNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Real auxvalue, SCIP_SOL *sol, SCIP_Real *viol, SCIP_Bool *violunder, SCIP_Bool *violover)
Definition: cons_nonlinear.c:13095
static SCIP_RETCODE estimateBivariateQuotient(SCIP *scip, SCIP_EXPR *xexpr, SCIP_EXPR *yexpr, SCIP_VAR *auxvar, SCIP_SOL *sol, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e, SCIP_Bool overestimate, SCIP_ROWPREP *rowprep, SCIP_Bool *branchingusefulx, SCIP_Bool *branchingusefuly, SCIP_Bool *success)
Definition: nlhdlr_quotient.c:920
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
Definition: misc_rowprep.c:561
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12796
private functions of nonlinear handlers of nonlinear constraints
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
Definition: misc_rowprep.c:771
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
Definition: misc_rowprep.c:929
Definition: objbenders.h:43
SCIP_INTERVAL SCIPgetExprBoundsNonlinear(SCIP *scip, SCIP_EXPR *expr)
Definition: cons_nonlinear.c:13131
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
preparation of a linear inequality to become a SCIP_ROW
SCIP_RETCODE SCIPsetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx, void *val)
Definition: scip_datastructures.c:574
static SCIP_DECL_NLHDLRREVERSEPROP(nlhdlrReversepropQuotient)
Definition: nlhdlr_quotient.c:1229
Definition: struct_misc.h:286
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRCOPYHDLR((*copy)))
Definition: nlhdlr.c:72