All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
cons_bivariate.c
Go to the documentation of this file.
17 * @brief constraint handler for bivariate nonlinear constraints \f$\textrm{lhs} \leq f(x,y) + c z \leq \textrm{rhs}\f$
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40 #define CONSHDLR_DESC "constraint handler for constraints of the form lhs <= f(x,y) + c*z <= rhs where f(x,y) is a bivariate function"
42 #define CONSHDLR_ENFOPRIORITY -55 /**< priority of the constraint handler for constraint enforcing */
43 #define CONSHDLR_CHECKPRIORITY -3600000 /**< priority of the constraint handler for checking feasibility */
44 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
45 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
46 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
48 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
49 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
50 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
51 #define CONSHDLR_DELAYPRESOL FALSE /**< should presolving method be delayed, if other presolvers found reductions? */
52 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
57 #define INITLPMAXVARVAL 1000.0 /**< maximal absolute value of variable for still generating a linearization cut at that point in initlp */
59 #define QUADCONSUPGD_PRIORITY 5000 /**< priority of the constraint handler for upgrading of quadratic constraints */
60 #define NONLINCONSUPGD_PRIORITY 10000 /**< priority of the constraint handler for upgrading of nonlinear constraints */
62 /* activate the following define to get output on number of bivariate constraints for each convexity-type during INITSOL */
97 unsigned int mayincreasez:1; /**< whether z can be increased without harming other constraints */
98 unsigned int maydecreasez:1; /**< whether z can be decreased without harming other constraints */
102 SCIP_EXPRGRAPHNODE* exprgraphnode; /**< node in expression graph corresponding to bivariate function */
104 SEPADATA_CONVEXCONCAVE sepaconvexconcave; /**< separation data for convex-concave constraints */
112 SCIP_Real mincutefficacysepa; /**< minimal efficacy of a cut in order to add it to relaxation during separation */
113 SCIP_Real mincutefficacyenfo; /**< minimal target efficacy of a cut in order to add it to relaxation during enforcement (may be ignored) */
114 SCIP_Real cutmaxrange; /**< maximal range (maximal coef / minimal coef) of a cut in order to be added to LP */
116 int maxproprounds; /**< limit on number of propagation rounds for a single constraint within one round of SCIP propagation */
117 int ninitlprefpoints; /**< number of reference points in each direction where to compute linear support for envelope in LP initialization */
118 SCIP_Bool enfocutsremovable; /**< are cuts added during enforcement removable from the LP in the same node? */
128 SCIP_Bool isremovedfixings; /**< whether variable fixations have been removed from the expression graph */
129 SCIP_Bool ispropagated; /**< whether the bounds on the variables in the expression graph have been propagated */
132 SCIP_NODE* lastenfolpnode; /**< the node for which enforcement was called the last time (and some constraint was violated) */
193 /* if right hand side is finite, then a tightening in the lower bound of coef*linvar is of interest */
201 /* if left hand side is finite, then a tightening in the upper bound of coef*linvar is of interest */
208 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->z, eventtype, conshdlrdata->linvareventhdlr, (SCIP_EVENTDATA*)&consdata->ispropagated, &consdata->eventfilterpos) );
245 /* if right hand side is finite, then a tightening in the lower bound of coef*linvar is of interest */
253 /* if left hand side is finite, then a tightening in the upper bound of coef*linvar is of interest */
260 SCIP_CALL( SCIPdropVarEvent(scip, consdata->z, eventtype, conshdlrdata->linvareventhdlr, (SCIP_EVENTDATA*)&consdata->ispropagated, consdata->eventfilterpos) );
290 SCIPvarGetName(SCIPeventGetVar(event)), SCIPeventGetOldbound(event), SCIPeventGetNewbound(event));
333 SCIP_CALL( SCIPcatchVarEvent(conshdlrdata->scip, (SCIP_VAR*)var, SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_VARFIXED, conshdlrdata->nonlinvareventhdlr, (SCIP_EVENTDATA*)varnode, NULL) );
334 SCIPdebugMessage("catch boundchange events on new expression graph variable <%s>\n", SCIPvarGetName(var_));
338 -infty2infty(SCIPinfinity(conshdlrdata->scip), INTERVALINFTY, -MIN(SCIPvarGetLbLocal(var_), SCIPvarGetUbLocal(var_))), /*lint !e666*/
339 +infty2infty(SCIPinfinity(conshdlrdata->scip), INTERVALINFTY, MAX(SCIPvarGetLbLocal(var_), SCIPvarGetUbLocal(var_))) /*lint !e666*/
369 SCIP_CALL( SCIPdropVarEvent(conshdlrdata->scip, var_, SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_VARFIXED, conshdlrdata->nonlinvareventhdlr, (SCIP_EVENTDATA*)varnode, -1) );
370 SCIPdebugMessage("drop boundchange events on expression graph variable <%s>\n", SCIPvarGetName(var_));
399 SCIP_CALL( SCIPlockVarCons(scip, var, cons, !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
403 SCIP_CALL( SCIPlockVarCons(scip, var, cons, !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
430 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
434 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
447 SCIP_Bool* isupgraded /**< buffer to store whether the constraint has been upgraded (and deleted) */
479 if( consdata->z != NULL && !SCIPvarIsActive(consdata->z) && SCIPvarGetStatus(consdata->z) != SCIP_VARSTATUS_MULTAGGR )
521 * in the latter case, we just do nothing, which may not be most efficient, but should still work
639 /* mark that variables in constraint should not be multiaggregated (bad for bound tightening and branching) */
710 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, coefs, &nvars, varssize, &constant, &requsize, TRUE) );
732 SCIP_CALL( SCIPexprgraphReplaceVarByLinearSum(conshdlrdata->exprgraph, var, nvars, coefs, (void**)vars, constant) );
803 /* project point onto box if from LP or very close to bounds to avoid eval error when function is not defined slightly outside bounds */
831 SCIP_CALL( SCIPexprintEval(conshdlrdata->exprinterpreter, consdata->f, xyvals, &consdata->activity) );
869 SCIP_CALL( SCIPexprintGrad(conshdlrdata->exprinterpreter, consdata->f, xyvals, TRUE, &val, grad) );
914 SCIP_CONS** maxviolcon /**< buffer to store constraint with largest violation, or NULL if solution is feasible */
952 /** setup vred(s;x0,y0,ylb,yub) for a given f(x,y) for computing a convex-concave underestimator
953 * vred(s;x0,y0,ylb,yub) = (yub-y0)/(yub-ylb) f((yub-ylb)/(yub-y0)x0 - (y0-ylb)/(yub-y0)*s, ylb) + (y0-ylb)/(yub-ylb) f(s,yub)
977 assert(SCIPexprGetOperator(SCIPexprtreeGetRoot(f)) != SCIP_EXPR_VARIDX); /* substitute cannot substitute the root node, but f should not be a single variable anyway */
979 /* setup vred(s;x0,y0,ylb,yub) for computing a convex-concave underestimator in the case where y is not at one of its bounds
980 * vred(s;x0,y0,ylb,yub) = (yub-y0)/(yub-ylb) f((yub-ylb)/(yub-y0)x0 - (y0-ylb)/(yub-y0)*s, ylb) + (y0-ylb)/(yub-ylb) f(s,yub)
994 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &e5, SCIP_EXPR_DIV, e3, e4) ); /* x0(yub-ylb)/(yub-y0) */
1008 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &e6, SCIP_EXPR_DIV, e3, e4) ); /* s(y0-ylb)/(yub-y0) */
1037 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &e5, SCIP_EXPR_DIV, e3, e4) ); /* (yub-y0)/(yub-ylb) */
1042 SCIP_CALL( SCIPexprCreateLinear(SCIPblkmem(scip), &e6, 1, &e1, &minusone, 1.0) ); /* 1 - (yub-y0)/(yub-ylb) */
1102 /* setup f(x,yfixed) for computing a convex-concave underestimator in the case where y is at one of its bounds */
1103 SCIP_CALL( SCIPexprtreeCopy(SCIPblkmem(scip), &consdata->sepaconvexconcave.f_yfixed, consdata->f) );
1124 /* setup vred(s;x0,y0,ylb,yub) for computing a convex-concave underestimator in the case where y is not at one of its bounds
1125 * vred(s;x0,y0,ylb,yub) = (yub-y0)/(yub-ylb) f((yub-ylb)/(yub-y0)x0 - (y0-ylb)/(yub-y0)*s, ylb) + (y0-ylb)/(yub-ylb) f(s,yub)
1160 SCIP_CALL( SCIPexprtreeCreate(SCIPblkmem(scip), &consdata->sepaconvexconcave.f_neg_swapped, minusf, 2, 0, NULL) );
1168 /* setup -f(y, xfixed) for computing a convex-concave overestimator in the case where x is at on of it's bounds */
1169 SCIP_CALL( SCIPexprtreeCopy(SCIPblkmem(scip), &consdata->sepaconvexconcave.f_neg_swapped_yfixed, consdata->sepaconvexconcave.f_neg_swapped) );
1178 SCIP_CALL( SCIPexprtreeSubstituteVars(consdata->sepaconvexconcave.f_neg_swapped_yfixed, subst) );
1188 SCIP_CALL( SCIPexprintCompile(exprinterpreter, consdata->sepaconvexconcave.f_neg_swapped_yfixed) );
1190 /* setup vred(s;y0,x0,xlb,xub) for computing a convex-concave underestimator in the case where x is not at one of its bounds */
1191 SCIP_CALL( initSepaDataCreateVred(scip, &consdata->sepaconvexconcave.vred_neg_swapped, consdata->sepaconvexconcave.f_neg_swapped) );
1192 SCIP_CALL( SCIPexprintCompile(exprinterpreter, consdata->sepaconvexconcave.vred_neg_swapped) );
1282 /** solves an equation f'(s) = constant for a univariate convex or concave function f with respect to bounds on s
1283 * if there is no s between the bounds such that f'(s) = constant, then it returns the closest bound (and still claims success)
1355 /* SCIPdebugMessage("s = %.20g [%g,%g] f(s) = %g grad = %g (perturbed by %g)\n", s, lb, ub, fval, grad, iter <= 65 ? 0.1 / (1<<iter) : 1e-20); */
1377 /* if f cannot be two times differentiated at s, take the Hessian from another point close by */
1390 * (multiply instead of divide by hess for the case that hess is zero and since only the sign matters
1413 /* if grad is targetvalue (w.r.t. feastol) and step length would be almost 0, then we are also done */
1442 /** generates a cut for f(x,y) + c*z <= rhs with f(x,y) being convex or 1-convex with x or y fixed or convex-concave with y fixed
1451 SCIP_Bool newxy, /**< whether the last evaluation of f(x,y) with the expression interpreter was at (x0, y0) */
1482 (consdata->convextype == SCIP_BIVAR_1CONVEX_INDEFINITE && (SCIPisEQ(scip, SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x)) || SCIPisEQ(scip, SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y)))) ||
1483 (consdata->convextype == SCIP_BIVAR_CONVEX_CONCAVE && SCIPisEQ(scip, SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y))) );
1506 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_linearization_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip));
1508 SCIP_CALL( SCIPcreateEmptyRowCons(scip, row, SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), rhs, FALSE, FALSE /* modifiable */, TRUE /* removable */) );
1518 /** Given three points, constructs coefficient of equation for hyperplane generated by these three points.
1559 /** given a convex (concave, resp.) bivariate function, computes an over- (under-, resp.) estimating hyperplane
1567 SCIP_Bool doover, /**< whether to compute an overestimator (TRUE) or an underestimator (FALSE) */
1572 SCIP_Bool* success /**< pointer to indicate whether coefficients where successfully computed */
1623 if( SCIPisInfinity(scip, -xlb) || SCIPisInfinity(scip, xub) || SCIPisInfinity(scip, -ylb) || SCIPisInfinity(scip, yub) )
1625 SCIPdebugMessage("skip estimating hyperplane since <%s> or <%s> is unbounded\n", SCIPvarGetName(x), SCIPvarGetName(y));
1631 SCIPdebugMessage("skip estimating hyperplane since both <%s> and <%s> are fixed\n", SCIPvarGetName(x), SCIPvarGetName(y));
1659 if( !SCIPisFinite(p1val) || SCIPisInfinity(scip, REALABS(p1val)) || !SCIPisFinite(p4val) || SCIPisInfinity(scip, REALABS(p4val)) )
1682 if( !SCIPisFinite(p1val) || SCIPisInfinity(scip, REALABS(p1val)) || !SCIPisFinite(p2val) || SCIPisInfinity(scip, REALABS(p2val)) )
1702 /* if we want an underestimator, flip f(x,y), i.e., do as if we compute an overestimator for -f(x,y) */
1716 if( !SCIPisFinite(p1val) || SCIPisInfinity(scip, REALABS(p1val)) || !SCIPisFinite(p2val) || SCIPisInfinity(scip, REALABS(p2val)) ||
1717 ! SCIPisFinite(p3val) || SCIPisInfinity(scip, REALABS(p3val)) || !SCIPisFinite(p4val) || SCIPisInfinity(scip, REALABS(p4val)) )
1727 * Since we assume that f is convex, we then know that all points (x,y,f(x,y)) are below this hyperplane, i.e.,
1736 getAlphaBetaGammaDelta(p1[0], p1[1], p1val, p2[0], p2[1], p2val, p3[0], p3[1], p3val, &alpha, &beta, &gamma_, &delta);
1737 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p1[0] + beta * p1[1] + gamma_ * p1val, delta));
1738 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p2[0] + beta * p2[1] + gamma_ * p2val, delta));
1739 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p3[0] + beta * p3[1] + gamma_ * p3val, delta));
1741 /* if hyperplane through p1,p2,p3 does not overestimate f(p4), then it must be the other variant */
1747 getAlphaBetaGammaDelta(p1[0], p1[1], p1val, p3[0], p3[1], p3val, p4[0], p4[1], p4val, &alpha, &beta, &gamma_, &delta);
1748 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p1[0] + beta * p1[1] + gamma_ * p1val, delta));
1749 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p3[0] + beta * p3[1] + gamma_ * p3val, delta));
1750 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p4[0] + beta * p4[1] + gamma_ * p4val, delta));
1752 /* if hyperplane through p1,p3,p4 does not overestimate f(p2), then it must be the other variant */
1761 getAlphaBetaGammaDelta(p1[0], p1[1], p1val, p2[0], p2[1], p2val, p4[0], p4[1], p4val, &alpha, &beta, &gamma_, &delta);
1764 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p1[0] + beta * p1[1] + gamma_ * p1val, delta));
1765 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p2[0] + beta * p2[1] + gamma_ * p2val, delta));
1766 assert(SCIPisInfinity(scip, delta) || SCIPisFeasLE(scip, alpha * p3[0] + beta * p3[1] + gamma_ * p3val, delta));
1767 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p4[0] + beta * p4[1] + gamma_ * p4val, delta));
1771 getAlphaBetaGammaDelta(p2[0], p2[1], p2val, p3[0], p3[1], p3val, p4[0], p4[1], p4val, &alpha, &beta, &gamma_, &delta);
1774 assert(SCIPisInfinity(scip, delta) || SCIPisFeasLE(scip, alpha * p1[0] + beta * p1[1] + gamma_ * p1val, delta));
1775 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p2[0] + beta * p2[1] + gamma_ * p2val, delta));
1776 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p3[0] + beta * p3[1] + gamma_ * p3val, delta));
1777 assert(SCIPisInfinity(scip, delta) || SCIPisFeasEQ(scip, alpha * p4[0] + beta * p4[1] + gamma_ * p4val, delta));
1781 SCIPdebugMessage("alpha = %g, beta = %g, gamma = %g, delta = %g\n", alpha, beta, gamma_, delta);
1825 SCIP_CALL( generateEstimatingHyperplane(scip, exprinterpreter, consdata->f, TRUE, x0y0, &coefs[0], &coefs[1], &constant, &success) );
1834 SCIP_CALL( SCIPcreateRowCons(scip, row, SCIPconsGetHdlr(cons), "bivaroveresthyperplanecut", 0, NULL, NULL, consdata->lhs - constant, SCIPinfinity(scip), TRUE, FALSE, TRUE) );
1842 SCIPdebugMessage("failed to compute overestimator for all-convex constraint <%s>\n", SCIPconsGetName(cons));
1934 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e1, SCIPexprtreeGetRoot(f)) ); /* e1 = f(x,y) */
1937 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &tmp2, SCIP_EXPR_CONST, 1.0 - 1.0 / t) ); /* tmp2 = 1-1/t */
1938 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &tmp, SCIP_EXPR_MUL, tmp, tmp2) ); /* tmp = (1-1/t)*s */
1941 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &tmp2, SCIP_EXPR_CONST, 1/t*xval) ); /* tmp2 = 1/t*xval */
1942 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &tmp, SCIP_EXPR_PLUS, tmp, tmp2) ); /* tmp = 1/t*xval + (1-1/t)*s */
1946 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &subst[1], SCIP_EXPR_CONST, ylb) ); /* tmp = ylb */
1948 assert(SCIPexprGetOperator(e1) != SCIP_EXPR_VARIDX); /* substitute cannot substitute the root node, but f should not be a single variable anyway */
1949 SCIP_CALL( SCIPexprSubstituteVars(SCIPblkmem(scip), e1, subst) ); /* e1 = f(1/t*xval + (1-1/t)*s, ylb) */
1955 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e2, SCIPexprtreeGetRoot(f)) ); /* e2 = f(x,y) */
1961 assert(SCIPexprGetOperator(e2) != SCIP_EXPR_VARIDX); /* substitute cannot substitute the root node, but f should not be a single variable anyway */
1968 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &e1, SCIP_EXPR_MUL, e1, tmp) ); /* e1 = t * f(1/t*xval+(1-1/t)*s,ylb) */
1970 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &tmp, SCIP_EXPR_CONST, 1.0 - t) ); /* tmp = 1 - t */
1971 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &e2, SCIP_EXPR_MUL, e2, tmp) ); /* e2 = (1-t) * f(s, yub) */
1987 SCIP_CALL( solveDerivativeEquation(scip, exprinterpreter, vredtree, 0.0, slb, sub, &sval, success) );
2055 SCIPdebugMessage("Parallel: r=%g in [%g,%g], s=%g in [%g,%g], f(r,ylb)=%g, f(xlb,s)=%g\n",rval,xlb,xub,sval,ylb,yub,frval,fsval);
2056 SCIPdebugMessage("(r,ylb)=(%g,%g), (s,yub)=(%g,%g), vredval=%g\n",rval,ylb,sval,yub,*convenvvalue);
2070 SCIPdebugMessage("Parallel: cutcoeff[0]=%g, cutcoeff[1]=%g, cutcoeff[2]=%g, cutcoeff[3]=%g\n",cutcoeff[0]/cutcoeff[2],cutcoeff[1]/cutcoeff[2],cutcoeff[2]/cutcoeff[2],cutcoeff[3]/cutcoeff[2]);
2160 SCIPdebugMessage("%s[%g,%g] = %g %s[%g,%g] = %g\n", SCIPvarGetName(x), xlb, xub, xval, SCIPvarGetName(y), ylb, yub, yval);
2170 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &tmp, SCIP_EXPR_CONST, yval-ylb) ); /* tmp = yval-ylb */
2171 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_DIV, tmp, expr) ); /* expr = (yval-ylb) / t */
2175 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_PLUS, expr, tmp) ); /* expr = ylb + (yval-ylb) / t */
2179 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &subst[0], SCIP_EXPR_CONST, xlb) ); /* subst[0] = xlb */
2181 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e1, SCIPexprtreeGetRoot(f)) ); /* e1 = f(x,y) */
2182 assert(SCIPexprGetOperator(e1) != SCIP_EXPR_VARIDX); /* expr substitute vars cannot substitute the root node, but f should not be a single variable anyway */
2183 SCIP_CALL( SCIPexprSubstituteVars(SCIPblkmem(scip), e1, subst) ); /* e1 = f(xlb, ylb + (yval-ylb)/t) */
2192 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr1, SCIP_EXPR_MINUS, tmp, expr1) ); /* expr1 = 1-t */
2196 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MUL, expr2, tmp) ); /* expr2 = xlb * t */
2198 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MINUS, tmp, expr2) ); /* expr2 = xval - xlb * t */
2200 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_DIV, expr2, expr1) ); /* expr = (xval-t*xlb)/(1-t) */
2203 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &subst[1], SCIP_EXPR_CONST, ylb) ); /* subst[0] = ylb */
2205 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e2, SCIPexprtreeGetRoot(f)) ); /* e2 = f(x,y) */
2206 assert(SCIPexprGetOperator(e2) != SCIP_EXPR_VARIDX); /* expr substitute vars cannot substitute the root node, but f should not be a single variable anyway */
2207 SCIP_CALL( SCIPexprSubstituteVars(SCIPblkmem(scip), e2, subst) ); /* e2 = f((xval-xlb*t)/(1-t), ylb) */
2215 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr1, SCIP_EXPR_MUL, expr, e1) ); /* expr1 = t * e1*/
2219 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_MINUS, tmp, expr) ); /* expr = 1 - t */
2220 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MUL, expr, e2) ); /* expr2 = (1-t) * e2 */
2231 SCIP_CALL( solveDerivativeEquation(scip, exprinterpreter, vredtree, 0.0, tlb, tub, &tval, success) );
2297 if( !SCIPisFinite(grad_sval[0]) || !SCIPisFinite(grad_rval[0]) || SCIPisInfinity(scip, REALABS(MIN(grad_sval[0],grad_rval[0]))) )
2299 /* FIXME maybe it is sufficient to have one of them finite, using that one for the MIN below? */
2310 SCIPdebugMessage("LowerLeft: r=%g in [%g,%g], s=%g in [%g,%g], f(s,ylb)=%g, f(xlb,r)=%g\n",rval,xlb,xub,sval,ylb,yub,fsval,frval);
2311 SCIPdebugMessage("(s,ylb)=(%g,%g) (xlb,r)=(%g,%g) t=%g, vredval=%g\n",sval,ylb,xlb,rval,tval,*convenvvalue);
2312 SCIPdebugMessage("LowerLeft: cutcoeff[0]=%g, cutcoeff[1]=%g,cutcoeff[2]=%g,cutcoeff[3]=%g\n",cutcoeff[0],cutcoeff[1],cutcoeff[2],cutcoeff[3]);
2321 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &tmp, SCIP_EXPR_CONST, yval-yub) ); /* tmp = yval-yub*/
2322 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_DIV, tmp, expr) ); /* expr = (yval-yub) / t */
2326 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_PLUS, expr, tmp) ); /* expr = yub + (yval-yub)/t */
2330 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &subst[0], SCIP_EXPR_CONST, xub) ); /* tmp = xub */
2332 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e1, SCIPexprtreeGetRoot(f)) ); /* e1 = f(x,y) */
2334 SCIP_CALL( SCIPexprSubstituteVars(SCIPblkmem(scip), e1, subst) ); /* e1 = f(xub, yub + (yval-yub)/t) */
2342 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr1, SCIP_EXPR_MINUS, tmp, expr1) ); /* expr1 = 1-t */
2346 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MUL, expr2, tmp) ); /* expr2 = xub * t */
2348 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MINUS, tmp, expr2) ); /* expr2 = xval - xub * t */
2350 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_DIV, expr2, expr1) ); /* expr = (xval-t*xub)/(1-t) */
2353 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &subst[1], SCIP_EXPR_CONST, yub) ); /* tmp = yub */
2355 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e2, SCIPexprtreeGetRoot(f)) ); /* e2 = f(x,y) */
2357 SCIP_CALL( SCIPexprSubstituteVars(SCIPblkmem(scip), e2, subst) ); /* e2 = f((xval-t*xub)/(1-t), yub) */
2364 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr1, SCIP_EXPR_MUL, e1, expr) ); /* expr1 = t * e1*/
2368 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_MINUS, tmp, expr) ); /* expr = 1-t */
2369 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MUL, e2, expr) ); /* expr2 = (1-t) * e2*/
2381 SCIP_CALL( solveDerivativeEquation(scip, exprinterpreter, vredtree, 0.0, tlb, tub, &tval, success) );
2453 if( !SCIPisFinite(grad_sval[0]) || !SCIPisFinite(grad_rval[0]) || SCIPisInfinity(scip, REALABS(MIN(grad_sval[0],grad_rval[0]))) )
2455 /* FIXME maybe it is sufficient to have one of them finite, using that one for the MIN below? */
2467 SCIPdebugMessage("UpperRight: r=%g in [%g,%g], s=%g in [%g,%g], f(r,yub)=%g, f(xub,s)=%g\n",rval,xlb,xub,sval,ylb,yub,frval,fsval);
2468 SCIPdebugMessage("(s,yub)=(%g,%g) (xub,r)=(%g,%g) t=%g, vredval=%g\n",sval,yub,xub,rval,tval,*convenvvalue);
2469 SCIPdebugMessage("UpperRight: cutcoeff[0]=%g, cutcoeff[1]=%g, cutcoeff[2]=%g, cutcoeff[3]=%g\n",cutcoeff[0],cutcoeff[1],cutcoeff[2],cutcoeff[3]);
2565 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &tmp, SCIP_EXPR_CONST, xval-xub) ); /* tmp = xval-xub */
2566 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_DIV, tmp, expr) ); /* expr = (xval-xub)/t */
2570 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_PLUS, expr, tmp) ); /* expr = xub + (xval-xub)/t */
2574 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &subst[1], SCIP_EXPR_CONST, ylb) ); /* subst[1] = ylb */
2576 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e1, SCIPexprtreeGetRoot(f)) ); /* e1 = f(x,y) */
2578 SCIP_CALL( SCIPexprSubstituteVars(SCIPblkmem(scip), e1, subst) ); /* e1 = f(xub + (xval-xub)/t, ylb) */
2587 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr1, SCIP_EXPR_MINUS, tmp, expr1) ); /* expr1 = 1-t */
2591 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MUL, expr2, tmp) ); /* expr2 = ylb * t */
2593 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MINUS, tmp, expr2) ); /* expr2 = yval - ylb * t */
2595 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_DIV, expr2, expr1) ); /* expr = (yval-t*ylb)/(1-t) */
2598 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &subst[0], SCIP_EXPR_CONST, xub) ); /* subst[0] = xub */
2600 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e2, SCIPexprtreeGetRoot(f)) ); /* e2 = f(x,y) */
2602 SCIP_CALL( SCIPexprSubstituteVars(SCIPblkmem(scip), e2, subst) ); /* e2 = f(xub, (yval-t*ylb)/(1-t)) */
2610 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr1, SCIP_EXPR_MUL, e1, expr) ); /* expr1 = t * e1*/
2615 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_MINUS, tmp, expr) ); /* expr = 1-t */
2616 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MUL, e2, expr) ); /* expr2 = (1-t) * e2*/
2629 SCIP_CALL( solveDerivativeEquation(scip, exprinterpreter, vredtree, 0.0, tlb, tub, &tval, success) );
2692 if( !SCIPisFinite(grad_sval[0]) || !SCIPisFinite(grad_rval[0]) || SCIPisInfinity(scip, REALABS(MIN(grad_sval[0],grad_rval[0]))) )
2694 /* FIXME maybe it is sufficient to have one of them finite, using that one for the MIN below? */
2706 SCIPdebugMessage("LowerRight: t=%g in [%g,%g], r=%g in [%g,%g], s=%g in [%g,%g]\n",tval,tlb,tub,rval,xlb,xub,sval,ylb,yub);
2707 SCIPdebugMessage("LowerRight: (r,ylb)=(%g,%g) (xub,sval)=(%g,%g) vredval=%g\n",rval,ylb,xub,sval,*convenvvalue);
2708 SCIPdebugMessage("LowerRight: cutcoeff[0]=%g, cutcoeff[1]=%g,cutcoeff[2]=%g,cutcoeff[3]=%g\n",cutcoeff[0]/cutcoeff[2],cutcoeff[1]/cutcoeff[2],cutcoeff[2]/cutcoeff[2],cutcoeff[3]/cutcoeff[2]);
2718 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &tmp, SCIP_EXPR_CONST, xval-xlb) ); /* tmp = xval-xlb */
2719 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_DIV, tmp, expr) ); /* expr = (xval-xlb)/lambda */
2723 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_PLUS, expr, tmp) ); /* expr = xlb + (xval-xlb)/t */
2727 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &subst[1], SCIP_EXPR_CONST, yub) ); /* subst[1] = yub */
2729 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e1, SCIPexprtreeGetRoot(f)) ); /* e1 = f(x,y) */
2731 SCIP_CALL( SCIPexprSubstituteVars(SCIPblkmem(scip), e1, subst) ); /* e1 = f(xlb + (xval-xlb)/t, yub) */
2740 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr1, SCIP_EXPR_MINUS, tmp, expr1) ); /* expr1 = 1-t */
2744 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MUL, expr2, tmp) ); /* expr2 = yub * t */
2746 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MINUS, tmp, expr2) ); /* expr2 = yval - yub * t */
2748 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_DIV, expr2, expr1) ); /* expr = (yval-t*yub)/(1-t) */
2751 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &subst[0], SCIP_EXPR_CONST, xlb) ); /* subst[0] = xlb */
2753 SCIP_CALL( SCIPexprCopyDeep(SCIPblkmem(scip), &e2, SCIPexprtreeGetRoot(f)) ); /* e2 = f(x,y) */
2754 SCIP_CALL( SCIPexprSubstituteVars(SCIPblkmem(scip), e2, subst) ); /* e2 = f( xlb , (yval-t*yub)/(1-t) ) */
2762 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr1, SCIP_EXPR_MUL, e1, expr) ); /* expr1 = t * e1*/
2767 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_MINUS, tmp, expr) ); /* expr = 1-t */
2768 SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr2, SCIP_EXPR_MUL, e2, expr) ); /* expr2 = (1-t) * e2*/
2781 SCIP_CALL( solveDerivativeEquation(scip, exprinterpreter, vredtree, 0.0, tlb, tub, &tval, success) );
2844 if( !SCIPisFinite(grad_sval[0]) || !SCIPisFinite(grad_rval[0]) || SCIPisInfinity(scip, REALABS(MIN(grad_rval[0],grad_sval[0]))) )
2846 /* FIXME maybe it is sufficient to have one of them finite, using that one for the MIN below? */
2857 SCIPdebugMessage("UpperLeft: r=%g in [%g,%g], s=%g in [%g,%g], f(r,yub)=%g, f(xlb,s)=%g\n",rval,xlb,xub,sval,ylb,yub,frval,fsval);
2858 SCIPdebugMessage("t=%g in [%g,%g], (r,yub)=(%g,%g) (xlb,sval)=(%g,%g) vredval=%g\n",tval,tlb,tub,rval,yub,xlb,sval,*convenvvalue);
2859 SCIPdebugMessage("UpperLeft: cutcoeff[0]=%g, cutcoeff[1]=%g,cutcoeff[2]=%g,cutcoeff[3]=%g\n",cutcoeff[0]/cutcoeff[2],cutcoeff[1]/cutcoeff[2],cutcoeff[2]/cutcoeff[2],cutcoeff[3]/cutcoeff[2]);
2866 /** generates a linear underestimator for f(x,y) with f(x,y) being STRICTLY convex in x and concave in y
2867 * generate coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)
2996 SCIPdebugMessage("cannot evaluate function or derivative in (xval,ylb), also after perturbation\n");
3034 if( !SCIPisFinite(gradylb[0]) || !SCIPisFinite(gradyub[0]) || !SCIPisFinite(fvalylb) || !SCIPisFinite(fvalyub) ||
3053 cutcoeff[0]/cutcoeff[2], cutcoeff[1]/cutcoeff[2], cutcoeff[2]/cutcoeff[2], cutcoeff[3]/cutcoeff[2]);
3091 SCIPdebug( SCIP_CALL( SCIPexprtreePrintWithNames(f_yfixed, SCIPgetMessagehdlr(scip), NULL) ) );
3095 SCIP_CALL( solveDerivativeEquation(scip, exprinterpreter, f_yfixed, grad[0], xlb, xub, &xtilde, success) );
3102 /* if we could not find an xtilde such that f'(xtilde,yub) = f'(xval,ylb), then probably because f'(x,yub) is constant
3103 * in this case, choose xtilde from {xlb, xub} such that it maximizes f'(xtilde, yub) - grad[0]*xtilde
3108 SCIPdebugMessage("couldn't solve deriv equ, compare f(%g,%g) - %g*%g = %g and f(%g,%g) - %g*%g = %g\n",
3141 SCIPdebugMessage("alpha: %g, beta: %g, gamma: %g, delta: %g\n", cutcoeff[0], cutcoeff[1], cutcoeff[2], cutcoeff[3]);
3176 SCIP_CALL( solveDerivativeEquation(scip, exprinterpreter, f_yfixed, grad[0], xlb, xub, &xtilde, success) );
3183 /* if we could not find an xtilde such that f'(xtilde,ylb) = f'(xval,yub), then probably because f'(x,ylb) is constant
3184 * in this case, choose xtilde from {xlb, xub} such that it maximizes f'(xtilde, yub) - grad[0]*xtilde
3189 SCIPdebugMessage("couldn't solve deriv equ, compare f(%g,%g) - %g*%g = %g and f(%g,%g) - %g*%g = %g\n",
3222 SCIPdebugMessage("alpha: %g, beta: %g, gamma: %g, delta: %g\n", cutcoeff[0], cutcoeff[1], cutcoeff[2], cutcoeff[3]);
3284 SCIP_CALL( solveDerivativeEquation(scip, exprinterpreter, vred, 0.0, slb, sub, &sval, success) );
3347 SCIPdebugMessage("Parallel: r=%g s=%g in [%g,%g], y in [%g,%g], f(r,ylb)=%g, f(xlb,s)=%g\n",rval,sval,xlb,xub,ylb,yub,frval,fsval);
3348 SCIPdebugMessage("(r,ylb)=(%g,%g), (s,yub)=(%g,%g), vredval=%g\n",rval,ylb,sval,yub,*convenvvalue);
3363 SCIPdebugMessage("Parallel: cutcoeff[0]=%g, cutcoeff[1]=%g,cutcoeff[2]=%g,cutcoeff[3]=%g\n",cutcoeff[0]/cutcoeff[2],cutcoeff[1]/cutcoeff[2],cutcoeff[2]/cutcoeff[2],cutcoeff[3]/cutcoeff[2]);
3371 /** generates a cut for one side of lhs <= f(x,y) + c*z <= rhs with f(x,y) being convex in x and concave in y */
3415 SCIP_CALL( generateEstimatingHyperplane(scip, exprinterpreter, consdata->f, TRUE, xyref, &coefs[0], &coefs[1], &constant, &success) );
3423 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s_overesthyperplanecut_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip));
3424 SCIP_CALL( SCIPcreateRowCons(scip, row, SCIPconsGetHdlr(cons), cutname, 0, NULL, NULL, consdata->lhs - constant, SCIPinfinity(scip), TRUE, FALSE, TRUE) );
3437 /* f is strictly concave in y -> can compute overestimator by applying generateConvexConcaveUnderstimator on -f(y,x) */
3442 SCIP_CALL( generateConvexConcaveUnderestimator(scip, exprinterpreter, consdata->sepaconvexconcave.f_neg_swapped, consdata->sepaconvexconcave.f_neg_swapped_yfixed, consdata->sepaconvexconcave.vred_neg_swapped, xyref_, cutcoeff, &dummy, &success) );
3459 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s_convexconcaveoverest_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip));
3460 SCIP_CALL( SCIPcreateEmptyRowCons(scip, row, SCIPconsGetHdlr(cons), cutname, consdata->lhs - cutcoeff[3]/cutcoeff[2], SCIPinfinity(scip),
3481 SCIP_CALL( generateEstimatingHyperplane(scip, exprinterpreter, consdata->f, FALSE, xyref, &coefs[0], &coefs[1], &constant, &success) );
3489 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s_underesthyperplanecut_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip));
3490 SCIP_CALL( SCIPcreateRowCons(scip, row, SCIPconsGetHdlr(cons), cutname, 0, NULL, NULL, -SCIPinfinity(scip), consdata->rhs - constant, TRUE, FALSE, TRUE) );
3501 /* f is strictly convex in x -> can compute underestimator by applying generateConvexConcaveUnderstimator */
3502 assert(!consdata->sepaconvexconcave.linearinx); /* generateConvexConcaveUnderestimator assumes that if f is strictly convex in x */
3504 SCIP_CALL( generateConvexConcaveUnderestimator(scip, exprinterpreter, consdata->f, consdata->sepaconvexconcave.f_yfixed, consdata->sepaconvexconcave.vred, xyref, cutcoeff, &dummy, &success) );
3522 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s_convexconcaveunderest_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip));
3523 SCIP_CALL( SCIPcreateEmptyRowCons(scip, row, SCIPconsGetHdlr(cons), cutname, -SCIPinfinity(scip), consdata->rhs + cutcoeff[3]/cutcoeff[2],
3538 /** computes an underestimating hyperplane for functions that are convex in x and y if the point to cut off lies on the boundary */
3626 /** generate a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y and the point to cut off lies on the boundary
3627 * generate coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)
3735 SCIP_CALL( lifting(scip,exprinterpreter,f,xval,yval,xlb,xlb,ylb,yub,-1,cutcoeff,convenvvalue,success) );
3752 SCIP_CALL( lifting(scip,exprinterpreter,f,xval,yval,xlb,xub,ylb,ylb,-1,cutcoeff,convenvvalue,success) );
3777 SCIP_CALL( lifting(scip,exprinterpreter,f,xval,yval,xub,xub,ylb,yub,1,cutcoeff,convenvvalue,success) );
3794 SCIP_CALL( lifting(scip,exprinterpreter,f,xval,yval,xlb,xub,yub,yub,1,cutcoeff,convenvvalue,success) );
3808 SCIPerrorMessage("Tries to compute underestimator for a point at the boundary. But point is not on the boundary!\n");
3812 /** generates a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y but indefinite
3813 * This is for the case where the cone of the concave directions is (R_+ x R_-) union (R_\- x R_+).
3891 if( !SCIPisFinite(fval_xub_ylb) || SCIPisInfinity(scip, REALABS(fval_xub_ylb)) || !SCIPisFinite(fval_xlb_yub) || SCIPisInfinity(scip, REALABS(fval_xlb_yub)) )
3938 SCIP_CALL( generateOrthogonal_lx_ly_Underestimator(scip, exprinterpreter, f, xyref, all_cutcoeff[0], &all_convenvvalue[0], &all_success[0]) );
3940 SCIP_CALL( generateUnderestimatorParallelYFacets(scip, exprinterpreter, f, xyref, all_cutcoeff[1], &all_convenvvalue[1], &all_success[1]) );
3952 SCIP_CALL( generateOrthogonal_lx_ly_Underestimator(scip, exprinterpreter, fswapped, xyref_, all_cutcoeff[0], &all_convenvvalue[0], &all_success[0]) ); /*lint !e644*/
3954 SCIP_CALL( generateUnderestimatorParallelYFacets(scip, exprinterpreter, fswapped, xyref_, all_cutcoeff[1], &all_convenvvalue[1], &all_success[1]) );
4011 /** generates a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y but indefinite
4012 * This is for the case where the cone of the concave directions is (R_+ x R_+) union (R_- x R_-).
4021 * Generates coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)
4095 if( !SCIPisFinite(fval_xlb_ylb) || SCIPisInfinity(scip, REALABS(fval_xlb_ylb)) || !SCIPisFinite(fval_xub_yub) || SCIPisInfinity(scip, REALABS(fval_xub_yub)) )
4110 if( SCIPisGE( scip, fval_xlb_ylb+(yub-ylb)*grad_xlb_ylb[1], fval_xub_yub+(xlb-xub)*grad_xub_yub[0] ) )
4137 SCIP_CALL( generateOrthogonal_lx_uy_Underestimator(scip, exprinterpreter, f, xyref, all_cutcoeff[0], &all_convenvvalue[0], &all_success[0]) );
4139 SCIP_CALL( generateUnderestimatorParallelYFacets(scip, exprinterpreter, f, xyref, all_cutcoeff[1], &all_convenvvalue[1], &all_success[1]) );
4150 SCIP_CALL( generateOrthogonal_lx_uy_Underestimator(scip, exprinterpreter, fswapped, xyref_, all_cutcoeff[0], &all_convenvvalue[0], &all_success[0]) ); /*lint !e644*/
4152 SCIP_CALL( generateUnderestimatorParallelYFacets(scip, exprinterpreter, fswapped, xyref_, all_cutcoeff[1], &all_convenvvalue[1], &all_success[1]) );
4209 /** generates a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y but indefinite
4210 * generate coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)
4267 if( SCIPisInfinity(scip, -xlb) || SCIPisInfinity(scip, xub) || SCIPisInfinity(scip, -ylb) || SCIPisInfinity(scip, yub) )
4269 SCIPdebugMessage("skip underestimate for 1-convex indefinite constraint <%s> since <%s> or <%s> is unbounded\n", SCIPconsGetName(cons), SCIPvarGetName(x), SCIPvarGetName(y));
4280 if( SCIPisFeasEQ(scip,xyref[0],xlb) || SCIPisFeasEQ(scip,xyref[0],xub) || SCIPisFeasEQ(scip,xyref[1],ylb) || SCIPisFeasEQ(scip,xyref[1],yub) )
4282 SCIP_CALL( generate1ConvexIndefiniteUnderestimatorAtBoundary(scip, exprinterpreter, f, xyref, cutcoeff, &convenvvalue, &success) );
4305 SCIP_CALL( generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternA(scip, exprinterpreter, f, xyref, cutcoeff, &convenvvalue, &success) );
4311 SCIP_CALL( generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternB(scip, exprinterpreter, f, xyref, cutcoeff, &convenvvalue, &success) );
4348 SCIP_CALL( SCIPcreateEmptyRowCons(scip, row, SCIPconsGetHdlr(cons), "1ConvexUnderest", -SCIPinfinity(scip), rhs,
4350 SCIP_CALL( SCIPaddVarToRow(scip, *row, SCIPexprtreeGetVars(consdata->f)[0], cutcoeff[0] / cutcoeff[2]) );
4351 SCIP_CALL( SCIPaddVarToRow(scip, *row, SCIPexprtreeGetVars(consdata->f)[1], cutcoeff[1] / cutcoeff[2]) );
4402 SCIPdebugMessage("generate cut for constraint <%s> with %s hand side violated by %g\n", SCIPconsGetName(cons), violside == SCIP_SIDETYPE_LEFT ? "left" : "right", violside == SCIP_SIDETYPE_LEFT ? consdata->lhsviol : consdata->rhsviol);
4408 SCIPdebugPrintf(", %s = %g with bounds [%g, %g]", SCIPvarGetName(consdata->z), SCIPgetSolVal(scip, sol, consdata->z), SCIPvarGetLbLocal(consdata->z), SCIPvarGetUbLocal(consdata->z));
4478 SCIPdebugMessage("cut coefficients for constraint <%s> have very large range: mincoef = %g maxcoef = %g\n", SCIPconsGetName(cons), mincoef, maxcoef);
4480 /* if minimal coefficient is given by z, then give up (probably the maximal coefficient is the problem) */
4498 if( ((coef > 0.0 && violside == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && violside == SCIP_SIDETYPE_LEFT)) && !SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)) )
4500 SCIPdebugMessage("eliminate coefficient %g for <%s> = %g [%g, %g]\n", coef, SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
4507 if( ((coef < 0.0 && violside == SCIP_SIDETYPE_RIGHT) || (coef > 0.0 && violside == SCIP_SIDETYPE_LEFT)) && !SCIPisInfinity(scip, SCIPvarGetUbLocal(var)) )
4509 SCIPdebugMessage("eliminate coefficient %g for <%s> = %g [%g, %g]\n", coef, SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
4543 SCIPdebugMessage("drop row for constraint <%s> because range of coefficients is too large: mincoef = %g, maxcoef = %g -> range = %g\n",
4551 SCIPdebugMessage("drop row for constraint <%s> because of very large side: %g\n", SCIPconsGetName(cons), violside == SCIP_SIDETYPE_LEFT ? -SCIProwGetLhs(*row) : SCIProwGetRhs(*row));
4560 * i.e., if side == RIGHT, then returns whether constraint function is convex w.r.t. local bounds
4604 return (side == SCIP_SIDETYPE_RIGHT && SCIPisEQ(scip, SCIPvarGetLbLocal(xy[1]), SCIPvarGetUbLocal(xy[1]))) ||
4605 (side == SCIP_SIDETYPE_LEFT && SCIPisEQ(scip, SCIPvarGetLbLocal(xy[0]), SCIPvarGetUbLocal(xy[0])));
4638 SCIPinfoMessage(scip, NULL, "splot [%g:%g] [%g:%g] ", SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x), SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y));
4640 SCIPinfoMessage(scip, NULL, "%+g", side == SCIP_SIDETYPE_LEFT ? consdata->lhs : consdata->rhs);
4642 SCIPinfoMessage(scip, NULL, ", %g", SCIPisInfinity(scip, SCIProwGetRhs(row)) ? -SCIProwGetLhs(row) : -SCIProwGetRhs(row));
4654 SCIPinfoMessage(scip, NULL, ", \"< echo '%g %g %g'\" with circles", SCIPgetSolVal(scip, sol, x), SCIPgetSolVal(scip, sol, y), consdata->activity);
4675 SCIP_Real* bestefficacy /**< buffer to store best efficacy of a cut that was added to the LP, if found; or NULL if not of interest */
4707 if( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
4713 violside = SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT;
4716 SCIP_CALL( generateCut(scip, conshdlrdata->exprinterpreter, conss[c], sol, violside, conshdlrdata->cutmaxrange, &row) );
4732 /* in difference to SCIPgetCutEfficacy, we scale by norm only if the norm is > 1.0 this avoid finding cuts
4733 * efficient which are only very slightly violated CPLEX does not seem to scale row coefficients up too
4734 * also we use infinity norm, since that seem to be the usual scaling strategy in LP solvers (equilibrium
4758 /* if cut is strong enough or it's weak but we separate on a convex function and accept weak cuts there, add cut to SCIP */
4760 (inenforcement && SCIPisGT(scip, efficacy, SCIPgetRelaxFeastolFactor(scip) > 0.0 ? SCIPepsilon(scip) : SCIPfeastol(scip)) && isConvexLocal(scip, conss[c], violside))) &&
4769 SCIPdebugMessage("cut for constraint <%s> is infeasible -> cutoff.\n", SCIPconsGetName(conss[c]));
4774 SCIPdebugMessage("added cut with efficacy %g for constraint <%s> violated by %g\n", efficacy, SCIPconsGetName(conss[c]), MAX(consdata->lhsviol, consdata->rhsviol));
4796 * others are only checked and enforced if we are still feasible or have not found a separating cut yet
4805 /** processes the event that a new primal solution has been found adds linearizations of all-convex constraints to the cutpool */
4839 /* we are only interested in solution coming from some heuristic other than trysol, but not from the tree
4840 * the reason for ignoring trysol solutions is that they may come from an NLP solve in sepalp, where we already added linearizations,
4849 SCIPdebugMessage("catched new sol event %x from heur <%s>; have %d conss\n", SCIPeventGetType(event), SCIPheurGetName(SCIPsolGetHeur(sol)), nconss);
4864 SCIP_CALL( generateLinearizationCut(scip, conshdlrdata->exprinterpreter, conss[c], x0y0, TRUE, &row) );
4881 /** registers unfixed variables in nonlinear terms of violated constraints as external branching candidates
4882 * We score the variables by their gap between the convex envelope and the bivariate function in the current (x,y).
4883 * This value is given by the constraint violation, since we assume that cuts have been generated which support
4908 SCIPdebugMessage("cons <%s> violation: %g %g\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol);
4922 /* regarding left hand side, we are concave in x and convex in y, so branch on x, if not fixed */
4925 SCIPdebugMessage("register variable x = <%s>[%g,%g] in convex-concave <%s> with violation %g %g\n", SCIPvarGetName(xy[0]), SCIPvarGetLbLocal(xy[0]), SCIPvarGetUbLocal(xy[0]), SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol);
4932 /* regarding right hand side, we are convex in x and concave in y, so branch on y, if not fixed */
4935 SCIPdebugMessage("register variable y = <%s>[%g,%g] in convex-concave <%s> with violation %g %g\n", SCIPvarGetName(xy[1]), SCIPvarGetLbLocal(xy[1]), SCIPvarGetUbLocal(xy[1]), SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol);
4946 if( SCIPisEQ(scip, SCIPvarGetLbLocal(xy[0]), SCIPvarGetUbLocal(xy[0])) || SCIPisEQ(scip, SCIPvarGetLbLocal(xy[1]), SCIPvarGetUbLocal(xy[1])) )
4952 SCIPdebugMessage("register variable x = <%s>[%g,%g] in 1-convex <%s> with violation %g %g\n", SCIPvarGetName(xy[0]), SCIPvarGetLbLocal(xy[0]), SCIPvarGetUbLocal(xy[0]), SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol);
4959 SCIPdebugMessage("register variable y = <%s>[%g,%g] in 1-convex <%s> with violation %g %g\n", SCIPvarGetName(xy[1]), SCIPvarGetLbLocal(xy[1]), SCIPvarGetUbLocal(xy[1]), SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol);
4978 SCIPdebugMessage("register variable x = <%s>[%g,%g] in allconvex <%s> with violation %g %g\n", SCIPvarGetName(xy[0]), SCIPvarGetLbLocal(xy[0]), SCIPvarGetUbLocal(xy[0]), SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol);
4985 SCIPdebugMessage("register variable y = <%s>[%g,%g] in allconvex <%s> with violation %g %g\n", SCIPvarGetName(xy[1]), SCIPvarGetLbLocal(xy[1]), SCIPvarGetUbLocal(xy[1]), SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol);
4996 /** registers a nonlinear variable from a violated constraint as branching candidate that has a large absolute value in the LP relaxation */
5025 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
5051 /** enforces violated bivariate constraints where both nonlinear variables can be assumed to be fixed
5083 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
5090 /* if all variables are fixed (at least up to epsilson), then the activity of the nonlinear part should be bounded */
5112 SCIPdebugMessage("Linear constraint with one variable: %g <= %g <%s> <= %g\n", lhs, coef, SCIPvarGetName(consdata->z), rhs);
5136 SCIPdebugMessage("Linear constraint is a bound: %g <= <%s> <= %g\n", lhs, SCIPvarGetName(consdata->z), rhs);
5206 SCIPdebugMessage("found <%s> infeasible due to domain propagation for variable <%s>\n", cons != NULL ? SCIPconsGetName(cons) : "???", SCIPvarGetName(var)); /*lint !e585*/
5211 if( !SCIPisInfinity(scip, -SCIPintervalGetInf(bounds)) && SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR )
5217 SCIPdebugMessage("found <%s> infeasible due to domain propagation for variable <%s>\n", cons != NULL ? SCIPconsGetName(cons) : "???", SCIPvarGetName(var)); /*lint !e585*/
5223 SCIPdebugMessage("tightened lower bound of variable <%s> in constraint <%s> to %g\n", SCIPvarGetName(var), cons != NULL ? SCIPconsGetName(cons) : "???", SCIPvarGetLbLocal(var)); /*lint !e585*/
5229 if( !SCIPisInfinity(scip, SCIPintervalGetSup(bounds)) && SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR )
5235 SCIPdebugMessage("found <%s> infeasible due to domain propagation for variable <%s>\n", cons != NULL ? SCIPconsGetName(cons) : "???", SCIPvarGetName(var)); /*lint !e585*/
5241 SCIPdebugMessage("tightened upper bound of variable <%s> in constraint <%s> to %g\n", SCIPvarGetName(var), cons != NULL ? SCIPconsGetName(cons) : "???", SCIPvarGetUbLocal(var)); /*lint !e585*/
5260 SCIP_Bool* redundant /**< buffer where to store whether constraint has been found to be redundant */
5288 /* extend interval by epsilon to avoid cutoff in forward propagation if constraint is only almost feasible */
5290 -infty2infty(SCIPinfinity(scip), INTERVALINFTY, -consdata->lhs+SCIPepsilon(scip)), /*lint !e666*/
5291 +infty2infty(SCIPinfinity(scip), INTERVALINFTY, consdata->rhs+SCIPepsilon(scip)) ); /*lint !e666*/
5301 -infty2infty(SCIPinfinity(scip), INTERVALINFTY, -MIN(SCIPvarGetLbLocal(consdata->z), SCIPvarGetUbLocal(consdata->z))), /*lint !e666*/
5302 +infty2infty(SCIPinfinity(scip), INTERVALINFTY, MAX(SCIPvarGetLbLocal(consdata->z), SCIPvarGetUbLocal(consdata->z)))); /*lint !e666*/
5316 SCIPdebugMessage("found constraint <%s> to be redundant: sides: [%g, %g], activity: [%g, %g]\n",
5317 SCIPconsGetName(cons), consdata->lhs, consdata->rhs, SCIPintervalGetInf(consactivity), SCIPintervalGetSup(consactivity));
5325 SCIPdebugMessage("found constraint <%s> to be infeasible; sides: [%g, %g], activity: [%g, %g], infeas: %g\n",
5326 SCIPconsGetName(cons), consdata->lhs, consdata->rhs, SCIPintervalGetInf(consactivity), SCIPintervalGetSup(consactivity),
5327 MAX(consdata->lhs - SCIPintervalGetSup(consactivity), SCIPintervalGetInf(consactivity) - consdata->rhs)); /*lint !e666*/
5349 -infty2infty(SCIPinfinity(scip), INTERVALINFTY, -MIN(SCIPvarGetLbLocal(consdata->z), SCIPvarGetUbLocal(consdata->z))), /*lint !e666*/
5350 +infty2infty(SCIPinfinity(scip), INTERVALINFTY, MAX(SCIPvarGetLbLocal(consdata->z), SCIPvarGetUbLocal(consdata->z)))); /*lint !e666*/
5357 SCIPexprgraphTightenNodeBounds(conshdlrdata->exprgraph, consdata->exprgraphnode, tmp, 0.05, &cutoff);
5360 SCIPdebugMessage("found constraint <%s> infeasible%s\n", SCIPconsGetName(cons), SCIPinProbing(scip) ? " in probing" : "");
5377 int* ndelconss /**< buffer where to increase if a constraint was deleted (locally) due to redundancy */
5435 SCIPdebugMessage("starting domain propagation round %d for %d constraints\n", roundnr, nconss);
5441 * @todo could give FALSE if no linear variable in the constraints had been relaxed since last time
5443 SCIP_CALL( SCIPexprgraphPropagateVarBounds(conshdlrdata->exprgraph, INTERVALINFTY, roundnr == 0, &domainerror) );
5490 SCIPdebugMessage("backward propagation found problem infeasible%s\n", SCIPinProbing(scip) ? " in probing" : "");
5502 SCIP_CALL( propagateBoundsTightenVar(scip, vars[i], SCIPexprgraphGetNodeBounds(varnodes[i]), NULL, &propresult, nchgbds) );
5516 /** Given a solution where every bivariate constraint is either feasible or can be made feasible by
5517 * moving the linear variable, construct the corresponding feasible solution and pass it to the trysol heuristic.
5518 * The method assumes that this is always possible and that not all constraints are feasible already.
5527 SCIP_Bool* success /**< buffer to store whether we succeeded to construct a solution that satisfies all provided constraints */
5602 SCIPdebugMessage("increase <%s> by %g to %g\n", SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var));
5632 SCIPdebugMessage("increase <%s> by %g to %g\n", SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var));
5645 if( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
5649 if( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) && !SCIPisSumLT(scip, SCIPgetSolTransObj(scip, newsol), SCIPgetUpperbound(scip)) )
5653 /* if we have a solution that should satisfy all nonlinear constraints and has a better objective than the current upper bound,
5657 SCIPdebugMessage("pass solution with objective value %g to trysol heuristic\n", SCIPgetSolTransObj(scip, newsol));
5669 * lhs <= xsqrcoef * x^2 + xlincoef * x + ysqrcoef * y^2 + ylincoef * y + bilincoef * x*y + zcoef * z <= rhs
5799 SCIP_CALL( SCIPexprCreateQuadratic(SCIPblkmem(scip), &e, 2, children, 0.0, (coefx != 0.0 || coefy != 0.0) ? lincoefs : NULL, nquadelems, quadelems) ); /*lint !e826*/
5821 SCIPdebugMessage("upgrading constraint <%s> to bivariate constraint <%s> with convexity type %d\n", SCIPconsGetName(srccons), name, convextype);
5836 /** creates expression tree for monomial of the form coef * x^p * y^q with x >= 0 and y >= 0 and checks its convexity type */
5869 *mult = coef < 0.0 ? -1.0 : 1.0; /* for the check, assume that monomial has positive coefficient */
5877 else if( (p > 1.0 && q > 1.0) || (p + q < 1.0 && ((p > 1.0 && q < 0.0) || (p < 0.0 && q > 1.0))) )
5919 assert(*convextype != SCIP_BIVAR_UNKNOWN); /* there should be no case where this can still happen */
5940 SCIP_CALL( SCIPexprCreateMonomial(SCIPblkmem(scip), &monomial, *mult*coef, 2, childidxs, exponents) );
5942 SCIP_CALL( SCIPexprCreatePolynomial(SCIPblkmem(scip), &e, 2, children, 1, &monomial, 0.0, FALSE) );
5951 /** creates bivariate constraint from monomial of the form coef * x^p * y^q with x >= 0 and y >= 0
5986 SCIP_CALL( createExprtreeFromMonomial(scip, x, y, coef, p, q, &exprtree, &mult, &convextype) );
6001 SCIPdebugMessage("upgrading monomial %g<%s>^%g<%s>^%g from constraint <%s> to bivariate constraint with convexity type %d\n", /*lint !e585*/
6002 coef, SCIPvarGetName(x), p, SCIPvarGetName(y), q, srccons != NULL ? SCIPconsGetName(srccons) : "??", convextype); /*lint !e585*/
6046 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
6092 /** deinitialization method of constraint handler (called before transformed problem is freed) */
6110 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
6125 /* reset may{in,de}creasez to FALSE in case some values are still set from a previous solve round */
6133 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
6173 assert(consdata->z == NULL || SCIPvarIsActive(consdata->z) || SCIPvarGetStatus(consdata->z) == SCIP_VARSTATUS_MULTAGGR);
6184 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
6279 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, (SCIP_EVENTDATA*)conshdlr, &conshdlrdata->newsoleventfilterpos) );
6301 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%4d left and %4d right bivariate constraints of type [%s]\n", nconvextypeslhs[c], nconvextypesrhs[c], typename);
6305 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "NOTE: the constraint handler for bivariate constraints is still experimental!\n");
6315 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
6335 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, (SCIP_EVENTDATA*)conshdlr, conshdlrdata->newsoleventfilterpos) );
6367 /* expression should have been removed from expression graph when constraint was deactivated */
6407 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
6409 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons),
6415 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
6465 * For a missing bound, we either reflect the other bound at 0.0 if finite and on the right side,
6516 SCIPvarGetLbGlobal(SCIPexprtreeGetVars(consdata->f)[0]), SCIPvarGetUbGlobal(SCIPexprtreeGetVars(consdata->f)[0]),
6518 SCIPvarGetLbGlobal(SCIPexprtreeGetVars(consdata->f)[1]), SCIPvarGetUbGlobal(SCIPexprtreeGetVars(consdata->f)[1])
6526 if( !SCIPisInfinity(scip, -consdata->lhs) && !unbounded[0] && !unbounded[1] && (ix == 0 || ix == nref-1) && (iy == 0 || iy == nref-1) )
6532 SCIP_CALL( generateOverestimatingHyperplaneCut(scip, conshdlrdata->exprinterpreter, conss[c], xy, &row1) ); /*lint !e613*/
6537 SCIP_CALL( generateLinearizationCut(scip, conshdlrdata->exprinterpreter, conss[c], xy, TRUE, &row2) ); /*lint !e613*/
6547 SCIP_CALL( generateConvexConcaveEstimator(scip, conshdlrdata->exprinterpreter, conss[c], xy, SCIP_SIDETYPE_LEFT, &row1) ); /*lint !e613*/
6552 SCIP_CALL( generateConvexConcaveEstimator(scip, conshdlrdata->exprinterpreter, conss[c], xy, SCIP_SIDETYPE_RIGHT, &row2) ); /*lint !e613*/
6559 if( !SCIPisInfinity(scip, -consdata->lhs) && !unbounded[0] && !unbounded[1] && (ix == 0 || ix == nref-1) && (iy == 0 || iy == nref-1) )
6565 SCIP_CALL( generateOverestimatingHyperplaneCut(scip, conshdlrdata->exprinterpreter, conss[c], xy, &row1) ); /*lint !e613*/
6569 SCIP_CALL( generate1ConvexIndefiniteUnderestimator(scip, conshdlrdata->exprinterpreter, conss[c], xy, &row2) ); /*lint !e613*/
6576 SCIPwarningMessage(scip, "initlp for convexity type %d not implemented\n", consdata->convextype);
6583 if( SCIPgetRowMaxCoef(scip, row1) / SCIPgetRowMinCoef(scip, row1) > conshdlrdata->cutmaxrange )
6585 SCIPdebugMessage("drop row1 for constraint <%s> because range of coefficients is too large: mincoef = %g, maxcoef = %g -> range = %g\n",
6586 SCIPconsGetName(conss[c]), SCIPgetRowMinCoef(scip, row1), SCIPgetRowMaxCoef(scip, row1), SCIPgetRowMaxCoef(scip, row1) / SCIPgetRowMinCoef(scip, row1)); /*lint !e613*/
6593 SCIPdebugMessage("drop row1 for constraint <%s> because of very large lhs: %g\n", SCIPconsGetName(conss[c]), SCIProwGetLhs(row1)); /*lint !e613*/
6600 if( SCIPgetRowMaxCoef(scip, row2) / SCIPgetRowMinCoef(scip, row2) > conshdlrdata->cutmaxrange )
6602 SCIPdebugMessage("drop row2 for constraint <%s> because range of coefficients is too large: mincoef = %g, maxcoef = %g -> range = %g\n",
6603 SCIPconsGetName(conss[c]), SCIPgetRowMinCoef(scip, row2), SCIPgetRowMaxCoef(scip, row2), SCIPgetRowMaxCoef(scip, row2) / SCIPgetRowMinCoef(scip, row2)); /*lint !e613*/
6610 SCIPdebugMessage("drop row2 for constraint <%s> because of very large rhs: %g\n", SCIPconsGetName(conss[c]), SCIProwGetLhs(row2)); /*lint !e613*/
6662 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, conshdlrdata->mincutefficacysepa, FALSE, result, NULL) );
6689 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, sol, conshdlrdata->mincutefficacysepa, FALSE, result, NULL) );
6728 * (maybe the LP does not think that the cuts we add are violated, or we do ECP on a high-dimensional convex function)
6729 * in this case, check if some limit is hit or SCIP should stop for some other reason and terminate enforcement by creating a dummy node
6730 * (in optimized more, returning SCIP_INFEASIBLE in *result would be sufficient, but in debug mode this would give an assert in scip.c)
6731 * the reason to wait for 100 rounds is to avoid calls to SCIPisStopped in normal runs, which may be expensive
6742 SCIP_CALL( SCIPcreateChild(scip, &child, 1.0, SCIPnodeGetEstimate(SCIPgetCurrentNode(scip))) );
6762 SCIPdebugMessage("enfolp with max violation %g in cons <%s>\n", maxviol, SCIPconsGetName(maxviolcons));
6775 * thus, in the latter case, we are also happy if the efficacy is at least, say, 75% of the maximal violation
6780 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, minefficacy, TRUE, &separateresult, &sepaefficacy) );
6783 SCIPdebugMessage("separation succeeded (bestefficacy = %g, minefficacy = %g, cutoff = %d)\n", sepaefficacy, minefficacy, separateresult == SCIP_CUTOFF);
6792 SCIPdebugMessage("separation failed (bestefficacy = %g < %g = minefficacy ); max viol: %g\n", sepaefficacy, minefficacy, maxviol);
6797 /* if sepastore can decrease LP feasibility tolerance, we can add cuts with efficacy in [eps, feastol] */
6798 leastpossibleefficacy = SCIPgetRelaxFeastolFactor(scip) > 0.0 ? SCIPepsilon(scip) : SCIPfeastol(scip);
6802 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, leastpossibleefficacy, TRUE, &separateresult, &sepaefficacy) );
6812 /* fallback 2: separation probably failed because of numerical difficulties with a convex constraint;
6813 * if noone declared solution infeasible yet and we had not even found a weak cut, try to resolve by branching
6819 /* fallback 3: all nonlinear variables in all violated constraints seem to be fixed -> treat as linear constraint in one variable */
6824 /* if the linear constraints are actually feasible, then adding them and returning SCIP_CONSADDED confuses SCIP when it enforces the new constraints again and nothing resolves the infeasiblity that we declare here
6825 * thus, we only add them if considered violated, and otherwise claim the solution is feasible (but print a warning)
6834 SCIPwarningMessage(scip, "could not enforce feasibility by separating or branching; declaring solution with viol %g as feasible\n", maxviol);
6840 SCIPdebugMessage("Could not find any usual branching variable candidate. Proposed variable <%s> with LP value %g for branching.\n", SCIPvarGetName(brvar), SCIPgetSolVal(scip, NULL, brvar));
6898 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
6901 /* if nonlinear variables are fixed, z should be propagated such that the constraint becomes feasible,
6904 if( consdata->z != NULL && !SCIPisRelEQ(scip, SCIPvarGetLbLocal(consdata->z), SCIPvarGetUbLocal(consdata->z)) )
6906 SCIP_CALL( SCIPaddExternBranchCand(scip, consdata->z, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) );
6915 SCIP_CALL( SCIPaddExternBranchCand(scip, var, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) );
6923 SCIPdebugMessage("All variables in violated constraints fixed (up to epsilon). Cannot find branching candidate. Forcing solution of LP.\n");
6961 if( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
6969 SCIPinfoMessage(scip, NULL, "violation: left hand side is violated by %.15g (scaled: %.15g)\n", consdata->lhs - consdata->activity, consdata->lhsviol);
6973 SCIPinfoMessage(scip, NULL, "violation: right hand side is violated by %.15g (scaled: %.15g)\n", consdata->activity - consdata->rhs, consdata->rhsviol);
6983 /* do not try to shift linear variables if activity is at infinity (leads to setting variable to infinity in solution, which is not allowed) */
6993 if( !(consdata->mayincreasez && consdata->zcoef > 0.0) && !(consdata->maydecreasez && consdata->zcoef < 0.0) )
7001 if( !(consdata->mayincreasez && consdata->zcoef < 0.0) && !(consdata->maydecreasez && consdata->zcoef > 0.0) )
7118 /* ensure we are called again if we are about to finish, since another presolver may still fix some variable and we cannot remove these fixations in exitpre anymore */
7188 SCIPdebugMessage("activate %scons <%s>\n", SCIPconsIsTransformed(cons) ? "transformed " : "", SCIPconsGetName(cons));
7191 SCIP_CALL( SCIPexprgraphAddExprtreeSum(conshdlrdata->exprgraph, 1, &consdata->f, NULL, &consdata->exprgraphnode, &exprtreeisnew) );
7194 /* mark that variables in constraint should not be multiaggregated (bad for bound tightening and branching) */
7231 SCIPdebugMessage("deactivate %scons <%s>\n", SCIPconsIsTransformed(cons) ? "transformed " : "", SCIPconsGetName(cons));
7259 SCIPdebugMessage("enable %scons <%s>\n", SCIPconsIsTransformed(cons) ? "transformed " : "", SCIPconsGetName(cons));
7290 SCIPdebugMessage("disable %scons <%s>\n", SCIPconsIsTransformed(cons) ? "transformed " : "", SCIPconsGetName(cons));
7388 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, consdata->z, &z, varmap, consmap, global, valid) );
7396 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, SCIPexprtreeGetVars(consdata->f)[0], &xy[0], varmap, consmap, global, valid) );
7402 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, SCIPexprtreeGetVars(consdata->f)[1], &xy[1], varmap, consmap, global, valid) );
7418 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
7455 /** constraint method of constraint handler which returns the number of variables (if possible) */
7552 x, y, z, coefxx, coefx, coefyy, coefy, coefxy, zcoef, SCIPgetLhsQuadratic(scip, cons), SCIPgetRhsQuadratic(scip, cons)) );
7569 /* check if we find at least one bilinear term for which we would create a bivariate constraint
7570 * thus, we search for a variable that has a square term and is involved in at least one bivariate term */
7604 /* require enough space here already, so we do not create and add aux vars that we cannot get rid of easily later */
7611 /* initial remaining quadratic constraint: take linear part and constraint sides from original constraint */
7613 SCIPgetNLinearVarsQuadratic(scip, cons), SCIPgetLinearVarsQuadratic(scip, cons), SCIPgetCoefsLinearVarsQuadratic(scip, cons),
7621 /* remember for each quadratic variable whether its linear and square part has been moved into a bivariate constraint */
7627 /* check for each bilinear term, whether we want to create a bivariate constraint for it and associated square terms */
7700 SCIP_CALL( SCIPdebugAddSolVal(scip, auxvar, coefxx * xval * xval + coefyy * yval * yval + coefxy * xval * yval + coefx * xval + coefy * yval) );
7717 /* complete quadcons: check for unmarked quadvarterms and add their linear and square coefficients to quadcons */
7726 * if the variable appears in a bilinear term, then this term should have been added to quadcons above, so the variable is there
7739 SCIP_CALL( SCIPaddQuadVarQuadratic(scip, quadcons, x, quadvarterms[i].lincoef, quadvarterms[i].sqrcoef) );
7766 SCIPgetNLinearVarsQuadratic(scip, cons), SCIPgetLinearVarsQuadratic(scip, cons), SCIPgetCoefsLinearVarsQuadratic(scip, cons),
7810 /* could also upgrade bivariate quadratic, but if we don't then node will appear in cons_quadratic later, from which we also upgrade...
7819 /* we are only interested in monomials that are not convex or concave, since cons_nonlinear can handle these the same was as we do */
7826 /* @todo we could also do some more complex reformulation for n-variate monomials, something better than what reformMonomial in cons_nonlinear is doing */
7838 /* so far only support variables as arguments @todo could allow more here, e.g., f(x)^pg(y)^q */
7848 if( SCIPisNegative(scip, SCIPvarGetLbGlobal(x)) || SCIPisNegative(scip, SCIPvarGetLbGlobal(y)) )
7855 SCIP_CALL( SCIPcreateVar(scip, &auxvar, name, SCIPexprgraphGetNodeBounds(node).inf, SCIPexprgraphGetNodeBounds(node).sup,
7861 SCIPexprGetMonomialCoef(monomial), expx, expy, -1.0, -SCIPexprgraphGetNodePolynomialConstant(node), -SCIPexprgraphGetNodePolynomialConstant(node)) );
7925 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBivariate, CONSHDLR_MAXPREROUNDS, CONSHDLR_DELAYPRESOL) );
7927 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropBivariate, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
7929 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpBivariate, consSepasolBivariate, CONSHDLR_SEPAFREQ,
7934 SCIP_CALL( SCIPincludeQuadconsUpgrade(scip, quadconsUpgdBivariate, QUADCONSUPGD_PRIORITY, FALSE, CONSHDLR_NAME) );
7937 SCIP_CALL( SCIPincludeNonlinconsUpgrade(scip, NULL, exprgraphnodeReformBivariate, NONLINCONSUPGD_PRIORITY, FALSE, CONSHDLR_NAME) );
7941 "minimal efficacy for a cut to be added to the LP during separation; overwrites separating/efficacy",
7945 "minimal target efficacy of a cut in order to add it to relaxation during enforcement (may be ignored)",
7946 &conshdlrdata->mincutefficacyenfo, FALSE, 2.0*SCIPfeastol(scip), 0.0, SCIPinfinity(scip), NULL, NULL) );
7949 "maximal coef range of a cut (maximal coefficient divided by minimal coefficient) in order to be added to LP relaxation",
7953 "whether to try to make solutions in check function feasible by shifting a linear variable (esp. useful if constraint was actually objective function)",
7957 "limit on number of propagation rounds for a single constraint within one round of SCIP propagation",
7961 "number of reference points in each direction where to compute linear support for envelope in LP initialization",
7969 "whether scaling of infeasibility is 'o'ff, by sup-norm of function 'g'radient, or by left/right hand 's'ide",
7973 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->linvareventhdlr), CONSHDLR_NAME"_boundchange", "signals a bound tightening in a linear variable to a bivariate constraint",
7978 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->nonlinvareventhdlr), CONSHDLR_NAME"_boundchange2", "signals a bound change in a nonlinear variable to the bivariate constraint handler",
7982 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, NULL, CONSHDLR_NAME"_newsolution", "handles the event that a new primal solution has been found",
8001 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
8031 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
8033 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
8073 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
8080 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
8081 * method SCIPcreateConsBivariate(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
|