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 { 1001 /* if an integer variable x with a x^2 is tightened to [0,1], then we can replace the x^2 by x, which is done in mergeAndCleanQuadVarTerms() 1003 * unfortunately, SCIP does not have an eventtype for vartype changes (nor do they always count as presolve reductions) and the bounds are 1004 * not updated yet when this event is processed, so we cannot use SCIPvarIsBinary here to check if the tightened integer variable will be binary 1006 if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING && SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER && quadvarterm->sqrcoef != 0.0 && quadvarterm->nadjbilin == 0 && 1007 ( ((eventtype & SCIP_EVENTTYPE_LBTIGHTENED) && SCIPeventGetNewbound(event) > -0.5 && SCIPvarGetUbGlobal(var) < 1.5) || 1008 ((eventtype & SCIP_EVENTTYPE_UBTIGHTENED) && SCIPeventGetNewbound(event) < 1.5 && SCIPvarGetLbGlobal(var) > -0.5) ) ) 1021 consdataUpdateLinearActivityLbChange(scip, consdata, consdata->lincoefs[varidx], SCIPeventGetOldbound(event), SCIPeventGetNewbound(event)); 1023 consdataUpdateLinearActivityUbChange(scip, consdata, consdata->lincoefs[varidx], SCIPeventGetOldbound(event), SCIPeventGetNewbound(event)); 1039 /* 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 */ 1040 if( SCIPvarIsBinary(SCIPeventGetVar(event)) && consdata->quadvarterms[-varidx-1].nadjbilin > 0 ) 1065 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->linvars, consdata->linvarssize, newsize) ); 1066 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->lincoefs, consdata->linvarssize, newsize) ); 1069 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->lineventdata, consdata->linvarssize, newsize) ); 1095 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->quadvarterms, consdata->quadvarssize, newsize) ); 1120 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &quadvarterm->adjbilin, quadvarterm->adjbilinsize, newsize) ); 1145 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->bilinterms, consdata->bilintermssize, newsize) ); 1256 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->quadvarterms, quadvarterms, nquadvars) ); 1263 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->quadvarterms[i].adjbilin, quadvarterms[i].adjbilin, quadvarterms[i].nadjbilin) ); 1291 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bilinterms, bilinterms, nbilinterms) ); 1335 assert((*consdata)->lineventdata == NULL || (*consdata)->lineventdata[i] == NULL); /* variable events should have been dropped earlier */ 1349 assert((*consdata)->quadvarterms[i].eventdata == NULL); /* variable events should have been dropped earlier */ 1350 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->quadvarterms[i].adjbilin, (*consdata)->quadvarterms[i].adjbilinsize); 1393 SCIPsortPtrReal((void**)consdata->linvars, consdata->lincoefs, SCIPvarComp, consdata->nlinvars); 1399 SCIPsortPtrPtrReal((void**)consdata->linvars, (void**)consdata->lineventdata, consdata->lincoefs, SCIPvarComp, consdata->nlinvars); 1411 /** returns the position of variable in the linear coefficients array of a constraint, or -1 if not found */ 1428 if( !SCIPsortedvecFindPtr((void**)consdata->linvars, SCIPvarComp, (void*)var, consdata->nlinvars, &pos) ) 1435 /** index comparison method for quadratic variable terms: compares two indices of the quadratic variable set in the quadratic constraint */ 1517 /** returns the position of variable in the quadratic variable terms array of a constraint, or -1 if not found */ 1523 int* pos /**< buffer where to store position of var in quadvarterms array, or -1 if not found */ 1570 /** index comparison method for bilinear terms: compares two index pairs of the bilinear term set in the quadratic constraint */ 1837 consdata->linvarssorted = consdata->linvarssorted && (SCIPvarCompare(consdata->linvars[consdata->nlinvars-2], consdata->linvars[consdata->nlinvars-1]) == -1); 1838 /* always set too FALSE since the new linear variable should be checked if already existing as quad var term */ 2093 (SCIPvarCompare(consdata->quadvarterms[consdata->nquadvars-2].var, consdata->quadvarterms[consdata->nquadvars-1].var) == -1); 2094 /* also set to FALSE if nquadvars == 1, since the new variable should be checked for linearity and other stuff in mergeAndClean ... */ 2147 SCIPfreeBlockMemoryArrayNull(scip, &consdata->quadvarterms[pos].adjbilin, consdata->quadvarterms[pos].adjbilinsize); 2173 * Allows to replace x by coef*y+offset, thereby maintaining linear and square coefficients and bilinear terms. 2265 * thus, for now we just set the coefficient to 0.0 and clear in later when the bilinear terms are merged */ 2378 if( SCIPvarCompare(consdata->quadvarterms[var1pos].var, consdata->quadvarterms[var2pos].var) < 0 ) 2392 SCIPerrorMessage("tried to add bilinear term where both variables are the same, but appear at different positions in quadvarterms array\n"); 2397 SCIP_CALL( consdataEnsureAdjBilinSize(scip, &consdata->quadvarterms[var1pos], consdata->quadvarterms[var1pos].nadjbilin + 1) ); 2398 SCIP_CALL( consdataEnsureAdjBilinSize(scip, &consdata->quadvarterms[var2pos], consdata->quadvarterms[var2pos].nadjbilin + 1) ); 2400 consdata->quadvarterms[var1pos].adjbilin[consdata->quadvarterms[var1pos].nadjbilin] = consdata->nbilinterms; 2401 consdata->quadvarterms[var2pos].adjbilin[consdata->quadvarterms[var2pos].nadjbilin] = consdata->nbilinterms; 2423 /* we have to take care of the bilinear term in mergeAndCleanBilinearTerms() if the coefficient is zero */ 2542 * also replaces squares of binary variables by the binary variables, i.e., adds sqrcoef to lincoef. 2572 /* make sure quad var terms are sorted (do this in every round, since we may move variables around) */ 2577 for( j = i+1; j < consdata->nquadvars && consdata->quadvarterms[j].var == quadvarterm->var; ++j ) 2585 SCIP_CALL( consdataEnsureAdjBilinSize(scip, quadvarterm, quadvarterm->nadjbilin + consdata->quadvarterms[j].nadjbilin) ); 2586 BMScopyMemoryArray(&quadvarterm->adjbilin[quadvarterm->nadjbilin], consdata->quadvarterms[j].adjbilin, consdata->quadvarterms[j].nadjbilin); /*lint !e866*/ 2604 if( quadvarterm->sqrcoef != 0.0 && SCIPvarIsBinary(quadvarterm->var) && quadvarterm->nadjbilin == 0 ) 2606 SCIPdebugMessage("replace square of binary variable by itself: <%s>^2 --> <%s>\n", SCIPvarGetName(quadvarterm->var), SCIPvarGetName(quadvarterm->var)); 2640 /** merges entries with same linear variable into one entry and cleans up entries with coefficient 0.0 */ 2670 /* make sure linear variables are sorted (do this in every round, since we may move variables around) */ 2687 /* add newcoef to linear coefficient of quadratic variable and mark linear variable as to delete */ 2712 /** merges bilinear terms with same variables into a single term, removes bilinear terms with coefficient 0.0 */ 2756 for( j = i+1; j < consdata->nbilinterms && bilinterm->var1 == consdata->bilinterms[j].var1 && bilinterm->var2 == consdata->bilinterms[j].var2; ++j ) 2829 SCIPdebugMessage(" linear term %g*<%s> is replaced by %g * <%s> + %g\n", consdata->lincoefs[i], SCIPvarGetName(consdata->linvars[i]), 2902 SCIPdebugMessage(" quadratic variable <%s> with status %d is replaced by %g * <%s> + %g\n", SCIPvarGetName(consdata->quadvarterms[i].var), 2908 /* if not fixed to 0.0, add to linear coefs of vars in bilinear terms, and deal with linear and square term as constant */ 2927 offset = consdata->quadvarterms[i].lincoef * offset + consdata->quadvarterms[i].sqrcoef * offset * offset; 2935 SCIP_CALL( removeBilinearTermsPos(scip, cons, consdata->quadvarterms[i].nadjbilin, consdata->quadvarterms[i].adjbilin) ); 2945 /* if GetProbvar gave an active variable, replace the quad var term so that it uses the new variable */ 2955 /* if GetProbVar gave a multi-aggregated variable, add new quad var terms and new bilinear terms 3007 SCIP_CALL( consdataEnsureBilinSize(scip, consdata, consdata->nquadvars + (scoef != 0.0 ? (naggrs * (naggrs-1))/2 : 0) + consdata->quadvarterms[j].nadjbilin * naggrs) ); 3028 /* this is not efficient, but we cannot sort the quadratic terms here, since we currently iterate over them */ 3044 SCIP_CALL( addBilinearTerm(scip, cons, nquadtermsold + j, var2pos, bilinterm->coef * coef * aggrscalars[j]) ); 3052 SCIP_CALL( removeBilinearTermsPos(scip, cons, consdata->quadvarterms[i].nadjbilin, consdata->quadvarterms[i].adjbilin) ); 3076 * in this case, we want the linear variable to be removed, which happens in mergeAndCleanLinearVars 3109 SCIP_VAR** quadlinvars; /* variables of linear terms using variables that are in quadratic terms */ 3110 SCIP_Real* quadlincoefs; /* coefficients of linear terms using variables that are in quadratic terms */ 3172 * 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 */ 3204 SCIP_CALL( SCIPaddLinearCoefsToNlRow(scip, consdata->nlrow, nquadlinterms, quadlinvars, quadlincoefs) ); 3239 if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) && consdata->nlinvars == 0 && consdata->nquadvars == 2 && 3240 ((SCIPvarIsBinary(consdata->quadvarterms[0].var) && consdata->quadvarterms[1].sqrcoef == 0.0) || 3241 (SCIPvarIsBinary(consdata->quadvarterms[1].var) && consdata->quadvarterms[0].sqrcoef == 0.0)) ) 3256 * 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 3259 binvaridx = (SCIPvarIsBinary(consdata->quadvarterms[0].var) && consdata->quadvarterms[1].sqrcoef == 0.0) ? 0 : 1; 3267 assert(consdata->nbilinterms <= 1); /* should actually be 1, since constraint is otherwise linear */ 3272 SCIPdebugMessage("<%s> = 0 -> %g*<%s> = %g and <%s> = 1 -> %g*<%s> = %g\n", SCIPvarGetName(x), b, SCIPvarGetName(y), consdata->rhs, 3274 SCIPdebugMessage("=> attempt aggregation <%s> = %g*<%s> + %g\n", SCIPvarGetName(y), (consdata->rhs-a)/(b+c) - consdata->rhs/b, 3277 SCIP_CALL( SCIPaggregateVars(scip, x, y, (consdata->rhs-a)/(b+c) - consdata->rhs/b, -1.0, -consdata->rhs/b, &infeasible, redundant, &aggregated) ); 3300 * 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. 3353 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "prod%s_%s_%s", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]), SCIPconsGetName(cons)); 3355 SCIPvarIsInitial(vars[0]) || SCIPvarIsInitial(vars[1]), SCIPvarIsRemovable(vars[0]) && SCIPvarIsRemovable(vars[1]), NULL, NULL, NULL, NULL, NULL) ); 3369 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%sAND%s", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1])); 3397 /** gets bounds of variable y if x takes a certain value; checks whether x = xval has implications on y */ 3418 SCIPintervalSetBounds(resultant, MIN(SCIPvarGetLbGlobal(y), SCIPvarGetUbGlobal(y)), MAX(SCIPvarGetLbGlobal(y), SCIPvarGetUbGlobal(y))); /*lint !e666 */ 3479 /** Reformulates products of binary times bounded continuous variables as system of linear inequalities (plus auxiliary variable). 3482 * 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. 3484 * 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. 3485 * For each product of linear term of length at most maxnrvar with y, an auxiliary z and linear inequalities are added. 3487 * If y is a binary variable, the AND constraint \f$ z = x \wedge y \f$ may be added instead of linear constraints. 3557 SCIP_CALL( SCIPreallocBufferArray(scip, &xvars, MIN(maxnrvar, nbilinterms)+2) ); /* add 2 for later use when creating linear constraints */ 3567 /* 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) 3595 if( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(bvar)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(bvar)) ) 3614 if( SCIPfeastol(scip) * REALABS(act0.inf) >= conshdlrdata->binreformmaxcoef || SCIPfeastol(scip) * REALABS(act0.sup) >= conshdlrdata->binreformmaxcoef ) 3617 bilincoef, SCIPvarGetName(y), SCIPvarGetName(bvar), SCIPintervalGetInf(act0), SCIPintervalGetSup(act0), SCIPvarGetName(y)); 3620 if( SCIPfeastol(scip) * REALABS(act1.inf) >= conshdlrdata->binreformmaxcoef || SCIPfeastol(scip) * REALABS(act1.sup) >= conshdlrdata->binreformmaxcoef ) 3623 bilincoef, SCIPvarGetName(y), SCIPvarGetName(bvar), SCIPintervalGetInf(act1), SCIPintervalGetSup(act1), SCIPvarGetName(y)); 3627 SCIPfeastol(scip) * MAX(REALABS(act0.inf), REALABS(act0.sup)) / MIN(REALABS(act0.inf), REALABS(act0.sup)) >= conshdlrdata->binreformmaxcoef ) 3629 SCIPdebugMessage("skip reform of %g<%s><%s> due to huge activity ratio %g for <%s> = 0.0\n", bilincoef, SCIPvarGetName(y), SCIPvarGetName(bvar), 3630 MAX(REALABS(act0.inf), REALABS(act0.sup)) / MIN(REALABS(act0.inf), REALABS(act0.sup)), SCIPvarGetName(y)); 3634 SCIPfeastol(scip) * MAX(REALABS(act1.inf), REALABS(act1.sup)) / MIN(REALABS(act1.inf), REALABS(act1.sup)) >= conshdlrdata->binreformmaxcoef ) 3636 SCIPdebugMessage("skip reform of %g<%s><%s> due to huge activity ratio %g for <%s> = 0.0\n", bilincoef, SCIPvarGetName(y), SCIPvarGetName(bvar), 3637 MAX(REALABS(act1.inf), REALABS(act1.sup)) / MIN(REALABS(act1.inf), REALABS(act1.sup)), SCIPvarGetName(y)); 3656 integral &= (SCIPvarGetType(bvar) < SCIP_VARTYPE_CONTINUOUS) && SCIPisIntegral(scip, bilincoef); /*lint !e514 */ 3688 SCIPdebugMessage("got different bounds for y = 0: [%g, %g] and y = 1: [%g, %g]\n", xbndszero.inf, xbndszero.sup, xbndsone.inf, xbndsone.sup); 3696 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "prod%s_%s_%s", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3712 /* add constraint z = x and y; need to be enforced, as it is not redundant w.r.t. existing constraints */ 3714 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%sAND%s_%s", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3734 /* product of binary variable with more than one binary or with continuous variables or with binary and user 3739 * if all coefficients are integral, take a value that preserves integrality (-> gcd), so we can make the auxiliary variable impl. integer 3748 /* scaling by the only coefficient gives auxiliary variable = x * y, which thus will be implicit integral provided y is not continuous */ 3766 /* if x-term is always negative for y = 1, negate scale so we get a positive auxiliary variable; maybe this is better sometimes? */ 3770 SCIPdebugMessage("binary reformulation using scale %g, nxvars = %d, integral = %u\n", scale, nxvars, integral); 3781 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "prod%s_%s_%s", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3783 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "prod%s_%s_more_%s", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3784 SCIP_CALL( SCIPcreateVar(scip, &auxvar, name, MIN(0., SCIPintervalGetInf(xbndsone)), MAX(0., SCIPintervalGetSup(xbndsone)), 3817 * it seems to be advantageous to make the varbound constraints initial and the linear constraints not initial 3818 * maybe because it is more likely that a binary variable takes value 0 instead of 1, and thus the varbound constraints 3824 /* add 0 <= z - xbndsone.inf * y constraint (as varbound constraint), need to be enforced as not redundant */ 3826 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s_%s_1", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3828 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s*more_%s_1", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3829 SCIP_CALL( SCIPcreateConsVarbound(scip, &auxcons, name, auxvar, y, -SCIPintervalGetInf(xbndsone), 0.0, SCIPinfinity(scip), 3842 /* add z - xbndsone.sup * y <= 0 constraint (as varbound constraint), need to be enforced as not redundant */ 3844 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s_%s_2", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3846 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s*more_%s_2", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3847 SCIP_CALL( SCIPcreateConsVarbound(scip, &auxcons, name, auxvar, y, -SCIPintervalGetSup(xbndsone), -SCIPinfinity(scip), 0.0, 3859 /* add xbndszero.inf <= sum_i a_i*x_i + xbndszero.inf * y - z constraint, need to be enforced as not redundant */ 3866 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s_%s_3", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3868 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s*more_%s_3", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3869 SCIP_CALL( SCIPcreateConsLinear(scip, &auxcons, name, nxvars+2, xvars, xcoef, SCIPintervalGetInf(xbndszero), SCIPinfinity(scip), 3880 /* add sum_i a_i*x_i + xbndszero.sup * y - z <= xbndszero.sup constraint, need to be enforced as not redundant */ 3884 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s_%s_4", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3886 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "linreform%s*%s*more_%s_4", SCIPvarGetName(y), SCIPvarGetName(xvars[0]), SCIPconsGetName(cons)); 3887 SCIP_CALL( SCIPcreateConsLinear(scip, &auxcons, name, nxvars+2, xvars, xcoef, -SCIPinfinity(scip), SCIPintervalGetSup(xbndszero), 3920 /** tries to automatically convert a quadratic constraint (or a part of it) into a more specific and more specialized constraint */ 3928 int* naddconss, /**< buffer to increase with number of additional constraints created during upgrade */ 4050 integral = integral && SCIPisRelEQ(scip, lb, ub) && SCIPisIntegral(scip, lincoef * lb + quadcoef * lb * lb); 4063 if( SCIPvarGetType(consdata->bilinterms[i].var1) < SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(consdata->bilinterms[i].var2) < SCIP_VARTYPE_CONTINUOUS ) 4074 SCIPdebugMessage(" binlin=%d binquad=%d intlin=%d intquad=%d impllin=%d implquad=%d contlin=%d contquad=%d integral=%u\n", 4118 /* count the first upgrade constraint as constraint upgrade and the remaining ones as added constraints */ 4173 consdata->bilinterms[quadvarterm->adjbilin[i]].var2 : consdata->bilinterms[quadvarterm->adjbilin[i]].var1; 4176 SCIP_CALL( presolveDisaggregateMarkComponent(scip, consdata, othervaridx, var2component, componentnr) ); 4182 /** for quadratic constraints that consists of a sum of quadratic terms, disaggregates the sum into a set of constraints by introducing auxiliary variables */ 4216 /* sort quadratic variable terms here, so we can later search in it without reordering the array */ 4220 * in other words, the number of components in the sparsity graph of the quadratic term matrix */ 4222 SCIP_CALL( SCIPhashmapCreate(&var2component, SCIPblkmem(scip), SCIPcalcHashtableSize(consdata->nquadvars)) ); 4235 * @todo we could still split the constraint into several while keeping the number of variables sharing several constraints as small as possible 4252 SCIP_CALL( SCIPcreateVar(scip, &auxvars[comp], name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, 4255 SCIP_CALL( SCIPcreateConsQuadratic2(scip, &auxconss[comp], name, 0, NULL, NULL, 0, NULL, 0, NULL, 4274 SCIP_CALL( SCIPaddQuadVarQuadratic(scip, auxconss[comp], consdata->quadvarterms[i].var, consdata->quadvarterms[i].lincoef, consdata->quadvarterms[i].sqrcoef) ); 4277 if( !SCIPisZero(scip, consdata->quadvarterms[i].lincoef) && ABS(consdata->quadvarterms[i].lincoef) < auxcoefs[comp] ) 4279 if( !SCIPisZero(scip, consdata->quadvarterms[i].sqrcoef) && ABS(consdata->quadvarterms[i].sqrcoef) < auxcoefs[comp] ) 4282 SCIPfreeBlockMemoryArray(scip, &consdata->quadvarterms[i].adjbilin, consdata->quadvarterms[i].adjbilinsize); 4291 assert(comp == (int)(size_t) SCIPhashmapGetImage(var2component, consdata->bilinterms[i].var2)); 4318 SCIPdebugMessage("add %d constraints for disaggregation of quadratic constraint <%s>\n", ncomponents, SCIPconsGetName(cons)); 4347 /** checks if there are bilinear terms x*y with a binary variable x and an implication x = {0,1} -> y = 0 4406 y = consdata->bilinterms[k].var1 == x ? consdata->bilinterms[k].var2 : consdata->bilinterms[k].var1; 4414 SCIPdebugMessage("remove bilinear term %g<%s><%s> from <%s> due to implication\n", consdata->bilinterms[k].coef, SCIPvarGetName(x), SCIPvarGetName(y), SCIPconsGetName(cons)); 4425 * we only move the coefficient to the linear coef of y here and mark the bilinterms as not merged */ 4426 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)); 4457 /** checks a quadratic constraint for convexity and/or concavity without checking multivariate functions */ 4463 SCIP_Bool checkmultivariate /**< whether curvature will be checked later on for multivariate functions */ 4482 SCIPdebugMessage("Checking curvature of constraint <%s> without multivariate functions\n", SCIPconsGetName(cons)); 4506 consdata->isconvex = consdata->isconvex && !SCIPisNegative(scip, consdata->quadvarterms[v].sqrcoef); 4507 consdata->isconcave = consdata->isconcave && !SCIPisPositive(scip, consdata->quadvarterms[v].sqrcoef); 4527 SCIP_Bool checkmultivariate /**< whether curvature should also be checked for multivariate functions */ 4561 SCIPdebugMessage("Checking curvature of constraint <%s> with multivariate functions\n", SCIPconsGetName(cons)); 4570 4 * consdata->quadvarterms[0].sqrcoef * consdata->quadvarterms[1].sqrcoef >= consdata->bilinterms[0].coef * consdata->bilinterms[0].coef; 4574 4 * consdata->quadvarterms[0].sqrcoef * consdata->quadvarterms[1].sqrcoef >= consdata->bilinterms[0].coef * consdata->bilinterms[0].coef; 4584 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "cons_quadratic - n is too large to check the curvature\n"); 4642 SCIPwarningMessage(scip, "Failed to compute eigenvalues of quadratic coefficient matrix of constraint %s. Assuming matrix is indefinite.\n", SCIPconsGetName(cons)); 4648 /* deconvexification reformulates a stricly convex quadratic function in binaries such that it becomes not-strictly convex 4650 * 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 4654 printf("cons <%s>[%g,%g] spectrum = [%g,%g]\n", SCIPconsGetName(cons), consdata->lhs, consdata->rhs, alleigval[0], alleigval[n-1]); 4667 printf("deconvexify cons <%s> by shifting hessian by %g\n", SCIPconsGetName(cons), alleigval[0]); 4677 printf("deconcavify cons <%s> by shifting hessian by %g\n", SCIPconsGetName(cons), alleigval[n-1]); 4693 consdata->iscurvchecked = TRUE; /* set to TRUE since it does not help to repeat this procedure again and again (that will not bring Ipopt in) */ 4702 /** check whether indefinite constraint function is factorable and store corresponding coefficients */ 4738 * compute an eigenvalue factorization of A and check if there are one positive and one negative eigenvalue 4739 * 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 4742 * we then store sigma1 v1^T - sigma2 v2^T as left factor coef, and sigma1 v1^T + sigma2 v2^T as right factor coef 4745 /* if we already know that there are only positive or only negative eigenvalues, then don't try */ 4790 SCIPdebugMessage("Failed to compute eigenvalues and eigenvectors of augmented quadratic form matrix for constraint <%s>.\n", SCIPconsGetName(cons)); 4816 SCIPdebugMessage("Augmented quadratic form of constraint <%s> is not factorable.\n", SCIPconsGetName(cons)); 4843 SCIPdebugMessage("constraint <%s> has factorable quadratic form: (%g", SCIPconsGetName(cons), consdata->factorleft[n-1]); 4847 SCIPdebugPrintf(" %+g<%s>", consdata->factorleft[i], SCIPvarGetName(consdata->quadvarterms[i].var)); 4853 SCIPdebugPrintf(" %+g<%s>", consdata->factorright[i], SCIPvarGetName(consdata->quadvarterms[i].var)); 4871 if( !SCIPisRelEQ(scip, consdata->factorleft[idx1] * consdata->factorright[idx2] + consdata->factorleft[idx2] * consdata->factorright[idx1], bilinterm->coef) ) 4881 if( !SCIPisRelEQ(scip, consdata->factorleft[i] * consdata->factorright[i], consdata->quadvarterms[i].sqrcoef) ) 4887 if( !SCIPisRelEQ(scip, consdata->factorleft[n-1] * consdata->factorright[i] + consdata->factorleft[i] * consdata->factorright[n-1], consdata->quadvarterms[i].lincoef) ) 4990 /* @todo Take better care of variables at +/- infinity: e.g., run instance waste in debug mode with a short timelimit (30s). */ 5006 /* project onto local box, in case the LP solution is slightly outside the bounds (which is not our job to enforce) */ 5009 /* 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 5033 /* project onto local box, in case the LP solution is slightly outside the bounds (which is not our job to enforce) */ 5036 /* 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 consdata->activity += (consdata->quadvarterms[j].lincoef + consdata->quadvarterms[j].sqrcoef * varval) * varval; 5053 /* project onto local box, in case the LP solution is slightly outside the bounds (which is not our job to enforce) */ 5056 #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 */ 5062 #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 */ 5131 SCIP_CONS** maxviolcon /**< buffer to store constraint with largest violation, or NULL if solution is feasible */ 5168 /** tries to compute cut for multleft * <coefleft, x'> * multright <= rhs / (multright * <coefright, x'>) where x'=(x,1) */ 5203 * 1 / multright*<coefright, x'> <= 1/minact + 1/maxact - 1/(minact * maxact) multright*<coefright, x'> 5207 * multright/rightminactivity + multright/rightmaxactivity - multright/(rightminactivity * rightmaxactivity) *<coefright, x'> 5210 * rhs / (multright * <coefright, x'>) <= rhs * multright * (1/rightminactivity + 1/rightmaxactivity - 1/(rightminactivity * rightmaxactivity) * <coefright, x'>) 5224 constant += rhs * multright * coefright[consdata->nquadvars] / (rightminactivity * rightmaxactivity); 5232 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_factorablesecant_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip)); 5240 * <= rhs / (multright * <coefright, ref'>) - rhs / (multright * <coefright, ref'>)^2 * (multright * <coefright, x'> - multright * <coefright, ref'>) 5241 * = 2*rhs / (multright * <coefright, ref'>) - rhs / (multright * <coefright, ref'>)^2 * (multright * <coefright, x'>) 5251 /* should not happen, since we checked activity of <coefright,x> before, and assume ref within bounds */ 5264 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_factorablelinearization_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip)); 5274 /** tries to generate a cut if constraint quadratic function is factorable and there are no linear variables 5275 * (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 5368 rightminactivity += consdata->factorright[i] * SCIPvarGetLbLocal(consdata->quadvarterms[i].var); 5375 rightminactivity += consdata->factorright[i] * SCIPvarGetUbLocal(consdata->quadvarterms[i].var); 5385 rightmaxactivity += consdata->factorright[i] * SCIPvarGetUbLocal(consdata->quadvarterms[i].var); 5392 rightmaxactivity += consdata->factorright[i] * SCIPvarGetLbLocal(consdata->quadvarterms[i].var); 5418 if( !SCIPisFeasPositive(scip, rightminactivity) && !SCIPisFeasNegative(scip, rightmaxactivity) ) 5426 /* write violated constraint as multleft * factorleft * multright * (multright * factorright) <= rhs 5435 generateCutFactorableDo(scip, cons, ref, multleft, consdata->factorleft, multright, consdata->factorright, rightminactivity, rightmaxactivity, rhs, cutcoef, cutrhs, islocal, success, name); 5437 else if( !SCIPisFeasPositive(scip, rightminactivity) && !SCIPisFeasNegative(scip, rightmaxactivity) ) 5444 /* write violated constraint as multleft * factorright * multright * (multright * factorleft) <= rhs 5453 generateCutFactorableDo(scip, cons, ref, multleft, consdata->factorright, multright, consdata->factorleft, leftminactivity, leftmaxactivity, rhs, cutcoef, cutrhs, islocal, success, name); 5456 (!SCIPisInfinity(scip, -rightminactivity) && !SCIPisInfinity(scip, rightmaxactivity) && rightmaxactivity - rightminactivity < leftmaxactivity - leftminactivity) ) 5458 /* both factors are bounded away from 0, but the right one has a smaller activity range, so divide by that one */ 5460 /* write violated constraint as multleft * factorleft * multright * (multright * factorright) <= rhs 5469 generateCutFactorableDo(scip, cons, ref, multleft, consdata->factorleft, multright, consdata->factorright, rightminactivity, rightmaxactivity, rhs, cutcoef, cutrhs, islocal, success, name); 5473 /* both factors are bounded away from 0, but the left one has a smaller activity range, so divide by that one */ 5475 /* write violated constraint as multleft * factorright * multright * (multright * factorleft) <= rhs 5484 generateCutFactorableDo(scip, cons, ref, multleft, consdata->factorright, multright, consdata->factorleft, leftminactivity, leftmaxactivity, rhs, cutcoef, cutrhs, islocal, success, name); 5490 /* finds intersections of a parametric line (x,y) = (x0,y0) + t [(x1,y1) - (x0,y0)] on curves x*y = wl and x*y = wu; 5618 * such that intersecting it with one of them (the first if whichuse is FALSE, the second otherwise) 5678 * The code is an adaptation of the methods in exprMul-upperHull.cpp in Couenne/stable/0.4 rev773, 5755 /* both variables have mixed sign (xl < 0 && xu > 0 && yl < 0 && yu > 0) and both xl*yl and xu*yu are feasible 5775 /* both variables have mixed sign (xl < 0 && xu > 0 && yl < 0 && yu > 0) and both xl*yu and xu*yl are feasible 5820 /* project refpoint into box not only for numerical reasons, but also due to preliminary bound tightening above */ 5844 if( generateCutLTIfindIntersection(scip, 0.0, 0.0, x0, y0_, wl, wu, &xlow, &ylow, &xupp, &yupp) ) 5851 /* Case 1: If both are outside of bounding box, either NW or SE, then McCormick is sufficient, so return */ 5855 /* There will be at least one cut. Define coefficients and rhs ---will have to change them back if (flipX || flipY) */ 5885 if( generateCutLTIfindIntersection(scip, xupp, yupp, x0, y0_, wl, SCIP_INVALID, &xlow, &ylow, NULL, NULL) ) 5919 if( generateCutLTIfindIntersection(scip, xlow, ylow, x0, y0_, SCIP_INVALID, wu, NULL, NULL, &xupp, &yupp) ) 5970 /* Nothing to find. Just separate two inequalities at the same point, just using different support */ 5988 /* find the intersection on the lower (upper) curve on the line through xLP and the upper (lower) point 5991 if( generateCutLTIfindIntersection(scip, xlow, ylow, x0, y0_, SCIP_INVALID, wu, NULL, NULL, &xupp2, &yupp2) || 5994 if( generateCutLTIfindIntersection(scip, xupp, yupp, x0, y0_, wl, SCIP_INVALID, &xlow2, &ylow2, NULL, NULL) || 6035 /** tries to generate a cut if constraint quadratic function is factorable and there are linear variables 6038 * Belotti, Miller, Namazifar, Lifted inequalities for bounded products of variables, SIAG/OPT Views-and-News 22:1, 2011 6047 SCIP_Real** cutcoeflin, /**< buffer to store pointer to array with coefficients for linear variables */ 6081 /* currently only separate LP solution or solutions given as SCIP_SOL, i.e., no cutgeneration during initlp */ 6206 rightminactivity += consdata->factorright[i] * SCIPvarGetLbLocal(consdata->quadvarterms[i].var); 6213 rightminactivity += consdata->factorright[i] * SCIPvarGetUbLocal(consdata->quadvarterms[i].var); 6223 rightmaxactivity += consdata->factorright[i] * SCIPvarGetUbLocal(consdata->quadvarterms[i].var); 6230 rightmaxactivity += consdata->factorright[i] * SCIPvarGetLbLocal(consdata->quadvarterms[i].var); 6236 /* if activities exceed "opposite" infinity, huge bounds seem to be involved, for which the below method is not prepared */ 6241 /* if any of the factors is essentially fixed, give up and do usual method (numerically less sensitive, I hope) */ 6242 if( SCIPisRelEQ(scip, leftminactivity, leftmaxactivity) || SCIPisRelEQ(scip, rightminactivity, rightmaxactivity) ) 6260 leftminactivity, leftmaxactivity, rightminactivity, rightmaxactivity, rhsminactivity, rhsmaxactivity, 6265 if( coefleft * leftrefactivity + coefright * rightrefactivity + coefrhs * rhsrefactivity >= *cutlhs ) 6273 * coefleft * leftfactor + coefright * rightfactor + coefrhs * w >= cutlhs, where conslhs - lincoefs <= w <= consrhs - lincoefs 6299 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lti_%d", SCIPconsGetName(cons), SCIPgetNLPs(scip)); 6354 consdata->quadvarterms[j].nadjbilin == 0 && SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS, &coef[j], &constant, success); 6370 SCIPaddBilinLinearization(scip, bilinterm->coef, ref[j], ref[var2pos], &coef[j], &coef[var2pos], &constant, success); 6376 SCIPdebugMessage("no success in linearization of <%s> in reference point\n", SCIPconsGetName(cons)); 6391 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_side%d_linearization_%d", SCIPconsGetName(cons), violside, SCIPgetNLPs(scip)); 6448 if( (violside == SCIP_SIDETYPE_LEFT && sqrcoef <= 0.0) || (violside == SCIP_SIDETYPE_RIGHT && sqrcoef > 0.0) ) 6451 SCIPaddSquareLinearization(scip, sqrcoef, ref[j], SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS, &coef[j], 6457 SCIPaddSquareSecant(scip, sqrcoef, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), ref[j], &coef[j], 6499 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_side%d_estimation_%d", SCIPconsGetName(cons), violside, SCIPgetNLPs(scip)); 6504 /** generates a cut based on linearization (if convex) or McCormick (if nonconvex) in a given reference point */ 6514 SCIP_Real* efficacy, /**< buffer to store efficacy of row in reference solution, or NULL if not of interest */ 6515 SCIP_Bool checkcurvmultivar, /**< are we allowed to check the curvature of a multivariate quadratic function, if not done yet */ 6516 SCIP_Real minefficacy /**< minimal required efficacy (violation scaled by maximal absolute coefficient) */ 6568 SCIP_CALL( generateCutFactorable(scip, cons, violside, ref, coef, &lhs, &rhs, &islocal, &success, cutname) ); 6574 /* generateCutLTI needs reference values also for the linear variables, which we only have if sol is given or LP has been solved */ 6575 SCIP_CALL( generateCutLTI(scip, cons, violside, ref, sol, &lincoefs, coef, &lhs, &rhs, &islocal, &success, cutname) ); 6577 /* in case of LTI cuts, we have to recompute the min and max of lincoefs, since they may have been modified */ 6593 if( (violside == SCIP_SIDETYPE_LEFT && consdata->isconcave) || (violside == SCIP_SIDETYPE_RIGHT && consdata->isconvex) ) 6595 SCIP_CALL( generateCutConvex(scip, cons, violside, ref, coef, &lhs, &rhs, &islocal, &success, cutname) ); 6599 SCIP_CALL( generateCutNonConvex(scip, cons, violside, ref, coef, &lhs, &rhs, &islocal, &success, cutname) ); 6622 * it is required if we need to check or return cut efficacy, for some debug output below, and some assert 6623 * round almost integral coefficients in integers, since this will happen when adding coefs to row (see comments below) 6631 * HOWEVER, they become column variables when they are added to a row (via SCIPaddVarsToRow below). 6633 * So when calculating the row activity, we treat loose variable as if they were already column variables. 6636 refactivitylinpart += (SCIPisIntegral(scip, lincoefs[j]) ? SCIPround(scip, lincoefs[j]) : lincoefs[j]) * SCIPgetSolVal(scip, sol, consdata->linvars[j]); 6653 * thus, we anticipate by rounding coef here, but also modify constant so that cut is still valid (if possible) 6676 SCIPdebugMessage("var <%s> [%g,%g] has almost integral coef %.20g, round coefficient to %g and add constant %g\n", 6677 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), coef[j], roundcoef, (coef[j]-roundcoef) * xbnd); 6686 /* As above: When calculating the row activity, we treat loose variable as if they were already column variables. */ 6710 SCIPdebugMessage("skip cut for constraint <%s> since all coefficients are zero and it's always satisfied\n", SCIPconsGetName(cons)); 6723 SCIPdebugMessage("cut coefficients for constraint <%s> have very large range: mincoef = %g maxcoef = %g\n", SCIPconsGetName(cons), mincoef, maxcoef); 6728 * since we use local bounds, we need to make the row local if they are different from their global counterpart 6730 if( ((coef[mincoefidx] > 0.0 && !SCIPisInfinity(scip, rhs)) || (coef[mincoefidx] < 0.0 && !SCIPisInfinity(scip, -lhs))) && 6733 SCIPdebugMessage("eliminate coefficient %g for <%s> [%g, %g]\n", coef[mincoefidx], SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 6739 else if( ((coef[mincoefidx] < 0.0 && !SCIPisInfinity(scip, rhs)) || (coef[mincoefidx] > 0.0 && !SCIPisInfinity(scip, -lhs))) && 6742 SCIPdebugMessage("eliminate coefficient %g for <%s> [%g, %g]\n", coef[mincoefidx], SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 6771 SCIPdebugMessage("skip cut for constraint <%s> because both sides are not finite: lhs = %g, rhs = %g\n", SCIPconsGetName(cons), lhs, rhs); 6785 /* in difference to SCIPgetCutEfficacy, we scale by norm only if the norm is > 1.0 this avoid finding cuts 6786 * efficient which are only very slightly violated CPLEX does not seem to scale row coefficients up too also we 6787 * use infinity norm, since that seem to be the usual scaling strategy in LP solvers (equilibrium scaling) */ 6814 if( success && !SCIPisInfinity(scip, -minefficacy) && rowefficacy < minefficacy ) /*lint !e644*/ 6816 SCIPdebugMessage("skip cut for constraint <%s> because efficacy %g too low (< %g)\n", SCIPconsGetName(cons), rowefficacy, minefficacy); 6823 SCIP_CALL( SCIPcreateEmptyRowCons(scip, row, SCIPconsGetHdlr(cons), cutname, lhs, rhs, islocal && (SCIPgetDepth(scip) > 0), FALSE, TRUE) ); 6832 SCIPdebugMessage("found cut <%s>, lhs=%g, rhs=%g, mincoef=%g, maxcoef=%g, range=%g, nnz=%d, violation=%g, efficacy=%g\n", 6842 * computing efficacy w.r.t. the LP solution makes only sense if the LP was solved to optimality (see bug 612) 6844 * disabled these asserts as they can fail due to numerical reasons (cancelation when substracting big numbers), 6845 * as the order in which we add up the activity for the single terms can be different than the one that lp.c uses 6849 assert((conshdlrdata->scaling != 'g') || (SCIPisFeasPositive(scip, rowefficacy) == SCIPisFeasPositive(scip, -SCIPgetRowSolFeasibility(scip, *row, sol)/MAX(1.0,SCIPgetRowMaxCoef(scip, *row))))); 6850 assert((conshdlrdata->scaling != 's') || (SCIPisFeasPositive(scip, rowefficacy) == SCIPisFeasPositive(scip, -SCIPgetRowSolFeasibility(scip, *row, sol)/MAX(1.0,MIN(REALABS(lhs),REALABS(rhs)))))); 6851 assert((conshdlrdata->scaling != 'o') || (SCIPisFeasPositive(scip, rowefficacy) == SCIPisFeasPositive(scip, -SCIPgetRowSolFeasibility(scip, *row, sol)))); 6858 /* if coefficients for linear variables are different than those in constraint, then free array */ 6928 /* in the convex case, we try to find an interior point of x^T A x + b^T x <= rhs - maximum activity linear part 6929 * in the concave case: lhs - minimum activity linear part <= x^T A x + b^T x; we compute activities ourselves, 6930 * since consdata->max(min)linactivity are only computed when lhs (rhs) is finite and this not always holds 6955 SCIPdebugMessage("maximum activity is infinity: there is no interior point for fun <= rhs - maxlinactivity!\n"); 6988 SCIPdebugMessage("minimum activity is -infinity: there is no interior point for fun >= lhs - minlinactivity!\n"); 7029 /* TODO: maybe one should set some generous iteration limit and/or a timelimit (remaining scip solve time)? */ 7061 assert(nlrowquadvars[nlrowquadelems[i].idx1] == consdata->quadvarterms[nlrowquadelems[i].idx1].var); 7062 assert(nlrowquadvars[nlrowquadelems[i].idx2] == consdata->quadvarterms[nlrowquadelems[i].idx2].var); 7075 SCIP_CALL( SCIPnlpiAddConstraints(nlpi, prob, 1, NULL, &nlpiside, &nquadvars, &lininds, &lincoefs, 7080 SCIP_CALL( SCIPnlpiAddConstraints(nlpi, prob, 1, &nlpiside, NULL, &nquadvars, &lininds, &lincoefs, 7135 SCIPdebugMessage("cons <%s>: found an interior point. solution status: %d, termination status: %d\n", 7142 /* TODO: we could still use the point, and let evaluateGauge decide whether the point is interior or not */ 7143 SCIPdebugMessage("cons <%s>: failed to find an interior point. solution status: %d, termination status: %d\n", 7151 SCIPerrorMessage("cons <%s>: undefined behaviour of NLP Solver. solution status: %d, termination status: %d\n", 7158 * note: nlpiGetSolution (at least for IPOPT) makes interiorpoint point to the internal solution stored in the 7159 * nlpi problem data structure; we need to copy it here because it will be destroyed once the problem is free'd 7182 printf(" - is convex. rhs: %g maximum activity of linear variables: %g\n", consdata->rhs, consdata->rhs - nlpiside); 7187 printf(" - is concave. lhs: %g minimum activity of linear variables: %g\n", consdata->lhs, consdata->lhs - nlpiside); 7207 printf("%s = %g\n", SCIPvarGetName(consdata->quadvarterms[i].var), consdata->interiorpoint[i]); 7238 /** 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$. 7240 * Here, \f$ f(x) \f$ is a purely quadratic (i.e, all \f$x\f$ variables appear in a bilinear or quadratic term). 7273 assert(consdata->sepabilinvar2pos != NULL || consdata->nbilinterms == 0); /* this should have been computed in INITSOL */ 7297 * we are going to evaluate the function at interiorpoint; so, we need to compute interiorpoint^T A interiorpoint; 7298 * therefore, we need a mechanism that for a given variable, it returns its interior point value 7304 /* compute value of quadratic part at interior point, build map and compute gaugeconst (c_gauge) */ 7328 /* the index of the variable associated with var2 in bilinterm should be given by sepabilinvar2pos */ 7329 assert(consdata->quadvarterms[consdata->sepabilinvar2pos[bilintermidx]].var == bilinterm->var2); 7342 consdata->gaugecoefs[i] += quadvarterm->lincoef + 2.0 * quadvarterm->sqrcoef * consdata->interiorpoint[i]; 7356 /* the index of the variable associated with var2 in bilinterm should be given by sepabilinvar2pos */ 7370 printf("b_gauge[%s] = %g\n", SCIPvarGetName(consdata->quadvarterms[j].var), consdata->gaugecoefs[j]); 7381 /** 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$. 7432 /* it can happen that the interior point is not really interior, since we are not so strict at the moment of 7433 * computing the interior point, which makes sense in the case that the constraint is quadratic <= linear expr, 7434 * since we compute a point in quadratic <= min linear expr and it might be that this set consists of a single 7435 * point which will not be interior. furthermore, if this set is empty, we could just take any point and it could 7436 * happen that for some value of linear expr, the point is actually interior, but for many it could not be. 7437 * also, if min linear expr = -infinity, we might have computed an interior point using some finite value. 7444 printf("rhs: %g level: %15.20g interiorpointval: %15.20g\n", consdata->rhs, side, consdata->interiorpointval); 7457 printf("rhs: %g level: %15.20g interiorpointval: %15.20g\n", consdata->rhs, side, consdata->interiorpointval); 7478 printf("lhs: %g level: %15.20g interiorpointval: %15.20g\n", consdata->lhs, side, consdata->interiorpointval); 7491 printf("lhs: %g level: %15.20g interiorpointval: %15.20g\n", consdata->lhs, side, consdata->interiorpointval); 7522 cterm += consdata->bilinterms[i].coef * SCIPgetSolVal(scip, refsol, var1) * SCIPgetSolVal(scip, refsol, var2); 7566 SCIP_SOL* refsol, /**< reference point where to compute gauge, or NULL if LP solution should be used */ 7619 printf("refsol is in the closure of the region (gaugeval <= 1), don't modify reference point\n"); 7637 /* set reference to (refsol - interior point)/gaugeval + interior point and project into bounds 7666 /** generates a cut based on linearization (if convex) or McCormick (if nonconvex) in a solution */ 7676 SCIP_Real* efficacy, /**< buffer to store efficacy of row in reference solution, or NULL if not of interest */ 7677 SCIP_Bool checkcurvmultivar, /**< are we allowed to check the curvature of a multivariate quadratic function, if not done yet */ 7678 SCIP_Real minefficacy /**< minimal required efficacy (violation scaled by maximal absolute coefficient) */ 7716 SCIP_CALL( generateCut(scip, conshdlr, cons, ref, sol, violside, row, efficacy, checkcurvmultivar, minefficacy) ); 7719 if( *row == NULL || (efficacy != NULL && !SCIPisGT(scip, *efficacy, minefficacy)) || !SCIPisCutApplicable(scip, *row) ) /*lint !e644 */ 7741 SCIP_CALL( generateCut(scip, conshdlr, cons, ref, sol, violside, row, efficacy, checkcurvmultivar, minefficacy) ); 7752 * For nonconvex functions, we just call generateCutSol with the unbounded solution as reference point. 7761 SCIP_Real* rowrayprod, /**< buffer to store product of ray with row coefficients, or NULL if not of interest */ 7762 SCIP_Bool checkcurvmultivar /**< are we allowed to check the curvature of a multivariate quadratic function, if not done yet */ 7798 SCIP_CALL( generateCutSol(scip, conshdlr, cons, NULL, NULL, violside, row, NULL, FALSE, -SCIPinfinity(scip)) ); 7817 /* we seek for a linearization of the quadratic function such that it intersects with the unbounded ray 7818 * that is, we need a reference point ref such that for the gradient g of xAx+bx in ref, we have 7821 * 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) 7822 * <ref, 2*A*ray> + <b,ray> is sufficiently larger 0.0, we call generateCut for this point, otherwise, we scale up ref 7838 matrixrayprod += bilinterm->coef * SCIPgetPrimalRayVal(scip, bilinterm->var1 == var ? bilinterm->var2 : bilinterm->var1); 7851 assert((violside == SCIP_SIDETYPE_RIGHT && quadrayprod >= 0.0) || (violside == SCIP_SIDETYPE_LEFT && quadrayprod <= 0.0)); 7864 SCIPdebugMessage("initially have <b,ray> = %g and <ref, 2*A*ref> = %g\n", linrayprod, quadrayprod); 7866 /* 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 7869 if( (!SCIPisZero(scip, linrayprod) && violside == SCIP_SIDETYPE_RIGHT && quadrayprod < -2*linrayprod) || 7870 ( !SCIPisZero(scip, linrayprod) && violside == SCIP_SIDETYPE_LEFT && quadrayprod > -2*linrayprod) || 7890 SCIP_CALL( generateCut(scip, conshdlr, cons, ref, NULL, violside, row, NULL, FALSE, -SCIPinfinity(scip)) ); 7912 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 */ 7943 if( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) ) 7949 violside = SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT; 7952 actminefficacy = inenforcement && ((violside == SCIP_SIDETYPE_RIGHT && consdata->isconvex ) || (violside == SCIP_SIDETYPE_LEFT && consdata->isconcave)) 7959 /* if the LP is unbounded, then we need a cut that cuts into the direction of a hopefully existing primal ray 7960 * 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 7961 * given a cut lhs <= <c,x> <= rhs, we check whether it imposes an upper bound on t and thus bounds the ray 7962 * 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> 7969 SCIP_CALL( generateCutUnboundedLP(scip, conshdlr, conss[c], violside, &row, &rayprod, conshdlrdata->checkcurvature) ); 7986 /* in difference to SCIPgetCutEfficacy, we scale by norm only if the norm is > 1.0 this avoid finding 7988 * coefficients up too also we use infinity norm, since that seem to be the usual scaling strategy 8013 /* @todo If convex, can we easily move the refpoint closer to the feasible region to get a stronger cut? 8016 SCIP_CALL( generateCutSol(scip, conshdlr, conss[c], sol, NULL, violside, &row, &efficacy, conshdlrdata->checkcurvature, actminefficacy) ); 8017 /* @todo If generation failed not because of low efficacy, then probably because of numerical issues; 8018 * if the constraint is convex and we are desperate to get a cut, then we may try again with a better chosen reference point 8025 if( SCIPisGT(scip, efficacy, actminefficacy) && SCIPisCutApplicable(scip, row) ) /*lint !e644 */ 8033 SCIPdebugMessage("cut for constraint <%s> is infeasible -> cutoff.\n", SCIPconsGetName(conss[c])); 8058 * others are only checked and enforced if we are still feasible or have not found a separating cut yet 8067 /** adds linearizations cuts for convex constraints w.r.t. a given reference point to cutpool and sepastore 8069 * - 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. 8070 * - If separatedlpsol is not NULL, but cut does not separate the LP solution, then it is added to the cutpool only. 8080 SCIP_Bool* separatedlpsol, /**< buffer to store whether a cut that separates the current LP solution was found and added to LP, 8082 SCIP_Real minefficacy /**< minimal efficacy of a cut when checking for separation of LP solution */ 8115 SCIP_CALL( generateCutSol(scip, conshdlr, conss[c], NULL, ref, SCIP_SIDETYPE_RIGHT, &row, NULL, 8144 /* in difference to SCIPgetCutEfficacy, we scale by norm only if the norm is > 1.0 this avoid finding cuts 8145 * efficient which are only very slightly violated CPLEX does not seem to scale row coefficients up too 8146 * also we use infinity norm, since that seem to be the usual scaling strategy in LP solvers (equilibrium 8176 SCIPdebugMessage("added linearization cut <%s> to LP, efficacy = %g\n", SCIProwGetName(row), efficacy); 8195 { 8222 /* we are only interested in solution coming from some heuristic other than trysol, but not from the tree 8223 * the reason for ignoring trysol solutions is that they may come from an NLP solve in sepalp, where we already added linearizations, 8232 SCIPdebugMessage("caught new sol event %x from heur <%s>; have %d conss\n", SCIPeventGetType(event), SCIPheurGetName(SCIPsolGetHeur(sol)), nconss); 8241 * That is, computes for every nonconvex term the gap between the terms value in the LP solution and the value of the underestimator 8242 * as it would be (and maybe has been) constructed by the separation routines of this constraint handler. Then it registers all 8243 * variables occurring in each term with the computed gap. If variables appear in more than one term, they are registered several times. 8292 SCIPdebugMessage("cons %s violation: %g %g convex: %u %u\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol, consdata->isconvex, consdata->isconcave); 8298 if( (SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) && consdata->quadvarterms[j].sqrcoef < 0) || 8299 ( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && consdata->quadvarterms[j].sqrcoef > 0) ) 8305 SCIPdebugMessage("ignore fixed variable <%s>[%g, %g], diff %g\n", SCIPvarGetName(x), xlb, xub, xub-xlb); 8328 /* if any of the variables if fixed, then it actually behaves like a linear term, so we don't need to branch on it */ 8351 /* if both variables are at one of its bounds, then no need to branch, since McCormick is exact there */ 8359 coef_ = SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) ? -consdata->bilinterms[j].coef : consdata->bilinterms[j].coef; 8375 assert(!SCIPisNegative(scip, gap / MAX3(MAX(REALABS(xlb), REALABS(xub)), MAX(REALABS(ylb), REALABS(yub)), 1.0))); /*lint !e666*/ 8380 /* if one of the variables is binary or integral with domain width 1, then branching on this makes the term linear, so prefer this */ 8410 /* if both variables are integral, prefer the one with the smaller domain, so variable gets fixed soon 8411 * does not seem to work well on tln instances, so disable for now and may look at it later again 8432 * this is, because after branching both variables will be one the bounds, and McCormick will be exact then */ 8453 * That is, registers all variables appearing in nonconvex terms^1 with a score that is the violation of the constraint. 8454 * This is the same rule as is applied in cons_nonlinear and other nonlinear constraint handlers. 8456 * 1) We mean all quadratic variables that appear either in a nonconvex square term or in a bilinear term, if the constraint 8457 * itself is nonconvex. (and this under the assumption that the rhs is violated; for violated lhs, swap terms) 8495 SCIPdebugMessage("cons %s violation: %g %g convex: %u %u\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol, consdata->isconvex, consdata->isconcave); 8512 /* if variable is at bounds and only in a nonconvex square term, then no need to branch, since secant is exact there */ 8519 SCIPdebugMessage("ignore fixed variable <%s>[%g, %g], diff %g\n", SCIPvarGetName(x), xlb, xub, xub-xlb); 8523 SCIP_CALL( SCIPaddExternBranchCand(scip, x, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) ); 8536 * That is, registers all variables appearing in nonconvex terms^1 with a score that is given by the distance of the 8537 * variable value from its bounds. This rule should not make sense, as the distance to the bounds is also (often) considered 8540 * 1) We mean all quadratic variables that appear either in a nonconvex square term or in a bilinear term, if the constraint 8541 * itself is nonconvex. (and this under the assumption that the rhs is violated; for violated lhs, swap terms) 8580 SCIPdebugMessage("cons %s violation: %g %g convex: %u %u\n", SCIPconsGetName(conss[c]), consdata->lhsviol, consdata->rhsviol, consdata->isconvex, consdata->isconcave); 8595 SCIPdebugMessage("ignore fixed variable <%s>[%g, %g], diff %g\n", SCIPvarGetName(x), xlb, xub, xub-xlb); 8608 if( (!SCIPisInfinity(scip, -xlb) && SCIPisEQ(scip, xval, xlb)) || (!SCIPisInfinity(scip, xub) && SCIPisEQ(scip, xval, xub)) ) 8668 /** registers a quadratic variable from a violated constraint as branching candidate that has a large absolute value in the LP relaxation */ 8695 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) ) 8701 if( SCIPisRelEQ(scip, SCIPvarGetLbLocal(consdata->quadvarterms[i].var), SCIPvarGetUbLocal(consdata->quadvarterms[i].var)) ) 8720 /** replaces violated quadratic constraints where all quadratic variables are fixed by linear constraints */ 8756 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) ) 8764 assert(SCIPisRelEQ(scip, SCIPvarGetLbLocal(consdata->quadvarterms[i].var), SCIPvarGetUbLocal(consdata->quadvarterms[i].var))); 8766 val1 = (SCIPvarGetUbLocal(consdata->quadvarterms[i].var) + SCIPvarGetLbLocal(consdata->quadvarterms[i].var)) / 2.0; 8767 constant += (consdata->quadvarterms[i].lincoef + consdata->quadvarterms[i].sqrcoef * val1) * val1; 8772 val1 = (SCIPvarGetUbLocal(consdata->bilinterms[i].var1) + SCIPvarGetLbLocal(consdata->bilinterms[i].var1)) / 2.0; 8773 val2 = (SCIPvarGetUbLocal(consdata->bilinterms[i].var2) + SCIPvarGetLbLocal(consdata->bilinterms[i].var2)) / 2.0; 8798 SCIPdebugMessage("Linear constraint with one variable: %g <= %g <%s> <= %g\n", lhs, coef, SCIPvarGetName(*consdata->linvars), rhs); 8823 SCIPdebugMessage("Linear constraint is a bound: %g <= <%s> <= %g\n", lhs, SCIPvarGetName(*consdata->linvars), rhs); 8877 SCIPdebugMessage("replace quadratic constraint <%s> by linear constraint after all quadratic vars have been fixed\n", SCIPconsGetName(conss[c]) ); 8942 SCIPdebugMessage("%s found constraint <%s> infeasible due to tightened lower bound %g for variable <%s>\n", 9003 SCIPdebugMessage("%s found constraint <%s> infeasible due to tightened upper bound %g for variable <%s>\n", 9021 /** 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 */ 9049 SCIPdebugMessage("found <%s> infeasible due to domain propagation for quadratic variable <%s>\n", SCIPconsGetName(cons), SCIPvarGetName(var)); 9073 SCIPdebugMessage("found <%s> infeasible due to domain propagation for quadratic variable <%s>\n", SCIPconsGetName(cons), SCIPvarGetName(var)); 9088 /* 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); */ 9090 if( SCIPisInfinity(scip, SCIPintervalGetInf(newrange)) || SCIPisInfinity(scip, -SCIPintervalGetSup(newrange)) ) 9093 SCIPdebugMessage("found <%s> infeasible because propagated domain of quadratic variable <%s> is outside of (-infty, +infty)\n", 9102 SCIPdebugMessage("found <%s> infeasible due to domain propagation for quadratic variable <%s>\n", SCIPconsGetName(cons), SCIPvarGetName(var)); 9109 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, SCIPintervalGetInf(newrange), result, nchgbds) ); 9116 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, SCIPintervalGetSup(newrange), result, nchgbds) ); 9124 /* The new version below computes potentially tighter bounds, but also always adds a small safety area since it is not implemented roundingsafe. 9129 /** tries to deduce domain reductions for x in xsqrcoef x^2 + xlincoef x + ysqrcoef y^2 + ylincoef y + bilincoef x y \\in rhs 9168 SCIPintervalSetBounds(&varbnds, MIN(SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y)), MAX(SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y))); /*lint !e666 */ 9173 /* if rhs is unbounded by above, it is sufficient to get an upper bound on ysqrcoef*y^2 + ylincoef * y */ 9186 /* if rhs is unbounded by below, it is sufficient to get a lower bound on ysqrcoef*y^2 + ylincoef * y */ 9212 SCIP_CALL( propagateBoundsQuadVar(scip, cons, intervalinfty, x, xsqrcoef, lincoef, myrhs, result, nchgbds) ); 9217 /** tries to deduce domain reductions for x in xsqrcoef x^2 + xlincoef x + ysqrcoef y^2 + ylincoef y + bilincoef x y \\in rhs 9255 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x))), /*lint !e666*/ 9256 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x)))); /*lint !e666*/ 9258 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y))), /*lint !e666*/ 9259 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(y), SCIPvarGetUbLocal(y)))); /*lint !e666*/ 9262 SCIPintervalSolveBivariateQuadExpressionAllScalar(intervalinfty, &xbnds, xsqrcoef, ysqrcoef, bilincoef, xlincoef, ylincoef, rhs, xbnds, ybnds); 9266 SCIPdebugMessage("found <%s> infeasible due to domain propagation for quadratic variable <%s>\n", SCIPconsGetName(cons), SCIPvarGetName(x)); 9273 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, x, SCIPintervalGetInf(xbnds), result, nchgbds) ); 9280 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, x, SCIPintervalGetSup(xbnds), result, nchgbds) ); 9300 SCIP_Real* minquadactivity, /**< minimal activity of quadratic variable terms where only terms with finite minimal activity contribute */ 9301 SCIP_Real* maxquadactivity, /**< maximal activity of quadratic variable terms where only terms with finite maximal activity contribute */ 9302 int* minactivityinf, /**< number of quadratic variables that contribute -infinity to minimal activity */ 9303 int* maxactivityinf, /**< number of quadratic variables that contribute +infinity to maximal activity */ 9348 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->quadvarterms[i].var), SCIPvarGetUbLocal(consdata->quadvarterms[i].var))), 9349 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->quadvarterms[i].var), SCIPvarGetUbLocal(consdata->quadvarterms[i].var)))); 9359 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))), 9360 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2)))); 9368 bnd = SCIPintervalQuadUpperBound(intervalinfty, consdata->quadvarterms[i].sqrcoef, lincoef, xrng); 9375 /* if maximal activity is below value for -infinity, let's take -1e10 as upper bound on maximal activity 9396 bnd = -SCIPintervalQuadUpperBound(intervalinfty, -consdata->quadvarterms[i].sqrcoef, lincoef, xrng); 9404 /* if minimal activity is above value for infinity, let's take 1e10 as lower bound on minimal activity 9437 SCIP_Bool* redundant /**< buffer where to store whether constraint has been found to be redundant */ 9446 int quadminactinf; /* number of quadratic variables that contribute -infinity to minimal activity of quadratic term */ 9447 int quadmaxactinf; /* number of quadratic variables that contribute +infinity to maximal activity of quadratic term */ 9448 SCIP_INTERVAL* quadactcontr; /* contribution of each quadratic variable term to quadactivity */ 9492 /* sort quadratic variable terms, in case we need to search for terms occuring in bilinear terms later 9505 propagateBoundsGetQuadActivity(scip, consdata, intervalinfty, &minquadactivity, &maxquadactivity, &quadminactinf, &quadmaxactinf, quadactcontr); 9520 SCIPintervalSetBounds(&consactivity, consdata->minlinactivityinf > 0 ? -intervalinfty : consdata->minlinactivity, 9525 SCIPdebugMessage("found constraint <%s> to be redundant: sides: [%g, %g], activity: [%g, %g]\n", 9526 SCIPconsGetName(cons), consdata->lhs, consdata->rhs, SCIPintervalGetInf(consactivity), SCIPintervalGetSup(consactivity)); 9531 /* was SCIPintervalAreDisjoint(consbounds, consactivity), but that would allow violations up to eps only 9534 if( SCIPisFeasGT(scip, consbounds.inf, consactivity.sup) || SCIPisFeasLT(scip, consbounds.sup, consactivity.inf) ) 9536 SCIPdebugMessage("found constraint <%s> to be infeasible; sides: [%g, %g], activity: [%g, %g], infeas: %g\n", 9537 SCIPconsGetName(cons), consdata->lhs, consdata->rhs, SCIPintervalGetInf(consactivity), SCIPintervalGetSup(consactivity), 9538 MAX(consdata->lhs - SCIPintervalGetSup(consactivity), SCIPintervalGetInf(consactivity) - consdata->rhs)); 9543 /* propagate linear part \in rhs = consbounds - quadactivity (use the one from consdata, since that includes infinities) */ 9556 * we can't expect much more tightening, but may detect infeasiblity, but shouldn't the check on the constraints activity detect that? 9578 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, bnd, result, nchgbds) ); 9592 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, bnd, result, nchgbds) ); 9614 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, bnd, result, nchgbds) ); 9628 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, bnd, result, nchgbds) ); 9653 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, bnd, result, nchgbds) ); 9667 SCIP_CALL( propagateBoundsTightenVarUb(scip, cons, intervalinfty, var, bnd, result, nchgbds) ); 9689 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, bnd, result, nchgbds) ); 9703 SCIP_CALL( propagateBoundsTightenVarLb(scip, cons, intervalinfty, var, bnd, result, nchgbds) ); 9718 consdataUpdateLinearActivity(scip, consdata, intervalinfty); /* make sure, activities of linear part did not become invalid by above bound changes, if any */ 9719 assert(consdata->minlinactivityinf > 0 || consdata->maxlinactivityinf > 0 || consdata->minlinactivity <= consdata->maxlinactivity); 9737 SCIP_CALL( propagateBoundsQuadVar(scip, cons, intervalinfty, var, consdata->quadvarterms[0].sqrcoef, lincoef, rhs, result, nchgbds) ); 9741 /* quadratic part is just ax*x^2+bx*x + ay*y^2+by*y + c*xy -> a common case that we treat directly */ 9742 assert(consdata->bilinterms[0].var1 == consdata->quadvarterms[0].var || consdata->bilinterms[0].var1 == consdata->quadvarterms[1].var); 9743 assert(consdata->bilinterms[0].var2 == consdata->quadvarterms[0].var || consdata->bilinterms[0].var2 == consdata->quadvarterms[1].var); 9747 consdata->quadvarterms[0].var, consdata->quadvarterms[0].sqrcoef, consdata->quadvarterms[0].lincoef, 9748 consdata->quadvarterms[1].var, consdata->quadvarterms[1].sqrcoef, consdata->quadvarterms[1].lincoef, 9755 consdata->quadvarterms[1].var, consdata->quadvarterms[1].sqrcoef, consdata->quadvarterms[1].lincoef, 9756 consdata->quadvarterms[0].var, consdata->quadvarterms[0].sqrcoef, consdata->quadvarterms[0].lincoef, 9770 propagateBoundsGetQuadActivity(scip, consdata, intervalinfty, &minquadactivity, &maxquadactivity, &quadminactinf, &quadmaxactinf, quadactcontr); 9776 /* if the quad activities are not hopelessly unbounded on useful sides, try to deduce domain reductions on quad vars */ 9791 * we can't expect much more tightening, but may detect infeasiblity, but shouldn't the check on the constraints activity detect that? 9798 /* setup rhs2.sup = rhs.sup - (quadactivity.inf - quadactcontr[i].inf), if everything were finite 9799 * if only quadactcontr[i].inf is infinite (i.e., the other i are all finite), we just get rhs2.sup = rhs.sup 9803 if( quadminactinf == 0 || (quadminactinf == 1 && SCIPintervalGetInf(quadactcontr[i]) <= -intervalinfty) ) 9808 /* if the residual quad min activity w.r.t. quad var term i is finite and nonzero, so add it to right hand side */ 9815 /* there are either >= 2 quad var terms contributing -infinity, or there is one which is not i */ 9827 if( quadmaxactinf == 0 || (quadmaxactinf == 1 && SCIPintervalGetSup(quadactcontr[i]) >= intervalinfty) ) 9832 /* if the residual quad max activity w.r.t. quad var term i is finite and nonzero, so add it to right hand side */ 9839 /* there are either >= 2 quad var terms contributing infinity, or there is one which is not i */ 9861 /* bilinear term k contributes to the activity of quad var term i, so just add bounds to linear coef */ 9863 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))), 9864 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2)))); 9873 * 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 9874 * HOWEVER: when computing rhs2, we may not just have added the bounds for the bilinear term, but for the associated quadratic term 9876 * since we do not want to repeat a call to SCIPintervalQuad for that quadratic term with bilinear term k removed, 9877 * we only remove the bounds for the bilinear term k from rhs2 if the associated quadratic term consists only of this bilinear term, 9878 * i.e., the quadratic term corresponding to var1 should be only var1*var2, but have no square or linear coefs or other bilinear terms 9879 * (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) 9892 if( (consdata->quadvarterms[otherpos].sqrcoef != 0.0) || consdata->quadvarterms[otherpos].lincoef != 0.0 || 9898 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var1), SCIPvarGetUbLocal(consdata->bilinterms[k].var1))), 9899 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var1), SCIPvarGetUbLocal(consdata->bilinterms[k].var1)))); 9904 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))), 9905 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2)))); 9941 -infty2infty(SCIPinfinity(scip), intervalinfty, -MIN(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2))), 9942 +infty2infty(SCIPinfinity(scip), intervalinfty, MAX(SCIPvarGetLbLocal(consdata->bilinterms[k].var2), SCIPvarGetUbLocal(consdata->bilinterms[k].var2)))); 9949 SCIP_CALL( propagateBoundsQuadVar(scip, cons, intervalinfty, var, consdata->quadvarterms[i].sqrcoef, lincoef, rhs2, result, nchgbds) ); 9988 assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_SOLVING); 10005 SCIPdebugMessage("starting domain propagation round %d of %d for %d constraints\n", roundnr, maxproprounds, nconss); 10032 /** checks for a linear variable that can be increase or decreased without harming feasibility */ 10046 /* check for a linear variable that can be increase or decreased without harming feasibility */ 10065 /* if we have already one candidate, then take the one where the loss in the objective function is less */ 10067 (SCIPvarGetObj(consdata->linvars[consdata->linvar_maydecrease]) / consdata->lincoefs[consdata->linvar_maydecrease] > SCIPvarGetObj(consdata->linvars[i]) / consdata->lincoefs[i]) ) 10074 /* if we have already one candidate, then take the one where the loss in the objective function is less */ 10076 (SCIPvarGetObj(consdata->linvars[consdata->linvar_mayincrease]) / consdata->lincoefs[consdata->linvar_mayincrease] > SCIPvarGetObj(consdata->linvars[i]) / consdata->lincoefs[i]) ) 10084 SCIPdebugMessage("may increase <%s> to become feasible\n", SCIPvarGetName(consdata->linvars[consdata->linvar_mayincrease])); 10088 SCIPdebugMessage("may decrease <%s> to become feasible\n", SCIPvarGetName(consdata->linvars[consdata->linvar_maydecrease])); 10093 /** Given a solution where every quadratic constraint is either feasible or can be made feasible by 10094 * moving a linear variable, construct the corresponding feasible solution and pass it to the trysol heuristic. 10096 * The method assumes that this is always possible and that not all constraints are feasible already. 10105 SCIP_Bool* success /**< buffer to store whether we succeeded to construct a solution that satisfies all provided constraints */ 10142 sol != NULL ? (SCIPsolGetHeur(sol) != NULL ? SCIPheurGetName(SCIPsolGetHeur(sol)) : "tree") : "LP"); 10170 ((viol > 0.0 && consdata->lincoefs[consdata->linvar_mayincrease] > 0.0) || (viol < 0.0 && consdata->lincoefs[consdata->linvar_mayincrease] < 0.0)) ) 10190 SCIPdebugMessage("increase <%s> by %g to %g\n", SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var)); 10201 ((viol > 0.0 && consdata->lincoefs[consdata->linvar_maydecrease] < 0.0) || (viol < 0.0 && consdata->lincoefs[consdata->linvar_maydecrease] > 0.0)) ) 10220 SCIPdebugMessage("increase <%s> by %g to %g\n", SCIPvarGetName(var), delta, SCIPgetSolVal(scip, newsol, var)); 10229 /* still here... so probably we could not make constraint feasible due to variable bounds, thus give up */ 10234 /* if we have a solution that should satisfy all quadratic constraints and has a better objective than the current upper bound, 10237 if( c == nconss && (SCIPisInfinity(scip, SCIPgetUpperbound(scip)) || SCIPisSumLT(scip, SCIPgetSolTransObj(scip, newsol), SCIPgetUpperbound(scip))) ) 10239 SCIPdebugMessage("pass solution with objective val %g to trysol heuristic\n", SCIPgetSolTransObj(scip, newsol)); 10255 { 10271 /* if a quadratic expression has been simplified, then all children of the node should be variables */ 10305 /* these do not look like an quadratic expression (assuming the expression graph simplifier did run) */ 10317 SCIPwarningMessage(scip, "unexpected expression operator %d in nonlinear constraint <%s>\n", SCIPexprgraphGetNodeOperator(node), SCIPconsGetName(cons)); 10332 SCIPgetNLinearVarsNonlinear(scip, cons), SCIPgetLinearVarsNonlinear(scip, cons), SCIPgetLinearCoefsNonlinear(scip, cons), 10346 SCIP_CALL( SCIPaddQuadVarQuadratic(scip, upgdconss[0], (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, SCIPexprgraphGetNodeChildren(node)[i]), 0.0, 0.0) ); 10404 (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, SCIPexprgraphGetNodeChildren(node)[quadelems[i].idx1]), 10411 (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, SCIPexprgraphGetNodeChildren(node)[quadelems[i].idx1]), 10412 (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, SCIPexprgraphGetNodeChildren(node)[quadelems[i].idx2]), 10448 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 10451 { 10492 /** deinitialization method of constraint handler (called before transformed problem is freed) */ 10510 /** presolving initialization method of constraint handler (called when presolving is about to begin) */ 10530 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */ 10581 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) 10587 { 10606 /* check for a linear variable that can be increase or decreased without harming feasibility */ 10614 consdata->lincoefsmin = MIN(consdata->lincoefsmin, REALABS(consdata->lincoefs[i])); /*lint !e666 */ 10615 consdata->lincoefsmax = MAX(consdata->lincoefsmax, REALABS(consdata->lincoefs[i])); /*lint !e666 */ 10635 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->sepabilinvar2pos, consdata->nbilinterms) ); 10645 SCIP_CALL( consdataFindQuadVarTerm(scip, consdata, consdata->bilinterms[i].var2, &consdata->sepabilinvar2pos[i]) ); 10651 /* check if constraint function is factorable, i.e., can be written as product of two linear functions */ 10655 /* compute gauge function using interior points per constraint, only when there are quadratic variables */ 10683 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, (SCIP_EVENTDATA*)conshdlr, &conshdlrdata->newsoleventfilterpos) ); 10688 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"); 10699 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) 10753 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, (SCIP_EVENTDATA*)conshdlr, conshdlrdata->newsoleventfilterpos) ); 10763 { 10780 { 10803 SCIP_CALL( SCIPgetTransformedVar(scip, targetdata->quadvarterms[i].var, &targetdata->quadvarterms[i].var) ); 10809 SCIP_CALL( SCIPgetTransformedVar(scip, targetdata->bilinterms[i].var1, &targetdata->bilinterms[i].var1) ); 10810 SCIP_CALL( SCIPgetTransformedVar(scip, targetdata->bilinterms[i].var2, &targetdata->bilinterms[i].var2) ); 10822 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata, 10823 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons), 10825 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), 10834 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */ 10837 { 10869 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(conss[c]), SCIPconsGetName(conss[c]), consdata->lhs, consdata->rhs, 10871 SCIP_CALL( SCIPaddVarsToRow(scip, row, consdata->nlinvars, consdata->linvars, consdata->lincoefs) ); 10918 SCIP_CALL( generateCut(scip, conshdlr, conss[c], x, NULL, consdata->isconvex ? SCIP_SIDETYPE_RIGHT : SCIP_SIDETYPE_LEFT, &row, NULL, 10924 SCIPdebugMessage("initlp adds row <%s> for lambda = %g of conss <%s>\n", SCIProwGetName(row), lambda, SCIPconsGetName(conss[c])); /*lint !e613 */ 10938 if( (! consdata->isconvex && !SCIPisInfinity(scip, consdata->rhs)) || (! consdata->isconcave && !SCIPisInfinity(scip, -consdata->lhs)) ) 10953 /* Set reference point to 0 projected on bounds for unbounded variables or in between lower and upper bound 10954 * for bounded variables in the first round, we set it closer to the best bound for one part of the 10957 * The reason for the latter is, that for a bilinear term with bounded variables, there are always two linear underestimators 10958 * if the same weight is used for both variables of a product, then rounding and luck decides which underestimator is chosen 10959 * of course, the possible number of cuts is something in the order of 2^nquadvars, and we choose two of them here. 10985 x[i] = lambda * SCIPvarGetBestBoundLocal(var) + (1.0-lambda) * SCIPvarGetWorstBoundLocal(var); 11001 SCIPdebugMessage("initlp adds row <%s> for rhs of conss <%s>, round %d\n", SCIProwGetName(row), SCIPconsGetName(conss[c]), k); /*lint !e613 */ 11020 SCIPdebugMessage("initlp adds row <%s> for lhs of conss <%s>, round %d\n", SCIProwGetName(row), SCIPconsGetName(conss[c]), k); /*lint !e613 */ 11032 /* if there are unbounded variables, then there is typically only at most one possible underestimator, so don't try another round 11033 * 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 */ 11050 { 11068 /* at root, check if we want to solve the NLP relaxation and use its solutions as reference point 11069 * if there is something convex, then linearizing in the solution of the NLP relaxation can be very useful 11073 (SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_UNBOUNDEDRAY && conshdlrdata->sepanlpmincont <= 1.0)) && 11086 * but first check whether there is a violated constraint side which corresponds to a convex function 11096 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) ) 11164 SCIPdebugMessage("pass solution with obj. value %g to trysol\n", SCIPgetSolOrigObj(scip, nlpsol)); 11169 SCIP_CALL( addLinearizationCuts(scip, conshdlr, conss, nconss, nlpsol, &lpsolseparated, conshdlrdata->mincutefficacysepa) ); 11173 /* if a cut that separated the LP solution was added, then return, otherwise continue with usual separation in LP solution */ 11183 /* if we do not want to try solving the NLP, or have no NLP, or have no NLP solver, or solving the NLP failed, 11184 * or separating with NLP solution as reference point failed, then try (again) with LP solution as reference point 11187 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, conshdlrdata->mincutefficacysepa, FALSE, result, NULL) ); 11195 { 11214 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, sol, conshdlrdata->mincutefficacysepa, FALSE, result, NULL) ); 11256 SCIPdebugMessage("enfolp with max violation %g in cons <%s>\n", maxviol, SCIPconsGetName(maxviolcon)); 11259 * (maybe the LP does not think that the cuts we add are violated, or we do ECP on a high-dimensional convex function) 11260 * 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 11261 * (in optimized more, returning SCIP_INFEASIBLE in *result would be sufficient, but in debug mode this would give an assert in scip.c) 11262 * the reason to wait for 100 rounds is to avoid calls to SCIPisStopped in normal runs, which may be expensive 11273 SCIP_CALL( SCIPcreateChild(scip, &child, 1.0, SCIPnodeGetEstimate(SCIPgetCurrentNode(scip))) ); 11282 /* cut off the current subtree, if a limit on the enforcement rounds should be applied. At this point, feasible 11283 * solutions might get cut off; the enfolplimit parameter should therefore only be set if SCIP is used as a 11286 if( conshdlrdata->enfolplimit != -1 && conshdlrdata->nenfolprounds > conshdlrdata->enfolplimit ) 11289 "cut off subtree because enforcement limit was reached; this might lead to incorrect results\n"); 11305 SCIPdebugMessage("propagation succeeded (%s)\n", propresult == SCIP_CUTOFF ? "cutoff" : "reduceddom"); 11312 * thus, in the latter case, we are also happy if the efficacy is at least, say, 75% of the maximal violation 11315 minefficacy = MIN(0.75*maxviol, conshdlrdata->mincutefficacyenfofac * SCIPfeastol(scip)); /*lint !e666 */ 11317 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, minefficacy, TRUE, &separateresult, &sepaefficacy) ); 11326 SCIPdebugMessage("separation succeeded (bestefficacy = %g, minefficacy = %g)\n", sepaefficacy, minefficacy); 11335 SCIPdebugMessage("separation failed (bestefficacy = %g < %g = minefficacy ); max viol: %g\n", sepaefficacy, minefficacy, maxviol); 11340 /* if sepastore can decrease LP feasibility tolerance, we can add cuts with efficacy in [eps, feastol] */ 11341 leastpossibleefficacy = SCIPgetRelaxFeastolFactor(scip) > 0.0 ? SCIPepsilon(scip) : SCIPfeastol(scip); 11345 SCIP_CALL( separatePoint(scip, conshdlr, conss, nconss, nusefulconss, NULL, leastpossibleefficacy, TRUE, &separateresult, &sepaefficacy) ); 11362 /* fallback 2: separation probably failed because of numerical difficulties with a convex constraint; 11363 * if noone declared solution infeasible yet and we had not even found a weak cut, try to resolve by branching 11374 SCIP_CALL( replaceByLinearConstraints(scip, conss, nconss, &addedcons, &reduceddom, &infeasible) ); 11375 /* if the linear constraints are actually feasible, then adding them and returning SCIP_CONSADDED confuses SCIP 11376 * when it enforces the new constraints again and nothing resolves the infeasiblity that we declare here thus, 11377 * we only add them if considered violated, and otherwise claim the solution is feasible (but print a 11388 SCIPwarningMessage(scip, "could not enforce feasibility by separating or branching; declaring solution with viol %g as feasible\n", maxviol); 11395 SCIPdebugMessage("Could not find any usual branching variable candidate. Proposed variable <%s> with LP value %g for branching.\n", 11452 if( !SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) && !SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) ) 11460 SCIP_CALL( SCIPaddExternBranchCand(scip, var, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) ); 11470 SCIP_CALL( SCIPaddExternBranchCand(scip, var, MAX(consdata->lhsviol, consdata->rhsviol), SCIP_INVALID) ); 11478 SCIPdebugMessage("All variables in violated constraints fixed (up to epsilon). Cannot find branching candidate. Forcing solution of LP.\n"); 11489 { 11524 * then try the reformulations (replacing products with binaries, disaggregation, setting default variable bounds) 11526 * @todo first do all usual presolving steps, then check SCIPisPresolveFinished(scip), and if true then do reformulations (and usual steps again) 11528 doreformulations = nrounds > 0 && ((presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 || SCIPisPresolveFinished(scip)); 11529 SCIPdebugMessage("presolving will %swait with reformulation\n", doreformulations ? "not " : ""); 11566 /* 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 11567 * we want to do this before (multi)aggregated variables are replaced, since that may change structure, e.g., introduce bilinear terms 11573 SCIP_CALL( presolveUpgrade(scip, conshdlr, conss[c], &upgraded, nupgdconss, naddconss, presoltiming) ); 11592 SCIPdebugMessage("solving constraint <%s> says problem is infeasible in presolve\n", SCIPconsGetName(conss[c])); 11622 /* user not so empathic about AND, or we don't have products of two binaries, so try this more general reformulation */ 11658 SCIPdebugMessage("constraint <%s> is constant and feasible, deleting\n", SCIPconsGetName(conss[c])); 11667 /* try domain propagation if there were bound changes or constraint has changed (in which case, processVarEvents may have set ispropagated to false) */ 11676 SCIPdebugMessage("starting domain propagation round %d of %d\n", roundnr, conshdlrdata->maxproproundspresolve); 11682 SCIPdebugMessage("propagation on constraint <%s> says problem is infeasible in presolve\n", SCIPconsGetName(conss[c])); 11747 SCIPdebugMessage("make variable <%s> implicit integer due to constraint <%s>\n", SCIPvarGetName(candidate), SCIPconsGetName(conss[c])); 11752 SCIPdebugMessage("infeasible upgrade of variable <%s> to integral type, domain is empty\n", SCIPvarGetName(candidate)); 11769 SCIP_CALL( presolveUpgrade(scip, conshdlr, conss[c], &upgraded, nupgdconss, naddconss, presoltiming) ); 11829 /* @todo try to be more clever, but variable locks that depend on the bounds of other variables are not trival to maintain */ 11830 SCIP_CALL( SCIPaddVarLocks(scip, consdata->quadvarterms[i].var, nlockspos+nlocksneg, nlockspos+nlocksneg) ); 11839 { 11998 SCIP_CALL( SCIPwriteVarsPolynomial(scip, file, monomialvars, monomialexps, monomialcoefs, monomialnvars, nmonomials, TRUE) ); 12064 if( SCIPisGT(scip, consdata->lhsviol, SCIPfeastol(scip)) || SCIPisGT(scip, consdata->rhsviol, SCIPfeastol(scip)) ) 12073 SCIPinfoMessage(scip, NULL, "violation: left hand side is violated by %.15g (scaled: %.15g)\n", consdata->lhs - consdata->activity, consdata->lhsviol); 12077 SCIPinfoMessage(scip, NULL, "violation: right hand side is violated by %.15g (scaled: %.15g)\n", consdata->activity - consdata->rhs, consdata->rhsviol); 12085 /* do not try to shift linear variables if activity is at infinity (leads to setting variable to infinity in solution, which is not allowed) */ 12091 /* update information on linear variables that may be in- or decreased, if initsolve has not done so yet */ 12092 if( SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED && SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE ) 12099 if( !(consdata->linvar_mayincrease >= 0 && consdata->lincoefs[consdata->linvar_mayincrease] > 0.0) && 12100 ! (consdata->linvar_maydecrease >= 0 && consdata->lincoefs[consdata->linvar_maydecrease] < 0.0) ) 12108 if( !(consdata->linvar_mayincrease >= 0 && consdata->lincoefs[consdata->linvar_mayincrease] < 0.0) && 12109 ! (consdata->linvar_maydecrease >= 0 && consdata->lincoefs[consdata->linvar_maydecrease] > 0.0) ) 12138 { 12170 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, consdata->linvars[i], &linvars[i], varmap, consmap, global, valid) ); 12189 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, consdata->quadvarterms[i].var, &quadvarterms[i].var, varmap, consmap, global, valid) ); 12283 if( isdigit((unsigned char)str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit((unsigned char)str[1])) ) 12312 SCIP_CALL( SCIPparseVarsPolynomial(scip, str, &monomialvars, &monomialexps, &monomialcoefs, &monomialnvars, &nmonomials, &endptr, success) ); 12436 SCIPfreeParseVarsPolynomialData(scip, &monomialvars, &monomialexps, &monomialcoefs, &monomialnvars, nmonomials); 12472 /** constraint method of constraint handler which returns the number of variables (if possible) */ 12530 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolQuadratic, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 12532 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropQuadratic, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, 12534 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpQuadratic, consSepasolQuadratic, CONSHDLR_SEPAFREQ, 12540 "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)", 12544 "empathy level for using the AND constraint handler: 0 always avoid using AND; 1 use AND sometimes; 2 use AND as often as possible", 12548 "whether to make non-varbound linear constraints added due to replacing products with binary variables initial", 12552 "limit (as factor on 1/feastol) on coefficients and coef. range in linear constraints created when replacing products with binary variables", 12556 "minimal efficacy for a cut to be added to the LP during separation; overwrites separating/efficacy", 12560 "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)", 12564 "whether scaling of infeasibility is 'o'ff, by sup-norm of function 'g'radient, or by left/right hand 's'ide", 12568 "maximal coef range of a cut (maximal coefficient divided by minimal coefficient) in order to be added to LP relaxation", 12572 "whether linearizations of convex quadratic constraints should be added to cutpool in a solution found by some heuristic", 12584 "whether to try to make solutions in check function feasible by shifting a linear variable (esp. useful if constraint was actually objective function)", 12588 "whether to disaggregate quadratic parts that decompose into a sum of non-overlapping quadratic terms", 12592 "limit on number of propagation rounds for a single constraint within one round of SCIP propagation during solve", 12596 "limit on number of propagation rounds for a single constraint within one round of SCIP presolve", 12600 "maximum number of enforcement rounds before declaring the LP relaxation infeasible (-1: no limit); WARNING: changing this parameter might lead to incorrect results!", 12604 "minimal required fraction of continuous variables in problem to use solution of NLP relaxation in root for separation", 12616 "how the interior point should be computed: 'a'ny point per constraint, 'm'ost interior per constraint", 12620 "which score to give branching candidates: convexification 'g'ap, constraint 'v'iolation, 'c'entrality of variable value in domain", 12624 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->eventhdlr),CONSHDLR_NAME"_boundchange", "signals a bound change to a quadratic constraint", 12628 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, NULL, CONSHDLR_NAME"_newsolution", "handles the event that a new primal solution has been found", 12632 SCIP_CALL( SCIPincludeNonlinconsUpgrade(scip, nonlinconsUpgdQuadratic, NULL, NONLINCONSUPGD_PRIORITY, TRUE, CONSHDLR_NAME) ); 12640 SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), /**< method to call for upgrading quadratic constraint */ 12687 for( i = conshdlrdata->nquadconsupgrades; i > 0 && conshdlrdata->quadconsupgrades[i-1]->priority < quadconsupgrade->priority; --i ) 12694 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "constraints/" CONSHDLR_NAME "/upgrade/%s", conshdlrname); 12695 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "enable quadratic upgrading for constraint handler <%s>", conshdlrname); 12712 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 12745 SCIP_Bool removable /**< should the relaxation be removed from the LP due to aging or cleanup? 12775 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 12779 SCIP_CALL( SCIPhashmapCreate(&quadvaridxs, SCIPblkmem(scip), SCIPcalcHashtableSize(5 * nquadterms)) ); 12799 SCIP_CALL( SCIPhashmapInsert(quadvaridxs, quadvars1[i], (void*)(size_t)(consdata->nquadvars-1)) ); 12820 SCIP_CALL( SCIPhashmapInsert(quadvaridxs, quadvars2[i], (void*)(size_t)(consdata->nquadvars-1)) ); 12856 /* if it's a linear coefficient for a quadratic variable, add it there, otherwise add as linear variable */ 12886 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 12914 * \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. 12917 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 12940 SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */ 12965 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 12976 * \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. 12979 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 13004 /** Adds a constant to the constraint function, that is, subtracts a constant from both sides */ 13065 /** Adds a quadratic variable with linear and square coefficient to a quadratic constraint. */ 13137 consdata->ispresolved = consdata->ispresolved && !SCIPisZero(scip, consdata->quadvarterms[pos].lincoef); 13193 consdata->ispresolved = consdata->ispresolved && !SCIPisZero(scip, consdata->quadvarterms[pos].sqrcoef); 13379 * @note If the quadratic variable terms have not been sorted before, then a search may reorder the current order of the terms. 13448 /** Check the quadratic function of a quadratic constraint for its semi-definiteness, if not done yet. */ 13461 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) convex. */ 13478 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) concave. */ 13525 * That is, checks whether each variable with a square term is fixed and for each bilinear term at least one variable is fixed. 13578 SCIP_HASHMAP* scipvar2nlpivar, /**< mapping from SCIP variables to variable indices in NLPI */ 13670 /* if othervar is on position 2, then we process this bilinear term later (or it was processed already) */ 13706 * @note This method may only be called during problem creation stage for an original constraint. 13728 SCIPerrorMessage("method may only be called during problem creation stage for original constraints\n"); 13751 * @note This method may only be called during problem creation stage for an original constraint. 13773 SCIPerrorMessage("method may only be called during problem creation stage for original constraints\n"); 13865 /** changes the linear coefficient value for a given quadratic variable in a quadratic constraint data; if not 13891 if( SCIPgetStage(scip) > SCIP_STAGE_PROBLEM || !SCIPconsIsOriginal(cons) || !SCIPvarIsOriginal(var) ) 13893 SCIPerrorMessage("method may only be called during problem creation stage for original constraints and variables\n"); 13930 /* decrease i by one since otherwise we would skip the coefficient which has been switched to position i */ 13958 /** changes the square coefficient value for a given quadratic variable in a quadratic constraint data; if not 13985 if( SCIPgetStage(scip) > SCIP_STAGE_PROBLEM || !SCIPconsIsOriginal(cons) || !SCIPvarIsOriginal(var) ) 13987 SCIPerrorMessage("method may only be called during problem creation stage for original constraints and variables\n"); 14027 /** changes the bilinear coefficient value for a given quadratic variable in a quadratic constraint data; if not 14056 if( SCIPgetStage(scip) > SCIP_STAGE_PROBLEM || !SCIPconsIsOriginal(cons) || !SCIPvarIsOriginal(var1) || !SCIPvarIsOriginal(var2) ) 14058 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:17352 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:16861 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:2643 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:5625 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:1196 Definition: type_result.h:33 Definition: type_nlpi.h:65 SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name) Definition: scip.c:5878 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:9024 Definition: type_result.h:37 SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans))) Definition: scip.c:5588 static SCIP_DECL_CONSENFOPS(consEnfopsQuadratic) Definition: cons_quadratic.c:11409 Definition: type_expr.h:55 SCIP_BILINTERM * SCIPgetBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13414 static void consdataMoveLinearVar(SCIP_CONSDATA *consdata, int oldpos, int newpos) Definition: cons_quadratic.c:1693 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:9764 static SCIP_RETCODE consdataSortBilinTerms(SCIP *scip, SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:1615 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:7903 static SCIP_DECL_CONSSEPASOL(consSepasolQuadratic) Definition: cons_quadratic.c:11195 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:22886 static SCIP_RETCODE consdataEnsureQuadVarTermsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num) Definition: cons_quadratic.c:1081 static SCIP_DECL_CONSINITSOL(consInitsolQuadratic) Definition: cons_quadratic.c:10587 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:6399 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:9223 SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur) Definition: scip.c:34072 SCIP_RETCODE SCIPgetViolationQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *violation) Definition: cons_quadratic.c:13497 Definition: type_nlpi.h:66 int SCIPexprgraphGetNodeNChildren(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12733 Definition: type_expr.h:63 SCIP_QUADVARTERM * SCIPgetQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13353 void SCIPwarningMessage(SCIP *scip, const char *formatstr,...) Definition: scip.c:1248 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:15737 SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41920 static SCIP_RETCODE replaceQuadVarTermPos(SCIP *scip, SCIP_CONS *cons, int pos, SCIP_VAR *var, SCIP_Real coef, SCIP_Real offset) Definition: cons_quadratic.c:2177 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:5246 void SCIPsortPtrPtrReal(void **ptrarray1, void **ptrarray2, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_RETCODE SCIPaddBilinTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef) Definition: cons_quadratic.c:13207 static SCIP_RETCODE getImpliedBounds(SCIP *scip, SCIP_VAR *x, SCIP_Bool xval, SCIP_VAR *y, SCIP_INTERVAL *resultant) Definition: cons_quadratic.c:3400 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:12982 SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr) Definition: cons.c:4258 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:29365 static SCIP_DECL_CONSSEPALP(consSepalpQuadratic) Definition: cons_quadratic.c:11050 internal methods for NLPI solver interfaces SCIP_RETCODE SCIPchgLhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs) Definition: cons_quadratic.c:13709 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:5334 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:6309 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:2012 SCIP_RETCODE SCIPsortQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13365 SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant) Definition: scip.c:17429 static SCIP_DECL_CONSENABLE(consEnableQuadratic) Definition: cons_quadratic.c:11839 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:6507 SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars))) Definition: scip.c:5818 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:10255 Definition: cons_quadratic.h:75 void SCIPaddSquareLinearization(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success) Definition: scip.c:30454 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:5703 static SCIP_DECL_CONSEXITPRE(consExitpreQuadratic) Definition: cons_quadratic.c:10533 SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize) Definition: misc.c:2057 static SCIP_Real getGradientMaxElement(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol) Definition: cons_quadratic.c:4911 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:7390 SCIP_RETCODE SCIPaddQuadVarLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:13097 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:16027 static SCIP_RETCODE presolveSolve(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result, SCIP_Bool *redundant, int *naggrvars) Definition: cons_quadratic.c:3217 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:7778 SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval) Definition: scip.c:33396 static SCIP_RETCODE registerBranchingCandidatesViolation(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int *nnotify) Definition: cons_quadratic.c:8461 Definition: type_var.h:53 SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse))) Definition: scip.c:5795 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: scip.c:30619 static void consdataFindUnlockedLinearVar(SCIP *scip, SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:10035 static void checkCurvatureEasy(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *determined, SCIP_Bool checkmultivariate) Definition: cons_quadratic.c:4460 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:9536 SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals) Definition: scip.c:27888 static SCIP_RETCODE removeBilinearTermsPos(SCIP *scip, SCIP_CONS *cons, int nterms, int *termposs) Definition: cons_quadratic.c:2447 Definition: type_expr.h:98 static SCIP_RETCODE computeViolation(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SOL *sol) Definition: cons_quadratic.c:4963 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:13067 SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var) Definition: scip.c:34983 Definition: type_expr.h:38 SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom) Definition: misc.c:7620 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:8545 static SCIP_RETCODE presolveTryAddAND(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, int *naddconss) Definition: cons_quadratic.c:3304 Constraint handler for "and" constraints, . SCIP_Bool SCIPisLinearLocalQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13528 SCIP_RETCODE SCIPaddToNlpiProblemQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *scipvar2nlpivar, SCIP_Bool names) Definition: cons_quadratic.c:13574 static SCIP_RETCODE mergeAndCleanBilinearTerms(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:2715 int SCIPgetNLinearVarsNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9524 SCIP_Real SCIPgetRhsNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9623 void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2116 static SCIP_RETCODE chgLinearCoefPos(SCIP *scip, SCIP_CONS *cons, int pos, SCIP_Real newcoef) Definition: cons_quadratic.c:1916 static SCIP_RETCODE propagateBoundsCons(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_RESULT *result, int *nchgbds, SCIP_Bool *redundant) Definition: cons_quadratic.c:9432 static SCIP_DECL_CONSENFOLP(consEnfolpQuadratic) Definition: cons_quadratic.c:11222 Definition: type_message.h:46 SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file) Definition: scip.c:26237 SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible) Definition: scip.c:30967 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:28910 SCIP_Real SCIPgetLhsNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9611 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:12497 SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree))) Definition: scip.c:5359 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:4545 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:7908 Definition: struct_sol.h:50 SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit))) Definition: scip.c:5383 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:3547 SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2159 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:3573 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:12715 SCIP_EXPROP SCIPexprgraphGetNodeOperator(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12793 static SCIP_RETCODE consdataSortQuadVarTerms(SCIP *scip, SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:1451 SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr) Definition: cons.c:3917 Definition: type_expr.h:45 void SCIPaddConstantQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real constant) Definition: cons_quadratic.c:13006 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:36622 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:8632 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:9110 static SCIP_RETCODE checkCurvature(SCIP *scip, SCIP_CONS *cons, SCIP_Bool checkmultivariate) Definition: cons_quadratic.c:4525 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:1781 static SCIP_RETCODE presolveTryAddLinearReform(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, int *naddconss) Definition: cons_quadratic.c:3491 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:5171 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:13450 SCIP_Real * SCIPgetLinearCoefsNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9548 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:17075 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:9297 int SCIPgetNLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13298 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:8075 Definition: type_result.h:35 Definition: struct_cons.h:36 interval arithmetics for provable bounds static SCIP_RETCODE removeFixedVariables(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:2788 void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant) Definition: intervalarith.c:493 #define SCIPfreeBlockMemoryArrayNull(scip, ptr, num) Definition: scip.h:20574 SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19526 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:7669 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:25870 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:10763 SCIP_RETCODE SCIPchgRhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs) Definition: cons_quadratic.c:13754 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:3923 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:5527 SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row) Definition: scip.c:28151 Definition: type_result.h:36 SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub) Definition: scip.c:19717 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:11506 Definition: cons_quadratic.c:176 SCIP_RETCODE SCIPchgSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:13964 constraint handler for quadratic constraints SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre))) Definition: scip.c:5503 #define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum) Definition: scip.h:20562 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:5279 SCIP_RETCODE SCIPfindQuadVarTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, int *pos) Definition: cons_quadratic.c:13382 SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing) Definition: var.c:17367 SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13480 SCIP_RETCODE SCIPaddLinearVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:13042 Definition: type_set.h:41 Definition: type_retcode.h:33 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: scip.c:30522 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:5126 SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming) Definition: scip.c:5292 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:5192 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:2330 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:7563 SCIP_VAR ** SCIPgetLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13312 SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41946 SCIP_EXPRGRAPHNODE * SCIPgetExprgraphNodeNonlinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_nonlinear.c:9599 Definition: struct_heur.h:75 SCIP_RETCODE SCIPgetActivityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *activity) Definition: cons_quadratic.c:13837 Definition: type_lp.h:34 SCIP_RETCODE SCIPsetConshdlrDisable(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDISABLE((*consdisable))) Definition: scip.c:5726 Definition: type_retcode.h:34 static SCIP_RETCODE consdataEnsureAdjBilinSize(SCIP *scip, SCIP_QUADVARTERM *quadvarterm, int num) Definition: cons_quadratic.c:1106 static SCIP_RETCODE proposeFeasibleSolution(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool *success) Definition: cons_quadratic.c:10100 SCIP_Real SCIPexprgraphGetNodeQuadraticConstant(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12896 Ipopt NLP interface. SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible) Definition: scip.c:22681 static SCIP_RETCODE computeInteriorPoint(SCIP *scip, SCIP_CONS *cons, char method, SCIP_Bool *success) Definition: cons_quadratic.c:6878 SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20193 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:8963 SCIP_RETCODE SCIPaddLinearCoefsToNlRow(SCIP *scip, SCIP_NLROW *nlrow, int nvars, SCIP_VAR **vars, SCIP_Real *vals) Definition: scip.c:29587 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:24772 SCIP_Bool SCIPisSumLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41819 static SCIP_DECL_CONSINITLP(consInitlpQuadratic) Definition: cons_quadratic.c:10837 static SCIP_RETCODE presolveDisaggregate(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, int *naddconss) Definition: cons_quadratic.c:4185 SCIP_Bool SCIPexprgraphAreAllNodeChildrenVars(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:14382 static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyQuadratic) Definition: cons_quadratic.c:10435 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:7253 SCIP_RETCODE SCIPgetFeasibilityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *feasibility) Definition: cons_quadratic.c:13796 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:12889 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:22165 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:8245 Definition: struct_lp.h:189 static SCIP_DECL_CONSEXITSOL(consExitsolQuadratic) Definition: cons_quadratic.c:10705 static SCIP_RETCODE replaceByLinearConstraints(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool *addedcons, SCIP_Bool *reduceddom, SCIP_Bool *infeasible) Definition: cons_quadratic.c:8723 SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol) Definition: scip.c:34271 static SCIP_RETCODE registerLargeLPValueVariableForBranching(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_VAR **brvar) Definition: cons_quadratic.c:8671 methods for debugging Definition: type_set.h:38 static void consdataSortLinearVars(SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:1377 Definition: cons_quadratic.h:92 SCIP_Real * SCIPgetCoefsLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13326 Definition: type_set.h:39 Definition: struct_expr.h:115 int SCIPgetNQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13339 SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow) Definition: cons_quadratic.c:13273 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:5611 void SCIPmarkRowNotRemovableLocal(SCIP *scip, SCIP_ROW *row) Definition: scip.c:28027 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:13871 SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var) Definition: var.c:16849 Definition: type_set.h:43 static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata) Definition: cons_quadratic.c:1316 Constraint handler for linear constraints in their most general form, . static SCIP_RETCODE createNlRow(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:3099 static SCIP_Bool consdataCheckBilinTermsSort(SCIP_CONSDATA *consdata) Definition: cons_quadratic.c:1592 SCIP_RETCODE SCIPincSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real incval) Definition: scip.c:34940 Definition: type_nlpi.h:74 void * SCIPexprgraphGetNodeVar(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12825 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:16442 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:5683 void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...) Definition: scip.c:1298 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:5495 SCIP_Real * SCIPexprgraphGetNodeQuadraticLinearCoefs(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12908 SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos) Definition: scip.c:36668 SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete))) Definition: scip.c:5565 Definition: type_set.h:37 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:5431 SCIP_RETCODE SCIPupdateStartpointHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *solcand, SCIP_Real violation) Definition: heur_subnlp.c:2364 static SCIP_RETCODE addBilinearTerm(SCIP *scip, SCIP_CONS *cons, int var1pos, int var2pos, SCIP_Real coef) Definition: cons_quadratic.c:2345 SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos) Definition: scip.c:36588 static void consdataMoveQuadVarTerm(SCIP_CONSDATA *consdata, int oldpos, int newpos) Definition: cons_quadratic.c:1726 SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint))) Definition: scip.c:5772 void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len) Definition: misc.c:3829 Definition: type_expr.h:77 static SCIP_RETCODE consdataCreateEmpty(SCIP *scip, SCIP_CONSDATA **consdata) Definition: cons_quadratic.c:1156 static SCIP_DECL_CONSGETNVARS(consGetNVarsQuadratic) Definition: cons_quadratic.c:12475 Definition: type_nlpi.h:61 SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow) Definition: scip.c:29472 void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...) Definition: scip.c:1281 SCIP_Real SCIPintervalQuadUpperBound(SCIP_Real infinity, SCIP_Real a, SCIP_INTERVAL b_, SCIP_INTERVAL x) Definition: intervalarith.c:2680 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:12444 int SCIPgetNBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13400 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:16099 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:5455 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:6042 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:41933 SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19453 void SCIPfreeParseVarsPolynomialData(SCIP *scip, SCIP_VAR ****monomialvars, SCIP_Real ***monomialexps, SCIP_Real **monomialcoefs, int **monomialnvars, int nmonomials) Definition: scip.c:16794 Definition: type_expr.h:69 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: scip.c:30572 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:3657 SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20299 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:27600 SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur) Definition: scip.c:34044 Definition: struct_nlp.h:62 SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file) Definition: scip.c:28334 SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41959 static SCIP_RETCODE checkFactorable(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:4705 SCIP_RETCODE SCIPincludeQuadconsUpgrade(SCIP *scip, SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), int priority, SCIP_Bool active, const char *conshdlrname) Definition: cons_quadratic.c:12639 #define SCIPduplicateBlockMemoryArray(scip, ptr, source, num) Definition: scip.h:20568 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:12743 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:14033 void SCIPsortInt(int *intarray, int len) SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol) Definition: scip.c:28735 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:8902 static SCIP_RETCODE delLinearCoefPos(SCIP *scip, SCIP_CONS *cons, int pos) Definition: cons_quadratic.c:1847 static SCIP_RETCODE consdataEnsureBilinSize(SCIP *scip, SCIP_CONSDATA *consdata, int num) Definition: cons_quadratic.c:1131 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:19685 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:5407 SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup) Definition: scip.c:19399 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:12920 SCIP_RETCODE SCIPaddSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:13150 SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:42283 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:33701 static SCIP_RETCODE addLinearCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) Definition: cons_quadratic.c:1756 SCIP_RETCODE SCIPaddConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_NODE *validnode) Definition: scip.c:11999 Definition: type_result.h:46 SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing) Definition: var.c:17381 static SCIP_RETCODE delQuadVarTermPos(SCIP *scip, SCIP_CONS *cons, int pos) Definition: cons_quadratic.c:2105 SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image) Definition: misc.c:2094 static SCIP_RETCODE registerBranchingCandidatesGap(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int *nnotify) Definition: cons_quadratic.c:8247 static SCIP_RETCODE presolveDisaggregateMarkComponent(SCIP *scip, SCIP_CONSDATA *consdata, int quadvaridx, SCIP_HASHMAP *var2component, int componentnr) Definition: cons_quadratic.c:4139 SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13426 static SCIP_RETCODE propagateBounds(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_RESULT *result, int *nchgbds) Definition: cons_quadratic.c:9966 int SCIPexprgraphGetNodeQuadraticNQuadElements(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12932 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 Definition: objbranchrule.h:33 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:3629 SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars))) Definition: scip.c:5841 static SCIP_RETCODE consdataFindQuadVarTerm(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR *var, int *pos) Definition: cons_quadratic.c:1520 SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void) Definition: intervalarith.c:196 SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2) Definition: misc.c:7083 static SCIP_RETCODE mergeAndCleanQuadVarTerms(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:2546 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:2797 SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13438 static SCIP_RETCODE consdataEnsureLinearVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num) Definition: cons_quadratic.c:1051 void SCIPintervalSetRoundingModeDownwards(void) Definition: intervalarith.c:390 Definition: type_result.h:39 static SCIP_DECL_CONSDISABLE(consDisableQuadratic) Definition: cons_quadratic.c:11876 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:36554 SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons) Definition: cons_quadratic.c:13463 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:7756 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:12920 Definition: struct_nlpi.h:35 Definition: type_var.h:56 |