All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
cons_nonlinear.c
Go to the documentation of this file.
17 * @brief constraint handler for nonlinear constraints \f$\textrm{lhs} \leq \sum_{i=1}^n a_ix_i + \sum_{j=1}^m c_jf_j(x) \leq \textrm{rhs}\f$
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42 #define CONSHDLR_ENFOPRIORITY -60 /**< priority of the constraint handler for constraint enforcing */
43 #define CONSHDLR_CHECKPRIORITY -4000010 /**< 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? */
56 #define BOUNDTIGHTENING_MINSTRENGTH 0.05/**< minimal required bound tightening strength in expression graph domain tightening for propagating bound change */
57 #define INITLPMAXVARVAL 1000.0 /**< maximal absolute value of variable for still generating a linearization cut at that point in initlp */
88 SCIP_EXPRCURV* curvatures; /**< curvature of each expression tree (taking nonlincoefs into account) */
89 SCIP_EXPRGRAPHNODE* exprgraphnode; /**< node in expression graph corresponding to expression tree of this constraint */
98 unsigned int isremovedfixingslin:1; /**< did we removed fixed/aggr/multiaggr variables in linear part? */
99 unsigned int ispropagated:1; /**< did we propagate the current bounds of linear variables in this constraint? */
100 unsigned int ispresolved:1; /**< did we checked for possibilities of upgrading or implicit integer variables? */
101 unsigned int forcebackprop:1; /**< should we force to run the backward propagation on our subgraph in the exprgraph? */
103 SCIP_Real minlinactivity; /**< sum of minimal activities of all linear terms with finite minimal activity */
104 SCIP_Real maxlinactivity; /**< sum of maximal activities of all linear terms with finite maximal activity */
108 SCIP_Real lhsviol; /**< violation of lower bound by current solution (used temporarily inside constraint handler) */
109 SCIP_Real rhsviol; /**< violation of lower bound by current solution (used temporarily inside constraint handler) */
111 int linvar_maydecrease; /**< index of a variable in linvars that may be decreased without making any other constraint infeasible, or -1 if none */
112 int linvar_mayincrease; /**< index of a variable in linvars that may be increased without making any other constraint infeasible, or -1 if none */
114 SCIP_Real lincoefsmin; /**< maximal absolute value of coefficients in linear part, only available in solving stage */
115 SCIP_Real lincoefsmax; /**< minimal absolute value of coefficients in linear part, only available in solving stage */
122 SCIP_DECL_NONLINCONSUPGD((*nlconsupgd)); /**< method to call for upgrading nonlinear constraint */
123 SCIP_DECL_EXPRGRAPHNODEREFORM((*nodereform));/**< method to call for reformulating an expression graph node */
134 SCIP_Real mincutefficacysepa; /**< minimal efficacy of a cut in order to add it to relaxation during separation */
135 SCIP_Real mincutefficacyenfofac;/**< minimal target efficacy of a cut in order to add it to relaxation during enforcement as factor of feasibility tolerance (may be ignored) */
137 SCIP_Real cutmaxrange; /**< maximal range (maximal coef / minimal coef) of a cut in order to be added to LP */
140 SCIP_Bool assumeconvex; /**< whether functions in inequalities should be assumed to be convex */
141 int maxproprounds; /**< limit on number of propagation rounds for a single constraint within one round of SCIP propagation */
143 int maxexpansionexponent;/**< maximal exponent where still expanding non-monomial polynomials in expression simplification */
144 SCIP_Real sepanlpmincont; /**< minimal required fraction of continuous variables in problem to use solution of NLP relaxation in root for separation */
145 SCIP_Bool enfocutsremovable; /**< are cuts added during enforcement removable from the LP in the same node? */
150 SCIP_EVENTHDLR* nonlinvareventhdlr; /**< our handler for nonlinear variable bound change events */
153 SCIP_NLCONSUPGRADE** nlconsupgrades; /**< nonlinear constraint upgrade methods for specializing nonlinear constraints */
159 unsigned int isremovedfixings:1; /**< have fixed variables been removed in the expression graph? */
160 unsigned int ispropagated:1; /**< have current bounds of linear variables in constraints and variables in expression graph been propagated? */
164 SCIP_NODE* lastenfolpnode; /**< the node for which enforcement was called the last time (and some constraint was violated) */
212 /* if right hand side is finite, then a tightening in the lower bound of coef*linvar is of interest */
220 /* if left hand side is finite, then a tightening in the upper bound of coef*linvar is of interest */
230 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->linvars[linvarpos], eventtype, conshdlrdata->linvareventhdlr, (SCIP_EVENTDATA*)eventdata, &eventdata->filterpos) );
240 /* since bound changes were not catched before, a possibly stored linear activity may have become outdated, so set to invalid */
283 /* if right hand side is finite, then a tightening in the lower bound of coef*linvar is of interest */
291 /* if left hand side is finite, then a tightening in the upper bound of coef*linvar is of interest */
298 SCIP_CALL( SCIPdropVarEvent(scip, consdata->linvars[linvarpos], eventtype, conshdlrdata->linvareventhdlr, (SCIP_EVENTDATA*)consdata->lineventdata[linvarpos], consdata->lineventdata[linvarpos]->filterpos) );
326 SCIP_CALL( SCIPlockVarCons(scip, var, cons, !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
330 SCIP_CALL( SCIPlockVarCons(scip, var, cons, !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
357 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
361 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
385 if( consdata->minlinactivity != SCIP_INVALID && consdata->maxlinactivity != SCIP_INVALID ) /*lint !e777*/
476 assert(consdata->minlinactivity <= consdata->maxlinactivity || consdata->minlinactivityinf > 0 || consdata->maxlinactivityinf > 0);
705 consdataUpdateLinearActivityLbChange(scip, consdata, consdata->lincoefs[varidx], SCIPeventGetOldbound(event), SCIPeventGetNewbound(event));
707 consdataUpdateLinearActivityUbChange(scip, consdata, consdata->lincoefs[varidx], SCIPeventGetOldbound(event), SCIPeventGetNewbound(event));
745 SCIPvarGetName(SCIPeventGetVar(event)), SCIPeventGetOldbound(event), SCIPeventGetNewbound(event));
749 /* @todo a global bound tightening may yield in convex/concave curvatures, maybe the iscurvcheck flag should be reset? */
754 newbd = -infty2infty(SCIPinfinity(scip), INTERVALINFTY, -SCIPeventGetNewbound(event)); /*lint !e666*/
756 * this is to ensure that an original positive variable does not get negative by this, which may have an adverse effect on convexity recoginition, for example */
765 newbd = +infty2infty(SCIPinfinity(scip), INTERVALINFTY, SCIPeventGetNewbound(event)); /*lint !e666*/
802 SCIP_CALL( SCIPcatchVarEvent(conshdlrdata->scip, (SCIP_VAR*)var, SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_VARFIXED, conshdlrdata->nonlinvareventhdlr, (SCIP_EVENTDATA*)varnode, NULL) );
803 SCIPdebugMessage("catch boundchange events on new expression graph variable <%s>\n", SCIPvarGetName(var_));
807 -infty2infty(SCIPinfinity(conshdlrdata->scip), INTERVALINFTY, -MIN(SCIPvarGetLbLocal(var_), SCIPvarGetUbLocal(var_))), /*lint !e666*/
808 +infty2infty(SCIPinfinity(conshdlrdata->scip), INTERVALINFTY, MAX(SCIPvarGetLbLocal(var_), SCIPvarGetUbLocal(var_))) /*lint !e666*/
841 SCIP_CALL( SCIPdropVarEvent(conshdlrdata->scip, var_, SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_VARFIXED, conshdlrdata->nonlinvareventhdlr, (SCIP_EVENTDATA*)varnode, -1) );
842 SCIPdebugMessage("drop boundchange events on expression graph variable <%s>\n", SCIPvarGetName(var_));
898 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->exprtrees, consdata->nexprtrees, consdata->nexprtrees + nexprtrees) );
899 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->nonlincoefs, consdata->nexprtrees, consdata->nexprtrees + nexprtrees) );
900 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->curvatures, consdata->nexprtrees, consdata->nexprtrees + nexprtrees) );
911 SCIP_CALL( SCIPexprtreeCopy(SCIPblkmem(scip), &consdata->exprtrees[consdata->nexprtrees + i], exprtrees[i]) );
993 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->linvars, consdata->linvarssize, newsize) );
994 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->lincoefs, consdata->linvarssize, newsize) );
997 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->lineventdata, consdata->linvarssize, newsize) );
1130 assert((*consdata)->lineventdata == NULL || (*consdata)->lineventdata[i] == NULL); /* variable events should have been dropped earlier */
1191 SCIPsortPtrReal((void**)consdata->linvars, consdata->lincoefs, SCIPvarComp, consdata->nlinvars);
1197 SCIPsortPtrPtrReal((void**)consdata->linvars, (void**)consdata->lineventdata, consdata->lincoefs, SCIPvarComp, consdata->nlinvars);
1208 /* this function is currently not needed, but also to nice to be deleted, so it is only deactivated */
1210 /** returns the position of variable in the linear coefficients array of a constraint, or -1 if not found */
1227 if( !SCIPsortedvecFindPtr((void**)consdata->linvars, SCIPvarComp, (void*)var, consdata->nlinvars, &pos) )
1340 (SCIPvarCompare(consdata->linvars[consdata->nlinvars-2], consdata->linvars[consdata->nlinvars-1]) == -1);
1341 /* always set too FALSE since the new linear variable should be checked if already existing as quad var term */
1492 /* merges entries with same linear variable into one entry and cleans up entries with coefficient 0.0 */
1521 /* make sure linear variables are sorted (do this in every round, since we may move variables around) */
1588 SCIPdebugMessage(" linear term %g*<%s> is replaced by %g * <%s> + %g\n", consdata->lincoefs[i], SCIPvarGetName(consdata->linvars[i]), coef, SCIPvarGetName(var), offset);
1648 SCIPdebugMessage("removed fixations of linear variables from <%s>\n -> ", SCIPconsGetName(cons));
1704 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, coefs, &nvars, varssize, &constant, &requsize, TRUE) );
1726 SCIP_CALL( SCIPexprgraphReplaceVarByLinearSum(conshdlrdata->exprgraph, var, nvars, coefs, (void**)vars, constant) );
1739 /** moves constant and linear part from expression graph node into constraint sides and linear part
1771 /* number of children of expression graph node is a good upper estimate on number of linear variables */
1778 SCIP_CALL( SCIPexprgraphNodeSplitOffLinear(conshdlrdata->exprgraph, &consdata->exprgraphnode, linvarssize, &nlinvars, (void**)linvars, lincoefs, &constant) );
1796 /* @todo linear variables that are also children of exprgraphnode could be moved into the expression graph for certain nonlinear operators (quadratic, polynomial), since that may allow better bound tightening */
1848 SCIP_CALL( SCIPexprgraphGetTree(conshdlrdata->exprgraph, consdata->exprgraphnode, &exprtree) );
1859 /** tries to automatically convert a nonlinear constraint (or a part of it) into a more specific and more specialized constraint */
1867 int* naddconss /**< buffer to increase with number of additional constraints created during upgrade */
1895 /* set debug solution in expression graph and evaluate nodes, so reformulation methods can compute debug solution values for new auxiliary variables */
1901 SCIP_CALL( SCIPallocBufferArray(scip, &varvals, SCIPexprgraphGetNVars(conshdlrdata->exprgraph)) );
1904 SCIP_CALL( SCIPdebugGetSolVal(scip, (SCIP_VAR*)SCIPexprgraphGetVars(conshdlrdata->exprgraph)[i], &varvals[i]) );
1929 SCIP_CALL( conshdlrdata->nlconsupgrades[i]->nlconsupgd(scip, cons, &nupgdconss_, upgdconss, upgdconsssize) );
1938 SCIP_CALL( conshdlrdata->nlconsupgrades[i]->nlconsupgd(scip, cons, &nupgdconss_, upgdconss, upgdconsssize) );
1960 /* count the first upgrade constraint as constraint upgrade and the remaining ones as added constraints */
2030 SCIP_CALL( SCIPallocBufferArray(scip, &varbounds, SCIPexprtreeGetNVars(consdata->exprtrees[i])) );
2035 SCIP_CALL( SCIPreallocBufferArray(scip, &varbounds, SCIPexprtreeGetNVars(consdata->exprtrees[i])) );
2044 -infty2infty(SCIPinfinity(scip), INTERVALINFTY, -MIN(SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var))), /*lint !e666*/
2045 +infty2infty(SCIPinfinity(scip), INTERVALINFTY, MAX(SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var))) ); /*lint !e666*/
2048 SCIP_CALL( SCIPexprtreeCheckCurvature(consdata->exprtrees[i], INTERVALINFTY, varbounds, &consdata->curvatures[i], NULL) );
2049 consdata->curvatures[i] = SCIPexprcurvMultiply(consdata->nonlincoefs[i], consdata->curvatures[i]);
2051 if( consdata->curvatures[i] == SCIP_EXPRCURV_UNKNOWN && SCIPconshdlrGetData(SCIPconsGetHdlr(cons))->isreformulated )
2053 SCIPwarningMessage(scip, "indefinite expression tree in constraint <%s>\n", SCIPconsGetName(cons));
2054 SCIPdebug( SCIP_CALL( SCIPexprtreePrintWithNames(consdata->exprtrees[i], SCIPgetMessagehdlr(scip), NULL) ) );
2063 SCIPdebugMessage("-> tree %d with coef %g is %s -> nonlinear part is %s\n", i, consdata->nonlincoefs[i], SCIPexprcurvGetName(consdata->curvatures[i]), SCIPexprcurvGetName(consdata->curvature));
2096 /* if node still exists, then because it is captured by some constraint (it should not have parents anymore)
2098 * @todo may be expensive when this is done more often, esp. when we know that node will not be freed due to an added auxiliary constraint
2114 /* since we change the node, also the constraint changes, so ensure that it is presolved again */
2123 /** creates a new auxiliary variable and a new auxiliary nonlinear constraint connecting the var and a given node
2124 * node is replaced by new new auxiliary variables node in all parents of node in expression graph and in all constraints that use node
2154 SCIPdebugMessage("add auxiliary variable and constraint %s for node %p(%d,%d)\n", name, (void*)node, SCIPexprgraphGetNodeDepth(node), SCIPexprgraphGetNodePosition(node));
2156 SCIP_CALL( SCIPcreateVar(scip, &auxvar, name, SCIPintervalGetInf(bounds), SCIPintervalGetSup(bounds), 0.0,
2163 /* store debug sol value of node as value for auxvar in debug solution and as value for auxvarnode */
2174 /* set also bounds of auxvarnode to bounds, so it is available for new parent nodes (currently node->parents)
2175 * when updating their curvature information; avoid having to run domain propagation through exprgraph
2177 SCIPexprgraphTightenNodeBounds(exprgraph, auxvarnode, bounds, BOUNDTIGHTENING_MINSTRENGTH, &cutoff);
2178 assert(!cutoff); /* we tightenend bounds from [-inf,+inf] to bounds, this should not be infeasible */
2182 SCIP_CALL( SCIPcreateConsNonlinear2(scip, &auxcons, name, 1, &auxvar, &minusone, node, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE,
2198 /** ensures that all children of a node have at least a given curvature by adding auxiliary variables */
2231 (void*)child, SCIPexprgraphGetNodeDepth(child), SCIPexprgraphGetNodePosition(child), SCIPexprcurvGetName(SCIPexprgraphGetNodeCurvature(child)) );
2238 assert(SCIPexprgraphGetNodeOperator(SCIPexprgraphGetNodeChildren(node)[i]) == SCIP_EXPR_VARIDX);
2246 SCIP_CALL( SCIPexprgraphUpdateNodeBoundsCurvature(node, INTERVALINFTY, BOUNDTIGHTENING_MINSTRENGTH, TRUE) );
2253 /** reformulates a monomial by adding auxiliary variables and constraints for bilinear terms */
2261 SCIP_EXPRGRAPHNODE** resultnode, /**< buffer to store node which represents the reformulated monomial */
2288 if( nfactors == 1 && exponents[0] < 0.0 && SCIPexprgraphGetNodeBounds(factors[0]).inf < 0.0 && SCIPexprgraphGetNodeBounds(factors[0]).sup > 0.0 ) /*lint !e613*/
2303 /* store debug sol value of node as value for auxvar in debug solution and as value for resultnode */
2313 /* increase naddcons before next call to reformMonomial, to avoid duplicate variable names, which is bad for debugging */
2323 SCIP_CALL( reformMonomial(scip, exprgraph, 2, reformfactors, reformexp, &auxnode, FALSE, naddcons) );
2366 SCIP_CALL( SCIPexprgraphCreateNode(SCIPblkmem(scip), &expnode, SCIP_EXPR_INTPOWER, (int)SCIPround(scip, exponents[0])) );
2368 SCIP_CALL( SCIPexprgraphCreateNode(SCIPblkmem(scip), &expnode, SCIP_EXPR_REALPOWER, exponents[0]) );
2371 SCIP_CALL( SCIPexprgraphUpdateNodeBoundsCurvature(expnode, INTERVALINFTY, BOUNDTIGHTENING_MINSTRENGTH, TRUE) );
2377 /* @todo if there was already a node for factors[0]^exponents[0], then there may have been also been already an auxiliary variable and constraint (-> ex7_3_4) */
2396 SCIP_CALL( SCIPcreateConsNonlinear2(scip, &auxcons, name, 1, &auxvar, &minusone, expnode, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE,
2413 if( nfactors == 2 && exponents != NULL && exponents[0] != 1.0 && exponents[0] == exponents[1] ) /*lint !e777*/
2415 /* factor0^exponent * factor1^exponent with exponent != 1.0, reform as (factor0*factor1)^exponent */
2422 SCIP_CALL( reformMonomial(scip, exprgraph, 1, &productnode, &exponents[0], resultnode, createauxcons, naddcons) );
2429 /* factor0^exponent * factor1^(-exponent), reform as (factor0/factor1)^exponent or (factor1/factor0)^(-exponent) */
2435 /* create variable and constraint for factor0 = auxvar * factor1 (if exponent > 0) or factor1 = auxvar * factor0 (if exponent < 0) */
2446 /* store debug sol value of node as value for auxvar in debug solution and as value for resultnode */
2459 /* add new constraint resultnode(= auxvar) * factor1 - factor0 == 0 (exponent > 0) or auxvar * factor0 - factor1 == 0 (exponent < 0) */
2472 SCIP_CALL( SCIPcreateConsNonlinear2(scip, &auxcons, name, 0, NULL, NULL, auxconsnode, 0.0, 0.0,
2484 SCIP_CALL( reformMonomial(scip, exprgraph, 1, &auxvarnode, &absexp, resultnode, createauxcons, naddcons) );
2489 /* @todo if nfactors > 2, assemble groups of factors with same exponent and replace these by a single variable first */
2493 /* create auxvar for left half (recursively) and auxvar for right half (recursively) and maybe new auxvar for product */
2494 /* @todo it may be enough to replace single factors in a monomial to get it convex or concave, see Westerlund et.al. */
2506 SCIP_CALL( reformMonomial(scip, exprgraph, half, factors, exponents, &leftright[0], TRUE, naddcons) );
2507 SCIP_CALL( reformMonomial(scip, exprgraph, nfactors-half, &factors[half], exponents != NULL ? &exponents[half] : NULL, &leftright[1], TRUE, naddcons) ); /*lint !e826*/
2518 if( (SCIPexprgraphGetNodeChildren(parent)[0] == leftright[0] && SCIPexprgraphGetNodeChildren(parent)[1] == leftright[1]) ||
2519 ( SCIPexprgraphGetNodeChildren(parent)[0] == leftright[1] && SCIPexprgraphGetNodeChildren(parent)[1] == leftright[0]) )
2530 SCIP_CALL( SCIPexprgraphUpdateNodeBoundsCurvature(productnode, INTERVALINFTY, BOUNDTIGHTENING_MINSTRENGTH, TRUE) );
2536 /* @todo if there was already a node for factors[0]^exponents[0], then there may have been also been already an auxiliary variable and constraint (-> ex7_3_4) */
2555 SCIP_CALL( SCIPcreateConsNonlinear2(scip, &auxcons, name, 1, &auxvar, &minusone, productnode, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE,
2573 /** reformulates expression graph into a form so that for each node under- and overestimators could be computed
2574 * similar to factorable reformulation in other global solvers, but sometimes does not split up complex operands (like quadratic)
2624 /* set debug solution in expression graph and evaluate nodes, so we can compute debug solution values for auxiliary variables */
2633 SCIP_CALL( SCIPdebugGetSolVal(scip, (SCIP_VAR*)SCIPexprgraphGetVars(exprgraph)[i], &varvals[i]) );
2657 SCIP_CALL( SCIPexprgraphUpdateNodeBoundsCurvature(node, INTERVALINFTY, BOUNDTIGHTENING_MINSTRENGTH, TRUE) );
2663 if( conshdlrdata->nlconsupgrades[u]->nodereform != NULL && conshdlrdata->nlconsupgrades[u]->active )
2665 SCIP_CALL( conshdlrdata->nlconsupgrades[u]->nodereform(scip, exprgraph, node, naddcons, &reformnode) );
2670 (void*)node, SCIPexprgraphGetNodeDepth(node), SCIPexprgraphGetNodePosition(node), (void*)reformnode);
2673 SCIP_CALL( SCIPexprgraphUpdateNodeBoundsCurvature(reformnode, INTERVALINFTY, BOUNDTIGHTENING_MINSTRENGTH, TRUE) );
2686 SCIPdebugMessage("skip reformulating node %p(%d,%d) = ", (void*)node, SCIPexprgraphGetNodeDepth(node), SCIPexprgraphGetNodePosition(node));
2694 * we want to know whether the current node will be at the top of the tree after the next simplification run
2701 SCIPdebugMessage("think about reformulating %s node %p(%d,%d) = ", SCIPexpropGetName(SCIPexprgraphGetNodeOperator(node)), (void*)node, SCIPexprgraphGetNodeDepth(node), SCIPexprgraphGetNodePosition(node));
2710 /* at this place, all children nodes should have a known curvature, except if they only appear only linearly in constraints
2711 * the latter for cases where constraints with unknown curvature are upgraded to other constraint handler that can handle these (quadratic, signpower,...)
2730 SCIPerrorMessage("node with operator %d cannot have unknown curvature\n", SCIPexprgraphGetNodeOperator(node));
2754 /* ensure all children are linear, so next simplifier run makes sure all children will be variables */
2755 SCIP_CALL( reformEnsureChildrenMinCurvature(scip, exprgraph, node, SCIP_EXPRCURV_LINEAR, conss, nconss, naddcons) );
2763 /* if we have nonlinear parents or a sibling, then add add auxiliary variable for this node, so an upgrade to cons_quadratic should take place
2764 * we assume that siblings are non-linear and non-quadratic, which should be the case if simplifier was run, and also if this node was created during reformulating a polynomial
2766 * @todo if sibling nodes are quadratic (or even linear) due to reformulation, then we do not need to reform here... (-> nvs16)
2767 * maybe this step should not be done here at all if havenonlinparent is FALSE? e.g., move into upgrade from quadratic?
2773 assert(SCIPexprgraphGetNodeNParents(node) == 0); /* node should now be at top of graph, so it can be upgraded by cons_quadratic */
2784 * note that in the reformulation, a zero in the denominator forces the nominator to be zero too, but the auxiliary can be arbitrary
2799 SCIPdebugMessage("add auxiliary variable %s for division in node %p(%d,%d)\n", name, (void*)node, SCIPexprgraphGetNodeDepth(node), SCIPexprgraphGetNodePosition(node));
2801 SCIP_CALL( SCIPcreateVar(scip, &auxvar, name, SCIPintervalGetInf(bounds), SCIPintervalGetSup(bounds), 0.0,
2829 SCIP_CALL( SCIPexprgraphCreateNodeQuadratic(SCIPblkmem(scip), &auxnode, 3, lincoefs, 1, &quadelem, 0.0) );
2851 SCIP_CALL( reformEnsureChildrenMinCurvature(scip, exprgraph, node, SCIP_EXPRCURV_CONCAVE, conss, nconss, naddcons) );
2860 SCIP_CALL( reformEnsureChildrenMinCurvature(scip, exprgraph, node, SCIP_EXPRCURV_CONVEX, conss, nconss, naddcons) );
2871 /* for an intpower with mixed sign in the base and negative exponent, we reformulate similar as for EXPR_DIV */
2872 if( SCIPexprgraphGetNodeIntPowerExponent(node) < 0 && SCIPintervalGetInf(SCIPexprgraphGetNodeBounds(children[0])) < 0.0 && SCIPintervalGetSup(SCIPexprgraphGetNodeBounds(children[0])) > 0.0 ) /*lint !e613*/
2877 /* if we have something like x^(-3) with mixed sign for x, then add auxvar and reform as auxvar*x^3 = 1 via reformMonomial */
2879 SCIP_CALL( reformMonomial(scip, exprgraph, 1, children, &exponent, &auxvarnode, TRUE, naddcons) );
2888 /* univariate operands where the child does not have bounds and curvature from which we can deduce curvature of this node,
2902 SCIP_CALL( reformEnsureChildrenMinCurvature(scip, exprgraph, node, SCIP_EXPRCURV_LINEAR, conss, nconss, naddcons) );
2906 /* the only case where f(x) for a linear term x is indefinite here is if f is intpower or signpower and x has mixed sign */
2907 assert(SCIPexprgraphGetNodeOperator(node) == SCIP_EXPR_INTPOWER || SCIPexprgraphGetNodeOperator(node) == SCIP_EXPR_SIGNPOWER);
2913 SCIP_CALL( SCIPexprgraphUpdateNodeBoundsCurvature(node, INTERVALINFTY, BOUNDTIGHTENING_MINSTRENGTH, TRUE) );
2918 /* if intpower and signpower with positive exponent and a mixed sign in the child bounds still does not give a curvature,
2919 * we can do more if we make this node the root of a nonlinear constraints expression node, so it can be upgraded by cons_signpower
2925 assert(SCIPexprgraphGetNodeOperator(node) == SCIP_EXPR_INTPOWER || SCIPexprgraphGetNodeOperator(node) == SCIP_EXPR_SIGNPOWER);
2926 assert(SCIPexprgraphGetNodeOperator(node) != SCIP_EXPR_INTPOWER || SCIPexprgraphGetNodeIntPowerExponent(node) > 1);
2927 assert(SCIPexprgraphGetNodeOperator(node) != SCIP_EXPR_SIGNPOWER || SCIPexprgraphGetNodeSignPowerExponent(node) > 1.0);
2932 assert(SCIPexprgraphGetNodeNParents(node) == 0); /* node should now be at top of graph (and used by new auxiliary constraint) */
2954 SCIP_CALL( reformEnsureChildrenMinCurvature(scip, exprgraph, node, SCIP_EXPRCURV_LINEAR, conss, nconss, naddcons) );
2962 * if node has parents, then ensure that it has a known curvature, otherwise we are also fine with a node that is a product of two (aux)variables */
2963 SCIP_CALL( reformMonomial(scip, exprgraph, nchildren, children, NULL, &reformnode, havenonlinparent, naddcons) );
2973 /* if polynomial has several monomials, replace by a sum of nodes each having a single monomial and one that has all linear and quadratic monomials
3004 /* @todo if a monomial is a factor of another monomial, then we could (and should?) replace it there by the node we create for it here -> ex7_2_1
3008 /* constant part of polynomials, to add to first monomialnode, if any, or quadratic or linear part */
3018 /* expression graph nodes representing single higher-degree monomials, and single node with linear and/or quadratic monomials */
3087 SCIP_CALL( SCIPexprCreateMonomial(SCIPblkmem(scip), &monomialnew, coef, nfactors, NULL, exponents) );
3088 SCIP_CALL( SCIPexprgraphCreateNodePolynomial(SCIPblkmem(scip), &monomialnodes[nmonomialnodes], 1, &monomialnew, constant, FALSE) );
3100 * no need to refresh bounds/curvature here, since that will be done when we reach this node next */
3101 SCIP_CALL( SCIPexprgraphAddNode(exprgraph, monomialnodes[nmonomialnodes], SCIPexprgraphGetNodeDepth(node), nfactors, childrennew) );
3111 /* create and add additional node for quadratic and linear part, simplifier should take care of removing unused children later */
3112 SCIP_CALL( SCIPexprgraphCreateNodeQuadratic(SCIPblkmem(scip), &monomialnodes[nmonomialnodes], nchildren, lincoefs, nquadelems, quadelems, constant) );
3114 SCIP_CALL( SCIPexprgraphAddNode(exprgraph, monomialnodes[nmonomialnodes], SCIPexprgraphGetNodeDepth(node), nchildren, children) );
3119 /* create additional node for linear part, simplifier should take care of removing unused children later */
3120 SCIP_CALL( SCIPexprgraphCreateNodeLinear(SCIPblkmem(scip), &monomialnodes[nmonomialnodes], nchildren, lincoefs, constant) );
3122 SCIP_CALL( SCIPexprgraphAddNode(exprgraph, monomialnodes[nmonomialnodes], SCIPexprgraphGetNodeDepth(node), nchildren, children) );
3135 SCIP_CALL( SCIPexprgraphCreateNode(SCIPblkmem(scip), &sumnode, nmonomialnodes == 2 ? SCIP_EXPR_PLUS : SCIP_EXPR_SUM) );
3141 assert(SCIPexprgraphGetNodeOperator(monomialnodes[0]) == SCIP_EXPR_LINEAR || SCIPexprgraphGetNodeOperator(monomialnodes[0]) == SCIP_EXPR_QUADRATIC);
3170 /* ensure that the child of an univariate monomial is linear if its current (bounds,curvature) yields an unknown curvature for the monomial
3174 assert(SCIPexprcurvPower(childbounds, childcurv, exponents[0]) == SCIP_EXPRCURV_UNKNOWN); /* this is exactly the curvature of the node, which is unknown */
3177 if( SCIPexprcurvPower(childbounds, SCIP_EXPRCURV_LINEAR, exponents[0]) != SCIP_EXPRCURV_UNKNOWN )
3180 SCIPdebugMessage("reform child %d (univar. monomial) with curv %s into var\n", childidxs[0], SCIPexprcurvGetName(childcurv));
3181 SCIP_CALL( reformNode2Var(scip, exprgraph, children[childidxs[0]], conss, nconss, naddcons, FALSE) ); /*lint !e613*/
3187 /* check if the conditions on the exponents allow for a convex or concave monomial, assuming that the children are linear
3188 * if one of these conditions is fulfilled but a children curvature does not fit, then make these children linear
3229 /* if some child can be both positive and negative, then nothing we can do here to get the monomial convex or concave
3236 * - all except one exponent j* are negative and exp_j* >= 1 - sum_{j!=j*}exp_j, but the latter is equivalent to sum_j exp_j >= 1
3248 /* if exponents are such that we can be convex, but children curvature does not fit, make some children linear */
3249 SCIPdebugMessage("%d-variate monomial is convex (modulo sign), child curv fits = %u\n", nfactors, expcurvpos);
3250 /* since current node curvature is set to unknown, there must be such a child, since otherwise the node curvature had to be convex */
3256 /* if exponents are such that we can be concave, but children curvature does not fit, make some children linear */
3257 SCIPdebugMessage("%d-variate monomial is concave (modulo sign), child curv fits = %u\n", nfactors, expcurvneg);
3258 /* since current node curvature is set to unknown, there must be such a child, since otherwise the node curvature had to be concave */
3289 childidxs[f], f, SCIPexprcurvGetName(SCIPexprgraphGetNodeCurvature(children[childidxs[f]]))); /*lint !e613*/
3290 SCIP_CALL( reformNode2Var(scip, exprgraph, children[childidxs[f]], conss, nconss, naddcons, FALSE) ); /*lint !e613*/
3299 /* refresh curvature information in node, since we changed children, it should be convex or concave now */
3300 SCIP_CALL( SCIPexprgraphUpdateNodeBoundsCurvature(node, INTERVALINFTY, BOUNDTIGHTENING_MINSTRENGTH, TRUE) );
3310 * or is of form x^a with x both negative and positive and a an odd or negative integer (-> INTPOWER expression)
3313 (SCIPexprgraphGetNodeBounds(children[childidxs[0]]).inf < 0.0 && SCIPexprgraphGetNodeBounds(children[childidxs[0]]).sup > 0.0 &&
3314 SCIPisIntegral(scip, exponents[0]) && (exponents[0] < 0.0 || ((int)SCIPround(scip, exponents[0]) % 2 != 0)))
3317 /* bilinear monomials should not come up here, since simplifier should have turned them into quadratic expression nodes */
3320 /* reform monomial if it is a product, or we need it to be on the top of the graph, or if it of the form x^a with a < 0.0 (and thus x having mixed sign, see assert above)
3321 * thus, in the case x^a with a an odd positive integer we assume that cons_signpower will do something */
3338 * if node has parents and monomial is of indefinite form x^a, then also create auxvar for it, since otherwise we create a auxnode with unknown curvature
3339 * note, that the case x^a with positive and odd a will still give an indefinite node (without parents), where we assume that signpower will pick it up at some point
3341 SCIP_CALL( reformMonomial(scip, exprgraph, nfactors, factors, exponents, &auxnode, havenonlinparent, naddcons) );
3353 SCIP_CALL( SCIPexprgraphCreateNodeLinear(SCIPblkmem(scip), &replnode, 1, &coef, SCIPexprgraphGetNodePolynomialConstant(node)) );
3360 SCIP_CALL( SCIPexprgraphUpdateNodeBoundsCurvature(auxnode, INTERVALINFTY, BOUNDTIGHTENING_MINSTRENGTH, TRUE) );
3367 SCIPdebugMessage("no reformulation of monomial node, assume signpower will take care of it\n");
3381 /* for constraints with concave f(g(x)) with linear g:R^n -> R, n>1, reformulate to get a univariate concave function, since this is easier to underestimate
3382 * @todo this does not work yet for sums of functions, e.g., polynomials with more than one monomial
3397 /* after reformulation, force a round of backpropagation in expression graph for all constraints,
3398 * since new variables (nlreform*) may now be used in existing constraints and we want domain restrictions
3419 assert(SCIPexprgraphGetNodeOperator(multivarnode) == SCIP_EXPR_CONST || SCIPexprgraphGetNodeOperator(multivarnode) == SCIP_EXPR_VARIDX);
3431 SCIPdebugMessage("replace linear multivariate node %p(%d,%d) in expression of cons <%s> by auxvar\n",
3432 (void*)multivarnode, SCIPexprgraphGetNodeDepth(multivarnode), SCIPexprgraphGetNodePosition(multivarnode), SCIPconsGetName(conss[c])); /*lint !e613*/
3490 /* compile expression tree, if not done before (can happen, if called from proposeFeasibleSolution) */
3498 /* in the not so unusual case that an expression has only one variable, we do not extra alloc memory */
3565 * during presolving and if the constraint is active, it is assumes that SCIPexprgraphEval has been called for sol before
3609 /* project onto local box, in case the LP solution is slightly outside the bounds (which is not our job to enforce) */
3612 #if 0 /* with non-initial columns, this might fail because variables can shortly be a column variable before entering the LP and have value 0.0 in this case */
3637 /* in the not so unusual case that an expression has only one variable, we do not need to extra allocate memory */
3641 /* project onto local box, in case the LP solution is slightly outside the bounds (and then cannot be evaluated) */
3644 #if 0 /* with non-initial columns, this might fail because variables can shortly be a column variable before entering the LP and have value 0.0 in this case */
3651 SCIP_CALL( SCIPexprintEval(conshdlrdata->exprinterpreter, consdata->exprtrees[i], &varval, &val) );
3665 /* project onto local box, in case the LP solution is slightly outside the bounds (and then cannot be evaluated) */
3668 #if 0 /* with non-initial columns, this might fail because variables can shortly be a column variable before entering the LP and have value 0.0 in this case */
3699 assert(SCIPgetStage(scip) >= SCIP_STAGE_INITPRESOLVE && SCIPgetStage(scip) <= SCIP_STAGE_EXITPRESOLVE);
3716 if( !SCIPisInfinity(scip, -consdata->lhs) && SCIPisGT(scip, consdata->lhs - consdata->activity, SCIPfeastol(scip)) )
3721 if( !SCIPisInfinity(scip, consdata->rhs) && SCIPisGT(scip, consdata->activity - consdata->rhs, SCIPfeastol(scip)) )
3736 if( (consdata->lhsviol > 0.0 || consdata->rhsviol > 0.0) && (consdata->exprgraphnode == NULL || consdata->nexprtrees > 0) )
3740 SCIP_CALL( getGradientMaxElement(scip, conshdlrdata->exprinterpreter, cons, sol, FALSE, &norm) );
3777 SCIP_CONS** maxviolcon /**< buffer to store constraint with largest violation, or NULL if solution is feasible */
3790 if( SCIPgetStage(scip) >= SCIP_STAGE_INITPRESOLVE && SCIPgetStage(scip) <= SCIP_STAGE_EXITPRESOLVE )
3799 SCIP_CALL( SCIPallocBufferArray(scip, &varvals, SCIPexprgraphGetNVars(conshdlrdata->exprgraph)) );
3800 SCIP_CALL( SCIPgetSolVals(scip, sol, SCIPexprgraphGetNVars(conshdlrdata->exprgraph), (SCIP_VAR**)SCIPexprgraphGetVars(conshdlrdata->exprgraph), varvals) );
3828 /* SCIPdebugMessage("constraint <%s> violated by (%g, %g), activity = %g\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol, consdata->activity); */
3842 SCIP_Bool newx, /**< whether the last evaluation of the expression with the expression interpreter was not at x */
3844 SCIP_Bool* success /**< buffer to store whether a linearization was succefully added to the row */
3898 if( !SCIPisFinite(grad[i]) || SCIPisInfinity(scip, grad[i]) || SCIPisInfinity(scip, -grad[i]) )
3904 /* coefficients smaller than epsilon are rounded to 0.0 when added to row, this can be wrong if variable value is very large (bad numerics)
3905 * in this case, set gradient to 0.0 here, but modify constant so that cut is still valid (if possible)
3906 * i.e., estimate grad[i]*x >= grad[i] * bound(x) or grad[i]*x <= grad[i] * bound(x), depending on whether we compute an underestimator (convex) or an overestimator (concave)
3926 SCIPdebugMessage("var <%s> [%g,%g] has tiny gradient %g, replace coefficient by constant %g\n",
3927 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), grad[i], grad[i] * xbnd);
3934 SCIPdebugMessage("skipping linearization, var <%s> [%g,%g] has tiny gradient %g but no finite bound in this direction\n",
3946 SCIPdebugMessage("got nonfinite value in evaluation or gradient of <%s>: ", SCIPconsGetName(cons));
3962 x[i] += MIN3(0.9*(ub-x[i]), 0.9*(x[i]-lb), i*SCIPfeastol(scip)) * (i%2 != 0 ? -1.0 : 1.0); /*lint !e666*/
3991 SCIPdebugMessage("added linearization for tree %d of constraint <%s>\n", exprtreeidx, SCIPconsGetName(cons));
4044 SCIPdebugMessage("skip secant for tree %d of constraint <%s> since variable is unbounded\n", exprtreeidx, SCIPconsGetName(cons));
4052 SCIPdebugMessage("skip secant for tree %d of constraint <%s> since function cannot be evaluated in lower bound\n", exprtreeidx, SCIPconsGetName(cons));
4060 SCIPdebugMessage("skip secant for tree %d of constraint <%s> since function cannot be evaluated in upper bound\n", exprtreeidx, SCIPconsGetName(cons));
4093 SCIPdebugMessage("added secant for tree %d of constraint <%s>, slope = %g\n", exprtreeidx, SCIPconsGetName(cons), slope);
4099 /** given three points, constructs coefficient of equation for hyperplane generated by these three points
4200 if( SCIPisInfinity(scip, -xlb) || SCIPisInfinity(scip, xub) || SCIPisInfinity(scip, -ylb) || SCIPisInfinity(scip, yub) )
4202 SCIPdebugMessage("skip bivariate secant since <%s> or <%s> is unbounded\n", SCIPvarGetName(x), SCIPvarGetName(y));
4236 SCIPdebugMessage("skip secant for tree %d of constraint <%s> since function cannot be evaluated\n", exprtreeidx, SCIPconsGetName(cons));
4253 if( !SCIPisFinite(p1val) || SCIPisInfinity(scip, REALABS(p1val)) || !SCIPisFinite(p4val) || SCIPisInfinity(scip, REALABS(p4val)) )
4255 SCIPdebugMessage("skip secant for tree %d of constraint <%s> since function cannot be evaluated\n", exprtreeidx, SCIPconsGetName(cons));
4272 if( !SCIPisFinite(p1val) || SCIPisInfinity(scip, REALABS(p1val)) || !SCIPisFinite(p2val) || SCIPisInfinity(scip, REALABS(p2val)) )
4274 SCIPdebugMessage("skip secant for tree %d of constraint <%s> since function cannot be evaluated\n", exprtreeidx, SCIPconsGetName(cons));
4291 /* if function is convex, then we want an overestimator, otherwise we want an underestimator */
4292 assert(consdata->curvatures[exprtreeidx] == SCIP_EXPRCURV_CONVEX || consdata->curvatures[exprtreeidx] == SCIP_EXPRCURV_CONCAVE);
4299 if( !SCIPisFinite(p1val) || SCIPisInfinity(scip, REALABS(p1val)) || !SCIPisFinite(p2val) || SCIPisInfinity(scip, REALABS(p2val)) ||
4300 ! SCIPisFinite(p3val) || SCIPisInfinity(scip, REALABS(p3val)) || !SCIPisFinite(p4val) || SCIPisInfinity(scip, REALABS(p4val)) )
4302 SCIPdebugMessage("skip secant for tree %d of constraint <%s> since function cannot be evaluated\n", exprtreeidx, SCIPconsGetName(cons));
4310 /* if we want an underestimator, flip f(x,y), i.e., do as if we compute an overestimator for -f(x,y) */
4328 * Since we assume that f is convex, we then know that all points (x,y,f(x,y)) are below this hyperplane, i.e.,
4337 getAlphaBetaGammaDelta(p1[0], p1[1], p1val, p2[0], p2[1], p2val, p3[0], p3[1], p3val, &alpha, &beta, &gamma_, &delta);
4342 /* if hyperplane through p1,p2,p3 does not overestimate f(p4), then it must be the other variant */
4349 getAlphaBetaGammaDelta(p1[0], p1[1], p1val, p3[0], p3[1], p3val, p4[0], p4[1], p4val, &alpha, &beta, &gamma_, &delta);
4354 /* if hyperplane through p1,p3,p4 does not overestimate f(p2), then it must be the other variant */
4361 getAlphaBetaGammaDelta(p1[0], p1[1], p1val, p3[0], p3[1], p3val, p4[0], p4[1], p4val, &alpha, &beta, &gamma_, &delta);
4366 /* if hyperplane through p1,p3,p4 does not overestimate f(p2), then it must be the other variant */
4373 getAlphaBetaGammaDelta(p1[0], p1[1], p1val, p2[0], p2[1], p2val, p3[0], p3[1], p3val, &alpha, &beta, &gamma_, &delta);
4378 /* if hyperplane through p1,p2,p3 does not overestimate f(p4), then it must be the other variant */
4388 getAlphaBetaGammaDelta(p1[0], p1[1], p1val, p2[0], p2[1], p2val, p4[0], p4[1], p4val, &alpha, &beta, &gamma_, &delta);
4400 getAlphaBetaGammaDelta(p2[0], p2[1], p2val, p3[0], p3[1], p3val, p4[0], p4[1], p4val, &alpha, &beta, &gamma_, &delta);
4411 getAlphaBetaGammaDelta(p2[0], p2[1], p2val, p3[0], p3[1], p3val, p4[0], p4[1], p4val, &alpha, &beta, &gamma_, &delta);
4423 getAlphaBetaGammaDelta(p1[0], p1[1], p1val, p2[0], p2[1], p2val, p4[0], p4[1], p4val, &alpha, &beta, &gamma_, &delta);
4434 SCIPdebugMessage("alpha = %g, beta = %g, gamma = %g, delta = %g\n", alpha, beta, gamma_, delta);
4449 /* if we loose coefficients because division by gamma makes them < SCIPepsilon(scip), then better not generate a cut here */
4453 SCIPdebugMessage("skip bivar secant for <%s> tree %d due to bad numerics\n", SCIPconsGetName(cons), exprtreeidx);
4472 SCIPdebugMessage("added bivariate secant for tree %d of constraint <%s>\n", exprtreeidx, SCIPconsGetName(cons));
4550 SCIPwarningMessage(scip, "concave function in constraint <%s> too high-dimensional to compute underestimator\n", SCIPconsGetName(cons));
4559 * otherwise we can easily get an unbounded LP below, e.g., with instances like ex6_2_* from GlobalLib
4563 if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(vars[j])) || SCIPisInfinity(scip, SCIPvarGetUbLocal(vars[j])) )
4565 SCIPdebugMessage("cannot compute underestimator for concave because variable <%s> is unbounded\n", SCIPvarGetName(vars[j]));
4570 ref[j] = MIN(SCIPvarGetUbLocal(vars[j]), MAX(SCIPvarGetLbLocal(vars[j]), ref[j])); /*lint !e666*/
4573 assert(consdata->curvatures[exprtreeidx] == SCIP_EXPRCURV_CONVEX || consdata->curvatures[exprtreeidx] == SCIP_EXPRCURV_CONCAVE);
4603 /* if j'th bit of row index i is set, then take upper bound on var j, otherwise lower bound var j
4604 * we check this by shifting i for j positions to the right and checking whether the j'th bit is set */
4621 SCIPdebugMessage("cannot compute underestimator for concave because constaint <%s> cannot be evaluated\n", SCIPconsGetName(cons));
4658 SCIP_CALL( SCIPlpiCreate(&lpi, SCIPgetMessagehdlr(scip), "concaveunderest", doupper ? SCIP_OBJSEN_MINIMIZE : SCIP_OBJSEN_MAXIMIZE) );
4666 SCIP_CALL( SCIPlpiSetRealpar(lpi, doupper ? SCIP_LPPAR_LOBJLIM : SCIP_LPPAR_UOBJLIM, funcval) );
4676 SCIPwarningMessage(scip, "solving auxiliary LP for underestimator of concave function returned %d\n", lpret);
4682 SCIPdebugMessage("failed to find feasible solution for auxiliary LP for underestimator of concave function, iterlimexc = %u, cutoff = %u, unbounded = %u\n", SCIPlpiIsIterlimExc(lpi), SCIPlpiIsObjlimExc(lpi), SCIPlpiIsPrimalUnbounded(lpi));
4694 if( (!doupper && SCIPisFeasGT(scip, lpobj, funcval)) || (doupper && SCIPisFeasGT(scip, funcval, lpobj)) )
4696 SCIPwarningMessage(scip, "computed cut does not underestimate concave function in refpoint\n");
4742 SCIP_Bool newx, /**< whether the last evaluation of the expression with the expression interpreter was not at x */
4743 SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
4803 SCIPdebugMessage("skip interval gradient estimator for constraint <%s> because variable <%s> is still unbounded.\n", SCIPconsGetName(cons), SCIPvarGetName(vars[i]));
4830 SCIPdebugMessage("Got nonfinite function value from evaluation of constraint %s tree %d. skipping interval gradient estimator.\n", SCIPconsGetName(cons), exprtreeidx);
4840 SCIP_CALL( SCIPexprintGradInt(exprint, exprtree, INTERVALINFTY, box, TRUE, &intval, intgrad) );
4843 /* printf("nvars %d side %d xref = %g x = [%g,%g] intval = [%g,%g] intgrad = [%g,%g]\n", nvars, side, x[0],
4895 /** generates a cut based on linearization (if convex), secant (if concave), or intervalgradient (if indefinite)
4903 SCIP_SOL* sol, /**< reference solution where cut should be generated, or NULL if LP solution should be used */
4904 SCIP_Bool newsol, /**< whether the last evaluation of the expression with the expression interpreter was not at sol */
4922 SCIPdebugMessage("constructing cut for %s hand side of constraint <%s>\n", side == SCIP_SIDETYPE_LEFT ? "left" : "right", SCIPconsGetName(cons));
4931 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%u", SCIPconsGetName(cons), ++(consdata->ncuts));
4934 SCIP_CALL( SCIPcreateEmptyRowCons(scip, row, SCIPconsGetHdlr(cons), rowname, consdata->lhs, consdata->rhs, SCIPconsIsLocal(cons), FALSE , TRUE) );
4935 SCIP_CALL( SCIPaddVarsToRow(scip, *row, consdata->nlinvars, consdata->linvars, consdata->lincoefs) );
4939 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%u", SCIPconsGetName(cons), ++(consdata->ncuts));
4958 SCIP_CALL( SCIPgetSolVals(scip, sol, SCIPexprtreeGetNVars(consdata->exprtrees[i]), SCIPexprtreeGetVars(consdata->exprtrees[i]), x) );
4989 SCIPdebugMessage("failed to generate polyhedral estimator for %d-dim concave function in exprtree %d, fall back to intervalgradient cut\n", SCIPexprtreeGetNVars(consdata->exprtrees[i]), i);
4990 SCIP_CALL( addIntervalGradientEstimator(scip, exprint, cons, i, x, newsol, side == SCIP_SIDETYPE_LEFT, *row, &success) );
4995 SCIP_CALL( addIntervalGradientEstimator(scip, exprint, cons, i, x, newsol, side == SCIP_SIDETYPE_LEFT, *row, &success) );
5027 /* if range of coefficients is bad, find very small coefficients (from nonlinear vars) and make them zero */
5028 SCIPdebugMessage("cut coefficients for constraint <%s> have very large range: mincoef = %g maxcoef = %g\n", SCIPconsGetName(cons), mincoef, maxcoef);
5030 /* if minimal coefficient is given by linear var, then give up (probably the maximal coefficient is the problem) */
5048 if( ((coef > 0.0 && side == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && side == SCIP_SIDETYPE_LEFT)) &&
5051 SCIPdebugMessage("eliminate coefficient %g for <%s> = %g [%g, %g]\n", coef, SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
5058 if( ((coef < 0.0 && side == SCIP_SIDETYPE_RIGHT) || (coef > 0.0 && side == SCIP_SIDETYPE_LEFT)) &&
5061 SCIPdebugMessage("eliminate coefficient %g for <%s> = %g [%g, %g]\n", coef, SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
5098 SCIPdebugMessage("drop row for constraint <%s> because range of coefficients is too large: mincoef = %g, maxcoef = %g -> range = %g\n",
5108 SCIPdebugMessage("drop row for constraint <%s> because of very large side: %g\n", SCIPconsGetName(cons), side == SCIP_SIDETYPE_LEFT ? -SCIProwGetLhs(*row) : SCIProwGetRhs(*row));
5119 SCIP_CALL( SCIPaddVarsToRow(scip, *row, consdata->nlinvars, consdata->linvars, consdata->lincoefs) );
5140 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 */
5178 if( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
5184 violside = SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT;
5187 * if function is defined at sol (activity<infinity) and constraint is violated, then expression interpreter should have evaluated at sol to get gradient before
5189 SCIP_CALL( generateCut(scip, conshdlrdata->exprinterpreter, conss[c], NULL, sol, newsol || SCIPisInfinity(scip, consdata->activity), violside, &row, conshdlrdata->cutmaxrange, conshdlrdata->checkconvexexpensive, conshdlrdata->assumeconvex) );
5206 /* in difference to SCIPgetCutEfficacy, we scale by norm only if the norm is > 1.0 this avoid finding cuts
5207 * efficient which are only very slightly violated CPLEX does not seem to scale row coefficients up too also
5208 * we use infinity norm, since that seem to be the usual scaling strategy in LP solvers (equilibrium
5234 SCIPisGT(scip, efficacy, SCIPgetRelaxFeastolFactor(scip) > 0.0 ? SCIPepsilon(scip) : SCIPfeastol(scip))
5250 SCIPdebugMessage("add cut with efficacy %g for constraint <%s> violated by %g\n", efficacy, SCIPconsGetName(conss[c]), MAX(consdata->lhsviol, consdata->rhsviol));
5272 * others are only checked and enforced if we are still feasible or have not found a separating cut yet
5281 /** adds linearizations cuts for convex constraints w.r.t. a given reference point to cutpool and sepastore
5282 * if separatedlpsol is not NULL, then a cut that separates the LP solution is added to the sepastore and is forced to enter the LP
5283 * if separatedlpsol is not NULL, but cut does not separate the LP solution, then it is added to the cutpool only
5293 SCIP_Bool* separatedlpsol, /**< buffer to store whether a cut that separates the current LP solution was found and added to LP, or NULL if adding to cutpool only */
5294 SCIP_Real minefficacy /**< minimal efficacy of a cut when checking for separation of LP solution */
5320 SCIP_CALL( checkCurvature(scip, conss[c], conshdlrdata->checkconvexexpensive, conshdlrdata->assumeconvex) ); /*lint !e613*/
5352 /* in difference to SCIPgetCutEfficacy, we scale by norm only if the norm is > 1.0 this avoid finding cuts
5353 * efficient which are only very slightly violated CPLEX does not seem to scale row coefficients up too also
5354 * we use infinity norm, since that seem to be the usual scaling strategy in LP solvers (equilibrium
5427 /* we are only interested in solution coming from some heuristic other than trysol, but not from the tree
5428 * the reason for ignoring trysol solutions is that they may come from an NLP solve in sepalp, where we already added linearizations,
5437 SCIPdebugMessage("catched new sol event %x from heur <%s>; have %d conss\n", SCIPeventGetType(event), SCIPheurGetName(SCIPsolGetHeur(sol)), nconss);
5444 /** registers unfixed variables in nonlinear terms of violated constraints as external branching candidates */
5476 if( (!SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || (consdata->curvature & SCIP_EXPRCURV_CONCAVE)) &&
5477 ( !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) || (consdata->curvature & SCIP_EXPRCURV_CONVEX )) )
5479 SCIPdebugMessage("cons <%s> violation: %g %g curvature: %s\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol, SCIPexprcurvGetName(consdata->curvature));
5484 if( (!SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || (consdata->curvatures[i] & SCIP_EXPRCURV_CONCAVE)) &&
5485 ( !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) || (consdata->curvatures[i] & SCIP_EXPRCURV_CONVEX )) )
5495 SCIPdebugMessage("ignore fixed variable <%s>[%g, %g], width %g\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var));
5499 SCIP_CALL( SCIPaddExternBranchCand(scip, var, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) );
5510 /** registers a nonlinear variable from a violated constraint as branching candidate that has a large absolute value in the LP relaxation */
5539 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
5568 /** replaces violated nonlinear constraints where all nonlinear variables are fixed by linear constraints
5605 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
5615 SCIP_CALL( SCIPevalExprtreeLocalBounds(scip, consdata->exprtrees[i], INTERVALINFTY, &nonlinactivity) );
5618 SCIPintervalMulScalar(INTERVALINFTY, &nonlinactivity, nonlinactivity, consdata->nonlincoefs[i]);
5638 SCIPdebugMessage("Linear constraint with one variable: %g <= %g <%s> <= %g\n", lhs, coef, SCIPvarGetName(*consdata->linvars), rhs);
5663 SCIPdebugMessage("Linear constraint is a bound: %g <= <%s> <= %g\n", lhs, SCIPvarGetName(*consdata->linvars), rhs);
5706 SCIPdebugMessage("replace violated nonlinear constraint <%s> by linear constraint after all nonlinear vars have been fixed\n", SCIPconsGetName(conss[c]) );
5733 SCIP_CONS* cons, /**< constraint where we currently propagate, or NULL if tightening is from expression graph */
5768 SCIPdebugMessage("%sfound constraint <%s> infeasible due to tightened lower bound %g for variable <%s>\n", SCIPinProbing(scip) ? "in probing " : "", cons != NULL ? SCIPconsGetName(cons) : "??", bnd, SCIPvarGetName(var)); /*lint !e585*/
5778 SCIPdebugMessage("%stightened lower bound of variable <%s> in constraint <%s> to %.20g\n", SCIPinProbing(scip) ? "in probing " : "", SCIPvarGetName(var), cons != NULL ? SCIPconsGetName(cons) : "??", bnd); /*lint !e585*/
5794 SCIP_CONS* cons, /**< constraint where we currently propagate, or NULL if tightening is from expression graph */
5829 SCIPdebugMessage("%sfound constraint <%s> infeasible due to tightened upper bound %g for variable <%s>\n", SCIPinProbing(scip) ? "in probing " : "", cons != NULL ? SCIPconsGetName(cons) : "??", bnd, SCIPvarGetName(var)); /*lint !e585*/
5839 SCIPdebugMessage("%stightened upper bound of variable <%s> in constraint <%s> to %g\n", SCIPinProbing(scip) ? "in probing " : "", SCIPvarGetName(var), cons != NULL ? SCIPconsGetName(cons) : "??", bnd); /*lint !e585*/
5859 SCIP_Bool* redundant /**< buffer where to store whether constraint has been found to be redundant */
5889 SCIPdebugMessage("start linear vars domain propagation for constraint <%s>\n", SCIPconsGetName(cons));
5918 SCIPintervalSetBounds(&consactivity, consdata->minlinactivityinf > 0 ? -INTERVALINFTY : consdata->minlinactivity, consdata->maxlinactivityinf > 0 ? INTERVALINFTY : consdata->maxlinactivity);
5922 SCIPdebugMessage("found constraint <%s> to be redundant: sides: [%g, %g], activity: [%g, %g]\n",
5923 SCIPconsGetName(cons), consdata->lhs, consdata->rhs, SCIPintervalGetInf(consactivity), SCIPintervalGetSup(consactivity));
5930 SCIPdebugMessage("found constraint <%s> to be infeasible; sides: [%g, %g], activity: [%g, %g], infeas: %.20g\n",
5931 SCIPconsGetName(cons), consdata->lhs, consdata->rhs, SCIPintervalGetInf(consactivity), SCIPintervalGetSup(consactivity),
5932 MAX(consdata->lhs - SCIPintervalGetSup(consactivity), SCIPintervalGetInf(consactivity) - consdata->rhs));
5937 /* propagate linear part in rhs = consbounds - nonlinactivity (use the one from consdata, since that includes infinities) */
5950 * we can't expect much more tightening, but may detect infeasiblity, but shouldn't the check on the constraints activity detect that?
6153 SCIP_CALL( SCIPexprgraphPrintDot(conshdlrdata->exprgraph, SCIPgetMessagehdlr(scip), file, NULL) );
6182 bounds.sup = SCIPintervalNegateReal(consdata->minlinactivity - consdata->rhs - SCIPfeastol(scip));
6188 /* if we want the expression graph to propagate the bounds in any case, we set minstrength to a negative value */
6195 SCIPdebugMessage("found constraint <%s> infeasible%s\n", SCIPconsGetName(conss[c]), SCIPinProbing(scip) ? " in probing" : "");
6202 SCIPexprgraphPropagateNodeBounds(conshdlrdata->exprgraph, INTERVALINFTY, BOUNDTIGHTENING_MINSTRENGTH, &cutoff);
6210 SCIP_CALL( SCIPexprgraphPrintDot(conshdlrdata->exprgraph, SCIPgetMessagehdlr(scip), file, NULL) );
6218 SCIPdebugMessage("backward propagation found problem infeasible%s\n", SCIPinProbing(scip) ? " in probing" : "");
6233 SCIP_CALL( propagateBoundsTightenVarLb(scip, NULL, vars[i], SCIPintervalGetInf(SCIPexprgraphGetNodeBounds(varnodes[i])), result, nchgbds) );
6235 if( *result != SCIP_CUTOFF && !SCIPisInfinity(scip, SCIPintervalGetSup(SCIPexprgraphGetNodeBounds(varnodes[i]))) )
6237 SCIP_CALL( propagateBoundsTightenVarUb(scip, NULL, vars[i], SCIPintervalGetSup(SCIPexprgraphGetNodeBounds(varnodes[i])), result, nchgbds) );
6253 int* ndelconss /**< buffer where to increase if a constraint was deleted (locally) due to redundancy */
6291 SCIPdebugMessage("starting domain propagation round %d for %d constraints\n", roundnr, nconss);
6297 * @todo could give FALSE if no linear variable in the constraints had been relaxed since last time
6299 SCIP_CALL( SCIPexprgraphPropagateVarBounds(conshdlrdata->exprgraph, INTERVALINFTY, roundnr == 0, &domainerror) );
6307 SCIP_CALL( SCIPexprgraphPrintDot(conshdlrdata->exprgraph, SCIPgetMessagehdlr(scip), file, NULL) );
6320 /* check for redundancy and infeasibility of constraints, tighten bounds on linear variables */
6331 assert(consdata->exprgraphnode == NULL || !SCIPintervalIsEmpty(SCIPexprgraphGetNodeBounds(consdata->exprgraphnode)));
6366 /* checks for a linear variable that can be increase or decreased without harming feasibility */
6400 /* if we have already one candidate, then take the one where the loss in the objective function is less */
6402 (SCIPvarGetObj(consdata->linvars[consdata->linvar_maydecrease]) / consdata->lincoefs[consdata->linvar_maydecrease] > SCIPvarGetObj(consdata->linvars[i]) / consdata->lincoefs[i]) )
6409 /* if we have already one candidate, then take the one where the loss in the objective function is less */
6411 (SCIPvarGetObj(consdata->linvars[consdata->linvar_mayincrease]) / consdata->lincoefs[consdata->linvar_mayincrease] > SCIPvarGetObj(consdata->linvars[i]) / consdata->lincoefs[i]) )
6419 SCIPdebugMessage("may increase <%s> to become feasible\n", SCIPvarGetName(consdata->linvars[consdata->linvar_mayincrease]));
6423 SCIPdebugMessage("may decrease <%s> to become feasible\n", SCIPvarGetName(consdata->linvars[consdata->linvar_maydecrease]));
6428 /** Given a solution where every nonlinear constraint is either feasible or can be made feasible by
6429 * moving a linear variable, construct the corresponding feasible solution and pass it to the trysol heuristic.
6430 * The method assumes that this is always possible and that not all constraints are feasible already.
6439 SCIP_Bool* success /**< buffer to store whether we succeeded to construct a solution that satisfies all provided constraints */
6515 SCIPdebugMessage("increase <%s> by %g to %g\n", SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var));
6546 SCIPdebugMessage("increase <%s> by %g to %g\n", SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var));
6555 /* still here... so probably we could not make constraint feasible due to variable bounds, thus give up */
6559 /* if we have a solution that should satisfy all nonlinear constraints and has a better objective than the current upper bound,
6561 if( c == nconss && (SCIPisInfinity(scip, SCIPgetUpperbound(scip)) || SCIPisSumLT(scip, SCIPgetSolTransObj(scip, newsol), SCIPgetUpperbound(scip))) )
6563 SCIPdebugMessage("pass solution with objective value %g to trysol heuristic\n", SCIPgetSolTransObj(scip, newsol));
6594 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
6653 SCIP_CALL( SCIPexprgraphPrintDot(conshdlrdata->exprgraph, SCIPgetMessagehdlr(scip), file, NULL) );
6662 /** deinitialization method of constraint handler (called before transformed problem is freed) */
6681 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
6710 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
6742 /* if undefined expressions in exprgraph (very unlikely), we will hopefully recognize this during domain propagation later (if it involved an active constraint) */
6743 SCIP_CALL( SCIPexprgraphSimplify(conshdlrdata->exprgraph, SCIPgetMessagehdlr(scip), SCIPepsilon(scip), conshdlrdata->maxexpansionexponent, &havechange, &domainerror) );
6744 SCIPdebugMessage("expression graph simplifier found %schange, domain error = %u\n", havechange ? "" : "no ", domainerror);
6815 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
6837 /* check for a linear variable that can be increase or decreased without harming feasibility */
6845 consdata->lincoefsmin = MIN(consdata->lincoefsmin, REALABS(consdata->lincoefs[i])); /*lint !e666*/
6846 consdata->lincoefsmax = MAX(consdata->lincoefsmax, REALABS(consdata->lincoefs[i])); /*lint !e666*/
6869 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, (SCIP_EVENTDATA*)conshdlr, &conshdlrdata->newsoleventfilterpos) );
6880 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
6902 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, (SCIP_EVENTDATA*)conshdlr, conshdlrdata->newsoleventfilterpos) );
6935 /* expression should have been removed from expression graph when constraint was deactivated */
6983 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
6985 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons),
6994 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
7020 SCIP_CALL( checkCurvature(scip, conss[c], conshdlrdata->checkconvexexpensive, conshdlrdata->assumeconvex) ); /*lint !e613*/
7033 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(conss[c]), SCIPconsGetName(conss[c]), consdata->lhs, consdata->rhs,
7035 SCIP_CALL( SCIPaddVarsToRow(scip, row, consdata->nlinvars, consdata->linvars, consdata->lincoefs) );
7084 if( !SCIPisInfinity(scip, consdata->rhs) && ((consdata->curvature & SCIP_EXPRCURV_CONVEX) || !haveunboundedvar) )
7086 SCIP_CALL( generateCut(scip, conshdlrdata->exprinterpreter, conss[c], x, NULL, TRUE, SCIP_SIDETYPE_RIGHT, &row, conshdlrdata->cutmaxrange, FALSE, FALSE) ); /*lint !e613*/
7098 if( !SCIPisInfinity(scip, -consdata->lhs) && ((consdata->curvature & SCIP_EXPRCURV_CONCAVE) || !haveunboundedvar) )
7100 SCIP_CALL( generateCut(scip, conshdlrdata->exprinterpreter, conss[c], x, NULL, TRUE, SCIP_SIDETYPE_LEFT, &row, conshdlrdata->cutmaxrange, FALSE, FALSE) ); /*lint !e613*/
7148 /* at root, check if we want to solve the NLP relaxation and use its solutions as reference point
7149 * if there is something convex, then linearizing in the solution of the NLP relaxation can be very useful
7152 (SCIPgetNContVars(scip) >= conshdlrdata->sepanlpmincont * SCIPgetNVars(scip) || (SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_UNBOUNDEDRAY && conshdlrdata->sepanlpmincont <= 1.0)) &&
7165 * but first check whether there is a violated constraint side which corresponds to a convex function
7176 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
7180 SCIP_CALL( checkCurvature(scip, conss[c], conshdlrdata->checkconvexexpensive, conshdlrdata->assumeconvex) ); /*lint !e613*/
7182 if( (SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) && (consdata->curvature & SCIP_EXPRCURV_CONVEX )) ||
7183 ( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && (consdata->curvature & SCIP_EXPRCURV_CONCAVE)) )
7248 SCIP_CALL( addLinearizationCuts(scip, conshdlr, conss, nconss, nlpsol, &lpsolseparated, conshdlrdata->mincutefficacysepa) );
7253 /* if a cut that separated the LP solution was added, then return, otherwise continue with usual separation in LP solution */
7264 /* if we do not want to try solving the NLP, or have no NLP, or have no NLP solver, or solving the NLP failed,
7265 * or separating with NLP solution as reference point failed, then try (again) with LP solution as reference point
7268 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, newsol, conshdlrdata->mincutefficacysepa, FALSE, result, NULL) );
7295 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, sol, FALSE, conshdlrdata->mincutefficacysepa, FALSE, result, NULL) );
7338 SCIPdebugMessage("enfolp with max violation %g in cons <%s>\n", maxviol, SCIPconsGetName(maxviolcons));
7340 /* we propagate and separate constraints only if they are active and enforcing by branching only does not seem much effective */
7344 * (maybe the LP does not think that the cuts we add are violated, or we do ECP on a high-dimensional convex function)
7345 * 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
7346 * (in optimized more, returning SCIP_INFEASIBLE in *result would be sufficient, but in debug mode this would give an assert in scip.c)
7347 * the reason to wait for 100 rounds is to avoid calls to SCIPisStopped in normal runs, which may be expensive
7358 SCIP_CALL( SCIPcreateChild(scip, &child, 1.0, SCIPnodeGetEstimate(SCIPgetCurrentNode(scip))) );
7384 * thus, in the latter case, we are also happy if the efficacy is at least, say, 75% of the maximal violation
7387 minefficacy = MIN(0.75*maxviol, conshdlrdata->mincutefficacyenfofac * SCIPfeastol(scip)); /*lint !e666*/
7389 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, FALSE, minefficacy, TRUE, &separateresult, &sepaefficacy) );
7398 SCIPdebugMessage("separation succeeded (bestefficacy = %g, minefficacy = %g)\n", sepaefficacy, minefficacy);
7407 SCIPdebugMessage("separation failed (bestefficacy = %g < %g = minefficacy ); max viol: %g\n", sepaefficacy, minefficacy, maxviol);
7412 /* if sepastore can decrease LP feasibility tolerance, we can add cuts with efficacy in [eps, feastol] */
7413 leastpossibleefficacy = SCIPgetRelaxFeastolFactor(scip) > 0.0 ? SCIPepsilon(scip) : SCIPfeastol(scip);
7417 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, FALSE, leastpossibleefficacy, TRUE, &separateresult, &sepaefficacy) );
7427 /* fallback 2: separation probably failed because of numerical difficulties with a convex constraint;
7428 * if noone declared solution infeasible yet and we had not even found a weak cut, try to resolve by branching
7434 /* fallback 3: all nonlinear variables in all violated constraints seem to be fixed -> replace by linear constraints */
7439 SCIPdebugMessage("All nonlinear variables seem to be fixed. Replace remaining violated nonlinear constraints by linear constraints.\n");
7440 SCIP_CALL( replaceViolatedByLinearConstraints(scip, conss, nconss, &addedcons, &reduceddom, &infeasible) );
7441 /* if the linear constraints are actually feasible, then adding them and returning SCIP_CONSADDED confuses SCIP
7442 * when it enforces the new constraints again and nothing resolves the infeasiblity that we declare here thus,
7443 * we only add them if considered violated, and otherwise claim the solution is feasible (but print a
7454 SCIPwarningMessage(scip, "could not enforce feasibility by separating or branching; declaring solution with viol %g as feasible\n", maxviol);
7461 SCIPdebugMessage("Could not find any usual branching variable candidate. Proposed variable <%s> with LP value %g for branching.\n",
7500 /* we propagate constraints only if they are active and enforcing by branching only does not seem much effective */
7523 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
7531 SCIP_CALL( SCIPaddExternBranchCand(scip, var, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) );
7542 SCIP_CALL( SCIPaddExternBranchCand(scip, var, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) );
7550 SCIPdebugMessage("All variables in violated constraints fixed (up to epsilon). Cannot find branching candidate. Forcing solution of LP.\n");
7578 /* during presolve, we do not have exprtrees in the constraints, but we can get values from the expression graph, if we have evaluated it */
7579 if( SCIPgetStage(scip) >= SCIP_STAGE_INITPRESOLVE && SCIPgetStage(scip) <= SCIP_STAGE_EXITPRESOLVE )
7585 SCIP_CALL( SCIPallocBufferArray(scip, &varvals, SCIPexprgraphGetNVars(conshdlrdata->exprgraph)) );
7586 SCIP_CALL( SCIPgetSolVals(scip, sol, SCIPexprgraphGetNVars(conshdlrdata->exprgraph), (SCIP_VAR**)SCIPexprgraphGetVars(conshdlrdata->exprgraph), varvals) );
7597 (SCIPgetStage(scip) < SCIP_STAGE_INITPRESOLVE || SCIPgetStage(scip) > SCIP_STAGE_EXITPRESOLVE) &&
7608 if( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
7617 SCIPinfoMessage(scip, NULL, "violation: left hand side is violated by %.15g (scaled: %.15g)\n", consdata->lhs - consdata->activity, consdata->lhsviol);
7621 SCIPinfoMessage(scip, NULL, "violation: right hand side is violated by %.15g (scaled: %.15g)\n", consdata->activity - consdata->rhs, consdata->rhsviol);
7631 /* do not try to shift linear variables if activity is at infinity (leads to setting variable to infinity in solution, which is not allowed) */
7645 if( !(consdata->linvar_mayincrease >= 0 && consdata->lincoefs[consdata->linvar_mayincrease] > 0.0) &&
7646 ! (consdata->linvar_maydecrease >= 0 && consdata->lincoefs[consdata->linvar_maydecrease] < 0.0) )
7654 if( !(consdata->linvar_mayincrease >= 0 && consdata->lincoefs[consdata->linvar_mayincrease] < 0.0) &&
7655 ! (consdata->linvar_maydecrease >= 0 && consdata->lincoefs[consdata->linvar_maydecrease] > 0.0) )
7662 /* SCIPdebugMessage("constraint <%s> is feasible (%g, %g) in check, activity = %g, sides = [%g, %g]\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol, consdata->activity, consdata->lhs, consdata->rhs); */
7736 SCIP_CALL( SCIPexprgraphSimplify(conshdlrdata->exprgraph, SCIPgetMessagehdlr(scip), SCIPepsilon(scip), conshdlrdata->maxexpansionexponent, &havechange, &domainerror) );
7737 SCIPdebugMessage("expression graph simplifier found %schange, domain error = %u\n", havechange ? "" : "no ", domainerror);
7741 * usually, this should be discovered during domain propagation already, but since that is using interval arithmetics,
7742 * it may overestimate in a way that actually undefined expressions still get a value assigned (e.g., 0^(-1) = [-inf,inf]) */
7751 /* upgrade methods may look at expression graph bounds, which are not present in the first presolving round yet */
7752 SCIP_CALL( SCIPexprgraphPropagateVarBounds(conshdlrdata->exprgraph, INTERVALINFTY, TRUE, &domainerror) );
7756 SCIPdebugMessage("propagating variable bounds through expression graph found that some expressions cannot be evaluated w.r.t. current bounds, thus cutoff\n");
7781 /* the reductions below require the constraint nonlinear function to be in the expression graph, which is only the case for active constraints */
7805 SCIPdebugMessage("constraint <%s> is constant and feasible, deleting\n", SCIPconsGetName(conss[c]));
7813 /* call upgrade methods if constraint was not presolved, has been changed, or the expression graph has changed */
7847 * then try the reformulations (replacing products with binaries, disaggregation, setting default variable bounds)
7864 /* if expression graph changed, ensure that we apply all presolving techniques (esp. upgrades) in next round again */
7880 /* if we did not try reformulations, ensure that presolving is called again even if there were only a few changes (< abortfac) */
7902 * since only active constraints have their nonlinear part in the expression graph, we can lock only active constraints
7969 SCIP_CALL( SCIPexprgraphAddExprtreeSum(conshdlrdata->exprgraph, consdata->nexprtrees, consdata->exprtrees, consdata->nonlincoefs, &consdata->exprgraphnode, &exprtreeisnew) );
7974 if( SCIPgetStage(scip) >= SCIP_STAGE_INITPRESOLVE && SCIPgetStage(scip) < SCIP_STAGE_EXITPRESOLVE )
7982 /* remember that we should force backward propagation on our subgraph propagating the next time,
7989 /* if constraint already comes with node in expression graph, then also remember that we should run reformulation again */
7992 /* remember that we should force backward propagation on our subgraph propagating the next time,
8027 /* during presolving, the exprtrees in the constraint are removed, so put them back before releasing the exprgraphnode */
8030 /* if only presolve is run and problem is found infeasible there, then constraints may not be deactivated there, but in a later call to freeTransform */
8031 /* @todo if infeasible in presolve, will constraints be deactivated still in presolving stage, or in exitpre? */
8032 assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) <= SCIP_STAGE_EXITPRESOLVE || SCIPgetStage(scip) == SCIP_STAGE_FREETRANS);
8034 SCIP_CALL( SCIPexprgraphGetTree(conshdlrdata->exprgraph, consdata->exprgraphnode, &exprtree) );
8079 consdata->isremovedfixingslin = consdata->isremovedfixingslin && SCIPvarIsActive(consdata->linvars[i]);
8155 SCIP_CALL( SCIPexprtreePrintWithNames(consdata->exprtrees[j], SCIPgetMessagehdlr(scip), file) );
8174 SCIPinfoMessage(scip, file, "%+.15g<%s>[%c] ", consdata->lincoefs[j], SCIPvarGetName(consdata->linvars[j]),
8236 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, consdata->linvars[i], &linvars[i], varmap, consmap, global, valid) );
8253 SCIP_CALL( SCIPallocBufferArray(sourcescip, &nonlinvars, SCIPexprtreeGetNVars(consdata->exprtrees[0])) );
8257 SCIP_CALL( SCIPreallocBufferArray(sourcescip, &nonlinvars, SCIPexprtreeGetNVars(consdata->exprtrees[j])) );
8260 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, SCIPexprtreeGetVars(consdata->exprtrees[j])[i], &nonlinvars[i], varmap, consmap, global, valid) );
8267 SCIP_CALL( SCIPexprtreeSetVars(exprtrees[j], SCIPexprtreeGetNVars(consdata->exprtrees[j]), nonlinvars) );
8286 SCIP_CALL( SCIPexprgraphGetTree(conshdlrdata->exprgraph, consdata->exprgraphnode, &exprtrees[0]) );
8291 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, nonlinvars[i], &nonlinvars[i], varmap, consmap, global, valid) );
8302 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
8307 targetconsdata->iscurvchecked = consdata->iscurvchecked && global; /* if the copy is local, then curvature may change (get stronger) */
8358 SCIP_CALL( SCIPallocBufferArray(scip, &varsusage, SCIPexprgraphGetNVars(conshdlrdata->exprgraph)) );
8405 /** constraint method of constraint handler which returns the number of variables (if possible) */
8425 SCIP_CALL( SCIPallocBufferArray(scip, &varsusage, SCIPexprgraphGetNVars(conshdlrdata->exprgraph)) );
8487 /* parse constraint to get lhs, rhs, and expression in between (from cons_linear.c::consparse, but parsing whole string first, then getting expression) */
8490 if( isdigit((unsigned char)str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit((unsigned char)str[1])) )
8587 /* alloc some space for variable names incl. indices; shouldn't be longer than expression string, and we even give it sizeof(int) times this length (plus 5) */
8591 SCIP_CALL( SCIPexprParse(SCIPblkmem(scip), SCIPgetMessagehdlr(scip), &expr, exprstart, exprlastchar, &nvars, varnames) );
8605 SCIPerrorMessage("Unknown SCIP variable <%s> encountered in expression.\n", (char*)curvarname);
8621 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
8674 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolNonlinear, CONSHDLR_MAXPREROUNDS, CONSHDLR_DELAYPRESOL) );
8676 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropNonlinear, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
8678 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpNonlinear, consSepasolNonlinear, CONSHDLR_SEPAFREQ,
8685 "minimal efficacy for a cut to be added to the LP during separation; overwrites separating/efficacy",
8689 "minimal target efficacy of a cut in order to add it to relaxation during enforcement as a factor of the feasibility tolerance (may be ignored)",
8693 "whether scaling of infeasibility is 'o'ff, by sup-norm of function 'g'radient, or by left/right hand 's'ide",
8697 "maximal coef range of a cut (maximal coefficient divided by minimal coefficient) in order to be added to LP relaxation",
8701 "whether to try to make solutions in check function feasible by shifting a linear variable (esp. useful if constraint was actually objective function)",
8711 "whether to assume that nonlinear functions in inequalities (<=) are convex (disables reformulation)",
8715 "limit on number of propagation rounds for a single constraint within one round of SCIP propagation",
8723 "maximal exponent where still expanding non-monomial polynomials in expression simplification",
8727 "minimal required fraction of continuous variables in problem to use solution of NLP relaxation in root for separation",
8735 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->linvareventhdlr), CONSHDLR_NAME"_boundchange", "signals a bound change to a nonlinear constraint",
8740 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->nonlinvareventhdlr), CONSHDLR_NAME"_boundchange2", "signals a bound change to a nonlinear constraint handler",
8744 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, NULL, CONSHDLR_NAME"_newsolution", "handles the event that a new primal solution has been found",
8764 SCIP_DECL_NONLINCONSUPGD((*nonlinconsupgd)),/**< method to call for upgrading nonlinear constraint, or NULL */
8765 SCIP_DECL_EXPRGRAPHNODEREFORM((*nodereform)),/**< method to call for reformulating expression graph node, or NULL */
8798 if( conshdlrdata->nlconsupgrades[i]->nlconsupgd == nonlinconsupgd && conshdlrdata->nlconsupgrades[i]->nodereform == nodereform)
8801 SCIPwarningMessage(scip, "Try to add already known upgrade method pair (%p,%p) for constraint handler <%s>.\n", nonlinconsupgd, nodereform, conshdlrname); /*lint !e611*/
8826 for( i = conshdlrdata->nnlconsupgrades; i > 0 && conshdlrdata->nlconsupgrades[i-1]->priority < nlconsupgrade->priority; --i )
8833 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "constraints/"CONSHDLR_NAME"/upgrade/%s", conshdlrname);
8834 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "enable nonlinear upgrading for constraint handler <%s>", conshdlrname);
8845 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
8856 SCIP_Real* nonlincoefs, /**< coefficients for expression trees for nonlinear part, or NULL if all 1.0 */
8877 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
8879 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
8908 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
8931 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
8932 * method SCIPcreateConsNonlinear(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
8938 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
8949 SCIP_Real* nonlincoefs, /**< coefficients for expression trees for nonlinear part, or NULL if all 1.0 */
8956 SCIP_CALL( SCIPcreateConsNonlinear(scip, cons, name, nlinvars, linvars, lincoefs, nexprtrees, exprtrees,
8964 * this variant takes a node of the expression graph as input and can only be used during presolving
8965 * it is assumed that the nonlinear constraint will be added to the transformed problem short after creation
8968 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
8977 SCIP_EXPRGRAPHNODE* exprgraphnode, /**< expression graph node associated to nonlinear expression */
8998 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
9000 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
9027 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
9057 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
9058 * method SCIPcreateConsNonlinear(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
9060 * this variant takes a node of the expression graph as input and can only be used during presolving
9061 * it is assumed that the nonlinear constraint will be added to the transformed problem short after creation
9066 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
9075 SCIP_EXPRGRAPHNODE* exprgraphnode, /**< expression graph node associated to nonlinear expression */
9082 SCIP_CALL( SCIPcreateConsNonlinear2(scip, cons, name, nlinvars, linvars, lincoefs, exprgraphnode, lhs, rhs,
9123 SCIP_CALL( consdataSetExprtrees(scip, SCIPconsGetData(cons), nexprtrees, exprtrees, coefs, TRUE) );
9145 SCIP_CALL( consdataAddExprtrees(scip, SCIPconsGetData(cons), nexprtrees, exprtrees, coefs, TRUE) );
9219 assert(SCIPgetStage(scip) < SCIP_STAGE_INITPRESOLVE || SCIPgetStage(scip) > SCIP_STAGE_EXITPRESOLVE);
9232 assert(SCIPgetStage(scip) < SCIP_STAGE_INITPRESOLVE || SCIPgetStage(scip) > SCIP_STAGE_EXITPRESOLVE);
9245 assert(SCIPgetStage(scip) < SCIP_STAGE_INITPRESOLVE || SCIPgetStage(scip) > SCIP_STAGE_EXITPRESOLVE);
9303 SCIP_CALL( checkCurvature(scip, cons, conshdlrdata->checkconvexexpensive, conshdlrdata->assumeconvex) );
9334 SCIP_CALL( checkCurvature(scip, cons, conshdlrdata->checkconvexexpensive, conshdlrdata->assumeconvex) );
9342 /** gets the curvature of the expression trees (multiplied by their coefficient) of a nonlinear constraint */
9357 assert(SCIPgetStage(scip) < SCIP_STAGE_INITPRESOLVE || SCIPgetStage(scip) > SCIP_STAGE_EXITPRESOLVE);
9371 SCIP_CALL( checkCurvature(scip, cons, conshdlrdata->checkconvexexpensive, conshdlrdata->assumeconvex) );
9394 if( SCIPgetStage(scip) >= SCIP_STAGE_INITPRESOLVE && SCIPgetStage(scip) <= SCIP_STAGE_EXITPRESOLVE && SCIPconsIsActive(cons) )
9397 SCIPwarningMessage(scip, "SCIPgetViolationNonlinear is not available for active constraints during presolve.\n");
|