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