cons_nonlinear.c
Go to the documentation of this file.
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
78 #define CONSHDLR_ENFOPRIORITY -60 /**< priority of the constraint handler for constraint enforcing */
79 #define CONSHDLR_CHECKPRIORITY -4000010 /**< priority of the constraint handler for checking feasibility */
80 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
82 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
86 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
87 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
89 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
90 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
91 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler*/
93 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
94 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
100 #define TABLE_EARLIEST_STAGE_NONLINEAR SCIP_STAGE_TRANSFORMED /**< output of the statistics table is only printed from this stage onwards */
106 #define TABLE_EARLIEST_STAGE_NLHDLR SCIP_STAGE_PRESOLVING /**< output of the statistics table is only printed from this stage onwards */
114 #define VERTEXPOLY_RANDNUMINITSEED 20181029 /**< seed for random number generator, which is used to move points away from the boundary */
115 #define VERTEXPOLY_ADJUSTFACETFACTOR 1e1 /**< adjust resulting facets in checkRikun() up to a violation of this value times lpfeastol */
117 #define BRANCH_RANDNUMINITSEED 20191229 /**< seed for random number generator, which is used to select from several similar good branching candidates */
131 #define ENFOLOG(x) if( SCIPgetSubscipDepth(scip) == 0 && SCIPgetVerbLevel(scip) >= SCIP_VERBLEVEL_NORMAL ) { x }
143 {
153 /** data stored by constraint handler in an expression that belongs to a nonlinear constraint */
161 SCIP_MONOTONE* monotonicity; /**< array containing monotonicity of expression w.r.t. each child */
166 unsigned int propboundstag; /**< tag to indicate whether propbounds are valid for the current propagation rounds */
172 unsigned int lastenforced; /**< last enforcement round where expression was enforced successfully */
173 unsigned int nactivityusesprop; /**< number of nonlinear handlers whose activity computation (or domain propagation) depends on the activity of the expression */
174 unsigned int nactivityusessepa; /**< number of nonlinear handlers whose separation (estimate or enfo) depends on the activity of the expression */
175 unsigned int nauxvaruses; /**< number of nonlinear handlers whose separation uses an auxvar in the expression */
179 SCIP_Real violscoresum; /**< sum of violation scores for branching stored for this expression */
180 SCIP_Real violscoremax; /**< max of violation scores for branching stored for this expression */
182 unsigned int violscoretag; /**< tag to decide whether a violation score of an expression needs to be initialized */
209 SCIP_Real gradnorm; /**< norm of gradient of constraint function in current solution (if evaluated) */
221 SCIP_VAR* linvardecr; /**< variable that may be decreased without making any other constraint infeasible, or NULL if none */
222 SCIP_VAR* linvarincr; /**< variable that may be increased without making any other constraint infeasible, or NULL if none */
229 int consindex; /**< an index of the constraint that is unique among all expr-constraints in this SCIP instance and is constant */
234 {
235 SCIP_DECL_NONLINCONSUPGD((*consupgd)); /**< method to call for upgrading nonlinear constraint */
248 SCIP_Bool registerusesactivitysepabelow; /**< a flag that is used only during \ref @detectNlhdlr() */
249 SCIP_Bool registerusesactivitysepaabove; /**< a flag that is used only during \ref @detectNlhdlr() */
252 CONSUPGRADE** consupgrades; /**< constraint upgrade methods for specializing nonlinear constraints */
265 SCIP_Longint lastvaractivitymethodchange; /**< tag when method used to evaluate activity of variables changed last */
270 SCIP_DECL_EXPR_INTEVALVAR((*intevalvar)); /**< method currently used for activity calculation of variable expressions */
271 SCIP_Bool globalbounds; /**< whether global variable bounds should be used for activity calculation */
272 SCIP_QUEUE* reversepropqueue; /**< expression queue to be used in reverse propagation, filled by SCIPtightenExprIntervalNonlinear */
273 SCIP_Bool forceboundtightening; /**< whether bound change passed to SCIPtightenExprIntervalNonlinear should be forced */
274 unsigned int curpropboundstag; /**< tag indicating current propagation rounds, to match with expr->propboundstag */
277 int maxproprounds; /**< limit on number of propagation rounds for a set of constraints within one round of SCIP propagation */
278 SCIP_Bool propauxvars; /**< whether to check bounds of all auxiliary variable to seed reverse propagation */
280 SCIP_Real varboundrelaxamount; /**< by how much to relax variable bounds during bound tightening */
281 SCIP_Real conssiderelaxamount; /**< by how much to relax constraint sides during bound tightening */
283 SCIP_Real vp_adjfacetthreshold; /**< adjust computed facet up to a violation of this value times lpfeastol */
284 SCIP_Bool vp_dualsimplex; /**< whether to use dual simplex instead of primal simplex for facet computing LP */
285 SCIP_Bool reformbinprods; /**< whether to reformulate products of binary variables during presolving */
286 SCIP_Bool reformbinprodsand; /**< whether to use the AND constraint handler for reformulating binary products */
287 int reformbinprodsfac; /**< minimum number of terms to reformulate bilinear binary products by factorizing variables (<= 1: disabled) */
288 SCIP_Bool forbidmultaggrnlvar; /**< whether to forbid multiaggregation of variables that appear in a nonlinear term of a constraint */
289 SCIP_Bool tightenlpfeastol; /**< whether to tighten LP feasibility tolerance during enforcement, if it seems useful */
291 SCIP_Real weakcutthreshold; /**< threshold for when to regard a cut from an estimator as weak */
292 SCIP_Real strongcutmaxcoef; /**< "strong" cuts will be scaled to have their maximal coef in [1/strongcutmaxcoef,strongcutmaxcoef] */
293 SCIP_Bool strongcutefficacy; /**< consider efficacy requirement when deciding whether a cut is "strong" */
295 SCIP_Real enfoauxviolfactor; /**< an expression will be enforced if the "auxiliary" violation is at least enfoauxviolfactor times the "original" violation */
296 SCIP_Real weakcutminviolfactor; /**< retry with weak cuts for constraints with violation at least this factor of maximal violated constraints */
297 char rownotremovable; /**< whether to make rows to be non-removable in the node where they are added (can prevent some cycling): 'o'ff, in 'e'nforcement only, 'a'lways */
298 char violscale; /**< method how to scale violations to make them comparable (not used for feasibility check) */
299 char checkvarlocks; /**< whether variables contained in a single constraint should be forced to be at their lower or upper bounds ('d'isable, change 't'ype, add 'b'ound disjunction) */
302 SCIP_Real branchhighviolfactor; /**< consider a constraint highly violated if its violation is >= this factor * maximal violation among all constraints */
303 SCIP_Real branchhighscorefactor; /**< consider a variable branching score high if its branching score >= this factor * maximal branching score among all variables */
304 SCIP_Real branchviolweight; /**< weight by how much to consider the violation assigned to a variable for its branching score */
305 SCIP_Real branchdualweight; /**< weight by how much to consider the dual values of rows that contain a variable for its branching score */
306 SCIP_Real branchpscostweight; /**< weight by how much to consider the pseudo cost of a variable for its branching score */
307 SCIP_Real branchdomainweight; /**< weight by how much to consider the domain width in branching score */
308 SCIP_Real branchvartypeweight;/**< weight by how much to consider variable type in branching score */
309 char branchscoreagg; /**< how to aggregate several branching scores given for the same expression ('a'verage, 'm'aximum, or 's'um) */
310 char branchviolsplit; /**< method used to split violation in expression onto variables ('u'niform, 'm'idness of solution, 'd'omain width, 'l'ogarithmic domain width) */
311 SCIP_Real branchpscostreliable; /**< minimum pseudo-cost update count required to consider pseudo-costs reliable */
312 char linearizeheursol; /**< whether tight linearizations of nonlinear constraints should be added to cutpool when some heuristics finds a new solution ('o'ff, on new 'i'ncumbents, on 'e'very solution) */
317 SCIP_Longint ntightenlp; /**< number of times we requested solving the LP with a smaller feasibility tolerance when enforcing */
318 SCIP_Longint ndesperatetightenlp; /**< number of times we requested solving the LP with a smaller feasibility tolerance when enforcing because we didn't know anything better */
319 SCIP_Longint ndesperatebranch; /**< number of times we branched on some variable because normal enforcement was not successful */
320 SCIP_Longint ndesperatecutoff; /**< number of times we cut off a node in enforcement because no branching candidate could be found */
321 SCIP_Longint nforcelp; /**< number of times we forced solving the LP when enforcing a pseudo solution */
327 SCIP_LPI* vp_lp[SCIP_MAXVERTEXPOLYDIM+1]; /**< LPs used to compute facets for functions of different dimension */
337 SCIP_RANDNUMGEN* branchrandnumgen; /**< random number generated used in branching variable selection */
341 SCIP_Bool checkedvarlocks; /**< whether variables contained in a single constraint have been already considered */
348 {
369 SCIP_Bool* infeasible, /**< buffer to store whether the problem is infeasible (NULL if not needed) */
370 int* ntightenings /**< buffer to store the number of auxiliary variable tightenings (NULL if not needed) */
391 SCIPdebugMsg(scip, "remove auxiliary variable <%s> for expression %p\n", SCIPvarGetName(mydata->auxvar), (void*)expr);
394 * as this is a relaxation-only variable, no other plugin should use it for deducing any type of reductions or cutting planes
414 SCIP_Bool freeauxvar /**< whether aux var should be released and activity usage counts be reset */
475 {
511 * (if no variable-expression stored for var hashmap, then the var hasn't been used in any constraint, so do nothing
555 SCIPinfoMessage(scip, file, " (<%s> in [%g, %g])", SCIPvarGetName(ownerdata->auxvar), SCIPvarGetLbLocal(ownerdata->auxvar), SCIPvarGetUbLocal(ownerdata->auxvar));
564 * Reevaluate activity if currently stored is not up to date (some bound was changed since last evaluation).
568 {
592 {
628 /* just so that we can use filterpos to recognize whether an expr is a varexpr if not having a SCIP pointer around */
661 assert(SCIPhashmapGetImage(SCIPconshdlrGetData(conshdlr)->var2expr, (void*)var) == (void*)*expr);
748 /* if simplified, then we should have removed inactive variables and replaced common subexpressions,
761 SCIP_CALL( SCIPgetExprVarExprs(scip, consdata->expr, consdata->varexprs, &(consdata->nvarexprs)) );
767 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->varexprs, varexprssize, consdata->nvarexprs) );
775 * when removing duplicate subexpressions it can happen that a var->varexpr map was removed from the hashmap
781 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->var2expr, SCIPgetVarExprVar(consdata->varexprs[i]), consdata->varexprs[i]) );
829 {
871 /* do not look at integer variables, they already have integral bounds, so wouldn't be relaxed */
894 /* do not look at integer variables, they already have integral bounds, so wouldn't be relaxed */
909 /* do not look at integer variables, they already have integral bounds, so wouldn't be relaxed */
913 /* relax bounds by epsilon*max(1,|bnd|), instead of just epsilon as in case 'a', thus we trust the first log(epsilon) digits
914 * however, when domains get small, relaxing can excessively weaken bound tightening, thus do only fraction of |ub-lb| if that is smaller
920 lb = MAX(bnd, lb - MIN(conshdlrdata->varboundrelaxamount * MAX(1.0, REALABS(lb)), 0.001 * REALABS(ub-lb)));
926 ub = MIN(bnd, ub + MIN(conshdlrdata->varboundrelaxamount * MAX(1.0, REALABS(ub)), 0.001 * REALABS(ub-lb)));
934 SCIPerrorMessage("Unsupported value '%c' for varboundrelax option.\n", conshdlrdata->varboundrelax);
956 {
981 SCIPdebugMsg(scip, " exec event %" SCIP_EVENTTYPE_FORMAT " for variable <%s> (local [%g,%g], global [%g,%g])\n", eventtype,
992 /* notify constraints that use this variable expression (expr) to repropagate and possibly resimplify
1008 * TODO we could try be more selective here and only trigger a propagation if a relevant bound has changed,
1009 * that is, we don't need to repropagate x + ... <= rhs if only the upper bound of x has been tightened
1045 * (we could call expr->activity = intevalvar(var, consdhlr) directly, but then the exprhdlr statistics are not updated)
1047 SCIP_CALL( SCIPcallExprInteval(scip, expr, &activity, conshdlrdata->intevalvar, conshdlrdata) );
1091 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &ownerdata->conss, &ownerdata->consssize, ownerdata->nconss + 1) );
1099 ownerdata->consssorted = compIndexConsNonlinear(ownerdata->conss[ownerdata->nconss-2], ownerdata->conss[ownerdata->nconss-1]) > 0;
1110 SCIP_CALL( SCIPcatchVarEvent(scip, SCIPgetVarExprVar(expr), eventtype, eventhdlr, (SCIP_EVENTDATA*)expr, &ownerdata->filterpos) );
1157 /* from now on, activity of var-expr will usually be updated in processVarEvent if variable bound is changing
1158 * since we just registered this eventhdlr, we should make sure that the activity is also up to date now
1163 SCIP_CALL( SCIPcallExprInteval(scip, expr, &activity, intEvalVarBoundTightening, conshdlrdata) );
1167 SCIPdebugMsg(scip, "var-exprhdlr::inteval for var <%s> = [%.20g, %.20g]\n", SCIPvarGetName(SCIPgetVarExprVar(expr)), activity.inf, activity.sup);
1179 * The given constraint is removed from the constraints array in the ownerdata of the variable-expression.
1214 if( !SCIPsortedvecFindPtr((void**)ownerdata->conss, compIndexConsNonlinear, cons, ownerdata->nconss, &pos) )
1216 SCIPerrorMessage("Constraint <%s> not in constraint array of expression for variable <%s>\n", SCIPconsGetName(cons), SCIPvarGetName(SCIPgetVarExprVar(expr)));
1240 SCIP_CALL( SCIPdropVarEvent(scip, SCIPgetVarExprVar(expr), eventtype, eventhdlr, (SCIP_EVENTDATA*)expr, ownerdata->filterpos) );
1287 * @attention Use copyexpr=FALSE only if expr is already "owned" by conshdlr, that is, if expressions were created with exprownerCreate() and ownerdata passed in the last two arguments
1298 SCIP_Bool copyexpr, /**< whether to copy the expression or reuse the given expr (capture it) */
1348 /* copy expression, thereby map variables expressions to already existing variables expressions in var2expr map, or augment var2expr map */
1349 SCIP_CALL( SCIPduplicateExpr(scip, expr, &consdata->expr, mapexprvar, conshdlr, exprownerCreate, (void*)conshdlr) );
1362 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
1373 * If there are negative locks, then return the violation of z ≤ f(x) and sets `violover` to TRUE.
1374 * If there are positive locks, then return the violation of z ≥ f(x) and sets `violunder` to TRUE.
1376 * If f could not be evaluated, then return SCIPinfinity() and set both `violover` and `violunder` to TRUE.
1378 * @note This does not reevaluate the violation, but assumes that the expression has been evaluated
1436 * Assume the expression is f(w), where w are auxiliary variables that were introduced by some nlhdlr.
1439 * If there are negative locks, then return the violation of z ≤ f(w) and sets `violover` to TRUE.
1440 * If there are positive locks, then return the violation of z ≥ f(w) and sets `violunder` to TRUE.
1442 * If f could not be evaluated, then return SCIPinfinity() and set both `violover` and `violunder` to TRUE.
1444 * @note This does not reevaluate the violation, but assumes that f(w) is passed in with auxvalue.
1532 consdata->lhsviol = SCIPisInfinity(scip, -consdata->lhs) ? -SCIPinfinity(scip) : consdata->lhs - activity;
1533 consdata->rhsviol = SCIPisInfinity(scip, consdata->rhs) ? -SCIPinfinity(scip) : activity - consdata->rhs;
1540 * @note This does not reevaluate the violation, but assumes that computeViolation() has been called before.
1559 * @note This does not reevaluate the violation, but assumes that computeViolation() has been called before.
1659 * @note This does not reevaluate the violation, but assumes that computeViolation() has been called before.
1670 /** checks for a linear variable that can be increased or decreased without harming feasibility */
1719 SCIPdebugMsg(scip, "child <%s> locks: %d %d\n", SCIPvarGetName(var), SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL), SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL));
1724 * if we have already one candidate, then take the one where the loss in the objective function is less
1737 * if we have already one candidate, then take the one where the loss in the objective function is less
1754 SCIPdebugMsg(scip, "may increase <%s> to become feasible\n", SCIPvarGetName(consdata->linvarincr));
1758 SCIPdebugMsg(scip, "may decrease <%s> to become feasible\n", SCIPvarGetName(consdata->linvardecr));
1762 /** Given a solution where every nonlinear constraint is either feasible or can be made feasible by
1763 * moving a linear variable, construct the corresponding feasible solution and pass it to the trysol heuristic.
1765 * The method assumes that this is always possible and that not all constraints are feasible already.
1774 SCIP_Bool* success /**< buffer to store whether we succeeded to construct a solution that satisfies all provided constraints */
1804 SCIPdebugMsg(scip, "attempt to make solution from <%s> feasible by shifting linear variable\n",
1805 sol != NULL ? (SCIPsolGetHeur(sol) != NULL ? SCIPheurGetName(SCIPsolGetHeur(sol)) : "tree") : "LP");
1825 ((viol > 0.0 && consdata->linvarincrcoef > 0.0) || (viol < 0.0 && consdata->linvarincrcoef < 0.0)) )
1847 SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var), viol, SCIPconsGetName(conss[c])); /*lint !e613*/
1858 ((viol > 0.0 && consdata->linvardecrcoef < 0.0) || (viol < 0.0 && consdata->linvardecrcoef > 0.0)) )
1880 SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var), viol, SCIPconsGetName(conss[c]));
1889 /* still here... so probably we could not make constraint feasible due to variable bounds, thus give up */
1893 /* if we have a solution that should satisfy all quadratic constraints and has a better objective than the current upper bound,
1896 if( c == nconss && (SCIPisInfinity(scip, SCIPgetUpperbound(scip)) || SCIPisSumLT(scip, SCIPgetSolTransObj(scip, newsol), SCIPgetUpperbound(scip))) )
1898 SCIPdebugMsg(scip, "pass solution with objective val %g to trysol heuristic\n", SCIPgetSolTransObj(scip, newsol));
1913 * Called by addTightEstimatorCuts() for a specific expression, nlhdlr, and estimate-direction (over or under).
1938 ENFOLOG( SCIPinfoMessage(scip, enfologfile, " %sestimate using nlhdlr <%s> for expr %p (%s)\n",
1939 overestimate ? "over" : "under", SCIPnlhdlrGetName(exprenfo->nlhdlr), (void*)expr, SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))); )
1941 SCIP_CALL( SCIPnlhdlrEstimate(scip, conshdlr, exprenfo->nlhdlr, expr, exprenfo->nlhdlrexprdata, sol,
1942 exprenfo->auxvalue, overestimate, overestimate ? SCIPinfinity(scip) : -SCIPinfinity(scip), FALSE, rowpreps, &estimatesuccess, &branchscoresuccess) );
1950 ENFOLOG( SCIPinfoMessage(scip, enfologfile, " estimate of nlhdlr %s failed\n", SCIPnlhdlrGetName(exprenfo->nlhdlr)); )
1963 assert(SCIProwprepGetSidetype(rowprep) == (overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT));
1976 estimateval += SCIProwprepGetCoefs(rowprep)[i] * SCIPgetSolVal(scip, sol, SCIProwprepGetVars(rowprep)[i]);
1978 /* if estimator value is not tight (or even "more than tight", e.g., when estimating in integer vars), then skip */
1982 ENFOLOG( SCIPinfoMessage(scip, enfologfile, " skip non-tight estimator with value %g, expr value %g\n", estimateval, SCIPexprGetEvalValue(expr)); )
1994 ENFOLOG( SCIPinfoMessage(scip, enfologfile, " skip after cleanup failed or made estimator locally valid\n"); )
2019 * Essentially we want to ensure that the LP relaxation is tight in the new solution, if possible.
2021 * To avoid checking explicitly for convexity, we compute estimators via any nlhdlr that didn't say it would
2024 * Since linearization may happen in auxiliary variables, we ensure that auxiliary variables are set
2025 * to the eval-value of its expression, i.e., we change sol so it is also feasible in the extended formulation.
2047 ENFOLOG( SCIPinfoMessage(scip, enfologfile, "add tight estimators in new solution from <%s> to cutpool\n", SCIPheurGetName(SCIPsolGetHeur(sol))); )
2063 if( !SCIPconsIsEnabled(conss[c]) || SCIPconsIsDeleted(conss[c]) || !SCIPconsIsSeparationEnabled(conss[c]) )
2092 for( expr = SCIPexpriterRestartDFS(it, consdata->expr); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2103 /* set value for auxvar in sol to value of expr, in case it is used to compute estimators higher up of this expression */
2120 /* skip nlhdlr that does not participate in separation or looks like it would give only locally-valid estimators
2123 if( ((ownerdata->enfos[e]->nlhdlrparticipation & SCIP_NLHDLR_METHOD_SEPAABOVE) == 0 || ownerdata->enfos[e]->sepaaboveusesactivity) &&
2124 ((ownerdata->enfos[e]->nlhdlrparticipation & SCIP_NLHDLR_METHOD_SEPABELOW) == 0 || ownerdata->enfos[e]->sepabelowusesactivity) )
2127 /* skip nlhdlr_default on sum, as the estimator doesn't depend on the reference point (expr is linear in auxvars) */
2131 /* evaluate the expression w.r.t. the nlhdlrs auxiliary variables, since some nlhdlr expect this before their estimate is called */
2132 SCIP_CALL( SCIPnlhdlrEvalaux(scip, nlhdlr, expr, ownerdata->enfos[e]->nlhdlrexprdata, &ownerdata->enfos[e]->auxvalue, sol) );
2136 SCIPinfoMessage(scip, enfologfile, " (%p): evalvalue %.15g auxvarvalue %.15g, nlhdlr <%s> auxvalue: %.15g\n",
2137 (void*)expr, SCIPexprGetEvalValue(expr), SCIPgetSolVal(scip, sol, ownerdata->auxvar), SCIPnlhdlrGetName(nlhdlr), ownerdata->enfos[e]->auxvalue);
2139 /* due to setting values of auxvars to expr values in sol, the auxvalue should equal to expr evalvalue */
2142 /* if nlhdlr wants to be called for overestimate and does not use local bounds, then call estimate of nlhdlr */
2143 if( (ownerdata->enfos[e]->nlhdlrparticipation & SCIP_NLHDLR_METHOD_SEPAABOVE) && !ownerdata->enfos[e]->sepaaboveusesactivity )
2145 SCIP_CALL( addTightEstimatorCut(scip, conshdlr, conss[c], expr, ownerdata->enfos[e], sol, TRUE, rowpreps) );
2148 /* if nlhdlr wants to be called for underestimate and does not use local bounds, then call estimate of nlhdlr */
2149 if( (ownerdata->enfos[e]->nlhdlrparticipation & SCIP_NLHDLR_METHOD_SEPABELOW) && !ownerdata->enfos[e]->sepabelowusesactivity )
2151 SCIP_CALL( addTightEstimatorCut(scip, conshdlr, conss[c], expr, ownerdata->enfos[e], sol, FALSE, rowpreps) );
2166 {
2188 /* we are only interested in solution coming from some heuristic other than trysol, but not from the tree
2189 * the reason for ignoring trysol solutions is that they may come ~~from an NLP solve in sepalp, where we already added linearizations, or are~~
2195 SCIPdebugMsg(scip, "caught new sol event %" SCIP_EVENTTYPE_FORMAT " from heur <%s>\n", SCIPeventGetType(event), SCIPheurGetName(SCIPsolGetHeur(sol)));
2197 SCIP_CALL( addTightEstimatorCuts(scip, conshdlr, SCIPconshdlrGetConss(conshdlr), SCIPconshdlrGetNConss(conshdlr), sol) );
2202 /** tightens the bounds of the auxiliary variable associated with an expression (or original variable if being a variable-expression) according to given bounds
2204 * The given bounds may very well be the exprs activity (when called from forwardPropExpr()), but can also be some
2229 /* the given bounds must not be empty (we could cope, but we shouldn't be called in this situation) */
2245 force = SCIPconshdlrGetData(conshdlr)->forceboundtightening || SCIPisEQ(scip, bounds.inf, bounds.sup);
2253 SCIPdebugMsg(scip, "tightened lb on auxvar <%s> to %.15g (forced:%u)\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), force);
2257 SCIPdebugMsg(scip, "cutoff when tightening lb on auxvar <%s> to %.15g\n", SCIPvarGetName(var), bounds.inf);
2267 SCIPdebugMsg(scip, "tightened ub on auxvar <%s> to %.15g (forced:%u)\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var), force);
2271 SCIPdebugMsg(scip, "cutoff when tightening ub on auxvar <%s> to %.15g\n", SCIPvarGetName(var), bounds.sup);
2275 /* TODO expr->activity should have been reevaluated now due to boundchange-events, but it used to relax bounds
2283 /** propagate bounds of the expressions in a given expression tree (that is, updates activity intervals)
2292 SCIP_Bool* infeasible, /**< buffer to store whether the problem is infeasible (NULL if not needed) */
2293 int* ntightenings /**< buffer to store the number of auxiliary variable tightenings (NULL if not needed) */
2313 if( SCIPexprGetActivityTag(rootexpr) >= conshdlrdata->lastboundrelax && SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, SCIPexprGetActivity(rootexpr)) )
2315 SCIPdebugMsg(scip, "stored activity of root expr is empty and valid (activitytag >= lastboundrelax (%" SCIP_LONGINT_FORMAT ")), skip forwardPropExpr -> cutoff\n", conshdlrdata->lastboundrelax);
2329 SCIPdebugMsg(scip, "activitytag of root expr equals curboundstag (%" SCIP_LONGINT_FORMAT "), skip forwardPropExpr\n", conshdlrdata->curboundstag);
2331 assert(!SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, SCIPexprGetActivity(rootexpr))); /* handled in previous if() */
2339 /* if activity of rootexpr is not used, but expr participated in detect (nenfos >= 0), then we do nothing
2340 * it seems wrong to be called for such an expression (unless we are in detect at the moment), so I add a SCIPABORT()
2344 if( ownerdata->nenfos >= 0 && ownerdata->nactivityusesprop == 0 && ownerdata->nactivityusessepa == 0 && !conshdlrdata->indetect)
2369 if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, SCIPexprGetActivity(child)) && infeasible != NULL )
2389 /* for var exprs where varevents are catched, activity is updated immediately when the varbound has been changed
2395 SCIPexprGetActivityTag(expr) >= conshdlrdata->lastvaractivitymethodchange && !conshdlrdata->globalbounds )
2400 SCIP_CALL( SCIPcallExprInteval(scip, expr, &exprhdlrinterval, conshdlrdata->intevalvar, conshdlrdata) );
2405 SCIPdebugMsg(scip, "skip interval evaluation of expr for var <%s> [%g,%g]\n", SCIPvarGetName(SCIPgetVarExprVar(expr)), SCIPexprGetActivity(expr).inf, SCIPexprGetActivity(expr).sup);
2441 /* if activity of expr is not used, but expr participated in detect (nenfos >= 0), then do nothing */
2442 if( ownerdata->nenfos >= 0 && ownerdata->nactivityusesprop == 0 && ownerdata->nactivityusessepa == 0 && !conshdlrdata->indetect )
2445 SCIPdebugMsg(scip, "expr %p activity is not used but enfo initialized, skip inteval\n", (void*)expr);
2453 SCIPdebugMsgPrint(scip, ", current activity = [%.20g, %.20g]\n", SCIPexprGetActivity(expr).inf, SCIPexprGetActivity(expr).sup);
2464 for( e = 0; e < ownerdata->nenfos && !SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, activity); ++e )
2473 /* skip nlhdlr if it does not provide interval evaluation (so it may only provide reverse propagation) */
2482 SCIPdebugMsg(scip, " nlhdlr <%s>::inteval = [%.20g, %.20g]", SCIPnlhdlrGetName(nlhdlr), nlhdlrinterval.inf, nlhdlrinterval.sup);
2494 /* for node without enforcement (before or during detect), call the callback of the exprhdlr directly */
2496 SCIP_CALL( SCIPcallExprInteval(scip, expr, &exprhdlrinterval, conshdlrdata->intevalvar, conshdlrdata) );
2498 SCIPdebugMsg(scip, " exprhdlr <%s>::inteval = [%.20g, %.20g]", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), exprhdlrinterval.inf, exprhdlrinterval.sup);
2509 * this should undo the addition of some unnecessary safety added by use of nextafter() in interval arithmetics, e.g., when doing pow()
2510 * it would be ok to use ceil() and floor(), but for safety we use SCIPceil and SCIPfloor for now
2511 * do this only if using boundtightening-inteval and not in redundancy check (there we really want to relax all variables)
2512 * boundtightening-inteval does not relax integer variables, so can omit expressions without children
2515 if( SCIPexprIsIntegral(expr) && conshdlrdata->intevalvar == intEvalVarBoundTightening && SCIPexprGetNChildren(expr) > 0 )
2526 /* mark the current node to be infeasible if either the lower/upper bound is above/below +/- SCIPinfinity()
2531 SCIPdebugMsg(scip, "cut off due to activity [%g,%g] beyond infinity\n", activity.inf, activity.sup);
2547 SCIP_CALL( tightenAuxVarBounds(scip, conshdlr, expr, activity, &tighteninfeasible, ntightenings) );
2575 /** returns whether intersecting `oldinterval` with `newinterval` would provide a properly smaller interval
2577 * If `subsetsufficient` is TRUE, then the intersection being smaller than oldinterval is sufficient.
2587 SCIP_Bool subsetsufficient, /**< whether the intersection being a proper subset of oldinterval is sufficient */
2609 if( !SCIPisEQ(scip, oldinterval.inf, oldinterval.sup) && SCIPisEQ(scip, MAX(oldinterval.inf, newinterval.inf), MIN(oldinterval.sup, newinterval.sup)) )
2612 /* check whether lower bound on interval will be better by SCIP's quality measures for boundchanges */
2616 /* check whether upper bound on interval will be better by SCIP's quality measures for boundchanges */
2623 /** propagates bounds for each sub-expression in the `reversepropqueue` by starting from the root expressions
2627 * @note Calling this function requires feasible intervals for each sub-expression; this is guaranteed by calling
2636 SCIP_Bool* infeasible, /**< buffer to update whether an expression's bounds were propagated to an empty interval */
2653 * when reverseprop finds a tightening for an expression, then that expression is added to the queue (within the reverseprop call)
2670 /* since the expr was in the propagation queue, the propbounds should belong to current propagation and should not be empty
2671 * (propbounds being entire doesn't make much sense, so assert this for now, too, but that could be removed)
2678 * I doubt this would be much helpful, since propbounds are already subset of activity and we also propagate
2711 SCIPdebugMsgPrint(scip, " in [%g,%g] using nlhdlr <%s>\n", propbounds.inf, propbounds.sup, SCIPnlhdlrGetName(nlhdlr));
2715 SCIP_CALL( SCIPnlhdlrReverseprop(scip, conshdlr, nlhdlr, expr, ownerdata->enfos[e]->nlhdlrexprdata, propbounds, infeasible, &nreds) );
2722 /* if expr without enforcement (before detect), call reverse propagation callback of exprhdlr directly */
2729 SCIPdebugMsgPrint(scip, " in [%g,%g] using exprhdlr <%s>\n", SCIPexprGetActivity(expr).inf, SCIPexprGetActivity(expr).sup, SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)));
2732 /* if someone added an expr without nlhdlr into the reversepropqueue, then this must be because its enfo hasn't
2747 SCIP_CALL( SCIPtightenExprIntervalNonlinear(scip, SCIPexprGetChildren(expr)[c], childrenbounds[c], infeasible, ntightenings) );
2754 /* reset inpropqueue for all remaining expr's in queue (can happen in case of early stop due to infeasibility) */
2774 * Reverse propagation tries to derive tighter variable bounds by reversing the activity computation, using the constraints
2778 * 1. apply forward propagation (update activities) for all constraints not marked as propagated
2779 * 2. if presolve or propauxvars is disabled: collect expressions for which the constraint sides provide tighter bounds
2780 * if solve and propauxvars is enabled: collect expressions for which auxvars (including those in root exprs)
2786 * @note After calling forward propagation for a constraint, we mark this constraint as propagated. This flag might be
2787 * reset during the reverse propagation when we find a bound tightening of a variable expression contained in the
2790 * TODO should we distinguish between expressions where activity information is used for separation and those where not,
2865 if( SCIPconsIsDeleted(conss[i]) || !SCIPconsIsActive(conss[i]) || !SCIPconsIsPropagationEnabled(conss[i]) )
2868 /* skip already propagated constraints, i.e., constraints where no (original) variable has changed and thus
2875 SCIPdebugMsg(scip, "call forwardPropExpr() for constraint <%s> (round %d): ", SCIPconsGetName(conss[i]), roundnr);
2880 assert(cutoff || !SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, SCIPexprGetActivity(consdata->expr)));
2884 SCIPdebugMsg(scip, " -> cutoff in forwardPropExpr (due to domain error or auxvar tightening) of constraint <%s>\n", SCIPconsGetName(conss[i]));
2891 /* TODO for a constraint that only has an auxvar for consdata->expr (e.g., convex quadratic), we could also just do the if(TRUE)-branch */
2895 * (if we have auxvar (not in presolve), then bounds of the auxvar are initially set to constraint sides,
2901 SCIP_Real lhs = SCIPisInfinity(scip, -consdata->lhs) ? -SCIP_INTERVAL_INFINITY : consdata->lhs - conshdlrdata->conssiderelaxamount;
2902 SCIP_Real rhs = SCIPisInfinity(scip, consdata->rhs) ? SCIP_INTERVAL_INFINITY : consdata->rhs + conshdlrdata->conssiderelaxamount;
2909 SCIP_CALL( SCIPtightenExprIntervalNonlinear(scip, consdata->expr, conssides, &cutoff, &ntightenings) );
2921 for( expr = SCIPexpriterGetCurrent(revpropcollectit); !SCIPexpriterIsEnd(revpropcollectit) && !cutoff; expr = SCIPexpriterGetNext(revpropcollectit) )
2939 SCIPdebugMsg(scip, " -> cutoff after intersect with conssides of constraint <%s>\n", SCIPconsGetName(conss[i]));
2951 /* mark constraint as propagated; this will be reset via the event system when we find a variable tightening */
2988 /** calls the reverseprop callbacks of all nlhdlrs in all expressions in all constraints using activity as bounds
2990 * This is meant to propagate any domain restrictions on functions onto variable bounds, if possible.
2993 * Therefore, a good place to call this function is immediately after propConss() or after forwardPropExpr() if outside propagation.
3034 if( SCIPconsIsDeleted(conss[c]) || !SCIPconsIsActive(conss[c]) || !SCIPconsIsPropagationEnabled(conss[c]) )
3040 for( expr = SCIPexpriterRestartDFS(it, consdata->expr); !SCIPexpriterIsEnd(it) && !cutoff; expr = SCIPexpriterGetNext(it) )
3058 SCIPdebugMsg(scip, "propExprDomains calling reverseprop for expression %p [%g,%g]\n", (void*)expr,
3061 SCIP_CALL( SCIPnlhdlrReverseprop(scip, conshdlr, nlhdlr, expr, ownerdata->enfos[e]->nlhdlrexprdata,
3067 SCIPdebugMsg(scip, "detect infeasibility for constraint <%s> during reverseprop()\n", SCIPconsGetName(conss[c]));
3126 SCIPexpriterSetStagesDFS(it, SCIP_EXPRITER_ENTEREXPR | SCIP_EXPRITER_VISITINGCHILD | SCIP_EXPRITER_LEAVEEXPR);
3158 if( ownerdata->nlockspos == nlockspos && ownerdata->nlocksneg == nlocksneg && SCIPexprGetNChildren(expr) > 0
3166 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &ownerdata->monotonicity, SCIPexprGetNChildren(expr)) );
3181 if( ownerdata->nlockspos == 0 && ownerdata->nlocksneg == 0 && ownerdata->monotonicity != NULL )
3184 /* keep this assert for checking whether someone changed an expression without updating locks properly */
3198 /* NOTE: the monotonicity stored in an expression might be different from the result obtained by
3201 monotonicity = ownerdata->monotonicity != NULL ? ownerdata->monotonicity[SCIPexpriterGetChildIdxDFS(it)] : SCIP_MONOTONE_UNKNOWN;
3245 * Locks for a nonlinear constraint are used to update locks for all sub-expressions and variables.
3247 * consider the constraint \f$x^2 \leq 1\f$ with \f$x \in [-2,-1]\f$ implies an up-lock for the root
3248 * expression (pow) and a down-lock for its child \f$x\f$ because \f$x^2\f$ is decreasing on [-2,-1].
3249 * Since the monotonicity (and thus the locks) might also depend on variable bounds, the function remembers
3250 * the computed monotonicity information of each expression until all locks of an expression have been removed,
3251 * which implies that updating the monotonicity information during the next locking of this expression does not
3254 * @note When modifying the structure of an expression, e.g., during simplification, it is necessary to remove all
3255 * locks from an expression and repropagating them after the structural changes have been applied.
3256 * Because of existing common sub-expressions, it might be necessary to remove the locks of all constraints
3291 SCIP_CALL( propagateLocks(scip, consdata->expr, nlockspos + nlocksneg, nlockspos + nlocksneg));
3306 /** create a nonlinear row representation of a nonlinear constraint and stores them in consdata */
3342 SCIP_CALL( SCIPchgNlRowConstant(scip, consdata->nlrow, SCIPgetConstantExprSum(consdata->expr)) );
3344 /* a sum-expression that will hold the nonlinear terms and be passed to the nlrow eventually */
3345 SCIP_CALL( SCIPcreateExprSum(scip, &nonlinpart, 0, NULL, NULL, 0.0, exprownerCreate, (void*)SCIPconsGetHdlr(cons)) );
3353 SCIP_CALL( SCIPaddLinearCoefToNlRow(scip, consdata->nlrow, SCIPgetVarExprVar(child), coefs[i]) );
3379 * If handlers have same enforcement priority, then compare by detection priority, then by name.
3383 {
3438 /* check which enforcement methods are required by setting flags in enforcemethods for those that are NOT required
3440 * - if auxiliary variable is used, but nobody positively (up) locks expr -> only need to enforce expr >= auxvar -> no need for underestimation
3441 * - if auxiliary variable is used, but nobody negatively (down) locks expr -> only need to enforce expr <= auxvar -> no need for overestimation
3457 /* it doesn't make sense to have been called on detectNlhdlr, if the expr isn't used for anything */
3460 /* all methods that have not been flagged above are the ones that we want to be handled by nlhdlrs */
3489 conshdlrdata->registerusesactivitysepabelow = FALSE; /* SCIPregisterExprUsageNonlinear() as called by detect may set this to TRUE */
3490 conshdlrdata->registerusesactivitysepaabove = FALSE; /* SCIPregisterExprUsageNonlinear() as called by detect may set this to TRUE */
3492 SCIP_CALL( SCIPnlhdlrDetect(scip, ownerdata->conshdlr, nlhdlr, expr, cons, &enforcemethodsnew, &nlhdlrparticipating, &nlhdlrexprdata) );
3497 /* detection is only allowed to augment to nlhdlrenforcemethods, so previous enforcemethods must still be set */
3500 /* Because of the previous assert, nlhdlrenforcenew ^ enforcemethods are the methods enforced by this nlhdlr.
3518 /* nlhdlr cannot have added an enforcement method if it doesn't participate (actually redundant due to previous asserts) */
3526 SCIPdebugMsg(scip, "nlhdlr <%s> detect successful; sepabelow: %s, sepaabove: %s, activity: %s\n",
3528 ((nlhdlrenforcemethods & SCIP_NLHDLR_METHOD_SEPABELOW) != 0) ? "enforcing" : ((nlhdlrparticipating & SCIP_NLHDLR_METHOD_SEPABELOW) != 0) ? "participating" : "no",
3529 ((nlhdlrenforcemethods & SCIP_NLHDLR_METHOD_SEPAABOVE) != 0) ? "enforcing" : ((nlhdlrparticipating & SCIP_NLHDLR_METHOD_SEPAABOVE) != 0) ? "participating" : "no",
3530 ((nlhdlrenforcemethods & SCIP_NLHDLR_METHOD_ACTIVITY) != 0) ? "enforcing" : ((nlhdlrparticipating & SCIP_NLHDLR_METHOD_ACTIVITY) != 0) ? "participating" : "no");
3533 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &ownerdata->enfos, &enfossize, ownerdata->nenfos+1) );
3539 ownerdata->enfos[ownerdata->nenfos]->sepabelowusesactivity = conshdlrdata->registerusesactivitysepabelow;
3540 ownerdata->enfos[ownerdata->nenfos]->sepaaboveusesactivity = conshdlrdata->registerusesactivitysepaabove;
3550 * (as long as the expression provides its callbacks, the default nlhdlr should have provided all enforcement methods)
3565 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &ownerdata->enfos, enfossize, ownerdata->nenfos) );
3588 assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_INITSOLVE || SCIPgetStage(scip) == SCIP_STAGE_SOLVING); /* should only be called in presolve or initsolve or consactive */
3598 /* ensure that activities are recomputed w.r.t. the global variable bounds if CONSACTIVE is called in a local node;
3599 * for example, this happens if globally valid nonlinear constraints are added during the tree search
3616 * TODO we may relax this with a little more programming effort when required, see also TODO in INITLP
3618 assert((!SCIPconsIsSeparated(conss[i]) && !SCIPconsIsEnforced(conss[i])) || SCIPconsIsInitial(conss[i]));
3623 /* because of common sub-expressions it might happen that we already detected a nonlinear handler and added it to the expr
3625 * HOWEVER: most likely we have been running DETECT with cons == NULL, which may interest less nlhdlrs
3634 /* if constraint will be enforced, and we are in solve, then ensure auxiliary variable for root expression
3635 * this way we can treat the root expression like any other expression when enforcing via separation
3641 SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE && (SCIPconsIsSeparated(conss[i]) || SCIPconsIsEnforced(conss[i])),
3650 for( expr = SCIPexpriterRestartDFS(it, consdata->expr); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
3660 * auxvar == expr (or auxvar >= expr or auxvar <= expr) or we are at the root expression (expr==consdata->expr)
3663 * activity of this expression is updated; this someone would also benefit from better bounds on the activity of this expression
3666 if( ownerdata->nauxvaruses > 0 || ownerdata->nactivityusesprop > 0 || ownerdata->nactivityusessepa > 0 )
3675 * even though we have not actually run detectNlhdlr, because no nlhdlr showed interest in this expr,
3676 * in some situations (forwardPropExpr, to be specific) we will have to distinguish between exprs for which
3677 * we have not initialized enforcement yet (nenfos < 0) and expressions which are just not used in enforcement (nenfos == 0)
3683 /* include this constraint into the next propagation round because the added nlhdlr may do find tighter bounds now */
3699 /* ensure that all activities (except for var-exprs) are reevaluated since better methods may be available now */
3710 * This initializes data in a constraint that is used for separation, propagation, etc, and assumes that expressions will
3718 * This function can be called in presolve and solve and can be called several times with different sets of constraints,
3733 /* check for a linear variable that can be increase or decreased without harming feasibility */
3754 SCIP_CALL( SCIPhasExprCurvature(scip, consdata->expr, SCIP_EXPRCURV_CONCAVE, &success, NULL) );
3769 SCIPwarningMessage(scip, "Nonlinear constraint <%s> has finite left- and right-hand side, but constraints/nonlinear/assumeconvex is enabled.\n", SCIPconsGetName(conss[c]));
3774 consdata->curv = !SCIPisInfinity(scip, consdata->rhs) ? SCIP_EXPRCURV_CONVEX : SCIP_EXPRCURV_CONCAVE;
3777 SCIPdebugMsg(scip, "root curvature of constraint %s = %d\n", SCIPconsGetName(conss[c]), consdata->curv);
3842 rootactivityvalid = SCIPexprGetActivityTag(consdata->expr) >= SCIPconshdlrGetData(conshdlr)->lastboundrelax;
3844 for( expr = SCIPexpriterRestartDFS(it, consdata->expr); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
3846 SCIPdebugMsg(scip, "exitsepa and free nonlinear handler data for expression %p\n", (void*)expr);
3848 /* remove nonlinear handlers in expression and their data and auxiliary variables; reset activityusage count */
3857 * this is mainly to ensure that we do not leave invalid activities in parts of the expression tree where activity was not used,
3858 * e.g., an expr's activity was kept up to date by a nlhdlr, but without using some childs activity
3878 /* forget about linear variables that can be increased or decreased without harming feasibility */
3891 /** helper method to decide whether a given expression is product of at least two binary variables */
3944 int* childidxs, /**< array to store the index of the child of each stored bilinear binary product */
4015 /* TODO could compute minact and maxact for facvar=0 and facvar=1 separately, taking implied bounds into account, allowing for possibly tighter big-M's below */
4025 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "binreform_%s_%s", SCIPconsGetName(cons), SCIPvarGetName(facvar));
4026 SCIP_CALL( SCIPcreateVarBasic(scip, &auxvar, name, minact, maxact, 0.0, integral ? SCIP_VARTYPE_IMPLINT : SCIP_VARTYPE_CONTINUOUS) );
4032 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "binreform_%s_%s_1", SCIPconsGetName(cons), SCIPvarGetName(facvar));
4033 SCIP_CALL( SCIPcreateConsBasicVarbound(scip, &newcons, name, auxvar, facvar, -maxact, -SCIPinfinity(scip), 0.0) );
4043 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "binreform_%s_%s_2", SCIPconsGetName(cons), SCIPvarGetName(facvar));
4044 SCIP_CALL( SCIPcreateConsBasicVarbound(scip, &newcons, name, auxvar, facvar, -minact, 0.0, SCIPinfinity(scip)) );
4052 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "binreform_%s_%s_3", SCIPconsGetName(cons), SCIPvarGetName(facvar));
4053 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &newcons, name, nvars, vars, coefs, minact, SCIPinfinity(scip)) );
4065 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "binreform_%s_%s_4", SCIPconsGetName(cons), SCIPvarGetName(facvar));
4066 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &newcons, name, nvars, vars, coefs, -SCIPinfinity(scip), maxact) );
4086 /** helper method to generate an expression for a sum of products of binary variables; note that the method captures the generated expression */
4094 SCIP_EXPR** newexpr, /**< pointer to store the expression that represents the binary quadratic */
4196 SCIPdebugMsg(scip, "consider facvar = %s with count = %d\n", SCIPvarGetName(facvar), count[SCIPvarGetIndex(vars[i])]);
4234 assert(count[SCIPvarGetIndex(facvar)] == 0); /* facvar should not appear in any other bilinear term */
4237 SCIP_CALL( reformulateFactorizedBinaryQuadratic(scip, conshdlr, cons, facvar, tmpvars, tmpcoefs, ntmpvars, &exprs[nexprs], naddconss) );
4259 SCIP_CALL( SCIPcreateExprSum(scip, newexpr, nexprs, exprs, exprcoefs, SCIPgetConstantExprSum(sumexpr), exprownerCreate, (void*)conshdlr) );
4261 /* release all expressions that have been generated by reformulateFactorizedBinaryQuadratic() */
4284 /** helper method to create an AND constraint or varbound constraints for a given binary product expression */
4291 int* naddconss, /**< pointer to update the total number of added constraints (might be NULL) */
4332 /* use variable bound constraints if it is a bilinear product and there is no empathy for an AND constraint */
4343 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "binreform_%s_%s_1", SCIPvarGetName(x), SCIPvarGetName(y));
4344 SCIP_CALL( SCIPcreateConsBasicVarbound(scip, &cons, name, x, w, -1.0, 0.0, SCIPinfinity(scip)) );
4349 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "binreform_%s_%s_2", SCIPvarGetName(x), SCIPvarGetName(y));
4350 SCIP_CALL( SCIPcreateConsBasicVarbound(scip, &cons, name, y, w, -1.0, 0.0, SCIPinfinity(scip)) );
4357 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "binreform_%s_%s_3", SCIPvarGetName(x), SCIPvarGetName(y));
4358 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name, 3, vars, coefs, -SCIPinfinity(scip), 1.0) );
4393 /** helper method to generate an expression for the product of binary variables; note that the method captures the generated expression */
4398 SCIP_HASHMAP* exprmap, /**< map to remember generated variables for visited product expressions */
4401 int* naddconss, /**< pointer to update the total number of added constraints (might be NULL) */
4402 int* nchgcoefs /**< pointer to update the total number of changed coefficients (might be NULL) */
4433 SCIPdebugMsg(scip, " product expression %p has been considered for the first time\n", (void*)prodexpr);
4509 SCIP_CALL( SCIPcreateExprSum(scip, newexpr, 2, sum_children, sum_coefs, -1.0, exprownerCreate, (void*)conshdlr) );
4526 SCIP_CALL( getBinaryProductExprDo(scip, conshdlr, prodexpr, newexpr, naddconss, conshdlrdata->reformbinprodsand) );
4532 SCIP_CALL( getBinaryProductExprDo(scip, conshdlr, prodexpr, newexpr, naddconss, conshdlrdata->reformbinprodsand) );
4548 SCIP_HASHMAP* exprmap, /**< map to remember generated variables for visited product expressions */
4550 int* naddconss, /**< pointer to update the total number of added constraints (might be NULL) */
4551 int* nchgcoefs /**< pointer to update the total number of changed coefficients (might be NULL) */
4572 for( expr = SCIPexpriterRestartDFS(it, consdata->expr); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
4583 /* try to factorize variables in a sum expression that contains several products of binary variables */
4586 SCIP_CALL( getFactorizedBinaryQuadraticExpr(scip, conshdlr, cons, childexpr, conshdlrdata->reformbinprodsfac, &newexpr, naddconss) );
4592 SCIP_CALL( getBinaryProductExpr(scip, conshdlr, exprmap, childexpr, &newexpr, naddconss, nchgcoefs) );
4602 /* note that the expression has been captured by getBinaryProductExpr and SCIPreplaceExprChild */
4616 * Each term \f$x_i x_j\f$ is reformulated with the help of an extra (implicit integer) variable \f$z_{ij}\f$ in {0,1}:
4621 * Before reformulating \f$x_i x_j\f$ in this way, it is checked whether there is a clique that contains \f$x_i\f$ and \f$x_j\f$.
4629 * The reformulation using \f$z_{ij}\f$ or the cliques is implemented in getBinaryProductExpr().
4631 * Introducing too many extra variables and constraints can have a negative impact on the performance (e.g., due to
4632 * slow probing). For this reason, it is checked in getFactorizedBinaryQuadraticExpr() whether \f$\sum_{i,j} Q_{ij} x_i x_j\f$
4633 * contains large (≥ `reformbinprodsfac` parameter) lower sums of the form \f$x_i \sum_j Q_{ij} x_j\f$.
4643 * We mark \f$w_i\f$ to be implicit integer if all \f$Q_{ij}\f$ are integer. After each replacement of a lower sum, it
4644 * is checked whether there are enough terms left to factorize other binary variables. Lower sums with a larger number
4654 int* nchgcoefs /**< pointer to store the total number of changed coefficients (might be NULL) */
4695 SCIP_CALL( getFactorizedBinaryQuadraticExpr(scip, conshdlr, conss[c], consdata->expr, conshdlrdata->reformbinprodsfac, &newexpr, naddconss) );
4709 SCIP_CALL( replaceBinaryProducts(scip, conshdlr, conss[c], exprmap, it, naddconss, nchgcoefs) );
4721 * Let \f$n_+\f$ the number of positive coefficients \f$c_i\f$ and \f$n_-\f$ be the number of negative coefficients.
4753 /* handle special case when constraint is l <= -f(x) <= r and f(x) not a sum: simplfy ensures f is not a sum */
4789 SCIP_CALL( SCIPcreateExprSum(scip, &expr, nchildren, SCIPexprGetChildren(consdata->expr), newcoefs, -constant, exprownerCreate, (void*)conshdlr) );
4836 /* if root expression is sum, then forbid multiaggregation only for variables that are not in linear terms of sum,
4851 for( expr = SCIPexpriterRestartDFS(it, child); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
4860 for( expr = SCIPexpriterRestartDFS(it, consdata->expr); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
4882 SCIP_PRESOLTIMING presoltiming, /**< presolve timing (SCIP_PRESOLTIMING_ALWAYS if not in presolving) */
4912 /* set havechange to TRUE in the first call of canonicalize; otherwise we might not replace common subexpressions */
4915 /* free nonlinear handlers information from expressions */ /* TODO can skip this in first presolve round */
4970 /* call this function before simplification because expressions might not be simplified after reformulating
4971 * binary products; the detection of some nonlinear handlers might assume that expressions are simplified
4973 SCIP_CALL( presolveBinaryProducts(scip, conshdlr, conss, nconss, &tmpnaddconss, &tmpnchgcoefs) );
4998 SCIP_CALL( SCIPsimplifyExpr(scip, consdata->expr, &simplified, &changed, infeasible, exprownerCreate, (void*)conshdlr) );
5004 /* If root expression changed, then we need to take care updating the locks as well (the consdata is the one holding consdata->expr "as a child").
5005 * If root expression did not change, some subexpression may still have changed, but the locks were taking care of in the corresponding SCIPreplaceExprChild() call.
5034 /* handle constant root expression; either the problem is infeasible or the constraint is redundant */
5038 if( (!SCIPisInfinity(scip, -consdata->lhs) && SCIPisFeasNegative(scip, value - consdata->lhs)) ||
5041 SCIPdebugMsg(scip, "<%s> with constant expression found infeasible\n", SCIPconsGetName(conss[i]));
5080 /* TODO this is a possibly expensive way to update the variable expressions stored inside an expression which might have
5081 * been changed after simplification; now we completely recollect all variable expression and variable events
5084 /* Each variable stores the constraints for which it catched varbound events sorted by the constraint index.
5085 * Thus, for performance reasons, it is better to call dropVarEvents in descending order of constraint index.
5111 * a multiaggregation of a nonlinear variable can yield to a large increase in expressions due to
5204 SCIPconsGetName(conss[c]), consdata->rhs, imgconsdata->lhs, SCIPconsGetName(conss[idx]), imgconsdata->rhs);
5207 if( !updatelocks[idx] && ((SCIPisInfinity(scip, -imgconsdata->lhs) && !SCIPisInfinity(scip, -consdata->lhs))
5278 * (actually some assert complains if trying SCIPisRelEQ if both bounds are at different infinity)
5301 * Checks whether the activity of constraint functions is a subset of the constraint sides (relaxed by feastol).
5302 * To compute the activity, we use forwardPropExpr(), but relax variable bounds by feastol, because solutions to be checked
5304 * This is the main reason why the redundancy check is not done in propConss(), which relaxes variable bounds by epsilon only.
5308 * @todo it would be sufficient to check constraints for which we know that they are not currently violated by a valid solution
5310 * @note This could should not run during solving, because the forwardProp takes the bounds of auxiliary variables into account.
5311 * For the root expression, these bounds are already set to the constraint sides, so that the activity of every expression
5347 * we do this here to trigger a reevaluation of all variable bounds, since we will relax variable bounds
5368 /* handle constant expressions separately: either the problem is infeasible or the constraint is redundant */
5376 SCIPdebugMsg(scip, "constant constraint <%s> is infeasible: %g in [%g,%g] ", SCIPconsGetName(conss[i]), value, consdata->lhs, consdata->rhs);
5382 SCIPdebugMsg(scip, "constant constraint <%s> is redundant: %g in [%g,%g] ", SCIPconsGetName(conss[i]), value, consdata->lhs, consdata->rhs);
5390 /* handle variable expressions separately: tighten variable bounds to constraint sides, then remove constraint (now redundant) */
5399 SCIPdebugMsg(scip, "variable constraint <%s> can be made redundant: <%s>[%g,%g] in [%g,%g]\n", SCIPconsGetName(conss[i]), SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), consdata->lhs, consdata->rhs);
5432 * we relax variable bounds by feastol here, as solutions that are checked later can also violate
5434 * (relaxing fixed variables seems to be too much, but they would be removed by presolve soon anyway)
5440 assert(*cutoff || !SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, SCIPexprGetActivity(consdata->expr)));
5453 * we could accept every solution that violates constraints up to feastol as redundant, so this is the most permissive we can be
5456 SCIPisInfinity(scip, -consdata->lhs) ? -SCIP_INTERVAL_INFINITY : consdata->lhs - SCIPfeastol(scip),
5457 SCIPisInfinity(scip, consdata->rhs) ? SCIP_INTERVAL_INFINITY : consdata->rhs + SCIPfeastol(scip));
5461 SCIPdebugMsg(scip, " -> redundant: activity [%g,%g] within sides [%g,%g]\n", activity.inf, activity.sup, consdata->lhs, consdata->rhs);
5469 SCIPdebugMsg(scip, " -> not redundant: activity [%g,%g] not within sides [%g,%g]\n", activity.inf, activity.sup, consdata->lhs, consdata->rhs);
5473 /* make sure all activities are reevaluated again, since we relaxed bounds in a different way */
5482 /** tries to automatically convert a nonlinear constraint into a more specific and more specialized constraint */
5490 int* naddconss /**< buffer to increase with number of additional constraints created during upgrade */
5523 SCIPdebugMsg(scip, "upgrading nonlinear constraint <%s> (up to %d upgrade methods): ", SCIPconsGetName(cons), conshdlrdata->nconsupgrades);
5537 SCIP_CALL( conshdlrdata->consupgrades[i]->consupgd(scip, cons, consdata->nvarexprs, &nupgdconss_, upgdconss, upgdconsssize) );
5546 SCIP_CALL( conshdlrdata->consupgrades[i]->consupgd(scip, cons, consdata->nvarexprs, &nupgdconss_, upgdconss, upgdconsssize) );
5568 /* count the first upgrade constraint as constraint upgrade and the remaining ones as added constraints */
5586 /** returns whether the variable of a given variable expression is a candidate for presolveSingleLockedVars(), i.e.,
5587 * the variable is only contained in a single nonlinear constraint, has no objective coefficient, has finite
5610 && !SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) && !SCIPisInfinity(scip, SCIPvarGetUbGlobal(var))
5615 /** removes all variable expressions that are contained in a given expression from a hash map */
5626 for( e = SCIPexpriterRestartDFS(it, expr); !SCIPexpriterIsEnd(it); e = SCIPexpriterGetNext(it) )