cons_linear.c
Go to the documentation of this file.
18 * @brief Constraint handler for linear constraints in their most general form, \f$lhs <= a^T x <= rhs\f$.
48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
93 #define CONSHDLR_ENFOPRIORITY -1000000 /**< priority of the constraint handler for constraint enforcing */
94 #define CONSHDLR_CHECKPRIORITY -1000000 /**< priority of the constraint handler for checking feasibility */
95 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
96 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
97 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
99 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
100 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
101 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
102 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
104 #define CONSHDLR_PRESOLTIMING (SCIP_PRESOLTIMING_FAST | SCIP_PRESOLTIMING_EXHAUSTIVE) /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
114 #define DEFAULT_TIGHTENBOUNDSFREQ 1 /**< multiplier on propagation frequency, how often the bounds are tightened */
115 #define DEFAULT_MAXROUNDS 5 /**< maximal number of separation rounds per node (-1: unlimited) */
116 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
118 #define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of cuts separated per separation round in root node */
119 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
120 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
121 #define DEFAULT_NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
122 #define DEFAULT_MINGAINPERNMINCOMP 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise
124 #define DEFAULT_SORTVARS TRUE /**< should variables be sorted after presolve w.r.t their coefficient absolute for faster
126 #define DEFAULT_CHECKRELMAXABS FALSE /**< should the violation for a constraint with side 0.0 be checked relative
128 #define DEFAULT_MAXAGGRNORMSCALE 0.0 /**< maximal allowed relative gain in maximum norm for constraint aggregation
130 #define DEFAULT_MAXEASYACTIVITYDELTA 1e6 /**< maximum activity delta to run easy propagation on linear constraint
132 #define DEFAULT_MAXCARDBOUNDDIST 0.0 /**< maximal relative distance from current node's dual bound to primal bound compared
134 #define DEFAULT_SEPARATEALL FALSE /**< should all constraints be subject to cardinality cut generation instead of only
136 #define DEFAULT_AGGREGATEVARIABLES TRUE /**< should presolving search for redundant variables in equations */
137 #define DEFAULT_SIMPLIFYINEQUALITIES TRUE /**< should presolving try to simplify inequalities */
139 #define DEFAULT_SINGLETONSTUFFING TRUE /**< should stuffing of singleton continuous variables be performed? */
140 #define DEFAULT_SINGLEVARSTUFFING FALSE /**< should single variable stuffing be performed, which tries to fulfill
142 #define DEFAULT_DETECTCUTOFFBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
145 #define DEFAULT_DETECTLOWERBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
148 #define DEFAULT_DETECTPARTIALOBJECTIVE TRUE/**< should presolving try to detect subsets of constraints parallel to the
151 #define DEFAULT_RANGEDROWARTCONS TRUE /**< should presolving and propagation extract sub-constraints from ranged rows and equations? */
155 #define DEFAULT_MULTAGGRREMOVE FALSE /**< should multi-aggregations only be performed if the constraint can be
157 #define DEFAULT_MAXMULTAGGRQUOT 1e+03 /**< maximum coefficient dynamism (ie. maxabsval / minabsval) for multiaggregation */
158 #define DEFAULT_MAXDUALMULTAGGRQUOT 1e+20 /**< maximum coefficient dynamism (ie. maxabsval / minabsval) for multiaggregation */
163 #define MAXSCALEDCOEFINTEGER 0 /**< maximal coefficient value after scaling if all variables are of integral
170 #define MAXVALRECOMP 1e+06 /**< maximal abolsute value we trust without recomputing the activity */
171 #define MINVALRECOMP 1e-05 /**< minimal abolsute value we trust without recomputing the activity */
174 #define NONLINCONSUPGD_PRIORITY 1000000 /**< priority of the constraint handler for upgrading of expressions constraints */
176 /* @todo add multi-aggregation of variables that are in exactly two equations (, if not numerically an issue),
183 {
188 SCIP_Real minactivity; /**< minimal value w.r.t. the variable's local bounds for the constraint's
190 SCIP_Real maxactivity; /**< maximal value w.r.t. the variable's local bounds for the constraint's
196 SCIP_Real glbminactivity; /**< minimal value w.r.t. the variable's global bounds for the constraint's
198 SCIP_Real glbmaxactivity; /**< maximal value w.r.t. the variable's global bounds for the constraint's
200 SCIP_Real lastglbminactivity; /**< last global minimal activity which was computed by complete summation
202 SCIP_Real lastglbmaxactivity; /**< last global maximal activity which was computed by complete summation
204 SCIP_Real maxactdelta; /**< maximal activity contribution of a single variable, or SCIP_INVALID if invalid */
205 SCIP_VAR* maxactdeltavar; /**< variable with maximal activity contribution, or NULL if invalid */
213 int minactivityneginf; /**< number of coefficients contributing with neg. infinite value to minactivity */
214 int minactivityposinf; /**< number of coefficients contributing with pos. infinite value to minactivity */
215 int maxactivityneginf; /**< number of coefficients contributing with neg. infinite value to maxactivity */
216 int maxactivityposinf; /**< number of coefficients contributing with pos. infinite value to maxactivity */
217 int minactivityneghuge; /**< number of coefficients contributing with huge neg. value to minactivity */
218 int minactivityposhuge; /**< number of coefficients contributing with huge pos. value to minactivity */
219 int maxactivityneghuge; /**< number of coefficients contributing with huge neg. value to maxactivity */
220 int maxactivityposhuge; /**< number of coefficients contributing with huge pos. value to maxactivity */
221 int glbminactivityneginf;/**< number of coefficients contrib. with neg. infinite value to glbminactivity */
222 int glbminactivityposinf;/**< number of coefficients contrib. with pos. infinite value to glbminactivity */
223 int glbmaxactivityneginf;/**< number of coefficients contrib. with neg. infinite value to glbmaxactivity */
224 int glbmaxactivityposinf;/**< number of coefficients contrib. with pos. infinite value to glbmaxactivity */
225 int glbminactivityneghuge;/**< number of coefficients contrib. with huge neg. value to glbminactivity */
226 int glbminactivityposhuge;/**< number of coefficients contrib. with huge pos. value to glbminactivity */
227 int glbmaxactivityneghuge;/**< number of coefficients contrib. with huge neg. value to glbmaxactivity */
228 int glbmaxactivityposhuge;/**< number of coefficients contrib. with huge pos. value to glbmaxactivity */
235 unsigned int rangedrowpropagated:2; /**< did we perform ranged row propagation on this constraint?
247 unsigned int changed:1; /**< was constraint changed since last aggregation round in preprocessing? */
250 unsigned int upgraded:1; /**< is the constraint upgraded and will it be removed after preprocessing? */
255 unsigned int coefsorted:1; /**< are variables sorted by type and their absolute activity delta? */
257 unsigned int hascontvar:1; /**< does the constraint contain at least one continuous variable? */
258 unsigned int hasnonbinvar:1; /**< does the constraint contain at least one non-binary variable? */
259 unsigned int hasnonbinvalid:1; /**< is the information stored in hasnonbinvar and hascontvar valid? */
260 unsigned int checkabsolute:1; /**< should the constraint be checked w.r.t. an absolute feasibilty tolerance? */
275 SCIP_LINCONSUPGRADE** linconsupgrades; /**< linear constraint upgrade methods for specializing linear constraints */
276 SCIP_Real maxaggrnormscale; /**< maximal allowed relative gain in maximum norm for constraint aggregation
278 SCIP_Real maxcardbounddist; /**< maximal relative distance from current node's dual bound to primal bound compared
280 SCIP_Real mingainpernmincomp; /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
281 SCIP_Real maxeasyactivitydelta;/**< maximum activity delta to run easy propagation on linear constraint
285 int tightenboundsfreq; /**< multiplier on propagation frequency, how often the bounds are tightened */
292 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
293 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
294 SCIP_Bool separateall; /**< should all constraints be subject to cardinality cut generation instead of only
296 SCIP_Bool aggregatevariables; /**< should presolving search for redundant variables in equations */
297 SCIP_Bool simplifyinequalities;/**< should presolving try to cancel down or delete coefficients in inequalities */
299 SCIP_Bool singletonstuffing; /**< should stuffing of singleton continuous variables be performed? */
300 SCIP_Bool singlevarstuffing; /**< should single variable stuffing be performed, which tries to fulfill
303 SCIP_Bool checkrelmaxabs; /**< should the violation for a constraint with side 0.0 be checked relative
305 SCIP_Bool detectcutoffbound; /**< should presolving try to detect constraints parallel to the objective
308 SCIP_Bool detectlowerbound; /**< should presolving try to detect constraints parallel to the objective
311 SCIP_Bool detectpartialobjective;/**< should presolving try to detect subsets of constraints parallel to
313 SCIP_Bool rangedrowpropagation;/**< should presolving and propagation try to improve bounds, detect
316 SCIP_Bool rangedrowartcons; /**< should presolving and propagation extract sub-constraints from ranged rows and equations?*/
319 SCIP_Bool multaggrremove; /**< should multi-aggregations only be performed if the constraint can be
321 SCIP_Real maxmultaggrquot; /**< maximum coefficient dynamism (ie. maxabsval / minabsval) for primal multiaggregation */
322 SCIP_Real maxdualmultaggrquot;/**< maximum coefficient dynamism (ie. maxabsval / minabsval) for dual multiaggregation */
345 PROPRULE_1_RANGEDROW = 3, /**< fixed variables and gcd of all left variables tighten bounds of a
360 } asbits;
362 } val;
383 )
425 /** constructs an inference information out of a propagation rule and a position number, returns info as int */
446 )
457 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->linconsupgrades, conshdlrdata->linconsupgradessize, newsize) );
486 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize, newsize) );
542 {
576 SCIPfreeBlockMemoryArrayNull(scip, &(*conshdlrdata)->linconsupgrades, (*conshdlrdata)->linconsupgradessize);
602 SCIPwarningMessage(scip, "Try to add already known upgrade message for constraint handler %s.\n", conshdlrname);
625 SCIP_CALL( conshdlrdataEnsureLinconsupgradesSize(scip, conshdlrdata, conshdlrdata->nlinconsupgrades+1) );
632 assert(0 <= i && i <= conshdlrdata->nlinconsupgrades);
643 /** installs rounding locks for the given variable associated to the given coefficient in the linear constraint */
676 /** removes rounding locks for the given variable associated to the given coefficient in the linear constraint */
770 assert(consdata->eventdata[pos]->cons == cons);
918 if( SCIPisConsCompressionEnabled(scip) && SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) )
960 /* due to compressed copying, we may have fixed variables contributing to the left and right hand side */
1032 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
1116 {
1118 SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, consdata->vars, consdata->vals, consdata->nvars, TRUE) );
1151 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " [%s] <%s>: ", SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), SCIPconsGetName(cons));
1273 bound = (SCIPvarGetBestBoundType(consdata->vars[i]) == SCIP_BOUNDTYPE_LOWER) ? SCIPvarGetLbLocal(consdata->vars[i]) : SCIPvarGetUbLocal(consdata->vars[i]);
1319 bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetLbLocal(consdata->vars[i]) : SCIPvarGetUbLocal(consdata->vars[i]);
1321 && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1346 bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetUbLocal(consdata->vars[i]) : SCIPvarGetLbLocal(consdata->vars[i]);
1348 && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1373 bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetLbGlobal(consdata->vars[i]) : SCIPvarGetUbGlobal(consdata->vars[i]);
1375 && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1400 bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetUbGlobal(consdata->vars[i]) : SCIPvarGetLbGlobal(consdata->vars[i]);
1402 && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1434 }
1458 {
1466 /** checks the type of all variables of the constraint and sets hasnonbinvar and hascontvar flags accordingly */
1487 {
1563 {
1615 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
1667 * lower bound + neg. coef: update maxactivity, positive and negative infinity counters have to be switched
1669 * upper bound + neg. coef: update minactivity, positive and negative infinity counters have to be switched
1723 * lower bound + neg. coef: update maxactivity, positive and negative infinity counters have to be switched
1725 * upper bound + neg. coef: update minactivity, positive and negative infinity counters have to be switched
1793 /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
1821 /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
1846 * but checking here that the bound is not huge again would not handle a change from a huge to an infinite bound
1852 /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
1855 /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
1861 /* if the contribution of this variable is too large and positive, increase the corresponding counter */
1864 /* if the contribution of this variable is too large and negative, increase the corresponding counter */
1879 * but checking here that the bound is not huge again would not handle a change from a huge to an infinite bound
1885 /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
1888 /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
1894 /* if the contribution of this variable is too large and positive, increase the corresponding counter */
1897 /* if the contribution of this variable is too large and negative, increase the corresponding counter */
1949 /* update the activity, if the current value is valid and there was a change in the finite part */
1998 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2007 consdataUpdateActivities(scip, consdata, var, oldlb, newlb, val, SCIP_BOUNDTYPE_LOWER, FALSE, checkreliability);
2009 assert(!SCIPisInfinity(scip, -consdata->minactivity) && !SCIPisInfinity(scip, consdata->minactivity));
2010 assert(!SCIPisInfinity(scip, -consdata->maxactivity) && !SCIPisInfinity(scip, consdata->maxactivity));
2023 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2032 consdataUpdateActivities(scip, consdata, var, oldub, newub, val, SCIP_BOUNDTYPE_UPPER, FALSE, checkreliability);
2034 assert(!SCIPisInfinity(scip, -consdata->minactivity) && !SCIPisInfinity(scip, consdata->minactivity));
2035 assert(!SCIPisInfinity(scip, -consdata->maxactivity) && !SCIPisInfinity(scip, consdata->maxactivity));
2047 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2055 consdataUpdateActivities(scip, consdata, NULL, oldlb, newlb, val, SCIP_BOUNDTYPE_LOWER, TRUE, checkreliability);
2057 assert(!SCIPisInfinity(scip, -consdata->glbminactivity) && !SCIPisInfinity(scip, consdata->glbminactivity));
2058 assert(!SCIPisInfinity(scip, -consdata->glbmaxactivity) && !SCIPisInfinity(scip, consdata->glbmaxactivity));
2060 }
2070 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2078 consdataUpdateActivities(scip, consdata, NULL, oldub, newub, val, SCIP_BOUNDTYPE_UPPER, TRUE, checkreliability);
2080 assert(!SCIPisInfinity(scip, -consdata->glbminactivity) && !SCIPisInfinity(scip, consdata->glbminactivity));
2081 assert(!SCIPisInfinity(scip, -consdata->glbmaxactivity) && !SCIPisInfinity(scip, consdata->glbmaxactivity));
2083 }
2085 /** updates minimum and maximum activity and maximum absolute value for coefficient addition */
2092 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2128 consdataUpdateActivitiesLb(scip, consdata, var, 0.0, SCIPvarGetLbLocal(var), val, checkreliability);
2129 consdataUpdateActivitiesUb(scip, consdata, var, 0.0, SCIPvarGetUbLocal(var), val, checkreliability);
2130 consdataUpdateActivitiesGlbLb(scip, consdata, 0.0, SCIPvarGetLbGlobal(var), val, checkreliability);
2131 consdataUpdateActivitiesGlbUb(scip, consdata, 0.0, SCIPvarGetUbGlobal(var), val, checkreliability);
2135 /** updates minimum and maximum activity for coefficient deletion, invalidates maximum absolute value if necessary */
2142 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2185 consdataUpdateActivitiesLb(scip, consdata, var, SCIPvarGetLbLocal(var), 0.0, val, checkreliability);
2186 consdataUpdateActivitiesUb(scip, consdata, var, SCIPvarGetUbLocal(var), 0.0, val, checkreliability);
2187 consdataUpdateActivitiesGlbLb(scip, consdata, SCIPvarGetLbGlobal(var), 0.0, val, checkreliability);
2188 consdataUpdateActivitiesGlbUb(scip, consdata, SCIPvarGetUbGlobal(var), 0.0, val, checkreliability);
2192 /** updates minimum and maximum activity for coefficient change, invalidates maximum absolute value if necessary */
2200 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2280 /* reset maximal activity delta, so that it will be recalculated on the next real propagation */
2286 /* @todo do something more clever here, e.g. if oldval * newval >= 0, do the update directly */
2312 {
2385 /** gets minimal activity for constraint and given values of counters for infinite and huge contributions
2386 * and (if needed) delta to subtract from stored finite part of activity in case of a residual activity
2399 SCIP_Bool goodrelax, /**< should a good relaxation be computed or are relaxed acticities ignored, anyway? */
2403 SCIP_Bool* issettoinfinity /**< pointer to store whether minactivity was set to infinity or calculated */
2408 assert(posinf >= 0);
2430 /* if we have neg. huge contributions, we only know that -infty is a relaxation of the minactivity */
2437 /* we do not need a good relaxation and we have positive huge contributions, so we just return -infty as activity */
2468 * times the minimum value counting as "huge" plus finite (and non-huge) part of minactivity - delta
2486 /** gets maximal activity for constraint and given values of counters for infinite and huge contributions
2487 * and (if needed) delta to subtract from stored finite part of activity in case of a residual activity
2500 SCIP_Bool goodrelax, /**< should a good relaxation be computed or are relaxed acticities ignored, anyway? */
2504 SCIP_Bool* issettoinfinity /**< pointer to store whether maxactivity was set to infinity or calculated */
2509 assert(posinf >= 0);
2531 /* if we have pos. huge contributions, we only know that +infty is a relaxation of the maxactivity */
2538 /* we do not need a good relaxation and we have positve huge contributions, so we just return +infty as activity */
2569 * times the minimum value counting as "huge" plus the finite (and non-huge) part of maxactivity minus delta
2596 SCIP_Bool* minisrelax, /**< pointer to store whether the returned minactivity is just a relaxation,
2599 SCIP_Bool* maxisrelax, /**< pointer to store whether the returned maxactivity is just a relaxation,
2602 SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minactivity was set to infinity or calculated */
2603 SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxactivity was set to infinity or calculated */
2728 SCIP_Bool* minisrelax, /**< pointer to store whether the returned residual minactivity is just a
2731 SCIP_Bool* maxisrelax, /**< pointer to store whether the returned residual maxactivity is just a
2734 SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2735 SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2783 /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
2784 * and contribution of variable set to zero that has to be subtracted from finite part of activity
2821 consdata->minactivityposhuge, consdata->minactivityneghuge, absval * minactbound, FALSE, goodrelax,
2825 /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
2826 * and contribution of variable set to zero that has to be subtracted from finite part of activity
2863 consdata->maxactivityposhuge, consdata->maxactivityneghuge, absval * maxactbound, FALSE, goodrelax,
2875 SCIP_Real* glbminactivity, /**< pointer to store the minimal activity, or NULL, if not needed */
2876 SCIP_Real* glbmaxactivity, /**< pointer to store the maximal activity, or NULL, if not needed */
2877 SCIP_Bool* minisrelax, /**< pointer to store whether the returned minactivity is just a relaxation,
2880 SCIP_Bool* maxisrelax, /**< pointer to store whether the returned maxactivity is just a relaxation,
2883 SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2884 SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2939 SCIP_Real* minresactivity, /**< pointer to store the minimal residual activity, or NULL, if not needed */
2940 SCIP_Real* maxresactivity, /**< pointer to store the maximal residual activity, or NULL, if not needed */
2941 SCIP_Bool* minisrelax, /**< pointer to store whether the returned residual minactivity is just a
2944 SCIP_Bool* maxisrelax, /**< pointer to store whether the returned residual maxactivity is just a
2947 SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2948 SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2990 /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
2991 * and contribution of variable set to zero that has to be subtracted from finite part of activity
2997 getMinActivity(scip, consdata, consdata->glbminactivityposinf - 1, consdata->glbminactivityneginf,
3005 getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf - 1,
3038 /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
3039 * and contribution of variable set to zero that has to be subtracted from finite part of activity
3045 getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf - 1,
3053 getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf - 1, consdata->glbmaxactivityneginf,
3120 else if( (SCIPisInfinity(scip, solval) && negsign) || (SCIPisInfinity(scip, -solval) && !negsign) )
3127 SCIPdebugMsg(scip, "activity of linear constraint: %.15g, %d positive infinity values, %d negative infinity values \n", activity, nposinf, nneginf);
3216 /** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
3255 /** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
3311 SCIP_Real abscont1 = REALABS(consdata->vals[ind1] * (SCIPvarGetUbGlobal(var1) - SCIPvarGetLbGlobal(var1)));
3312 SCIP_Real abscont2 = REALABS(consdata->vals[ind2] * (SCIPvarGetUbGlobal(var2) - SCIPvarGetLbGlobal(var2)));
3346 {
3396 * sorts variables of the remaining problem by binaries, integers, implicit integers, and continuous variables,
3517 /* the left hand side switched from -infinity to a non-infinite value -> install rounding locks */
3542 /* the left hand side switched from a non-infinite value to -infinity -> remove rounding locks */
3563 /* check whether the left hand side is increased, if and only if that's the case we maybe can propagate, tighten and add more cliques */
3645 /* the right hand side switched from infinity to a non-infinite value -> install rounding locks */
3670 /* the right hand side switched from a non-infinite value to infinity -> remove rounding locks */
3691 /* check whether the right hand side is decreased, if and only if that's the case we maybe can propagate, tighten and add more cliques */
3739 assert(!SCIPvarIsRelaxationOnly(var) || (!SCIPconsIsChecked(cons) && !SCIPconsIsEnforced(cons)));
3854 consdata->indexsorted = consdata->indexsorted && (consdataCompVar((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
3860 consdata->coefsorted = consdata->coefsorted && (consdataCompVarProp((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
3951 /* if at most one variable is left, the activities should be recalculated (to correspond exactly to the bounds
3963 /* if the variable defining the maximal activity delta was removed from the constraint, the maximal activity
4029 assert(0 <= pos && pos < consdata->nvars);
4111 SCIPwarningMessage(scip, "skipped scaling for linear constraint <%s> to avoid numerical troubles (scalar: %.15g)\n",
4122 /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
4130 SCIPwarningMessage(scip, "coefficient %.15g of variable <%s> in linear constraint <%s> scaled to zero (scalar: %.15g)\n",
4152 /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
4164 /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasCeil, we subtract 0.5 before ceiling up
4201 {
4226 * Apply the following rules in the given order, until the sign of the factor is determined. Later rules only apply,
4231 * 4. the number of positive coefficients must not be smaller than the number of negative coefficients
4234 * Try to identify a rational representation of the fractional coefficients, and multiply all coefficients
4325 SCIPdebugMsg(scip, "divide linear constraint with %g, because all coefficients are in absolute value the same\n", maxabsval);
4367 epsilon = SCIPepsilon(scip) * 0.9; /* slightly decrease epsilon to be safe in rational conversion below */
4376 maxmult = MIN(maxmult, (SCIP_Longint) (MAXSCALEDCOEFINTEGER / MAX(maxabsval, 1.0))); /*lint !e835*/
4402 /* 3. the absolute value of the right hand side must be greater than that of the left hand side */
4411 /* 4. the number of positive coefficients must not be smaller than the number of negative coefficients */
4464 /* it might be that we have really big coefficients, but all are integral, in that case we want to divide them by
4484 SCIPdebugMsg(scip, "scale linear constraint with %" SCIP_LONGINT_FORMAT " to make coefficients integral\n", scm);
4533 /* since the lhs/rhs is not respected for gcd calculation it can happen that we detect infeasibility */
4536 if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) && !SCIPisFeasIntegral(scip, consdata->rhs / gcd) )
4540 SCIPdebugMsg(scip, "detected infeasibility of constraint after scaling with gcd=%" SCIP_LONGINT_FORMAT ":\n", gcd);
4548 SCIPdebugMsg(scip, "divide linear constraint by greatest common divisor %" SCIP_LONGINT_FORMAT "\n", gcd);
4621 /* if the variable defining the maximal activity delta was removed from the constraint, the maximal activity
4694 /* if an unmodifiable row has been added to the LP, then we cannot apply fixing anymore (cannot change a row)
4695 * this should not happen, as applyFixings is called in addRelaxation() before creating and adding a row
4697 assert(consdata->row == NULL || !SCIProwIsInLP(consdata->row) || SCIProwIsModifiable(consdata->row));
4850 if( SCIPisEQ(scip, lhssubtrahend, consdata->lhs) && SCIPisFeasGE(scip, REALABS(lhssubtrahend), 1.0) )
4866 if( SCIPisEQ(scip, rhssubtrahend, consdata->rhs ) && SCIPisFeasGE(scip, REALABS(rhssubtrahend), 1.0) )
4880 /* if aggregated variables have been replaced, multiple entries of the same variable are possible and we have
4899 /** for each variable in the linear constraint, except the inferred variable, adds one bound to the conflict analysis'
4900 * candidate store (bound depends on sign of coefficient and whether the left or right hand side was the reason for the
4901 * inference variable's bound change); the conflict analysis can be initialized with the linear constraint being the
4909 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4938 /* for each variable, add the bound to the conflict queue, that is responsible for the minimal or maximal
4939 * residual value, depending on whether the left or right hand side is responsible for the bound change:
4944 /* if the variable is integral we only need to add reason bounds until the propagation could be applied */
4957 /* calculate the minimal and maximal global activity of all other variables involved in the constraint */
4962 consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, &minresactivity, NULL,
4965 consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, NULL, &maxresactivity,
4979 if( (reasonisrhs && !isminsettoinfinity && !minisrelax) || (!reasonisrhs && !ismaxsettoinfinity && !maxisrelax) ) /*lint !e644*/
4986 /* calculate the residual capacity that would be left, if the variable would be set to one more / one less
5041 /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound */
5043 rescap -= vals[i] * (SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetLbGlobal(vars[i]));
5047 /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound */
5049 rescap -= vals[i] * (SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetUbGlobal(vars[i]));
5069 /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound is responsible */
5074 /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound is responsible */
5082 /** for each variable in the linear ranged row constraint, except the inferred variable, adds the bounds of all fixed
5083 * variables to the conflict analysis' candidate store; the conflict analysis can be initialized
5084 * with the linear constraint being the conflict detecting constraint by using NULL as inferred variable
5091 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
5106 nvars = consdata->nvars;
5123 if( !SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetLbGlobal(vars[v])) )
5129 if( !SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetUbGlobal(vars[v])) )
5139 if( SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE)) )
5141 /* add all bounds of fixed variables which lead to the boundchange of the given inference variable */
5171 {
5198 /** resolves a propagation on the given variable by supplying the variables needed for applying the corresponding
5209 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
5210 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
5251 /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
5252 * constraint (only taking the other variables into account) didn't leave enough space for a larger
5261 /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
5262 * constraint (only taking the other variables into account) didn't leave enough space for a larger
5271 /* the bound of the variable was tightened, because some variables were already fixed and the leftover only allow
5283 SCIPerrorMessage("invalid inference information %d in linear constraint <%s> at position %d for %s bound of variable <%s>\n",
5294 /** analyzes conflicting bounds on given constraint, and adds conflict constraint to problem */
5303 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
5309 /* add the conflicting bound for each variable of infeasible constraint to conflict candidate queue */
5357 SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5381 SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, old bds=[%.15g,%.15g], val=%.15g, activity=[%.15g,%.15g], sides=[%.15g,%.15g] -> newub=%.15g\n",
5382 SCIPconsGetName(cons), SCIPvarGetName(var), lb, oldub, consdata->vals[pos], consdata->minactivity, consdata->maxactivity, consdata->lhs, consdata->rhs, newub);
5387 SCIP_CALL( SCIPinferVarUbCons(scip, var, newub, cons, getInferInt(proprule, pos), force, &infeasible, &tightened) );
5426 SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5450 SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, old bds=[%.15g,%.15g], val=%.15g, activity=[%.15g,%.15g], sides=[%.15g,%.15g] -> newlb=%.15g\n",
5451 SCIPconsGetName(cons), SCIPvarGetName(var), oldlb, ub, consdata->vals[pos], consdata->minactivity, consdata->maxactivity, consdata->lhs, consdata->rhs, newlb);
5456 SCIP_CALL( SCIPinferVarLbCons(scip, var, newlb, cons, getInferInt(proprule, pos), force, &infeasible, &tightened) );
5492 SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5552 /* min activity should be valid at this point (if this is not true, then some decisions might be wrong!) */
5555 /* if the minactivity is larger than the right hand side by feasibility epsilon, the constraint is infeasible */
5567 /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5611 /* if the maxactivity is smaller than the left hand side by feasibility epsilon, the constraint is infeasible */
5622 /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5658 /* min activity should be valid at this point (if this is not true, then some decisions might be wrong!) */
5661 /* if the minactivity is larger than the right hand side by feasibility epsilon, the constraint is infeasible */
5673 /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5716 /* if the maxactivity is smaller than the left hand side by feasibility epsilon, the constraint is infeasible */
5728 /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5760 /** analyzes conflicting bounds on given ranged row constraint, and adds conflict constraint to problem */
5783 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
5789 /* add the conflicting fixed variables of this ranged row constraint to conflict candidate queue */
5803 * Check ranged rows for possible solutions, possibly detect infeasibility, fix variables due to having only one possible
5804 * solution, tighten bounds if having only two possible solutions or add constraints which propagate a subset of
5889 addartconss = conshdlrdata->rangedrowartcons && SCIPgetDepth(scip) < 1 && !SCIPinProbing(scip) && !SCIPinRepropagation(scip);
5894 /* we are not allowed to add artificial constraints during propagation; if nothing changed on this constraint since
5895 * the last rangedrowpropagation, we can stop; otherwise, we mark this constraint to be rangedrowpropagated without
5913 if( SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->vars[v]), SCIPvarGetUbLocal(consdata->vars[v])) )
5942 * coefficient so that all variables in this group will have a gcd greater than 1, this group will be implicitly
5945 * the second group will contain all left unfixed variables and will be saved as infcheckvars with corresponding
5946 * coefficients as infcheckvals, the order of these variables should be the same as in the consdata object
5949 /* find first integral variables with integral coefficient greater than 1, thereby collecting all other unfixed
5959 /* partition the variables, do not change the order of collection, because it might be used later on */
5963 if( !SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->vars[v]), SCIPvarGetUbLocal(consdata->vars[v])) )
5991 while( v < consdata->nvars && SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->vars[v]), SCIPvarGetUbLocal(consdata->vars[v])) );
6005 assert(!SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->vars[v]), SCIPvarGetUbLocal(consdata->vars[v])));
6006 assert(SCIPisIntegral(scip, consdata->vals[v]) && SCIPvarGetType(consdata->vars[v]) != SCIP_VARTYPE_CONTINUOUS && REALABS(consdata->vals[v]) > 1.5);