nlhdlr_quotient.c
Go to the documentation of this file.
23 * @todo use the convex envelope for x/y described in Tawarmalani and Sahinidis (2002) if y has a finite upper bound
166 * @todo At the moment quotients like xy / z are not detected, because they are turned into a product expression
173 SCIP_NLHDLREXPRDATA** nlhdlrexprdata, /**< pointer to store nonlinear handler expression data */
174 SCIP_Bool* success /**< pointer to store whether nonlinear handler should be called for this expression */
210 if( SCIPisExprPower(scip, children[0]) && SCIPgetExponentExprPow(children[0]) == -1.0 ) /*lint !e777*/
215 else if( SCIPisExprPower(scip, children[1]) && SCIPgetExponentExprPow(children[1]) == -1.0 ) /*lint !e777*/
234 && SCIPisExprProduct(scip, children[1]) && SCIPexprGetNChildren(children[1]) == 2 ) /* lint !e777 */
255 && SCIPisExprProduct(scip, children[0]) && SCIPexprGetNChildren(children[0]) == 2 ) /* lint !e777 */
281 /* transform numerator and denominator to detect structures like (a * f(x) + b) / (c * f(x) + d) */
285 SCIPdebugMsg(scip, "detected numerator (%g * %p + %g) and denominator (%g * %p + %g)\n", a, (void*)xexpr, b,
288 /* detection is only be successful if the expression of the numerator an denominator are the same
289 * (so boundtightening can be stronger than default) or we are going to provide estimators (there will be an auxvar)
317 * if univariate, then we also do inteval and reverseprop, so mark that the activities will be used for inteval
335 SCIPdebugMsg(scip, "detected quotient expression (%g * %p + %g) / (%g * %p + %g) + %g\n", a, (void*)xexpr,
450 /* if the expression is constant or the limit lies inside the domain, nothing can be propagated */
548 SCIP_Bool* branchinguseful, /**< pointer to store whether branching on the expression would improve the estimator */
622 /** helper method to compute estimator for the univariate case; the estimator is stored in a given rowprep */
635 SCIP_Bool* branchinguseful, /**< pointer to store whether branching on the expression would improve the estimator */
681 SCIP_CALL( estimateUnivariate(scip, lbx, ubx, gllbx, glubx, solx, a, b, c, d, e, &coef, &constant, overestimate, &local, branchinguseful, success) );
686 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "quot_%s_%lld", SCIPvarGetName(x), SCIPgetNLPs(scip));
696 * h^c(x,y) := \frac{1}{y} \left(\frac{x + \sqrt{\text{lbx}\cdot\text{ubx}}}{\sqrt{\text{lbx}} + \sqrt{\text{ubx}}}\right)^2
738 * x = y * z ≤ a * y + b * z + c. Note that b > 0 because of y > 0. The inequality is then transformed
739 * to x / b - a/b * y - c/b ≤ z, which results in a valid underestimator for x / y over the set
740 * {(x,y) | lbz ≤ x / y ≤ ubz}. Note that overestimating/underestimating the bilinear term with McCormick
744 * - 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$
745 * - 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
747 * If y < 0, swap and negate its bounds and compute the respective opposite estimator (and negate it).
767 SCIP_Bool* branchingusefulx, /**< pointer to store whether branching on x would improve the estimator */
768 SCIP_Bool* branchingusefuly, /**< pointer to store whether branching on y would improve the estimator */
818 /* as explained in the description of this method, overestimating/underestimating the bilinear term results in an
821 SCIPaddBilinMcCormick(scip, 1.0, lbz, ubz, solz, lby, uby, soly, !overestimate, &mccoefaux, &mccoefy, &mcconst,
882 /* if exactly one variable has been negated, then we have computed an underestimate/overestimate for the negated
924 SCIP_Bool* branchingusefulx, /**< pointer to store whether branching on x would improve the estimator */
925 SCIP_Bool* branchingusefuly, /**< pointer to store whether branching on y would improve the estimator */
1000 /* transform estimator Ax' + By'+ C = A(ax + b) + B (cy + d) + C = (Aa) x + (Bc) y + (C + Ab + Bd);
1008 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "quot_%s_%s_%lld", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]),
1135 SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, TRUE) );
1140 SCIP_CALL( estimateUnivariateQuotient(scip, sol, nlhdlrexprdata->numexpr, nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst,
1141 nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst, nlhdlrexprdata->constant, overestimate, rowprep,
1147 SCIP_CALL( estimateBivariateQuotient(scip, nlhdlrexprdata->numexpr, nlhdlrexprdata->denomexpr, SCIPgetExprAuxVarNonlinear(expr), sol,
1148 nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst, nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst,
1176 SCIP_CALL( SCIPgetExprRelAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
1178 SCIP_CALL( SCIPgetExprAbsAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
1182 SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, exprs, nexprs, violation, sol, addedbranchscores) );
1201 * we should not be called in this case, as we haven't said we would participate in this activity in detect
1229 * we should not be called in this case, as we haven't said we would participate in this activity in detect
1233 SCIPdebugMsg(scip, "call reverse propagation for expression (%g %p + %g) / (%g %p + %g) + %g bounds [%g,%g]\n",
1248 SCIP_CALL( SCIPtightenExprIntervalNonlinear(scip, nlhdlrexprdata->numexpr, result, infeasible, nreductions) );
1272 SCIP_CALL( SCIPincludeNlhdlrNonlinear(scip, &nlhdlr, NLHDLR_NAME, NLHDLR_DESC, NLHDLR_DETECTPRIORITY,
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
Definition: intervalarith.c:458
void SCIPintervalUnify(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:597
Definition: intervalarith.h:44
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1476
Definition: struct_scip.h:59
unsigned int SCIPgetExprNAuxvarUsesNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12897
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1706
static SCIP_DECL_NLHDLRDETECT(nlhdlrDetectQuotient)
Definition: nlhdlr_quotient.c:1050
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEEXPRDATA((*freeexprdata)))
Definition: nlhdlr.c:85
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: struct_var.h:198
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
Definition: cons_nonlinear.c:12920
static SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrQuotient)
Definition: nlhdlr_quotient.c:1022
void SCIPintervalIntersectEps(SCIP_INTERVAL *resultant, SCIP_Real eps, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:566
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:705
static void transformExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **target, SCIP_Real *coef, SCIP_Real *constant)
Definition: nlhdlr_quotient.c:131
static SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateQuotient)
Definition: nlhdlr_quotient.c:1120
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
Definition: intervalarith.c:409
Definition: type_lp.h:55
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
Definition: misc_rowprep.c:855
Definition: struct_nlhdlr.h:34
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
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:345
static SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataQuotient)
Definition: nlhdlr_quotient.c:1036
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1454
bilinear nonlinear handler
Definition: struct_sol.h:64
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:703
void SCIPintervalDiv(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:1142
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:532
static SCIP_RETCODE exprdataFree(SCIP *scip, SCIP_NLHDLREXPRDATA **nlhdlrexprdata)
Definition: nlhdlr_quotient.c:109
static SCIP_RETCODE detectExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool *success)
Definition: nlhdlr_quotient.c:170
SCIP_RETCODE SCIPincludeNlhdlrQuotient(SCIP *scip)
Definition: nlhdlr_quotient.c:1260
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
Definition: intervalarith.c:446
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:13687
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
Definition: intervalarith.c:435
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
Definition: intervalarith.c:393
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
Definition: intervalarith.c:401
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1103
Definition: type_retcode.h:33
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:558
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
Definition: misc_rowprep.c:714
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:752
quotient nonlinear handler
SCIP_Real SCIPgetCoefExprProduct(SCIP_EXPR *expr)
Definition: expr_product.c:2146
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)), SCIP_DECL_NLHDLREXITSEPA((*exitsepa)))
Definition: nlhdlr.c:123
Definition: struct_expr.h:95
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:624
static SCIP_DECL_NLHDLRINTEVAL(nlhdlrIntevalQuotient)
Definition: nlhdlr_quotient.c:1192
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:110
static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalauxQuotient)
Definition: nlhdlr_quotient.c:1080
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:1753
void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:833
static SCIP_RETCODE createRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR **vars, SCIP_Real *coefs, SCIP_Real constant, int nlinvars)
Definition: nlhdlr_quotient.c:491
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:70
SCIP_RETCODE SCIPtightenExprIntervalNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_INTERVAL newbounds, SCIP_Bool *cutoff, int *ntightenings)
Definition: cons_nonlinear.c:13169
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:429
void SCIPintervalDivScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1196
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:13045
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
Definition: intervalarith.c:421
SCIP_RETCODE SCIPaddExprsViolScoreNonlinear(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Real violscore, SCIP_SOL *sol, SCIP_Bool *success)
Definition: cons_nonlinear.c:13414
Definition: type_lp.h:56
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:13077
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:911
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
Definition: misc_rowprep.c:538
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12778
private functions of nonlinear handlers of nonlinear constraints
SCIPallocBlockMemory(scip, subsol))
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
Definition: misc_rowprep.c:748
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
Definition: misc_rowprep.c:906
Definition: objbenders.h:33
SCIP_INTERVAL SCIPgetExprBoundsNonlinear(SCIP *scip, SCIP_EXPR *expr)
Definition: cons_nonlinear.c:13113
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
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:565
static SCIP_DECL_NLHDLRREVERSEPROP(nlhdlrReversepropQuotient)
Definition: nlhdlr_quotient.c:1220
Definition: struct_misc.h:277
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRCOPYHDLR((*copy)))
Definition: nlhdlr.c:63