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