Scippy

SCIP

Solving Constraint Integer Programs

cons_linear.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file cons_linear.c
26  * @ingroup DEFPLUGINS_CONS
27  * @brief Constraint handler for linear constraints in their most general form, \f$lhs <= a^T x <= rhs\f$.
28  * @author Tobias Achterberg
29  * @author Timo Berthold
30  * @author Marc Pfetsch
31  * @author Kati Wolter
32  * @author Michael Winkler
33  * @author Gerald Gamrath
34  * @author Domenico Salvagnin
35  *
36  * Linear constraints are separated with a high priority, because they are easy
37  * to separate. Instead of using the global cut pool, the same effect can be
38  * implemented by adding linear constraints to the root node, such that they are
39  * separated each time, the linear constraints are separated. A constraint
40  * handler, which generates linear constraints in this way should have a lower
41  * separation priority than the linear constraint handler, and it should have a
42  * separation frequency that is a multiple of the frequency of the linear
43  * constraint handler. In this way, it can be avoided to separate the same cut
44  * twice, because if a separation run of the handler is always preceded by a
45  * separation of the linear constraints, the priorily added constraints are
46  * always satisfied.
47  *
48  * Linear constraints are enforced and checked with a very low priority. Checking
49  * of (many) linear constraints is much more involved than checking the solution
50  * values for integrality. Because we are separating the linear constraints quite
51  * often, it is only necessary to enforce them for integral solutions. A constraint
52  * handler which generates pool cuts in its enforcing method should have an
53  * enforcing priority smaller than that of the linear constraint handler to avoid
54  * regenerating constraints which already exist.
55  */
56 
57 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
58 
59 #include "blockmemshell/memory.h"
60 #include "scip/cons_nonlinear.h"
61 #include "scip/cons_knapsack.h"
62 #include "scip/cons_linear.h"
63 #include "scip/debug.h"
64 #include "scip/pub_conflict.h"
65 #include "scip/pub_cons.h"
66 #include "scip/pub_event.h"
67 #include "scip/pub_expr.h"
68 #include "scip/pub_lp.h"
69 #include "scip/pub_message.h"
70 #include "scip/pub_misc.h"
71 #include "scip/pub_misc_sort.h"
72 #include "scip/pub_var.h"
73 #include "scip/scip_branch.h"
74 #include "scip/scip_conflict.h"
75 #include "scip/scip_cons.h"
76 #include "scip/scip_copy.h"
77 #include "scip/scip_cut.h"
78 #include "scip/scip_event.h"
79 #include "scip/scip_general.h"
80 #include "scip/scip_lp.h"
81 #include "scip/scip_mem.h"
82 #include "scip/scip_message.h"
83 #include "scip/scip_numerics.h"
84 #include "scip/scip_param.h"
85 #include "scip/scip_prob.h"
86 #include "scip/scip_probing.h"
87 #include "scip/scip_sol.h"
88 #include "scip/scip_solvingstats.h"
89 #include "scip/scip_tree.h"
90 #include "scip/scip_var.h"
91 #include "scip/dbldblarith.h"
92 
93 
94 #define CONSHDLR_NAME "linear"
95 #define CONSHDLR_DESC "linear constraints of the form lhs <= a^T x <= rhs"
96 #define CONSHDLR_SEPAPRIORITY +100000 /**< priority of the constraint handler for separation */
97 #define CONSHDLR_ENFOPRIORITY -1000000 /**< priority of the constraint handler for constraint enforcing */
98 #define CONSHDLR_CHECKPRIORITY -1000000 /**< priority of the constraint handler for checking feasibility */
99 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
100 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
101 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
102  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
103 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
104 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
105 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
106 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
108 #define CONSHDLR_PRESOLTIMING (SCIP_PRESOLTIMING_FAST | SCIP_PRESOLTIMING_EXHAUSTIVE) /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
109 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
111 #define EVENTHDLR_NAME "linear"
112 #define EVENTHDLR_DESC "bound change event handler for linear constraints"
114 #define CONFLICTHDLR_NAME "linear"
115 #define CONFLICTHDLR_DESC "conflict handler creating linear constraints"
116 #define CONFLICTHDLR_PRIORITY -1000000
118 #define DEFAULT_TIGHTENBOUNDSFREQ 1 /**< multiplier on propagation frequency, how often the bounds are tightened */
119 #define DEFAULT_MAXROUNDS 5 /**< maximal number of separation rounds per node (-1: unlimited) */
120 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
121 #define DEFAULT_MAXSEPACUTS 50 /**< maximal number of cuts separated per separation round */
122 #define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of cuts separated per separation round in root node */
123 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
124 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
125 #define DEFAULT_NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
126 #define DEFAULT_MINGAINPERNMINCOMP 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise
127  * comparison round */
128 #define DEFAULT_SORTVARS TRUE /**< should variables be sorted after presolve w.r.t their coefficient absolute for faster
129  * propagation? */
130 #define DEFAULT_CHECKRELMAXABS FALSE /**< should the violation for a constraint with side 0.0 be checked relative
131  * to 1.0 (FALSE) or to the maximum absolute value in the activity (TRUE)? */
132 #define DEFAULT_MAXAGGRNORMSCALE 0.0 /**< maximal allowed relative gain in maximum norm for constraint aggregation
133  * (0.0: disable constraint aggregation) */
134 #define DEFAULT_MAXEASYACTIVITYDELTA 1e6 /**< maximum activity delta to run easy propagation on linear constraint
135  * (faster, but numerically less stable) */
136 #define DEFAULT_MAXCARDBOUNDDIST 0.0 /**< maximal relative distance from current node's dual bound to primal bound compared
137  * to best node's dual bound for separating knapsack cardinality cuts */
138 #define DEFAULT_SEPARATEALL FALSE /**< should all constraints be subject to cardinality cut generation instead of only
139  * the ones with non-zero dual value? */
140 #define DEFAULT_AGGREGATEVARIABLES TRUE /**< should presolving search for redundant variables in equations */
141 #define DEFAULT_SIMPLIFYINEQUALITIES TRUE /**< should presolving try to simplify inequalities */
142 #define DEFAULT_DUALPRESOLVING TRUE /**< should dual presolving steps be performed? */
143 #define DEFAULT_SINGLETONSTUFFING TRUE /**< should stuffing of singleton continuous variables be performed? */
144 #define DEFAULT_SINGLEVARSTUFFING FALSE /**< should single variable stuffing be performed, which tries to fulfill
145  * constraints using the cheapest variable? */
146 #define DEFAULT_DETECTCUTOFFBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
147  * function defining an upper bound and prevent these constraints from
148  * entering the LP */
149 #define DEFAULT_DETECTLOWERBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
150  * function defining a lower bound and prevent these constraints from
151  * entering the LP */
152 #define DEFAULT_DETECTPARTIALOBJECTIVE TRUE/**< should presolving try to detect subsets of constraints parallel to the
153  * objective function */
154 #define DEFAULT_RANGEDROWPROPAGATION TRUE /**< should we perform ranged row propagation */
155 #define DEFAULT_RANGEDROWARTCONS TRUE /**< should presolving and propagation extract sub-constraints from ranged rows and equations? */
156 #define DEFAULT_RANGEDROWMAXDEPTH INT_MAX /**< maximum depth to apply ranged row propagation */
157 #define DEFAULT_RANGEDROWFREQ 1 /**< frequency for applying ranged row propagation */
158 
159 #define DEFAULT_MULTAGGRREMOVE FALSE /**< should multi-aggregations only be performed if the constraint can be
160  * removed afterwards? */
161 #define DEFAULT_MAXMULTAGGRQUOT 1e+03 /**< maximum coefficient dynamism (ie. maxabsval / minabsval) for multiaggregation */
162 #define DEFAULT_MAXDUALMULTAGGRQUOT 1e+20 /**< maximum coefficient dynamism (ie. maxabsval / minabsval) for multiaggregation */
163 #define DEFAULT_EXTRACTCLIQUES TRUE /**< should cliques be extracted? */
164 
165 #define MAXDNOM 10000LL /**< maximal denominator for simple rational fixed values */
166 #define MAXSCALEDCOEF 0 /**< maximal coefficient value after scaling */
167 #define MAXSCALEDCOEFINTEGER 0 /**< maximal coefficient value after scaling if all variables are of integral
168  * type
169  */
170 #define MAXACTVAL 1e+09 /**< maximal absolute value of full and partial activities such that
171  * redundancy-based simplifications are allowed to be applied
172  */
174 #define MAXVALRECOMP 1e+06 /**< maximal abolsute value we trust without recomputing the activity */
175 #define MINVALRECOMP 1e-05 /**< minimal abolsute value we trust without recomputing the activity */
178 #define NONLINCONSUPGD_PRIORITY 1000000 /**< priority of the constraint handler for upgrading of expressions constraints */
179 
180 /* @todo add multi-aggregation of variables that are in exactly two equations (, if not numerically an issue),
181  * maybe in fullDualPresolve(), see convertLongEquality()
182  */
183 
184 
185 /** constraint data for linear constraints */
186 struct SCIP_ConsData
187 {
188  SCIP_Real lhs; /**< left hand side of row (for ranged rows) */
189  SCIP_Real rhs; /**< right hand side of row */
190  SCIP_Real maxabsval; /**< maximum absolute value of all coefficients */
191  SCIP_Real minabsval; /**< minimal absolute value of all coefficients */
192  QUAD_MEMBER(SCIP_Real minactivity); /**< minimal value w.r.t. the variable's local bounds for the constraint's
193  * activity, ignoring the coefficients contributing with infinite value */
194  QUAD_MEMBER(SCIP_Real maxactivity); /**< maximal value w.r.t. the variable's local bounds for the constraint's
195  * activity, ignoring the coefficients contributing with infinite value */
196  SCIP_Real lastminactivity; /**< last minimal activity which was computed by complete summation
197  * over all contributing values */
198  SCIP_Real lastmaxactivity; /**< last maximal activity which was computed by complete summation
199  * over all contributing values */
200  QUAD_MEMBER(SCIP_Real glbminactivity); /**< minimal value w.r.t. the variable's global bounds for the constraint's
201  * activity, ignoring the coefficients contributing with infinite value */
202  QUAD_MEMBER(SCIP_Real glbmaxactivity); /**< maximal value w.r.t. the variable's global bounds for the constraint's
203  * activity, ignoring the coefficients contributing with infinite value */
204  SCIP_Real lastglbminactivity; /**< last global minimal activity which was computed by complete summation
205  * over all contributing values */
206  SCIP_Real lastglbmaxactivity; /**< last global maximal activity which was computed by complete summation
207  * over all contributing values */
208  SCIP_Real maxactdelta; /**< maximal activity contribution of a single variable, or SCIP_INVALID if invalid */
209  SCIP_VAR* maxactdeltavar; /**< variable with maximal activity contribution, or NULL if invalid */
210  uint64_t possignature; /**< bit signature of coefficients that may take a positive value */
211  uint64_t negsignature; /**< bit signature of coefficients that may take a negative value */
212  SCIP_ROW* row; /**< LP row, if constraint is already stored in LP row format */
213  SCIP_NLROW* nlrow; /**< NLP row, if constraint has been added to NLP relaxation */
214  SCIP_VAR** vars; /**< variables of constraint entries */
215  SCIP_Real* vals; /**< coefficients of constraint entries */
216  SCIP_EVENTDATA** eventdata; /**< event data for bound change events of the variables */
217  int minactivityneginf; /**< number of coefficients contributing with neg. infinite value to minactivity */
218  int minactivityposinf; /**< number of coefficients contributing with pos. infinite value to minactivity */
219  int maxactivityneginf; /**< number of coefficients contributing with neg. infinite value to maxactivity */
220  int maxactivityposinf; /**< number of coefficients contributing with pos. infinite value to maxactivity */
221  int minactivityneghuge; /**< number of coefficients contributing with huge neg. value to minactivity */
222  int minactivityposhuge; /**< number of coefficients contributing with huge pos. value to minactivity */
223  int maxactivityneghuge; /**< number of coefficients contributing with huge neg. value to maxactivity */
224  int maxactivityposhuge; /**< number of coefficients contributing with huge pos. value to maxactivity */
225  int glbminactivityneginf;/**< number of coefficients contrib. with neg. infinite value to glbminactivity */
226  int glbminactivityposinf;/**< number of coefficients contrib. with pos. infinite value to glbminactivity */
227  int glbmaxactivityneginf;/**< number of coefficients contrib. with neg. infinite value to glbmaxactivity */
228  int glbmaxactivityposinf;/**< number of coefficients contrib. with pos. infinite value to glbmaxactivity */
229  int glbminactivityneghuge;/**< number of coefficients contrib. with huge neg. value to glbminactivity */
230  int glbminactivityposhuge;/**< number of coefficients contrib. with huge pos. value to glbminactivity */
231  int glbmaxactivityneghuge;/**< number of coefficients contrib. with huge neg. value to glbmaxactivity */
232  int glbmaxactivityposhuge;/**< number of coefficients contrib. with huge pos. value to glbmaxactivity */
233  int varssize; /**< size of the vars- and vals-arrays */
234  int nvars; /**< number of nonzeros in constraint */
235  int nbinvars; /**< the number of binary variables in the constraint, only valid after
236  * sorting in stage >= SCIP_STAGE_INITSOLVE
237  */
238  unsigned int boundstightened:2; /**< is constraint already propagated with bound tightening? */
239  unsigned int rangedrowpropagated:2; /**< did we perform ranged row propagation on this constraint?
240  * (0: no, 1: yes, 2: with potentially adding artificial constraint */
241  unsigned int validmaxabsval:1; /**< is the maximum absolute value valid? */
242  unsigned int validminabsval:1; /**< is the minimum absolute value valid? */
243  unsigned int validactivities:1; /**< are the activity bounds (local and global) valid? */
244  unsigned int validminact:1; /**< is the local minactivity valid? */
245  unsigned int validmaxact:1; /**< is the local maxactivity valid? */
246  unsigned int validglbminact:1; /**< is the global minactivity valid? */
247  unsigned int validglbmaxact:1; /**< is the global maxactivity valid? */
248  unsigned int presolved:1; /**< is constraint already presolved? */
249  unsigned int removedfixings:1; /**< are all fixed variables removed from the constraint? */
250  unsigned int validsignature:1; /**< is the bit signature valid? */
251  unsigned int changed:1; /**< was constraint changed since last aggregation round in preprocessing? */
252  unsigned int normalized:1; /**< is the constraint in normalized form? */
253  unsigned int upgradetried:1; /**< was the constraint already tried to be upgraded? */
254  unsigned int upgraded:1; /**< is the constraint upgraded and will it be removed after preprocessing? */
255  unsigned int indexsorted:1; /**< are the constraint's variables sorted by type and index? */
256  unsigned int merged:1; /**< are the constraint's equal variables already merged? */
257  unsigned int cliquesadded:1; /**< were the cliques of the constraint already extracted? */
258  unsigned int implsadded:1; /**< were the implications of the constraint already extracted? */
259  unsigned int coefsorted:1; /**< are variables sorted by type and their absolute activity delta? */
260  unsigned int varsdeleted:1; /**< were variables deleted after last cleanup? */
261  unsigned int hascontvar:1; /**< does the constraint contain at least one continuous variable? */
262  unsigned int hasnonbinvar:1; /**< does the constraint contain at least one non-binary variable? */
263  unsigned int hasnonbinvalid:1; /**< is the information stored in hasnonbinvar and hascontvar valid? */
264  unsigned int checkabsolute:1; /**< should the constraint be checked w.r.t. an absolute feasibilty tolerance? */
265 };
266 
267 /** event data for bound change event */
268 struct SCIP_EventData
269 {
270  SCIP_CONS* cons; /**< linear constraint to process the bound change for */
271  int varpos; /**< position of variable in vars array */
272  int filterpos; /**< position of event in variable's event filter */
273 };
274 
275 /** constraint handler data */
276 struct SCIP_ConshdlrData
277 {
278  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
279  SCIP_LINCONSUPGRADE** linconsupgrades; /**< linear constraint upgrade methods for specializing linear constraints */
280  SCIP_Real maxaggrnormscale; /**< maximal allowed relative gain in maximum norm for constraint aggregation
281  * (0.0: disable constraint aggregation) */
282  SCIP_Real maxcardbounddist; /**< maximal relative distance from current node's dual bound to primal bound compared
283  * to best node's dual bound for separating knapsack cardinality cuts */
284  SCIP_Real mingainpernmincomp; /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
285  SCIP_Real maxeasyactivitydelta;/**< maximum activity delta to run easy propagation on linear constraint
286  * (faster, but numerically less stable) */
287  int linconsupgradessize;/**< size of linconsupgrade array */
288  int nlinconsupgrades; /**< number of linear constraint upgrade methods */
289  int tightenboundsfreq; /**< multiplier on propagation frequency, how often the bounds are tightened */
290  int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */
291  int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */
292  int maxsepacuts; /**< maximal number of cuts separated per separation round */
293  int maxsepacutsroot; /**< maximal number of cuts separated per separation round in root node */
294  int nmincomparisons; /**< number for minimal pairwise presolving comparisons */
295  int naddconss; /**< number of added constraints */
296  SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
297  SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
298  SCIP_Bool separateall; /**< should all constraints be subject to cardinality cut generation instead of only
299  * the ones with non-zero dual value? */
300  SCIP_Bool aggregatevariables; /**< should presolving search for redundant variables in equations */
301  SCIP_Bool simplifyinequalities;/**< should presolving try to cancel down or delete coefficients in inequalities */
302  SCIP_Bool dualpresolving; /**< should dual presolving steps be performed? */
303  SCIP_Bool singletonstuffing; /**< should stuffing of singleton continuous variables be performed? */
304  SCIP_Bool singlevarstuffing; /**< should single variable stuffing be performed, which tries to fulfill
305  * constraints using the cheapest variable? */
306  SCIP_Bool sortvars; /**< should binary variables be sorted for faster propagation? */
307  SCIP_Bool checkrelmaxabs; /**< should the violation for a constraint with side 0.0 be checked relative
308  * to 1.0 (FALSE) or to the maximum absolute value in the activity (TRUE)? */
309  SCIP_Bool detectcutoffbound; /**< should presolving try to detect constraints parallel to the objective
310  * function defining an upper bound and prevent these constraints from
311  * entering the LP */
312  SCIP_Bool detectlowerbound; /**< should presolving try to detect constraints parallel to the objective
313  * function defining a lower bound and prevent these constraints from
314  * entering the LP */
315  SCIP_Bool detectpartialobjective;/**< should presolving try to detect subsets of constraints parallel to
316  * the objective function */
317  SCIP_Bool rangedrowpropagation;/**< should presolving and propagation try to improve bounds, detect
318  * infeasibility, and extract sub-constraints from ranged rows and
319  * equations */
320  SCIP_Bool rangedrowartcons; /**< should presolving and propagation extract sub-constraints from ranged rows and equations?*/
321  int rangedrowmaxdepth; /**< maximum depth to apply ranged row propagation */
322  int rangedrowfreq; /**< frequency for applying ranged row propagation */
323  SCIP_Bool multaggrremove; /**< should multi-aggregations only be performed if the constraint can be
324  * removed afterwards? */
325  SCIP_Real maxmultaggrquot; /**< maximum coefficient dynamism (ie. maxabsval / minabsval) for primal multiaggregation */
326  SCIP_Real maxdualmultaggrquot;/**< maximum coefficient dynamism (ie. maxabsval / minabsval) for dual multiaggregation */
327  SCIP_Bool extractcliques; /**< should cliques be extracted? */
328 };
329 
330 /** linear constraint update method */
331 struct SCIP_LinConsUpgrade
332 {
333  SCIP_DECL_LINCONSUPGD((*linconsupgd)); /**< method to call for upgrading linear constraint */
334  int priority; /**< priority of upgrading method */
335  SCIP_Bool active; /**< is upgrading enabled */
336 };
337 
338 
339 /*
340  * Propagation rules
341  */
342 
343 enum Proprule
344 {
345  PROPRULE_1_RHS = 1, /**< activity residuals of all other variables tighten bounds of single
346  * variable due to the right hand side of the inequality */
347  PROPRULE_1_LHS = 2, /**< activity residuals of all other variables tighten bounds of single
348  * variable due to the left hand side of the inequality */
349  PROPRULE_1_RANGEDROW = 3, /**< fixed variables and gcd of all left variables tighten bounds of a
350  * single variable in this reanged row */
351  PROPRULE_INVALID = 0 /**< propagation was applied without a specific propagation rule */
352 };
353 typedef enum Proprule PROPRULE;
355 /** inference information */
356 struct InferInfo
357 {
358  union
359  {
360  struct
361  {
362  unsigned int proprule:8; /**< propagation rule that was applied */
363  unsigned int pos:24; /**< variable position, the propagation rule was applied at */
364  } asbits;
365  int asint; /**< inference information as a single int value */
366  } val;
367 };
368 typedef struct InferInfo INFERINFO;
369 
370 /** converts an integer into an inference information */
371 static
373  int i /**< integer to convert */
374  )
375 {
376  INFERINFO inferinfo;
377 
378  inferinfo.val.asint = i;
379 
380  return inferinfo;
381 }
382 
383 /** converts an inference information into an int */
384 static
385 int inferInfoToInt(
386  INFERINFO inferinfo /**< inference information to convert */
387  )
388 {
389  return inferinfo.val.asint;
390 }
392 /** returns the propagation rule stored in the inference information */
393 static
395  INFERINFO inferinfo /**< inference information to convert */
396  )
397 {
398  return (int) inferinfo.val.asbits.proprule;
399 }
400 
401 /** returns the position stored in the inference information */
402 static
403 int inferInfoGetPos(
404  INFERINFO inferinfo /**< inference information to convert */
405  )
406 {
407  return (int) inferinfo.val.asbits.pos;
408 }
409 
410 /** constructs an inference information out of a propagation rule and a position number */
411 static
413  PROPRULE proprule, /**< propagation rule that deduced the value */
414  int pos /**< variable position, the propagation rule was applied at */
415  )
416 {
417  INFERINFO inferinfo;
418 
419  assert(pos >= 0);
420  /* in the inferinfo struct only 24 bits for 'pos' are reserved */
421  assert(pos < (1<<24));
423  inferinfo.val.asbits.proprule = (unsigned int) proprule; /*lint !e641*/
424  inferinfo.val.asbits.pos = (unsigned int) pos; /*lint !e732*/
425 
426  return inferinfo;
427 }
428 
429 /** constructs an inference information out of a propagation rule and a position number, returns info as int */
430 static
432  PROPRULE proprule, /**< propagation rule that deduced the value */
433  int pos /**< variable position, the propagation rule was applied at */
434  )
435 {
436  return inferInfoToInt(getInferInfo(proprule, pos));
437 }
438 
439 
440 /*
441  * memory growing methods for dynamically allocated arrays
442  */
443 
444 /** ensures, that linconsupgrades array can store at least num entries */
445 static
447  SCIP* scip, /**< SCIP data structure */
448  SCIP_CONSHDLRDATA* conshdlrdata, /**< linear constraint handler data */
449  int num /**< minimum number of entries to store */
450  )
451 {
452  assert(scip != NULL);
453  assert(conshdlrdata != NULL);
454  assert(conshdlrdata->nlinconsupgrades <= conshdlrdata->linconsupgradessize);
455 
456  if( num > conshdlrdata->linconsupgradessize )
457  {
458  int newsize;
459 
460  newsize = SCIPcalcMemGrowSize(scip, num);
461  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->linconsupgrades, conshdlrdata->linconsupgradessize, newsize) );
462  conshdlrdata->linconsupgradessize = newsize;
463  }
464  assert(num <= conshdlrdata->linconsupgradessize);
466  return SCIP_OKAY;
467 }
468 
469 /** ensures, that vars and vals arrays can store at least num entries */
470 static
472  SCIP* scip, /**< SCIP data structure */
473  SCIP_CONSDATA* consdata, /**< linear constraint data */
474  int num /**< minimum number of entries to store */
475  )
476 {
477  assert(scip != NULL);
478  assert(consdata != NULL);
479  assert(consdata->nvars <= consdata->varssize);
480 
481  if( num > consdata->varssize )
482  {
483  int newsize;
484 
485  newsize = SCIPcalcMemGrowSize(scip, num);
486  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
487  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vals, consdata->varssize, newsize) );
488  if( consdata->eventdata != NULL )
489  {
490  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize, newsize) );
491  }
492  consdata->varssize = newsize;
493  }
494  assert(num <= consdata->varssize);
495 
496  return SCIP_OKAY;
497 }
498 
499 
500 /*
501  * local methods for managing linear constraint update methods
502  */
503 
504 /** creates a linear constraint upgrade data object */
505 static
507  SCIP* scip, /**< SCIP data structure */
508  SCIP_LINCONSUPGRADE** linconsupgrade, /**< pointer to store the linear constraint upgrade */
509  SCIP_DECL_LINCONSUPGD((*linconsupgd)), /**< method to call for upgrading linear constraint */
510  int priority /**< priority of upgrading method */
511  )
512 {
513  assert(scip != NULL);
514  assert(linconsupgrade != NULL);
515  assert(linconsupgd != NULL);
516 
517  SCIP_CALL( SCIPallocBlockMemory(scip, linconsupgrade) );
518  (*linconsupgrade)->linconsupgd = linconsupgd;
519  (*linconsupgrade)->priority = priority;
520  (*linconsupgrade)->active = TRUE;
521 
522  return SCIP_OKAY;
523 }
524 
525 /** frees a linear constraint upgrade data object */
526 static
527 void linconsupgradeFree(
528  SCIP* scip, /**< SCIP data structure */
529  SCIP_LINCONSUPGRADE** linconsupgrade /**< pointer to the linear constraint upgrade */
530  )
531 {
532  assert(scip != NULL);
533  assert(linconsupgrade != NULL);
534  assert(*linconsupgrade != NULL);
535 
536  SCIPfreeBlockMemory(scip, linconsupgrade);
537 }
538 
539 /** creates constraint handler data for linear constraint handler */
540 static
542  SCIP* scip, /**< SCIP data structure */
543  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
544  SCIP_EVENTHDLR* eventhdlr /**< event handler */
545  )
546 {
547  assert(scip != NULL);
548  assert(conshdlrdata != NULL);
549  assert(eventhdlr != NULL);
550 
551  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
552  (*conshdlrdata)->linconsupgrades = NULL;
553  (*conshdlrdata)->linconsupgradessize = 0;
554  (*conshdlrdata)->nlinconsupgrades = 0;
555  (*conshdlrdata)->naddconss = 0;
556 
557  /* set event handler for updating linear constraint activity bounds */
558  (*conshdlrdata)->eventhdlr = eventhdlr;
559 
560  return SCIP_OKAY;
561 }
562 
563 /** frees constraint handler data for linear constraint handler */
564 static
565 void conshdlrdataFree(
566  SCIP* scip, /**< SCIP data structure */
567  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
568  )
569 {
570  int i;
571 
572  assert(scip != NULL);
573  assert(conshdlrdata != NULL);
574  assert(*conshdlrdata != NULL);
575 
576  for( i = 0; i < (*conshdlrdata)->nlinconsupgrades; ++i )
577  {
578  linconsupgradeFree(scip, &(*conshdlrdata)->linconsupgrades[i]);
579  }
580  SCIPfreeBlockMemoryArrayNull(scip, &(*conshdlrdata)->linconsupgrades, (*conshdlrdata)->linconsupgradessize);
581 
582  SCIPfreeBlockMemory(scip, conshdlrdata);
583 }
585 /** creates a linear constraint upgrade data object */
586 static
588  SCIP* scip, /**< SCIP data structure */
589  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
590  SCIP_DECL_LINCONSUPGD((*linconsupgd)), /**< method to call for upgrading linear constraint */
591  const char* conshdlrname /**< name of the constraint handler */
592  )
593 {
594  int i;
595 
596  assert(scip != NULL);
597  assert(conshdlrdata != NULL);
598  assert(linconsupgd != NULL);
599  assert(conshdlrname != NULL);
600 
601  for( i = conshdlrdata->nlinconsupgrades - 1; i >= 0; --i )
602  {
603  if( conshdlrdata->linconsupgrades[i]->linconsupgd == linconsupgd )
604  {
605 #ifdef SCIP_DEBUG
606  SCIPwarningMessage(scip, "Try to add already known upgrade message for constraint handler %s.\n", conshdlrname);
607 #endif
608  return TRUE;
609  }
610  }
611 
612  return FALSE;
613 }
614 
615 /** adds a linear constraint update method to the constraint handler's data */
616 static
618  SCIP* scip, /**< SCIP data structure */
619  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
620  SCIP_LINCONSUPGRADE* linconsupgrade /**< linear constraint upgrade method */
621  )
622 {
623  int i;
624 
625  assert(scip != NULL);
626  assert(conshdlrdata != NULL);
627  assert(linconsupgrade != NULL);
628 
629  SCIP_CALL( conshdlrdataEnsureLinconsupgradesSize(scip, conshdlrdata, conshdlrdata->nlinconsupgrades+1) );
630 
631  for( i = conshdlrdata->nlinconsupgrades;
632  i > 0 && conshdlrdata->linconsupgrades[i-1]->priority < linconsupgrade->priority; --i )
633  {
634  conshdlrdata->linconsupgrades[i] = conshdlrdata->linconsupgrades[i-1];
635  }
636  assert(0 <= i && i <= conshdlrdata->nlinconsupgrades);
637  conshdlrdata->linconsupgrades[i] = linconsupgrade;
638  conshdlrdata->nlinconsupgrades++;
639 
640  return SCIP_OKAY;
641 }
642 
643 /*
644  * local methods
645  */
646 
647 /** installs rounding locks for the given variable associated to the given coefficient in the linear constraint */
648 static
650  SCIP* scip, /**< SCIP data structure */
651  SCIP_CONS* cons, /**< linear constraint */
652  SCIP_VAR* var, /**< variable of constraint entry */
653  SCIP_Real val /**< coefficient of constraint entry */
654  )
655 {
656  SCIP_CONSDATA* consdata;
657 
658  assert(scip != NULL);
659  assert(cons != NULL);
660  assert(var != NULL);
661 
662  consdata = SCIPconsGetData(cons);
663  assert(consdata != NULL);
664  assert(!SCIPisZero(scip, val));
665 
666  if( SCIPisPositive(scip, val) )
667  {
668  SCIP_CALL( SCIPlockVarCons(scip, var, cons,
669  !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
670  }
671  else
672  {
673  SCIP_CALL( SCIPlockVarCons(scip, var, cons,
674  !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
675  }
676 
677  return SCIP_OKAY;
678 }
679 
680 /** removes rounding locks for the given variable associated to the given coefficient in the linear constraint */
681 static
683  SCIP* scip, /**< SCIP data structure */
684  SCIP_CONS* cons, /**< linear constraint */
685  SCIP_VAR* var, /**< variable of constraint entry */
686  SCIP_Real val /**< coefficient of constraint entry */
687  )
688 {
689  SCIP_CONSDATA* consdata;
690 
691  assert(scip != NULL);
692  assert(cons != NULL);
693  assert(var != NULL);
694 
695  consdata = SCIPconsGetData(cons);
696  assert(consdata != NULL);
697  assert(!SCIPisZero(scip, val));
698 
699  if( SCIPisPositive(scip, val) )
700  {
701  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, -consdata->lhs),
702  !SCIPisInfinity(scip, consdata->rhs)) );
703  }
704  else
705  {
706  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, consdata->rhs),
707  !SCIPisInfinity(scip, -consdata->lhs)) );
708  }
709 
710  return SCIP_OKAY;
711 }
712 
713 /** creates event data for variable at given position, and catches events */
714 /**! [SnippetDebugAssertions] */
715 static
717  SCIP* scip, /**< SCIP data structure */
718  SCIP_CONS* cons, /**< linear constraint */
719  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
720  int pos /**< array position of variable to catch bound change events for */
721  )
722 {
723  SCIP_CONSDATA* consdata;
724  assert(scip != NULL);
725  assert(cons != NULL);
726  assert(eventhdlr != NULL);
727 
728  consdata = SCIPconsGetData(cons);
729  assert(consdata != NULL);
730 
731  assert(0 <= pos && pos < consdata->nvars);
732  assert(consdata->vars != NULL);
733  assert(consdata->vars[pos] != NULL);
734  assert(SCIPvarIsTransformed(consdata->vars[pos]));
735  assert(consdata->eventdata != NULL);
736  assert(consdata->eventdata[pos] == NULL);
737 
738  SCIP_CALL( SCIPallocBlockMemory(scip, &(consdata->eventdata[pos])) ); /*lint !e866*/
739  consdata->eventdata[pos]->cons = cons;
740  consdata->eventdata[pos]->varpos = pos;
741 
742  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[pos],
745  eventhdlr, consdata->eventdata[pos], &consdata->eventdata[pos]->filterpos) );
746 
747  consdata->removedfixings = consdata->removedfixings && SCIPvarIsActive(consdata->vars[pos]);
748 
749  return SCIP_OKAY;
750 }
751 /**! [SnippetDebugAssertions] */
752 
753 /** deletes event data for variable at given position, and drops events */
754 static
756  SCIP* scip, /**< SCIP data structure */
757  SCIP_CONS* cons, /**< linear constraint */
758  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
759  int pos /**< array position of variable to catch bound change events for */
760  )
761 {
762  SCIP_CONSDATA* consdata;
763  assert(scip != NULL);
764  assert(cons != NULL);
765  assert(eventhdlr != NULL);
766 
767  consdata = SCIPconsGetData(cons);
768  assert(consdata != NULL);
769 
770  assert(0 <= pos && pos < consdata->nvars);
771  assert(consdata->vars[pos] != NULL);
772  assert(consdata->eventdata != NULL);
773  assert(consdata->eventdata[pos] != NULL);
774  assert(consdata->eventdata[pos]->cons == cons);
775  assert(consdata->eventdata[pos]->varpos == pos);
776 
777  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos],
780  eventhdlr, consdata->eventdata[pos], consdata->eventdata[pos]->filterpos) );
781 
782  SCIPfreeBlockMemory(scip, &consdata->eventdata[pos]); /*lint !e866*/
783 
784  return SCIP_OKAY;
785 }
786 
787 /** catches bound change events for all variables in transformed linear constraint */
788 static
790  SCIP* scip, /**< SCIP data structure */
791  SCIP_CONS* cons, /**< linear constraint */
792  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
793  )
794 {
795  SCIP_CONSDATA* consdata;
796  int i;
797 
798  assert(scip != NULL);
799  assert(cons != NULL);
800 
801  consdata = SCIPconsGetData(cons);
802  assert(consdata != NULL);
803  assert(consdata->eventdata == NULL);
804 
805  /* allocate eventdata array */
806  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize) );
807  assert(consdata->eventdata != NULL);
808  BMSclearMemoryArray(consdata->eventdata, consdata->nvars);
809 
810  /* catch event for every single variable */
811  for( i = 0; i < consdata->nvars; ++i )
812  {
813  SCIP_CALL( consCatchEvent(scip, cons, eventhdlr, i) );
814  }
815 
816  return SCIP_OKAY;
817 }
818 
819 /** drops bound change events for all variables in transformed linear constraint */
820 static
822  SCIP* scip, /**< SCIP data structure */
823  SCIP_CONS* cons, /**< linear constraint */
824  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
825  )
826 {
827  SCIP_CONSDATA* consdata;
828  int i;
829 
830  assert(scip != NULL);
831  assert(cons != NULL);
832 
833  consdata = SCIPconsGetData(cons);
834  assert(consdata != NULL);
835  assert(consdata->eventdata != NULL);
836 
837  /* drop event of every single variable */
838  for( i = consdata->nvars - 1; i >= 0; --i )
839  {
840  SCIP_CALL( consDropEvent(scip, cons, eventhdlr, i) );
841  }
842 
843  /* free eventdata array */
844  SCIPfreeBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize);
845  assert(consdata->eventdata == NULL);
846 
847  return SCIP_OKAY;
848 }
849 
850 /** creates a linear constraint data */
851 static
853  SCIP* scip, /**< SCIP data structure */
854  SCIP_CONSDATA** consdata, /**< pointer to linear constraint data */
855  int nvars, /**< number of nonzeros in the constraint */
856  SCIP_VAR** vars, /**< array with variables of constraint entries */
857  SCIP_Real* vals, /**< array with coefficients of constraint entries */
858  SCIP_Real lhs, /**< left hand side of row */
859  SCIP_Real rhs /**< right hand side of row */
860  )
861 {
862  int v;
863  SCIP_Real constant;
864 
865  assert(scip != NULL);
866  assert(consdata != NULL);
867  assert(nvars == 0 || vars != NULL);
868  assert(nvars == 0 || vals != NULL);
869 
870  if( SCIPisInfinity(scip, rhs) )
871  rhs = SCIPinfinity(scip);
872  else if( SCIPisInfinity(scip, -rhs) )
873  rhs = -SCIPinfinity(scip);
874 
875  if( SCIPisInfinity(scip, -lhs) )
876  lhs = -SCIPinfinity(scip);
877  else if( SCIPisInfinity(scip, lhs) )
878  lhs = SCIPinfinity(scip);
879 
880  if( SCIPisGT(scip, lhs, rhs) )
881  {
882  SCIPwarningMessage(scip, "left hand side of linear constraint greater than right hand side\n");
883  SCIPwarningMessage(scip, " -> lhs=%g, rhs=%g\n", lhs, rhs);
884  }
885 
886  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
887 
888  (*consdata)->varssize = 0;
889  (*consdata)->nvars = nvars;
890  (*consdata)->hascontvar = FALSE;
891  (*consdata)->hasnonbinvar = FALSE;
892  (*consdata)->hasnonbinvalid = TRUE;
893  (*consdata)->vars = NULL;
894  (*consdata)->vals = NULL;
895 
896  constant = 0.0;
897  if( nvars > 0 )
898  {
899  int k;
900 
901  SCIP_VAR** varsbuffer;
902  SCIP_Real* valsbuffer;
903 
904  /* copy variables into temporary buffer */
905  SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) );
906  SCIP_CALL( SCIPallocBufferArray(scip, &valsbuffer, nvars) );
907  k = 0;
908 
909  /* loop over variables and sort out fixed ones */
910  for( v = 0; v < nvars; ++v )
911  {
912  SCIP_VAR* var;
913  SCIP_Real val;
914 
915  var = vars[v];
916  val = vals[v];
917 
918  assert(var != NULL);
919  if( !SCIPisZero(scip, val) )
920  {
921  /* treat fixed variable as a constant if problem compression is enabled */
923  {
924  constant += SCIPvarGetLbGlobal(var) * val;
925  }
926  else
927  {
928  varsbuffer[k] = var;
929  valsbuffer[k] = val;
930  k++;
931 
932  /* update hascontvar and hasnonbinvar flags */
933  if( !(*consdata)->hascontvar )
934  {
935  SCIP_VARTYPE vartype = SCIPvarGetType(var);
936 
937  if( vartype != SCIP_VARTYPE_BINARY )
938  {
939  (*consdata)->hasnonbinvar = TRUE;
940 
941  if( vartype == SCIP_VARTYPE_CONTINUOUS )
942  (*consdata)->hascontvar = TRUE;
943  }
944  }
945  }
946  }
947  }
948  (*consdata)->nvars = k;
949 
950  if( k > 0 )
951  {
952  /* copy the possibly reduced buffer arrays into block */
953  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, k) );
954  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vals, valsbuffer, k) );
955  (*consdata)->varssize = k;
956  }
957  /* free temporary buffer */
958  SCIPfreeBufferArray(scip, &valsbuffer);
959  SCIPfreeBufferArray(scip, &varsbuffer);
960  }
961 
962  (*consdata)->eventdata = NULL;
963 
964  /* due to compressed copying, we may have fixed variables contributing to the left and right hand side */
965  if( !SCIPisZero(scip, constant) )
966  {
967  if( !SCIPisInfinity(scip, REALABS(lhs)) )
968  lhs -= constant;
969 
970  if( !SCIPisInfinity(scip, REALABS(rhs)) )
971  rhs -= constant;
972  }
973 
974  (*consdata)->row = NULL;
975  (*consdata)->nlrow = NULL;
976  (*consdata)->lhs = lhs;
977  (*consdata)->rhs = rhs;
978  (*consdata)->maxabsval = SCIP_INVALID;
979  (*consdata)->minabsval = SCIP_INVALID;
980  QUAD_ASSIGN((*consdata)->minactivity, SCIP_INVALID);
981  QUAD_ASSIGN((*consdata)->maxactivity, SCIP_INVALID);
982  (*consdata)->lastminactivity = SCIP_INVALID;
983  (*consdata)->lastmaxactivity = SCIP_INVALID;
984  (*consdata)->maxactdelta = SCIP_INVALID;
985  (*consdata)->maxactdeltavar = NULL;
986  (*consdata)->minactivityneginf = -1;
987  (*consdata)->minactivityposinf = -1;
988  (*consdata)->maxactivityneginf = -1;
989  (*consdata)->maxactivityposinf = -1;
990  (*consdata)->minactivityneghuge = -1;
991  (*consdata)->minactivityposhuge = -1;
992  (*consdata)->maxactivityneghuge = -1;
993  (*consdata)->maxactivityposhuge = -1;
994  QUAD_ASSIGN((*consdata)->glbminactivity, SCIP_INVALID);
995  QUAD_ASSIGN((*consdata)->glbmaxactivity, SCIP_INVALID);
996  (*consdata)->lastglbminactivity = SCIP_INVALID;
997  (*consdata)->lastglbmaxactivity = SCIP_INVALID;
998  (*consdata)->glbminactivityneginf = -1;
999  (*consdata)->glbminactivityposinf = -1;
1000  (*consdata)->glbmaxactivityneginf = -1;
1001  (*consdata)->glbmaxactivityposinf = -1;
1002  (*consdata)->glbminactivityneghuge = -1;
1003  (*consdata)->glbminactivityposhuge = -1;
1004  (*consdata)->glbmaxactivityneghuge = -1;
1005  (*consdata)->glbmaxactivityposhuge = -1;
1006  (*consdata)->possignature = 0;
1007  (*consdata)->negsignature = 0;
1008  (*consdata)->validmaxabsval = FALSE;
1009  (*consdata)->validminabsval = FALSE;
1010  (*consdata)->validactivities = FALSE;
1011  (*consdata)->validminact = FALSE;
1012  (*consdata)->validmaxact = FALSE;
1013  (*consdata)->validglbminact = FALSE;
1014  (*consdata)->validglbmaxact = FALSE;
1015  (*consdata)->boundstightened = 0;
1016  (*consdata)->presolved = FALSE;
1017  (*consdata)->removedfixings = FALSE;
1018  (*consdata)->validsignature = FALSE;
1019  (*consdata)->changed = TRUE;
1020  (*consdata)->normalized = FALSE;
1021  (*consdata)->upgradetried = FALSE;
1022  (*consdata)->upgraded = FALSE;
1023  (*consdata)->indexsorted = (nvars <= 1);
1024  (*consdata)->merged = (nvars <= 1);
1025  (*consdata)->cliquesadded = FALSE;
1026  (*consdata)->implsadded = FALSE;
1027  (*consdata)->coefsorted = FALSE;
1028  (*consdata)->nbinvars = -1;
1029  (*consdata)->varsdeleted = FALSE;
1030  (*consdata)->rangedrowpropagated = 0;
1031  (*consdata)->checkabsolute = FALSE;
1032 
1033  if( SCIPisTransformed(scip) )
1034  {
1035  /* get transformed variables */
1036  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
1037  }
1038 
1039  /* capture variables */
1040  for( v = 0; v < (*consdata)->nvars; v++ )
1041  {
1042  /* likely implies a deleted variable */
1043  if( (*consdata)->vars[v] == NULL )
1044  {
1045  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
1046  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vals, (*consdata)->varssize);
1047  SCIPfreeBlockMemory(scip, consdata);
1048  return SCIP_INVALIDDATA;
1049  }
1050 
1051  assert(!SCIPisZero(scip, (*consdata)->vals[v]));
1052  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
1053  }
1054 
1055  return SCIP_OKAY;
1056 }
1057 
1058 /** frees a linear constraint data */
1059 static
1061  SCIP* scip, /**< SCIP data structure */
1062  SCIP_CONSDATA** consdata /**< pointer to linear constraint data */
1063  )
1064 {
1065  int v;
1066 
1067  assert(scip != NULL);
1068  assert(consdata != NULL);
1069  assert(*consdata != NULL);
1070  assert((*consdata)->varssize >= 0);
1071 
1072  /* release the row */
1073  if( (*consdata)->row != NULL )
1074  {
1075  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
1076  }
1077 
1078  /* release the nlrow */
1079  if( (*consdata)->nlrow != NULL )
1080  {
1081  SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow) );
1082  }
1083 
1084  /* release variables */
1085  for( v = 0; v < (*consdata)->nvars; v++ )
1086  {
1087  assert((*consdata)->vars[v] != NULL);
1088  assert(!SCIPisZero(scip, (*consdata)->vals[v]));
1089  SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
1090  }
1091 
1092  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
1093  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vals, (*consdata)->varssize);
1094  SCIPfreeBlockMemory(scip, consdata);
1095 
1096  return SCIP_OKAY;
1097 }
1098 
1099 /** prints linear constraint in CIP format to file stream */
1100 static
1102  SCIP* scip, /**< SCIP data structure */
1103  SCIP_CONSDATA* consdata, /**< linear constraint data */
1104  FILE* file /**< output file (or NULL for standard output) */
1105  )
1106 {
1107  assert(scip != NULL);
1108  assert(consdata != NULL);
1109 
1110  /* print left hand side for ranged rows */
1111  if( !SCIPisInfinity(scip, -consdata->lhs)
1112  && !SCIPisInfinity(scip, consdata->rhs)
1113  && !SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
1114  SCIPinfoMessage(scip, file, "%.15g <= ", consdata->lhs);
1115 
1116  /* print coefficients and variables */
1117  if( consdata->nvars == 0 )
1118  SCIPinfoMessage(scip, file, "0");
1119  else
1120  {
1121  /* post linear sum of the linear constraint */
1122  SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, consdata->vars, consdata->vals, consdata->nvars, TRUE) );
1123  }
1124 
1125  /* print right hand side */
1126  if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
1127  SCIPinfoMessage(scip, file, " == %.15g", consdata->rhs);
1128  else if( !SCIPisInfinity(scip, consdata->rhs) )
1129  SCIPinfoMessage(scip, file, " <= %.15g", consdata->rhs);
1130  else if( !SCIPisInfinity(scip, -consdata->lhs) )
1131  SCIPinfoMessage(scip, file, " >= %.15g", consdata->lhs);
1132  else
1133  SCIPinfoMessage(scip, file, " [free]");
1134 
1135  return SCIP_OKAY;
1136 }
1137 
1138 /** prints linear constraint and contained solution values of variables to file stream */
1139 static
1141  SCIP* scip, /**< SCIP data structure */
1142  SCIP_CONS* cons, /**< linear constraint */
1143  SCIP_SOL* sol, /**< solution to print */
1144  FILE* file /**< output file (or NULL for standard output) */
1145  )
1146 {
1147  SCIP_CONSDATA* consdata;
1148 
1149  assert(scip != NULL);
1150  assert(cons != NULL);
1151 
1152  consdata = SCIPconsGetData(cons);
1153  assert(consdata != NULL);
1154 
1156 
1157  /* print left hand side for ranged rows */
1158  if( !SCIPisInfinity(scip, -consdata->lhs)
1159  && !SCIPisInfinity(scip, consdata->rhs)
1160  && !SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
1161  SCIPinfoMessage(scip, file, "%.15g <= ", consdata->lhs);
1162 
1163  /* print coefficients and variables */
1164  if( consdata->nvars == 0 )
1165  SCIPinfoMessage(scip, file, "0");
1166  else
1167  {
1168  int v;
1169 
1170  /* post linear sum of the linear constraint */
1171  for( v = 0; v < consdata->nvars; ++v )
1172  {
1173  if( consdata->vals != NULL )
1174  {
1175  if( consdata->vals[v] == 1.0 )
1176  {
1177  if( v > 0 )
1178  SCIPinfoMessage(scip, file, " +");
1179  }
1180  else if( consdata->vals[v] == -1.0 )
1181  SCIPinfoMessage(scip, file, " -");
1182  else
1183  SCIPinfoMessage(scip, file, " %+.9g", consdata->vals[v]);
1184  }
1185  else if( consdata->nvars > 0 )
1186  SCIPinfoMessage(scip, file, " +");
1187 
1188  /* print variable name */
1189  SCIP_CALL( SCIPwriteVarName(scip, file, consdata->vars[v], TRUE) );
1190 
1191  SCIPinfoMessage(scip, file, " (%+.9g)", SCIPgetSolVal(scip, sol, consdata->vars[v]));
1192  }
1193  }
1194 
1195  /* print right hand side */
1196  if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
1197  SCIPinfoMessage(scip, file, " == %.15g", consdata->rhs);
1198  else if( !SCIPisInfinity(scip, consdata->rhs) )
1199  SCIPinfoMessage(scip, file, " <= %.15g", consdata->rhs);
1200  else if( !SCIPisInfinity(scip, -consdata->lhs) )
1201  SCIPinfoMessage(scip, file, " >= %.15g", consdata->lhs);
1202  else
1203  SCIPinfoMessage(scip, file, " [free]");
1204 
1205  SCIPinfoMessage(scip, file, ";\n");
1206 
1207  return SCIP_OKAY;
1208 }
1209 
1210 /** invalidates activity bounds, such that they are recalculated in next get */
1211 static
1213  SCIP_CONSDATA* consdata /**< linear constraint */
1214  )
1215 {
1216  assert(consdata != NULL);
1217 
1218  consdata->validactivities = FALSE;
1219  consdata->validminact = FALSE;
1220  consdata->validmaxact = FALSE;
1221  consdata->validglbminact = FALSE;
1222  consdata->validglbmaxact = FALSE;
1223  consdata->validmaxabsval = FALSE;
1224  consdata->validminabsval = FALSE;
1225  consdata->hasnonbinvalid = FALSE;
1226  QUAD_ASSIGN(consdata->minactivity, SCIP_INVALID);
1227  QUAD_ASSIGN(consdata->maxactivity, SCIP_INVALID);
1228  consdata->lastminactivity = SCIP_INVALID;
1229  consdata->lastmaxactivity = SCIP_INVALID;
1230  consdata->maxabsval = SCIP_INVALID;
1231  consdata->minabsval = SCIP_INVALID;
1232  consdata->maxactdelta = SCIP_INVALID;
1233  consdata->maxactdeltavar = NULL;
1234  consdata->minactivityneginf = -1;
1235  consdata->minactivityposinf = -1;
1236  consdata->maxactivityneginf = -1;
1237  consdata->maxactivityposinf = -1;
1238  consdata->minactivityneghuge = -1;
1239  consdata->minactivityposhuge = -1;
1240  consdata->maxactivityneghuge = -1;
1241  consdata->maxactivityposhuge = -1;
1242  QUAD_ASSIGN(consdata->glbminactivity, SCIP_INVALID);
1243  QUAD_ASSIGN(consdata->glbmaxactivity, SCIP_INVALID);
1244  consdata->lastglbminactivity = SCIP_INVALID;
1245  consdata->lastglbmaxactivity = SCIP_INVALID;
1246  consdata->glbminactivityneginf = -1;
1247  consdata->glbminactivityposinf = -1;
1248  consdata->glbmaxactivityneginf = -1;
1249  consdata->glbmaxactivityposinf = -1;
1250  consdata->glbminactivityneghuge = -1;
1251  consdata->glbminactivityposhuge = -1;
1252  consdata->glbmaxactivityneghuge = -1;
1253  consdata->glbmaxactivityposhuge = -1;
1254 }
1255 
1256 /** compute the pseudo activity of a constraint */
1257 static
1259  SCIP* scip, /**< SCIP data structure */
1260  SCIP_CONSDATA* consdata /**< linear constraint data */
1261  )
1262 {
1263  int i;
1264  int pseudoactivityposinf;
1265  int pseudoactivityneginf;
1266  SCIP_Real pseudoactivity;
1267  SCIP_Real bound;
1268  SCIP_Real val;
1269 
1270  pseudoactivity = 0;
1271  pseudoactivityposinf = 0;
1272  pseudoactivityneginf = 0;
1273 
1274  for( i = consdata->nvars - 1; i >= 0; --i )
1275  {
1276  val = consdata->vals[i];
1277  bound = (SCIPvarGetBestBoundType(consdata->vars[i]) == SCIP_BOUNDTYPE_LOWER) ? SCIPvarGetLbLocal(consdata->vars[i]) : SCIPvarGetUbLocal(consdata->vars[i]);
1278  if( SCIPisInfinity(scip, bound) )
1279  {
1280  if( val > 0.0 )
1281  pseudoactivityposinf++;
1282  else
1283  pseudoactivityneginf++;
1284  }
1285  else
1286  {
1287  if( SCIPisInfinity(scip, -bound) )
1288  {
1289  if( val > 0.0 )
1290  pseudoactivityneginf++;
1291  else
1292  pseudoactivityposinf++;
1293  }
1294  else
1295  pseudoactivity += val * bound;
1296  }
1297  }
1298 
1299  if( pseudoactivityneginf > 0 && pseudoactivityposinf > 0 )
1300  return SCIP_INVALID;
1301  else if( pseudoactivityneginf > 0 )
1302  return -SCIPinfinity(scip);
1303  else if( pseudoactivityposinf > 0 )
1304  return SCIPinfinity(scip);
1305 
1306  return pseudoactivity;
1307 }
1308 
1309 /** recompute the minactivity of a constraint */
1310 static
1312  SCIP* scip, /**< SCIP data structure */
1313  SCIP_CONSDATA* consdata /**< linear constraint data */
1314  )
1315 {
1316  int i;
1317  SCIP_Real bound;
1318 
1319  QUAD_ASSIGN(consdata->minactivity, 0.0);
1320 
1321  for( i = consdata->nvars - 1; i >= 0; --i )
1322  {
1323  bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetLbLocal(consdata->vars[i]) : SCIPvarGetUbLocal(consdata->vars[i]);
1324  if( !SCIPisInfinity(scip, bound) && !SCIPisInfinity(scip, -bound)
1325  && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1326  SCIPquadprecSumQD(consdata->minactivity, consdata->minactivity, consdata->vals[i] * bound);
1327  }
1328 
1329  /* the activity was just computed from scratch and is valid now */
1330  consdata->validminact = TRUE;
1331 
1332  /* the activity was just computed from scratch, mark it to be reliable */
1333  consdata->lastminactivity = QUAD_TO_DBL(consdata->minactivity);
1334 }
1335 
1336 /** recompute the maxactivity of a constraint */
1337 static
1339  SCIP* scip, /**< SCIP data structure */
1340  SCIP_CONSDATA* consdata /**< linear constraint data */
1341  )
1342 {
1343  int i;
1344  SCIP_Real bound;
1345 
1346  QUAD_ASSIGN(consdata->maxactivity, 0.0);
1347 
1348  for( i = consdata->nvars - 1; i >= 0; --i )
1349  {
1350  bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetUbLocal(consdata->vars[i]) : SCIPvarGetLbLocal(consdata->vars[i]);
1351  if( !SCIPisInfinity(scip, bound) && !SCIPisInfinity(scip, -bound)
1352  && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1353  SCIPquadprecSumQD(consdata->maxactivity, consdata->maxactivity, consdata->vals[i] * bound);
1354  }
1355 
1356  /* the activity was just computed from scratch and is valid now */
1357  consdata->validmaxact = TRUE;
1358 
1359  /* the activity was just computed from scratch, mark it to be reliable */
1360  consdata->lastmaxactivity = QUAD_TO_DBL(consdata->maxactivity);
1361 }
1362 
1363 /** recompute the global minactivity of a constraint */
1364 static
1366  SCIP* scip, /**< SCIP data structure */
1367  SCIP_CONSDATA* consdata /**< linear constraint data */
1368  )
1369 {
1370  int i;
1371  SCIP_Real bound;
1372 
1373  QUAD_ASSIGN(consdata->glbminactivity, 0.0);
1374 
1375  for( i = consdata->nvars - 1; i >= 0; --i )
1376  {
1377  bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetLbGlobal(consdata->vars[i]) : SCIPvarGetUbGlobal(consdata->vars[i]);
1378  if( !SCIPisInfinity(scip, bound) && !SCIPisInfinity(scip, -bound)
1379  && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1380  SCIPquadprecSumQD(consdata->glbminactivity, consdata->glbminactivity, consdata->vals[i] * bound);
1381  }
1382 
1383  /* the activity was just computed from scratch and is valid now */
1384  consdata->validglbminact = TRUE;
1385 
1386  /* the activity was just computed from scratch, mark it to be reliable */
1387  consdata->lastglbminactivity = QUAD_TO_DBL(consdata->glbminactivity);
1388 }
1389 
1390 /** recompute the global maxactivity of a constraint */
1391 static
1393  SCIP* scip, /**< SCIP data structure */
1394  SCIP_CONSDATA* consdata /**< linear constraint data */
1395  )
1396 {
1397  int i;
1398  SCIP_Real bound;
1399 
1400  QUAD_ASSIGN(consdata->glbmaxactivity, 0.0);
1401 
1402  for( i = consdata->nvars - 1; i >= 0; --i )
1403  {
1404  bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetUbGlobal(consdata->vars[i]) : SCIPvarGetLbGlobal(consdata->vars[i]);
1405  if( !SCIPisInfinity(scip, bound) && !SCIPisInfinity(scip, -bound)
1406  && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1407  SCIPquadprecSumQD(consdata->glbmaxactivity, consdata->glbmaxactivity, consdata->vals[i] * bound);
1408  }
1409 
1410  /* the activity was just computed from scratch and is valid now */
1411  consdata->validglbmaxact = TRUE;
1412 
1413  /* the activity was just computed from scratch, mark it to be reliable */
1414  consdata->lastglbmaxactivity = QUAD_TO_DBL(consdata->glbmaxactivity);
1415 }
1416 
1417 /** calculates maximum absolute value of coefficients */
1418 static
1420  SCIP_CONSDATA* consdata /**< linear constraint data */
1421  )
1422 {
1423  SCIP_Real absval;
1424  int i;
1425 
1426  assert(consdata != NULL);
1427  assert(!consdata->validmaxabsval);
1428  assert(consdata->maxabsval >= SCIP_INVALID);
1429 
1430  consdata->validmaxabsval = TRUE;
1431  consdata->maxabsval = 0.0;
1432  for( i = 0; i < consdata->nvars; ++i )
1433  {
1434  absval = consdata->vals[i];
1435  absval = REALABS(absval);
1436  if( absval > consdata->maxabsval )
1437  consdata->maxabsval = absval;
1438  }
1439 }
1440 
1441 /** calculates minimum absolute value of coefficients */
1442 static
1444  SCIP_CONSDATA* consdata /**< linear constraint data */
1445  )
1446 {
1447  SCIP_Real absval;
1448  int i;
1449 
1450  assert(consdata != NULL);
1451  assert(!consdata->validminabsval);
1452  assert(consdata->minabsval >= SCIP_INVALID);
1453 
1454  consdata->validminabsval = TRUE;
1455 
1456  if( consdata->nvars > 0 )
1457  consdata->minabsval = REALABS(consdata->vals[0]);
1458  else
1459  consdata->minabsval = 0.0;
1460 
1461  for( i = 1; i < consdata->nvars; ++i )
1462  {
1463  absval = consdata->vals[i];
1464  absval = REALABS(absval);
1465  if( absval < consdata->minabsval )
1466  consdata->minabsval = absval;
1467  }
1468 }
1469 
1470 /** checks the type of all variables of the constraint and sets hasnonbinvar and hascontvar flags accordingly */
1471 static
1473  SCIP_CONSDATA* consdata /**< linear constraint data */
1474  )
1475 {
1476  int v;
1477 
1478  assert(!consdata->hasnonbinvalid);
1479  consdata->hasnonbinvar = FALSE;
1480  consdata->hascontvar = FALSE;
1481 
1482  for( v = consdata->nvars - 1; v >= 0; --v )
1483  {
1484  SCIP_VARTYPE vartype = SCIPvarGetType(consdata->vars[v]);
1485 
1486  if( vartype != SCIP_VARTYPE_BINARY )
1487  {
1488  consdata->hasnonbinvar = TRUE;
1489 
1490  if( vartype == SCIP_VARTYPE_CONTINUOUS )
1491  {
1492  consdata->hascontvar = TRUE;
1493  break;
1494  }
1495  }
1496  }
1497  assert(consdata->hascontvar || v < 0);
1498 
1499  consdata->hasnonbinvalid = TRUE;
1500 }
1501 
1502 
1503 #ifdef CHECKMAXACTDELTA
1504 /** checks that the stored maximal activity delta (if not invalid) is correct */
1505 static
1507  SCIP* scip, /**< SCIP data structure */
1508  SCIP_CONSDATA* consdata /**< linear constraint data */
1509  )
1510 {
1511  if( consdata->maxactdelta != SCIP_INVALID )
1512  {
1513  SCIP_Real maxactdelta = 0.0;
1514  SCIP_Real domain;
1515  SCIP_Real delta;
1516  SCIP_Real lb;
1517  SCIP_Real ub;
1518  int v;
1519 
1520  for( v = consdata->nvars - 1; v >= 0; --v )
1521  {
1522  lb = SCIPvarGetLbLocal(consdata->vars[v]);
1523  ub = SCIPvarGetUbLocal(consdata->vars[v]);
1524 
1525  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
1526  {
1527  maxactdelta = SCIPinfinity(scip);
1528  break;
1529  }
1530 
1531  domain = ub - lb;
1532  delta = REALABS(consdata->vals[v]) * domain;
1533 
1534  if( delta > maxactdelta )
1535  {
1536  maxactdelta = delta;
1537  }
1538  }
1539  assert(SCIPisFeasEQ(scip, maxactdelta, consdata->maxactdelta));
1540  }
1541 }
1542 #else
1543 #define checkMaxActivityDelta(scip, consdata) /**/
1544 #endif
1545 
1546 /** recompute maximal activity contribution for a single variable */
1547 static
1549  SCIP* scip, /**< SCIP data structure */
1550  SCIP_CONSDATA* consdata /**< linear constraint data */
1551  )
1552 {
1553  SCIP_Real delta;
1554  int v;
1555 
1556  consdata->maxactdelta = 0.0;
1557 
1558  if( !consdata->hasnonbinvalid )
1559  consdataCheckNonbinvar(consdata);
1560 
1561  /* easy case, the problem consists only of binary variables */
1562  if( !consdata->hasnonbinvar )
1563  {
1564  for( v = consdata->nvars - 1; v >= 0; --v )
1565  {
1566  if( SCIPvarGetLbLocal(consdata->vars[v]) < 0.5 && SCIPvarGetUbLocal(consdata->vars[v]) > 0.5 )
1567  {
1568  delta = REALABS(consdata->vals[v]);
1569 
1570  if( delta > consdata->maxactdelta )
1571  {
1572  consdata->maxactdelta = delta;
1573  consdata->maxactdeltavar = consdata->vars[v];
1574  }
1575  }
1576  }
1577  return;
1578  }
1579 
1580  for( v = consdata->nvars - 1; v >= 0; --v )
1581  {
1582  SCIP_Real domain;
1583  SCIP_Real lb;
1584  SCIP_Real ub;
1585 
1586  lb = SCIPvarGetLbLocal(consdata->vars[v]);
1587  ub = SCIPvarGetUbLocal(consdata->vars[v]);
1588 
1589  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
1590  {
1591  consdata->maxactdelta = SCIPinfinity(scip);
1592  consdata->maxactdeltavar = consdata->vars[v];
1593  break;
1594  }
1595 
1596  domain = ub - lb;
1597  delta = REALABS(consdata->vals[v]) * domain;
1598 
1599  if( delta > consdata->maxactdelta )
1600  {
1601  consdata->maxactdelta = delta;
1602  consdata->maxactdeltavar = consdata->vars[v];
1603  }
1604  }
1605 }
1606 
1607 
1608 /** updates activities for a change in a bound */
1609 static
1611  SCIP* scip, /**< SCIP data structure */
1612  SCIP_CONSDATA* consdata, /**< linear constraint data */
1613  SCIP_VAR* var, /**< variable that has been changed; can be NULL for global bound changes */
1614  SCIP_Real oldbound, /**< old bound of variable */
1615  SCIP_Real newbound, /**< new bound of variable */
1616  SCIP_Real val, /**< coefficient of constraint entry */
1617  SCIP_BOUNDTYPE boundtype, /**< type of the bound change */
1618  SCIP_Bool global, /**< is it a global or a local bound change? */
1619  SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
1620  )
1621 {
1622  QUAD_MEMBER(SCIP_Real* activity);
1623  SCIP_Real* lastactivity;
1624  int* activityposinf;
1625  int* activityneginf;
1626  int* activityposhuge;
1627  int* activityneghuge;
1628  SCIP_Real oldcontribution;
1629  SCIP_Real newcontribution;
1630  SCIP_Real delta;
1631  SCIP_Bool validact;
1632  SCIP_Bool finitenewbound;
1633  SCIP_Bool hugevalnewcont;
1634 
1635  assert(scip != NULL);
1636  assert(consdata != NULL);
1637  assert(global || (var != NULL));
1638  assert(consdata->validactivities);
1639  assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
1640  assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
1641  assert(consdata->lastminactivity < SCIP_INVALID);
1642  assert(consdata->lastmaxactivity < SCIP_INVALID);
1643  assert(consdata->minactivityneginf >= 0);
1644  assert(consdata->minactivityposinf >= 0);
1645  assert(consdata->maxactivityneginf >= 0);
1646  assert(consdata->maxactivityposinf >= 0);
1647  assert(consdata->minactivityneghuge >= 0);
1648  assert(consdata->minactivityposhuge >= 0);
1649  assert(consdata->maxactivityneghuge >= 0);
1650  assert(consdata->maxactivityposhuge >= 0);
1651  assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
1652  assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
1653  assert(consdata->lastglbminactivity < SCIP_INVALID);
1654  assert(consdata->lastglbmaxactivity < SCIP_INVALID);
1655  assert(consdata->glbminactivityneginf >= 0);
1656  assert(consdata->glbminactivityposinf >= 0);
1657  assert(consdata->glbmaxactivityneginf >= 0);
1658  assert(consdata->glbmaxactivityposinf >= 0);
1659  assert(consdata->glbminactivityneghuge >= 0);
1660  assert(consdata->glbminactivityposhuge >= 0);
1661  assert(consdata->glbmaxactivityneghuge >= 0);
1662  assert(consdata->glbmaxactivityposhuge >= 0);
1663 
1664  delta = 0.0;
1665 
1666  /* we are updating global activities */
1667  if( global )
1668  {
1669  /* depending on the boundtype and the coefficient, we choose the activity to be updated:
1670  * lower bound + pos. coef: update minactivity
1671  * lower bound + neg. coef: update maxactivity, positive and negative infinity counters have to be switched
1672  * upper bound + pos. coef: update maxactivity
1673  * upper bound + neg. coef: update minactivity, positive and negative infinity counters have to be switched
1674  */
1675  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1676  {
1677  if( val > 0.0 )
1678  {
1679  QUAD_ASSIGN_Q(activity, &consdata->glbminactivity);
1680  lastactivity = &(consdata->lastglbminactivity);
1681  activityposinf = &(consdata->glbminactivityposinf);
1682  activityneginf = &(consdata->glbminactivityneginf);
1683  activityposhuge = &(consdata->glbminactivityposhuge);
1684  activityneghuge = &(consdata->glbminactivityneghuge);
1685  validact = consdata->validglbminact;
1686  }
1687  else
1688  {
1689  QUAD_ASSIGN_Q(activity, &consdata->glbmaxactivity);
1690  lastactivity = &(consdata->lastglbmaxactivity);
1691  activityposinf = &(consdata->glbmaxactivityneginf);
1692  activityneginf = &(consdata->glbmaxactivityposinf);
1693  activityposhuge = &(consdata->glbmaxactivityposhuge);
1694  activityneghuge = &(consdata->glbmaxactivityneghuge);
1695  validact = consdata->validglbmaxact;
1696  }
1697  }
1698  else
1699  {
1700  if( val > 0.0 )
1701  {
1702  QUAD_ASSIGN_Q(activity, &consdata->glbmaxactivity);
1703  lastactivity = &(consdata->lastglbmaxactivity);
1704  activityposinf = &(consdata->glbmaxactivityposinf);
1705  activityneginf = &(consdata->glbmaxactivityneginf);
1706  activityposhuge = &(consdata->glbmaxactivityposhuge);
1707  activityneghuge = &(consdata->glbmaxactivityneghuge);
1708  validact = consdata->validglbmaxact;
1709  }
1710  else
1711  {
1712  QUAD_ASSIGN_Q(activity, &consdata->glbminactivity);
1713  lastactivity = &(consdata->lastglbminactivity);
1714  activityposinf = &(consdata->glbminactivityneginf);
1715  activityneginf = &(consdata->glbminactivityposinf);
1716  activityposhuge = &(consdata->glbminactivityposhuge);
1717  activityneghuge = &(consdata->glbminactivityneghuge);
1718  validact = consdata->validglbminact;
1719  }
1720  }
1721  }
1722  /* we are updating local activities */
1723  else
1724  {
1725  /* depending on the boundtype and the coefficient, we choose the activity to be updated:
1726  * lower bound + pos. coef: update minactivity
1727  * lower bound + neg. coef: update maxactivity, positive and negative infinity counters have to be switched
1728  * upper bound + pos. coef: update maxactivity
1729  * upper bound + neg. coef: update minactivity, positive and negative infinity counters have to be switched
1730  */
1731  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1732  {
1733  if( val > 0.0 )
1734  {
1735  QUAD_ASSIGN_Q(activity, &consdata->minactivity);
1736  lastactivity = &(consdata->lastminactivity);
1737  activityposinf = &(consdata->minactivityposinf);
1738  activityneginf = &(consdata->minactivityneginf);
1739  activityposhuge = &(consdata->minactivityposhuge);
1740  activityneghuge = &(consdata->minactivityneghuge);
1741  validact = consdata->validminact;
1742  }
1743  else
1744  {
1745  QUAD_ASSIGN_Q(activity, &consdata->maxactivity);
1746  lastactivity = &(consdata->lastmaxactivity);
1747  activityposinf = &(consdata->maxactivityneginf);
1748  activityneginf = &(consdata->maxactivityposinf);
1749  activityposhuge = &(consdata->maxactivityposhuge);
1750  activityneghuge = &(consdata->maxactivityneghuge);
1751  validact = consdata->validmaxact;
1752  }
1753  }
1754  else
1755  {
1756  if( val > 0.0 )
1757  {
1758  QUAD_ASSIGN_Q(activity, &consdata->maxactivity);
1759  lastactivity = &(consdata->lastmaxactivity);
1760  activityposinf = &(consdata->maxactivityposinf);
1761  activityneginf = &(consdata->maxactivityneginf);
1762  activityposhuge = &(consdata->maxactivityposhuge);
1763  activityneghuge = &(consdata->maxactivityneghuge);
1764  validact = consdata->validmaxact;
1765  }
1766  else
1767  {
1768  QUAD_ASSIGN_Q(activity, &consdata->minactivity);
1769  lastactivity = &(consdata->lastminactivity);
1770  activityposinf = &(consdata->minactivityneginf);
1771  activityneginf = &(consdata->minactivityposinf);
1772  activityposhuge = &(consdata->minactivityposhuge);
1773  activityneghuge = &(consdata->minactivityneghuge);
1774  validact = consdata->validminact;
1775  }
1776  }
1777  }
1778 
1779  oldcontribution = val * oldbound;
1780  newcontribution = val * newbound;
1781  hugevalnewcont = SCIPisHugeValue(scip, REALABS(newcontribution));
1782  finitenewbound = !SCIPisInfinity(scip, REALABS(newbound));
1783 
1784  if( SCIPisInfinity(scip, REALABS(oldbound)) )
1785  {
1786  /* old bound was +infinity */
1787  if( oldbound > 0.0 )
1788  {
1789  assert((*activityposinf) >= 1);
1790 
1791  /* we only have to do something if the new bound is not again +infinity */
1792  if( finitenewbound || newbound < 0.0 )
1793  {
1794  /* decrease the counter for positive infinite contributions */
1795  (*activityposinf)--;
1796 
1797  /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
1798  if( !finitenewbound && newbound < 0.0 )
1799  (*activityneginf)++;
1800  else if( hugevalnewcont )
1801  {
1802  /* if the contribution of this variable is too large, increase the counter for huge values */
1803  if( newcontribution > 0.0 )
1804  (*activityposhuge)++;
1805  else
1806  (*activityneghuge)++;
1807  }
1808  /* "normal case": just add the contribution to the activity */
1809  else
1810  delta = newcontribution;
1811  }
1812  }
1813  /* old bound was -infinity */
1814  else
1815  {
1816  assert(oldbound < 0.0);
1817  assert((*activityneginf) >= 1);
1818 
1819  /* we only have to do something ig the new bound is not again -infinity */
1820  if( finitenewbound || newbound > 0.0 )
1821  {
1822  /* decrease the counter for negative infinite contributions */
1823  (*activityneginf)--;
1824 
1825  /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
1826  if( !finitenewbound && newbound > 0.0 )
1827  (*activityposinf)++;
1828  else if( hugevalnewcont )
1829  {
1830  /* if the contribution of this variable is too large, increase the counter for huge values */
1831  if( newcontribution > 0.0 )
1832  (*activityposhuge)++;
1833  else
1834  (*activityneghuge)++;
1835  }
1836  /* "normal case": just add the contribution to the activity */
1837  else
1838  delta = newcontribution;
1839  }
1840  }
1841  }
1842  else if( SCIPisHugeValue(scip, REALABS(oldcontribution)) )
1843  {
1844  /* old contribution was too large and positive */
1845  if( oldcontribution > 0.0 )
1846  {
1847  assert((*activityposhuge) >= 1);
1848 
1849  /* decrease the counter for huge positive contributions; it might be increased again later,
1850  * but checking here that the bound is not huge again would not handle a change from a huge to an infinite bound
1851  */
1852  (*activityposhuge)--;
1853 
1854  if( !finitenewbound )
1855  {
1856  /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
1857  if( newbound > 0.0 )
1858  (*activityposinf)++;
1859  /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
1860  else
1861  (*activityneginf)++;
1862  }
1863  else if( hugevalnewcont )
1864  {
1865  /* if the contribution of this variable is too large and positive, increase the corresponding counter */
1866  if( newcontribution > 0.0 )
1867  (*activityposhuge)++;
1868  /* if the contribution of this variable is too large and negative, increase the corresponding counter */
1869  else
1870  (*activityneghuge)++;
1871  }
1872  /* "normal case": just add the contribution to the activity */
1873  else
1874  delta = newcontribution;
1875  }
1876  /* old contribution was too large and negative */
1877  else
1878  {
1879  assert(oldcontribution < 0.0);
1880  assert((*activityneghuge) >= 1);
1881 
1882  /* decrease the counter for huge negative contributions; it might be increased again later,
1883  * but checking here that the bound is not huge again would not handle a change from a huge to an infinite bound
1884  */
1885  (*activityneghuge)--;
1886 
1887  if( !finitenewbound )
1888  {
1889  /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
1890  if( newbound > 0.0 )
1891  (*activityposinf)++;
1892  /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
1893  else
1894  (*activityneginf)++;
1895  }
1896  else if( hugevalnewcont )
1897  {
1898  /* if the contribution of this variable is too large and positive, increase the corresponding counter */
1899  if( newcontribution > 0.0 )
1900  (*activityposhuge)++;
1901  /* if the contribution of this variable is too large and negative, increase the corresponding counter */
1902  else
1903  (*activityneghuge)++;
1904  }
1905  /* "normal case": just add the contribution to the activity */
1906  else
1907  delta = newcontribution;
1908  }
1909  }
1910  /* old bound was finite and not too large */
1911  else
1912  {
1913  if( !finitenewbound )
1914  {
1915  /* if the new bound is +infinity, the old contribution has to be subtracted
1916  * and the counter for positive infinite contributions has to be increased
1917  */
1918  if( newbound > 0.0 )
1919  {
1920  (*activityposinf)++;
1921  delta = -oldcontribution;
1922  }
1923  /* if the new bound is -infinity, the old contribution has to be subtracted
1924  * and the counter for negative infinite contributions has to be increased
1925  */
1926  else
1927  {
1928  assert(newbound < 0.0 );
1929 
1930  (*activityneginf)++;
1931  delta = -oldcontribution;
1932  }
1933  }
1934  /* if the contribution of this variable is too large, increase the counter for huge values */
1935  else if( hugevalnewcont )
1936  {
1937  if( newcontribution > 0.0 )
1938  {
1939  (*activityposhuge)++;
1940  delta = -oldcontribution;
1941  }
1942  else
1943  {
1944  (*activityneghuge)++;
1945  delta = -oldcontribution;
1946  }
1947  }
1948  /* "normal case": just update the activity */
1949  else
1950  delta = newcontribution - oldcontribution;
1951  }
1952 
1953  /* update the activity, if the current value is valid and there was a change in the finite part */
1954  if( validact && (delta != 0.0) )
1955  {
1956  SCIP_Real curractivity;
1957 
1958  /* if the absolute value of the activity is increased, this is regarded as reliable,
1959  * otherwise, we check whether we can still trust the updated value
1960  */
1961  SCIPquadprecSumQD(*activity, *activity, delta);
1962 
1963  curractivity = QUAD_TO_DBL(*activity);
1964  assert(!SCIPisInfinity(scip, -curractivity) && !SCIPisInfinity(scip, curractivity));
1965 
1966  if( REALABS((*lastactivity)) < REALABS(curractivity) )
1967  {
1968  (*lastactivity) = curractivity;
1969  }
1970  else
1971  {
1972  if( checkreliability && SCIPisUpdateUnreliable(scip, curractivity, (*lastactivity)) )
1973  {
1974  SCIPdebugMsg(scip, "%s activity of linear constraint unreliable after update: %16.9g\n",
1975  (global ? "global " : ""), curractivity);
1976 
1977  /* mark the activity that was just changed and is not reliable anymore to be invalid */
1978  if( global )
1979  {
1980  if( (boundtype == SCIP_BOUNDTYPE_LOWER) == (val > 0.0) )
1981  consdata->validglbminact = FALSE;
1982  else
1983  consdata->validglbmaxact = FALSE;
1984  }
1985  else
1986  {
1987  if( (boundtype == SCIP_BOUNDTYPE_LOWER) == (val > 0.0) )
1988  consdata->validminact = FALSE;
1989  else
1990  consdata->validmaxact = FALSE;
1991  }
1992  }
1993  }
1994  }
1995 }
1996 
1997 /** updates minimum and maximum activity for a change in lower bound */
1998 static
2000  SCIP* scip, /**< SCIP data structure */
2001  SCIP_CONSDATA* consdata, /**< linear constraint data */
2002  SCIP_VAR* var, /**< variable that has been changed */
2003  SCIP_Real oldlb, /**< old lower bound of variable */
2004  SCIP_Real newlb, /**< new lower bound of variable */
2005  SCIP_Real val, /**< coefficient of constraint entry */
2006  SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2007  )
2008 {
2009  assert(scip != NULL);
2010  assert(consdata != NULL);
2011  assert(var != NULL);
2012 
2013  if( consdata->validactivities )
2014  {
2015  consdataUpdateActivities(scip, consdata, var, oldlb, newlb, val, SCIP_BOUNDTYPE_LOWER, FALSE, checkreliability);
2016 
2017  assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->minactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->minactivity)));
2018  assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->maxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->maxactivity)));
2019  }
2020 }
2021 
2022 /** updates minimum and maximum activity for a change in upper bound */
2023 static
2025  SCIP* scip, /**< SCIP data structure */
2026  SCIP_CONSDATA* consdata, /**< linear constraint data */
2027  SCIP_VAR* var, /**< variable that has been changed */
2028  SCIP_Real oldub, /**< old upper bound of variable */
2029  SCIP_Real newub, /**< new upper bound of variable */
2030  SCIP_Real val, /**< coefficient of constraint entry */
2031  SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2032  )
2033 {
2034  assert(scip != NULL);
2035  assert(consdata != NULL);
2036  assert(var != NULL);
2037 
2038  if( consdata->validactivities )
2039  {
2040  consdataUpdateActivities(scip, consdata, var, oldub, newub, val, SCIP_BOUNDTYPE_UPPER, FALSE, checkreliability);
2041 
2042  assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->minactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->minactivity)));
2043  assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->maxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->maxactivity)));
2044  }
2045 }
2046 
2047 /** updates minimum and maximum global activity for a change in the global lower bound */
2048 static
2050  SCIP* scip, /**< SCIP data structure */
2051  SCIP_CONSDATA* consdata, /**< linear constraint data */
2052  SCIP_Real oldlb, /**< old lower bound of variable */
2053  SCIP_Real newlb, /**< new lower bound of variable */
2054  SCIP_Real val, /**< coefficient of constraint entry */
2055  SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2056  )
2057 {
2058  assert(scip != NULL);
2059  assert(consdata != NULL);
2060 
2061  if( consdata->validactivities )
2062  {
2063  consdataUpdateActivities(scip, consdata, NULL, oldlb, newlb, val, SCIP_BOUNDTYPE_LOWER, TRUE, checkreliability);
2064 
2065  assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbminactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbminactivity)));
2066  assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbmaxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbmaxactivity)));
2067  }
2069 
2070 /** updates minimum and maximum global activity for a change in global upper bound */
2071 static
2073  SCIP* scip, /**< SCIP data structure */
2074  SCIP_CONSDATA* consdata, /**< linear constraint data */
2075  SCIP_Real oldub, /**< old upper bound of variable */
2076  SCIP_Real newub, /**< new upper bound of variable */
2077  SCIP_Real val, /**< coefficient of constraint entry */
2078  SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2079  )
2080 {
2081  assert(scip != NULL);
2082  assert(consdata != NULL);
2083 
2084  if( consdata->validactivities )
2085  {
2086  consdataUpdateActivities(scip, consdata, NULL, oldub, newub, val, SCIP_BOUNDTYPE_UPPER, TRUE, checkreliability);
2087 
2088  assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbminactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbminactivity)));
2089  assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbmaxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbmaxactivity)));
2090  }
2092 
2093 /** updates minimum and maximum activity and maximum absolute value for coefficient addition */
2094 static
2096  SCIP* scip, /**< SCIP data structure */
2097  SCIP_CONSDATA* consdata, /**< linear constraint data */
2098  SCIP_VAR* var, /**< variable of constraint entry */
2099  SCIP_Real val, /**< coefficient of constraint entry */
2100  SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2101  )
2102 {
2103  assert(scip != NULL);
2104  assert(consdata != NULL);
2105  assert(var != NULL);
2106 
2107  /* update maximum absolute value */
2108  if( consdata->validmaxabsval )
2109  {
2110  SCIP_Real absval;
2111 
2112  assert(consdata->maxabsval < SCIP_INVALID);
2113 
2114  absval = REALABS(val);
2115  consdata->maxabsval = MAX(consdata->maxabsval, absval);
2116  }
2117 
2118  if( consdata->validminabsval )
2119  {
2120  SCIP_Real absval;
2121 
2122  assert(consdata->minabsval < SCIP_INVALID);
2123 
2124  absval = REALABS(val);
2125  consdata->minabsval = MIN(consdata->minabsval, absval);
2126  }
2127 
2128  /* update minimal and maximal activity */
2129  if( consdata->validactivities )
2130  {
2131  assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
2132  assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
2133  assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
2134  assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
2135 
2136  consdataUpdateActivitiesLb(scip, consdata, var, 0.0, SCIPvarGetLbLocal(var), val, checkreliability);
2137  consdataUpdateActivitiesUb(scip, consdata, var, 0.0, SCIPvarGetUbLocal(var), val, checkreliability);
2138  consdataUpdateActivitiesGlbLb(scip, consdata, 0.0, SCIPvarGetLbGlobal(var), val, checkreliability);
2139  consdataUpdateActivitiesGlbUb(scip, consdata, 0.0, SCIPvarGetUbGlobal(var), val, checkreliability);
2140  }
2141 }
2142 
2143 /** updates minimum and maximum activity for coefficient deletion, invalidates maximum absolute value if necessary */
2144 static
2146  SCIP* scip, /**< SCIP data structure */
2147  SCIP_CONSDATA* consdata, /**< linear constraint data */
2148  SCIP_VAR* var, /**< variable of constraint entry */
2149  SCIP_Real val, /**< coefficient of constraint entry */
2150  SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2151  )
2152 {
2153  assert(scip != NULL);
2154  assert(consdata != NULL);
2155  assert(var != NULL);
2156 
2157  /* invalidate maximum absolute value, if this coefficient was the maximum */
2158  if( consdata->validmaxabsval )
2159  {
2160  SCIP_Real absval;
2161 
2162  absval = REALABS(val);
2163 
2164  if( SCIPisEQ(scip, absval, consdata->maxabsval) )
2165  {
2166  consdata->validmaxabsval = FALSE;
2167  consdata->maxabsval = SCIP_INVALID;
2168  }
2169  }
2170 
2171  /* invalidate minimum absolute value, if this coefficient was the minimum */
2172  if( consdata->validminabsval )
2173  {
2174  SCIP_Real absval;
2175 
2176  absval = REALABS(val);
2177 
2178  if( SCIPisEQ(scip, absval, consdata->minabsval) )
2179  {
2180  consdata->validminabsval = FALSE;
2181  consdata->minabsval = SCIP_INVALID;
2182  }
2183  }
2184 
2185  /* update minimal and maximal activity */
2186  if( consdata->validactivities )
2187  {
2188  assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
2189  assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
2190  assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
2191  assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
2192 
2193  consdataUpdateActivitiesLb(scip, consdata, var, SCIPvarGetLbLocal(var), 0.0, val, checkreliability);
2194  consdataUpdateActivitiesUb(scip, consdata, var, SCIPvarGetUbLocal(var), 0.0, val, checkreliability);
2195  consdataUpdateActivitiesGlbLb(scip, consdata, SCIPvarGetLbGlobal(var), 0.0, val, checkreliability);
2196  consdataUpdateActivitiesGlbUb(scip, consdata, SCIPvarGetUbGlobal(var), 0.0, val, checkreliability);
2197  }
2198 }
2199 
2200 /** updates minimum and maximum activity for coefficient change, invalidates maximum absolute value if necessary */
2201 static
2203  SCIP* scip, /**< SCIP data structure */
2204  SCIP_CONSDATA* consdata, /**< linear constraint data */
2205  SCIP_VAR* var, /**< variable of constraint entry */
2206  SCIP_Real oldval, /**< old coefficient of constraint entry */
2207  SCIP_Real newval, /**< new coefficient of constraint entry */
2208  SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2209  )
2210 {
2211  assert(scip != NULL);
2212  assert(consdata != NULL);
2213  assert(var != NULL);
2214 
2215  /* old zero coefficients should be handled by consdataUpdateAddCoef() */
2216  assert(!SCIPisZero(scip, oldval));
2217 
2218  /* new zero coefficients should be handled by consdataUpdateDelCoef() */
2219  assert(!SCIPisZero(scip, newval));
2220 
2221  /* update maximum absolute value */
2222  if( consdata->validmaxabsval )
2223  {
2224  SCIP_Real absval;
2225 
2226  absval = REALABS(newval);
2227 
2228  if( SCIPisGE(scip, absval, consdata->maxabsval) )
2229  {
2230  consdata->maxabsval = absval;
2231  }
2232  else
2233  {
2234  absval = REALABS(oldval);
2235 
2236  /* invalidate maximum absolute value */
2237  if( SCIPisEQ(scip, absval, consdata->maxabsval) )
2238  {
2239  consdata->validmaxabsval = FALSE;
2240  consdata->maxabsval = SCIP_INVALID;
2241  }
2242  }
2243  }
2244 
2245  /* update minimum absolute value */
2246  if( consdata->validminabsval )
2247  {
2248  SCIP_Real absval;
2249 
2250  absval = REALABS(newval);
2251 
2252  if( SCIPisLE(scip, absval, consdata->minabsval) )
2253  {
2254  consdata->minabsval = absval;
2255  }
2256  else
2257  {
2258  absval = REALABS(oldval);
2259 
2260  /* invalidate minimum absolute value */
2261  if( SCIPisEQ(scip, absval, consdata->minabsval) )
2262  {
2263  consdata->validminabsval = FALSE;
2264  consdata->minabsval = SCIP_INVALID;
2265  }
2266  }
2267  }
2268 
2269  /* update maximum activity delta */
2270  if( !SCIPisInfinity(scip, consdata->maxactdelta ) )
2271  {
2272  SCIP_Real domain;
2273  SCIP_Real delta;
2274 
2275  assert(!SCIPisInfinity(scip, SCIPvarGetLbLocal(var)));
2276  assert(!SCIPisInfinity(scip, SCIPvarGetUbLocal(var)));
2277 
2278  domain = SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var);
2279  delta = REALABS(newval) * domain;
2280 
2281  if( delta > consdata->maxactdelta )
2282  {
2283  consdata->maxactdelta = delta;
2284  consdata->maxactdeltavar = var;
2285  }
2286  else
2287  {
2288  /* reset maximal activity delta, so that it will be recalculated on the next real propagation */
2289  if( consdata->maxactdeltavar == var )
2290  consdata->maxactdelta = SCIP_INVALID;
2291  }
2292  }
2293 
2294  /* @todo do something more clever here, e.g. if oldval * newval >= 0, do the update directly */
2295  consdataUpdateDelCoef(scip, consdata, var, oldval, checkreliability);
2296  consdataUpdateAddCoef(scip, consdata, var, newval, checkreliability);
2297 }
2298 
2299 /** returns the maximum absolute value of all coefficients in the constraint */
2300 static
2302  SCIP_CONSDATA* consdata /**< linear constraint data */
2303  )
2304 {
2305  assert(consdata != NULL);
2306 
2307  if( !consdata->validmaxabsval )
2308  consdataCalcMaxAbsval(consdata);
2309  assert(consdata->validmaxabsval);
2310  assert(consdata->maxabsval < SCIP_INVALID);
2311 
2312  return consdata->maxabsval;
2313 }
2314 
2315 /** returns the minimum absolute value of all coefficients in the constraint */
2316 static
2318  SCIP_CONSDATA* consdata /**< linear constraint data */
2319  )
2321  assert(consdata != NULL);
2322 
2323  if( !consdata->validminabsval )
2324  consdataCalcMinAbsval(consdata);
2325  assert(consdata->validminabsval);
2326  assert(consdata->minabsval < SCIP_INVALID);
2327 
2328  return consdata->minabsval;
2329 }
2330 
2331 /** calculates minimum and maximum local and global activity for constraint from scratch;
2332  * additionally recalculates maximum absolute value of coefficients
2333  */
2334 static
2336  SCIP* scip, /**< SCIP data structure */
2337  SCIP_CONSDATA* consdata /**< linear constraint data */
2338  )
2339 {
2340  int i;
2341 
2342  assert(scip != NULL);
2343  assert(consdata != NULL);
2344  assert(!consdata->validactivities);
2345  assert(QUAD_TO_DBL(consdata->minactivity) >= SCIP_INVALID || consdata->validminact);
2346  assert(QUAD_TO_DBL(consdata->maxactivity) >= SCIP_INVALID || consdata->validmaxact);
2347  assert(QUAD_TO_DBL(consdata->glbminactivity) >= SCIP_INVALID || consdata->validglbminact);
2348  assert(QUAD_TO_DBL(consdata->glbmaxactivity) >= SCIP_INVALID || consdata->validglbmaxact);
2349 
2350  consdata->validmaxabsval = TRUE;
2351  consdata->validminabsval = TRUE;
2352  consdata->validactivities = TRUE;
2353  consdata->validminact = TRUE;
2354  consdata->validmaxact = TRUE;
2355  consdata->validglbminact = TRUE;
2356  consdata->validglbmaxact = TRUE;
2357  consdata->maxabsval = 0.0;
2358  consdata->minabsval = (consdata->nvars == 0 ? 0.0 : REALABS(consdata->vals[0]));
2359  QUAD_ASSIGN(consdata->minactivity, 0.0);
2360  QUAD_ASSIGN(consdata->maxactivity, 0.0);
2361  consdata->lastminactivity = 0.0;
2362  consdata->lastmaxactivity = 0.0;
2363  consdata->minactivityneginf = 0;
2364  consdata->minactivityposinf = 0;
2365  consdata->maxactivityneginf = 0;
2366  consdata->maxactivityposinf = 0;
2367  consdata->minactivityneghuge = 0;
2368  consdata->minactivityposhuge = 0;
2369  consdata->maxactivityneghuge = 0;
2370  consdata->maxactivityposhuge = 0;
2371  QUAD_ASSIGN(consdata->glbminactivity, 0.0);
2372  QUAD_ASSIGN(consdata->glbmaxactivity, 0.0);
2373  consdata->lastglbminactivity = 0.0;
2374  consdata->lastglbmaxactivity = 0.0;
2375  consdata->glbminactivityneginf = 0;
2376  consdata->glbminactivityposinf = 0;
2377  consdata->glbmaxactivityneginf = 0;
2378  consdata->glbmaxactivityposinf = 0;
2379  consdata->glbminactivityneghuge = 0;
2380  consdata->glbminactivityposhuge = 0;
2381  consdata->glbmaxactivityneghuge = 0;
2382  consdata->glbmaxactivityposhuge = 0;
2383 
2384  for( i = 0; i < consdata->nvars; ++i )
2385  consdataUpdateAddCoef(scip, consdata, consdata->vars[i], consdata->vals[i], FALSE);
2386 
2387  consdata->lastminactivity = QUAD_TO_DBL(consdata->minactivity);
2388  consdata->lastmaxactivity = QUAD_TO_DBL(consdata->maxactivity);
2389  consdata->lastglbminactivity = QUAD_TO_DBL(consdata->glbminactivity);
2390  consdata->lastglbmaxactivity = QUAD_TO_DBL(consdata->glbmaxactivity);
2391 }
2392 
2393 /** gets minimal activity for constraint and given values of counters for infinite and huge contributions
2394  * and (if needed) delta to subtract from stored finite part of activity in case of a residual activity
2395  */
2396 static
2397 void getMinActivity(
2398  SCIP* scip, /**< SCIP data structure */
2399  SCIP_CONSDATA* consdata, /**< linear constraint */
2400  int posinf, /**< number of coefficients contributing pos. infinite value */
2401  int neginf, /**< number of coefficients contributing neg. infinite value */
2402  int poshuge, /**< number of coefficients contributing huge pos. value */
2403  int neghuge, /**< number of coefficients contributing huge neg. value */
2404  SCIP_Real delta, /**< value to subtract from stored minactivity
2405  * (contribution of the variable set to zero when getting residual activity) */
2406  SCIP_Bool global, /**< should the global or local minimal activity be returned? */
2407  SCIP_Bool goodrelax, /**< should a good relaxation be computed or are relaxed acticities ignored, anyway? */
2408  SCIP_Real* minactivity, /**< pointer to store the minimal activity */
2409  SCIP_Bool* isrelax, /**< pointer to store whether the activity is a relaxation,
2410  * i.e. is <= the exact minactivity (in case of huge contributing values) */
2411  SCIP_Bool* issettoinfinity /**< pointer to store whether minactivity was set to infinity or calculated */
2412  )
2413 {
2414  assert(scip != NULL);
2415  assert(consdata != NULL);
2416  assert(posinf >= 0);
2417  assert(neginf >= 0);
2418  assert(poshuge >= 0);
2419  assert(neghuge >= 0);
2420  assert(minactivity != NULL);
2421  assert(isrelax != NULL);
2422  assert(issettoinfinity != NULL);
2423 
2424  /* if we have pos. infinite contributions, the minactivity is +infty */
2425  if( posinf > 0 )
2426  {
2427  *minactivity = SCIPinfinity(scip);
2428  *issettoinfinity = TRUE;
2429  *isrelax = FALSE;
2430  }
2431  /* if we have neg. (and no pos.) infinite contributions, the minactivity is -infty */
2432  else if( neginf > 0 )
2433  {
2434  *minactivity = -SCIPinfinity(scip);
2435  *issettoinfinity = TRUE;
2436  *isrelax = FALSE;
2437  }
2438  /* if we have neg. huge contributions, we only know that -infty is a relaxation of the minactivity */
2439  else if( neghuge > 0 )
2440  {
2441  *minactivity = -SCIPinfinity(scip);
2442  *issettoinfinity = TRUE;
2443  *isrelax = TRUE;
2444  }
2445  /* we do not need a good relaxation and we have positive huge contributions, so we just return -infty as activity */
2446  else if( !goodrelax && poshuge > 0 )
2447  {
2448  *minactivity = -SCIPinfinity(scip);
2449  *issettoinfinity = TRUE;
2450  *isrelax = TRUE;
2451  }
2452  else
2453  {
2454  SCIP_Real tmpactivity;
2455 
2456  /* recompute minactivity if it is not valid */
2457  if( global )
2458  {
2459  if( !consdata->validglbminact )
2460  consdataRecomputeGlbMinactivity(scip, consdata);
2461  assert(consdata->validglbminact);
2462 
2463  tmpactivity = QUAD_TO_DBL(consdata->glbminactivity);
2464  }
2465  else
2466  {
2467  if( !consdata->validminact )
2468  consdataRecomputeMinactivity(scip, consdata);
2469  assert(consdata->validminact);
2470 
2471  tmpactivity = QUAD_TO_DBL(consdata->minactivity);
2472  }
2473 
2474  /* we have no infinite and no neg. huge contributions, but pos. huge contributions;
2475  * a feasible relaxation of the minactivity is the number of positive huge contributions
2476  * times the minimum value counting as "huge" plus finite (and non-huge) part of minactivity - delta
2477  */
2478  if( poshuge > 0 )
2479  {
2480  *minactivity = 1.0 * poshuge * SCIPgetHugeValue(scip) + (tmpactivity - delta);
2481  *issettoinfinity = FALSE;
2482  *isrelax = TRUE;
2483  }
2484  /* all counters are zero, so the minactivity is just stored and we subtract the delta */
2485  else
2486  {
2487  *minactivity = tmpactivity - delta;
2488  *issettoinfinity = FALSE;
2489  *isrelax = FALSE;
2490  }
2491  }
2492 }
2493 
2494 /** gets maximal activity for constraint and given values of counters for infinite and huge contributions
2495  * and (if needed) delta to subtract from stored finite part of activity in case of a residual activity
2496  */
2497 static
2498 void getMaxActivity(
2499  SCIP* scip, /**< SCIP data structure */
2500  SCIP_CONSDATA* consdata, /**< linear constraint */
2501  int posinf, /**< number of coefficients contributing pos. infinite value */
2502  int neginf, /**< number of coefficients contributing neg. infinite value */
2503  int poshuge, /**< number of coefficients contributing huge pos. value */
2504  int neghuge, /**< number of coefficients contributing huge neg. value */
2505  SCIP_Real delta, /**< value to subtract from stored maxactivity
2506  * (contribution of the variable set to zero when getting residual activity) */
2507  SCIP_Bool global, /**< should the global or local maximal activity be returned? */
2508  SCIP_Bool goodrelax, /**< should a good relaxation be computed or are relaxed acticities ignored, anyway? */
2509  SCIP_Real* maxactivity, /**< pointer to store the maximal activity */
2510  SCIP_Bool* isrelax, /**< pointer to store whether the activity is a relaxation,
2511  * i.e. is >= the exact maxactivity (in case of huge contributing values) */
2512  SCIP_Bool* issettoinfinity /**< pointer to store whether maxactivity was set to infinity or calculated */
2513  )
2514 {
2515  assert(scip != NULL);
2516  assert(consdata != NULL);
2517  assert(posinf >= 0);
2518  assert(neginf >= 0);
2519  assert(poshuge >= 0);
2520  assert(neghuge >= 0);
2521  assert(maxactivity != NULL);
2522  assert(isrelax != NULL);
2523  assert(issettoinfinity != NULL);
2524 
2525  /* if we have neg. infinite contributions, the maxactivity is -infty */
2526  if( neginf > 0 )
2527  {
2528  *maxactivity = -SCIPinfinity(scip);
2529  *issettoinfinity = TRUE;
2530  *isrelax = FALSE;
2531  }
2532  /* if we have pos. (and no neg.) infinite contributions, the maxactivity is +infty */
2533  else if( posinf > 0 )
2534  {
2535  *maxactivity = SCIPinfinity(scip);
2536  *issettoinfinity = TRUE;
2537  *isrelax = FALSE;
2538  }
2539  /* if we have pos. huge contributions, we only know that +infty is a relaxation of the maxactivity */
2540  else if( poshuge > 0 )
2541  {
2542  *maxactivity = SCIPinfinity(scip);
2543  *issettoinfinity = TRUE;
2544  *isrelax = TRUE;
2545  }
2546  /* we do not need a good relaxation and we have positve huge contributions, so we just return +infty as activity */
2547  else if( !goodrelax && neghuge > 0 )
2548  {
2549  *maxactivity = SCIPinfinity(scip);
2550  *issettoinfinity = TRUE;
2551  *isrelax = TRUE;
2552  }
2553  else
2554  {
2555  SCIP_Real tmpactivity;
2556 
2557  /* recompute maxactivity if it is not valid */
2558  if( global )
2559  {
2560  if( !consdata->validglbmaxact )
2561  consdataRecomputeGlbMaxactivity(scip, consdata);
2562  assert(consdata->validglbmaxact);
2563 
2564  tmpactivity = QUAD_TO_DBL(consdata->glbmaxactivity);
2565  }
2566  else
2567  {
2568  if( !consdata->validmaxact )
2569  consdataRecomputeMaxactivity(scip, consdata);
2570  assert(consdata->validmaxact);
2571 
2572  tmpactivity = QUAD_TO_DBL(consdata->maxactivity);
2573  }
2574 
2575  /* we have no infinite, and no pos. huge contributions, but neg. huge contributions;
2576  * a feasible relaxation of the maxactivity is minus the number of negative huge contributions
2577  * times the minimum value counting as "huge" plus the finite (and non-huge) part of maxactivity minus delta
2578  */
2579  if( neghuge > 0 )
2580  {
2581  *maxactivity = -1.0 * neghuge * SCIPgetHugeValue(scip) + tmpactivity - delta;
2582  *issettoinfinity = FALSE;
2583  *isrelax = TRUE;
2584  }
2585  /* all counters are zero, so the maxactivity is just stored and we subtract the delta */
2586  else
2587  {
2588  *maxactivity = tmpactivity - delta;
2589  *issettoinfinity = FALSE;
2590  *isrelax = FALSE;
2591  }
2592  }
2593 }
2594 
2595 /** gets activity bounds for constraint */
2596 static
2598  SCIP* scip, /**< SCIP data structure */
2599  SCIP_CONSDATA* consdata, /**< linear constraint */
2600  SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2601  * relaxed activities ignored, anyway? */
2602  SCIP_Real* minactivity, /**< pointer to store the minimal activity */
2603  SCIP_Real* maxactivity, /**< pointer to store the maximal activity */
2604  SCIP_Bool* minisrelax, /**< pointer to store whether the returned minactivity is just a relaxation,
2605  * i.e. <= the exact minactivity (in case of huge contributions),
2606  * or equal to the exact minimal activity */
2607  SCIP_Bool* maxisrelax, /**< pointer to store whether the returned maxactivity is just a relaxation,
2608  * i.e. >= the exact maxactivity (in case of huge contributions),
2609  * or equal to the exact maximal activity */
2610  SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minactivity was set to infinity or calculated */
2611  SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxactivity was set to infinity or calculated */
2612 
2613  )
2614 {
2615  assert(scip != NULL);
2616  assert(consdata != NULL);
2617  assert(minactivity != NULL);
2618  assert(maxactivity != NULL);
2619  assert(isminsettoinfinity != NULL);
2620  assert(ismaxsettoinfinity != NULL);
2621 
2622  if( !consdata->validactivities )
2623  {
2624  consdataCalcActivities(scip, consdata);
2625  assert(consdata->validminact);
2626  assert(consdata->validmaxact);
2627  }
2628  assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
2629  assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
2630  assert(consdata->minactivityneginf >= 0);
2631  assert(consdata->minactivityposinf >= 0);
2632  assert(consdata->maxactivityneginf >= 0);
2633  assert(consdata->maxactivityposinf >= 0);
2634 
2635  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2636  consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2637  minactivity, minisrelax, isminsettoinfinity);
2638 
2639  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2640  consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2641  maxactivity, maxisrelax, ismaxsettoinfinity);
2642 }
2643 
2644 /** calculates activity bounds for constraint after setting variable to zero */
2645 static
2647  SCIP* scip, /**< SCIP data structure */
2648  SCIP_CONSDATA* consdata, /**< linear constraint */
2649  SCIP_VAR* cancelvar, /**< variable to calculate activity residual for */
2650  SCIP_Real* resactivity, /**< pointer to store the residual activity */
2651  SCIP_Bool isminresact, /**< should minimal or maximal residual activity be calculated? */
2652  SCIP_Bool useglobalbounds /**< should global or local bounds be used? */
2653  )
2654 {
2655  SCIP_VAR* var;
2656  SCIP_Real val;
2657  SCIP_Real lb;
2658  SCIP_Real ub;
2659  int v;
2660 
2661  assert(scip != NULL);
2662  assert(consdata != NULL);
2663  assert(cancelvar != NULL);
2664  assert(resactivity != NULL);
2666  *resactivity = 0.0;
2667 
2668  for( v = 0; v < consdata->nvars; ++v )
2669  {
2670  var = consdata->vars[v];
2671  assert(var != NULL);
2672  if( var == cancelvar )
2673  continue;
2674 
2675  val = consdata->vals[v];
2676 
2677  if( useglobalbounds )
2678  {
2679  lb = SCIPvarGetLbGlobal(var);
2680  ub = SCIPvarGetUbGlobal(var);
2681  }
2682  else
2683  {
2684  lb = SCIPvarGetLbLocal(var);
2685  ub = SCIPvarGetUbLocal(var);
2686  }
2687 
2688  assert(!SCIPisZero(scip, val));
2689  assert(SCIPisLE(scip, lb, ub));
2690 
2691  if( val > 0.0 )
2692  {
2693  if( isminresact )
2694  {
2695  assert(!SCIPisInfinity(scip, -lb));
2696  assert(!SCIPisHugeValue(scip, REALABS(val*lb)));
2697  *resactivity += val*lb;
2698  }
2699  else
2700  {
2701  assert(!SCIPisInfinity(scip, ub));
2702  assert(!SCIPisHugeValue(scip, REALABS(val*ub)));
2703  *resactivity += val*ub;
2704  }
2705  }
2706  else
2707  {
2708  if( isminresact)
2709  {
2710  assert(!SCIPisInfinity(scip, ub));
2711  assert(!SCIPisHugeValue(scip, REALABS(val*ub)));
2712  *resactivity += val*ub;
2713  }
2714  else
2715  {
2716  assert(!SCIPisInfinity(scip, -lb));
2717  assert(!SCIPisHugeValue(scip, REALABS(val*lb)));
2718  *resactivity += val*lb;
2719  }
2720  }
2721  }
2722  assert(!SCIPisInfinity(scip, *resactivity) && !SCIPisInfinity(scip, -(*resactivity)));
2723 }
2724 
2725 /** gets activity bounds for constraint after setting variable to zero */
2726 static
2728  SCIP* scip, /**< SCIP data structure */
2729  SCIP_CONSDATA* consdata, /**< linear constraint */
2730  SCIP_VAR* var, /**< variable to calculate activity residual for */
2731  SCIP_Real val, /**< coefficient value of variable in linear constraint */
2732  SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2733  * relaxed acticities ignored, anyway? */
2734  SCIP_Real* minresactivity, /**< pointer to store the minimal residual activity */
2735  SCIP_Real* maxresactivity, /**< pointer to store the maximal residual activity */
2736  SCIP_Bool* minisrelax, /**< pointer to store whether the returned residual minactivity is just a
2737  * relaxation, i.e. <= the exact residual minactivity (in case of huge
2738  * contributions), or equal to the exact residual minactivity */
2739  SCIP_Bool* maxisrelax, /**< pointer to store whether the returned residual maxactivity is just a
2740  * relaxation, i.e. <= the exact residual maxactivity (in case of huge
2741  * contributions), or equal to the exact residual minactivity */
2742  SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2743  SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2744  )
2745 {
2746  SCIP_Real minactbound;
2747  SCIP_Real maxactbound;
2748  SCIP_Real absval;
2749 
2750  assert(scip != NULL);
2751  assert(consdata != NULL);
2752  assert(var != NULL);
2753  assert(minresactivity != NULL);
2754  assert(maxresactivity != NULL);
2755  assert(minisrelax != NULL);
2756  assert(maxisrelax != NULL);
2757  assert(isminsettoinfinity != NULL);
2758  assert(ismaxsettoinfinity != NULL);
2759 
2760  /* get activity bounds of linear constraint */
2761  if( !consdata->validactivities )
2762  {
2763  consdataCalcActivities(scip, consdata);
2764  assert(consdata->validminact);
2765  assert(consdata->validmaxact);
2766  }
2767  assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
2768  assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
2769  assert(consdata->minactivityneginf >= 0);
2770  assert(consdata->minactivityposinf >= 0);
2771  assert(consdata->maxactivityneginf >= 0);
2772  assert(consdata->maxactivityposinf >= 0);
2773  assert(consdata->minactivityneghuge >= 0);
2774  assert(consdata->minactivityposhuge >= 0);
2775  assert(consdata->maxactivityneghuge >= 0);
2776  assert(consdata->maxactivityposhuge >= 0);
2777 
2778  if( val > 0.0 )
2779  {
2780  minactbound = SCIPvarGetLbLocal(var);
2781  maxactbound = SCIPvarGetUbLocal(var);
2782  absval = val;
2783  }
2784  else
2785  {
2786  minactbound = -SCIPvarGetUbLocal(var);
2787  maxactbound = -SCIPvarGetLbLocal(var);
2788  absval = -val;
2789  }
2790 
2791  /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
2792  * and contribution of variable set to zero that has to be subtracted from finite part of activity
2793  */
2794  if( SCIPisInfinity(scip, minactbound) )
2795  {
2796  assert(consdata->minactivityposinf >= 1);
2797 
2798  getMinActivity(scip, consdata, consdata->minactivityposinf - 1, consdata->minactivityneginf,
2799  consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2800  minresactivity, minisrelax, isminsettoinfinity);
2801  }
2802  else if( SCIPisInfinity(scip, -minactbound) )
2803  {
2804  assert(consdata->minactivityneginf >= 1);
2805 
2806  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf - 1,
2807  consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2808  minresactivity, minisrelax, isminsettoinfinity);
2809  }
2810  else if( SCIPisHugeValue(scip, minactbound * absval) )
2811  {
2812  assert(consdata->minactivityposhuge >= 1);
2813 
2814  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2815  consdata->minactivityposhuge - 1, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2816  minresactivity, minisrelax, isminsettoinfinity);
2817  }
2818  else if( SCIPisHugeValue(scip, -minactbound * absval) )
2819  {
2820  assert(consdata->minactivityneghuge >= 1);
2821 
2822  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2823  consdata->minactivityposhuge, consdata->minactivityneghuge - 1, 0.0, FALSE, goodrelax,
2824  minresactivity, minisrelax, isminsettoinfinity);
2825  }
2826  else
2827  {
2828  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2829  consdata->minactivityposhuge, consdata->minactivityneghuge, absval * minactbound, FALSE, goodrelax,
2830  minresactivity, minisrelax, isminsettoinfinity);
2831  }
2832 
2833  /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
2834  * and contribution of variable set to zero that has to be subtracted from finite part of activity
2835  */
2836  if( SCIPisInfinity(scip, -maxactbound) )
2837  {
2838  assert(consdata->maxactivityneginf >= 1);
2839 
2840  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf - 1,
2841  consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2842  maxresactivity, maxisrelax, ismaxsettoinfinity);
2843  }
2844  else if( SCIPisInfinity(scip, maxactbound) )
2845  {
2846  assert(consdata->maxactivityposinf >= 1);
2847 
2848  getMaxActivity(scip, consdata, consdata->maxactivityposinf - 1, consdata->maxactivityneginf,
2849  consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2850  maxresactivity, maxisrelax, ismaxsettoinfinity);
2851  }
2852  else if( SCIPisHugeValue(scip, absval * maxactbound) )
2853  {
2854  assert(consdata->maxactivityposhuge >= 1);
2855 
2856  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2857  consdata->maxactivityposhuge - 1, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2858  maxresactivity, maxisrelax, ismaxsettoinfinity);
2859  }
2860  else if( SCIPisHugeValue(scip, -absval * maxactbound) )
2861  {
2862  assert(consdata->maxactivityneghuge >= 1);
2863 
2864  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2865  consdata->maxactivityposhuge, consdata->maxactivityneghuge - 1, 0.0, FALSE, goodrelax,
2866  maxresactivity, maxisrelax, ismaxsettoinfinity);
2867  }
2868  else
2869  {
2870  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2871  consdata->maxactivityposhuge, consdata->maxactivityneghuge, absval * maxactbound, FALSE, goodrelax,
2872  maxresactivity, maxisrelax, ismaxsettoinfinity);
2873  }
2874 }
2875 
2876 /** gets global activity bounds for constraint */
2877 static
2879  SCIP* scip, /**< SCIP data structure */
2880  SCIP_CONSDATA* consdata, /**< linear constraint */
2881  SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2882  * relaxed acticities ignored, anyway? */
2883  SCIP_Real* glbminactivity, /**< pointer to store the minimal activity, or NULL, if not needed */
2884  SCIP_Real* glbmaxactivity, /**< pointer to store the maximal activity, or NULL, if not needed */
2885  SCIP_Bool* minisrelax, /**< pointer to store whether the returned minactivity is just a relaxation,
2886  * i.e. <= the exact minactivity (in case of huge contributions),
2887  * or equal to the exact minimal activity */
2888  SCIP_Bool* maxisrelax, /**< pointer to store whether the returned maxactivity is just a relaxation,
2889  * i.e. >= the exact maxactivity (in case of huge contributions),
2890  * or equal to the exact maximal activity */
2891  SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2892  SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2893  )
2894 {
2895  assert(scip != NULL);
2896  assert(consdata != NULL);
2897  assert((glbminactivity != NULL && minisrelax != NULL && isminsettoinfinity != NULL)
2898  || (glbmaxactivity != NULL && maxisrelax != NULL && ismaxsettoinfinity != NULL));
2899 
2900  if( !consdata->validactivities )
2901  {
2902  consdataCalcActivities(scip, consdata);
2903  assert(consdata->validglbminact);
2904  assert(consdata->validglbmaxact);
2905  }
2906  assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
2907  assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
2908  assert(consdata->glbminactivityneginf >= 0);
2909  assert(consdata->glbminactivityposinf >= 0);
2910  assert(consdata->glbmaxactivityneginf >= 0);
2911  assert(consdata->glbmaxactivityposinf >= 0);
2912  assert(consdata->glbminactivityneghuge >= 0);
2913  assert(consdata->glbminactivityposhuge >= 0);
2914  assert(consdata->glbmaxactivityneghuge >= 0);
2915  assert(consdata->glbmaxactivityposhuge >= 0);
2916 
2917  if( glbminactivity != NULL )
2918  {
2919  assert(isminsettoinfinity != NULL);
2920  assert(minisrelax != NULL);
2921 
2922  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
2923  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
2924  glbminactivity, minisrelax, isminsettoinfinity);
2925  }
2926 
2927  if( glbmaxactivity != NULL )
2928  {
2929  assert(ismaxsettoinfinity != NULL);
2930  assert(maxisrelax != NULL);
2931 
2932  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
2933  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
2934  glbmaxactivity, maxisrelax, ismaxsettoinfinity);
2935  }
2936 }
2937 
2938 /** gets global activity bounds for constraint after setting variable to zero */
2939 static
2941  SCIP* scip, /**< SCIP data structure */
2942  SCIP_CONSDATA* consdata, /**< linear constraint */
2943  SCIP_VAR* var, /**< variable to calculate activity residual for */
2944  SCIP_Real val, /**< coefficient value of variable in linear constraint */
2945  SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2946  * relaxed acticities ignored, anyway? */
2947  SCIP_Real* minresactivity, /**< pointer to store the minimal residual activity, or NULL, if not needed */
2948  SCIP_Real* maxresactivity, /**< pointer to store the maximal residual activity, or NULL, if not needed */
2949  SCIP_Bool* minisrelax, /**< pointer to store whether the returned residual minactivity is just a
2950  * relaxation, i.e. <= the exact residual minactivity (in case of huge
2951  * contributions), or equal to the exact residual minactivity */
2952  SCIP_Bool* maxisrelax, /**< pointer to store whether the returned residual maxactivity is just a
2953  * relaxation, i.e. <= the exact residual maxactivity (in case of huge
2954  * contributions), or equal to the exact residual minactivity */
2955  SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2956  SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2957  )
2958 {
2959  SCIP_Real minactbound;
2960  SCIP_Real maxactbound;
2961  SCIP_Real absval;
2962 
2963  assert(scip != NULL);
2964  assert(consdata != NULL);
2965  assert(var != NULL);
2966  assert((minresactivity != NULL && minisrelax != NULL && isminsettoinfinity != NULL )
2967  || (maxresactivity != NULL && maxisrelax != NULL && ismaxsettoinfinity != NULL));
2968 
2969  /* get activity bounds of linear constraint */
2970  if( !consdata->validactivities )
2971  consdataCalcActivities(scip, consdata);
2972 
2973  assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
2974  assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
2975  assert(consdata->glbminactivityneginf >= 0);
2976  assert(consdata->glbminactivityposinf >= 0);
2977  assert(consdata->glbmaxactivityneginf >= 0);
2978  assert(consdata->glbmaxactivityposinf >= 0);
2979 
2980  if( val > 0.0 )
2981  {
2982  minactbound = SCIPvarGetLbGlobal(var);
2983  maxactbound = SCIPvarGetUbGlobal(var);
2984  absval = val;
2985  }
2986  else
2987  {
2988  minactbound = -SCIPvarGetUbGlobal(var);
2989  maxactbound = -SCIPvarGetLbGlobal(var);
2990  absval = -val;
2991  }
2992 
2993  if( minresactivity != NULL )
2994  {
2995  assert(isminsettoinfinity != NULL);
2996  assert(minisrelax != NULL);
2997 
2998  /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
2999  * and contribution of variable set to zero that has to be subtracted from finite part of activity
3000  */
3001  if( SCIPisInfinity(scip, minactbound) )
3002  {
3003  assert(consdata->glbminactivityposinf >= 1);
3004 
3005  getMinActivity(scip, consdata, consdata->glbminactivityposinf - 1, consdata->glbminactivityneginf,
3006  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
3007  minresactivity, minisrelax, isminsettoinfinity);
3008  }
3009  else if( SCIPisInfinity(scip, -minactbound) )
3010  {
3011  assert(consdata->glbminactivityneginf >= 1);
3012 
3013  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf - 1,
3014  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
3015  minresactivity, minisrelax, isminsettoinfinity);
3016  }
3017  else if( SCIPisHugeValue(scip, minactbound * absval) )
3018  {
3019  assert(consdata->glbminactivityposhuge >= 1);
3020 
3021  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
3022  consdata->glbminactivityposhuge - 1, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
3023  minresactivity, minisrelax, isminsettoinfinity);
3024  }
3025  else if( SCIPisHugeValue(scip, -minactbound * absval) )
3026  {
3027  assert(consdata->glbminactivityneghuge >= 1);
3028 
3029  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
3030  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge - 1, 0.0, TRUE, goodrelax,
3031  minresactivity, minisrelax, isminsettoinfinity);
3032  }
3033  else
3034  {
3035  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
3036  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, absval * minactbound, TRUE,
3037  goodrelax, minresactivity, minisrelax, isminsettoinfinity);
3038  }
3039  }
3040 
3041  if( maxresactivity != NULL )
3042  {
3043  assert(ismaxsettoinfinity != NULL);
3044  assert(maxisrelax != NULL);
3045 
3046  /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
3047  * and contribution of variable set to zero that has to be subtracted from finite part of activity
3048  */
3049  if( SCIPisInfinity(scip, -maxactbound) )
3050  {
3051  assert(consdata->glbmaxactivityneginf >= 1);
3052 
3053  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf - 1,
3054  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
3055  maxresactivity, maxisrelax, ismaxsettoinfinity);
3056  }
3057  else if( SCIPisInfinity(scip, maxactbound) )
3058  {
3059  assert(consdata->glbmaxactivityposinf >= 1);
3060 
3061  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf - 1, consdata->glbmaxactivityneginf,
3062  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
3063  maxresactivity, maxisrelax, ismaxsettoinfinity);
3064  }
3065  else if( SCIPisHugeValue(scip, absval * maxactbound) )
3066  {
3067  assert(consdata->glbmaxactivityposhuge >= 1);
3068 
3069  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
3070  consdata->glbmaxactivityposhuge - 1, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
3071  maxresactivity, maxisrelax, ismaxsettoinfinity);
3072  }
3073  else if( SCIPisHugeValue(scip, -absval * maxactbound) )
3074  {
3075  assert(consdata->glbmaxactivityneghuge >= 1);
3076 
3077  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
3078  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge - 1, 0.0, TRUE, goodrelax,
3079  maxresactivity, maxisrelax, ismaxsettoinfinity);
3080  }
3081  else
3082  {
3083  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
3084  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, absval * maxactbound, TRUE,
3085  goodrelax, maxresactivity, maxisrelax, ismaxsettoinfinity);
3086  }
3087  }
3088 }
3089 
3090 /** calculates the activity of the linear constraint for given solution */
3091 static
3093  SCIP* scip, /**< SCIP data structure */
3094  SCIP_CONSDATA* consdata, /**< linear constraint data */
3095  SCIP_SOL* sol /**< solution to get activity for, NULL to current solution */
3096  )
3097 {
3098  SCIP_Real activity;
3099 
3100  assert(scip != NULL);
3101  assert(consdata != NULL);
3102 
3103  if( sol == NULL && !SCIPhasCurrentNodeLP(scip) )
3104  activity = consdataComputePseudoActivity(scip, consdata);
3105  else
3106  {
3107  SCIP_Real solval;
3108  int nposinf;
3109  int nneginf;
3110  SCIP_Bool negsign;
3111  int v;
3112 
3113  activity = 0.0;
3114  nposinf = 0;
3115  nneginf = 0;
3116 
3117  for( v = 0; v < consdata->nvars; ++v )
3118  {
3119  solval = SCIPgetSolVal(scip, sol, consdata->vars[v]);
3120 
3121  if( consdata->vals[v] < 0 )
3122  negsign = TRUE;
3123  else
3124  negsign = FALSE;
3125 
3126  if( (SCIPisInfinity(scip, solval) && !negsign) || (SCIPisInfinity(scip, -solval) && negsign) )
3127  ++nposinf;
3128  else if( (SCIPisInfinity(scip, solval) && negsign) || (SCIPisInfinity(scip, -solval) && !negsign) )
3129  ++nneginf;
3130  else
3131  activity += consdata->vals[v] * solval;
3132  }
3133  assert(nneginf >= 0 && nposinf >= 0);
3134 
3135  SCIPdebugMsg(scip, "activity of linear constraint: %.15g, %d positive infinity values, %d negative infinity values \n", activity, nposinf, nneginf);
3136 
3137  /* check for amount of infinity values and correct the activity */
3138  if( nposinf > 0 && nneginf > 0 )
3139  activity = (consdata->rhs + consdata->lhs) / 2;
3140  else if( nposinf > 0 )
3141  activity = SCIPinfinity(scip);
3142  else if( nneginf > 0 )
3143  activity = -SCIPinfinity(scip);
3144 
3145  SCIPdebugMsg(scip, "corrected activity of linear constraint: %.15g\n", activity);
3146  }
3147 
3148  if( activity == SCIP_INVALID ) /*lint !e777*/
3149  return activity;
3150  else if( activity < 0 )
3151  activity = MAX(activity, -SCIPinfinity(scip)); /*lint !e666*/
3152  else
3153  activity = MIN(activity, SCIPinfinity(scip)); /*lint !e666*/
3154 
3155  return activity;
3156 }
3157 
3158 /** calculates the feasibility of the linear constraint for given solution */
3159 static
3161  SCIP* scip, /**< SCIP data structure */
3162  SCIP_CONSDATA* consdata, /**< linear constraint data */
3163  SCIP_SOL* sol /**< solution to get feasibility for, NULL to current solution */
3164  )
3165 {
3166  SCIP_Real activity;
3167 
3168  assert(scip != NULL);
3169  assert(consdata != NULL);
3170 
3171  activity = consdataGetActivity(scip, consdata, sol);
3172 
3173  if( activity == SCIP_INVALID ) /*lint !e777*/
3174  return -SCIPinfinity(scip);
3175 
3176  return MIN(consdata->rhs - activity, activity - consdata->lhs);
3177 }
3178 
3179 /** updates bit signatures after adding a single coefficient */
3180 static
3182  SCIP_CONSDATA* consdata, /**< linear constraint data */
3183  int pos /**< position of coefficient to update signatures for */
3184  )
3185 {
3186  uint64_t varsignature;
3187  SCIP_Real lb;
3188  SCIP_Real ub;
3189  SCIP_Real val;
3190 
3191  assert(consdata != NULL);
3192  assert(consdata->validsignature);
3193 
3194  varsignature = SCIPhashSignature64(SCIPvarGetIndex(consdata->vars[pos]));
3195  lb = SCIPvarGetLbGlobal(consdata->vars[pos]);
3196  ub = SCIPvarGetUbGlobal(consdata->vars[pos]);
3197  val = consdata->vals[pos];
3198  if( (val > 0.0 && ub > 0.0) || (val < 0.0 && lb < 0.0) )
3199  consdata->possignature |= varsignature;
3200  if( (val > 0.0 && lb < 0.0) || (val < 0.0 && ub > 0.0) )
3201  consdata->negsignature |= varsignature;
3202 }
3203 
3204 /** calculates the bit signatures of the given constraint data */
3205 static
3207  SCIP_CONSDATA* consdata /**< linear constraint data */
3208  )
3209 {
3210  assert(consdata != NULL);
3211 
3212  if( !consdata->validsignature )
3213  {
3214  int i;
3215 
3216  consdata->validsignature = TRUE;
3217  consdata->possignature = 0;
3218  consdata->negsignature = 0;
3219  for( i = 0; i < consdata->nvars; ++i )
3220  consdataUpdateSignatures(consdata, i);
3221  }
3222 }
3223 
3224 /** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
3225 static
3226 SCIP_DECL_SORTINDCOMP(consdataCompVar)
3227 { /*lint --e{715}*/
3228  SCIP_CONSDATA* consdata = (SCIP_CONSDATA*)dataptr;
3229  SCIP_VAR* var1;
3230  SCIP_VAR* var2;
3231 
3232  assert(consdata != NULL);
3233  assert(0 <= ind1 && ind1 < consdata->nvars);
3234  assert(0 <= ind2 && ind2 < consdata->nvars);
3235 
3236  var1 = consdata->vars[ind1];
3237  var2 = consdata->vars[ind2];
3238 
3239  /* exactly one variable is binary */
3240  if( SCIPvarIsBinary(var1) != SCIPvarIsBinary(var2) )
3241  {
3242  return (SCIPvarIsBinary(var1) ? -1 : +1);
3243  }
3244  /* both variables are binary */
3245  else if( SCIPvarIsBinary(var1) )
3246  {
3247  return SCIPvarCompare(var1, var2);
3248  }
3249  else
3250  {
3251  SCIP_VARTYPE vartype1 = SCIPvarGetType(var1);
3252  SCIP_VARTYPE vartype2 = SCIPvarGetType(var2);
3253 
3254  if( vartype1 < vartype2 )
3255  return -1;
3256  else if( vartype1 > vartype2 )
3257  return +1;
3258  else
3259  return SCIPvarCompare(var1, var2);
3260  }
3261 }
3262 
3263 /** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
3264 static
3265 SCIP_DECL_SORTINDCOMP(consdataCompVarProp)
3266 { /*lint --e{715}*/
3267  SCIP_CONSDATA* consdata = (SCIP_CONSDATA*)dataptr;
3268  SCIP_VAR* var1;
3269  SCIP_VAR* var2;
3270 
3271  assert(consdata != NULL);
3272  assert(0 <= ind1 && ind1 < consdata->nvars);
3273  assert(0 <= ind2 && ind2 < consdata->nvars);
3274 
3275  var1 = consdata->vars[ind1];
3276  var2 = consdata->vars[ind2];
3277 
3278  /* exactly one variable is binary */
3279  if( SCIPvarIsBinary(var1) != SCIPvarIsBinary(var2) )
3280  {
3281  return (SCIPvarIsBinary(var1) ? -1 : +1);
3282  }
3283  /* both variables are binary */
3284  else if( SCIPvarIsBinary(var1) )
3285  {
3286  SCIP_Real abscoef1 = REALABS(consdata->vals[ind1]);
3287  SCIP_Real abscoef2 = REALABS(consdata->vals[ind2]);
3288 
3289  if( EPSGT(abscoef1, abscoef2, 1e-9) )
3290  return -1;
3291  else if( EPSGT(abscoef2, abscoef1, 1e-9) )
3292  return +1;
3293  else
3294  return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
3295  }
3296  else
3297  {
3298  SCIP_VARTYPE vartype1 = SCIPvarGetType(var1);
3299  SCIP_VARTYPE vartype2 = SCIPvarGetType(var2);
3300 
3301  if( vartype1 < vartype2 )
3302  {
3303  return -1;
3304  }
3305  else if( vartype1 > vartype2 )
3306  {
3307  return +1;
3308  }
3309  else
3310  {
3311  /* both variables are continuous */
3312  if( !SCIPvarIsIntegral(var1) )
3313  {
3314  assert(!SCIPvarIsIntegral(var2));
3315  return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
3316  }
3317  else
3318  {
3319  SCIP_Real abscont1 = REALABS(consdata->vals[ind1] * (SCIPvarGetUbGlobal(var1) - SCIPvarGetLbGlobal(var1)));
3320  SCIP_Real abscont2 = REALABS(consdata->vals[ind2] * (SCIPvarGetUbGlobal(var2) - SCIPvarGetLbGlobal(var2)));
3321 
3322  if( EPSGT(abscont1, abscont2, 1e-9) )
3323  return -1;
3324  else if( EPSGT(abscont2, abscont1, 1e-9) )
3325  return +1;
3326  else
3327  return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
3328  }
3329  }
3330  }
3331 }
3332 
3333 /** permutes the constraint's variables according to a given permutation. */
3334 static
3335 void permSortConsdata(
3336  SCIP_CONSDATA* consdata, /**< the constraint data */
3337  int* perm, /**< the target permutation */
3338  int nvars /**< the number of variables */
3339  )
3340 { /*lint --e{715}*/
3341  SCIP_VAR* varv;
3342  SCIP_EVENTDATA* eventdatav;
3343  SCIP_Real valv;
3344  int v;
3345  int i;
3346  int nexti;
3347 
3348  assert(perm != NULL);
3349  assert(consdata != NULL);
3350 
3351  /* permute the variables in the linear constraint according to the target permutation */
3352  eventdatav = NULL;
3353  for( v = 0; v < nvars; ++v )
3354  {
3355  if( perm[v] != v )
3356  {
3357  varv = consdata->vars[v];
3358  valv = consdata->vals[v];
3359  if( consdata->eventdata != NULL )
3360  eventdatav = consdata->eventdata[v];
3361  i = v;
3362  do
3363  {
3364  assert(0 <= perm[i] && perm[i] < nvars);
3365  assert(perm[i] != i);
3366  consdata->vars[i] = consdata->vars[perm[i]];
3367  consdata->vals[i] = consdata->vals[perm[i]];
3368  if( consdata->eventdata != NULL )
3369  {
3370  consdata->eventdata[i] = consdata->eventdata[perm[i]];
3371  consdata->eventdata[i]->varpos = i;
3372  }
3373  nexti = perm[i];
3374  perm[i] = i;
3375  i = nexti;
3376  }
3377  while( perm[i] != v );
3378  consdata->vars[i] = varv;
3379  consdata->vals[i] = valv;
3380  if( consdata->eventdata != NULL )
3381  {
3382  consdata->eventdata[i] = eventdatav;
3383  consdata->eventdata[i]->varpos = i;
3384  }
3385  perm[i] = i;
3386  }
3387  }
3388 #ifdef SCIP_DEBUG
3389  /* check sorting */
3390  for( v = 0; v < nvars; ++v )
3391  {
3392  assert(perm[v] == v);
3393  assert(consdata->eventdata == NULL || consdata->eventdata[v]->varpos == v);
3394  }
3395 #endif
3396 }
3397 
3398 /** sorts linear constraint's variables depending on the stage of the solving process:
3399  * - during PRESOLVING
3400  * sorts variables by binaries, integers, implicit integers, and continuous variables,
3401  * and the variables of the same type by non-decreasing variable index
3402  *
3403  * - during SOLVING
3404  * sorts variables of the remaining problem by binaries, integers, implicit integers, and continuous variables,
3405  * and binary and integer variables by their global max activity delta (within each group),
3406  * ties within a group are broken by problem index of the variable.
3407  *
3408  * This fastens the propagation time of the constraint handler.
3409  */
3410 static
3412  SCIP* scip, /**< SCIP data structure */
3413  SCIP_CONSDATA* consdata /**< linear constraint data */
3414  )
3415 {
3416  assert(scip != NULL);
3417  assert(consdata != NULL);
3418 
3419  /* check if there are variables for sorting */
3420  if( consdata->nvars <= 1 )
3421  {
3422  consdata->indexsorted = TRUE;
3423  consdata->coefsorted = TRUE;
3424  consdata->nbinvars = (consdata->nvars == 1 ? (int)SCIPvarIsBinary(consdata->vars[0]) : 0);
3425  }
3426  else if( (!consdata->indexsorted && SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE)
3427  || (!consdata->coefsorted && SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE) )
3428  {
3429  int* perm;
3430  int v;
3431 
3432  /* get temporary memory to store the sorted permutation */
3433  SCIP_CALL( SCIPallocBufferArray(scip, &perm, consdata->nvars) );
3434 
3435  /* call sorting method */
3436  if( SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE )
3437  SCIPsort(perm, consdataCompVar, (void*)consdata, consdata->nvars);
3438  else
3439  SCIPsort(perm, consdataCompVarProp, (void*)consdata, consdata->nvars);
3440 
3441  permSortConsdata(consdata, perm, consdata->nvars);
3442 
3443  /* free temporary memory */
3444  SCIPfreeBufferArray(scip, &perm);
3445 
3446  if( SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE )
3447  {
3448  consdata->indexsorted = FALSE;
3449  consdata->coefsorted = TRUE;
3450 
3451  /* count binary variables in the sorted vars array */
3452  consdata->nbinvars = 0;
3453  for( v = 0; v < consdata->nvars; ++v )
3454  {
3455  if( SCIPvarIsBinary(consdata->vars[v]) )
3456  ++consdata->nbinvars;
3457  else
3458  break;
3459  }
3460  }
3461  else
3462  {
3463  consdata->indexsorted = TRUE;
3464  consdata->coefsorted = FALSE;
3465  }
3466  }
3467 
3468  return SCIP_OKAY;
3469 }
3470 
3471 
3472 /*
3473  * local linear constraint handler methods
3474  */
3475 
3476 /** sets left hand side of linear constraint */
3477 static
3479  SCIP* scip, /**< SCIP data structure */
3480  SCIP_CONS* cons, /**< linear constraint */
3481  SCIP_Real lhs /**< new left hand side */
3482  )
3483 {
3484  SCIP_CONSDATA* consdata;
3485  SCIP_Bool locked;
3486  int i;
3487 
3488  assert(scip != NULL);
3489  assert(cons != NULL);
3490  assert(!SCIPisInfinity(scip, lhs));
3491 
3492  /* adjust value to not be smaller than -inf */
3493  if ( SCIPisInfinity(scip, -lhs) )
3494  lhs = -SCIPinfinity(scip);
3495 
3496  consdata = SCIPconsGetData(cons);
3497  assert(consdata != NULL);
3498  assert(consdata->nvars == 0 || (consdata->vars != NULL && consdata->vals != NULL));
3499  assert(!SCIPisInfinity(scip, consdata->lhs));
3500 
3501  /* check whether the side is not changed */
3502  if( SCIPisEQ(scip, consdata->lhs, lhs) )
3503  return SCIP_OKAY;
3504 
3505  /* ensure that rhs >= lhs is satisfied without numerical tolerance */
3506  if( SCIPisEQ(scip, lhs, consdata->rhs) )
3507  {
3508  consdata->rhs = lhs;
3509  assert(consdata->row == NULL);
3510  }
3511 
3512  locked = FALSE;
3513  for( i = 0; i < NLOCKTYPES && !locked; i++ )
3514  locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
3515 
3516  /* if necessary, update the rounding locks of variables */
3517  if( locked )
3518  {
3519  if( SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, -lhs) )
3520  {
3521  SCIP_VAR** vars;
3522  SCIP_Real* vals;
3523  int v;
3524 
3525  /* the left hand side switched from -infinity to a non-infinite value -> install rounding locks */
3526  vars = consdata->vars;
3527  vals = consdata->vals;
3528 
3529  for( v = 0; v < consdata->nvars; ++v )
3530  {
3531  assert(vars[v] != NULL);
3532  assert(!SCIPisZero(scip, vals[v]));
3533 
3534  if( SCIPisPositive(scip, vals[v]) )
3535  {
3536  SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3537  }
3538  else
3539  {
3540  SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3541  }
3542  }
3543  }
3544  else if( !SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -lhs) )
3545  {
3546  SCIP_VAR** vars;
3547  SCIP_Real* vals;
3548  int v;
3549 
3550  /* the left hand side switched from a non-infinite value to -infinity -> remove rounding locks */
3551  vars = consdata->vars;
3552  vals = consdata->vals;
3553 
3554  for( v = 0; v < consdata->nvars; ++v )
3555  {
3556  assert(vars[v] != NULL);
3557  assert(!SCIPisZero(scip, vals[v]));
3558 
3559  if( SCIPisPositive(scip, vals[v]) )
3560  {
3561  SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3562  }
3563  else
3564  {
3565  SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3566  }
3567  }
3568  }
3569  }
3570 
3571  /* 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 */
3572  if( !SCIPisInfinity(scip, -lhs) && SCIPisGT(scip, lhs, consdata->lhs) )
3573  {
3574  consdata->boundstightened = 0;
3575  consdata->presolved = FALSE;
3576  consdata->cliquesadded = FALSE;
3577  consdata->implsadded = FALSE;
3578 
3579  /* mark the constraint for propagation */
3580  if( SCIPconsIsTransformed(cons) )
3581  {
3582  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
3583  }
3584  }
3585 
3586  /* set new left hand side and update constraint data */
3587  consdata->lhs = lhs;
3588  consdata->changed = TRUE;
3589  consdata->normalized = FALSE;
3590  consdata->upgradetried = FALSE;
3591  consdata->rangedrowpropagated = 0;
3592 
3593  /* update the lhs of the LP row */
3594  if( consdata->row != NULL )
3595  {
3596  SCIP_CALL( SCIPchgRowLhs(scip, consdata->row, lhs) );
3597  }
3598 
3599  return SCIP_OKAY;
3600 }
3601 
3602 /** sets right hand side of linear constraint */
3603 static
3605  SCIP* scip, /**< SCIP data structure */
3606  SCIP_CONS* cons, /**< linear constraint */
3607  SCIP_Real rhs /**< new right hand side */
3608  )
3609 {
3610  SCIP_CONSDATA* consdata;
3611  SCIP_Bool locked;
3612  int i;
3613 
3614  assert(scip != NULL);
3615  assert(cons != NULL);
3616  assert(!SCIPisInfinity(scip, -rhs));
3617 
3618  /* adjust value to not be larger than inf */
3619  if ( SCIPisInfinity(scip, rhs) )
3620  rhs = SCIPinfinity(scip);
3621 
3622  consdata = SCIPconsGetData(cons);
3623  assert(consdata != NULL);
3624  assert(consdata->nvars == 0 || (consdata->vars != NULL && consdata->vals != NULL));
3625  assert(!SCIPisInfinity(scip, -consdata->rhs));
3626 
3627  /* check whether the side is not changed */
3628  if( SCIPisEQ(scip, consdata->rhs, rhs) )
3629  return SCIP_OKAY;
3630 
3631  /* ensure that rhs >= lhs is satisfied without numerical tolerance */
3632  if( SCIPisEQ(scip, rhs, consdata->lhs) )
3633  {
3634  consdata->lhs = rhs;
3635  assert(consdata->row == NULL);
3636  }
3637 
3638  locked = FALSE;
3639  for( i = 0; i < NLOCKTYPES && !locked; i++ )
3640  locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
3641 
3642  /* if necessary, update the rounding locks of variables */
3643  if( locked )
3644  {
3645  assert(SCIPconsIsTransformed(cons));
3646 
3647  if( SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, rhs) )
3648  {
3649  SCIP_VAR** vars;
3650  SCIP_Real* vals;
3651  int v;
3652 
3653  /* the right hand side switched from infinity to a non-infinite value -> install rounding locks */
3654  vars = consdata->vars;
3655  vals = consdata->vals;
3656 
3657  for( v = 0; v < consdata->nvars; ++v )
3658  {
3659  assert(vars[v] != NULL);
3660  assert(!SCIPisZero(scip, vals[v]));
3661 
3662  if( SCIPisPositive(scip, vals[v]) )
3663  {
3664  SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3665  }
3666  else
3667  {
3668  SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3669  }
3670  }
3671  }
3672  else if( !SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, rhs) )
3673  {
3674  SCIP_VAR** vars;
3675  SCIP_Real* vals;
3676  int v;
3677 
3678  /* the right hand side switched from a non-infinite value to infinity -> remove rounding locks */
3679  vars = consdata->vars;
3680  vals = consdata->vals;
3681 
3682  for( v = 0; v < consdata->nvars; ++v )
3683  {
3684  assert(vars[v] != NULL);
3685  assert(!SCIPisZero(scip, vals[v]));
3686 
3687  if( SCIPisPositive(scip, vals[v]) )
3688  {
3689  SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3690  }
3691  else
3692  {
3693  SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3694  }
3695  }
3696  }
3697  }
3698 
3699  /* 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 */
3700  if( !SCIPisInfinity(scip, rhs) && SCIPisLT(scip, rhs, consdata->rhs) )
3701  {
3702  consdata->boundstightened = 0;
3703  consdata->presolved = FALSE;
3704  consdata->cliquesadded = FALSE;
3705  consdata->implsadded = FALSE;
3706 
3707  /* mark the constraint for propagation */
3708  if( SCIPconsIsTransformed(cons) )
3709  {
3710  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
3711  }
3712  }
3713 
3714  /* set new right hand side and update constraint data */
3715  consdata->rhs = rhs;
3716  consdata->changed = TRUE;
3717  consdata->normalized = FALSE;
3718  consdata->upgradetried = FALSE;
3719  consdata->rangedrowpropagated = 0;
3720 
3721  /* update the rhs of the LP row */
3722  if( consdata->row != NULL )
3723  {
3724  SCIP_CALL( SCIPchgRowRhs(scip, consdata->row, rhs) );
3725  }
3726 
3727  return SCIP_OKAY;
3728 }
3729 
3730 /** adds coefficient in linear constraint */
3731 static
3733  SCIP* scip, /**< SCIP data structure */
3734  SCIP_CONS* cons, /**< linear constraint */
3735  SCIP_VAR* var, /**< variable of constraint entry */
3736  SCIP_Real val /**< coefficient of constraint entry */
3737  )
3738 {
3739  SCIP_CONSDATA* consdata;
3740  SCIP_Bool transformed;
3741 
3742  assert(scip != NULL);
3743  assert(cons != NULL);
3744  assert(var != NULL);
3745 
3746  /* relaxation-only variables must not be used in checked or enforced constraints */
3747  assert(!SCIPvarIsRelaxationOnly(var) || (!SCIPconsIsChecked(cons) && !SCIPconsIsEnforced(cons)));
3748 
3749  /* ignore coefficient if it is nearly zero */
3750  if( SCIPisZero(scip, val) )
3751  return SCIP_OKAY;
3752 
3753  consdata = SCIPconsGetData(cons);
3754  assert(consdata != NULL);
3755 
3756  /* are we in the transformed problem? */
3757  transformed = SCIPconsIsTransformed(cons);
3758 
3759  /* always use transformed variables in transformed constraints */
3760  if( transformed )
3761  {
3762  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
3763  }
3764  assert(var != NULL);
3765  assert(transformed == SCIPvarIsTransformed(var));
3766 
3767  SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
3768  consdata->vars[consdata->nvars] = var;
3769  consdata->vals[consdata->nvars] = val;
3770  consdata->nvars++;
3771 
3772  /* capture variable */
3773  SCIP_CALL( SCIPcaptureVar(scip, var) );
3774 
3775  /* if we are in transformed problem, the variable needs an additional event data */
3776  if( transformed )
3777  {
3778  if( consdata->eventdata != NULL )
3779  {
3780  SCIP_CONSHDLR* conshdlr;
3781  SCIP_CONSHDLRDATA* conshdlrdata;
3782 
3783  /* check for event handler */
3784  conshdlr = SCIPconsGetHdlr(cons);
3785  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3786  assert(conshdlrdata != NULL);
3787  assert(conshdlrdata->eventhdlr != NULL);
3788 
3789  /* initialize eventdata array */
3790  consdata->eventdata[consdata->nvars-1] = NULL;
3791 
3792  /* catch bound change events of variable */
3793  SCIP_CALL( consCatchEvent(scip, cons, conshdlrdata->eventhdlr, consdata->nvars-1) );
3794  }
3795 
3796  /* update minimum and maximum activities */
3797  consdataUpdateAddCoef(scip, consdata, var, val, FALSE);
3798 
3799  /* update maximum activity delta */
3800  if( !SCIPisInfinity(scip, consdata->maxactdelta ) )
3801  {
3802  SCIP_Real lb;
3803  SCIP_Real ub;
3804 
3805  lb = SCIPvarGetLbLocal(var);
3806  ub = SCIPvarGetUbLocal(var);
3807 
3808  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
3809  {
3810  consdata->maxactdelta = SCIPinfinity(scip);
3811  consdata->maxactdeltavar = var;
3812  }
3813  else
3814  {
3815  SCIP_Real domain = ub - lb;
3816  SCIP_Real delta = REALABS(val) * domain;
3817 
3818  if( delta > consdata->maxactdelta )
3819  {
3820  consdata->maxactdelta = delta;
3821  consdata->maxactdeltavar = var;
3822  }
3823  }
3824  }
3825  }
3826 
3827  /* install rounding locks for new variable */
3828  SCIP_CALL( lockRounding(scip, cons, var, val) );
3829 
3830  /* mark the constraint for propagation */
3831  if( transformed )
3832  {
3833  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
3834  }
3835 
3836  consdata->boundstightened = 0;
3837  consdata->presolved = FALSE;
3838  consdata->removedfixings = consdata->removedfixings && SCIPvarIsActive(var);
3839 
3840  if( consdata->validsignature )
3841  consdataUpdateSignatures(consdata, consdata->nvars-1);
3842 
3843  consdata->changed = TRUE;
3844  consdata->normalized = FALSE;
3845  consdata->upgradetried = FALSE;
3846  consdata->cliquesadded = FALSE;
3847  consdata->implsadded = FALSE;
3848  consdata->rangedrowpropagated = 0;
3849 
3850  if( consdata->nvars == 1 )
3851  {
3852  consdata->indexsorted = TRUE;
3853  consdata->coefsorted = TRUE;
3854  consdata->merged = TRUE;
3855  }
3856  else
3857  {
3858  consdata->merged = FALSE;
3859 
3860  if( SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE )
3861  {
3862  consdata->indexsorted = consdata->indexsorted && (consdataCompVar((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
3863  consdata->coefsorted = FALSE;
3864  }
3865  else
3866  {
3867  consdata->indexsorted = FALSE;
3868  consdata->coefsorted = consdata->coefsorted && (consdataCompVarProp((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
3869  }
3870  }
3871 
3872  /* update hascontvar and hasnonbinvar flags */
3873  if( consdata->hasnonbinvalid && !consdata->hascontvar )
3874  {
3875  SCIP_VARTYPE vartype = SCIPvarGetType(var);
3876 
3877  if( vartype != SCIP_VARTYPE_BINARY )
3878  {
3879  consdata->hasnonbinvar = TRUE;
3880 
3881  if( vartype == SCIP_VARTYPE_CONTINUOUS )
3882  consdata->hascontvar = TRUE;
3883  }
3884  }
3885 
3886  /* add the new coefficient to the LP row */
3887  if( consdata->row != NULL )
3888  {
3889  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, val) );
3890  }
3891 
3892  return SCIP_OKAY;
3893 }
3894 
3895 /** deletes coefficient at given position from linear constraint data */
3896 static
3898  SCIP* scip, /**< SCIP data structure */
3899  SCIP_CONS* cons, /**< linear constraint */
3900  int pos /**< position of coefficient to delete */
3901  )
3902 {
3903  SCIP_CONSDATA* consdata;
3904  SCIP_VAR* var;
3905  SCIP_Real val;
3906 
3907  assert(scip != NULL);
3908  assert(cons != NULL);
3909 
3910  consdata = SCIPconsGetData(cons);
3911  assert(consdata != NULL);
3912  assert(0 <= pos && pos < consdata->nvars);
3913 
3914  var = consdata->vars[pos];
3915  val = consdata->vals[pos];
3916  assert(var != NULL);
3917 
3918  /* remove rounding locks for deleted variable */
3919  SCIP_CALL( unlockRounding(scip, cons, var, val) );
3920 
3921  /* if we are in transformed problem, delete the event data of the variable */
3922  if( SCIPconsIsTransformed(cons) )
3923  {
3924  SCIP_CONSHDLR* conshdlr;
3925  SCIP_CONSHDLRDATA* conshdlrdata;
3926 
3927  /* check for event handler */
3928  conshdlr = SCIPconsGetHdlr(cons);
3929  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3930  assert(conshdlrdata != NULL);
3931  assert(conshdlrdata->eventhdlr != NULL);
3932 
3933  /* drop bound change events of variable */
3934  if( consdata->eventdata != NULL )
3935  {
3936  SCIP_CALL( consDropEvent(scip, cons, conshdlrdata->eventhdlr, pos) );
3937  assert(consdata->eventdata[pos] == NULL);
3938  }
3939  }
3940 
3941  /* move the last variable to the free slot */
3942  if( pos != consdata->nvars - 1 )
3943  {
3944  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
3945  consdata->vals[pos] = consdata->vals[consdata->nvars-1];
3946 
3947  if( consdata->eventdata != NULL )
3948  {
3949  consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
3950  assert(consdata->eventdata[pos] != NULL);
3951  consdata->eventdata[pos]->varpos = pos;
3952  }
3953 
3954  consdata->indexsorted = consdata->indexsorted && (pos + 2 >= consdata->nvars);
3955  consdata->coefsorted = consdata->coefsorted && (pos + 2 >= consdata->nvars);
3956  }
3957  consdata->nvars--;
3958 
3959  /* if at most one variable is left, the activities should be recalculated (to correspond exactly to the bounds
3960  * of the remaining variable, or give exactly 0.0)
3961  */
3962  if( consdata->nvars <= 1 )
3963  consdataInvalidateActivities(consdata);
3964  else
3965  {
3966  if( SCIPconsIsTransformed(cons) )
3967  {
3968  /* if we are in transformed problem, update minimum and maximum activities */
3969  consdataUpdateDelCoef(scip, consdata, var, val, TRUE);
3970 
3971  /* if the variable defining the maximal activity delta was removed from the constraint, the maximal activity
3972  * delta needs to be recalculated on the next real propagation
3973  */
3974  if( consdata->maxactdeltavar == var )
3975  {
3976  consdata->maxactdelta = SCIP_INVALID;
3977  consdata->maxactdeltavar = NULL;
3978  }
3979  }
3980  }
3981 
3982  /* mark the constraint for propagation */
3983  if( SCIPconsIsTransformed(cons) )
3984  {
3985  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
3986  }
3987 
3988  consdata->boundstightened = 0;
3989  consdata->presolved = FALSE;
3990  consdata->validsignature = FALSE;
3991  consdata->changed = TRUE;
3992  consdata->normalized = FALSE;
3993  consdata->upgradetried = FALSE;
3994  consdata->cliquesadded = FALSE;
3995  consdata->implsadded = FALSE;
3996  consdata->rangedrowpropagated = 0;
3997 
3998  /* check if hasnonbinvar flag might be incorrect now */
3999  if( consdata->hasnonbinvar && SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
4000  {
4001  consdata->hasnonbinvalid = FALSE;
4002  }
4003 
4004  /* delete coefficient from the LP row */
4005  if( consdata->row != NULL )
4006  {
4007  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, -val) );
4008  }
4009 
4010  /* release variable */
4011  SCIP_CALL( SCIPreleaseVar(scip, &var) );
4012 
4013  return SCIP_OKAY;
4014 }
4015 
4016 /** changes coefficient value at given position of linear constraint data */
4017 static
4019  SCIP* scip, /**< SCIP data structure */
4020  SCIP_CONS* cons, /**< linear constraint */
4021  int pos, /**< position of coefficient to delete */
4022  SCIP_Real newval /**< new value of coefficient */
4023  )
4024 {
4025  SCIP_CONSDATA* consdata;
4026  SCIP_VAR* var;
4027  SCIP_Real val;
4028  SCIP_Bool locked;
4029  int i;
4030 
4031  assert(scip != NULL);
4032  assert(cons != NULL);
4033  assert(!SCIPisZero(scip, newval));
4034 
4035  consdata = SCIPconsGetData(cons);
4036  assert(consdata != NULL);
4037  assert(0 <= pos && pos < consdata->nvars);
4038  assert(!SCIPisZero(scip, newval));
4039 
4040  var = consdata->vars[pos];
4041  val = consdata->vals[pos];
4042  assert(var != NULL);
4043  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var));
4044 
4045  locked = FALSE;
4046  for( i = 0; i < NLOCKTYPES && !locked; i++ )
4047  locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
4048 
4049  /* if necessary, update the rounding locks of the variable */
4050  if( locked && newval * val < 0.0 )
4051  {
4052  assert(SCIPconsIsTransformed(cons));
4053 
4054  /* remove rounding locks for variable with old coefficient */
4055  SCIP_CALL( unlockRounding(scip, cons, var, val) );
4056 
4057  /* install rounding locks for variable with new coefficient */
4058  SCIP_CALL( lockRounding(scip, cons, var, newval) );
4059  }
4060 
4061  /* change the value */
4062  consdata->vals[pos] = newval;
4063 
4064  if( consdata->coefsorted )
4065  {
4066  if( pos > 0 )
4067  consdata->coefsorted = (consdataCompVarProp((void*)consdata, pos - 1, pos) <= 0);
4068  if( consdata->coefsorted && pos < consdata->nvars - 1 )
4069  consdata->coefsorted = (consdataCompVarProp((void*)consdata, pos, pos + 1) <= 0);
4070  }
4071 
4072  /* update minimum and maximum activities */
4073  if( SCIPconsIsTransformed(cons) )
4074  consdataUpdateChgCoef(scip, consdata, var, val, newval, TRUE);
4075 
4076  /* mark the constraint for propagation */
4077  if( SCIPconsIsTransformed(cons) )
4078  {
4079  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
4080  }
4081 
4082  consdata->boundstightened = 0;
4083  consdata->presolved = FALSE;
4084  consdata->validsignature = consdata->validsignature && (newval * val > 0.0);
4085  consdata->changed = TRUE;
4086  consdata->normalized = FALSE;
4087  consdata->upgradetried = FALSE;
4088  consdata->cliquesadded = FALSE;
4089  consdata->implsadded = FALSE;
4090  consdata->rangedrowpropagated = 0;
4091 
4092  return SCIP_OKAY;
4093 }
4094 
4095 /** scales a linear constraint with a constant scalar */
4096 static
4098  SCIP* scip, /**< SCIP data structure */
4099  SCIP_CONS* cons, /**< linear constraint to scale */
4100  SCIP_Real scalar /**< value to scale constraint with */
4101  )
4102 {
4103  SCIP_CONSDATA* consdata;
4104  SCIP_Real newval;
4105  SCIP_Real absscalar;
4106  int i;
4107 
4108  assert(scip != NULL);
4109  assert(cons != NULL);
4110 
4111  consdata = SCIPconsGetData(cons);
4112  assert(consdata != NULL);
4113  assert(consdata->row == NULL);
4114  assert(!SCIPisEQ(scip, scalar, 1.0));
4115 
4116  if( (!SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -consdata->lhs * scalar))
4117  || (!SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, consdata->rhs * scalar)) )
4118  {
4119  SCIPwarningMessage(scip, "skipped scaling for linear constraint <%s> to avoid numerical troubles (scalar: %.15g)\n",
4120  SCIPconsGetName(cons), scalar);
4121 
4122  return SCIP_OKAY;
4123  }
4124 
4125  /* scale the coefficients */
4126  for( i = consdata->nvars - 1; i >= 0; --i )
4127  {
4128  newval = scalar * consdata->vals[i];
4129 
4130  /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
4131  * flooring down our new value
4132  */
4133  if( SCIPisScalingIntegral(scip, consdata->vals[i], scalar) )
4134  newval = SCIPfeasFloor(scip, newval + 0.5);
4135 
4136  if( SCIPisZero(scip, newval) )
4137  {
4138  SCIPwarningMessage(scip, "coefficient %.15g of variable <%s> in linear constraint <%s> scaled to zero (scalar: %.15g)\n",
4139  consdata->vals[i], SCIPvarGetName(consdata->vars[i]), SCIPconsGetName(cons), scalar);
4140  SCIP_CALL( delCoefPos(scip, cons, i) );
4141  }
4142  else
4143  consdata->vals[i] = newval;
4144  }
4145 
4146  /* scale the sides */
4147  if( scalar < 0.0 )
4148  {
4149  SCIP_Real lhs;
4150 
4151  lhs = consdata->lhs;
4152  consdata->lhs = -consdata->rhs;
4153  consdata->rhs = -lhs;
4154  }
4155  absscalar = REALABS(scalar);
4156  if( !SCIPisInfinity(scip, -consdata->lhs) )
4157  {
4158  newval = absscalar * consdata->lhs;
4159 
4160  /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
4161  * flooring down our new value
4162  */
4163  if( SCIPisScalingIntegral(scip, consdata->lhs, absscalar) )
4164  consdata->lhs = SCIPfeasFloor(scip, newval + 0.5);
4165  else
4166  consdata->lhs = newval;
4167  }
4168  if( !SCIPisInfinity(scip, consdata->rhs) )
4169  {
4170  newval = absscalar * consdata->rhs;
4171 
4172  /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasCeil, we subtract 0.5 before ceiling up
4173  * our new value
4174  */
4175  if( SCIPisScalingIntegral(scip, consdata->rhs, absscalar) )
4176  consdata->rhs = SCIPfeasCeil(scip, newval - 0.5);
4177  else
4178  consdata->rhs = newval;
4179  }
4180 
4181  consdataInvalidateActivities(consdata);
4182  consdata->cliquesadded = FALSE;
4183  consdata->implsadded = FALSE;
4184 
4185  return SCIP_OKAY;
4186 }
4187 
4188 /** perform deletion of variables in all constraints of the constraint handler */
4189 static
4191  SCIP* scip, /**< SCIP data structure */
4192  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4193  SCIP_CONS** conss, /**< array of constraints */
4194  int nconss /**< number of constraints */
4195  )
4196 {
4197  SCIP_CONSDATA* consdata;
4198  int i;
4199  int v;
4200 
4201  assert(scip != NULL);
4202  assert(conshdlr != NULL);
4203  assert(conss != NULL);
4204  assert(nconss >= 0);
4205  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4206 
4207  /* iterate over all constraints */
4208  for( i = 0; i < nconss; i++ )
4209  {
4210  consdata = SCIPconsGetData(conss[i]);
4211 
4212  /* constraint is marked, that some of its variables were deleted */
4213  if( consdata->varsdeleted )
4214  {
4215  /* iterate over all variables of the constraint and delete them from the constraint */
4216  for( v = consdata->nvars - 1; v >= 0; --v )
4217  {
4218  if( SCIPvarIsDeleted(consdata->vars[v]) )
4219  {
4220  SCIP_CALL( delCoefPos(scip, conss[i], v) );
4221  }
4222  }
4223  consdata->varsdeleted = FALSE;
4224  }
4225  }
4226 
4227  return SCIP_OKAY;
4228 }
4229 
4230 
4231 /** normalizes a linear constraint with the following rules:
4232  * - if all coefficients have them same absolute value, change them to (-)1.0
4233  * - multiplication with +1 or -1:
4234  * Apply the following rules in the given order, until the sign of the factor is determined. Later rules only apply,
4235  * if the current rule doesn't determine the sign):
4236  * 1. the right hand side must not be negative
4237  * 2. the right hand side must not be infinite
4238  * 3. the absolute value of the right hand side must be greater than that of the left hand side
4239  * 4. the number of positive coefficients must not be smaller than the number of negative coefficients
4240  * 5. multiply with +1
4241  * - rationals to integrals
4242  * Try to identify a rational representation of the fractional coefficients, and multiply all coefficients
4243  * by the smallest common multiple of all denominators to get integral coefficients.
4244  * Forbid large denominators due to numerical stability.
4245  * - division by greatest common divisor
4246  * If all coefficients are integral, divide them by the greatest common divisor.
4247  */
4248 static
4250  SCIP* scip, /**< SCIP data structure */
4251  SCIP_CONS* cons, /**< linear constraint to normalize */
4252  SCIP_Bool* infeasible /**< pointer to store whether infeasibility was detected */
4253  )
4254 {
4255  SCIP_CONSDATA* consdata;
4256  SCIP_Real* vals;
4257  SCIP_Longint scm;
4258  SCIP_Longint nominator;
4259  SCIP_Longint denominator;
4260  SCIP_Longint gcd;
4261  SCIP_Longint maxmult;
4262  SCIP_Real epsilon;
4263  SCIP_Real feastol;
4264  SCIP_Real maxabsval;
4265  SCIP_Real minabsval;
4266  SCIP_Bool success;
4267  SCIP_Bool onlyintegral;
4268  int nvars;
4269  int mult;
4270  int nposcoeffs;
4271  int nnegcoeffs;
4272  int i;
4273  int v;
4274 
4275  assert(scip != NULL);
4276  assert(cons != NULL);
4277  assert(infeasible != NULL);
4278 
4279  *infeasible = FALSE;
4280 
4281  /* we must not change a modifiable constraint in any way */
4282  if( SCIPconsIsModifiable(cons) )
4283  return SCIP_OKAY;
4284 
4285  /* get constraint data */
4286  consdata = SCIPconsGetData(cons);
4287  assert(consdata != NULL);
4288 
4289  /* check, if the constraint is already normalized */
4290  if( consdata->normalized )
4291  return SCIP_OKAY;
4292 
4293  /* get coefficient arrays */
4294  vals = consdata->vals;
4295  nvars = consdata->nvars;
4296  assert(nvars == 0 || vals != NULL);
4297 
4298  if( nvars == 0 )
4299  {
4300  consdata->normalized = TRUE;
4301  return SCIP_OKAY;
4302  }
4303 
4304  assert(vals != NULL);
4305 
4306  /* get maximal and minimal absolute coefficient */
4307  maxabsval = consdataGetMaxAbsval(consdata);
4308  minabsval = consdataGetMinAbsval(consdata);
4309 
4310  /* return if scaling by maxval will eliminate coefficients */
4311  if( SCIPisZero(scip, minabsval/maxabsval) )
4312  return SCIP_OKAY;
4313 
4314  /* check if all coefficients are in absolute value equal, and not 1.0 */
4315  if( !SCIPisEQ(scip, maxabsval, 1.0) )
4316  {
4317  SCIP_Bool abscoefsequ;
4318 
4319  abscoefsequ = TRUE;
4320 
4321  for( v = nvars - 1; v >= 0; --v )
4322  {
4323  if( !SCIPisEQ(scip, REALABS(vals[v]), maxabsval) )
4324  {
4325  abscoefsequ = FALSE;
4326  break;
4327  }
4328  }
4329 
4330  /* all coefficients are in absolute value equal, so change them to (-)1.0 */
4331  if( abscoefsequ )
4332  {
4333  SCIPdebugMsg(scip, "divide linear constraint with %g, because all coefficients are in absolute value the same\n", maxabsval);
4334  SCIPdebugPrintCons(scip, cons, NULL);
4335  SCIP_CALL( scaleCons(scip, cons, 1/maxabsval) );
4336 
4337  if( consdata->validmaxabsval )
4338  {
4339  if( !SCIPisEQ(scip, consdata->maxabsval, 1.0) )
4340  consdata->maxabsval = 1.0;
4341  if( !SCIPisEQ(scip, consdata->minabsval, 1.0) )
4342  consdata->minabsval = 1.0;
4343 
4344  maxabsval = 1.0;
4345  }
4346  else
4347  {
4348  /* get maximal absolute coefficient */
4349  maxabsval = consdataGetMaxAbsval(consdata);
4350  }
4351 
4352  /* get new consdata information, because scaleCons() might have deleted variables */
4353  vals = consdata->vals;
4354  nvars = consdata->nvars;
4355 
4356  assert(nvars == 0 || vals != NULL);
4357  }
4358  }
4359 
4360  /* nvars might have changed */
4361  if( nvars == 0 )
4362  {
4363  consdata->normalized = TRUE;
4364  return SCIP_OKAY;
4365  }
4366 
4367  assert(vals != NULL);
4368 
4369  /* calculate the maximal multiplier for common divisor calculation:
4370  * |p/q - val| < epsilon and q < feastol/epsilon => |p - q*val| < feastol
4371  * which means, a value of feastol/epsilon should be used as maximal multiplier;
4372  * additionally, we don't want to scale the constraint if this would lead to too
4373  * large coefficients
4374  */
4375  epsilon = SCIPepsilon(scip) * 0.9; /* slightly decrease epsilon to be safe in rational conversion below */
4376  feastol = SCIPfeastol(scip);
4377  maxmult = (SCIP_Longint)(feastol/epsilon + feastol);
4378 
4379  if( !consdata->hasnonbinvalid )
4380  consdataCheckNonbinvar(consdata);
4381 
4382  /* if all variables are of integral type we will allow a greater multiplier */
4383  if( !consdata->hascontvar )
4384  maxmult = MIN(maxmult, (SCIP_Longint) (MAXSCALEDCOEFINTEGER / MAX(maxabsval, 1.0))); /*lint !e835*/
4385  else
4386  maxmult = MIN(maxmult, (SCIP_Longint) (MAXSCALEDCOEF / MAX(maxabsval, 1.0))); /*lint !e835*/
4387 
4388  /*
4389  * multiplication with +1 or -1
4390  */
4391  mult = 0;
4392 
4393  /* 1. the right hand side must not be negative */
4394  if( SCIPisPositive(scip, consdata->lhs) )
4395  mult = +1;
4396  else if( SCIPisNegative(scip, consdata->rhs) )
4397  mult = -1;
4398 
4399  if( mult == 0 )
4400  {
4401  /* 2. the right hand side must not be infinite */
4402  if( SCIPisInfinity(scip, -consdata->lhs) )
4403  mult = +1;
4404  else if( SCIPisInfinity(scip, consdata->rhs) )
4405  mult = -1;
4406  }
4407 
4408  if( mult == 0 )
4409  {
4410  /* 3. the absolute value of the right hand side must be greater than that of the left hand side */
4411  if( SCIPisGT(scip, REALABS(consdata->rhs), REALABS(consdata->lhs)) )
4412  mult = +1;
4413  else if( SCIPisLT(scip, REALABS(consdata->rhs), REALABS(consdata->lhs)) )
4414  mult = -1;
4415  }
4416 
4417  if( mult == 0 )
4418  {
4419  /* 4. the number of positive coefficients must not be smaller than the number of negative coefficients */
4420  nposcoeffs = 0;
4421  nnegcoeffs = 0;
4422  for( i = 0; i < nvars; ++i )
4423  {
4424  if( vals[i] > 0.0 )
4425  nposcoeffs++;
4426  else
4427  nnegcoeffs++;
4428  }
4429  if( nposcoeffs > nnegcoeffs )
4430  mult = +1;
4431  else if( nposcoeffs < nnegcoeffs )
4432  mult = -1;
4433  }
4434 
4435  if( mult == 0 )
4436  {
4437  /* 5. multiply with +1 */
4438  mult = +1;
4439  }
4440 
4441  assert(mult == +1 || mult == -1);
4442  if( mult == -1 )
4443  {
4444  /* scale the constraint with -1 */
4445  SCIPdebugMsg(scip, "multiply linear constraint with -1.0\n");
4446  SCIPdebugPrintCons(scip, cons, NULL);
4447  SCIP_CALL( scaleCons(scip, cons, -1.0) );
4448 
4449  /* scalecons() can delete variables, but scaling with -1 should not do that */
4450  assert(nvars == consdata->nvars);
4451  }
4452 
4453  /*
4454  * rationals to integrals
4455  *
4456  * @todo try scaling only on behalf of non-continuous variables
4457  */
4458  success = TRUE;
4459  scm = 1;
4460  for( i = 0; i < nvars && success && scm <= maxmult; ++i )
4461  {
4462  if( !SCIPisIntegral(scip, vals[i]) )
4463  {
4464  /* epsilon has been slightly decreased above - to be on the safe side */
4465  success = SCIPrealToRational(vals[i], -epsilon, epsilon , maxmult, &nominator, &denominator);
4466  if( success )
4467  scm = SCIPcalcSmaComMul(scm, denominator);
4468  }
4469  }
4470  assert(scm >= 1);
4471 
4472  /* it might be that we have really big coefficients, but all are integral, in that case we want to divide them by
4473  * their greatest common divisor
4474  */
4475  onlyintegral = TRUE;
4476  if( scm == 1 )
4477  {
4478  for( i = nvars - 1; i >= 0; --i )
4479  {
4480  if( !SCIPisIntegral(scip, vals[i]) )
4481  {
4482  onlyintegral = FALSE;
4483  break;
4484  }
4485  }
4486  }
4487 
4488  success = success && (scm <= maxmult || (scm == 1 && onlyintegral));
4489  if( success && scm != 1 )
4490  {
4491  /* scale the constraint with the smallest common multiple of all denominators */
4492  SCIPdebugMsg(scip, "scale linear constraint with %" SCIP_LONGINT_FORMAT " to make coefficients integral\n", scm);
4493  SCIPdebugPrintCons(scip, cons, NULL);
4494  SCIP_CALL( scaleCons(scip, cons, (SCIP_Real)scm) );
4495 
4496  if( consdata->validmaxabsval )
4497  {
4498  consdata->maxabsval *= REALABS((SCIP_Real)scm);
4499  if( !SCIPisIntegral(scip, consdata->maxabsval) )
4500  {
4501  consdata->validmaxabsval = FALSE;
4502  consdata->maxabsval = SCIP_INVALID;
4503  consdataCalcMaxAbsval(consdata);
4504  }
4505  }
4506 
4507  if( consdata->validminabsval )
4508  {
4509  consdata->minabsval *= REALABS((SCIP_Real)scm);
4510  if( !SCIPisIntegral(scip, consdata->minabsval) )
4511  {
4512  consdata->validminabsval = FALSE;
4513  consdata->minabsval = SCIP_INVALID;
4514  consdataCalcMinAbsval(consdata);
4515  }
4516  }
4517 
4518  /* get new consdata information, because scalecons() might have deleted variables */
4519  vals = consdata->vals;
4520  nvars = consdata->nvars;
4521  assert(nvars == 0 || vals != NULL);
4522  }
4523 
4524  /*
4525  * division by greatest common divisor
4526  */
4527  if( success && nvars >= 1 )
4528  {
4529  /* all coefficients are integral: divide them by their greatest common divisor */
4530  assert(SCIPisIntegral(scip, vals[0]));
4531 
4532  gcd = (SCIP_Longint)(REALABS(vals[0]) + feastol);
4533  for( i = 1; i < nvars && gcd > 1; ++i )
4534  {
4535  assert(SCIPisIntegral(scip, vals[i]));
4536  gcd = SCIPcalcGreComDiv(gcd, (SCIP_Longint)(REALABS(vals[i]) + feastol));
4537  }
4538 
4539  if( gcd > 1 )
4540  {
4541  /* since the lhs/rhs is not respected for gcd calculation it can happen that we detect infeasibility */
4542  if( !consdata->hascontvar && onlyintegral )
4543  {
4544  if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) && !SCIPisFeasIntegral(scip, consdata->rhs / gcd) )
4545  {
4546  *infeasible = TRUE;
4547 
4548  SCIPdebugMsg(scip, "detected infeasibility of constraint after scaling with gcd=%" SCIP_LONGINT_FORMAT ":\n", gcd);
4549  SCIPdebugPrintCons(scip, cons, NULL);
4550 
4551  return SCIP_OKAY;
4552  }
4553  }
4554 
4555  /* divide the constraint by the greatest common divisor of the coefficients */
4556  SCIPdebugMsg(scip, "divide linear constraint by greatest common divisor %" SCIP_LONGINT_FORMAT "\n", gcd);
4557  SCIPdebugPrintCons(scip, cons, NULL);
4558  SCIP_CALL( scaleCons(scip, cons, 1.0/(SCIP_Real)gcd) );
4559 
4560  if( consdata->validmaxabsval )
4561  {
4562  consdata->maxabsval /= REALABS((SCIP_Real)gcd);
4563  }
4564  if( consdata->validminabsval )
4565  {
4566  consdata->minabsval /= REALABS((SCIP_Real)gcd);
4567  }
4568  }
4569  }
4570 
4571  /* mark constraint to be normalized */
4572  consdata->normalized = TRUE;
4573 
4574  SCIPdebugMsg(scip, "normalized constraint:\n");
4575  SCIPdebugPrintCons(scip, cons, NULL);
4576 
4577  return SCIP_OKAY;
4578 }
4579 
4580 /** replaces multiple occurrences of a variable by a single coefficient */
4581 static
4583  SCIP* scip, /**< SCIP data structure */
4584  SCIP_CONS* cons /**< linear constraint */
4585  )
4586 {
4587  SCIP_CONSDATA* consdata;
4588  SCIP_VAR* var;
4589  SCIP_Real valsum;
4590  int v;
4591 
4592  assert(scip != NULL);
4593  assert(cons != NULL);
4594 
4595  consdata = SCIPconsGetData(cons);
4596  assert(consdata != NULL);
4597 
4598  if( consdata->merged )
4599  return SCIP_OKAY;
4600 
4601  /* sort the constraint */
4602  SCIP_CALL( consdataSort(scip, consdata) );
4603 
4604  /* go backwards through the constraint looking for multiple occurrences of the same variable;
4605  * backward direction is necessary, since delCoefPos() modifies the given position and
4606  * the subsequent ones
4607  */
4608  v = consdata->nvars-1;
4609  while( v >= 1 )
4610  {
4611  var = consdata->vars[v];
4612  if( consdata->vars[v-1] == var )
4613  {
4614  valsum = consdata->vals[v];
4615  do
4616  {
4617  SCIP_CALL( delCoefPos(scip, cons, v) );
4618  --v;
4619  valsum += consdata->vals[v];
4620  }
4621  while( v >= 1 && consdata->vars[v-1] == var );
4622 
4623  /* modify the last existing occurrence of the variable */
4624  assert(consdata->vars[v] == var);
4625  if( SCIPisZero(scip, valsum) )
4626  {
4627  SCIP_CALL( delCoefPos(scip, cons, v) );
4628 
4629  /* if the variable defining the maximal activity delta was removed from the constraint, the maximal activity
4630  * delta needs to be recalculated on the next real propagation
4631  */
4632  if( consdata->maxactdeltavar == var )
4633  {
4634  consdata->maxactdelta = SCIP_INVALID;
4635  consdata->maxactdeltavar = NULL;
4636  }
4637  }
4638  else
4639  {
4640  SCIP_CALL( chgCoefPos(scip, cons, v, valsum) );
4641  }
4642  }
4643  --v;
4644  }
4645 
4646  consdata->merged = TRUE;
4647 
4648  return SCIP_OKAY;
4649 }
4650 
4651 /** replaces all fixed and aggregated variables by their non-fixed counterparts */
4652 static
4654  SCIP* scip, /**< SCIP data structure */
4655  SCIP_CONS* cons, /**< linear constraint */
4656  SCIP_Bool* infeasible /**< pointer to store if infeasibility is detected; or NULL if this
4657  * information is not needed; in this case, we apply all fixings
4658  * instead of stopping after the first infeasible one */
4659  )
4660 {
4661  SCIP_CONSDATA* consdata;
4662  SCIP_VAR* var;
4663  SCIP_VAR** aggrvars;
4664  SCIP_Real val;
4665  SCIP_Real* aggrscalars;
4666  SCIP_Real fixedval;
4667  SCIP_Real aggrconst;
4668  int v;
4669  int naggrvars;
4670  int i;
4671 
4672  assert(scip != NULL);
4673  assert(cons != NULL);
4674 
4675  if( infeasible != NULL )
4676  *infeasible = FALSE;
4677 
4678  consdata = SCIPconsGetData(cons);
4679  assert(consdata != NULL);
4680 
4681  if( consdata->eventdata == NULL )
4682  {
4683  SCIP_CONSHDLR* conshdlr;
4684  SCIP_CONSHDLRDATA* conshdlrdata;
4685 
4686  conshdlr = SCIPconsGetHdlr(cons);
4687  assert(conshdlr != NULL);
4688 
4689  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4690  assert(conshdlrdata != NULL);
4691 
4692  /* catch bound change events of variables */
4693  SCIP_CALL( consCatchAllEvents(scip, cons, conshdlrdata->eventhdlr) );
4694  assert(consdata->eventdata != NULL);
4695  }
4696 
4697  if( !consdata->removedfixings )
4698  {
4699  SCIP_Real lhssubtrahend;
4700  SCIP_Real rhssubtrahend;
4701 
4702  /* if an unmodifiable row has been added to the LP, then we cannot apply fixing anymore (cannot change a row)
4703  * this should not happen, as applyFixings is called in addRelaxation() before creating and adding a row
4704  */
4705  assert(consdata->row == NULL || !SCIProwIsInLP(consdata->row) || SCIProwIsModifiable(consdata->row));
4706 
4707  lhssubtrahend = 0.0;
4708  rhssubtrahend = 0.0;
4709 
4710  SCIPdebugMsg(scip, "applying fixings:\n");
4711  SCIPdebugPrintCons(scip, cons, NULL);
4712 
4713  v = 0;
4714  while( v < consdata->nvars )
4715  {
4716  var = consdata->vars[v];
4717  val = consdata->vals[v];
4718  assert(SCIPvarIsTransformed(var));
4719 
4720  switch( SCIPvarGetStatus(var) )
4721  {
4723  SCIPerrorMessage("original variable in transformed linear constraint\n");
4724  return SCIP_INVALIDDATA;
4725 
4726  case SCIP_VARSTATUS_LOOSE:
4727  case SCIP_VARSTATUS_COLUMN:
4728  ++v;
4729  break;
4730 
4731  case SCIP_VARSTATUS_FIXED:
4732  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)));
4733  fixedval = SCIPvarGetLbGlobal(var);
4734  if( !SCIPisInfinity(scip, -consdata->lhs) )
4735  {
4736  if( SCIPisInfinity(scip, ABS(fixedval)) )
4737  {
4738  if( val * fixedval > 0.0 )
4739  {
4740  SCIP_CALL( chgLhs(scip, cons, -SCIPinfinity(scip)) );
4741  }
4742  else
4743  {
4744  if( infeasible != NULL )
4745  {
4746  /* if lhs gets infinity it means that the problem is infeasible */
4747  *infeasible = TRUE;
4748  return SCIP_OKAY;
4749  }
4750  else
4751  {
4752  SCIP_CALL( chgLhs(scip, cons, SCIPinfinity(scip)) );
4753  }
4754  }
4755  }
4756  else
4757  lhssubtrahend += val * fixedval;
4758  }
4759  if( !SCIPisInfinity(scip, consdata->rhs) )
4760  {
4761  if( SCIPisInfinity(scip, ABS(fixedval)) )
4762  {
4763  if( val * fixedval > 0.0 )
4764  {
4765  if( infeasible != NULL )
4766  {
4767  /* if rhs gets -infinity it means that the problem is infeasible */
4768  *infeasible = TRUE;
4769  return SCIP_OKAY;
4770  }
4771  else
4772  {
4773  SCIP_CALL( chgRhs(scip, cons, -SCIPinfinity(scip)) );
4774  }
4775  }
4776  else
4777  {
4778  SCIP_CALL( chgRhs(scip, cons, SCIPinfinity(scip)) );
4779  }
4780  }
4781  else
4782  rhssubtrahend += val * fixedval;
4783  }
4784  SCIP_CALL( delCoefPos(scip, cons, v) );
4785  break;
4786 
4788  {
4789  SCIP_VAR* activevar = SCIPvarGetAggrVar(var);
4790  SCIP_Real activescalar = val * SCIPvarGetAggrScalar(var);
4791  SCIP_Real activeconstant = val * SCIPvarGetAggrConstant(var);
4792 
4793  assert(activevar != NULL);
4794  SCIP_CALL( SCIPgetProbvarSum(scip, &activevar, &activescalar, &activeconstant) );
4795  assert(activevar != NULL);
4796 
4797  if( !SCIPisZero(scip, activescalar) )
4798  {
4799  SCIP_CALL( addCoef(scip, cons, activevar, activescalar) );
4800  }
4801 
4802  if( !SCIPisZero(scip, activeconstant) )
4803  {
4804  if( !SCIPisInfinity(scip, -consdata->lhs) )
4805  lhssubtrahend += activeconstant;
4806  if( !SCIPisInfinity(scip, consdata->rhs) )
4807  rhssubtrahend += activeconstant;
4808  }
4809 
4810  SCIP_CALL( delCoefPos(scip, cons, v) );
4811  break;
4812  }
4815  naggrvars = SCIPvarGetMultaggrNVars(var);
4816  aggrvars = SCIPvarGetMultaggrVars(var);
4817  aggrscalars = SCIPvarGetMultaggrScalars(var);
4818  for( i = 0; i < naggrvars; ++i )
4819  {
4820  SCIP_CALL( addCoef(scip, cons, aggrvars[i], val * aggrscalars[i]) );
4821  }
4822  aggrconst = SCIPvarGetMultaggrConstant(var);
4823 
4824  if( !SCIPisInfinity(scip, -consdata->lhs) )
4825  lhssubtrahend += val * aggrconst;
4826  if( !SCIPisInfinity(scip, consdata->rhs) )
4827  rhssubtrahend += val * aggrconst;
4828 
4829  SCIP_CALL( delCoefPos(scip, cons, v) );
4830  break;
4831 
4833  SCIP_CALL( addCoef(scip, cons, SCIPvarGetNegationVar(var), -val) );
4834  aggrconst = SCIPvarGetNegationConstant(var);
4835 
4836  if( !SCIPisInfinity(scip, -consdata->lhs) )
4837  lhssubtrahend += val * aggrconst;
4838  if( !SCIPisInfinity(scip, consdata->rhs) )
4839  rhssubtrahend += val * aggrconst;
4840 
4841  SCIP_CALL( delCoefPos(scip, cons, v) );
4842  break;
4843 
4844  default:
4845  SCIPerrorMessage("unknown variable status\n");
4846  SCIPABORT();
4847  return SCIP_INVALIDDATA; /*lint !e527*/
4848  }
4849  }
4850 
4851  if( !SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->lhs) )
4852  {
4853  /* for large numbers that are relatively equal, substraction can lead to cancellation,
4854  * causing wrong fixings of other variables --> better use a real zero here;
4855  * for small numbers, polishing the difference might lead to wrong results -->
4856  * better use the exact difference in this case
4857  */
4858  if( SCIPisEQ(scip, lhssubtrahend, consdata->lhs) && SCIPisFeasGE(scip, REALABS(lhssubtrahend), 1.0) )
4859  {
4860  SCIP_CALL( chgLhs(scip, cons, 0.0) );
4861  }
4862  else
4863  {
4864  SCIP_CALL( chgLhs(scip, cons, consdata->lhs - lhssubtrahend) );
4865  }
4866  }
4867  if( !SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, -consdata->rhs))
4868  {
4869  /* for large numbers that are relatively equal, substraction can lead to cancellation,
4870  * causing wrong fixings of other variables --> better use a real zero here;
4871  * for small numbers, polishing the difference might lead to wrong results -->
4872  * better use the exact difference in this case
4873  */
4874  if( SCIPisEQ(scip, rhssubtrahend, consdata->rhs ) && SCIPisFeasGE(scip, REALABS(rhssubtrahend), 1.0) )
4875  {
4876  SCIP_CALL( chgRhs(scip, cons, 0.0) );
4877  }
4878  else
4879  {
4880  SCIP_CALL( chgRhs(scip, cons, consdata->rhs - rhssubtrahend) );
4881  }
4882  }
4883  consdata->removedfixings = TRUE;
4884 
4885  SCIPdebugMsg(scip, "after fixings:\n");
4886  SCIPdebugPrintCons(scip, cons, NULL);
4887 
4888  /* if aggregated variables have been replaced, multiple entries of the same variable are possible and we have
4889  * to clean up the constraint
4890  */
4891  SCIP_CALL( mergeMultiples(scip, cons) );
4892 
4893  SCIPdebugMsg(scip, "after merging:\n");
4894  SCIPdebugPrintCons(scip, cons, NULL);
4895  }
4896  assert(consdata->removedfixings);
4897 
4898 #ifndef NDEBUG
4899  /* check, if all fixings are applied */
4900  for( v = 0; v < consdata->nvars; ++v )
4901  assert(SCIPvarIsActive(consdata->vars[v]));
4902 #endif
4903 
4904  return SCIP_OKAY;
4905 }
4906 
4907 /** for each variable in the linear constraint, except the inferred variable, adds one bound to the conflict analysis'
4908  * candidate store (bound depends on sign of coefficient and whether the left or right hand side was the reason for the
4909  * inference variable's bound change); the conflict analysis can be initialized with the linear constraint being the
4910  * conflict detecting constraint by using NULL as inferred variable
4911  */
4912 static
4914  SCIP* scip, /**< SCIP data structure */
4915  SCIP_CONS* cons, /**< constraint that inferred the bound change */
4916  SCIP_VAR* infervar, /**< variable that was deduced, or NULL */
4917  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4918  int inferpos, /**< position of the inferred variable in the vars array */
4919  SCIP_Bool reasonisrhs /**< is the right hand side responsible for the bound change? */
4920  )
4921 {
4922  SCIP_CONSDATA* consdata;
4923  SCIP_VAR** vars;
4924  SCIP_Real* vals;
4925  int nvars;
4926  int i;
4927 
4928  assert(scip != NULL);
4929  assert(cons != NULL);
4930 
4931  consdata = SCIPconsGetData(cons);
4933  assert(consdata != NULL);
4934 
4935  vars = consdata->vars;
4936  vals = consdata->vals;
4937  nvars = consdata->nvars;
4938 
4939  assert(vars != NULL || nvars == 0);
4940  assert(vals != NULL || nvars == 0);
4941 
4942  assert(-1 <= inferpos && inferpos < nvars);
4943  assert((infervar == NULL) == (inferpos == -1));
4944  assert(inferpos == -1 || vars[inferpos] == infervar); /*lint !e613*/
4945 
4946  /* for each variable, add the bound to the conflict queue, that is responsible for the minimal or maximal
4947  * residual value, depending on whether the left or right hand side is responsible for the bound change:
4948  * - if the right hand side is the reason, the minimal residual activity is responsible
4949  * - if the left hand side is the reason, the maximal residual activity is responsible
4950  */
4951 
4952  /* if the variable is integral we only need to add reason bounds until the propagation could be applied */
4953  if( infervar == NULL || SCIPvarIsIntegral(infervar) )
4954  {
4955  SCIP_Real minresactivity;
4956  SCIP_Real maxresactivity;
4957  SCIP_Bool minisrelax;
4958  SCIP_Bool maxisrelax;
4959  SCIP_Bool isminsettoinfinity;
4960  SCIP_Bool ismaxsettoinfinity;
4961 
4962  minresactivity = -SCIPinfinity(scip);
4963  maxresactivity = SCIPinfinity(scip);
4964 
4965  /* calculate the minimal and maximal global activity of all other variables involved in the constraint */
4966  if( infervar != NULL )
4967  {
4968  assert(vals != NULL); /* for flexelint */
4969  if( reasonisrhs )
4970  consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, &minresactivity, NULL,
4971  &minisrelax, NULL, &isminsettoinfinity, NULL);
4972  else
4973  consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, NULL, &maxresactivity,
4974  NULL, &maxisrelax, NULL, &ismaxsettoinfinity);
4975  }
4976  else
4977  {
4978  if( reasonisrhs )
4979  consdataGetGlbActivityBounds(scip, consdata, FALSE, &minresactivity, NULL,
4980  &minisrelax, NULL, &isminsettoinfinity, NULL);
4981  else
4982  consdataGetGlbActivityBounds(scip, consdata, FALSE, NULL, &maxresactivity,
4983  NULL, &maxisrelax, NULL, &ismaxsettoinfinity);
4984  }
4985 
4986  /* we can only do something clever, if the residual activity is finite and not relaxed */
4987  if( (reasonisrhs && !isminsettoinfinity && !minisrelax) || (!reasonisrhs && !ismaxsettoinfinity && !maxisrelax) ) /*lint !e644*/
4988  {
4989  SCIP_Real rescap;
4990  SCIP_Bool resactisinf;
4991 
4992  resactisinf = FALSE;
4993 
4994  /* calculate the residual capacity that would be left, if the variable would be set to one more / one less
4995  * than its inferred bound
4996  */
4997  if( infervar != NULL )
4998  {
4999  assert(vals != NULL); /* for flexelint */
5000 
5001  if( reasonisrhs )
5002  {
5003  if( SCIPisUpdateUnreliable(scip, minresactivity, consdata->lastglbminactivity) )
5004  {
5005  consdataGetReliableResidualActivity(scip, consdata, infervar, &minresactivity, TRUE, TRUE);
5006  if( SCIPisInfinity(scip, -minresactivity) )
5007  resactisinf = TRUE;
5008  }
5009  rescap = consdata->rhs - minresactivity;
5010  }
5011  else
5012  {
5013  if( SCIPisUpdateUnreliable(scip, maxresactivity, consdata->lastglbmaxactivity) )
5014  {
5015  consdataGetReliableResidualActivity(scip, consdata, infervar, &maxresactivity, FALSE, TRUE);
5016  if( SCIPisInfinity(scip, maxresactivity) )
5017  resactisinf = TRUE;
5018  }
5019  rescap = consdata->lhs - maxresactivity;
5020  }
5021 
5022  if( reasonisrhs == (vals[inferpos] > 0.0) )
5023  rescap -= vals[inferpos] * (SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) + 1.0);
5024  else
5025  rescap -= vals[inferpos] * (SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) - 1.0);
5026  }
5027  else
5028  rescap = (reasonisrhs ? consdata->rhs - minresactivity : consdata->lhs - maxresactivity);
5029 
5030  if( !resactisinf )
5031  {
5032  /* now add bounds as reasons until the residual capacity is exceeded */
5033  for( i = 0; i < nvars; ++i )
5034  {
5035  assert( vars != NULL && vals != NULL ); /* for lint */
5036 
5037  /* zero coefficients and the inferred variable can be ignored */
5038  if( vars[i] == infervar || SCIPisZero(scip, vals[i]) )
5039  continue;
5040 
5041  /* check if the residual capacity is exceeded */
5042  if( (reasonisrhs && SCIPisFeasNegative(scip, rescap))
5043  || (!reasonisrhs && SCIPisFeasPositive(scip, rescap)) )
5044  break;
5045 
5046  /* update the residual capacity due to the local bound of this variable */
5047  if( reasonisrhs == (vals[i] > 0.0) )
5048  {
5049  /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound */
5050  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
5051  rescap -= vals[i] * (SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetLbGlobal(vars[i]));
5052  }
5053  else
5054  {
5055  /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound */
5056  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
5057  rescap -= vals[i] * (SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetUbGlobal(vars[i]));
5058  }
5059  }
5060  return SCIP_OKAY;
5061  }
5062  }
5063  }
5064 
5065  /* for a bound change on a continuous variable, all locally changed bounds are responsible */
5066  for( i = 0; i < nvars; ++i )
5067  {
5068  assert(vars != NULL); /* for flexelint */
5069  assert(vals != NULL); /* for flexelint */
5070 
5071  /* zero coefficients and the inferred variable can be ignored */
5072  if( vars[i] == infervar || SCIPisZero(scip, vals[i]) )
5073  continue;
5074 
5075  if( reasonisrhs == (vals[i] > 0.0) )
5076  {
5077  /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound is responsible */
5078  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
5079  }
5080  else
5081  {
5082  /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound is responsible */
5083  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
5084  }
5085  }
5086 
5087  return SCIP_OKAY;
5088 }
5089 
5090 /** for each variable in the linear ranged row constraint, except the inferred variable, adds the bounds of all fixed
5091  * variables to the conflict analysis' candidate store; the conflict analysis can be initialized
5092  * with the linear constraint being the conflict detecting constraint by using NULL as inferred variable
5093  */
5094 static
5096  SCIP* scip, /**< SCIP data structure */
5097  SCIP_CONS* cons, /**< constraint that inferred the bound change */
5098  SCIP_VAR* infervar, /**< variable that was deduced, or NULL */
5099  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
5100  int inferpos /**< position of the inferred variable in the vars array, or -1 */
5101  )
5102 {
5103  SCIP_CONSDATA* consdata;
5104  SCIP_VAR** vars;
5105  int nvars;
5106  int v;
5107 
5108  assert(scip != NULL);
5109  assert(cons != NULL);
5110 
5111  consdata = SCIPconsGetData(cons);
5112  assert(consdata != NULL);
5113  vars = consdata->vars;
5114  nvars = consdata->nvars;
5115  assert(vars != NULL || nvars == 0);
5116  assert(-1 <= inferpos && inferpos < nvars);
5117  assert((infervar == NULL) == (inferpos == -1));
5118  assert(inferpos == -1 || vars != NULL);
5119  assert(inferpos == -1 || vars[inferpos] == infervar); /*lint !e613*/
5120 
5121  /* collect all fixed variables */
5122  for( v = nvars - 1; v >= 0; --v )
5123  {
5124  assert(vars != NULL); /* for flexelint */
5125 
5126  /* need to add old bounds before propagation of inferrence variable */
5127  if( vars[v] == infervar )
5128  {
5129  assert(vars[v] != NULL);
5130 
5131  if( !SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetLbGlobal(vars[v])) )
5132  {
5133  /* @todo get boundchange index before this last boundchange and correct the index */
5134  SCIP_CALL( SCIPaddConflictLb(scip, vars[v], bdchgidx) );
5135  }
5136 
5137  if( !SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetUbGlobal(vars[v])) )
5138  {
5139  /* @todo get boundchange index before this last boundchange and correct the index */
5140  SCIP_CALL( SCIPaddConflictUb(scip, vars[v], bdchgidx) );
5141  }
5142 
5143  continue;
5144  }
5145 
5146  /* check for fixed variables */
5147  if( SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE)) )
5148  {
5149  /* add all bounds of fixed variables which lead to the boundchange of the given inference variable */
5150  SCIP_CALL( SCIPaddConflictLb(scip, vars[v], bdchgidx) );
5151  SCIP_CALL( SCIPaddConflictUb(scip, vars[v], bdchgidx) );
5152  }
5153  }
5154 
5155  return SCIP_OKAY;
5156 }
5157 
5158 /** add reasoning variables to conflict candidate queue which led to the conflict */
5159 static
5161  SCIP* scip, /**< SCIP data structure */
5162  SCIP_VAR** vars, /**< variables reasoning the infeasibility */
5163  int nvars, /**< number of variables reasoning the infeasibility */
5164  SCIP_VAR* var, /**< variable which was tried to fix/tighten, or NULL */
5165  SCIP_Real bound /**< bound of variable which was tried to apply, or SCIP_INVALID */
5166  )
5167 {
5168  int v;
5169 
5170  assert(scip != NULL);
5171 
5172  /* collect all variables for which the local bounds differ from their global bounds */
5173  for( v = nvars - 1; v >= 0; --v )
5174  {
5175  assert(vars != NULL);
5176 
5177  /* check for local bound changes variables */
5178  if( !SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetLbGlobal(vars[v])) )
5179  {
5180  /* add conflict bound */
5181  SCIP_CALL( SCIPaddConflictLb(scip, vars[v], 0) );
5182  }
5183 
5184  if( !SCIPisEQ(scip, SCIPvarGetUbLocal(vars[v]), SCIPvarGetUbGlobal(vars[v])) )
5185  {
5186  SCIP_CALL( SCIPaddConflictUb(scip, vars[v], 0) );
5187  }
5188  }
5189 
5190  if( var != NULL )
5191  {
5192  if( bound < SCIPvarGetLbLocal(var) )
5193  {
5194  SCIP_CALL( SCIPaddConflictLb(scip, var, 0) );
5195  }
5196 
5197  if( bound > SCIPvarGetUbLocal(var) )
5198  {
5199  SCIP_CALL( SCIPaddConflictUb(scip, var, 0) );
5200  }
5201  }
5202 
5203  return SCIP_OKAY;
5204 }
5205 
5206 /** resolves a propagation on the given variable by supplying the variables needed for applying the corresponding
5207  * propagation rule (see propagateCons()):
5208  * (1) activity residuals of all other variables tighten bounds of single variable
5209  */
5210 static
5212  SCIP* scip, /**< SCIP data structure */
5213  SCIP_CONS* cons, /**< constraint that inferred the bound change */
5214  SCIP_VAR* infervar, /**< variable that was deduced */
5215  INFERINFO inferinfo, /**< inference information */
5216  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
5217  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
5218  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
5219  )
5220 {
5221  SCIP_CONSDATA* consdata;
5222  SCIP_VAR** vars;
5223 #ifndef NDEBUG
5224  SCIP_Real* vals;
5225 #endif
5226  int nvars;
5227  int inferpos;
5228 
5229  assert(scip != NULL);
5230  assert(cons != NULL);
5231  assert(result != NULL);
5232 
5233  consdata = SCIPconsGetData(cons);
5234  assert(consdata != NULL);
5235  vars = consdata->vars;
5236  nvars = consdata->nvars;
5237 #ifndef NDEBUG
5238  vals = consdata->vals;
5239  assert(vars != NULL);
5240  assert(vals != NULL);
5241 #endif
5242 
5243  /* get the position of the inferred variable in the vars array */
5244  inferpos = inferInfoGetPos(inferinfo);
5245  if( inferpos >= nvars || vars[inferpos] != infervar )
5246  {
5247  /* find inference variable in constraint */
5248  /**@todo use a binary search here; the variables can be sorted by variable index */
5249  for( inferpos = 0; inferpos < nvars && vars[inferpos] != infervar; ++inferpos )
5250  {}
5251  }
5252  assert(inferpos < nvars);
5253  assert(vars[inferpos] == infervar);
5254  assert(!SCIPisZero(scip, vals[inferpos]));
5255 
5256  switch( inferInfoGetProprule(inferinfo) )
5257  {
5258  case PROPRULE_1_RHS:
5259  /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
5260  * constraint (only taking the other variables into account) didn't leave enough space for a larger
5261  * domain in order to not exceed the right hand side of the inequality
5262  */
5263  assert((vals[inferpos] > 0.0) == (boundtype == SCIP_BOUNDTYPE_UPPER));
5264  SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, inferpos, TRUE) );
5265  *result = SCIP_SUCCESS;
5266  break;
5267 
5268  case PROPRULE_1_LHS:
5269  /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
5270  * constraint (only taking the other variables into account) didn't leave enough space for a larger
5271  * domain in order to not fall below the left hand side of the inequality
5272  */
5273  assert((vals[inferpos] > 0.0) == (boundtype == SCIP_BOUNDTYPE_LOWER));
5274  SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, inferpos, FALSE) );
5275  *result = SCIP_SUCCESS;
5276  break;
5277 
5278  case PROPRULE_1_RANGEDROW:
5279  /* the bound of the variable was tightened, because some variables were already fixed and the leftover only allow
5280  * the given inference variable to their bounds in this given ranged row
5281  */
5282 
5283  /* check that we really have a ranged row here */
5284  assert(!SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs));
5285  SCIP_CALL( addConflictFixedVars(scip, cons, infervar, bdchgidx, inferpos) );
5286  *result = SCIP_SUCCESS;
5287  break;
5288 
5289  case PROPRULE_INVALID:
5290  default:
5291  SCIPerrorMessage("invalid inference information %d in linear constraint <%s> at position %d for %s bound of variable <%s>\n",
5292  inferInfoGetProprule(inferinfo), SCIPconsGetName(cons), inferInfoGetPos(inferinfo),
5293  boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(infervar));
5294  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
5295  SCIPinfoMessage(scip, NULL, ";\n");
5296  return SCIP_INVALIDDATA;
5297  }
5298 
5299  return SCIP_OKAY;
5300 }
5301 
5302 /** analyzes conflicting bounds on given constraint, and adds conflict constraint to problem */
5303 static
5305  SCIP* scip, /**< SCIP data structure */
5306  SCIP_CONS* cons, /**< conflict detecting constraint */
5307  SCIP_Bool reasonisrhs /**< is the right hand side responsible for the conflict? */
5308  )
5309 {
5310  /* conflict analysis can only be applied in solving stage and if it is turned on */
5312  return SCIP_OKAY;
5313 
5314  /* initialize conflict analysis */
5316 
5317  /* add the conflicting bound for each variable of infeasible constraint to conflict candidate queue */
5318  SCIP_CALL( addConflictBounds(scip, cons, NULL, NULL, -1, reasonisrhs) );
5319 
5320  /* analyze the conflict */
5321  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
5322 
5323  return SCIP_OKAY;
5324 }
5325 
5326 /** check if there is any hope of tightening some bounds */
5327 static
5329  SCIP_CONS* cons /**< linear constraint */
5330  )
5331 {
5332  SCIP_CONSDATA* consdata;
5333  int infcountmin;
5334  int infcountmax;
5335 
5336  consdata = SCIPconsGetData(cons);
5337  assert(consdata != NULL);
5338 
5339  infcountmin = consdata->minactivityneginf
5340  + consdata->minactivityposinf
5341  + consdata->minactivityneghuge
5342  + consdata->minactivityposhuge;
5343  infcountmax = consdata->maxactivityneginf
5344  + consdata->maxactivityposinf
5345  + consdata->maxactivityneghuge
5346  + consdata->maxactivityposhuge;
5348  if( infcountmin > 1 && infcountmax > 1 )
5349  return FALSE;
5350 
5351  return TRUE;
5352 }
5353 
5354 /** tighten upper bound */
5355 static
5357  SCIP* scip, /**< SCIP data structure */
5358  SCIP_CONS* cons, /**< linear constraint */
5359  int pos, /**< variable position */
5360  PROPRULE proprule, /**< propagation rule that deduced the value */
5361  SCIP_Real newub, /**< new upper bound */
5362  SCIP_Real oldub, /**< old upper bound */
5363  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
5364  int* nchgbds, /**< pointer to count the total number of tightened bounds */
5365  SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5366  )
5367 {
5368  SCIP_CONSDATA* consdata;
5369  SCIP_VAR* var;
5370  SCIP_Real lb;
5371  SCIP_Bool infeasible;
5372  SCIP_Bool tightened;
5373 
5374  assert(cons != NULL);
5375  assert(!SCIPisInfinity(scip, newub));
5376 
5377  consdata = SCIPconsGetData(cons);
5378  assert(consdata != NULL);
5379  var = consdata->vars[pos];
5380  assert(var != NULL);
5381 
5382  lb = SCIPvarGetLbLocal(var);
5383  newub = SCIPadjustedVarUb(scip, var, newub);
5384 
5385  if( force || SCIPisUbBetter(scip, newub, lb, oldub) )
5386  {
5387  SCIP_VARTYPE vartype;
5388 
5389  SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, old bds=[%.15g,%.15g], val=%.15g, activity=[%.15g,%.15g], sides=[%.15g,%.15g] -> newub=%.15g\n",
5390  SCIPconsGetName(cons), SCIPvarGetName(var), lb, oldub, consdata->vals[pos],
5391  QUAD_TO_DBL(consdata->minactivity), QUAD_TO_DBL(consdata->maxactivity), consdata->lhs, consdata->rhs, newub);
5392 
5393  vartype = SCIPvarGetType(var);
5394 
5395  /* tighten upper bound */
5396  SCIP_CALL( SCIPinferVarUbCons(scip, var, newub, cons, getInferInt(proprule, pos), force, &infeasible, &tightened) );
5397 
5398  if( infeasible )
5399  {
5400  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5401  SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);
5402 
5403  /* analyze conflict */
5404  SCIP_CALL( analyzeConflict(scip, cons, TRUE) );
5405 
5406  *cutoff = TRUE;
5407  }
5408  else if( tightened )
5409  {
5410  assert(SCIPisFeasLE(scip, SCIPvarGetUbLocal(var), oldub));
5411  SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, new bds=[%.15g,%.15g]\n",
5412  SCIPconsGetName(cons), SCIPvarGetName(var), lb, SCIPvarGetUbLocal(var));
5413 
5414  (*nchgbds)++;
5415 
5416  /* if variable type was changed we might be able to upgrade the constraint */
5417  if( vartype != SCIPvarGetType(var) )
5418  consdata->upgradetried = FALSE;
5419  }
5420  }
5421  return SCIP_OKAY;
5422 }
5423 
5424 /** tighten lower bound */
5425 static
5427  SCIP* scip, /**< SCIP data structure */
5428  SCIP_CONS* cons, /**< linear constraint */
5429  int pos, /**< variable position */
5430  PROPRULE proprule, /**< propagation rule that deduced the value */
5431  SCIP_Real newlb, /**< new lower bound */
5432  SCIP_Real oldlb, /**< old lower bound */
5433  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
5434  int* nchgbds, /**< pointer to count the total number of tightened bounds */
5435  SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5436  )
5437 {
5438  SCIP_CONSDATA* consdata;
5439  SCIP_VAR* var;
5440  SCIP_Real ub;
5441  SCIP_Bool infeasible;
5442  SCIP_Bool tightened;
5443 
5444  assert(cons != NULL);
5445  assert(!SCIPisInfinity(scip, newlb));
5446 
5447  consdata = SCIPconsGetData(cons);
5448  assert(consdata != NULL);
5449  var = consdata->vars[pos];
5450  assert(var != NULL);
5451 
5452  ub = SCIPvarGetUbLocal(var);
5453  newlb = SCIPadjustedVarLb(scip, var, newlb);
5454 
5455  if( force || SCIPisLbBetter(scip, newlb, oldlb, ub) )
5456  {
5457  SCIP_VARTYPE vartype;
5458 
5459  SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, old bds=[%.15g,%.15g], val=%.15g, activity=[%.15g,%.15g], sides=[%.15g,%.15g] -> newlb=%.15g\n",
5460  SCIPconsGetName(cons), SCIPvarGetName(var), oldlb, ub, consdata->vals[pos],
5461  QUAD_TO_DBL(consdata->minactivity), QUAD_TO_DBL(consdata->maxactivity), consdata->lhs, consdata->rhs, newlb);
5462 
5463  vartype = SCIPvarGetType(var);
5464 
5465  /* tighten lower bound */
5466  SCIP_CALL( SCIPinferVarLbCons(scip, var, newlb, cons, getInferInt(proprule, pos), force, &infeasible, &tightened) );
5467 
5468  if( infeasible )
5469  {
5470  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5471  SCIPconsGetName(cons), SCIPvarGetName(var), newlb, ub);
5472 
5473  /* analyze conflict */
5474  SCIP_CALL( analyzeConflict(scip, cons, FALSE) );
5475 
5476  *cutoff = TRUE;
5477  }
5478  else if( tightened )
5479  {
5480  assert(SCIPisFeasGE(scip, SCIPvarGetLbLocal(var), oldlb));
5481  SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, new bds=[%.15g,%.15g]\n",
5482  SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetLbLocal(var), ub);
5483 
5484  (*nchgbds)++;
5485 
5486  /* if variable type was changed we might be able to upgrade the constraint */
5487  if( vartype != SCIPvarGetType(var) )
5488  consdata->upgradetried = FALSE;
5489  }
5490  }
5491  return SCIP_OKAY;
5492 }
5493 
5494 /** tightens bounds of a single variable due to activity bounds (easy case) */
5495 static
5497  SCIP* scip, /**< SCIP data structure */
5498  SCIP_CONS* cons, /**< linear constraint */
5499  int pos, /**< position of the variable in the vars array */
5500  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
5501  int* nchgbds, /**< pointer to count the total number of tightened bounds */
5502  SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5503  )
5504 {
5505  SCIP_CONSDATA* consdata;
5506  SCIP_VAR* var;
5507  SCIP_Real val;
5508  SCIP_Real lb;
5509  SCIP_Real ub;
5510  SCIP_Real lhs;
5511  SCIP_Real rhs;
5512 
5513  assert(scip != NULL);
5514  assert(cons != NULL);
5515  assert(cutoff != NULL);
5516  assert(nchgbds != NULL);
5517 
5518  /* we cannot tighten variables' bounds, if the constraint may be not complete */
5519  if( SCIPconsIsModifiable(cons) )
5520  return SCIP_OKAY;
5521 
5522  consdata = SCIPconsGetData(cons);
5523  assert(consdata != NULL);
5524  assert(0 <= pos && pos < consdata->nvars);
5525 
5526  *cutoff = FALSE;
5527 
5528  var = consdata->vars[pos];
5529  assert(var != NULL);
5530 
5531  /* we cannot tighten bounds of multi-aggregated variables */
5533  return SCIP_OKAY;
5534 
5535  val = consdata->vals[pos];
5536  lhs = consdata->lhs;
5537  rhs = consdata->rhs;
5538  assert(!SCIPisZero(scip, val));
5539  assert(!SCIPisInfinity(scip, lhs));
5540  assert(!SCIPisInfinity(scip, -rhs));
5541 
5542  lb = SCIPvarGetLbLocal(var);
5543  ub = SCIPvarGetUbLocal(var);
5544  assert(SCIPisLE(scip, lb, ub));
5545 
5546  /* recompute activities if needed */
5547  if( !consdata->validactivities )
5548  consdataCalcActivities(scip, consdata);
5549  assert(consdata->validactivities);
5550  if( !consdata->validminact )
5551  consdataRecomputeMinactivity(scip, consdata);
5552  assert(consdata->validminact);
5553 
5554  if( val > 0.0 )
5555  {
5556  /* check, if we can tighten the variable's upper bound */
5557  if( !SCIPisInfinity(scip, rhs) )
5558  {
5559  SCIP_Real slack;
5560  SCIP_Real alpha;
5561 
5562  /* min activity should be valid at this point (if this is not true, then some decisions might be wrong!) */
5563  assert(consdata->validminact);
5564 
5565  /* if the minactivity is larger than the right hand side by feasibility epsilon, the constraint is infeasible */
5566  if( SCIPisFeasLT(scip, rhs, QUAD_TO_DBL(consdata->minactivity)) )
5567  {
5568  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, minactivity=%.15g > rhs=%.15g\n",
5569  SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->minactivity), rhs);
5570 
5571  *cutoff = TRUE;
5572  return SCIP_OKAY;
5573  }
5574 
5575  slack = rhs - QUAD_TO_DBL(consdata->minactivity);
5576 
5577  /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5578  * it to zero
5579  */
5580  if( !SCIPisPositive(scip, slack) )
5581  slack = 0.0;
5582 
5583  alpha = val * (ub - lb);
5584  assert(!SCIPisNegative(scip, alpha));
5585 
5586  if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
5587  {
5588  SCIP_Real newub;
5589 
5590  /* compute new upper bound */
5591  newub = lb + (slack / val);
5592 
5593  SCIP_CALL( tightenVarUb(scip, cons, pos, PROPRULE_1_RHS, newub, ub, cutoff, nchgbds, force) );
5594 
5595  if( *cutoff )
5596  {
5597  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5598  SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);
5599 
5600  return SCIP_OKAY;
5601  }
5602 
5603  /* collect the new upper bound which is needed for the lower bound computation */
5604  ub = SCIPvarGetUbLocal(var);
5605  }
5606  }
5607 
5608  /* check, if we can tighten the variable's lower bound */
5609  if( !SCIPisInfinity(scip, -lhs) )
5610  {
5611  SCIP_Real slack;
5612  SCIP_Real alpha;
5613 
5614  /* make sure the max activity is reliable */
5615  if( !consdata->validmaxact )
5616  {
5617  consdataRecomputeMaxactivity(scip, consdata);
5618  }
5619  assert(consdata->validmaxact);
5620 
5621  /* if the maxactivity is smaller than the left hand side by feasibility epsilon, the constraint is infeasible */
5622  if( SCIPisFeasLT(scip, QUAD_TO_DBL(consdata->maxactivity), lhs) )
5623  {
5624  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, maxactivity=%.15g < lhs=%.15g\n",
5625  SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->maxactivity), lhs);
5626 
5627  *cutoff = TRUE;
5628  return SCIP_OKAY;
5629  }
5630 
5631  slack = QUAD_TO_DBL(consdata->maxactivity) - lhs;
5632 
5633  /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5634  * it to zero
5635  */
5636  if( !SCIPisPositive(scip, slack) )
5637  slack = 0.0;
5638 
5639  alpha = val * (ub - lb);
5640  assert(!SCIPisNegative(scip, alpha));
5641 
5642  if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
5643  {
5644  SCIP_Real newlb;
5645 
5646  /* compute new lower bound */
5647  newlb = ub - (slack / val);
5648 
5649  SCIP_CALL( tightenVarLb(scip, cons, pos, PROPRULE_1_LHS, newlb, lb, cutoff, nchgbds, force) );
5650 
5651  if( *cutoff )
5652  {
5653  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5654  SCIPconsGetName(cons), SCIPvarGetName(var), newlb, ub);
5655 
5656  return SCIP_OKAY;
5657  }
5658  }
5659  }
5660  }
5661  else
5662  {
5663  /* check, if we can tighten the variable's lower bound */
5664  if( !SCIPisInfinity(scip, rhs) )
5665  {
5666  SCIP_Real slack;
5667  SCIP_Real alpha;
5668 
5669  /* min activity should be valid at this point (if this is not true, then some decisions might be wrong!) */
5670  assert(consdata->validminact);
5671 
5672  /* if the minactivity is larger than the right hand side by feasibility epsilon, the constraint is infeasible */
5673  if( SCIPisFeasLT(scip, rhs, QUAD_TO_DBL(consdata->minactivity)) )
5674  {
5675  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, minactivity=%.15g > rhs=%.15g\n",
5676  SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->minactivity), rhs);
5677 
5678  *cutoff = TRUE;
5679  return SCIP_OKAY;
5680  }
5681 
5682  slack = rhs - QUAD_TO_DBL(consdata->minactivity);
5683 
5684  /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5685  * it to zero
5686  */
5687  if( !SCIPisPositive(scip, slack) )
5688  slack = 0.0;
5689 
5690  alpha = val * (lb - ub);
5691  assert(!SCIPisNegative(scip, alpha));
5692 
5693  if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
5694  {
5695  SCIP_Real newlb;
5696 
5697  /* compute new lower bound */
5698  newlb = ub + slack / val;
5699 
5700  SCIP_CALL( tightenVarLb(scip, cons, pos, PROPRULE_1_RHS, newlb, lb, cutoff, nchgbds, force) );
5701 
5702  if( *cutoff )
5703  {
5704  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5705  SCIPconsGetName(cons), SCIPvarGetName(var), newlb, ub);
5706 
5707  return SCIP_OKAY;
5708  }
5709  /* collect the new lower bound which is needed for the upper bound computation */
5710  lb = SCIPvarGetLbLocal(var);
5711  }
5712  }
5713 
5714  /* check, if we can tighten the variable's upper bound */
5715  if( !SCIPisInfinity(scip, -lhs) )
5716  {
5717  SCIP_Real slack;
5718  SCIP_Real alpha;
5719 
5720  /* make sure the max activity is reliable */
5721  if( !consdata->validmaxact )
5722  {
5723  consdataRecomputeMaxactivity(scip, consdata);
5724  }
5725  assert(consdata->validmaxact);
5726 
5727  /* if the maxactivity is smaller than the left hand side by feasibility epsilon, the constraint is infeasible */
5728  if( SCIPisFeasLT(scip, QUAD_TO_DBL(consdata->maxactivity), lhs) )
5729  {
5730  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, maxactivity=%.15g < lhs=%.15g\n",
5731  SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->maxactivity), lhs);
5732 
5733  *cutoff = TRUE;
5734  return SCIP_OKAY;
5735  }
5736 
5737  slack = QUAD_TO_DBL(consdata->maxactivity) - lhs;
5738 
5739  /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5740  * it to zero
5741  */
5742  if( !SCIPisPositive(scip, slack) )
5743  slack = 0.0;
5744 
5745  alpha = val * (lb - ub);
5746  assert(!SCIPisNegative(scip, alpha));
5747 
5748  if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
5749  {
5750  SCIP_Real newub;
5751 
5752  /* compute new upper bound */
5753  newub = lb - (slack / val);
5754 
5755  SCIP_CALL( tightenVarUb(scip, cons, pos, PROPRULE_1_LHS, newub, ub, cutoff, nchgbds, force) );
5756 
5757  if( *cutoff )
5758  {
5759  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5760  SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);
5761 
5762  return SCIP_OKAY;
5763  }
5764  }
5765  }
5766  }
5767 
5768  return SCIP_OKAY;
5769 }
5770 
5771 /** analyzes conflicting bounds on given ranged row constraint, and adds conflict constraint to problem */
5772 static
5774  SCIP* scip, /**< SCIP data structure */
5775  SCIP_CONS* cons, /**< conflict detecting constraint */
5776  SCIP_VAR** vars, /**< variables reasoning the infeasibility */
5777  int nvars, /**< number of variables reasoning the infeasibility */
5778  SCIP_VAR* var, /**< variable which was tried to fix/tighten, or NULL */
5779  SCIP_Real bound /**< bound of variable which was tried to apply, or SCIP_INVALID */
5780  )
5781 {
5782 #ifndef NDEBUG
5783  SCIP_CONSDATA* consdata;
5784 
5785  assert(scip != NULL);
5786  assert(cons != NULL);
5787 
5788  consdata = SCIPconsGetData(cons);
5789  assert(consdata != NULL);
5790  assert(!SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs));
5791 #endif
5793  /* conflict analysis can only be applied in solving stage and if it is turned on */
5795  return SCIP_OKAY;
5796 
5797  /* initialize conflict analysis */
5799 
5800  /* add the conflicting fixed variables of this ranged row constraint to conflict candidate queue */
5801  SCIP_CALL( addConflictFixedVars(scip, cons, NULL, NULL, -1) );
5802 
5803  /* add reasoning variables to conflict candidate queue which led to the conflict */
5804  SCIP_CALL( addConflictReasonVars(scip, vars, nvars, var, bound) );
5805 
5806  /* analyze the conflict */
5807  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
5808 
5809  return SCIP_OKAY;
5810 }
5811 
5812 /** propagate ranged rows
5813  *
5814  * Check ranged rows for possible solutions, possibly detect infeasibility, fix variables due to having only one possible
5815  * solution, tighten bounds if having only two possible solutions or add constraints which propagate a subset of
5816  * variables better.
5817  *
5818  * Example:
5819  * c1: 12 x1 + 9 x2 - x3 = 0 with x1, x2 free and 1 <= x3 <= 2
5820  *
5821  * x3 needs to be a multiple of 3, so the instance is infeasible.
5822  *
5823  * Example:
5824  * c1: 12 x1 + 9 x2 - x3 = 1 with x1, x2 free and 1 <= x3 <= 2
5825  *
5826  * The only possible value for x3 is 2, so the variable will be fixed.
5827  *
5828  * @todo add holes if possible
5829  */
5830 static
5832  SCIP* scip, /**< SCIP data structure */
5833  SCIP_CONS* cons, /**< linear constraint */
5834  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
5835  int* nfixedvars, /**< pointer to count number of fixed variables */
5836  int* nchgbds, /**< pointer to count the number of bound changes */
5837  int* naddconss /**< pointer to count number of added constraints */
5838  )
5839 {
5840  SCIP_CONSHDLRDATA* conshdlrdata;
5841  SCIP_CONSHDLR* conshdlr;
5842  SCIP_CONSDATA* consdata;
5843  SCIP_VAR** infcheckvars;
5844  SCIP_Real* infcheckvals;
5845  SCIP_Real minactinfvars;
5846  SCIP_Real maxactinfvars;
5847  SCIP_Real lb;
5848  SCIP_Real ub;
5849  SCIP_Real feastol;
5850  SCIP_Real fixedact;
5851  SCIP_Real lhs;
5852  SCIP_Real rhs;
5853  SCIP_Real absminbincoef;
5854  SCIP_Longint gcd;
5855  SCIP_Longint gcdtmp;
5856  SCIP_Bool minactinfvarsinvalid;
5857  SCIP_Bool maxactinfvarsinvalid;
5858  SCIP_Bool possiblegcd;
5859  SCIP_Bool gcdisone;
5860  SCIP_Bool addartconss;
5861  int ninfcheckvars;
5862  int nunfixedvars;
5863  int nfixedconsvars;
5864  int ncontvars;
5865  int pos;
5866  int v;
5867 
5868  assert(scip != NULL);
5869  assert(cons != NULL);
5870  assert(cutoff != NULL);
5871  assert(nfixedvars != NULL);
5872  assert(nchgbds != NULL);
5873  assert(naddconss != NULL);
5874 
5875  /* modifiable constraint can be changed so we do not have all necessary information */
5876  if( SCIPconsIsModifiable(cons) )
5877  return SCIP_OKAY;
5878 
5879  consdata = SCIPconsGetData(cons);
5880  assert(consdata != NULL);
5881 
5882  /* we already did full ranged row propagation */
5883  if( consdata->rangedrowpropagated == 2 )
5884  return SCIP_OKAY;
5885 
5886  /* at least three variables are needed */
5887  if( consdata->nvars < 3 )
5888  return SCIP_OKAY;
5889 
5890  /* do nothing on normal inequalities */
5891  if( SCIPisInfinity(scip, -consdata->lhs) || SCIPisInfinity(scip, consdata->rhs) )
5892  return SCIP_OKAY;
5893 
5894  /* get constraint handler data */
5895  conshdlr = SCIPconsGetHdlr(cons);
5896  assert(conshdlr != NULL);
5897  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5898  assert(conshdlrdata != NULL);
5899 
5900  addartconss = conshdlrdata->rangedrowartcons && SCIPgetDepth(scip) < 1 && !SCIPinProbing(scip) && !SCIPinRepropagation(scip);
5901 
5902  /* we may add artificial constraints */
5903  if( addartconss )
5904  consdata->rangedrowpropagated = 2;
5905  /* we are not allowed to add artificial constraints during propagation; if nothing changed on this constraint since
5906  * the last rangedrowpropagation, we can stop; otherwise, we mark this constraint to be rangedrowpropagated without
5907  * artificial constraints
5908  */
5909  else
5910  {
5911  if( consdata->rangedrowpropagated > 0 )
5912  return SCIP_OKAY;
5913 
5914  consdata->rangedrowpropagated = 1;
5915  }
5916  fixedact = 0;
5917  nfixedconsvars = 0;
5918  /* calculate fixed activity and number of fixed variables */
5919  for( v = consdata->nvars - 1; v >= 0; --v )
5920  {
5921  /* all zero coefficients should be eliminated */
5922  assert(!SCIPisZero(scip, consdata->vals[v]));
5923 
5924  if( SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->vars[v]), SCIPvarGetUbLocal(consdata->vars[v])) )
5925  {
5926  fixedact += SCIPvarGetLbLocal(consdata->vars[v]) * consdata->vals[v];
5927  ++nfixedconsvars;
5928  }
5929  }
5930 
5931  /* do not work with huge fixed activities */
5932  if( SCIPisHugeValue(scip, REALABS(fixedact)) )
5933  return SCIP_OKAY;
5934 
5935  /* compute lhs and rhs for unfixed variables only and get number of unfixed variables */
5936  assert(!SCIPisInfinity(scip, -fixedact) && !SCIPisInfinity(scip, fixedact));
5937  lhs = consdata->lhs - fixedact;
5938  rhs = consdata->rhs - fixedact;
5939  nunfixedvars = consdata->nvars - nfixedconsvars;
5940 
5941  /* allocate temporary memory for variables and coefficients which may lead to infeasibility */
5942  SCIP_CALL( SCIPallocBufferArray(scip, &infcheckvars, nunfixedvars) );
5943  SCIP_CALL( SCIPallocBufferArray(scip, &infcheckvals, nunfixedvars) );
5944 
5945  absminbincoef = SCIP_REAL_MAX;
5946  ncontvars = 0;
5947  gcdisone = TRUE;
5948  possiblegcd = TRUE;
5949 
5950  /* we now partition all unfixed variables in two groups:
5951  *
5952  * the first one contains all integral variable with integral
5953  * coefficient so that all variables in this group will have a gcd greater than 1, this group will be implicitly
5954  * given
5955  *
5956