44#define NLHDLR_NAME "quotient"
45#define NLHDLR_DESC "nonlinear handler for quotient expressions"
46#define NLHDLR_DETECTPRIORITY 20
47#define NLHDLR_ENFOPRIORITY 20
53#define infty2infty(infty1, infty2, val) ((val) >= (infty1) ? (infty2) : (val))
62struct SCIP_NlhdlrExprData
101 (*nlhdlrexprdata)->numexpr = numexpr;
102 (*nlhdlrexprdata)->numcoef = numcoef;
103 (*nlhdlrexprdata)->numconst = numconst;
104 (*nlhdlrexprdata)->denomexpr = denomexpr;
105 (*nlhdlrexprdata)->denomcoef = denomcoef;
106 (*nlhdlrexprdata)->denomconst = denomconst;
107 (*nlhdlrexprdata)->constant = constant;
222 numexpr = children[1];
227 numexpr = children[0];
259 nomfac = sumcoefs[1] * prodcoef;
260 numconst = sumcoefs[0];
280 nomfac = sumcoefs[0] * prodcoef;
281 numconst = sumcoefs[1];
288 if( denomexpr !=
NULL && numexpr !=
NULL )
294 SCIPdebugMsg(
scip,
"detected numerator (%g * %p + %g) and denominator (%g * %p + %g)\n",
a, (
void*)xexpr,
b,
340 b = nomfac *
b + numconst;
344 SCIPdebugMsg(
scip,
"detected quotient expression (%g * %p + %g) / (%g * %p + %g) + %g\n",
a, (
void*)xexpr,
345 b,
c, (
void*)yexpr, d, e);
390 if(
a*d -
b*
c == 0.0 )
401 for(
i = 0;
i < 2; ++
i )
460 if(
a*d -
b*
c == 0.0 || (bnds.
inf <
a /
c && bnds.
sup >
a /
c) )
467 for(
i = 0;
i < 2; ++
i )
565 assert(lbx <= solx && solx <= ubx);
572 *branchinguseful =
TRUE;
576 singularity = -d /
c;
579 *local = gllbx != lbx || glubx != ubx;
585 isinleftpart = (ubx < singularity);
586 monincreasing = (
a * d -
b *
c > 0.0);
589 if( monincreasing == (overestimate == isinleftpart) )
598 lbeval = (
a * lbx +
b) / (
c * lbx + d) + e;
599 ubeval = (
a * ubx +
b) / (
c * ubx + d) + e;
602 *coef = (ubeval - lbeval) / (ubx - lbx);
603 *constant = ubeval - (*coef) * ubx;
609 soleval = (
a * solx +
b) / (
c * solx + d) + e;
612 *coef = (
a * d -
b *
c) /
SQR(d +
c * solx);
613 *constant = soleval - (*coef) * solx;
619 *branchinguseful =
FALSE;
687 solx =
MIN(
MAX(solx, lbx), ubx);
690 SCIP_CALL(
estimateUnivariate(
scip, lbx, ubx, gllbx, glubx, solx,
a,
b,
c, d, e, &coef, &constant, overestimate, &local, branchinguseful, success) );
732 tmp1 = sqrt(lbx * ubx) + solx;
733 tmp2 =
SQR(sqrt(lbx) + sqrt(ubx)) * soly;
736 *coefx = 2.0 * tmp1 / tmp2;
737 *coefy = -
SQR(tmp1) / (tmp2 * soly);
738 *constant = 2.0 * sqrt(lbx * ubx) * tmp1 / tmp2;
784 assert(lbx <= solx && solx <= ubx);
785 assert(lby <= soly && soly <= uby);
786 assert(lbz <= solz && solz <= ubz);
794 *branchingusefulx =
TRUE;
795 *branchingusefuly =
TRUE;
817 overestimate = !overestimate;
821 if( lbx < 0.0 && 0.0 < ubx )
830 SCIPaddBilinMcCormick(
scip, 1.0, lbz, ubz, solz, lby, uby, soly, !overestimate, &mccoefaux, &mccoefy, &mcconst,
838 *coefx = 1.0 / mccoefaux;
839 *coefy = -mccoefy / mccoefaux;
840 *constant = -mcconst / mccoefaux;
854 overestimate = !overestimate;
861 if( uby * solx - lbx * soly + lbx * lby <= lby * solx - ubx * soly + ubx * uby )
864 *coefy = -lbx / (lby * uby);
865 *constant = lbx / uby;
870 *coefy = -ubx / (lby * uby);
871 *constant = ubx / lby;
878 hcGradCut(lbx, ubx, solx, soly, coefx, coefy, constant);
881 *branchingusefuly =
FALSE;
894 if( negatedx != negatedy )
898 *constant = -(*constant);
995 solx =
MIN(
MAX(solx, lbx), ubx);
996 soly =
MIN(
MAX(soly, lby), uby);
997 solz =
MIN(
MAX(solz, lbz), ubz);
1002 MIN(
c * lby,
c * uby) + d,
MAX(
c * lby,
c * uby) + d,
1003 lbz, ubz,
a * solx +
b,
c * soly + d, solz, overestimate, &coefs[0], &coefs[1], &constant,
1004 branchingusefulx, branchingusefuly, success) );
1012 constant += coefs[0] *
b + coefs[1] * d + e;
1073 if( (*nlhdlrexprdata)->numexpr == (*nlhdlrexprdata)->denomexpr )
1079 *enforcing |= *participating;
1113 nomval = nlhdlrexprdata->numcoef * solvalx + nlhdlrexprdata->numconst;
1114 denomval = nlhdlrexprdata->denomcoef * solvaly + nlhdlrexprdata->denomconst;
1117 *auxvalue = (denomval != 0.0) ? nlhdlrexprdata->constant + nomval / denomval :
SCIP_INVALID;
1141 *addedbranchscores =
FALSE;
1146 if( nlhdlrexprdata->numexpr == nlhdlrexprdata->denomexpr )
1150 nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst, nlhdlrexprdata->constant, overestimate, rowprep,
1151 &branchingusefulx, success) );
1157 nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst, nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst,
1158 nlhdlrexprdata->constant, overestimate, rowprep,
1159 &branchingusefulx, &branchingusefuly, success) );
1172 if( addbranchscores )
1178 if( branchingusefulx )
1179 exprs[nexprs++] = nlhdlrexprdata->numexpr;
1180 if( branchingusefuly )
1181 exprs[nexprs++] = nlhdlrexprdata->denomexpr;
1184#ifndef BRSCORE_ABSVIOL
1213 if( nlhdlrexprdata->numexpr != nlhdlrexprdata->denomexpr )
1220 solx =
MAX(
MIN(solx, ubx), lbx);
1222 for(
c = (overestimate ? 0 : 1);
c < (underestimate ? 2 : 1); ++
c )
1233 nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst, nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst, nlhdlrexprdata->constant,
1234 &coef, &constant,
c == 0, &local, &branchinguseful, &success) );
1237 if( !success || local || branchinguseful )
1277 assert(nlhdlrexprdata->numexpr == nlhdlrexprdata->denomexpr);
1284 *interval =
intEvalQuotient(
scip, bnds, nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst,
1285 nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst, nlhdlrexprdata->constant);
1305 assert(nlhdlrexprdata->numexpr == nlhdlrexprdata->denomexpr);
1307 SCIPdebugMsg(
scip,
"call reverse propagation for expression (%g %p + %g) / (%g %p + %g) + %g bounds [%g,%g]\n",
1308 nlhdlrexprdata->numcoef, (
void*)nlhdlrexprdata->numexpr, nlhdlrexprdata->numconst,
1309 nlhdlrexprdata->denomcoef, (
void*)nlhdlrexprdata->denomexpr, nlhdlrexprdata->denomconst,
1310 nlhdlrexprdata->constant, bounds.inf, bounds.sup);
1315 nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst, nlhdlrexprdata->constant);
constraint handler for nonlinear constraints specified by algebraic expressions
#define SCIP_INTERVAL_INFINITY
unsigned int SCIPgetExprNAuxvarUsesNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPgetExprRelAuxViolationNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Real auxvalue, SCIP_SOL *sol, SCIP_Real *viol, SCIP_Bool *violunder, SCIP_Bool *violover)
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPtightenExprIntervalNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_INTERVAL newbounds, SCIP_Bool *cutoff, int *ntightenings)
SCIP_RETCODE SCIPaddExprsViolScoreNonlinear(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Real violscore, SCIP_SOL *sol, SCIP_Bool *success)
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
SCIP_INTERVAL SCIPgetExprBoundsNonlinear(SCIP *scip, SCIP_EXPR *expr)
SCIP_RETCODE SCIPgetExprAbsAuxViolationNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Real auxvalue, SCIP_SOL *sol, SCIP_Real *viol, SCIP_Bool *violunder, SCIP_Bool *violover)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
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)
SCIP_RETCODE SCIPincludeNlhdlrQuotient(SCIP *scip)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPsetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx, void *val)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
SCIP_Real SCIPgetCoefExprProduct(SCIP_EXPR *expr)
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
SCIP_Real SCIPgetConstantExprSum(SCIP_EXPR *expr)
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
void SCIPcaptureExpr(SCIP_EXPR *expr)
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
void SCIPintervalIntersectEps(SCIP_INTERVAL *resultant, SCIP_Real eps, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
void SCIPintervalUnify(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
struct SCIP_Interval SCIP_INTERVAL
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalDiv(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalDivScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr,)
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
void SCIPnlhdlrSetSollinearize(SCIP_NLHDLR *nlhdlr,)
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)),)
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr,)
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)
void SCIPnlhdlrSetProp(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINTEVAL((*inteval)),)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
int SCIPsolGetIndex(SCIP_SOL *sol)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetHugeValue(SCIP *scip)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPcleanupRowprep2(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefbound, SCIP_Bool *success)
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
SCIP_Bool SCIProwprepIsLocal(SCIP_ROWPREP *rowprep)
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
private functions of nonlinear handlers of nonlinear constraints
#define NLHDLR_DETECTPRIORITY
#define NLHDLR_ENFOPRIORITY
bilinear nonlinear handler
static void hcGradCut(SCIP_Real lbx, SCIP_Real ubx, SCIP_Real solx, SCIP_Real soly, SCIP_Real *coefx, SCIP_Real *coefy, SCIP_Real *constant)
static void transformExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **target, SCIP_Real *coef, SCIP_Real *constant)
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)
static SCIP_RETCODE exprdataFree(SCIP *scip, SCIP_NLHDLREXPRDATA **nlhdlrexprdata)
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)
static SCIP_INTERVAL reversepropQuotient(SCIP_INTERVAL bnds, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e)
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)
static SCIP_INTERVAL intEvalQuotient(SCIP *scip, SCIP_INTERVAL bnds, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e)
#define infty2infty(infty1, infty2, val)
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)
static SCIP_RETCODE createRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR **vars, SCIP_Real *coefs, SCIP_Real constant, int nlinvars)
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)
static SCIP_RETCODE detectExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool *success)
quotient nonlinear handler
preparation of a linear inequality to become a SCIP_ROW
struct SCIP_Expr SCIP_EXPR
struct SCIP_RowPrep SCIP_ROWPREP
#define SCIP_DECL_NLHDLREVALAUX(x)
#define SCIP_DECL_NLHDLRESTIMATE(x)
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
#define SCIP_NLHDLR_METHOD_SEPABOTH
#define SCIP_DECL_NLHDLRCOPYHDLR(x)
#define SCIP_NLHDLR_METHOD_ACTIVITY
#define SCIP_DECL_NLHDLRSOLLINEARIZE(x)
#define SCIP_DECL_NLHDLRFREEEXPRDATA(x)
#define SCIP_DECL_NLHDLRDETECT(x)
struct SCIP_Nlhdlr SCIP_NLHDLR
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
#define SCIP_DECL_NLHDLRREVERSEPROP(x)
#define SCIP_DECL_NLHDLRINTEVAL(x)
enum SCIP_Retcode SCIP_RETCODE