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