|
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
cons_quadratic.c
Go to the documentation of this file.
17 * @brief constraint handler for quadratic constraints \f$\textrm{lhs} \leq \sum_{i,j=1}^n a_{i,j} x_i x_j + \sum_{i=1}^n b_i x_i \leq \textrm{rhs}\f$
22 * @todo SCIP might fix linear variables on +/- infinity; remove them in presolve and take care later
25 * @todo check if some quadratic terms appear in several constraints and try to simplify (e.g., nous1)
28 * @todo sort order in bilinvar1/bilinvar2 such that the var which is involved in more terms is in bilinvar1, and use this info propagate and AddLinearReform
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
55 #define CONSHDLR_ENFOPRIORITY -50 /**< priority of the constraint handler for constraint enforcing */
56 #define CONSHDLR_CHECKPRIORITY -4000000 /**< priority of the constraint handler for checking feasibility */
57 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
58 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
59 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
61 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
62 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
63 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
64 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
66 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
67 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
71 #define INITLPMAXVARVAL 1000.0 /**< maximal absolute value of variable for still generating a linearization cut at that point in initlp */
73 /* Activating this define enables reformulation of bilinear terms x*y with implications from x to y into linear terms.
74 * However, implications are not enforced by SCIP. Thus, if, e.g., the used implication was derived from this constraint and we then reformulate the constraint,
103 int varidx; /**< the index of the variable which bound change is caught, positive for linear variables, negative for quadratic variables */
134 unsigned int bilinmerged:1; /**< are equal bilinear terms (and bilinear terms with zero coefficient) already merged? */
140 unsigned int ispropagated:1; /**< was the constraint propagated with respect to the current bounds ? */
141 unsigned int ispresolved:1; /**< did we checked for possibilities of upgrading or implicit integer variables ? */
142 unsigned int initialmerge:1; /**< did we perform an initial merge and clean in presolving yet ? */
144 unsigned int isimpladded:1; /**< has there been an implication added for a binary variable in a bilinear term? */
148 SCIP_Real minlinactivity; /**< sum of minimal activities of all linear terms with finite minimal activity */
149 SCIP_Real maxlinactivity; /**< sum of maximal activities of all linear terms with finite maximal activity */
152 SCIP_INTERVAL quadactivitybounds; /**< bounds on the activity of the quadratic term, if up to date, otherwise empty interval */
154 SCIP_Real lhsviol; /**< violation of lower bound by current solution (used temporarily inside constraint handler) */
155 SCIP_Real rhsviol; /**< violation of lower bound by current solution (used temporarily inside constraint handler) */
157 int linvar_maydecrease; /**< index of a variable in linvars that may be decreased without making any other constraint infeasible, or -1 if none */
158 int linvar_mayincrease; /**< index of a variable in linvars that may be increased without making any other constraint infeasible, or -1 if none */
160 SCIP_VAR** sepaquadvars; /**< variables corresponding to quadvarterms to use in separation, only available in solving stage */
161 int* sepabilinvar2pos; /**< position of second variable in bilinear terms to use in separation, only available in solving stage */
162 SCIP_Real lincoefsmin; /**< minimal absolute value of coefficients in linear part, only available in solving stage */
163 SCIP_Real lincoefsmax; /**< maximal absolute value of coefficients in linear part, only available in solving stage */
166 SCIP_Real* factorright; /**< coefficients of right factor if constraint function is factorable */
176 {
177 SCIP_DECL_QUADCONSUPGD((*quadconsupgd)); /**< method to call for upgrading quadratic constraint */
180 };
181 typedef struct SCIP_QuadConsUpgrade SCIP_QUADCONSUPGRADE; /**< quadratic constraint update method */
186 int replacebinaryprodlength; /**< length of linear term which when multiplied with a binary variable is replaced by an auxiliary variable and an equivalent linear formulation */
187 int empathy4and; /**< how much empathy we have for using the AND constraint handler: 0 avoid always; 1 use sometimes; 2 use as often as possible */
188 SCIP_Bool binreforminitial; /**< whether to make constraints added due to replacing products with binary variables initial */
189 SCIP_Real binreformmaxcoef; /**< factor on 1/feastol to limit coefficients and coef range in linear constraints created by binary reformulation */
190 SCIP_Real mincutefficacysepa; /**< minimal efficacy of a cut in order to add it to relaxation during separation */
191 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) */
193 SCIP_Real cutmaxrange; /**< maximal range (maximal coef / minimal coef) of a cut in order to be added to LP */
194 SCIP_Bool linearizeheursol; /**< whether linearizations of convex quadratic constraints should be added to cutpool when some heuristics finds a new solution */
199 int maxproprounds; /**< limit on number of propagation rounds for a single constraint within one round of SCIP propagation during solve */
200 int maxproproundspresolve; /**< limit on number of propagation rounds for a single constraint within one presolving round */
201 SCIP_Real sepanlpmincont; /**< minimal required fraction of continuous variables in problem to use solution of NLP relaxation in root for separation */
202 SCIP_Bool enfocutsremovable; /**< are cuts added during enforcement removable from the LP in the same node? */
204 char interiorcomputation;/**< how the interior point should be computed: 'a'ny point per constraint,
218 SCIP_NODE* lastenfolpnode; /**< the node for which enforcement was called the last time (and some constraint was violated) */
220 SCIP_QUADCONSUPGRADE** quadconsupgrades; /**< quadratic constraint upgrade methods for specializing quadratic constraints */
236 SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), /**< method to call for upgrading quadratic constraint */
251 SCIPwarningMessage(scip, "Try to add already known upgrade message for constraint handler <%s>.\n", conshdlrname);
301 /* if right hand side is finite, then a tightening in the lower bound of coef*linvar is of interest
302 * since we also want to keep activities in consdata up-to-date, we also need to know when the corresponding bound is relaxed */
310 /* if left hand side is finite, then a tightening in the upper bound of coef*linvar is of interest
311 * since we also want to keep activities in consdata up-to-date, we also need to know when the corresponding bound is relaxed */
318 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->linvars[linvarpos], eventtype, eventhdlr, (SCIP_EVENTDATA*)eventdata, &eventdata->filterpos) );
323 * NOTE: It could happen that a constraint gets temporary deactivated and some variable bounds change. In this case
324 * we do not recognize those bound changes with the variable events and thus we have to recompute the activities.
364 /* if right hand side is finite, then a tightening in the lower bound of coef*linvar is of interest
365 * since we also want to keep activities in consdata up-to-date, we also need to know when the corresponding bound is relaxed */
373 /* if left hand side is finite, then a tightening in the upper bound of coef*linvar is of interest
374 * since we also want to keep activities in consdata up-to-date, we also need to know when the corresponding bound is relaxed */
381 SCIP_CALL( SCIPdropVarEvent(scip, consdata->linvars[linvarpos], eventtype, eventhdlr, (SCIP_EVENTDATA*)consdata->lineventdata[linvarpos], consdata->lineventdata[linvarpos]->filterpos) );
420 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->quadvarterms[quadvarpos].var, eventtype, eventhdlr, (SCIP_EVENTDATA*)eventdata, &eventdata->filterpos) );
425 * NOTE: It could happen that a constraint gets temporary deactivated and some variable bounds change. In this case
426 * we do not recognize those bound changes with the variable events and thus we have to recompute the activities.
464 SCIP_CALL( SCIPdropVarEvent(scip, consdata->quadvarterms[quadvarpos].var, eventtype, eventhdlr, (SCIP_EVENTDATA*)consdata->quadvarterms[quadvarpos].eventdata, consdata->quadvarterms[quadvarpos].eventdata->filterpos) );
498 consdata->isremovedfixings = consdata->isremovedfixings && SCIPvarIsActive(consdata->linvars[i]);
507 consdata->isremovedfixings = consdata->isremovedfixings && SCIPvarIsActive(consdata->quadvarterms[i].var);
577 SCIP_CALL( SCIPlockVarCons(scip, var, cons, !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
581 SCIP_CALL( SCIPlockVarCons(scip, var, cons, !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
608 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
612 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
664 /* if variable bounds are not strictly consistent, then the activity update methods may yield inconsistent activities
667 if( consdata->minlinactivity != SCIP_INVALID && consdata->maxlinactivity != SCIP_INVALID && /*lint !e777 */
668 (consdata->minlinactivityinf > 0 || consdata->maxlinactivityinf > 0 || consdata->minlinactivity <= consdata->maxlinactivity) )
760 assert(consdata->minlinactivityinf > 0 || consdata->maxlinactivityinf > 0 || consdata->minlinactivity <= consdata->maxlinactivity);
781 /* @todo since we check the linear activity for consistency later anyway, we may skip changing the rounding mode here */
884 /* @todo since we check the linear activity for consistency later anyway, we may skip changing the rounding mode here */
972 {
1002 consdataUpdateLinearActivityLbChange(scip, consdata, consdata->lincoefs[varidx], SCIPeventGetOldbound(event), SCIPeventGetNewbound(event));
1004 consdataUpdateLinearActivityUbChange(scip, consdata, consdata->lincoefs[varidx], SCIPeventGetOldbound(event), SCIPeventGetNewbound(event));
1020 /* if variable is binary (quite likely if an implication has been added) and occurs in a bilinear term, then mark that we should check implications */
1021 if( SCIPvarIsBinary(SCIPeventGetVar(event)) && consdata->quadvarterms[-varidx-1].nadjbilin > 0 )
1046 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->linvars, consdata->linvarssize, newsize) );
1047 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->lincoefs, consdata->linvarssize, newsize) );
1050 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->lineventdata, consdata->linvarssize, newsize) );
1076 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->quadvarterms, consdata->quadvarssize, newsize) );
1101 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &quadvarterm->adjbilin, quadvarterm->adjbilinsize, newsize) );
1126 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->bilinterms, consdata->bilintermssize, newsize) );
1237 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->quadvarterms, quadvarterms, nquadvars) );
1244 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->quadvarterms[i].adjbilin, quadvarterms[i].adjbilin, quadvarterms[i].nadjbilin) );
1272 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bilinterms, bilinterms, nbilinterms) );
1316 assert((*consdata)->lineventdata == NULL || (*consdata)->lineventdata[i] == NULL); /* variable events should have been dropped earlier */
1330 assert((*consdata)->quadvarterms[i].eventdata == NULL); /* variable events should have been dropped earlier */
1331 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->quadvarterms[i].adjbilin, (*consdata)->quadvarterms[i].adjbilinsize);
1374 SCIPsortPtrReal((void**)consdata->linvars, consdata->lincoefs, SCIPvarComp, consdata->nlinvars);
1380 SCIPsortPtrPtrReal((void**)consdata->linvars, (void**)consdata->lineventdata, consdata->lincoefs, SCIPvarComp, consdata->nlinvars);
1392 /** returns the position of variable in the linear coefficients array of a constraint, or -1 if not found */
1409 if( !SCIPsortedvecFindPtr((void**)consdata->linvars, SCIPvarComp, (void*)var, consdata->nlinvars, &pos) )
1416 /** index comparison method for quadratic variable terms: compares two indices of the quadratic variable set in the quadratic constraint */
1498 /** returns the position of variable in the quadratic variable terms array of a constraint, or -1 if not found */
1504 int* pos /**< buffer where to store position of var in quadvarterms array, or -1 if not found */
1551 /** index comparison method for bilinear terms: compares two index pairs of the bilinear term set in the quadratic constraint */
1818 consdata->linvarssorted = consdata->linvarssorted && (SCIPvarCompare(consdata->linvars[consdata->nlinvars-2], consdata->linvars[consdata->nlinvars-1]) == -1);
1819 /* always set too FALSE since the new linear variable should be checked if already existing as quad var term */
2074 (SCIPvarCompare(consdata->quadvarterms[consdata->nquadvars-2].var, consdata->quadvarterms[consdata->nquadvars-1].var) == -1);
2075 /* also set to FALSE if nquadvars == 1, since the new variable should be checked for linearity and other stuff in mergeAndClean ... */
2128 SCIPfreeBlockMemoryArrayNull(scip, &consdata->quadvarterms[pos].adjbilin, consdata->quadvarterms[pos].adjbilinsize);
2154 * Allows to replace x by coef*y+offset, thereby maintaining linear and square coefficients and bilinear terms.
2246 * thus, for now we just set the coefficient to 0.0 and clear in later when the bilinear terms are merged */
2359 if( SCIPvarCompare(consdata->quadvarterms[var1pos].var, consdata->quadvarterms[var2pos].var) < 0 )
2373 SCIPerrorMessage("tried to add bilinear term where both variables are the same, but appear at different positions in quadvarterms array\n");
2378 SCIP_CALL( consdataEnsureAdjBilinSize(scip, &consdata->quadvarterms[var1pos], consdata->quadvarterms[var1pos].nadjbilin + 1) );
2379 SCIP_CALL( consdataEnsureAdjBilinSize(scip, &consdata->quadvarterms[var2pos], consdata->quadvarterms[var2pos].nadjbilin + 1) );
2381 consdata->quadvarterms[var1pos].adjbilin[consdata->quadvarterms[var1pos].nadjbilin] = consdata->nbilinterms;
2382 consdata->quadvarterms[var2pos].adjbilin[consdata->quadvarterms[var2pos].nadjbilin] = consdata->nbilinterms;
2404 /* we have to take care of the bilinear term in mergeAndCleanBilinearTerms() if the coefficient is zero */
2523 * also replaces squares of binary variables by the binary variables, i.e., adds sqrcoef to lincoef.
2553 /* make sure quad var terms are sorted (do this in every round, since we may move variables around) */
2558 for( j = i+1; j < consdata->nquadvars && consdata->quadvarterms[j].var == quadvarterm->var; ++j )
2566 SCIP_CALL( consdataEnsureAdjBilinSize(scip, quadvarterm, quadvarterm->nadjbilin + consdata->quadvarterms[j].nadjbilin) );
2567 BMScopyMemoryArray(&quadvarterm->adjbilin[quadvarterm->nadjbilin], consdata->quadvarterms[j].adjbilin, consdata->quadvarterms[j].nadjbilin); /*lint !e866*/
2585 if( quadvarterm->sqrcoef != 0.0 && SCIPvarIsBinary(quadvarterm->var) && quadvarterm->nadjbilin == 0 )
2587 SCIPdebugMessage("replace square of binary variable by itself: <%s>^2 --> <%s>\n", SCIPvarGetName(quadvarterm->var), SCIPvarGetName(quadvarterm->var));
2621 /** merges entries with same linear variable into one entry and cleans up entries with coefficient 0.0 */
2651 /* make sure linear variables are sorted (do this in every round, since we may move variables around) */
2668 /* add newcoef to linear coefficient of quadratic variable and mark linear variable as to delete */
2693 /** merges bilinear terms with same variables into a single term, removes bilinear terms with coefficient 0.0 */
2737 for( j = i+1; j < consdata->nbilinterms && bilinterm->var1 == consdata->bilinterms[j].var1 && bilinterm->var2 == consdata->bilinterms[j].var2; ++j )
2810 SCIPdebugMessage(" linear term %g*<%s> is replaced by %g * <%s> + %g\n", consdata->lincoefs[i], SCIPvarGetName(consdata->linvars[i]),
2883 SCIPdebugMessage(" quadratic variable <%s> with status %d is replaced by %g * <%s> + %g\n", SCIPvarGetName(consdata->quadvarterms[i].var),
2889 /* if not fixed to 0.0, add to linear coefs of vars in bilinear terms, and deal with linear and square term as constant */
2908 offset = consdata->quadvarterms[i].lincoef * offset + consdata->quadvarterms[i].sqrcoef * offset * offset;
2916 SCIP_CALL( removeBilinearTermsPos(scip, cons, consdata->quadvarterms[i].nadjbilin, consdata->quadvarterms[i].adjbilin) );
2926 /* if GetProbvar gave an active variable, replace the quad var term so that it uses the new variable */
2936 /* if GetProbVar gave a multi-aggregated variable, add new quad var terms and new bilinear terms
2988 SCIP_CALL( consdataEnsureBilinSize(scip, consdata, consdata->nquadvars + (scoef != 0.0 ? (naggrs * (naggrs-1))/2 : 0) + consdata->quadvarterms[j].nadjbilin * naggrs) );
3009 /* this is not efficient, but we cannot sort the quadratic terms here, since we currently iterate over them */
3025 SCIP_CALL( addBilinearTerm(scip, cons, nquadtermsold + j, var2pos, bilinterm->coef * coef * aggrscalars[j]) );
3033 SCIP_CALL( removeBilinearTermsPos(scip, cons, consdata->quadvarterms[i].nadjbilin, consdata->quadvarterms[i].adjbilin) );
3057 * in this case, we want the linear variable to be removed, which happens in mergeAndCleanLinearVars
3090 SCIP_VAR** quadlinvars; /* variables of linear terms using variables that are in quadratic terms */
3091 SCIP_Real* quadlincoefs; /* coefficients of linear terms using variables that are in quadratic terms */
3153 * thus, it makes sense to remember the index of the previous first variable for the case a series of bilinear terms with the same first var appears */
3185 SCIP_CALL( SCIPaddLinearCoefsToNlRow(scip, consdata->nlrow, nquadlinterms, quadlinvars, quadlincoefs) );
3220 if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) && consdata->nlinvars == 0 && consdata->nquadvars == 2 &&
3221 ((SCIPvarIsBinary(consdata->quadvarterms[0].var) && consdata->quadvarterms[1].sqrcoef == 0.0) ||
3222 (SCIPvarIsBinary(consdata->quadvarterms[1].var) && consdata->quadvarterms[0].sqrcoef == 0.0)) )
3237 * if b != 0 and b+c != 0, then y = (rhs-a)/(b+c) * x + rhs/b * (1-x) = ((rhs-a)/(b+c) - rhs/b) * x + rhs/b
3240 binvaridx = (SCIPvarIsBinary(consdata->quadvarterms[0].var) && consdata->quadvarterms[1].sqrcoef == 0.0) ? 0 : 1;
3248 assert(consdata->nbilinterms <= 1); /* should actually be 1, since constraint is otherwise linear */
3253 SCIPdebugMessage("<%s> = 0 -> %g*<%s> = %g and <%s> = 1 -> %g*<%s> = %g\n", SCIPvarGetName(x), b, SCIPvarGetName(y), consdata->rhs,
3255 SCIPdebugMessage("=> attempt aggregation <%s> = %g*<%s> + %g\n", SCIPvarGetName(y), (consdata->rhs-a)/(b+c) - consdata->rhs/b,
3258 SCIP_CALL( SCIPaggregateVars(scip, x, y, (consdata->rhs-a)/(b+c) - consdata->rhs/b, -1.0, -consdata->rhs/b, &infeasible, redundant, &aggregated) );
3281 * For a product x*y, with x and y binary variables, the product is replaced by a new auxiliary variable z and the constraint z = {x and y} is added.
3334 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "prod%s_%s_%s", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]), SCIPconsGetName(cons));
3336 SCIPvarIsInitial(vars[0]) || SCIPvarIsInitial(vars[1]), SCIPvarIsRemovable(vars[0]) && SCIPvarIsRemovable(vars[1]), NULL, NULL, NULL, NULL, NULL) );
3350 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%sAND%s", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
3378 /** gets bounds of variable y if x takes a certain value; checks whether x = xval has implications on y */
3399 SCIPintervalSetBounds(resultant, MIN(SCIPvarGetLbGlobal(y), SCIPvarGetUbGlobal(y)), MAX(SCIPvarGetLbGlobal(y), SCIPvarGetUbGlobal(y))); /*lint !e666 */
3460 /** Reformulates products of binary times bounded continuous variables as system of linear inequalities (plus auxiliary variable).
3463 * an auxiliary variable z and the inequalities \f$ x^L y \leq z \leq x^U y \f$ and \f$ x - (1-y) x^U \leq z \leq x - (1-y) x^L \f$ are added.
3465 * If x is a linear term consisting of more than one variable, it is split up in groups of linear terms of length at most maxnrvar.
3466 * For each product of linear term of length at most maxnrvar with y, an auxiliary z and linear inequalities are added.
3468 * If y is a binary variable, the AND constraint \f$ z = x \wedge y \f$ may be added instead of linear constraints.
3538 SCIP_CALL( SCIPreallocBufferArray(scip, &xvars, MIN(maxnrvar, nbilinterms)+2) ); /* add 2 for later use when creating linear constraints */
3548 /* setup a list of bounded variables x_i with coefficients a_i that are multiplied with binary y: y*(sum_i a_i*x_i)
3576 if( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(bvar)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(bvar)) )
3595 if( SCIPfeastol(scip) * REALABS(act0.inf) >= conshdlrdata->binreformmaxcoef || SCIPfeastol(scip) * REALABS(act0.sup) >= conshdlrdata->binreformmaxcoef )
3598 bilincoef, SCIPvarGetName(y), SCIPvarGetName(bvar), SCIPintervalGetInf(act0), SCIPintervalGetSup(act0), SCIPvarGetName(y));
3601 if( SCIPfeastol(scip) * REALABS(act1.inf) >= conshdlrdata->binreformmaxcoef || SCIPfeastol(scip) * REALABS(act1.sup) >= conshdlrdata->binreformmaxcoef )
3604 bilincoef, SCIPvarGetName(y), SCIPvarGetName(bvar), SCIPintervalGetInf(act1), SCIPintervalGetSup(act1), SCIPvarGetName(y));
3608 SCIPfeastol(scip) * MAX(REALABS(act0.inf), REALABS(act0.sup)) / MIN(REALABS(act0.inf), REALABS(act0.sup)) >= conshdlrdata->binreformmaxcoef )
3610 SCIPdebugMessage("skip reform of %g<%s><%s> due to huge activity ratio %g for <%s> = 0.0\n", bilincoef, SCIPvarGetName(y), SCIPvarGetName(bvar),
3611 MAX(REALABS(act0.inf), REALABS(act0.sup)) / MIN(REALABS(act0.inf), REALABS(act0.sup)), SCIPvarGetName(y));
3615 SCIPfeastol(scip) * MAX(REALABS(act1.inf), REALABS(act1.sup)) / MIN(REALABS(act1.inf), REALABS(act1.sup)) >= conshdlrdata->binreformmaxcoef )
3617 SCIPdebugMessage("skip reform of %g<%s><%s> due to huge activity ratio %g for <%s> = 0.0\n", bilincoef, SCIPvarGetName(y), SCIPvarGetName(bvar),
3618 MAX(REALABS(act1.inf), REALABS(act1.sup)) / MIN(REALABS(act1.inf), REALABS(act1.sup)), SCIPvarGetName(y));
3637 integral &= (SCIPvarGetType(bvar) < SCIP_VARTYPE_CONTINUOUS) && SCIPisIntegral(scip, bilincoef); /*lint !e514 */
3669 SCIPdebugMessage("got different bounds for y = 0: [%g, %g] and y = 1: [%g, %g]\n", xbndszero.inf, xbndszero.sup, xbndsone.inf, xbndsone.sup);
3677 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "prod%s_%s_%s", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3693 /* add constraint z = x and y; need to be enforced, as it is not redundant w.r.t. existing constraints */
3695 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%sAND%s_%s", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3715 /* product of binary variable with more than one binary or with continuous variables or with binary and user
3720 * if all coefficients are integral, take a value that preserves integrality (-> gcd), so we can make the auxiliary variable impl. integer
3729 /* scaling by the only coefficient gives auxiliary variable = x * y, which thus will be implicit integral provided y is not continuous */
3747 /* if x-term is always negative for y = 1, negate scale so we get a positive auxiliary variable; maybe this is better sometimes? */
3751 SCIPdebugMessage("binary reformulation using scale %g, nxvars = %d, integral = %u\n", scale, nxvars, integral);
3762 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "prod%s_%s_%s", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3764 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "prod%s_%s_more_%s", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3765 SCIP_CALL( SCIPcreateVar(scip, &auxvar, name, MIN(0., SCIPintervalGetInf(xbndsone)), MAX(0., SCIPintervalGetSup(xbndsone)),
3798 * it seems to be advantageous to make the varbound constraints initial and the linear constraints not initial
3799 * maybe because it is more likely that a binary variable takes value 0 instead of 1, and thus the varbound constraints
3805 /* add 0 <= z - xbndsone.inf * y constraint (as varbound constraint), need to be enforced as not redundant */
3807 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s_%s_1", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3809 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s*more_%s_1", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3810 SCIP_CALL( SCIPcreateConsVarbound(scip, &auxcons, name, auxvar, y, -SCIPintervalGetInf(xbndsone), 0.0, SCIPinfinity(scip),
3823 /* add z - xbndsone.sup * y <= 0 constraint (as varbound constraint), need to be enforced as not redundant */
3825 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s_%s_2", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3827 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s*more_%s_2", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3828 SCIP_CALL( SCIPcreateConsVarbound(scip, &auxcons, name, auxvar, y, -SCIPintervalGetSup(xbndsone), -SCIPinfinity(scip), 0.0,
3840 /* add xbndszero.inf <= sum_i a_i*x_i + xbndszero.inf * y - z constraint, need to be enforced as not redundant */
3847 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s_%s_3", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3849 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s*more_%s_3", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3850 SCIP_CALL( SCIPcreateConsLinear(scip, &auxcons, name, nxvars+2, xvars, xcoef, SCIPintervalGetInf(xbndszero), SCIPinfinity(scip),
3861 /* add sum_i a_i*x_i + xbndszero.sup * y - z <= xbndszero.sup constraint, need to be enforced as not redundant */
3865 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s_%s_4", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3867 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s*more_%s_4", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons));
3868 SCIP_CALL( SCIPcreateConsLinear(scip, &auxcons, name, nxvars+2, xvars, xcoef, -SCIPinfinity(scip), SCIPintervalGetSup(xbndszero),
3901 /** tries to automatically convert a quadratic constraint (or a part of it) into a more specific and more specialized constraint */
3909 int* naddconss, /**< buffer to increase with number of additional constraints created during upgrade */
4031 integral = integral && SCIPisRelEQ(scip, lb, ub) && SCIPisIntegral(scip, lincoef * lb + quadcoef * lb * lb);
4044 if( SCIPvarGetType(consdata->bilinterms[i].var1) < SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(consdata->bilinterms[i].var2) < SCIP_VARTYPE_CONTINUOUS )
4055 SCIPdebugMessage(" binlin=%d binquad=%d intlin=%d intquad=%d impllin=%d implquad=%d contlin=%d contquad=%d integral=%u\n",
4099 /* count the first upgrade constraint as constraint upgrade and the remaining ones as added constraints */
4154 consdata->bilinterms[quadvarterm->adjbilin[i]].var2 : consdata->bilinterms[quadvarterm->adjbilin[i]].var1;
4157 SCIP_CALL( presolveDisaggregateMarkComponent(scip, consdata, othervaridx, var2component, componentnr) );
4163 /** for quadratic constraints that consists of a sum of quadratic terms, disaggregates the sum into a set of constraints by introducing auxiliary variables */
4197 /* sort quadratic variable terms here, so we can later search in it without reordering the array */
4201 * in other words, the number of components in the sparsity graph of the quadratic term matrix */
4203 SCIP_CALL( SCIPhashmapCreate(&var2component, SCIPblkmem(scip), SCIPcalcHashtableSize(consdata->nquadvars)) );
4216 * @todo we could still split the constraint into several while keeping the number of variables sharing several constraints as small as possible
4233 SCIP_CALL( SCIPcreateVar(scip, &auxvars[comp], name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
4236 SCIP_CALL( SCIPcreateConsQuadratic2(scip, &auxconss[comp], name, 0, NULL, NULL, 0, NULL, 0, NULL,
4255 SCIP_CALL( SCIPaddQuadVarQuadratic(scip, auxconss[comp], consdata->quadvarterms[i].var, consdata->quadvarterms[i].lincoef, consdata->quadvarterms[i].sqrcoef) );
4258 if( !SCIPisZero(scip, consdata->quadvarterms[i].lincoef) && ABS(consdata->quadvarterms[i].lincoef) < auxcoefs[comp] )
4260 if( !SCIPisZero(scip, consdata->quadvarterms[i].sqrcoef) && ABS(consdata->quadvarterms[i].sqrcoef) < auxcoefs[comp] )
4263 SCIPfreeBlockMemoryArray(scip, &consdata->quadvarterms[i].adjbilin, consdata->quadvarterms[i].adjbilinsize);
4272 assert(comp == (int)(size_t) SCIPhashmapGetImage(var2component, consdata->bilinterms[i].var2));
4299 SCIPdebugMessage("add %d constraints for disaggregation of quadratic constraint <%s>\n", ncomponents, SCIPconsGetName(cons));
4328 /** checks if there are bilinear terms x*y with a binary variable x and an implication x = {0,1} -> y = 0
4387 y = consdata->bilinterms[k].var1 == x ? consdata->bilinterms[k].var2 : consdata->bilinterms[k].var1;
4395 SCIPdebugMessage("remove bilinear term %g<%s><%s> from <%s> due to implication\n", consdata->bilinterms[k].coef, SCIPvarGetName(x), SCIPvarGetName(y), SCIPconsGetName(cons));
4406 * we only move the coefficient to the linear coef of y here and mark the bilinterms as not merged */
4407 SCIPdebugMessage("replace bilinear term %g<%s><%s> by %g<%s> in <%s> due to implication\n", consdata->bilinterms[k].coef, SCIPvarGetName(x), SCIPvarGetName(y), consdata->bilinterms[k].coef, SCIPvarGetName(y), SCIPconsGetName(cons));
4438 /** checks a quadratic constraint for convexity and/or concavity without checking multivariate functions */
4444 SCIP_Bool checkmultivariate /**< whether curvature will be checked later on for multivariate functions */
4463 SCIPdebugMessage("Checking curvature of constraint <%s> without multivariate functions\n", SCIPconsGetName(cons));
4487 consdata->isconvex = consdata->isconvex && !SCIPisNegative(scip, consdata->quadvarterms[v].sqrcoef);
4488 consdata->isconcave = consdata->isconcave && !SCIPisPositive(scip, consdata->quadvarterms[v].sqrcoef);
4508 SCIP_Bool checkmultivariate /**< whether curvature should also be checked for multivariate functions */
4542 SCIPdebugMessage("Checking curvature of constraint <%s> with multivariate functions\n", SCIPconsGetName(cons));
4551 4 * consdata->quadvarterms[0].sqrcoef * consdata->quadvarterms[1].sqrcoef >= consdata->bilinterms[0].coef * consdata->bilinterms[0].coef;
4555 4 * consdata->quadvarterms[0].sqrcoef * consdata->quadvarterms[1].sqrcoef >= consdata->bilinterms[0].coef * consdata->bilinterms[0].coef;
4565 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "cons_quadratic - n is too large to check the curvature\n");
4623 SCIPwarningMessage(scip, "Failed to compute eigenvalues of quadratic coefficient matrix of constraint %s. Assuming matrix is indefinite.\n", SCIPconsGetName(cons));
4629 /* deconvexification reformulates a stricly convex quadratic function in binaries such that it becomes not-strictly convex
4631 * the result is still a convex form "but less so" (ref. papers by Guignard et.al.), but with hopefully tighter value for the continuous relaxation
4635 printf("cons <%s>[%g,%g] spectrum = [%g,%g]\n", SCIPconsGetName(cons), consdata->lhs, consdata->rhs, alleigval[0], alleigval[n-1]);
4648 printf("deconvexify cons <%s> by shifting hessian by %g\n", SCIPconsGetName(cons), alleigval[0]);
4658 printf("deconcavify cons <%s> by shifting hessian by %g\n", SCIPconsGetName(cons), alleigval[n-1]);
4674 consdata->iscurvchecked = TRUE; /* set to TRUE since it does not help to repeat this procedure again and again (that will not bring Ipopt in) */
4683 /** check whether indefinite constraint function is factorable and store corresponding coefficients */
4719 * compute an eigenvalue factorization of A and check if there are one positive and one negative eigenvalue
4720 * if so, then let sigma1^2 and -sigma2^2 be these eigenvalues and v1 and v2 be the first two rows of the inverse eigenvector matrix
4723 * we then store sigma1 v1^T - sigma2 v2^T as left factor coef, and sigma1 v1^T + sigma2 v2^T as right factor coef
4726 /* if we already know that there are only positive or only negative eigenvalues, then don't try */
4771 SCIPdebugMessage("Failed to compute eigenvalues and eigenvectors of augmented quadratic form matrix for constraint <%s>.\n", SCIPconsGetName(cons));
4797 SCIPdebugMessage("Augmented quadratic form of constraint <%s> is not factorable.\n", SCIPconsGetName(cons));
4824 SCIPdebugMessage("constraint <%s> has factorable quadratic form: (%g", SCIPconsGetName(cons), consdata->factorleft[n-1]);
4828 SCIPdebugPrintf(" %+g<%s>", consdata->factorleft[i], SCIPvarGetName(consdata->quadvarterms[i].var));
4834 SCIPdebugPrintf(" %+g<%s>", consdata->factorright[i], SCIPvarGetName(consdata->quadvarterms[i].var));
4852 if( !SCIPisRelEQ(scip, consdata->factorleft[idx1] * consdata->factorright[idx2] + consdata->factorleft[idx2] * consdata->factorright[idx1], bilinterm->coef) )
4862 if( !SCIPisRelEQ(scip, consdata->factorleft[i] * consdata->factorright[i], consdata->quadvarterms[i].sqrcoef) )
4868 if( !SCIPisRelEQ(scip, consdata->factorleft[n-1] * consdata->factorright[i] + consdata->factorleft[i] * consdata->factorright[n-1], consdata->quadvarterms[i].lincoef) )
4971 /* @todo Take better care of variables at +/- infinity: e.g., run instance waste in debug mode with a short timelimit (30s). */
4987 /* project onto local box, in case the LP solution is slightly outside the bounds (which is not our job to enforce) */
4990 /* 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
5014 /* project onto local box, in case the LP solution is slightly outside the bounds (which is not our job to enforce) */
5017 /* 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
5024 consdata->activity += (consdata->quadvarterms[j].lincoef + consdata->quadvarterms[j].sqrcoef * varval) * varval;
5034 /* project onto local box, in case the LP solution is slightly outside the bounds (which is not our job to enforce) */
5037 #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 */
5043 #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 */
5112 SCIP_CONS** maxviolcon /**< buffer to store constraint with largest violation, or NULL if solution is feasible */
5149 /** tries to compute cut for multleft * <coefleft, x'> * multright <= rhs / (multright * <coefright, x'>) where x'=(x,1) */
5184 * 1 / multright*<coefright, x'> <= 1/minact + 1/maxact - 1/(minact * maxact) multright*<coefright, x'>
5188 * multright/rightminactivity + multright/rightmaxactivity - multright/(rightminactivity * rightmaxactivity) *<coefright, x'>
5191 * rhs / (multright * <coefright, x'>) <= rhs * multright * (1/rightminactivity + 1/rightmaxactivity - 1/(rightminactivity * rightmaxactivity) * <coefright, x'>)
5205 constant += rhs * multright * coefright[consdata->nquadvars] / (rightminactivity * rightmaxactivity);
5213 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_factorablesecant_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip));
5221 * <= rhs / (multright * <coefright, ref'>) - rhs / (multright * <coefright, ref'>)^2 * (multright * <coefright, x'> - multright * <coefright, ref'>)
5222 * = 2*rhs / (multright * <coefright, ref'>) - rhs / (multright * <coefright, ref'>)^2 * (multright * <coefright, x'>)
5232 /* should not happen, since we checked activity of <coefright,x> before, and assume ref within bounds */
5245 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_factorablelinearization_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip));
5255 /** tries to generate a cut if constraint quadratic function is factorable and there are no linear variables
5256 * (ax+b)(cx+d) <= rhs and cx+d >= 0 -> (ax+b) <= rhs / (cx+d), where the right hand side is concave and can be linearized
5349 rightminactivity += consdata->factorright[i] * SCIPvarGetLbLocal(consdata->quadvarterms[i].var);
5356 rightminactivity += consdata->factorright[i] * SCIPvarGetUbLocal(consdata->quadvarterms[i].var);
5366 rightmaxactivity += consdata->factorright[i] * SCIPvarGetUbLocal(consdata->quadvarterms[i].var);
5373 rightmaxactivity += consdata->factorright[i] * SCIPvarGetLbLocal(consdata->quadvarterms[i].var);
5399 if( !SCIPisFeasPositive(scip, rightminactivity) && !SCIPisFeasNegative(scip, rightmaxactivity) )
5407 /* write violated constraint as multleft * factorleft * multright * (multright * factorright) <= rhs
5416 generateCutFactorableDo(scip, cons, ref, multleft, consdata->factorleft, multright, consdata->factorright, rightminactivity, rightmaxactivity, rhs, cutcoef, cutrhs, islocal, success, name);
5418 else if( !SCIPisFeasPositive(scip, rightminactivity) && !SCIPisFeasNegative(scip, rightmaxactivity) )
5425 /* write violated constraint as multleft * factorright * multright * (multright * factorleft) <= rhs
5434 generateCutFactorableDo(scip, cons, ref, multleft, consdata->factorright, multright, consdata->factorleft, leftminactivity, leftmaxactivity, rhs, cutcoef, cutrhs, islocal, success, name);
5437 (!SCIPisInfinity(scip, -rightminactivity) && !SCIPisInfinity(scip, rightmaxactivity) && rightmaxactivity - rightminactivity < leftmaxactivity - leftminactivity) )
5439 /* both factors are bounded away from 0, but the right one has a smaller activity range, so divide by that one */
5441 /* write violated constraint as multleft * factorleft * multright * (multright * factorright) <= rhs
5450 generateCutFactorableDo(scip, cons, ref, multleft, consdata->factorleft, multright, consdata->factorright, rightminactivity, rightmaxactivity, rhs, cutcoef, cutrhs, islocal, success, name);
5454 /* both factors are bounded away from 0, but the left one has a smaller activity range, so divide by that one */
5456 /* write violated constraint as multleft * factorright * multright * (multright * factorleft) <= rhs
5465 generateCutFactorableDo(scip, cons, ref, multleft, consdata->factorright, multright, consdata->factorleft, leftminactivity, leftmaxactivity, rhs, cutcoef, cutrhs, islocal, success, name);
5471 /* finds intersections of a parametric line (x,y) = (x0,y0) + t [(x1,y1) - (x0,y0)] on curves x*y = wl and x*y = wu;
5591 * such that intersecting it with one of them (the first if whichuse is FALSE, the second otherwise)
5651 * The code is an adaptation of the methods in exprMul-upperHull.cpp in Couenne/stable/0.4 rev773,
5728 /* both variables have mixed sign (xl < 0 && xu > 0 && yl < 0 && yu > 0) and both xl*yl and xu*yu are feasible
5748 /* both variables have mixed sign (xl < 0 && xu > 0 && yl < 0 && yu > 0) and both xl*yu and xu*yl are feasible
5793 /* project refpoint into box not only for numerical reasons, but also due to preliminary bound tightening above */
5817 if( generateCutLTIfindIntersection(scip, 0.0, 0.0, x0, y0_, wl, wu, &xlow, &ylow, &xupp, &yupp) )
5824 /* Case 1: If both are outside of bounding box, either NW or SE, then McCormick is sufficient, so return */
5828 /* There will be at least one cut. Define coefficients and rhs ---will have to change them back if (flipX || flipY) */
5858 if( generateCutLTIfindIntersection(scip, xupp, yupp, x0, y0_, wl, SCIP_INVALID, &xlow, &ylow, NULL, NULL) )
5892 if( generateCutLTIfindIntersection(scip, xlow, ylow, x0, y0_, SCIP_INVALID, wu, NULL, NULL, &xupp, &yupp) )
5943 /* Nothing to find. Just separate two inequalities at the same point, just using different support */
5961 /* find the intersection on the lower (upper) curve on the line through xLP and the upper (lower) point
5964 if( generateCutLTIfindIntersection(scip, xlow, ylow, x0, y0_, SCIP_INVALID, wu, NULL, NULL, &xupp2, &yupp2) ||
5967 if( generateCutLTIfindIntersection(scip, xupp, yupp, x0, y0_, wl, SCIP_INVALID, &xlow2, &ylow2, NULL, NULL) ||
6008 /** tries to generate a cut if constraint quadratic function is factorable and there are linear variables
6011 * Belotti, Miller, Namazifar, Lifted inequalities for bounded products of variables, SIAG/OPT Views-and-News 22:1, 2011
6020 SCIP_Real** cutcoeflin, /**< buffer to store pointer to array with coefficients for linear variables */
6054 /* currently only separate LP solution or solutions given as SCIP_SOL, i.e., no cutgeneration during initlp */
6179 rightminactivity += consdata->factorright[i] * SCIPvarGetLbLocal(consdata->quadvarterms[i].var);
6186 rightminactivity += consdata->factorright[i] * SCIPvarGetUbLocal(consdata->quadvarterms[i].var);
6196 rightmaxactivity += consdata->factorright[i] * SCIPvarGetUbLocal(consdata->quadvarterms[i].var);
6203 rightmaxactivity += consdata->factorright[i] * SCIPvarGetLbLocal(consdata->quadvarterms[i].var);
6209 /* if activities exceed "opposite" infinity, huge bounds seem to be involved, for which the below method is not prepared */
6214 /* if any of the factors is essentially fixed, give up and do usual method (numerically less sensitive, I hope) */
6215 if( SCIPisRelEQ(scip, leftminactivity, leftmaxactivity) || SCIPisRelEQ(scip, rightminactivity, rightmaxactivity) )
6233 leftminactivity, leftmaxactivity, rightminactivity, rightmaxactivity, rhsminactivity, rhsmaxactivity,
6238 if( coefleft * leftrefactivity + coefright * rightrefactivity + coefrhs * rhsrefactivity >= *cutlhs )
6246 * coefleft * leftfactor + coefright * rightfactor + coefrhs * w >= cutlhs, where conslhs - lincoefs <= w <= consrhs - lincoefs
6272 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lti_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip));
6284 SCIP_Bool isint, /**< whether corresponding variable is a discrete variable, and thus linearization could be moved */
6287 SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
6324 /* sqrcoef * x^2 -> secant between f=floor(refpoint) and f+1 = sqrcoef * (f^2 + ((f+1)^2 - f^2) * (x-f)) = sqrcoef * (-f*(f+1) + (2*f+1)*x) */
6354 SCIP_Bool* success /**< buffer to set to FALSE if secant has failed due to large numbers or unboundedness */
6380 /* sqrcoef * x^2 -> sqrcoef * (lb * lb + (ub*ub - lb*lb)/(ub-lb) * (x-lb)) = sqrcoef * (lb*lb + (ub+lb)*(x-lb)) = sqrcoef * ((lb+ub)*x - lb*ub) */
6403 SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
6423 /* bilincoef * x * y -> bilincoef * (refpointx * refpointy + refpointy * (x - refpointx) + refpointx * (y - refpointy))
6429 if( SCIPisInfinity(scip, REALABS(bilincoef * refpointx)) || SCIPisInfinity(scip, REALABS(bilincoef * refpointy)) || SCIPisInfinity(scip, REALABS(constant)) )
6450 SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
6454 SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
6510 (SCIPisInfinity(scip, ubx) || SCIPisInfinity(scip, uby) || (uby - refpointy) * (ubx - refpointx) >= (refpointy - lby) * (refpointx - lbx)) )
6514 /* x*y = lbx * y + (x-lbx) * y >= lbx * y + (x-lbx) * lby >= lbx * y + min{(ubx-lbx) * lby, 0 * lby} */
6521 /* x*y = lby * x + (y-lby) * x >= lby * x + (y-lby) * lbx >= lby * x + min{(uby-lby) * lbx, 0 * lbx} */
6537 /* x*y = ubx * y + (x-ubx) * y >= ubx * y + (x-ubx) * uby >= ubx * y + min{(lbx-ubx) * uby, 0 * uby} */
6544 /* x*y = uby * x + (y-uby) * x >= uby * x + (y-uby) * ubx >= uby * x + min{(lby-uby) * ubx, 0 * ubx} */
6566 (SCIPisInfinity(scip, -lbx) || SCIPisInfinity(scip, uby) || (ubx - lbx) * (refpointy - lby) <= (uby - lby) * (refpointx - lbx)) )
6570 /* x*y = ubx * y + (x-ubx) * y <= ubx * y + (x-ubx) * lby <= ubx * y + max{(lbx-ubx) * lby, 0 * lby} */
6577 /* x*y = lby * x + (y-lby) * x <= lby * x + (y-lby) * ubx <= lby * x + max{(uby-lby) * ubx, 0 * ubx} */
6593 /* x*y = lbx * y + (x-lbx) * y <= lbx * y + (x-lbx) * uby <= lbx * y + max{(ubx-lbx) * uby, 0 * uby} */
6600 /* x*y = uby * x + (y-uby) * x <= uby * x + (y-uby) * lbx <= uby * x + max{(lby-uby) * lbx, 0 * lbx} */
6619 if( SCIPisInfinity(scip, REALABS(coefx)) || SCIPisInfinity(scip, REALABS(coefy)) || SCIPisInfinity(scip, REALABS(constant)) )
6632 /* SCIPdebugMessage("%.20g * x[%.20g,%.20g] * y[%.20g,%.20g] %c= %.20g * x %+.20g * y %+.20g\n", bilincoef, lbx, ubx, lby, uby,
6688 consdata->quadvarterms[j].nadjbilin == 0 && SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS, &coef[j], &constant, success);
6704 SCIPaddBilinLinearization(scip, bilinterm->coef, ref[j], ref[var2pos], &coef[j], &coef[var2pos], &constant, success);
6710 SCIPdebugMessage("no success in linearization of <%s> in reference point\n", SCIPconsGetName(cons));
6725 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_side%d_linearization_%d", SCIPconsGetName(cons), violside, SCIPgetNLPs(scip));
6782 if( (violside == SCIP_SIDETYPE_LEFT && sqrcoef <= 0.0) || (violside == SCIP_SIDETYPE_RIGHT && sqrcoef > 0.0) )
6785 SCIPaddSquareLinearization(scip, sqrcoef, ref[j], SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS, &coef[j],
6791 SCIPaddSquareSecant(scip, sqrcoef, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), ref[j], &coef[j],
6833 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_side%d_estimation_%d", SCIPconsGetName(cons), violside, SCIPgetNLPs(scip));
6838 /** generates a cut based on linearization (if convex) or McCormick (if nonconvex) in a given reference point */
6848 SCIP_Real* efficacy, /**< buffer to store efficacy of row in reference solution, or NULL if not of interest */
6849 SCIP_Bool checkcurvmultivar, /**< are we allowed to check the curvature of a multivariate quadratic function, if not done yet */
6850 SCIP_Real minefficacy /**< minimal required efficacy (violation scaled by maximal absolute coefficient) */
6902 SCIP_CALL( generateCutFactorable(scip, cons, violside, ref, coef, &lhs, &rhs, &islocal, &success, cutname) );
6908 /* generateCutLTI needs reference values also for the linear variables, which we only have if sol is given or LP has been solved */
6909 SCIP_CALL( generateCutLTI(scip, cons, violside, ref, sol, &lincoefs, coef, &lhs, &rhs, &islocal, &success, cutname) );
6911 /* in case of LTI cuts, we have to recompute the min and max of lincoefs, since they may have been modified */
6927 if( (violside == SCIP_SIDETYPE_LEFT && consdata->isconcave) || (violside == SCIP_SIDETYPE_RIGHT && consdata->isconvex) )
6929 SCIP_CALL( generateCutConvex(scip, cons, violside, ref, coef, &lhs, &rhs, &islocal, &success, cutname) );
6933 SCIP_CALL( generateCutNonConvex(scip, cons, violside, ref, coef, &lhs, &rhs, &islocal, &success, cutname) );
6956 * it is required if we need to check or return cut efficacy, for some debug output below, and some assert
6957 * round almost integral coefficients in integers, since this will happen when adding coefs to row (see comments below)
6965 * HOWEVER, they become column variables when they are added to a row (via SCIPaddVarsToRow below).
6967 * So when calculating the row activity, we treat loose variable as if they were already column variables.
6970 refactivitylinpart += (SCIPisIntegral(scip, lincoefs[j]) ? SCIPround(scip, lincoefs[j]) : lincoefs[j]) * SCIPgetSolVal(scip, sol, consdata->linvars[j]);
6987 * thus, we anticipate by rounding coef here, but also modify constant so that cut is still valid (if possible)
7010 SCIPdebugMessage("var <%s> [%g,%g] has almost integral coef %.20g, round coefficient to %g and add constant %g\n",
7011 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), coef[j], roundcoef, (coef[j]-roundcoef) * xbnd);
7020 /* As above: When calculating the row activity, we treat loose variable as if they were already column variables. */
7044 SCIPdebugMessage("skip cut for constraint <%s> since all coefficients are zero and it's always satisfied\n", SCIPconsGetName(cons));
7057 SCIPdebugMessage("cut coefficients for constraint <%s> have very large range: mincoef = %g maxcoef = %g\n", SCIPconsGetName(cons), mincoef, maxcoef);
7062 * since we use local bounds, we need to make the row local if they are different from their global counterpart
7064 if( ((coef[mincoefidx] > 0.0 && !SCIPisInfinity(scip, rhs)) || (coef[mincoefidx] < 0.0 && !SCIPisInfinity(scip, -lhs))) &&
7067 SCIPdebugMessage("eliminate coefficient %g for <%s> [%g, %g]\n", coef[mincoefidx], SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
7073 else if( ((coef[mincoefidx] < 0.0 && !SCIPisInfinity(scip, rhs)) || (coef[mincoefidx] > 0.0 && !SCIPisInfinity(scip, -lhs))) &&
7076 SCIPdebugMessage("eliminate coefficient %g for <%s> [%g, %g]\n", coef[mincoefidx], SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
7105 SCIPdebugMessage("skip cut for constraint <%s> because both sides are not finite: lhs = %g, rhs = %g\n", SCIPconsGetName(cons), lhs, rhs);
7119 /* in difference to SCIPgetCutEfficacy, we scale by norm only if the norm is > 1.0 this avoid finding cuts
7120 * efficient which are only very slightly violated CPLEX does not seem to scale row coefficients up too also we
7121 * use infinity norm, since that seem to be the usual scaling strategy in LP solvers (equilibrium scaling) */
7148 if( success && !SCIPisInfinity(scip, -minefficacy) && rowefficacy < minefficacy ) /*lint !e644*/
7150 SCIPdebugMessage("skip cut for constraint <%s> because efficacy %g too low (< %g)\n", SCIPconsGetName(cons), rowefficacy, minefficacy);
7157 SCIP_CALL( SCIPcreateEmptyRowCons(scip, row, SCIPconsGetHdlr(cons), cutname, lhs, rhs, islocal && (SCIPgetDepth(scip) > 0), FALSE, TRUE) );
7166 SCIPdebugMessage("found cut <%s>, lhs=%g, rhs=%g, mincoef=%g, maxcoef=%g, range=%g, nnz=%d, violation=%g, efficacy=%g\n",
7176 * computing efficacy w.r.t. the LP solution makes only sense if the LP was solved to optimality (see bug 612)
7178 * disabled these asserts as they can fail due to numerical reasons (cancelation when substracting big numbers),
7179 * as the order in which we add up the activity for the single terms can be different than the one that lp.c uses
7183 assert((conshdlrdata->scaling != 'g') || (SCIPisFeasPositive(scip, rowefficacy) == SCIPisFeasPositive(scip, -SCIPgetRowSolFeasibility(scip, *row, sol)/MAX(1.0,SCIPgetRowMaxCoef(scip, *row)))));
7184 assert((conshdlrdata->scaling != 's') || (SCIPisFeasPositive(scip, rowefficacy) == SCIPisFeasPositive(scip, -SCIPgetRowSolFeasibility(scip, *row, sol)/MAX(1.0,MIN(REALABS(lhs),REALABS(rhs))))));
7185 assert((conshdlrdata->scaling != 'o') || (SCIPisFeasPositive(scip, rowefficacy) == SCIPisFeasPositive(scip, -SCIPgetRowSolFeasibility(scip, *row, sol))));
7192 /* if coefficients for linear variables are different than those in constraint, then free array */
7262 /* in the convex case, we try to find an interior point of x^T A x + b^T x <= rhs - maximum activity linear part
7263 * in the concave case: lhs - minimum activity linear part <= x^T A x + b^T x; we compute activities ourselves,
7264 * since consdata->max(min)linactivity are only computed when lhs (rhs) is finite and this not always holds
7289 SCIPdebugMessage("maximum activity is infinity: there is no interior point for fun <= rhs - maxlinactivity!\n");
7322 SCIPdebugMessage("minimum activity is -infinity: there is no interior point for fun >= lhs - minlinactivity!\n");
7363 /* TODO: maybe one should set some generous iteration limit and/or a timelimit (remaining scip solve time)? */
7395 assert(nlrowquadvars[nlrowquadelems[i].idx1] == consdata->quadvarterms[nlrowquadelems[i].idx1].var);
7396 assert(nlrowquadvars[nlrowquadelems[i].idx2] == consdata->quadvarterms[nlrowquadelems[i].idx2].var);
7409 SCIP_CALL( SCIPnlpiAddConstraints(nlpi, prob, 1, NULL, &nlpiside, &nquadvars, &lininds, &lincoefs,
7414 SCIP_CALL( SCIPnlpiAddConstraints(nlpi, prob, 1, &nlpiside, NULL, &nquadvars, &lininds, &lincoefs,
7469 SCIPdebugMessage("cons <%s>: found an interior point. solution status: %d, termination status: %d\n",
7476 /* TODO: we could still use the point, and let evaluateGauge decide whether the point is interior or not */
7477 SCIPdebugMessage("cons <%s>: failed to find an interior point. solution status: %d, termination status: %d\n",
7485 SCIPerrorMessage("cons <%s>: undefined behaviour of NLP Solver. solution status: %d, termination status: %d\n",
7492 * note: nlpiGetSolution (at least for IPOPT) makes interiorpoint point to the internal solution stored in the
7493 * nlpi problem data structure; we need to copy it here because it will be destroyed once the problem is free'd
7516 printf(" - is convex. rhs: %g maximum activity of linear variables: %g\n", consdata->rhs, consdata->rhs - nlpiside);
7521 printf(" - is concave. lhs: %g minimum activity of linear variables: %g\n", consdata->lhs, consdata->lhs - nlpiside);
7541 printf("%s = %g\n", SCIPvarGetName(consdata->quadvarterms[i].var), consdata->interiorpoint[i]);
7572 /** compute gauge function of the set \f$S - s_0\f$ where \f$ S = \{ x : f(x) \le c \}\f$ and \f$ s_0 \in \mathring S\f$.
7574 * Here, \f$ f(x) \f$ is a purely quadratic (i.e, all \f$x\f$ variables appear in a bilinear or quadratic term).
7607 assert(consdata->sepabilinvar2pos != NULL || consdata->nbilinterms == 0); /* this should have been computed in INITSOL */
7631 * we are going to evaluate the function at interiorpoint; so, we need to compute interiorpoint^T A interiorpoint;
7632 * therefore, we need a mechanism that for a given variable, it returns its interior point value
7638 /* compute value of quadratic part at interior point, build map and compute gaugeconst (c_gauge) */
7662 /* the index of the variable associated with var2 in bilinterm should be given by sepabilinvar2pos */
7663 assert(consdata->quadvarterms[consdata->sepabilinvar2pos[bilintermidx]].var == bilinterm->var2);
7691 /* the index of the variable associated with var2 in bilinterm should be given by sepabilinvar2pos */
7692 assert(consdata->quadvarterms[consdata->sepabilinvar2pos[bilintermidx]].var == bilinterm->var2);
7710 printf("b_gauge[%s] = %g\n", SCIPvarGetName(consdata->quadvarterms[j].var), consdata->gaugecoefs[j]);
7721 /** evaluates gauge function of the set \f$S - s_0\f$ where \f$ S = \{ x : f(x) \le c \}\f$ and \f$ s_0 \in \mathring S\f$.
7772 /* it can happen that the interior point is not really interior, since we are not so strict at the moment of
7773 * computing the interior point, which makes sense in the case that the constraint is quadratic <= linear expr,
7774 * since we compute a point in quadratic <= min linear expr and it might be that this set consists of a single
7775 * point which will not be interior. furthermore, if this set is empty, we could just take any point and it could
7776 * happen that for some value of linear expr, the point is actually interior, but for many it could not be.
7777 * also, if min linear expr = -infinity, we might have computed an interior point using some finite value.
7784 printf("rhs: %g level: %15.20g interiorpointval: %15.20g\n", consdata->rhs, side, consdata->interiorpointval);
7797 printf("rhs: %g level: %15.20g interiorpointval: %15.20g\n", consdata->rhs, side, consdata->interiorpointval);
7818 printf("lhs: %g level: %15.20g interiorpointval: %15.20g\n", consdata->lhs, side, consdata->interiorpointval);
7831 printf("lhs: %g level: %15.20g interiorpointval: %15.20g\n", consdata->lhs, side, consdata->interiorpointval);
7862 cterm += consdata->bilinterms[i].coef * SCIPgetSolVal(scip, refsol, var1) * SCIPgetSolVal(scip, refsol, var2);
7906 SCIP_SOL* refsol, /**< reference point where to compute gauge, or NULL if LP solution should be used */
7959 printf("refsol is in the closure of the region (gaugeval <= 1), don't modify reference point\n");
7977 /* set reference to (refsol - interior point)/gaugeval + interior point and project into bounds
8006 /** generates a cut based on linearization (if convex) or McCormick (if nonconvex) in a solution */
8016 SCIP_Real* efficacy, /**< buffer to store efficacy of row in reference solution, or NULL if not of interest */
8017 SCIP_Bool checkcurvmultivar, /**< are we allowed to check the curvature of a multivariate quadratic function, if not done yet */
8018 SCIP_Real minefficacy /**< minimal required efficacy (violation scaled by maximal absolute coefficient) */
8056 SCIP_CALL( generateCut(scip, conshdlr, cons, ref, sol, violside, row, efficacy, checkcurvmultivar, minefficacy) );
8059 if( *row == NULL || (efficacy != NULL && !SCIPisGT(scip, *efficacy, minefficacy)) || !SCIPisCutApplicable(scip, *row) ) /*lint !e644 */
8081 SCIP_CALL( generateCut(scip, conshdlr, cons, ref, sol, violside, row, efficacy, checkcurvmultivar, minefficacy) );
8092 * For nonconvex functions, we just call generateCutSol with the unbounded solution as reference point.
8101 SCIP_Real* rowrayprod, /**< buffer to store product of ray with row coefficients, or NULL if not of interest */
8102 SCIP_Bool checkcurvmultivar /**< are we allowed to check the curvature of a multivariate quadratic function, if not done yet */
8138 SCIP_CALL( generateCutSol(scip, conshdlr, cons, NULL, NULL, violside, row, NULL, FALSE, -SCIPinfinity(scip)) );
8157 /* we seek for a linearization of the quadratic function such that it intersects with the unbounded ray
8158 * that is, we need a reference point ref such that for the gradient g of xAx+bx in ref, we have
8161 * initially, for finite rhs, we set ref_i = 1.0 if (A*ray)_i > 0.0 and ref_i = -1.0 if (A*ray)_i < 0.0 (for finite lhs analog)
8162 * <ref, 2*A*ray> + <b,ray> is sufficiently larger 0.0, we call generateCut for this point, otherwise, we scale up ref
8178 matrixrayprod += bilinterm->coef * SCIPgetPrimalRayVal(scip, bilinterm->var1 == var ? bilinterm->var2 : bilinterm->var1);
8191 assert((violside == SCIP_SIDETYPE_RIGHT && quadrayprod >= 0.0) || (violside == SCIP_SIDETYPE_LEFT && quadrayprod <= 0.0));
8204 SCIPdebugMessage("initially have <b,ray> = %g and <ref, 2*A*ref> = %g\n", linrayprod, quadrayprod);
8206 /* we scale the refpoint up, such that <ref, 2*A*ray> >= -2*<b, ray> (rhs finite) or <ref, 2*A*ray> <= -2*<b, ray> (lhs finite), if <b,ray> is not zero
8209 if( (!SCIPisZero(scip, linrayprod) && violside == SCIP_SIDETYPE_RIGHT && quadrayprod < -2*linrayprod) ||
8210 ( !SCIPisZero(scip, linrayprod) && violside == SCIP_SIDETYPE_LEFT && quadrayprod > -2*linrayprod) ||
8230 SCIP_CALL( generateCut(scip, conshdlr, cons, ref, NULL, violside, row, NULL, FALSE, -SCIPinfinity(scip)) );
8252 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 */
8283 if( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
8289 violside = SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT;
8292 actminefficacy = inenforcement && ((violside == SCIP_SIDETYPE_RIGHT && consdata->isconvex ) || (violside == SCIP_SIDETYPE_LEFT && consdata->isconcave))
8299 /* if the LP is unbounded, then we need a cut that cuts into the direction of a hopefully existing primal ray
8300 * that is, assume a ray r is given such that p + t*r is feasible for the LP for all t >= t_0 and some p
8301 * given a cut lhs <= <c,x> <= rhs, we check whether it imposes an upper bound on t and thus bounds the ray
8302 * this is given if rhs < infinity and <c,r> > 0, since we then enforce <c,p+t*r> = <c,p> + t<c,r> <= rhs, i.e., t <= (rhs - <c,p>)/<c,r>
8309 SCIP_CALL( generateCutUnboundedLP(scip, conshdlr, conss[c], violside, &row, &rayprod, conshdlrdata->checkcurvature) );
8326 /* in difference to SCIPgetCutEfficacy, we scale by norm only if the norm is > 1.0 this avoid finding
8328 * coefficients up too also we use infinity norm, since that seem to be the usual scaling strategy
8353 /* @todo If convex, can we easily move the refpoint closer to the feasible region to get a stronger cut?
8356 SCIP_CALL( generateCutSol(scip, conshdlr, conss[c], sol, NULL, violside, &row, &efficacy, conshdlrdata->checkcurvature, actminefficacy) );
8357 /* @todo If generation failed not because of low efficacy, then probably because of numerical issues;
8358 * if the constraint is convex and we are desperate to get a cut, then we may try again with a better chosen reference point
8365 if( SCIPisGT(scip, efficacy, actminefficacy) && SCIPisCutApplicable(scip, row) ) /*lint !e644 */
8373 SCIPdebugMessage("cut for constraint <%s> is infeasible -> cutoff.\n", SCIPconsGetName(conss[c]));
8398 * others are only checked and enforced if we are still feasible or have not found a separating cut yet
8407 /** adds linearizations cuts for convex constraints w.r.t. a given reference point to cutpool and sepastore
8409 * - 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.
8410 * - If separatedlpsol is not NULL, but cut does not separate the LP solution, then it is added to the cutpool only.
8420 SCIP_Bool* separatedlpsol, /**< buffer to store whether a cut that separates the current LP solution was found and added to LP,
8422 SCIP_Real minefficacy /**< minimal efficacy of a cut when checking for separation of LP solution */
8455 SCIP_CALL( generateCutSol(scip, conshdlr, conss[c], NULL, ref, SCIP_SIDETYPE_RIGHT, &row, NULL,
8484 /* in difference to SCIPgetCutEfficacy, we scale by norm only if the norm is > 1.0 this avoid finding cuts
8485 * efficient which are only very slightly violated CPLEX does not seem to scale row coefficients up too
8486 * also we use infinity norm, since that seem to be the usual scaling strategy in LP solvers (equilibrium
8516 SCIPdebugMessage("added linearization cut <%s> to LP, efficacy = %g\n", SCIProwGetName(row), efficacy);
8535 {
8562 /* we are only interested in solution coming from some heuristic other than trysol, but not from the tree
8563 * the reason for ignoring trysol solutions is that they may come from an NLP solve in sepalp, where we already added linearizations,
8572 SCIPdebugMessage("caught new sol event %x from heur <%s>; have %d conss\n", SCIPeventGetType(event), SCIPheurGetName(SCIPsolGetHeur(sol)), nconss);
8581 * That is, computes for every nonconvex term the gap between the terms value in the LP solution and the value of the underestimator
8582 * as it would be (and maybe has been) constructed by the separation routines of this constraint handler. Then it registers all
8583 * variables occurring in each term with the computed gap. If variables appear in more than one term, they are registered several times.
8632 SCIPdebugMessage("cons %s violation: %g %g convex: %u %u\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol, consdata->isconvex, consdata->isconcave);
8638 if( (SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) && consdata->quadvarterms[j].sqrcoef < 0) ||
8639 ( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && consdata->quadvarterms[j].sqrcoef > 0) )
8645 SCIPdebugMessage("ignore fixed variable <%s>[%g, %g], diff %g\n", SCIPvarGetName(x), xlb, xub, xub-xlb);
8668 /* if any of the variables if fixed, then it actually behaves like a linear term, so we don't need to branch on it */
8691 /* if both variables are at one of its bounds, then no need to branch, since McCormick is exact there */
8699 coef_ = SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) ? -consdata->bilinterms[j].coef : consdata->bilinterms[j].coef;
8715 assert(!SCIPisNegative(scip, gap / MAX3(MAX(REALABS(xlb), REALABS(xub)), MAX(REALABS(ylb), REALABS(yub)), 1.0))); /*lint !e666*/
8720 /* if one of the variables is binary or integral with domain width 1, then branching on this makes the term linear, so prefer this */
8750 /* if both variables are integral, prefer the one with the smaller domain, so variable gets fixed soon
8751 * does not seem to work well on tln instances, so disable for now and may look at it later again
8772 * this is, because after branching both variables will be one the bounds, and McCormick will be exact then */
8793 * That is, registers all variables appearing in nonconvex terms^1 with a score that is the violation of the constraint.
8794 * This is the same rule as is applied in cons_nonlinear and other nonlinear constraint handlers.
8796 * 1) We mean all quadratic variables that appear either in a nonconvex square term or in a bilinear term, if the constraint
8797 * itself is nonconvex. (and this under the assumption that the rhs is violated; for violated lhs, swap terms)
8835 SCIPdebugMessage("cons %s violation: %g %g convex: %u %u\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol, consdata->isconvex, consdata->isconcave);
8852 /* if variable is at bounds and only in a nonconvex square term, then no need to branch, since secant is exact there */
8859 SCIPdebugMessage("ignore fixed variable <%s>[%g, %g], diff %g\n", SCIPvarGetName(x), xlb, xub, xub-xlb);
8863 SCIP_CALL( SCIPaddExternBranchCand(scip, x, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) );
8876 * That is, registers all variables appearing in nonconvex terms^1 with a score that is given by the distance of the
8877 * variable value from its bounds. This rule should not make sense, as the distance to the bounds is also (often) considered
8880 * 1) We mean all quadratic variables that appear either in a nonconvex square term or in a bilinear term, if the constraint
8881 * itself is nonconvex. (and this under the assumption that the rhs is violated; for violated lhs, swap terms)
8920 SCIPdebugMessage("cons %s violation: %g %g convex: %u %u\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol, consdata->isconvex, consdata->isconcave);
8935 SCIPdebugMessage("ignore fixed variable <%s>[%g, %g], diff %g\n", SCIPvarGetName(x), xlb, xub, xub-xlb);
8948 if( (!SCIPisInfinity(scip, -xlb) && SCIPisEQ(scip, xval, xlb)) || (!SCIPisInfinity(scip, xub) && SCIPisEQ(scip, xval, xub)) )
9008 /** registers a quadratic variable from a violated constraint as branching candidate that has a large absolute value in the LP relaxation */
9035 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
9041 if( SCIPisRelEQ(scip, SCIPvarGetLbLocal(consdata->quadvarterms[i].var), SCIPvarGetUbLocal(consdata->quadvarterms[i].var)) )
9060 /** replaces violated quadratic constraints where all quadratic variables are fixed by linear constraints */
9096 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
9104 assert(SCIPisRelEQ(scip, SCIPvarGetLbLocal(consdata->quadvarterms[i].var), SCIPvarGetUbLocal(consdata->quadvarterms[i].var)));
9106 val1 = (SCIPvarGetUbLocal(consdata->quadvarterms[i].var) + SCIPvarGetLbLocal(consdata->quadvarterms[i].var)) / 2.0;
9107 constant += (consdata->quadvarterms[i].lincoef + consdata->quadvarterms[i].sqrcoef * val1) * val1;
9112 val1 = (SCIPvarGetUbLocal(consdata->bilinterms[i].var1) + SCIPvarGetLbLocal(consdata->bilinterms[i].var1)) / 2.0;
9113 val2 = (SCIPvarGetUbLocal(consdata->bilinterms[i].var2) + SCIPvarGetLbLocal(consdata->bilinterms[i].var2)) / 2.0;
9138 SCIPdebugMessage("Linear constraint with one variable: %g <= %g <%s> <= %g\n", lhs, coef, SCIPvarGetName(*consdata->linvars), rhs);
9163 SCIPdebugMessage("Linear constraint is a bound: %g <= <%s> <= %g\n", lhs, SCIPvarGetName(*consdata->linvars), rhs);
9217 SCIPdebugMessage("replace quadratic constraint <%s> by linear constraint after all quadratic vars have been fixed\n", SCIPconsGetName(conss[c]) );
9282 SCIPdebugMessage("%s found constraint <%s> infeasible due to tightened lower bound %g for variable <%s>\n",
9343 SCIPdebugMessage("%s found constraint <%s> infeasible due to tightened upper bound %g for variable <%s>\n",
9361 /** solves a quadratic equation \f$ a x^2 + b x \in rhs \f$ (with b an interval) and reduces bounds on x or deduces infeasibility if possible */
9389 SCIPdebugMessage("found <%s> infeasible due to domain propagation for quadratic variable <%s>\n", SCIPconsGetName(cons), SCIPvarGetName(var));
9413 SCIPdebugMessage("found <%s> infeasible due to domain propagation for quadratic variable <%s>\n", SCIPconsGetName(cons), SCIPvarGetName(var));
9428 /* SCIPdebugMessage("%g x^2 + [%g, %g] x in [%g, %g] -> [%g, %g]\n", a, b.inf, b.sup, rhs.inf, rhs.sup, newrange.inf, newrange.sup); */
9430 if( SCIPisInfinity(scip, SCIPintervalGetInf(newrange)) || SCIPisInfinity(scip, -SCIPintervalGetSup(newrange)) )
9433 SCIPdebugMessage("found <%s> infeasible because propagated domain of quadratic variable <%s> is outside of (-infty, +infty)\n",
9442 SCIPdebugMessage("found <%s> infeasible due to domain propagation for quadratic variable <%s>\n", SCIPconsGetName(cons), SCIPvarGetName(var));
9449 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, SCIPintervalGetInf(newrange), result, nchgbds) );
9456 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, SCIPintervalGetSup(newrange), result, nchgbds) );
9464 /* The new version below computes potentially tighter bounds, but also always adds a small safety area since it is not implemented roundingsafe.
9469 /** tries to deduce domain reductions for x in xsqrcoef x^2 + xlincoef x + ysqrcoef y^2 + ylincoef y + bilincoef x y \\in rhs
9508 SCIPintervalSetBounds(&varbnds, MIN(SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y)), MAX(SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y))); /*lint !e666 */
9513 /* if rhs is unbounded by above, it is sufficient to get an upper bound on ysqrcoef*y^2 + ylincoef * y */
9526 /* if rhs is unbounded by below, it is sufficient to get a lower bound on ysqrcoef*y^2 + ylincoef * y */
9552 SCIP_CALL( propagateBoundsQuadVar(scip, cons, intervalinfty, x, xsqrcoef, lincoef, myrhs, result, nchgbds) );
9557 /** tries to deduce domain reductions for x in xsqrcoef x^2 + xlincoef x + ysqrcoef y^2 + ylincoef y + bilincoef x y \\in rhs
9595 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x))), /*lint !e666*/
9596 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x)))); /*lint !e666*/
9598 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y))), /*lint !e666*/
9599 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y)))); /*lint !e666*/
9602 SCIPintervalSolveBivariateQuadExpressionAllScalar(intervalinfty, &xbnds, xsqrcoef, ysqrcoef, bilincoef, xlincoef, ylincoef, rhs, xbnds, ybnds);
9606 SCIPdebugMessage("found <%s> infeasible due to domain propagation for quadratic variable <%s>\n", SCIPconsGetName(cons), SCIPvarGetName(x));
9613 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, x, SCIPintervalGetInf(xbnds), result, nchgbds) );
9620 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, x, SCIPintervalGetSup(xbnds), result, nchgbds) );
9640 SCIP_Real* minquadactivity, /**< minimal activity of quadratic variable terms where only terms with finite minimal activity contribute */
9641 SCIP_Real* maxquadactivity, /**< maximal activity of quadratic variable terms where only terms with finite maximal activity contribute */
9642 int* minactivityinf, /**< number of quadratic variables that contribute -infinity to minimal activity */
9643 int* maxactivityinf, /**< number of quadratic variables that contribute +infinity to maximal activity */
9688 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->quadvarterms[i].var), SCIPvarGetUbLocal(consdata->quadvarterms[i].var))),
9689 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->quadvarterms[i].var), SCIPvarGetUbLocal(consdata->quadvarterms[i].var))));
9699 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))),
9700 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))));
9708 bnd = SCIPintervalQuadUpperBound(intervalinfty, consdata->quadvarterms[i].sqrcoef, lincoef, xrng);
9715 /* if maximal activity is below value for -infinity, let's take -1e10 as upper bound on maximal activity
9736 bnd = -SCIPintervalQuadUpperBound(intervalinfty, -consdata->quadvarterms[i].sqrcoef, lincoef, xrng);
9744 /* if minimal activity is above value for infinity, let's take 1e10 as lower bound on minimal activity
9777 SCIP_Bool* redundant /**< buffer where to store whether constraint has been found to be redundant */
9786 int quadminactinf; /* number of quadratic variables that contribute -infinity to minimal activity of quadratic term */
9787 int quadmaxactinf; /* number of quadratic variables that contribute +infinity to maximal activity of quadratic term */
9788 SCIP_INTERVAL* quadactcontr; /* contribution of each quadratic variable term to quadactivity */
9832 /* sort quadratic variable terms, in case we need to search for terms occuring in bilinear terms later
9845 propagateBoundsGetQuadActivity(scip, consdata, intervalinfty, &minquadactivity, &maxquadactivity, &quadminactinf, &quadmaxactinf, quadactcontr);
9860 SCIPintervalSetBounds(&consactivity, consdata->minlinactivityinf > 0 ? -intervalinfty : consdata->minlinactivity,
9865 SCIPdebugMessage("found constraint <%s> to be redundant: sides: [%g, %g], activity: [%g, %g]\n",
9866 SCIPconsGetName(cons), consdata->lhs, consdata->rhs, SCIPintervalGetInf(consactivity), SCIPintervalGetSup(consactivity));
9871 /* was SCIPintervalAreDisjoint(consbounds, consactivity), but that would allow violations up to eps only
9874 if( SCIPisFeasGT(scip, consbounds.inf, consactivity.sup) || SCIPisFeasLT(scip, consbounds.sup, consactivity.inf) )
9876 SCIPdebugMessage("found constraint <%s> to be infeasible; sides: [%g, %g], activity: [%g, %g], infeas: %g\n",
9877 SCIPconsGetName(cons), consdata->lhs, consdata->rhs, SCIPintervalGetInf(consactivity), SCIPintervalGetSup(consactivity),
9878 MAX(consdata->lhs - SCIPintervalGetSup(consactivity), SCIPintervalGetInf(consactivity) - consdata->rhs));
9883 /* propagate linear part \in rhs = consbounds - quadactivity (use the one from consdata, since that includes infinities) */
9896 * we can't expect much more tightening, but may detect infeasiblity, but shouldn't the check on the constraints activity detect that?
9918 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, bnd, result, nchgbds) );
9932 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, bnd, result, nchgbds) );
9954 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, bnd, result, nchgbds) );
9968 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, bnd, result, nchgbds) );
9993 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, bnd, result, nchgbds) );
10007 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, bnd, result, nchgbds) );
10029 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, bnd, result, nchgbds) );
10043 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, bnd, result, nchgbds) );
10058 consdataUpdateLinearActivity(scip, consdata, intervalinfty); /* make sure, activities of linear part did not become invalid by above bound changes, if any */
10059 assert(consdata->minlinactivityinf > 0 || consdata->maxlinactivityinf > 0 || consdata->minlinactivity <= consdata->maxlinactivity);
10077 SCIP_CALL( propagateBoundsQuadVar(scip, cons, intervalinfty, var, consdata->quadvarterms[0].sqrcoef, lincoef, rhs, result, nchgbds) );
10081 /* quadratic part is just ax*x^2+bx*x + ay*y^2+by*y + c*xy -> a common case that we treat directly */
10082 assert(consdata->bilinterms[0].var1 == consdata->quadvarterms[0].var || consdata->bilinterms[0].var1 == consdata->quadvarterms[1].var);
10083 assert(consdata->bilinterms[0].var2 == consdata->quadvarterms[0].var || consdata->bilinterms[0].var2 == consdata->quadvarterms[1].var);
10087 consdata->quadvarterms[0].var, consdata->quadvarterms[0].sqrcoef, consdata->quadvarterms[0].lincoef,
10088 consdata->quadvarterms[1].var, consdata->quadvarterms[1].sqrcoef, consdata->quadvarterms[1].lincoef,
10095 consdata->quadvarterms[1].var, consdata->quadvarterms[1].sqrcoef, consdata->quadvarterms[1].lincoef,
10096 consdata->quadvarterms[0].var, consdata->quadvarterms[0].sqrcoef, consdata->quadvarterms[0].lincoef,
10110 propagateBoundsGetQuadActivity(scip, consdata, intervalinfty, &minquadactivity, &maxquadactivity, &quadminactinf, &quadmaxactinf, quadactcontr);
10116 /* if the quad activities are not hopelessly unbounded on useful sides, try to deduce domain reductions on quad vars */
10131 * we can't expect much more tightening, but may detect infeasiblity, but shouldn't the check on the constraints activity detect that?
10138 /* setup rhs2.sup = rhs.sup - (quadactivity.inf - quadactcontr[i].inf), if everything were finite
10139 * if only quadactcontr[i].inf is infinite (i.e., the other i are all finite), we just get rhs2.sup = rhs.sup
10143 if( quadminactinf == 0 || (quadminactinf == 1 && SCIPintervalGetInf(quadactcontr[i]) <= -intervalinfty) )
10148 /* if the residual quad min activity w.r.t. quad var term i is finite and nonzero, so add it to right hand side */
10155 /* there are either >= 2 quad var terms contributing -infinity, or there is one which is not i */
10167 if( quadmaxactinf == 0 || (quadmaxactinf == 1 && SCIPintervalGetSup(quadactcontr[i]) >= intervalinfty) )
10172 /* if the residual quad max activity w.r.t. quad var term i is finite and nonzero, so add it to right hand side */
10179 /* there are either >= 2 quad var terms contributing infinity, or there is one which is not i */
10201 /* bilinear term k contributes to the activity of quad var term i, so just add bounds to linear coef */
10203 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))),
10204 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))));
10213 * if the bounds on bilinear term k as added to rhs2 are old due to recent bound tightening, we may not do best possible, but still correct
10214 * HOWEVER: when computing rhs2, we may not just have added the bounds for the bilinear term, but for the associated quadratic term
10216 * since we do not want to repeat a call to SCIPintervalQuad for that quadratic term with bilinear term k removed,
10217 * we only remove the bounds for the bilinear term k from rhs2 if the associated quadratic term consists only of this bilinear term,
10218 * i.e., the quadratic term corresponding to var1 should be only var1*var2, but have no square or linear coefs or other bilinear terms
10219 * (for efficiency reasons, we check here only if there are any other bilinear terms than var1*var2 associated with var1, even if they are not associated with the quad var term for var1)
10228 SCIP_CALL( consdataFindQuadVarTerm(scip, consdata, consdata->bilinterms[k].var1, &otherpos) );
10232 if( (consdata->quadvarterms[otherpos].sqrcoef != 0.0) || consdata->quadvarterms[otherpos].lincoef != 0.0 ||
10238 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var1), SCIPvarGetUbLocal(consdata->bilinterms[k].var1))),
10239 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var1), SCIPvarGetUbLocal(consdata->bilinterms[k].var1))));
10244 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))),
10245 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))));
10281 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))),
10282 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))));
10289 SCIP_CALL( propagateBoundsQuadVar(scip, cons, intervalinfty, var, consdata->quadvarterms[i].sqrcoef, lincoef, rhs2, result, nchgbds) );
10328 assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
10345 SCIPdebugMessage("starting domain propagation round %d of %d for %d constraints\n", roundnr, maxproprounds, nconss);
10372 /** checks for a linear variable that can be increase or decreased without harming feasibility */
10386 /* check for a linear variable that can be increase or decreased without harming feasibility */
10405 /* if we have already one candidate, then take the one where the loss in the objective function is less */
10407 (SCIPvarGetObj(consdata->linvars[consdata->linvar_maydecrease]) / consdata->lincoefs[consdata->linvar_maydecrease] > SCIPvarGetObj(consdata->linvars[i]) / consdata->lincoefs[i]) )
10414 /* if we have already one candidate, then take the one where the loss in the objective function is less */
10416 (SCIPvarGetObj(consdata->linvars[consdata->linvar_mayincrease]) / consdata->lincoefs[consdata->linvar_mayincrease] > SCIPvarGetObj(consdata->linvars[i]) / consdata->lincoefs[i]) )
10424 SCIPdebugMessage("may increase <%s> to become feasible\n", SCIPvarGetName(consdata->linvars[consdata->linvar_mayincrease]));
10428 SCIPdebugMessage("may decrease <%s> to become feasible\n", SCIPvarGetName(consdata->linvars[consdata->linvar_maydecrease]));
10433 /** Given a solution where every quadratic constraint is either feasible or can be made feasible by
10434 * moving a linear variable, construct the corresponding feasible solution and pass it to the trysol heuristic.
10436 * The method assumes that this is always possible and that not all constraints are feasible already.
10445 SCIP_Bool* success /**< buffer to store whether we succeeded to construct a solution that satisfies all provided constraints */
10478 sol != NULL ? (SCIPsolGetHeur(sol) != NULL ? SCIPheurGetName(SCIPsolGetHeur(sol)) : "tree") : "LP");
10506 ((viol > 0.0 && consdata->lincoefs[consdata->linvar_mayincrease] > 0.0) || (viol < 0.0 && consdata->lincoefs[consdata->linvar_mayincrease] < 0.0)) )
10526 SCIPdebugMessage("increase <%s> by %g to %g\n", SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var));
10537 ((viol > 0.0 && consdata->lincoefs[consdata->linvar_maydecrease] < 0.0) || (viol < 0.0 && consdata->lincoefs[consdata->linvar_maydecrease] > 0.0)) )
10556 SCIPdebugMessage("increase <%s> by %g to %g\n", SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var));
10565 /* still here... so probably we could not make constraint feasible due to variable bounds, thus give up */
10570 /* if we have a solution that should satisfy all quadratic constraints and has a better objective than the current upper bound,
10573 if( c == nconss && (SCIPisInfinity(scip, SCIPgetUpperbound(scip)) || SCIPisSumLT(scip, SCIPgetSolTransObj(scip, newsol), SCIPgetUpperbound(scip))) )
10575 SCIPdebugMessage("pass solution with objective val %g to trysol heuristic\n", SCIPgetSolTransObj(scip, newsol));
10591 {
10607 /* if a quadratic expression has been simplified, then all children of the node should be variables */
10641 /* these do not look like an quadratic expression (assuming the expression graph simplifier did run) */
10653 SCIPwarningMessage(scip, "unexpected expression operator %d in nonlinear constraint <%s>\n", SCIPexprgraphGetNodeOperator(node), SCIPconsGetName(cons));
10668 SCIPgetNLinearVarsNonlinear(scip, cons), SCIPgetLinearVarsNonlinear(scip, cons), SCIPgetLinearCoefsNonlinear(scip, cons),
10682 SCIP_CALL( SCIPaddQuadVarQuadratic(scip, upgdconss[0], (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, SCIPexprgraphGetNodeChildren(node)[i]), 0.0, 0.0) );
10740 (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, SCIPexprgraphGetNodeChildren(node)[quadelems[i].idx1]),
10747 (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, SCIPexprgraphGetNodeChildren(node)[quadelems[i].idx1]),
10748 (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, SCIPexprgraphGetNodeChildren(node)[quadelems[i].idx2]),
10784 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
10787 {
10828 /** deinitialization method of constraint handler (called before transformed problem is freed) */
10846 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
10866 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
10917 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin)
10923 {
10942 /* check for a linear variable that can be increase or decreased without harming feasibility */
10950 consdata->lincoefsmin = MIN(consdata->lincoefsmin, REALABS(consdata->lincoefs[i])); /*lint !e666 */
10951 consdata->lincoefsmax = MAX(consdata->lincoefsmax, REALABS(consdata->lincoefs[i])); /*lint !e666 */
10971 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->sepabilinvar2pos, consdata->nbilinterms) );
10981 SCIP_CALL( consdataFindQuadVarTerm(scip, consdata, consdata->bilinterms[i].var2, &consdata->sepabilinvar2pos[i]) );
10987 /* check if constraint function is factorable, i.e., can be written as product of two linear functions */
10991 /* compute gauge function using interior points per constraint, only when there are quadratic variables */
11019 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, (SCIP_EVENTDATA*)conshdlr, &conshdlrdata->newsoleventfilterpos) );
11024 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Quadratic constraint handler does not have LAPACK for eigenvalue computation. Will assume that matrices (with size > 2x2) are indefinite.\n");
11035 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
11089 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, (SCIP_EVENTDATA*)conshdlr, conshdlrdata->newsoleventfilterpos) );
11099 {
11116 {
11139 SCIP_CALL( SCIPgetTransformedVar(scip, targetdata->quadvarterms[i].var, &targetdata->quadvarterms[i].var) );
11145 SCIP_CALL( SCIPgetTransformedVar(scip, targetdata->bilinterms[i].var1, &targetdata->bilinterms[i].var1) );
11146 SCIP_CALL( SCIPgetTransformedVar(scip, targetdata->bilinterms[i].var2, &targetdata->bilinterms[i].var2) );
11158 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
11159 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
11161 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons),
11170 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
11173 {
11205 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(conss[c]), SCIPconsGetName(conss[c]), consdata->lhs, consdata->rhs,
11207 SCIP_CALL( SCIPaddVarsToRow(scip, row, consdata->nlinvars, consdata->linvars, consdata->lincoefs) );
11254 SCIP_CALL( generateCut(scip, conshdlr, conss[c], x, NULL, consdata->isconvex ? SCIP_SIDETYPE_RIGHT : SCIP_SIDETYPE_LEFT, &row, NULL,
11260 SCIPdebugMessage("initlp adds row <%s> for lambda = %g of conss <%s>\n", SCIProwGetName(row), lambda, SCIPconsGetName(conss[c])); /*lint !e613 */
11274 if( (! consdata->isconvex && !SCIPisInfinity(scip, consdata->rhs)) || (! consdata->isconcave && !SCIPisInfinity(scip, -consdata->lhs)) )
11289 /* Set reference point to 0 projected on bounds for unbounded variables or in between lower and upper bound
11290 * for bounded variables in the first round, we set it closer to the best bound for one part of the
11293 * The reason for the latter is, that for a bilinear term with bounded variables, there are always two linear underestimators
11294 * if the same weight is used for both variables of a product, then rounding and luck decides which underestimator is chosen
11295 * of course, the possible number of cuts is something in the order of 2^nquadvars, and we choose two of them here.
11321 x[i] = lambda * SCIPvarGetBestBoundLocal(var) + (1.0-lambda) * SCIPvarGetWorstBoundLocal(var);
11337 SCIPdebugMessage("initlp adds row <%s> for rhs of conss <%s>, round %d\n", SCIProwGetName(row), SCIPconsGetName(conss[c]), k); /*lint !e613 */
11356 SCIPdebugMessage("initlp adds row <%s> for lhs of conss <%s>, round %d\n", SCIProwGetName(row), SCIPconsGetName(conss[c]), k); /*lint !e613 */
11368 /* if there are unbounded variables, then there is typically only at most one possible underestimator, so don't try another round
11369 * similar, if there are no bilinear terms and no linearizations of square terms, then the reference point does not matter, so don't do another round */
11386 {
11404 /* at root, check if we want to solve the NLP relaxation and use its solutions as reference point
11405 * if there is something convex, then linearizing in the solution of the NLP relaxation can be very useful
11409 (SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_UNBOUNDEDRAY && conshdlrdata->sepanlpmincont <= 1.0)) &&
11422 * but first check whether there is a violated constraint side which corresponds to a convex function
11432 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
11500 SCIPdebugMessage("pass solution with obj. value %g to trysol\n", SCIPgetSolOrigObj(scip, nlpsol));
11505 SCIP_CALL( addLinearizationCuts(scip, conshdlr, conss, nconss, nlpsol, &lpsolseparated, conshdlrdata->mincutefficacysepa) );
11509 /* if a cut that separated the LP solution was added, then return, otherwise continue with usual separation in LP solution */
11519 /* if we do not want to try solving the NLP, or have no NLP, or have no NLP solver, or solving the NLP failed,
11520 * or separating with NLP solution as reference point failed, then try (again) with LP solution as reference point
11523 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, conshdlrdata->mincutefficacysepa, FALSE, result, NULL) );
11531 {
11550 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, sol, conshdlrdata->mincutefficacysepa, FALSE, result, NULL) );
11592 SCIPdebugMessage("enfolp with max violation %g in cons <%s>\n", maxviol, SCIPconsGetName(maxviolcon));
11595 * (maybe the LP does not think that the cuts we add are violated, or we do ECP on a high-dimensional convex function)
11596 * 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
11597 * (in optimized more, returning SCIP_INFEASIBLE in *result would be sufficient, but in debug mode this would give an assert in scip.c)
11598 * the reason to wait for 100 rounds is to avoid calls to SCIPisStopped in normal runs, which may be expensive
11609 SCIP_CALL( SCIPcreateChild(scip, &child, 1.0, SCIPnodeGetEstimate(SCIPgetCurrentNode(scip))) );
11618 /* cut off the current subtree, if a limit on the enforcement rounds should be applied. At this point, feasible
11619 * solutions might get cut off; the enfolplimit parameter should therefore only be set if SCIP is used as a
11622 if( conshdlrdata->enfolplimit != -1 && conshdlrdata->nenfolprounds > conshdlrdata->enfolplimit )
11625 "cut off subtree because enforcement limit was reached; this might lead to incorrect results\n");
11641 SCIPdebugMessage("propagation succeeded (%s)\n", propresult == SCIP_CUTOFF ? "cutoff" : "reduceddom");
11648 * thus, in the latter case, we are also happy if the efficacy is at least, say, 75% of the maximal violation
11651 minefficacy = MIN(0.75*maxviol, conshdlrdata->mincutefficacyenfofac * SCIPfeastol(scip)); /*lint !e666 */
11653 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, minefficacy, TRUE, &separateresult, &sepaefficacy) );
11662 SCIPdebugMessage("separation succeeded (bestefficacy = %g, minefficacy = %g)\n", sepaefficacy, minefficacy);
11671 SCIPdebugMessage("separation failed (bestefficacy = %g < %g = minefficacy ); max viol: %g\n", sepaefficacy, minefficacy, maxviol);
11676 /* if sepastore can decrease LP feasibility tolerance, we can add cuts with efficacy in [eps, feastol] */
11677 leastpossibleefficacy = SCIPgetRelaxFeastolFactor(scip) > 0.0 ? SCIPepsilon(scip) : SCIPfeastol(scip);
11681 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, leastpossibleefficacy, TRUE, &separateresult, &sepaefficacy) );
11698 /* fallback 2: separation probably failed because of numerical difficulties with a convex constraint;
11699 * if noone declared solution infeasible yet and we had not even found a weak cut, try to resolve by branching
11710 SCIP_CALL( replaceByLinearConstraints(scip, conss, nconss, &addedcons, &reduceddom, &infeasible) );
11711 /* if the linear constraints are actually feasible, then adding them and returning SCIP_CONSADDED confuses SCIP
11712 * when it enforces the new constraints again and nothing resolves the infeasiblity that we declare here thus,
11713 * we only add them if considered violated, and otherwise claim the solution is feasible (but print a
11724 SCIPwarningMessage(scip, "could not enforce feasibility by separating or branching; declaring solution with viol %g as feasible\n", maxviol);
11731 SCIPdebugMessage("Could not find any usual branching variable candidate. Proposed variable <%s> with LP value %g for branching.\n",
11788 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
11796 SCIP_CALL( SCIPaddExternBranchCand(scip, var, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) );
11806 SCIP_CALL( SCIPaddExternBranchCand(scip, var, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) );
11814 SCIPdebugMessage("All variables in violated constraints fixed (up to epsilon). Cannot find branching candidate. Forcing solution of LP.\n");
11825 {
11860 * then try the reformulations (replacing products with binaries, disaggregation, setting default variable bounds)
11862 * @todo first do all usual presolving steps, then check SCIPisPresolveFinished(scip), and if true then do reformulations (and usual steps again)
11864 doreformulations = nrounds > 0 && ((presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 || SCIPisPresolveFinished(scip));
11865 SCIPdebugMessage("presolving will %swait with reformulation\n", doreformulations ? "not " : "");
11902 /* call upgrade methods if the constraint has not been presolved yet or there has been a bound tightening or possibly be a change in variable type
11903 * we want to do this before (multi)aggregated variables are replaced, since that may change structure, e.g., introduce bilinear terms
11909 SCIP_CALL( presolveUpgrade(scip, conshdlr, conss[c], &upgraded, nupgdconss, naddconss, presoltiming) );
11928 SCIPdebugMessage("solving constraint <%s> says problem is infeasible in presolve\n", SCIPconsGetName(conss[c]));
11958 /* user not so empathic about AND, or we don't have products of two binaries, so try this more general reformulation */
11994 SCIPdebugMessage("constraint <%s> is constant and feasible, deleting\n", SCIPconsGetName(conss[c]));
12003 /* try domain propagation if there were bound changes or constraint has changed (in which case, processVarEvents may have set ispropagated to false) */
12012 SCIPdebugMessage("starting domain propagation round %d of %d\n", roundnr, conshdlrdata->maxproproundspresolve);
12018 SCIPdebugMessage("propagation on constraint <%s> says problem is infeasible in presolve\n", SCIPconsGetName(conss[c]));
12083 SCIPdebugMessage("make variable <%s> implicit integer due to constraint <%s>\n", SCIPvarGetName(candidate), SCIPconsGetName(conss[c]));
12088 SCIPdebugMessage("infeasible upgrade of variable <%s> to integral type, domain is empty\n", SCIPvarGetName(candidate));
12105 SCIP_CALL( presolveUpgrade(scip, conshdlr, conss[c], &upgraded, nupgdconss, naddconss, presoltiming) );
12165 /* @todo try to be more clever, but variable locks that depend on the bounds of other variables are not trival to maintain */
12166 SCIP_CALL( SCIPaddVarLocks(scip, consdata->quadvarterms[i].var, nlockspos+nlocksneg, nlockspos+nlocksneg) );
12175 {
12334 SCIP_CALL( SCIPwriteVarsPolynomial(scip, file, monomialvars, monomialexps, monomialcoefs, monomialnvars, nmonomials, TRUE) );
12400 if( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) )
12409 SCIPinfoMessage(scip, NULL, "violation: left hand side is violated by %.15g (scaled: %.15g)\n", consdata->lhs - consdata->activity, consdata->lhsviol);
12413 SCIPinfoMessage(scip, NULL, "violation: right hand side is violated by %.15g (scaled: %.15g)\n", consdata->activity - consdata->rhs, consdata->rhsviol);
12421 /* do not try to shift linear variables if activity is at infinity (leads to setting variable to infinity in solution, which is not allowed) */
12435 if( !(consdata->linvar_mayincrease >= 0 && consdata->lincoefs[consdata->linvar_mayincrease] > 0.0) &&
12436 ! (consdata->linvar_maydecrease >= 0 && consdata->lincoefs[consdata->linvar_maydecrease] < 0.0) )
12444 if( !(consdata->linvar_mayincrease >= 0 && consdata->lincoefs[consdata->linvar_mayincrease] < 0.0) &&
12445 ! (consdata->linvar_maydecrease >= 0 && consdata->lincoefs[consdata->linvar_maydecrease] > 0.0) )
12474 {
12506 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, consdata->linvars[i], &linvars[i], varmap, consmap, global, valid) );
12525 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, consdata->quadvarterms[i].var, &quadvarterms[i].var, varmap, consmap, global, valid) );
12619 if( isdigit((unsigned char)str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit((unsigned char)str[1])) )
12648 SCIP_CALL( SCIPparseVarsPolynomial(scip, str, &monomialvars, &monomialexps, &monomialcoefs, &monomialnvars, &nmonomials, &endptr, success) );
12772 SCIPfreeParseVarsPolynomialData(scip, &monomialvars, &monomialexps, &monomialcoefs, &monomialnvars, nmonomials);
12808 /** constraint method of constraint handler which returns the number of variables (if possible) */
12866 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolQuadratic, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
12868 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropQuadratic, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
12870 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpQuadratic, consSepasolQuadratic, CONSHDLR_SEPAFREQ,
12876 "max. length of linear term which when multiplied with a binary variables is replaced by an auxiliary variable and a linear reformulation (0 to turn off)",
12880 "empathy level for using the AND constraint handler: 0 always avoid using AND; 1 use AND sometimes; 2 use AND as often as possible",
12884 "whether to make non-varbound linear constraints added due to replacing products with binary variables initial",
12888 "limit (as factor on 1/feastol) on coefficients and coef. range in linear constraints created when replacing products with binary variables",
12892 "minimal efficacy for a cut to be added to the LP during separation; overwrites separating/efficacy",
12896 "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)",
12900 "whether scaling of infeasibility is 'o'ff, by sup-norm of function 'g'radient, or by left/right hand 's'ide",
12904 "maximal coef range of a cut (maximal coefficient divided by minimal coefficient) in order to be added to LP relaxation",
12908 "whether linearizations of convex quadratic constraints should be added to cutpool in a solution found by some heuristic",
12920 "whether to try to make solutions in check function feasible by shifting a linear variable (esp. useful if constraint was actually objective function)",
12924 "whether to disaggregate quadratic parts that decompose into a sum of non-overlapping quadratic terms",
12928 "limit on number of propagation rounds for a single constraint within one round of SCIP propagation during solve",
12932 "limit on number of propagation rounds for a single constraint within one round of SCIP presolve",
12936 "maximum number of enforcement rounds before declaring the LP relaxation infeasible (-1: no limit); WARNING: changing this parameter might lead to incorrect results!",
12940 "minimal required fraction of continuous variables in problem to use solution of NLP relaxation in root for separation",
12952 "how the interior point should be computed: 'a'ny point per constraint, 'm'ost interior per constraint",
12956 "which score to give branching candidates: convexification 'g'ap, constraint 'v'iolation, 'c'entrality of variable value in domain",
12960 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->eventhdlr),CONSHDLR_NAME"_boundchange", "signals a bound change to a quadratic constraint",
12964 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, NULL, CONSHDLR_NAME"_newsolution", "handles the event that a new primal solution has been found",
12968 SCIP_CALL( SCIPincludeNonlinconsUpgrade(scip, nonlinconsUpgdQuadratic, NULL, NONLINCONSUPGD_PRIORITY, TRUE, CONSHDLR_NAME) );
12976 SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), /**< method to call for upgrading quadratic constraint */
13023 for( i = conshdlrdata->nquadconsupgrades; i > 0 && conshdlrdata->quadconsupgrades[i-1]->priority < quadconsupgrade->priority; --i )
13030 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "constraints/" CONSHDLR_NAME "/upgrade/%s", conshdlrname);
13031 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "enable quadratic upgrading for constraint handler <%s>", conshdlrname);
13048 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
13081 SCIP_Bool removable /**< should the relaxation be removed from the LP due to aging or cleanup?
13111 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
13115 SCIP_CALL( SCIPhashmapCreate(&quadvaridxs, SCIPblkmem(scip), SCIPcalcHashtableSize(5 * nquadterms)) );
13135 SCIP_CALL( SCIPhashmapInsert(quadvaridxs, quadvars1[i], (void*)(size_t)(consdata->nquadvars-1)) );
13156 SCIP_CALL( SCIPhashmapInsert(quadvaridxs, quadvars2[i], (void*)(size_t)(consdata->nquadvars-1)) );
13192 /* if it's a linear coefficient for a quadratic variable, add it there, otherwise add as linear variable */
13222 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
13250 * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m (a_j y_j^2 + b_j y_j) + \sum_{k=1}^p c_k v_k w_k \leq u.
13253 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
13276 SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
13301 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
13312 * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m (a_j y_j^2 + b_j y_j) + \sum_{k=1}^p c_k v_k w_k \leq u.
13315 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
13340 /** Adds a constant to the constraint function, that is, subtracts a constant from both sides */
13401 /** Adds a quadratic variable with linear and square coefficient to a quadratic constraint. */
13473 consdata->ispresolved = consdata->ispresolved && !SCIPisZero(scip, consdata->quadvarterms[pos].lincoef);
13529 consdata->ispresolved = consdata->ispresolved && !SCIPisZero(scip, consdata->quadvarterms[pos].sqrcoef);
13715 * @note If the quadratic variable terms have not been sorted before, then a search may reorder the current order of the terms.
13784 /** Check the quadratic function of a quadratic constraint for its semi-definiteness, if not done yet. */
13797 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) convex. */
13814 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) concave. */
13861 * That is, checks whether each variable with a square term is fixed and for each bilinear term at least one variable is fixed.
13914 SCIP_HASHMAP* scipvar2nlpivar, /**< mapping from SCIP variables to variable indices in NLPI */
14006 /* if othervar is on position 2, then we process this bilinear term later (or it was processed already) */
14042 * @note This method may only be called during problem creation stage for an original constraint.
14064 SCIPerrorMessage("method may only be called during problem creation stage for original constraints\n");
14087 * @note This method may only be called during problem creation stage for an original constraint.
14109 SCIPerrorMessage("method may only be called during problem creation stage for original constraints\n");
14201 /** changes the linear coefficient value for a given quadratic variable in a quadratic constraint data; if not
14227 if( SCIPgetStage(scip) > SCIP_STAGE_PROBLEM || !SCIPconsIsOriginal(cons) || !SCIPvarIsOriginal(var) )
14229 SCIPerrorMessage("method may only be called during problem creation stage for original constraints and variables\n");
14266 /* decrease i by one since otherwise we would skip the coefficient which has been switched to position i */
14294 /** changes the square coefficient value for a given quadratic variable in a quadratic constraint data; if not
14321 if( SCIPgetStage(scip) > SCIP_STAGE_PROBLEM || !SCIPconsIsOriginal(cons) || !SCIPvarIsOriginal(var) )
14323 SCIPerrorMessage("method may only be called during problem creation stage for original constraints and variables\n");
14363 /** changes the bilinear coefficient value for a given quadratic variable in a quadratic constraint data; if not
14392 if( SCIPgetStage(scip) > SCIP_STAGE_PROBLEM || !SCIPconsIsOriginal(cons) || !SCIPvarIsOriginal(var1) || !SCIPvarIsOriginal(var2) )
14394 SCIPerrorMessage("method may only be called during problem creation stage for original constraints and variables\n");
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing) Definition: var.c:17250 Definition: type_nlpi.h:46 void SCIPintervalDivScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2) Definition: intervalarith.c:1182 SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var) Definition: var.c:16759 static SCIP_Bool conshdlrdataHasUpgrade(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), const char *conshdlrname) Definition: cons_quadratic.c:234 static SCIP_RETCODE mergeAndCleanLinearVars(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:2624 static SCIP_Bool generateCutLTIgenMulCoeff(SCIP *scip, SCIP_Real x1, SCIP_Real y1_, SCIP_Real x2, SCIP_Real y2, SCIP_Bool whichuse, SCIP_Real *cx, SCIP_Real *cy, SCIP_Real *cw) Definition: cons_quadratic.c:5598 void SCIPintervalMulSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:903 static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_Real lhs, SCIP_Real rhs, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadvars, SCIP_QUADVARTERM *quadvarterms, int nbilinterms, SCIP_BILINTERM *bilinterms, SCIP_Bool capturevars) Definition: cons_quadratic.c:1177 Definition: type_result.h:33 Definition: type_nlpi.h:65 SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name) Definition: scip.c:5847 static SCIP_RETCODE propagateBoundsQuadVar(SCIP *scip, SCIP_CONS *cons, SCIP_Real intervalinfty, SCIP_VAR *var, SCIP_Real a, SCIP_INTERVAL b, SCIP_INTERVAL rhs, SCIP_RESULT *result, int *nchgbds) Definition: cons_quadratic.c:9364 Definition: type_result.h:37 SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans))) Definition: scip.c:5557 static SCIP_DECL_CONSENFOPS(consEnfopsQuadratic) Definition: cons_quadratic.c:11745 Definition: type_expr.h:55 SCIP_BILINTERM * SCIPgetBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13750 static void consdataMoveLinearVar(SCIP_CONSDATA *consdata, int oldpos, int newpos) Definition: cons_quadratic.c:1674 SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand) Definition: intervalarith.c:504 SCIP_EXPRGRAPH * SCIPgetExprgraphNonlinear(SCIP *scip, SCIP_CONSHDLR *conshdlr) Definition: cons_nonlinear.c:9777 static SCIP_RETCODE consdataSortBilinTerms(SCIP *scip, SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:1596 primal heuristic that tries a given solution Definition: type_nlpi.h:64 Definition: intervalarith.h:36 Definition: type_expr.h:57 static SCIP_RETCODE separatePoint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_Real minefficacy, SCIP_Bool inenforcement, SCIP_RESULT *result, SCIP_Real *bestefficacy) Definition: cons_quadratic.c:8243 static SCIP_DECL_CONSSEPASOL(consSepasolQuadratic) Definition: cons_quadratic.c:11531 SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated) Definition: scip.c:22873 static SCIP_RETCODE consdataEnsureQuadVarTermsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num) Definition: cons_quadratic.c:1062 static SCIP_DECL_CONSINITSOL(consInitsolQuadratic) Definition: cons_quadratic.c:10923 Definition: struct_scip.h:53 Constraint handler for variable bound constraints . static SCIP_RETCODE generateCutNonConvex(SCIP *scip, SCIP_CONS *cons, SCIP_SIDETYPE violside, SCIP_Real *ref, SCIP_Real *coef, SCIP_Real *lhs, SCIP_Real *rhs, SCIP_Bool *islocal, SCIP_Bool *success, char *name) Definition: cons_quadratic.c:6733 Definition: type_expr.h:70 static SCIP_RETCODE propagateBoundsBilinearTerm(SCIP *scip, SCIP_CONS *cons, SCIP_Real intervalinfty, SCIP_VAR *x, SCIP_Real xsqrcoef, SCIP_Real xlincoef, SCIP_VAR *y, SCIP_Real ysqrcoef, SCIP_Real ylincoef, SCIP_Real bilincoef, SCIP_INTERVAL rhs, SCIP_RESULT *result, int *nchgbds) Definition: cons_quadratic.c:9563 SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur) Definition: scip.c:33682 SCIP_RETCODE SCIPgetViolationQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *violation) Definition: cons_quadratic.c:13833 Definition: type_nlpi.h:66 int SCIPexprgraphGetNodeNChildren(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12716 Definition: type_expr.h:63 SCIP_QUADVARTERM * SCIPgetQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13689 void SCIPwarningMessage(SCIP *scip, const char *formatstr,...) Definition: scip.c:1220 SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata) Definition: scip.c:15823 SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41528 static SCIP_RETCODE replaceQuadVarTermPos(SCIP *scip, SCIP_CONS *cons, int pos, SCIP_VAR *var, SCIP_Real coef, SCIP_Real offset) Definition: cons_quadratic.c:2158 SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa) Definition: scip.c:5215 void SCIPsortPtrPtrReal(void **ptrarray1, void **ptrarray2, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) void SCIPaddBilinLinearization(SCIP *scip, SCIP_Real bilincoef, SCIP_Real refpointx, SCIP_Real refpointy, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success) Definition: cons_quadratic.c:6396 SCIP_RETCODE SCIPaddBilinTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef) Definition: cons_quadratic.c:13543 static SCIP_RETCODE getImpliedBounds(SCIP *scip, SCIP_VAR *x, SCIP_Bool xval, SCIP_VAR *y, SCIP_INTERVAL *resultant) Definition: cons_quadratic.c:3381 Definition: type_result.h:49 SCIP_RETCODE SCIPcreateConsBasicQuadratic2(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadvarterms, SCIP_QUADVARTERM *quadvarterms, int nbilinterms, SCIP_BILINTERM *bilinterms, SCIP_Real lhs, SCIP_Real rhs) Definition: cons_quadratic.c:13318 SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr) Definition: cons.c:4262 SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadvars, SCIP_VAR **quadvars, int nquadelems, SCIP_QUADELEM *quadelems, SCIP_EXPRTREE *expression, SCIP_Real lhs, SCIP_Real rhs) Definition: scip.c:29352 static SCIP_DECL_CONSSEPALP(consSepalpQuadratic) Definition: cons_quadratic.c:11386 internal methods for NLPI solver interfaces SCIP_RETCODE SCIPchgLhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs) Definition: cons_quadratic.c:14045 static SCIP_RETCODE lockLinearVariable(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:559 Definition: type_expr.h:72 static SCIP_RETCODE catchVarEvents(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons) Definition: cons_quadratic.c:474 SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy))) Definition: scip.c:5303 SCIP_RETCODE SCIPheurPassSolTrySol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol) Definition: heur_trysol.c:236 static SCIP_RETCODE generateCutConvex(SCIP *scip, SCIP_CONS *cons, SCIP_SIDETYPE violside, SCIP_Real *ref, SCIP_Real *coef, SCIP_Real *lhs, SCIP_Real *rhs, SCIP_Bool *islocal, SCIP_Bool *success, char *name) Definition: cons_quadratic.c:6643 Definition: struct_var.h:196 static void consdataUpdateLinearActivityUbChange(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_Real coef, SCIP_Real oldbnd, SCIP_Real newbnd) Definition: cons_quadratic.c:869 static SCIP_RETCODE dropLinearVarEvents(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons, int linvarpos) Definition: cons_quadratic.c:337 static SCIP_RETCODE addQuadVarTerm(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real lincoef, SCIP_Real sqrcoef) Definition: cons_quadratic.c:1993 SCIP_RETCODE SCIPsortQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13701 SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant) Definition: scip.c:17512 static SCIP_DECL_CONSENABLE(consEnableQuadratic) Definition: cons_quadratic.c:12175 static SCIP_RETCODE generateCut(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Real *ref, SCIP_SOL *sol, SCIP_SIDETYPE violside, SCIP_ROW **row, SCIP_Real *efficacy, SCIP_Bool checkcurvmultivar, SCIP_Real minefficacy) Definition: cons_quadratic.c:6841 SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars))) Definition: scip.c:5787 static void consdataUpdateLinearActivityLbChange(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_Real coef, SCIP_Real oldbnd, SCIP_Real newbnd) Definition: cons_quadratic.c:766 static SCIP_DECL_NONLINCONSUPGD(nonlinconsUpgdQuadratic) Definition: cons_quadratic.c:10591 Definition: cons_quadratic.h:75 Definition: type_message.h:45 void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode) Definition: intervalarith.c:188 SCIP_RETCODE SCIPsetConshdlrEnable(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENABLE((*consenable))) Definition: scip.c:5672 static SCIP_DECL_CONSEXITPRE(consExitpreQuadratic) Definition: cons_quadratic.c:10869 SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize) Definition: misc.c:2052 static SCIP_Real getGradientMaxElement(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol) Definition: cons_quadratic.c:4892 static SCIP_RETCODE evaluateGauge(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SOL *refsol, SCIP_Real *gaugeval, SCIP_Bool *success) Definition: cons_quadratic.c:7730 SCIP_RETCODE SCIPaddQuadVarLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:13433 SCIP_RETCODE SCIPnlpiFreeProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem) Definition: nlpi.c:224 SCIP_RETCODE SCIPwriteVarsPolynomial(SCIP *scip, FILE *file, SCIP_VAR ***monomialvars, SCIP_Real **monomialexps, SCIP_Real *monomialcoefs, int *monomialnvars, int nmonomials, SCIP_Bool type) Definition: scip.c:16113 void SCIPaddSquareLinearization(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success) Definition: cons_quadratic.c:6281 static SCIP_RETCODE presolveSolve(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result, SCIP_Bool *redundant, int *naggrvars) Definition: cons_quadratic.c:3198 Definition: type_expr.h:60 Definition: type_expr.h:71 SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata) Definition: scip.c:7747 SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval) Definition: scip.c:33006 static SCIP_RETCODE registerBranchingCandidatesViolation(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int *nnotify) Definition: cons_quadratic.c:8801 Definition: type_var.h:53 SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse))) Definition: scip.c:5764 static void consdataFindUnlockedLinearVar(SCIP *scip, SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:10375 static void checkCurvatureEasy(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *determined, SCIP_Bool checkmultivariate) Definition: cons_quadratic.c:4441 void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup) Definition: intervalarith.c:479 SCIP_VAR ** SCIPgetLinearVarsNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9549 SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals) Definition: scip.c:27875 static SCIP_RETCODE removeBilinearTermsPos(SCIP *scip, SCIP_CONS *cons, int nterms, int *termposs) Definition: cons_quadratic.c:2428 Definition: type_expr.h:98 static SCIP_RETCODE computeViolation(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SOL *sol) Definition: cons_quadratic.c:4944 Definition: type_lp.h:55 SCIP_RETCODE SCIPaddQuadVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real lincoef, SCIP_Real sqrcoef) Definition: cons_quadratic.c:13403 SCIP_DECL_QUADCONSUPGD((*quadconsupgd)) SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var) Definition: scip.c:34593 Definition: type_expr.h:38 SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom) Definition: misc.c:7615 SCIP_RETCODE SCIPnlpiGetSolution(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real **primalvalues, SCIP_Real **consdualvalues, SCIP_Real **varlbdualvalues, SCIP_Real **varubdualvalues) Definition: nlpi.c:535 Definition: type_result.h:40 static SCIP_RETCODE registerBranchingCandidatesCentrality(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int *nnotify) Definition: cons_quadratic.c:8885 static SCIP_RETCODE presolveTryAddAND(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, int *naddconss) Definition: cons_quadratic.c:3285 Constraint handler for "and" constraints, . SCIP_Bool SCIPisLinearLocalQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13864 SCIP_RETCODE SCIPaddToNlpiProblemQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *scipvar2nlpivar, SCIP_Bool names) Definition: cons_quadratic.c:13910 static SCIP_RETCODE mergeAndCleanBilinearTerms(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:2696 int SCIPgetNLinearVarsNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9537 SCIP_Real SCIPgetRhsNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9636 void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2111 static SCIP_RETCODE chgLinearCoefPos(SCIP *scip, SCIP_CONS *cons, int pos, SCIP_Real newcoef) Definition: cons_quadratic.c:1897 static SCIP_RETCODE propagateBoundsCons(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_RESULT *result, int *nchgbds, SCIP_Bool *redundant) Definition: cons_quadratic.c:9772 static SCIP_DECL_CONSENFOLP(consEnfolpQuadratic) Definition: cons_quadratic.c:11558 Definition: type_message.h:46 SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file) Definition: scip.c:26224 SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible) Definition: scip.c:30577 static SCIP_RETCODE dropQuadVarEvents(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons, int quadvarpos) Definition: cons_quadratic.c:436 static void consdataUpdateLinearActivity(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_Real intervalinfty) Definition: cons_quadratic.c:652 Definition: type_expr.h:53 Definition: type_expr.h:44 Definition: struct_tree.h:122 SCIP_RETCODE SCIPgetNLPFracVars(SCIP *scip, SCIP_VAR ***fracvars, SCIP_Real **fracvarssol, SCIP_Real **fracvarsfrac, int *nfracvars, int *npriofracvars) Definition: scip.c:28897 SCIP_Real SCIPgetLhsNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9624 static SCIP_RETCODE lockQuadraticVariable(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) Definition: cons_quadratic.c:621 SCIP_RETCODE SCIPincludeConshdlrQuadratic(SCIP *scip) Definition: cons_quadratic.c:12833 SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree))) Definition: scip.c:5328 SCIP_RETCODE SCIPcreateConsVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_varbound.c:4517 void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs) Definition: intervalarith.c:2957 Definition: type_nlpi.h:67 static SCIP_RETCODE unlockQuadraticVariable(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) Definition: cons_quadratic.c:634 SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name) Definition: scip.c:7877 Definition: struct_sol.h:50 SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit))) Definition: scip.c:5352 SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3516 SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2154 SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3542 SCIP_RETCODE SCIPcreateConsQuadratic(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable) Definition: cons_quadratic.c:13051 SCIP_EXPROP SCIPexprgraphGetNodeOperator(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12776 static SCIP_RETCODE consdataSortQuadVarTerms(SCIP *scip, SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:1432 SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr) Definition: cons.c:3921 Definition: type_expr.h:45 void SCIPaddConstantQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real constant) Definition: cons_quadratic.c:13342 Definition: type_expr.h:47 SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos) Definition: scip.c:36232 Definition: type_expr.h:74 static SCIP_RETCODE registerBranchingCandidates(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int *nnotify) Definition: cons_quadratic.c:8972 Definition: struct_misc.h:101 SCIP_RETCODE SCIPincludeNonlinconsUpgrade(SCIP *scip, SCIP_DECL_NONLINCONSUPGD((*nonlinconsupgd)), SCIP_DECL_EXPRGRAPHNODEREFORM((*nodereform)), int priority, SCIP_Bool active, const char *conshdlrname) Definition: cons_nonlinear.c:9123 static SCIP_RETCODE checkCurvature(SCIP *scip, SCIP_CONS *cons, SCIP_Bool checkmultivariate) Definition: cons_quadratic.c:4506 Definition: type_expr.h:51 SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success) Definition: scip.c:1750 static SCIP_RETCODE presolveTryAddLinearReform(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, int *naddconss) Definition: cons_quadratic.c:3472 static void generateCutFactorableDo(SCIP *scip, SCIP_CONS *cons, SCIP_Real *ref, SCIP_Real multleft, SCIP_Real *coefleft, SCIP_Real multright, SCIP_Real *coefright, SCIP_Real rightminactivity, SCIP_Real rightmaxactivity, SCIP_Real rhs, SCIP_Real *cutcoef, SCIP_Real *cutrhs, SCIP_Bool *islocal, SCIP_Bool *success, char *name) Definition: cons_quadratic.c:5152 SCIP_NLPTERMSTAT SCIPnlpiGetTermstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem) Definition: nlpi.c:521 SCIP_RETCODE SCIPcheckCurvatureQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13786 SCIP_Real * SCIPgetLinearCoefsNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9561 Definition: type_nlpi.h:63 Definition: type_expr.h:49 SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand) Definition: intervalarith.c:528 SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar) Definition: scip.c:17159 static void propagateBoundsGetQuadActivity(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_Real intervalinfty, SCIP_Real *minquadactivity, SCIP_Real *maxquadactivity, int *minactivityinf, int *maxactivityinf, SCIP_INTERVAL *quadactcontr) Definition: cons_quadratic.c:9637 int SCIPgetNLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13634 static SCIP_RETCODE addLinearizationCuts(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *ref, SCIP_Bool *separatedlpsol, SCIP_Real minefficacy) Definition: cons_quadratic.c:8415 Definition: type_result.h:35 void SCIPaddSquareSecant(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real lb, SCIP_Real ub, SCIP_Real refpoint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success) Definition: cons_quadratic.c:6347 Definition: struct_cons.h:36 interval arithmetics for provable bounds static SCIP_RETCODE removeFixedVariables(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:2769 void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant) Definition: intervalarith.c:493 #define SCIPfreeBlockMemoryArrayNull(scip, ptr, num) Definition: scip.h:20403 SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19592 static SCIP_RETCODE generateCutSol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_SOL *refsol, SCIP_SIDETYPE violside, SCIP_ROW **row, SCIP_Real *efficacy, SCIP_Bool checkcurvmultivar, SCIP_Real minefficacy) Definition: cons_quadratic.c:8009 Definition: struct_cons.h:116 Definition: type_retcode.h:42 SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval) Definition: intervalarith.c:451 SCIP_RETCODE SCIPcheckCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_RESULT *result) Definition: scip.c:25857 SCIP_RETCODE SCIPnlpiAddVars(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nvars, const SCIP_Real *lbs, const SCIP_Real *ubs, const char **varnames) Definition: nlpi.c:250 static SCIP_DECL_CONSDELETE(consDeleteQuadratic) Definition: cons_quadratic.c:11099 SCIP_RETCODE SCIPchgRhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs) Definition: cons_quadratic.c:14090 Definition: type_expr.h:50 Definition: type_lp.h:47 static SCIP_RETCODE presolveUpgrade(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Bool *upgraded, int *nupgdconss, int *naddconss, SCIP_PRESOLTIMING presoltiming) Definition: cons_quadratic.c:3904 static SCIP_RETCODE catchQuadVarEvents(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons, int quadvarpos) Definition: cons_quadratic.c:391 Definition: type_set.h:44 SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming) Definition: scip.c:5496 SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row) Definition: scip.c:28138 Definition: type_result.h:36 SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub) Definition: scip.c:19783 SCIP_RETCODE SCIPnlpiSetIntPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, int ival) Definition: nlpi.c:633 SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos) SCIP_RETCODE SCIPnlpiCreateProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem, const char *name) Definition: nlpi.c:211 static SCIP_DECL_CONSPRESOL(consPresolQuadratic) Definition: cons_quadratic.c:11842 Definition: cons_quadratic.c:176 SCIP_RETCODE SCIPchgSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:14300 constraint handler for quadratic constraints SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre))) Definition: scip.c:5472 #define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum) Definition: scip.h:20391 static SCIP_RETCODE generateCutFactorable(SCIP *scip, SCIP_CONS *cons, SCIP_SIDETYPE violside, SCIP_Real *ref, SCIP_Real *cutcoef, SCIP_Real *cutlhs, SCIP_Real *cutrhs, SCIP_Bool *islocal, SCIP_Bool *success, char *name) Definition: cons_quadratic.c:5260 SCIP_RETCODE SCIPfindQuadVarTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, int *pos) Definition: cons_quadratic.c:13718 SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing) Definition: var.c:17265 SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13816 SCIP_RETCODE SCIPaddLinearVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:13378 Definition: type_set.h:41 Definition: type_retcode.h:33 struct SCIP_QuadVarEventData SCIP_QUADVAREVENTDATA Definition: cons_quadratic.h:71 static SCIP_RETCODE computeViolations(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_CONS **maxviolcon) Definition: cons_quadratic.c:5107 SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming) Definition: scip.c:5261 SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata) Definition: scip.c:5161 Definition: type_result.h:42 void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value) Definition: intervalarith.c:467 SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss) Definition: heur_subnlp.c:2224 static SCIP_RETCODE computeReferencePointGauge(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SOL *refsol, SCIP_Real **ref, SCIP_Bool *success) Definition: cons_quadratic.c:7903 SCIP_VAR ** SCIPgetLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13648 SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41554 SCIP_EXPRGRAPHNODE * SCIPgetExprgraphNodeNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9612 Definition: struct_heur.h:75 SCIP_RETCODE SCIPgetActivityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *activity) Definition: cons_quadratic.c:14173 Definition: type_lp.h:34 SCIP_RETCODE SCIPsetConshdlrDisable(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDISABLE((*consdisable))) Definition: scip.c:5695 Definition: type_retcode.h:34 static SCIP_RETCODE consdataEnsureAdjBilinSize(SCIP *scip, SCIP_QUADVARTERM *quadvarterm, int num) Definition: cons_quadratic.c:1087 static SCIP_RETCODE proposeFeasibleSolution(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool *success) Definition: cons_quadratic.c:10440 SCIP_Real SCIPexprgraphGetNodeQuadraticConstant(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12879 Ipopt NLP interface. SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible) Definition: scip.c:22668 static SCIP_RETCODE computeInteriorPoint(SCIP *scip, SCIP_CONS *cons, char method, SCIP_Bool *success) Definition: cons_quadratic.c:7212 SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20259 static SCIP_RETCODE propagateBoundsTightenVarUb(SCIP *scip, SCIP_CONS *cons, SCIP_Real intervalinfty, SCIP_VAR *var, SCIP_Real bnd, SCIP_RESULT *result, int *nchgbds) Definition: cons_quadratic.c:9303 SCIP_RETCODE SCIPaddLinearCoefsToNlRow(SCIP *scip, SCIP_NLROW *nlrow, int nvars, SCIP_VAR **vars, SCIP_Real *vals) Definition: scip.c:29574 SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: scip.c:24759 SCIP_Bool SCIPisSumLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41427 static SCIP_DECL_CONSINITLP(consInitlpQuadratic) Definition: cons_quadratic.c:11173 static SCIP_RETCODE presolveDisaggregate(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, int *naddconss) Definition: cons_quadratic.c:4166 SCIP_Bool SCIPexprgraphAreAllNodeChildrenVars(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:14365 static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyQuadratic) Definition: cons_quadratic.c:10771 Definition: type_expr.h:37 Definition: type_var.h:55 SCIP_RETCODE SCIPnlpiSetObjective(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nlins, const int *lininds, const SCIP_Real *linvals, int nquadelems, const SCIP_QUADELEM *quadelems, const int *exprvaridxs, const SCIP_EXPRTREE *exprtree, const SCIP_Real constant) Definition: nlpi.c:300 static SCIP_RETCODE computeGauge(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons) Definition: cons_quadratic.c:7587 SCIP_RETCODE SCIPgetFeasibilityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *feasibility) Definition: cons_quadratic.c:14132 SCIP_RETCODE SCIPcreateConsBasicQuadratic(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs) Definition: cons_quadratic.c:13225 constraint handler for nonlinear constraints Definition: type_var.h:54 SCIP_Bool SCIPhaveVarsCommonClique(SCIP *scip, SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics) Definition: scip.c:22152 void SCIPintervalSolveBivariateQuadExpressionAllScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real ax, SCIP_Real ay, SCIP_Real axy, SCIP_Real bx, SCIP_Real by, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds, SCIP_INTERVAL ybnds) Definition: intervalarith.c:3278 SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr) Definition: misc.c:8240 Definition: struct_lp.h:189 static SCIP_DECL_CONSEXITSOL(consExitsolQuadratic) Definition: cons_quadratic.c:11041 static SCIP_RETCODE replaceByLinearConstraints(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool *addedcons, SCIP_Bool *reduceddom, SCIP_Bool *infeasible) Definition: cons_quadratic.c:9063 SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol) Definition: scip.c:33881 static SCIP_RETCODE registerLargeLPValueVariableForBranching(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_VAR **brvar) Definition: cons_quadratic.c:9011 methods for debugging Definition: type_set.h:38 static void consdataSortLinearVars(SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:1358 Definition: cons_quadratic.h:92 SCIP_Real * SCIPgetCoefsLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13662 Definition: type_set.h:39 Definition: struct_expr.h:115 int SCIPgetNQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13675 SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow) Definition: cons_quadratic.c:13609 Definition: type_expr.h:56 Definition: type_var.h:41 Definition: type_var.h:45 void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:677 SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp))) Definition: scip.c:5580 void SCIPmarkRowNotRemovableLocal(SCIP *scip, SCIP_ROW *row) Definition: scip.c:28014 SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval) Definition: intervalarith.c:459 Definition: type_expr.h:62 SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem) Definition: nlpi.c:495 SCIP_RETCODE SCIPchgLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:14207 SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var) Definition: var.c:16747 static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata) Definition: cons_quadratic.c:1297 Constraint handler for linear constraints in their most general form, . static SCIP_RETCODE createNlRow(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:3080 static SCIP_Bool consdataCheckBilinTermsSort(SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:1573 SCIP_RETCODE SCIPincSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real incval) Definition: scip.c:34550 Definition: type_nlpi.h:74 void * SCIPexprgraphGetNodeVar(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12808 SCIP_RETCODE SCIPparseVarsPolynomial(SCIP *scip, const char *str, SCIP_VAR ****monomialvars, SCIP_Real ***monomialexps, SCIP_Real **monomialcoefs, int **monomialnvars, int *nmonomials, char **endptr, SCIP_Bool *success) Definition: scip.c:16526 Definition: type_expr.h:61 static void generateCutLTIcomputeCoefs(SCIP *scip, SCIP_Real xl, SCIP_Real xu, SCIP_Real x0, SCIP_Real yl, SCIP_Real yu, SCIP_Real y0_, SCIP_Real wl, SCIP_Real wu, SCIP_Real w0, SCIP_Real *cx, SCIP_Real *cy, SCIP_Real *cw, SCIP_Real *c0, SCIP_Bool *success) Definition: cons_quadratic.c:5656 void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...) Definition: scip.c:1270 static SCIP_Bool generateCutLTIfindIntersection(SCIP *scip, SCIP_Real x0, SCIP_Real y0_, SCIP_Real x1, SCIP_Real y1_, SCIP_Real wl, SCIP_Real wu, SCIP_Real *xl, SCIP_Real *yl, SCIP_Real *xu, SCIP_Real *yu) Definition: cons_quadratic.c:5476 SCIP_Real * SCIPexprgraphGetNodeQuadraticLinearCoefs(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12891 SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos) Definition: scip.c:36278 SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete))) Definition: scip.c:5534 Definition: type_set.h:34 Definition: type_lp.h:36 SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol))) Definition: scip.c:5400 SCIP_RETCODE SCIPupdateStartpointHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *solcand, SCIP_Real violation) Definition: heur_subnlp.c:2258 static SCIP_RETCODE addBilinearTerm(SCIP *scip, SCIP_CONS *cons, int var1pos, int var2pos, SCIP_Real coef) Definition: cons_quadratic.c:2326 SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos) Definition: scip.c:36198 static void consdataMoveQuadVarTerm(SCIP_CONSDATA *consdata, int oldpos, int newpos) Definition: cons_quadratic.c:1707 SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint))) Definition: scip.c:5741 void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len) Definition: misc.c:3824 Definition: type_expr.h:77 static SCIP_RETCODE consdataCreateEmpty(SCIP *scip, SCIP_CONSDATA **consdata) Definition: cons_quadratic.c:1137 static SCIP_DECL_CONSGETNVARS(consGetNVarsQuadratic) Definition: cons_quadratic.c:12811 Definition: type_nlpi.h:61 SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow) Definition: scip.c:29459 void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...) Definition: scip.c:1253 SCIP_Real SCIPintervalQuadUpperBound(SCIP_Real infinity, SCIP_Real a, SCIP_INTERVAL b_, SCIP_INTERVAL x) Definition: intervalarith.c:2680 void SCIPaddBilinMcCormick(SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success) Definition: cons_quadratic.c:6442 static SCIP_RETCODE dropVarEvents(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons) Definition: cons_quadratic.c:518 static SCIP_DECL_CONSGETVARS(consGetVarsQuadratic) Definition: cons_quadratic.c:12780 int SCIPgetNBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13736 SCIP_RETCODE SCIPcreateConsAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_and.c:4922 SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_linear.c:16236 static SCIP_RETCODE unlockLinearVariable(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:590 void SCIPintervalSetRoundingModeUpwards(void) Definition: intervalarith.c:398 SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol))) Definition: scip.c:5424 static SCIP_RETCODE generateCutLTI(SCIP *scip, SCIP_CONS *cons, SCIP_SIDETYPE violside, SCIP_Real *ref, SCIP_SOL *sol, SCIP_Real **cutcoeflin, SCIP_Real *cutcoefquad, SCIP_Real *cutlhs, SCIP_Real *cutrhs, SCIP_Bool *islocal, SCIP_Bool *success, char *name) Definition: cons_quadratic.c:6015 Definition: type_result.h:43 NLP local search primal heuristic using sub-SCIPs. SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41541 SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19519 void SCIPfreeParseVarsPolynomialData(SCIP *scip, SCIP_VAR ****monomialvars, SCIP_Real ***monomialexps, SCIP_Real **monomialcoefs, int **monomialnvars, int nmonomials) Definition: scip.c:16878 Definition: type_expr.h:69 SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3626 SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20365 Definition: type_expr.h:52 void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2) Definition: intervalarith.c:1102 Definition: type_lp.h:56 SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable) Definition: scip.c:27587 SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur) Definition: scip.c:33654 Definition: struct_nlp.h:62 SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file) Definition: scip.c:28321 SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41567 static SCIP_RETCODE checkFactorable(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:4686 SCIP_RETCODE SCIPincludeQuadconsUpgrade(SCIP *scip, SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), int priority, SCIP_Bool active, const char *conshdlrname) Definition: cons_quadratic.c:12975 #define SCIPduplicateBlockMemoryArray(scip, ptr, source, num) Definition: scip.h:20397 SCIP_RETCODE SCIPnlpiAddConstraints(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nconss, const SCIP_Real *lhss, const SCIP_Real *rhss, const int *nlininds, int *const *lininds, SCIP_Real *const *linvals, const int *nquadelems, SCIP_QUADELEM *const *quadelems, int *const *exprvaridxs, SCIP_EXPRTREE *const *exprtrees, const char **names) Definition: nlpi.c:268 SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeChildren(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12726 void SCIPsortPtrReal(void **ptrarray, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_RETCODE SCIPchgBilinCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef) Definition: cons_quadratic.c:14369 void SCIPsortInt(int *intarray, int len) SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol) Definition: scip.c:28722 static SCIP_RETCODE propagateBoundsTightenVarLb(SCIP *scip, SCIP_CONS *cons, SCIP_Real intervalinfty, SCIP_VAR *var, SCIP_Real bnd, SCIP_RESULT *result, int *nchgbds) Definition: cons_quadratic.c:9242 static SCIP_RETCODE delLinearCoefPos(SCIP *scip, SCIP_CONS *cons, int pos) Definition: cons_quadratic.c:1828 static SCIP_RETCODE consdataEnsureBilinSize(SCIP *scip, SCIP_CONSDATA *consdata, int num) Definition: cons_quadratic.c:1112 Definition: type_retcode.h:45 Definition: type_expr.h:73 Definition: type_expr.h:54 SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb) Definition: scip.c:19751 Definition: type_set.h:42 Definition: struct_expr.h:154 SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit))) Definition: scip.c:5376 SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup) Definition: scip.c:19465 SCIP_RETCODE SCIPcreateConsQuadratic2(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadvarterms, SCIP_QUADVARTERM *quadvarterms, int nbilinterms, SCIP_BILINTERM *bilinterms, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable) Definition: cons_quadratic.c:13256 SCIP_RETCODE SCIPaddSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:13486 SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41891 void SCIPintervalMulInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:843 Definition: type_nlpi.h:62 void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:784 Definition: type_result.h:45 SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate) Definition: scip.c:33311 static SCIP_RETCODE addLinearCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:1737 SCIP_RETCODE SCIPaddConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_NODE *validnode) Definition: scip.c:12036 Definition: type_result.h:46 SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing) Definition: var.c:17279 static SCIP_RETCODE delQuadVarTermPos(SCIP *scip, SCIP_CONS *cons, int pos) Definition: cons_quadratic.c:2086 SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image) Definition: misc.c:2089 static SCIP_RETCODE registerBranchingCandidatesGap(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int *nnotify) Definition: cons_quadratic.c:8587 static SCIP_RETCODE presolveDisaggregateMarkComponent(SCIP *scip, SCIP_CONSDATA *consdata, int quadvaridx, SCIP_HASHMAP *var2component, int componentnr) Definition: cons_quadratic.c:4120 SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13762 static SCIP_RETCODE propagateBounds(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_RESULT *result, int *nchgbds) Definition: cons_quadratic.c:10306 int SCIPexprgraphGetNodeQuadraticNQuadElements(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12915 Definition: type_retcode.h:43 Definition: type_expr.h:48 void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2) Definition: intervalarith.c:704 SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3598 SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars))) Definition: scip.c:5810 static SCIP_RETCODE consdataFindQuadVarTerm(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR *var, int *pos) Definition: cons_quadratic.c:1501 SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void) Definition: intervalarith.c:196 SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2) Definition: misc.c:7078 static SCIP_RETCODE mergeAndCleanQuadVarTerms(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:2527 Definition: type_set.h:36 Definition: nlpi_ipopt.cpp:124 SCIP_RETCODE LapackDsyev(SCIP_Bool computeeigenvectors, int N, SCIP_Real *a, SCIP_Real *w) Definition: nlpi_ipopt.cpp:2793 SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13774 static SCIP_RETCODE consdataEnsureLinearVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num) Definition: cons_quadratic.c:1032 void SCIPintervalSetRoundingModeDownwards(void) Definition: intervalarith.c:390 Definition: type_result.h:39 static SCIP_DECL_CONSDISABLE(consDisableQuadratic) Definition: cons_quadratic.c:12212 Definition: struct_event.h:185 SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem) Definition: nlpi.c:509 SCIP_Bool SCIPintervalIsSubsetEQ(SCIP_Real infinity, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:555 SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos) Definition: scip.c:36164 SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13799 void SCIPintervalSolveUnivariateQuadExpressionPositive(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs) Definition: intervalarith.c:2810 static SCIP_RETCODE catchLinearVarEvents(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons, int linvarpos) Definition: cons_quadratic.c:272 Definition: type_expr.h:46 Definition: type_expr.h:39 static SCIP_RETCODE generateCutUnboundedLP(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SIDETYPE violside, SCIP_ROW **row, SCIP_Real *rowrayprod, SCIP_Bool checkcurvmultivar) Definition: cons_quadratic.c:8096 void SCIPintervalQuad(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL xrng) Definition: intervalarith.c:2775 SCIP_QUADELEM * SCIPexprgraphGetNodeQuadraticQuadElements(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12903 Definition: struct_nlpi.h:35 Definition: type_var.h:56 |