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