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