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