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* istight, /**< pointer to store whether activity bound is tight to variable bounds
2415  * i.e. is the actual minactivity (otherwise a lower bound is provided) */
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(istight != NULL);
2427  assert(issettoinfinity != NULL);
2428 
2429  /* if we have neg. infinite contributions, the minactivity is -infty */
2430  if( neginf > 0 )
2431  {
2432  *minactivity = -SCIPinfinity(scip);
2433  *issettoinfinity = TRUE;
2434  *istight = posinf == 0;
2435  }
2436  /* if we have pos. (and no neg.) infinite contributions, the minactivity is +infty */
2437  else if( posinf > 0 )
2438  {
2439  *minactivity = SCIPinfinity(scip);
2440  *issettoinfinity = TRUE;
2441  *istight = TRUE;
2442  }
2443  /* if we have neg. huge contributions or do not need a good relaxation, we just return -infty as minactivity */
2444  else if( neghuge > 0 || ( poshuge > 0 && !goodrelax ) )
2445  {
2446  *minactivity = -SCIPinfinity(scip);
2447  *issettoinfinity = TRUE;
2448  *istight = FALSE;
2449  }
2450  else
2451  {
2452  SCIP_Real QUAD(tmpactivity);
2453 
2454  /* recompute minactivity if it is not valid */
2455  if( global )
2456  {
2457  if( !consdata->validglbminact )
2458  consdataRecomputeGlbMinactivity(scip, consdata);
2459  assert(consdata->validglbminact);
2460 
2461  QUAD_ASSIGN_Q(tmpactivity, consdata->glbminactivity);
2462  }
2463  else
2464  {
2465  if( !consdata->validminact )
2466  consdataRecomputeMinactivity(scip, consdata);
2467  assert(consdata->validminact);
2468 
2469  QUAD_ASSIGN_Q(tmpactivity, consdata->minactivity);
2470  }
2471 
2472  /* calculate residual minactivity */
2473  SCIPquadprecSumQD(tmpactivity, tmpactivity, -delta);
2474 
2475  /* we have no infinite and no neg. huge contributions, but pos. huge contributions; a feasible relaxation of the
2476  * minactivity is given by adding the number of positive huge contributions times the huge value
2477  */
2478  if( poshuge > 0 )
2479  {
2480  SCIPquadprecSumQD(tmpactivity, tmpactivity, poshuge * SCIPgetHugeValue(scip));
2481  *istight = FALSE;
2482  }
2483  /* all counters are zero, so the minactivity is tight */
2484  else
2485  *istight = TRUE;
2486 
2487  /* round residual minactivity */
2488  *minactivity = QUAD_TO_DBL(tmpactivity);
2489  *issettoinfinity = FALSE;
2490  }
2491 }
2492 
2493 /** gets maximal activity for constraint and given values of counters for infinite and huge contributions
2494  * and (if needed) delta to subtract from stored finite part of activity in case of a residual activity
2495  */
2496 static
2497 void getMaxActivity(
2498  SCIP* scip, /**< SCIP data structure */
2499  SCIP_CONSDATA* consdata, /**< linear constraint */
2500  int posinf, /**< number of coefficients contributing pos. infinite value */
2501  int neginf, /**< number of coefficients contributing neg. infinite value */
2502  int poshuge, /**< number of coefficients contributing huge pos. value */
2503  int neghuge, /**< number of coefficients contributing huge neg. value */
2504  SCIP_Real delta, /**< value to subtract from stored maxactivity
2505  * (contribution of the variable set to zero when getting residual activity) */
2506  SCIP_Bool global, /**< should the global or local maximal activity be returned? */
2507  SCIP_Bool goodrelax, /**< should a good relaxation be computed or are relaxed acticities ignored, anyway? */
2508  SCIP_Real* maxactivity, /**< pointer to store the maximal activity */
2509  SCIP_Bool* istight, /**< pointer to store whether activity bound is tight to variable bounds
2510  * i.e. is the actual maxactivity (otherwise an upper bound is provided) */
2511  SCIP_Bool* issettoinfinity /**< pointer to store whether maxactivity was set to infinity or calculated */
2512  )
2513 {
2514  assert(scip != NULL);
2515  assert(consdata != NULL);
2516  assert(posinf >= 0);
2517  assert(neginf >= 0);
2518  assert(poshuge >= 0);
2519  assert(neghuge >= 0);
2520  assert(maxactivity != NULL);
2521  assert(istight != NULL);
2522  assert(issettoinfinity != NULL);
2523 
2524  /* if we have pos. infinite contributions, the maxactivity is +infty */
2525  if( posinf > 0 )
2526  {
2527  *maxactivity = SCIPinfinity(scip);
2528  *issettoinfinity = TRUE;
2529  *istight = neginf == 0;
2530  }
2531  /* if we have neg. (and no pos.) infinite contributions, the maxactivity is -infty */
2532  else if( neginf > 0 )
2533  {
2534  *maxactivity = -SCIPinfinity(scip);
2535  *issettoinfinity = TRUE;
2536  *istight = TRUE;
2537  }
2538  /* if we have pos. huge contributions or do not need a good relaxation, we just return +infty as maxactivity */
2539  else if( poshuge > 0 || ( neghuge > 0 && !goodrelax ) )
2540  {
2541  *maxactivity = SCIPinfinity(scip);
2542  *issettoinfinity = TRUE;
2543  *istight = FALSE;
2544  }
2545  else
2546  {
2547  SCIP_Real QUAD(tmpactivity);
2548 
2549  /* recompute maxactivity if it is not valid */
2550  if( global )
2551  {
2552  if( !consdata->validglbmaxact )
2553  consdataRecomputeGlbMaxactivity(scip, consdata);
2554  assert(consdata->validglbmaxact);
2555 
2556  QUAD_ASSIGN_Q(tmpactivity, consdata->glbmaxactivity);
2557  }
2558  else
2559  {
2560  if( !consdata->validmaxact )
2561  consdataRecomputeMaxactivity(scip, consdata);
2562  assert(consdata->validmaxact);
2563 
2564  QUAD_ASSIGN_Q(tmpactivity, consdata->maxactivity);
2565  }
2566 
2567  /* calculate residual maxactivity */
2568  SCIPquadprecSumQD(tmpactivity, tmpactivity, -delta);
2569 
2570  /* we have no infinite and no pos. huge contributions, but neg. huge contributions; a feasible relaxation of the
2571  * maxactivity is given by subtracting the number of negative huge contributions times the huge value
2572  */
2573  if( neghuge > 0 )
2574  {
2575  SCIPquadprecSumQD(tmpactivity, tmpactivity, -neghuge * SCIPgetHugeValue(scip));
2576  *istight = FALSE;
2577  }
2578  /* all counters are zero, so the maxactivity is tight */
2579  else
2580  *istight = TRUE;
2581 
2582  /* round residual maxactivity */
2583  *maxactivity = QUAD_TO_DBL(tmpactivity);
2584  *issettoinfinity = FALSE;
2585  }
2586 }
2587 
2588 /** gets activity bounds for constraint */
2589 static
2591  SCIP* scip, /**< SCIP data structure */
2592  SCIP_CONSDATA* consdata, /**< linear constraint */
2593  SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2594  * relaxed activities ignored, anyway? */
2595  SCIP_Real* minactivity, /**< pointer to store the minimal activity */
2596  SCIP_Real* maxactivity, /**< pointer to store the maximal activity */
2597  SCIP_Bool* ismintight, /**< pointer to store whether the minactivity bound is tight
2598  * i.e. is the actual minactivity (otherwise a lower bound is provided) */
2599  SCIP_Bool* ismaxtight, /**< pointer to store whether the maxactivity bound is tight
2600  * i.e. is the actual maxactivity (otherwise an upper bound is provided) */
2601  SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minactivity was set to infinity or calculated */
2602  SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxactivity was set to infinity or calculated */
2603 
2604  )
2605 {
2606  assert(scip != NULL);
2607  assert(consdata != NULL);
2608  assert(minactivity != NULL);
2609  assert(maxactivity != NULL);
2610  assert(isminsettoinfinity != NULL);
2611  assert(ismaxsettoinfinity != NULL);
2612 
2613  if( !consdata->validactivities )
2614  {
2615  consdataCalcActivities(scip, consdata);
2616  assert(consdata->validminact);
2617  assert(consdata->validmaxact);
2618  }
2619  assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
2620  assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
2621  assert(consdata->minactivityneginf >= 0);
2622  assert(consdata->minactivityposinf >= 0);
2623  assert(consdata->maxactivityneginf >= 0);
2624  assert(consdata->maxactivityposinf >= 0);
2625 
2626  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2627  consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2628  minactivity, ismintight, isminsettoinfinity);
2629 
2630  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2631  consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2632  maxactivity, ismaxtight, ismaxsettoinfinity);
2633 }
2634 
2635 /** calculates activity bounds for constraint after setting variable to zero */
2636 static
2638  SCIP* scip, /**< SCIP data structure */
2639  SCIP_CONSDATA* consdata, /**< linear constraint */
2640  SCIP_VAR* cancelvar, /**< variable to calculate activity residual for */
2641  SCIP_Real* resactivity, /**< pointer to store the residual activity */
2642  SCIP_Bool isminresact, /**< should minimal or maximal residual activity be calculated? */
2643  SCIP_Bool useglobalbounds /**< should global or local bounds be used? */
2644  )
2645 {
2646  SCIP_VAR* var;
2647  SCIP_Real val;
2648  SCIP_Real lb;
2649  SCIP_Real ub;
2650  int v;
2651 
2652  assert(scip != NULL);
2653  assert(consdata != NULL);
2654  assert(cancelvar != NULL);
2655  assert(resactivity != NULL);
2657  *resactivity = 0.0;
2658 
2659  for( v = 0; v < consdata->nvars; ++v )
2660  {
2661  var = consdata->vars[v];
2662  assert(var != NULL);
2663  if( var == cancelvar )
2664  continue;
2665 
2666  val = consdata->vals[v];
2667 
2668  if( useglobalbounds )
2669  {
2670  lb = SCIPvarGetLbGlobal(var);
2671  ub = SCIPvarGetUbGlobal(var);
2672  }
2673  else
2674  {
2675  lb = SCIPvarGetLbLocal(var);
2676  ub = SCIPvarGetUbLocal(var);
2677  }
2678 
2679  assert(!SCIPisZero(scip, val));
2680  assert(SCIPisLE(scip, lb, ub));
2681 
2682  if( val > 0.0 )
2683  {
2684  if( isminresact )
2685  {
2686  assert(!SCIPisInfinity(scip, -lb));
2687  assert(!SCIPisHugeValue(scip, REALABS(val*lb)));
2688  *resactivity += val*lb;
2689  }
2690  else
2691  {
2692  assert(!SCIPisInfinity(scip, ub));
2693  assert(!SCIPisHugeValue(scip, REALABS(val*ub)));
2694  *resactivity += val*ub;
2695  }
2696  }
2697  else
2698  {
2699  if( isminresact)
2700  {
2701  assert(!SCIPisInfinity(scip, ub));
2702  assert(!SCIPisHugeValue(scip, REALABS(val*ub)));
2703  *resactivity += val*ub;
2704  }
2705  else
2706  {
2707  assert(!SCIPisInfinity(scip, -lb));
2708  assert(!SCIPisHugeValue(scip, REALABS(val*lb)));
2709  *resactivity += val*lb;
2710  }
2711  }
2712  }
2713  assert(!SCIPisInfinity(scip, *resactivity) && !SCIPisInfinity(scip, -(*resactivity)));
2714 }
2715 
2716 /** gets activity bounds for constraint after setting variable to zero */
2717 static
2719  SCIP* scip, /**< SCIP data structure */
2720  SCIP_CONSDATA* consdata, /**< linear constraint */
2721  SCIP_VAR* var, /**< variable to calculate activity residual for */
2722  SCIP_Real val, /**< coefficient value of variable in linear constraint */
2723  SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2724  * relaxed acticities ignored, anyway? */
2725  SCIP_Real* minresactivity, /**< pointer to store the minimal residual activity */
2726  SCIP_Real* maxresactivity, /**< pointer to store the maximal residual activity */
2727  SCIP_Bool* ismintight, /**< pointer to store whether the residual minactivity bound is tight
2728  * i.e. is the actual residual minactivity (otherwise a lower bound is provided) */
2729  SCIP_Bool* ismaxtight, /**< pointer to store whether the residual maxactivity bound is tight
2730  * i.e. is the actual residual maxactivity (otherwise an upper bound is provided) */
2731  SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2732  SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2733  )
2734 {
2735  SCIP_Real minactbound;
2736  SCIP_Real maxactbound;
2737  SCIP_Real absval;
2738 
2739  assert(scip != NULL);
2740  assert(consdata != NULL);
2741  assert(var != NULL);
2742  assert(minresactivity != NULL);
2743  assert(maxresactivity != NULL);
2744  assert(ismintight != NULL);
2745  assert(ismaxtight != NULL);
2746  assert(isminsettoinfinity != NULL);
2747  assert(ismaxsettoinfinity != NULL);
2748 
2749  /* get activity bounds of linear constraint */
2750  if( !consdata->validactivities )
2751  {
2752  consdataCalcActivities(scip, consdata);
2753  assert(consdata->validminact);
2754  assert(consdata->validmaxact);
2755  }
2756  assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
2757  assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
2758  assert(consdata->minactivityneginf >= 0);
2759  assert(consdata->minactivityposinf >= 0);
2760  assert(consdata->maxactivityneginf >= 0);
2761  assert(consdata->maxactivityposinf >= 0);
2762  assert(consdata->minactivityneghuge >= 0);
2763  assert(consdata->minactivityposhuge >= 0);
2764  assert(consdata->maxactivityneghuge >= 0);
2765  assert(consdata->maxactivityposhuge >= 0);
2766 
2767  if( val > 0.0 )
2768  {
2769  minactbound = SCIPvarGetLbLocal(var);
2770  maxactbound = SCIPvarGetUbLocal(var);
2771  absval = val;
2772  }
2773  else
2774  {
2775  minactbound = -SCIPvarGetUbLocal(var);
2776  maxactbound = -SCIPvarGetLbLocal(var);
2777  absval = -val;
2778  }
2779 
2780  /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
2781  * and contribution of variable set to zero that has to be subtracted from finite part of activity
2782  */
2783  if( SCIPisInfinity(scip, minactbound) )
2784  {
2785  assert(consdata->minactivityposinf >= 1);
2786 
2787  getMinActivity(scip, consdata, consdata->minactivityposinf - 1, consdata->minactivityneginf,
2788  consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2789  minresactivity, ismintight, isminsettoinfinity);
2790  }
2791  else if( SCIPisInfinity(scip, -minactbound) )
2792  {
2793  assert(consdata->minactivityneginf >= 1);
2794 
2795  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf - 1,
2796  consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2797  minresactivity, ismintight, isminsettoinfinity);
2798  }
2799  else if( SCIPisHugeValue(scip, minactbound * absval) )
2800  {
2801  assert(consdata->minactivityposhuge >= 1);
2802 
2803  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2804  consdata->minactivityposhuge - 1, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2805  minresactivity, ismintight, isminsettoinfinity);
2806  }
2807  else if( SCIPisHugeValue(scip, -minactbound * absval) )
2808  {
2809  assert(consdata->minactivityneghuge >= 1);
2810 
2811  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2812  consdata->minactivityposhuge, consdata->minactivityneghuge - 1, 0.0, FALSE, goodrelax,
2813  minresactivity, ismintight, isminsettoinfinity);
2814  }
2815  else
2816  {
2817  getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2818  consdata->minactivityposhuge, consdata->minactivityneghuge, absval * minactbound, FALSE, goodrelax,
2819  minresactivity, ismintight, isminsettoinfinity);
2820  }
2821 
2822  /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
2823  * and contribution of variable set to zero that has to be subtracted from finite part of activity
2824  */
2825  if( SCIPisInfinity(scip, -maxactbound) )
2826  {
2827  assert(consdata->maxactivityneginf >= 1);
2828 
2829  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf - 1,
2830  consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2831  maxresactivity, ismaxtight, ismaxsettoinfinity);
2832  }
2833  else if( SCIPisInfinity(scip, maxactbound) )
2834  {
2835  assert(consdata->maxactivityposinf >= 1);
2836 
2837  getMaxActivity(scip, consdata, consdata->maxactivityposinf - 1, consdata->maxactivityneginf,
2838  consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2839  maxresactivity, ismaxtight, ismaxsettoinfinity);
2840  }
2841  else if( SCIPisHugeValue(scip, absval * maxactbound) )
2842  {
2843  assert(consdata->maxactivityposhuge >= 1);
2844 
2845  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2846  consdata->maxactivityposhuge - 1, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2847  maxresactivity, ismaxtight, ismaxsettoinfinity);
2848  }
2849  else if( SCIPisHugeValue(scip, -absval * maxactbound) )
2850  {
2851  assert(consdata->maxactivityneghuge >= 1);
2852 
2853  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2854  consdata->maxactivityposhuge, consdata->maxactivityneghuge - 1, 0.0, FALSE, goodrelax,
2855  maxresactivity, ismaxtight, ismaxsettoinfinity);
2856  }
2857  else
2858  {
2859  getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2860  consdata->maxactivityposhuge, consdata->maxactivityneghuge, absval * maxactbound, FALSE, goodrelax,
2861  maxresactivity, ismaxtight, ismaxsettoinfinity);
2862  }
2863 }
2864 
2865 /** gets global activity bounds for constraint */
2866 static
2868  SCIP* scip, /**< SCIP data structure */
2869  SCIP_CONSDATA* consdata, /**< linear constraint */
2870  SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2871  * relaxed acticities ignored, anyway? */
2872  SCIP_Real* glbminactivity, /**< pointer to store the minimal activity, or NULL, if not needed */
2873  SCIP_Real* glbmaxactivity, /**< pointer to store the maximal activity, or NULL, if not needed */
2874  SCIP_Bool* ismintight, /**< pointer to store whether the minactivity bound is tight
2875  * i.e. is the actual minactivity (otherwise a lower bound is provided) */
2876  SCIP_Bool* ismaxtight, /**< pointer to store whether the maxactivity bound is tight
2877  * i.e. is the actual maxactivity (otherwise an upper bound is provided) */
2878  SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2879  SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2880  )
2881 {
2882  assert(scip != NULL);
2883  assert(consdata != NULL);
2884  assert((glbminactivity != NULL && ismintight != NULL && isminsettoinfinity != NULL)
2885  || (glbmaxactivity != NULL && ismaxtight != NULL && ismaxsettoinfinity != NULL));
2887  if( !consdata->validactivities )
2888  {
2889  consdataCalcActivities(scip, consdata);
2890  assert(consdata->validglbminact);
2891  assert(consdata->validglbmaxact);
2892  }
2893  assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
2894  assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
2895  assert(consdata->glbminactivityneginf >= 0);
2896  assert(consdata->glbminactivityposinf >= 0);
2897  assert(consdata->glbmaxactivityneginf >= 0);
2898  assert(consdata->glbmaxactivityposinf >= 0);
2899  assert(consdata->glbminactivityneghuge >= 0);
2900  assert(consdata->glbminactivityposhuge >= 0);
2901  assert(consdata->glbmaxactivityneghuge >= 0);
2902  assert(consdata->glbmaxactivityposhuge >= 0);
2903 
2904  if( glbminactivity != NULL )
2905  {
2906  assert(isminsettoinfinity != NULL);
2907  assert(ismintight != NULL);
2908 
2909  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
2910  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
2911  glbminactivity, ismintight, isminsettoinfinity);
2912  }
2913 
2914  if( glbmaxactivity != NULL )
2915  {
2916  assert(ismaxsettoinfinity != NULL);
2917  assert(ismaxtight != NULL);
2918 
2919  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
2920  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
2921  glbmaxactivity, ismaxtight, ismaxsettoinfinity);
2922  }
2923 }
2924 
2925 /** gets global activity bounds for constraint after setting variable to zero */
2926 static
2928  SCIP* scip, /**< SCIP data structure */
2929  SCIP_CONSDATA* consdata, /**< linear constraint */
2930  SCIP_VAR* var, /**< variable to calculate activity residual for */
2931  SCIP_Real val, /**< coefficient value of variable in linear constraint */
2932  SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2933  * relaxed acticities ignored, anyway? */
2934  SCIP_Real* minresactivity, /**< pointer to store the minimal residual activity, or NULL, if not needed */
2935  SCIP_Real* maxresactivity, /**< pointer to store the maximal residual activity, or NULL, if not needed */
2936  SCIP_Bool* ismintight, /**< pointer to store whether the residual minactivity bound is tight
2937  * i.e. is the actual residual minactivity (otherwise a lower bound is provided) */
2938  SCIP_Bool* ismaxtight, /**< pointer to store whether the residual maxactivity bound is tight
2939  * i.e. is the actual residual maxactivity (otherwise an upper bound is provided) */
2940  SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2941  SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2942  )
2943 {
2944  SCIP_Real minactbound;
2945  SCIP_Real maxactbound;
2946  SCIP_Real absval;
2947 
2948  assert(scip != NULL);
2949  assert(consdata != NULL);
2950  assert(var != NULL);
2951  assert((minresactivity != NULL && ismintight != NULL && isminsettoinfinity != NULL )
2952  || (maxresactivity != NULL && ismaxtight != NULL && ismaxsettoinfinity != NULL));
2953 
2954  /* get activity bounds of linear constraint */
2955  if( !consdata->validactivities )
2956  consdataCalcActivities(scip, consdata);
2957 
2958  assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
2959  assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
2960  assert(consdata->glbminactivityneginf >= 0);
2961  assert(consdata->glbminactivityposinf >= 0);
2962  assert(consdata->glbmaxactivityneginf >= 0);
2963  assert(consdata->glbmaxactivityposinf >= 0);
2964 
2965  if( val > 0.0 )
2966  {
2967  minactbound = SCIPvarGetLbGlobal(var);
2968  maxactbound = SCIPvarGetUbGlobal(var);
2969  absval = val;
2970  }
2971  else
2972  {
2973  minactbound = -SCIPvarGetUbGlobal(var);
2974  maxactbound = -SCIPvarGetLbGlobal(var);
2975  absval = -val;
2976  }
2977 
2978  if( minresactivity != NULL )
2979  {
2980  assert(isminsettoinfinity != NULL);
2981  assert(ismintight != NULL);
2982 
2983  /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
2984  * and contribution of variable set to zero that has to be subtracted from finite part of activity
2985  */
2986  if( SCIPisInfinity(scip, minactbound) )
2987  {
2988  assert(consdata->glbminactivityposinf >= 1);
2989 
2990  getMinActivity(scip, consdata, consdata->glbminactivityposinf - 1, consdata->glbminactivityneginf,
2991  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
2992  minresactivity, ismintight, isminsettoinfinity);
2993  }
2994  else if( SCIPisInfinity(scip, -minactbound) )
2995  {
2996  assert(consdata->glbminactivityneginf >= 1);
2997 
2998  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf - 1,
2999  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
3000  minresactivity, ismintight, isminsettoinfinity);
3001  }
3002  else if( SCIPisHugeValue(scip, minactbound * absval) )
3003  {
3004  assert(consdata->glbminactivityposhuge >= 1);
3005 
3006  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
3007  consdata->glbminactivityposhuge - 1, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
3008  minresactivity, ismintight, isminsettoinfinity);
3009  }
3010  else if( SCIPisHugeValue(scip, -minactbound * absval) )
3011  {
3012  assert(consdata->glbminactivityneghuge >= 1);
3013 
3014  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
3015  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge - 1, 0.0, TRUE, goodrelax,
3016  minresactivity, ismintight, isminsettoinfinity);
3017  }
3018  else
3019  {
3020  getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
3021  consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, absval * minactbound, TRUE,
3022  goodrelax, minresactivity, ismintight, isminsettoinfinity);
3023  }
3024  }
3025 
3026  if( maxresactivity != NULL )
3027  {
3028  assert(ismaxsettoinfinity != NULL);
3029  assert(ismaxtight != NULL);
3030 
3031  /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
3032  * and contribution of variable set to zero that has to be subtracted from finite part of activity
3033  */
3034  if( SCIPisInfinity(scip, -maxactbound) )
3035  {
3036  assert(consdata->glbmaxactivityneginf >= 1);
3037 
3038  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf - 1,
3039  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
3040  maxresactivity, ismaxtight, ismaxsettoinfinity);
3041  }
3042  else if( SCIPisInfinity(scip, maxactbound) )
3043  {
3044  assert(consdata->glbmaxactivityposinf >= 1);
3045 
3046  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf - 1, consdata->glbmaxactivityneginf,
3047  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
3048  maxresactivity, ismaxtight, ismaxsettoinfinity);
3049  }
3050  else if( SCIPisHugeValue(scip, absval * maxactbound) )
3051  {
3052  assert(consdata->glbmaxactivityposhuge >= 1);
3053 
3054  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
3055  consdata->glbmaxactivityposhuge - 1, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
3056  maxresactivity, ismaxtight, ismaxsettoinfinity);
3057  }
3058  else if( SCIPisHugeValue(scip, -absval * maxactbound) )
3059  {
3060  assert(consdata->glbmaxactivityneghuge >= 1);
3061 
3062  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
3063  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge - 1, 0.0, TRUE, goodrelax,
3064  maxresactivity, ismaxtight, ismaxsettoinfinity);
3065  }
3066  else
3067  {
3068  getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
3069  consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, absval * maxactbound, TRUE,
3070  goodrelax, maxresactivity, ismaxtight, ismaxsettoinfinity);
3071  }
3072  }
3073 }
3074 
3075 /** calculates the activity of the linear constraint for given solution */
3076 static
3078  SCIP* scip, /**< SCIP data structure */
3079  SCIP_CONSDATA* consdata, /**< linear constraint data */
3080  SCIP_SOL* sol /**< solution to get activity for, NULL to current solution */
3081  )
3082 {
3083  SCIP_Real activity;
3084 
3085  assert(scip != NULL);
3086  assert(consdata != NULL);
3087 
3088  if( sol == NULL && !SCIPhasCurrentNodeLP(scip) )
3089  activity = consdataComputePseudoActivity(scip, consdata);
3090  else
3091  {
3092  SCIP_Real solval;
3093  int nposinf;
3094  int nneginf;
3095  SCIP_Bool negsign;
3096  int v;
3097 
3098  activity = 0.0;
3099  nposinf = 0;
3100  nneginf = 0;
3101 
3102  for( v = 0; v < consdata->nvars; ++v )
3103  {
3104  solval = SCIPgetSolVal(scip, sol, consdata->vars[v]);
3105 
3106  if( consdata->vals[v] < 0 )
3107  negsign = TRUE;
3108  else
3109  negsign = FALSE;
3110 
3111  if( (SCIPisInfinity(scip, solval) && !negsign) || (SCIPisInfinity(scip, -solval) && negsign) )
3112  ++nposinf;
3113  else if( (SCIPisInfinity(scip, solval) && negsign) || (SCIPisInfinity(scip, -solval) && !negsign) )
3114  ++nneginf;
3115  else
3116  activity += consdata->vals[v] * solval;
3117  }
3118  assert(nneginf >= 0 && nposinf >= 0);
3119 
3120  SCIPdebugMsg(scip, "activity of linear constraint: %.15g, %d positive infinity values, %d negative infinity values \n", activity, nposinf, nneginf);
3121 
3122  /* check for amount of infinity values and correct the activity */
3123  if( nposinf > 0 && nneginf > 0 )
3124  activity = (consdata->rhs + consdata->lhs) / 2;
3125  else if( nposinf > 0 )
3126  activity = SCIPinfinity(scip);
3127  else if( nneginf > 0 )
3128  activity = -SCIPinfinity(scip);
3129 
3130  SCIPdebugMsg(scip, "corrected activity of linear constraint: %.15g\n", activity);
3131  }
3132 
3133  if( activity == SCIP_INVALID ) /*lint !e777*/
3134  return activity;
3135  else if( activity < 0 )
3136  activity = MAX(activity, -SCIPinfinity(scip)); /*lint !e666*/
3137  else
3138  activity = MIN(activity, SCIPinfinity(scip)); /*lint !e666*/
3139 
3140  return activity;
3141 }
3142 
3143 /** calculates the feasibility of the linear constraint for given solution */
3144 static
3146  SCIP* scip, /**< SCIP data structure */
3147  SCIP_CONSDATA* consdata, /**< linear constraint data */
3148  SCIP_SOL* sol /**< solution to get feasibility for, NULL to current solution */
3149  )
3150 {
3151  SCIP_Real activity;
3152 
3153  assert(scip != NULL);
3154  assert(consdata != NULL);
3155 
3156  activity = consdataGetActivity(scip, consdata, sol);
3157 
3158  if( activity == SCIP_INVALID ) /*lint !e777*/
3159  return -SCIPinfinity(scip);
3160 
3161  return MIN(consdata->rhs - activity, activity - consdata->lhs);
3162 }
3163 
3164 /** updates bit signatures after adding a single coefficient */
3165 static
3167  SCIP_CONSDATA* consdata, /**< linear constraint data */
3168  int pos /**< position of coefficient to update signatures for */
3169  )
3170 {
3171  uint64_t varsignature;
3172  SCIP_Real lb;
3173  SCIP_Real ub;
3174  SCIP_Real val;
3175 
3176  assert(consdata != NULL);
3177  assert(consdata->validsignature);
3178 
3179  varsignature = SCIPhashSignature64(SCIPvarGetIndex(consdata->vars[pos]));
3180  lb = SCIPvarGetLbGlobal(consdata->vars[pos]);
3181  ub = SCIPvarGetUbGlobal(consdata->vars[pos]);
3182  val = consdata->vals[pos];
3183  if( (val > 0.0 && ub > 0.0) || (val < 0.0 && lb < 0.0) )
3184  consdata->possignature |= varsignature;
3185  if( (val > 0.0 && lb < 0.0) || (val < 0.0 && ub > 0.0) )
3186  consdata->negsignature |= varsignature;
3187 }
3188 
3189 /** calculates the bit signatures of the given constraint data */
3190 static
3192  SCIP_CONSDATA* consdata /**< linear constraint data */
3193  )
3194 {
3195  assert(consdata != NULL);
3196 
3197  if( !consdata->validsignature )
3198  {
3199  int i;
3200 
3201  consdata->validsignature = TRUE;
3202  consdata->possignature = 0;
3203  consdata->negsignature = 0;
3204  for( i = 0; i < consdata->nvars; ++i )
3205  consdataUpdateSignatures(consdata, i);
3206  }
3207 }
3208 
3209 /** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
3210 static
3211 SCIP_DECL_SORTINDCOMP(consdataCompVar)
3212 { /*lint --e{715}*/
3213  SCIP_CONSDATA* consdata = (SCIP_CONSDATA*)dataptr;
3214  SCIP_VAR* var1;
3215  SCIP_VAR* var2;
3216 
3217  assert(consdata != NULL);
3218  assert(0 <= ind1 && ind1 < consdata->nvars);
3219  assert(0 <= ind2 && ind2 < consdata->nvars);
3220 
3221  var1 = consdata->vars[ind1];
3222  var2 = consdata->vars[ind2];
3223 
3224  /* exactly one variable is binary */
3225  if( SCIPvarIsBinary(var1) != SCIPvarIsBinary(var2) )
3226  {
3227  return (SCIPvarIsBinary(var1) ? -1 : +1);
3228  }
3229  /* both variables are binary */
3230  else if( SCIPvarIsBinary(var1) )
3231  {
3232  return SCIPvarCompare(var1, var2);
3233  }
3234  else
3235  {
3236  SCIP_VARTYPE vartype1 = SCIPvarGetType(var1);
3237  SCIP_VARTYPE vartype2 = SCIPvarGetType(var2);
3238 
3239  if( vartype1 < vartype2 )
3240  return -1;
3241  else if( vartype1 > vartype2 )
3242  return +1;
3243  else
3244  return SCIPvarCompare(var1, var2);
3245  }
3246 }
3247 
3248 /** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
3249 static
3250 SCIP_DECL_SORTINDCOMP(consdataCompVarProp)
3251 { /*lint --e{715}*/
3252  SCIP_CONSDATA* consdata = (SCIP_CONSDATA*)dataptr;
3253  SCIP_VAR* var1;
3254  SCIP_VAR* var2;
3255 
3256  assert(consdata != NULL);
3257  assert(0 <= ind1 && ind1 < consdata->nvars);
3258  assert(0 <= ind2 && ind2 < consdata->nvars);
3259 
3260  var1 = consdata->vars[ind1];
3261  var2 = consdata->vars[ind2];
3262 
3263  /* exactly one variable is binary */
3264  if( SCIPvarIsBinary(var1) != SCIPvarIsBinary(var2) )
3265  {
3266  return (SCIPvarIsBinary(var1) ? -1 : +1);
3267  }
3268  /* both variables are binary */
3269  else if( SCIPvarIsBinary(var1) )
3270  {
3271  SCIP_Real abscoef1 = REALABS(consdata->vals[ind1]);
3272  SCIP_Real abscoef2 = REALABS(consdata->vals[ind2]);
3273 
3274  if( EPSGT(abscoef1, abscoef2, 1e-9) )
3275  return -1;
3276  else if( EPSGT(abscoef2, abscoef1, 1e-9) )
3277  return +1;
3278  else
3279  return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
3280  }
3281  else
3282  {
3283  SCIP_VARTYPE vartype1 = SCIPvarGetType(var1);
3284  SCIP_VARTYPE vartype2 = SCIPvarGetType(var2);
3285 
3286  if( vartype1 < vartype2 )
3287  {
3288  return -1;
3289  }
3290  else if( vartype1 > vartype2 )
3291  {
3292  return +1;
3293  }
3294  else
3295  {
3296  /* both variables are continuous */
3297  if( !SCIPvarIsIntegral(var1) )
3298  {
3299  assert(!SCIPvarIsIntegral(var2));
3300  return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
3301  }
3302  else
3303  {
3304  SCIP_Real abscont1 = REALABS(consdata->vals[ind1] * (SCIPvarGetUbGlobal(var1) - SCIPvarGetLbGlobal(var1)));
3305  SCIP_Real abscont2 = REALABS(consdata->vals[ind2] * (SCIPvarGetUbGlobal(var2) - SCIPvarGetLbGlobal(var2)));
3306 
3307  if( EPSGT(abscont1, abscont2, 1e-9) )
3308  return -1;
3309  else if( EPSGT(abscont2, abscont1, 1e-9) )
3310  return +1;
3311  else
3312  return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
3313  }
3314  }
3315  }
3316 }
3317 
3318 /** permutes the constraint's variables according to a given permutation. */
3319 static
3320 void permSortConsdata(
3321  SCIP_CONSDATA* consdata, /**< the constraint data */
3322  int* perm, /**< the target permutation */
3323  int nvars /**< the number of variables */
3324  )
3325 { /*lint --e{715}*/
3326  SCIP_VAR* varv;
3327  SCIP_EVENTDATA* eventdatav;
3328  SCIP_Real valv;
3329  int v;
3330  int i;
3331  int nexti;
3332 
3333  assert(perm != NULL);
3334  assert(consdata != NULL);
3335 
3336  /* permute the variables in the linear constraint according to the target permutation */
3337  eventdatav = NULL;
3338  for( v = 0; v < nvars; ++v )
3339  {
3340  if( perm[v] != v )
3341  {
3342  varv = consdata->vars[v];
3343  valv = consdata->vals[v];
3344  if( consdata->eventdata != NULL )
3345  eventdatav = consdata->eventdata[v];
3346  i = v;
3347  do
3348  {
3349  assert(0 <= perm[i] && perm[i] < nvars);
3350  assert(perm[i] != i);
3351  consdata->vars[i] = consdata->vars[perm[i]];
3352  consdata->vals[i] = consdata->vals[perm[i]];
3353  if( consdata->eventdata != NULL )
3354  {
3355  consdata->eventdata[i] = consdata->eventdata[perm[i]];
3356  consdata->eventdata[i]->varpos = i;
3357  }
3358  nexti = perm[i];
3359  perm[i] = i;
3360  i = nexti;
3361  }
3362  while( perm[i] != v );
3363  consdata->vars[i] = varv;
3364  consdata->vals[i] = valv;
3365  if( consdata->eventdata != NULL )
3366  {
3367  consdata->eventdata[i] = eventdatav;
3368  consdata->eventdata[i]->varpos = i;
3369  }
3370  perm[i] = i;
3371  }
3372  }
3373 #ifdef SCIP_DEBUG
3374  /* check sorting */
3375  for( v = 0; v < nvars; ++v )
3376  {
3377  assert(perm[v] == v);
3378  assert(consdata->eventdata == NULL || consdata->eventdata[v]->varpos == v);
3379  }
3380 #endif
3381 }
3382 
3383 /** sorts linear constraint's variables depending on the stage of the solving process:
3384  * - during PRESOLVING
3385  * sorts variables by binaries, integers, implicit integers, and continuous variables,
3386  * and the variables of the same type by non-decreasing variable index
3387  *
3388  * - during SOLVING
3389  * sorts variables of the remaining problem by binaries, integers, implicit integers, and continuous variables,
3390  * and binary and integer variables by their global max activity delta (within each group),
3391  * ties within a group are broken by problem index of the variable.
3392  *
3393  * This fastens the propagation time of the constraint handler.
3394  */
3395 static
3397  SCIP* scip, /**< SCIP data structure */
3398  SCIP_CONSDATA* consdata /**< linear constraint data */
3399  )
3400 {
3401  assert(scip != NULL);
3402  assert(consdata != NULL);
3403 
3404  /* check if there are variables for sorting */
3405  if( consdata->nvars <= 1 )
3406  {
3407  consdata->indexsorted = TRUE;
3408  consdata->coefsorted = TRUE;
3409  consdata->nbinvars = (consdata->nvars == 1 ? (int)SCIPvarIsBinary(consdata->vars[0]) : 0);
3410  }
3411  else if( (!consdata->indexsorted && SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE)
3412  || (!consdata->coefsorted && SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE) )
3413  {
3414  int* perm;
3415  int v;
3416 
3417  /* get temporary memory to store the sorted permutation */
3418  SCIP_CALL( SCIPallocBufferArray(scip, &perm, consdata->nvars) );
3419 
3420  /* call sorting method */
3421  if( SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE )
3422  SCIPsort(perm, consdataCompVar, (void*)consdata, consdata->nvars);
3423  else
3424  SCIPsort(perm, consdataCompVarProp, (void*)consdata, consdata->nvars);
3425 
3426  permSortConsdata(consdata, perm, consdata->nvars);
3427 
3428  /* free temporary memory */
3429  SCIPfreeBufferArray(scip, &perm);
3430 
3431  if( SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE )
3432  {
3433  consdata->indexsorted = FALSE;
3434  consdata->coefsorted = TRUE;
3435 
3436  /* count binary variables in the sorted vars array */
3437  consdata->nbinvars = 0;
3438  for( v = 0; v < consdata->nvars; ++v )
3439  {
3440  if( SCIPvarIsBinary(consdata->vars[v]) )
3441  ++consdata->nbinvars;
3442  else
3443  break;
3444  }
3445  }
3446  else
3447  {
3448  consdata->indexsorted = TRUE;
3449  consdata->coefsorted = FALSE;
3450  }
3451  }
3452 
3453  return SCIP_OKAY;
3454 }
3455 
3456 
3457 /*
3458  * local linear constraint handler methods
3459  */
3460 
3461 /** sets left hand side of linear constraint */
3462 static
3464  SCIP* scip, /**< SCIP data structure */
3465  SCIP_CONS* cons, /**< linear constraint */
3466  SCIP_Real lhs /**< new left hand side */
3467  )
3468 {
3469  SCIP_CONSDATA* consdata;
3470  SCIP_Bool locked;
3471  int i;
3472 
3473  assert(scip != NULL);
3474  assert(cons != NULL);
3475 
3476  /* adjust value to be not beyond infinity */
3477  if( SCIPisInfinity(scip, -lhs) )
3478  lhs = -SCIPinfinity(scip);
3479  else if( SCIPisInfinity(scip, lhs) )
3480  lhs = SCIPinfinity(scip);
3481 
3482  consdata = SCIPconsGetData(cons);
3483  assert(consdata != NULL);
3484  assert(consdata->nvars == 0 || (consdata->vars != NULL && consdata->vals != NULL));
3485 
3486  /* check whether the side is not changed */
3487  if( SCIPisEQ(scip, consdata->lhs, lhs) )
3488  return SCIP_OKAY;
3489 
3490  assert(!SCIPisInfinity(scip, ABS(consdata->lhs)) || !SCIPisInfinity(scip, ABS(lhs)));
3491 
3492  /* ensure that rhs >= lhs is satisfied without numerical tolerance */
3493  if( SCIPisEQ(scip, lhs, consdata->rhs) )
3494  {
3495  consdata->rhs = lhs;
3496  assert(consdata->row == NULL);
3497  }
3498 
3499  locked = FALSE;
3500  for( i = 0; i < NLOCKTYPES && !locked; i++ )
3501  locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
3502 
3503  /* if necessary, update the rounding locks of variables */
3504  if( locked )
3505  {
3506  if( SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, -lhs) )
3507  {
3508  SCIP_VAR** vars;
3509  SCIP_Real* vals;
3510  int v;
3511 
3512  /* the left hand side switched from -infinity to a non-infinite value -> install rounding locks */
3513  vars = consdata->vars;
3514  vals = consdata->vals;
3515 
3516  for( v = 0; v < consdata->nvars; ++v )
3517  {
3518  assert(vars[v] != NULL);
3519  assert(!SCIPisZero(scip, vals[v]));
3520 
3521  if( SCIPisPositive(scip, vals[v]) )
3522  {
3523  SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3524  }
3525  else
3526  {
3527  SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3528  }
3529  }
3530  }
3531  else if( !SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -lhs) )
3532  {
3533  SCIP_VAR** vars;
3534  SCIP_Real* vals;
3535  int v;
3536 
3537  /* the left hand side switched from a non-infinite value to -infinity -> remove rounding locks */
3538  vars = consdata->vars;
3539  vals = consdata->vals;
3540 
3541  for( v = 0; v < consdata->nvars; ++v )
3542  {
3543  assert(vars[v] != NULL);
3544  assert(!SCIPisZero(scip, vals[v]));
3545 
3546  if( SCIPisPositive(scip, vals[v]) )
3547  {
3548  SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3549  }
3550  else
3551  {
3552  SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3553  }
3554  }
3555  }
3556  }
3557 
3558  /* 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 */
3559  if( !SCIPisInfinity(scip, ABS(lhs)) && SCIPisGT(scip, lhs, consdata->lhs) )
3560  {
3561  consdata->boundstightened = 0;
3562  consdata->presolved = FALSE;
3563  consdata->cliquesadded = FALSE;
3564  consdata->implsadded = FALSE;
3565 
3566  /* mark the constraint for propagation */
3567  if( SCIPconsIsTransformed(cons) )
3568  {
3569  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
3570  }
3571  }
3572 
3573  /* set new left hand side and update constraint data */
3574  consdata->lhs = lhs;
3575  consdata->changed = TRUE;
3576  consdata->normalized = FALSE;
3577  consdata->upgradetried = FALSE;
3578  consdata->rangedrowpropagated = 0;
3579 
3580  /* update the lhs of the LP row */
3581  if( consdata->row != NULL )
3582  {
3583  SCIP_CALL( SCIPchgRowLhs(scip, consdata->row, lhs) );
3584  }
3585 
3586  return SCIP_OKAY;
3587 }
3588 
3589 /** sets right hand side of linear constraint */
3590 static
3592  SCIP* scip, /**< SCIP data structure */
3593  SCIP_CONS* cons, /**< linear constraint */
3594  SCIP_Real rhs /**< new right hand side */
3595  )
3596 {
3597  SCIP_CONSDATA* consdata;
3598  SCIP_Bool locked;
3599  int i;
3600 
3601  assert(scip != NULL);
3602  assert(cons != NULL);
3603 
3604  /* adjust value to be not beyond infinity */
3605  if( SCIPisInfinity(scip, rhs) )
3606  rhs = SCIPinfinity(scip);
3607  else if( SCIPisInfinity(scip, -rhs) )
3608  rhs = -SCIPinfinity(scip);
3609 
3610  consdata = SCIPconsGetData(cons);
3611  assert(consdata != NULL);
3612  assert(consdata->nvars == 0 || (consdata->vars != NULL && consdata->vals != NULL));
3613 
3614  /* check whether the side is not changed */
3615  if( SCIPisEQ(scip, consdata->rhs, rhs) )
3616  return SCIP_OKAY;
3617 
3618  assert(!SCIPisInfinity(scip, ABS(consdata->rhs)) || !SCIPisInfinity(scip, ABS(rhs)));
3619 
3620  /* ensure that rhs >= lhs is satisfied without numerical tolerance */
3621  if( SCIPisEQ(scip, rhs, consdata->lhs) )
3622  {
3623  consdata->lhs = rhs;
3624  assert(consdata->row == NULL);
3625  }
3626 
3627  locked = FALSE;
3628  for( i = 0; i < NLOCKTYPES && !locked; i++ )
3629  locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
3630 
3631  /* if necessary, update the rounding locks of variables */
3632  if( locked )
3633  {
3634  assert(SCIPconsIsTransformed(cons));
3635 
3636  if( SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, rhs) )
3637  {
3638  SCIP_VAR** vars;
3639  SCIP_Real* vals;
3640  int v;
3641 
3642  /* the right hand side switched from infinity to a non-infinite value -> install rounding locks */
3643  vars = consdata->vars;
3644  vals = consdata->vals;
3645 
3646  for( v = 0; v < consdata->nvars; ++v )
3647  {
3648  assert(vars[v] != NULL);
3649  assert(!SCIPisZero(scip, vals[v]));
3650 
3651  if( SCIPisPositive(scip, vals[v]) )
3652  {
3653  SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3654  }
3655  else
3656  {
3657  SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3658  }
3659  }
3660  }
3661  else if( !SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, rhs) )
3662  {
3663  SCIP_VAR** vars;
3664  SCIP_Real* vals;
3665  int v;
3666 
3667  /* the right hand side switched from a non-infinite value to infinity -> remove rounding locks */
3668  vars = consdata->vars;
3669  vals = consdata->vals;
3670 
3671  for( v = 0; v < consdata->nvars; ++v )
3672  {
3673  assert(vars[v] != NULL);
3674  assert(!SCIPisZero(scip, vals[v]));
3675 
3676  if( SCIPisPositive(scip, vals[v]) )
3677  {
3678  SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3679  }
3680  else
3681  {
3682  SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3683  }
3684  }
3685  }
3686  }
3687 
3688  /* 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 */
3689  if( !SCIPisInfinity(scip, ABS(rhs)) && SCIPisLT(scip, rhs, consdata->rhs) )
3690  {
3691  consdata->boundstightened = 0;
3692  consdata->presolved = FALSE;
3693  consdata->cliquesadded = FALSE;
3694  consdata->implsadded = FALSE;
3695 
3696  /* mark the constraint for propagation */
3697  if( SCIPconsIsTransformed(cons) )
3698  {
3699  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
3700  }
3701  }
3702 
3703  /* set new right hand side and update constraint data */
3704  consdata->rhs = rhs;
3705  consdata->changed = TRUE;
3706  consdata->normalized = FALSE;
3707  consdata->upgradetried = FALSE;
3708  consdata->rangedrowpropagated = 0;
3709 
3710  /* update the rhs of the LP row */
3711  if( consdata->row != NULL )
3712  {
3713  SCIP_CALL( SCIPchgRowRhs(scip, consdata->row, rhs) );
3714  }
3715 
3716  return SCIP_OKAY;
3717 }
3718 
3719 /** adds coefficient in linear constraint */
3720 static
3722  SCIP* scip, /**< SCIP data structure */
3723  SCIP_CONS* cons, /**< linear constraint */
3724  SCIP_VAR* var, /**< variable of constraint entry */
3725  SCIP_Real val /**< coefficient of constraint entry */
3726  )
3727 {
3728  SCIP_CONSDATA* consdata;
3729  SCIP_Bool transformed;
3730 
3731  assert(scip != NULL);
3732  assert(cons != NULL);
3733  assert(var != NULL);
3734 
3735  /* relaxation-only variables must not be used in checked or enforced constraints */
3736  assert(!SCIPvarIsRelaxationOnly(var) || (!SCIPconsIsChecked(cons) && !SCIPconsIsEnforced(cons)));
3737 
3738  /* ignore coefficient if it is nearly zero */
3739  if( SCIPisZero(scip, val) )
3740  return SCIP_OKAY;
3741 
3742  consdata = SCIPconsGetData(cons);
3743  assert(consdata != NULL);
3744 
3745  /* are we in the transformed problem? */
3746  transformed = SCIPconsIsTransformed(cons);
3747 
3748  /* always use transformed variables in transformed constraints */
3749  if( transformed )
3750  {
3751  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
3752  }
3753  assert(var != NULL);
3754  assert(transformed == SCIPvarIsTransformed(var));
3755 
3756  SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
3757  consdata->vars[consdata->nvars] = var;
3758  consdata->vals[consdata->nvars] = val;
3759  consdata->nvars++;
3760 
3761  /* capture variable */
3762  SCIP_CALL( SCIPcaptureVar(scip, var) );
3763 
3764  /* if we are in transformed problem, the variable needs an additional event data */
3765  if( transformed )
3766  {
3767  if( consdata->eventdata != NULL )
3768  {
3769  SCIP_CONSHDLR* conshdlr;
3770  SCIP_CONSHDLRDATA* conshdlrdata;
3771 
3772  /* check for event handler */
3773  conshdlr = SCIPconsGetHdlr(cons);
3774  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3775  assert(conshdlrdata != NULL);
3776  assert(conshdlrdata->eventhdlr != NULL);
3777 
3778  /* initialize eventdata array */
3779  consdata->eventdata[consdata->nvars-1] = NULL;
3780 
3781  /* catch bound change events of variable */
3782  SCIP_CALL( consCatchEvent(scip, cons, conshdlrdata->eventhdlr, consdata->nvars-1) );
3783  }
3784 
3785  /* update minimum and maximum activities */
3786  consdataUpdateAddCoef(scip, consdata, var, val, FALSE);
3787 
3788  /* update maximum activity delta */
3789  if( !SCIPisInfinity(scip, consdata->maxactdelta ) )
3790  {
3791  SCIP_Real lb;
3792  SCIP_Real ub;
3793 
3794  lb = SCIPvarGetLbLocal(var);
3795  ub = SCIPvarGetUbLocal(var);
3796 
3797  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
3798  {
3799  consdata->maxactdelta = SCIPinfinity(scip);
3800  consdata->maxactdeltavar = var;
3801  }
3802  else
3803  {
3804  SCIP_Real domain = ub - lb;
3805  SCIP_Real delta = REALABS(val) * domain;
3806 
3807  if( delta > consdata->maxactdelta )
3808  {
3809  consdata->maxactdelta = delta;
3810  consdata->maxactdeltavar = var;
3811  }
3812  }
3813  }
3814  }
3815 
3816  /* install rounding locks for new variable */
3817  SCIP_CALL( lockRounding(scip, cons, var, val) );
3818 
3819  /* mark the constraint for propagation */
3820  if( transformed )
3821  {
3822  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
3823  }
3824 
3825  consdata->boundstightened = 0;
3826  consdata->presolved = FALSE;
3827  consdata->removedfixings = consdata->removedfixings && SCIPvarIsActive(var);
3828 
3829  if( consdata->validsignature )
3830  consdataUpdateSignatures(consdata, consdata->nvars-1);
3831 
3832  consdata->changed = TRUE;
3833  consdata->normalized = FALSE;
3834  consdata->upgradetried = FALSE;
3835  consdata->cliquesadded = FALSE;
3836  consdata->implsadded = FALSE;
3837  consdata->rangedrowpropagated = 0;
3838 
3839  if( consdata->nvars == 1 )
3840  {
3841  consdata->indexsorted = TRUE;
3842  consdata->coefsorted = TRUE;
3843  consdata->merged = TRUE;
3844  }
3845  else
3846  {
3847  consdata->merged = FALSE;
3848 
3849  if( SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE )
3850  {
3851  consdata->indexsorted = consdata->indexsorted && (consdataCompVar((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
3852  consdata->coefsorted = FALSE;
3853  }
3854  else
3855  {
3856  consdata->indexsorted = FALSE;
3857  consdata->coefsorted = consdata->coefsorted && (consdataCompVarProp((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
3858  }
3859  }
3860 
3861  /* update hascontvar and hasnonbinvar flags */
3862  if( consdata->hasnonbinvalid && !consdata->hascontvar )
3863  {
3864  SCIP_VARTYPE vartype = SCIPvarGetType(var);
3865 
3866  if( vartype != SCIP_VARTYPE_BINARY )
3867  {
3868  consdata->hasnonbinvar = TRUE;
3869 
3870  if( vartype == SCIP_VARTYPE_CONTINUOUS )
3871  consdata->hascontvar = TRUE;
3872  }
3873  }
3874 
3875  /* add the new coefficient to the LP row */
3876  if( consdata->row != NULL )
3877  {
3878  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, val) );
3879  }
3880 
3881  return SCIP_OKAY;
3882 }
3883 
3884 /** deletes coefficient at given position from linear constraint data */
3885 static
3887  SCIP* scip, /**< SCIP data structure */
3888  SCIP_CONS* cons, /**< linear constraint */
3889  int pos /**< position of coefficient to delete */
3890  )
3891 {
3892  SCIP_CONSDATA* consdata;
3893  SCIP_VAR* var;
3894  SCIP_Real val;
3895 
3896  assert(scip != NULL);
3897  assert(cons != NULL);
3898 
3899  consdata = SCIPconsGetData(cons);
3900  assert(consdata != NULL);
3901  assert(0 <= pos && pos < consdata->nvars);
3902 
3903  var = consdata->vars[pos];
3904  val = consdata->vals[pos];
3905  assert(var != NULL);
3906 
3907  /* remove rounding locks for deleted variable */
3908  SCIP_CALL( unlockRounding(scip, cons, var, val) );
3909 
3910  /* if we are in transformed problem, delete the event data of the variable */
3911  if( SCIPconsIsTransformed(cons) )
3912  {
3913  SCIP_CONSHDLR* conshdlr;
3914  SCIP_CONSHDLRDATA* conshdlrdata;
3915 
3916  /* check for event handler */
3917  conshdlr = SCIPconsGetHdlr(cons);
3918  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3919  assert(conshdlrdata != NULL);
3920  assert(conshdlrdata->eventhdlr != NULL);
3921 
3922  /* drop bound change events of variable */
3923  if( consdata->eventdata != NULL )
3924  {
3925  SCIP_CALL( consDropEvent(scip, cons, conshdlrdata->eventhdlr, pos) );
3926  assert(consdata->eventdata[pos] == NULL);
3927  }
3928  }
3929 
3930  /* move the last variable to the free slot */
3931  if( pos != consdata->nvars - 1 )
3932  {
3933  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
3934  consdata->vals[pos] = consdata->vals[consdata->nvars-1];
3935 
3936  if( consdata->eventdata != NULL )
3937  {
3938  consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
3939  assert(consdata->eventdata[pos] != NULL);
3940  consdata->eventdata[pos]->varpos = pos;
3941  }
3942 
3943  consdata->indexsorted = consdata->indexsorted && (pos + 2 >= consdata->nvars);
3944  consdata->coefsorted = consdata->coefsorted && (pos + 2 >= consdata->nvars);
3945  }
3946  consdata->nvars--;
3947 
3948  /* if at most one variable is left, the activities should be recalculated (to correspond exactly to the bounds
3949  * of the remaining variable, or give exactly 0.0)
3950  */
3951  if( consdata->nvars <= 1 )
3952  consdataInvalidateActivities(consdata);
3953  else
3954  {
3955  if( SCIPconsIsTransformed(cons) )
3956  {
3957  /* if we are in transformed problem, update minimum and maximum activities */
3958  consdataUpdateDelCoef(scip, consdata, var, val, TRUE);
3959 
3960  /* if the variable defining the maximal activity delta was removed from the constraint, the maximal activity
3961  * delta needs to be recalculated on the next real propagation
3962  */
3963  if( consdata->maxactdeltavar == var )
3964  {
3965  consdata->maxactdelta = SCIP_INVALID;
3966  consdata->maxactdeltavar = NULL;
3967  }
3968  }
3969  }
3970 
3971  /* mark the constraint for propagation */
3972  if( SCIPconsIsTransformed(cons) )
3973  {
3974  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
3975  }
3976 
3977  consdata->boundstightened = 0;
3978  consdata->presolved = FALSE;
3979  consdata->validsignature = FALSE;
3980  consdata->changed = TRUE;
3981  consdata->normalized = FALSE;
3982  consdata->upgradetried = FALSE;
3983  consdata->cliquesadded = FALSE;
3984  consdata->implsadded = FALSE;
3985  consdata->rangedrowpropagated = 0;
3986 
3987  /* check if hasnonbinvar flag might be incorrect now */
3988  if( consdata->hasnonbinvar && SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
3989  {
3990  consdata->hasnonbinvalid = FALSE;
3991  }
3992 
3993  /* delete coefficient from the LP row */
3994  if( consdata->row != NULL )
3995  {
3996  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, -val) );
3997  }
3998 
3999  /* release variable */
4000  SCIP_CALL( SCIPreleaseVar(scip, &var) );
4001 
4002  return SCIP_OKAY;
4003 }
4004 
4005 /** changes coefficient value at given position of linear constraint data */
4006 static
4008  SCIP* scip, /**< SCIP data structure */
4009  SCIP_CONS* cons, /**< linear constraint */
4010  int pos, /**< position of coefficient to delete */
4011  SCIP_Real newval /**< new value of coefficient */
4012  )
4013 {
4014  SCIP_CONSDATA* consdata;
4015  SCIP_VAR* var;
4016  SCIP_Real val;
4017  SCIP_Bool locked;
4018  int i;
4019 
4020  assert(scip != NULL);
4021  assert(cons != NULL);
4022  assert(!SCIPisZero(scip, newval));
4023 
4024  consdata = SCIPconsGetData(cons);
4025  assert(consdata != NULL);
4026  assert(0 <= pos && pos < consdata->nvars);
4027  assert(!SCIPisZero(scip, newval));
4028 
4029  var = consdata->vars[pos];
4030  val = consdata->vals[pos];
4031  assert(var != NULL);
4032  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var));
4033 
4034  locked = FALSE;
4035  for( i = 0; i < NLOCKTYPES && !locked; i++ )
4036  locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
4037 
4038  /* if necessary, update the rounding locks of the variable */
4039  if( locked && newval * val < 0.0 )
4040  {
4041  assert(SCIPconsIsTransformed(cons));
4042 
4043  /* remove rounding locks for variable with old coefficient */
4044  SCIP_CALL( unlockRounding(scip, cons, var, val) );
4045 
4046  /* install rounding locks for variable with new coefficient */
4047  SCIP_CALL( lockRounding(scip, cons, var, newval) );
4048  }
4049 
4050  /* change the value */
4051  consdata->vals[pos] = newval;
4052 
4053  if( consdata->coefsorted )
4054  {
4055  if( pos > 0 )
4056  consdata->coefsorted = (consdataCompVarProp((void*)consdata, pos - 1, pos) <= 0);
4057  if( consdata->coefsorted && pos < consdata->nvars - 1 )
4058  consdata->coefsorted = (consdataCompVarProp((void*)consdata, pos, pos + 1) <= 0);
4059  }
4060 
4061  /* update minimum and maximum activities */
4062  if( SCIPconsIsTransformed(cons) )
4063  consdataUpdateChgCoef(scip, consdata, var, val, newval, TRUE);
4064 
4065  /* mark the constraint for propagation */
4066  if( SCIPconsIsTransformed(cons) )
4067  {
4068  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
4069  }
4070 
4071  consdata->boundstightened = 0;
4072  consdata->presolved = FALSE;
4073  consdata->validsignature = consdata->validsignature && (newval * val > 0.0);
4074  consdata->changed = TRUE;
4075  consdata->normalized = FALSE;
4076  consdata->upgradetried = FALSE;
4077  consdata->cliquesadded = FALSE;
4078  consdata->implsadded = FALSE;
4079  consdata->rangedrowpropagated = 0;
4080 
4081  return SCIP_OKAY;
4082 }
4083 
4084 /** scales a linear constraint with a constant scalar */
4085 static
4087  SCIP* scip, /**< SCIP data structure */
4088  SCIP_CONS* cons, /**< linear constraint to scale */
4089  SCIP_Real scalar /**< value to scale constraint with */
4090  )
4091 {
4092  SCIP_CONSDATA* consdata;
4093  SCIP_Real newval;
4094  SCIP_Real absscalar;
4095  int i;
4096 
4097  assert(scip != NULL);
4098  assert(cons != NULL);
4099 
4100  consdata = SCIPconsGetData(cons);
4101  assert(consdata != NULL);
4102  assert(consdata->row == NULL);
4103  assert(scalar != 1.0);
4104 
4105  if( (!SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -consdata->lhs * scalar))
4106  || (!SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, consdata->rhs * scalar)) )
4107  {
4108  SCIPwarningMessage(scip, "skipped scaling for linear constraint <%s> to avoid numerical troubles (scalar: %.15g)\n",
4109  SCIPconsGetName(cons), scalar);
4110 
4111  return SCIP_OKAY;
4112  }
4113 
4114  /* scale the coefficients */
4115  for( i = consdata->nvars - 1; i >= 0; --i )
4116  {
4117  newval = scalar * consdata->vals[i];
4118 
4119  /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
4120  * flooring down our new value
4121  */
4122  if( SCIPisScalingIntegral(scip, consdata->vals[i], scalar) )
4123  newval = SCIPfeasFloor(scip, newval + 0.5);
4124 
4125  if( SCIPisZero(scip, newval) )
4126  {
4127  SCIPwarningMessage(scip, "coefficient %.15g of variable <%s> in linear constraint <%s> scaled to zero (scalar: %.15g)\n",
4128  consdata->vals[i], SCIPvarGetName(consdata->vars[i]), SCIPconsGetName(cons), scalar);
4129  SCIP_CALL( delCoefPos(scip, cons, i) );
4130  }
4131  else
4132  consdata->vals[i] = newval;
4133  }
4134 
4135  /* scale the sides */
4136  if( scalar < 0.0 )
4137  {
4138  SCIP_Real lhs;
4139 
4140  lhs = consdata->lhs;
4141  consdata->lhs = -consdata->rhs;
4142  consdata->rhs = -lhs;
4143  }
4144  absscalar = REALABS(scalar);
4145  if( !SCIPisInfinity(scip, -consdata->lhs) )
4146  {
4147  newval = absscalar * consdata->lhs;
4148 
4149  /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
4150  * flooring down our new value
4151  */
4152  if( SCIPisScalingIntegral(scip, consdata->lhs, absscalar) )
4153  consdata->lhs = SCIPfeasFloor(scip, newval + 0.5);
4154  else
4155  consdata->lhs = newval;
4156  }
4157  if( !SCIPisInfinity(scip, consdata->rhs) )
4158  {
4159  newval = absscalar * consdata->rhs;
4160 
4161  /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasCeil, we subtract 0.5 before ceiling up
4162  * our new value
4163  */
4164  if( SCIPisScalingIntegral(scip, consdata->rhs, absscalar) )
4165  consdata->rhs = SCIPfeasCeil(scip, newval - 0.5);
4166  else
4167  consdata->rhs = newval;
4168  }
4169 
4170  consdataInvalidateActivities(consdata);
4171  consdata->cliquesadded = FALSE;
4172  consdata->implsadded = FALSE;
4173 
4174  return SCIP_OKAY;
4175 }
4176 
4177 /** perform deletion of variables in all constraints of the constraint handler */
4178 static
4180  SCIP* scip, /**< SCIP data structure */
4181  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4182  SCIP_CONS** conss, /**< array of constraints */
4183  int nconss /**< number of constraints */
4184  )
4185 {
4186  SCIP_CONSDATA* consdata;
4187  int i;
4188  int v;
4189 
4190  assert(scip != NULL);
4191  assert(conshdlr != NULL);
4192  assert(conss != NULL);
4193  assert(nconss >= 0);
4194  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4195 
4196  /* iterate over all constraints */
4197  for( i = 0; i < nconss; i++ )
4198  {
4199  consdata = SCIPconsGetData(conss[i]);
4200 
4201  /* constraint is marked, that some of its variables were deleted */
4202  if( consdata->varsdeleted )
4203  {
4204  /* iterate over all variables of the constraint and delete them from the constraint */
4205  for( v = consdata->nvars - 1; v >= 0; --v )
4206  {
4207  if( SCIPvarIsDeleted(consdata->vars[v]) )
4208  {
4209  SCIP_CALL( delCoefPos(scip, conss[i], v) );
4210  }
4211  }
4212  consdata->varsdeleted = FALSE;
4213  }
4214  }
4215 
4216  return SCIP_OKAY;
4217 }
4218 
4219 
4220 /** normalizes a linear constraint with the following rules:
4221  * - if all coefficients have them same absolute value, change them to (-)1.0
4222  * - multiplication with +1 or -1:
4223  * Apply the following rules in the given order, until the sign of the factor is determined. Later rules only apply,
4224  * if the current rule doesn't determine the sign):
4225  * 1. the right hand side must not be negative
4226  * 2. the right hand side must not be infinite
4227  * 3. the absolute value of the right hand side must be greater than that of the left hand side
4228  * 4. the number of positive coefficients must not be smaller than the number of negative coefficients
4229  * 5. multiply with +1
4230  * - rationals to integrals
4231  * Try to identify a rational representation of the fractional coefficients, and multiply all coefficients
4232  * by the smallest common multiple of all denominators to get integral coefficients.
4233  * Forbid large denominators due to numerical stability.
4234  * - division by greatest common divisor
4235  * If all coefficients are integral, divide them by the greatest common divisor.
4236  */
4237 static
4239  SCIP* scip, /**< SCIP data structure */
4240  SCIP_CONS* cons, /**< linear constraint to normalize */
4241  SCIP_Bool* infeasible /**< pointer to store whether infeasibility was detected */
4242  )
4243 {
4244  SCIP_CONSDATA* consdata;
4245  SCIP_Real* vals;
4246  SCIP_Longint scm;
4247  SCIP_Longint nominator;
4248  SCIP_Longint denominator;
4249  SCIP_Longint gcd;
4250  SCIP_Longint maxmult;
4251  SCIP_Real epsilon;
4252  SCIP_Real feastol;
4253  SCIP_Real maxabsval;
4254  SCIP_Real minabsval;
4255  SCIP_Bool success;
4256  SCIP_Bool onlyintegral;
4257  int nvars;
4258  int mult;
4259  int nposcoeffs;
4260  int nnegcoeffs;
4261  int i;
4262 
4263  assert(scip != NULL);
4264  assert(cons != NULL);
4265  assert(infeasible != NULL);
4266 
4267  *infeasible = FALSE;
4268 
4269  /* we must not change a modifiable constraint in any way */
4270  if( SCIPconsIsModifiable(cons) )
4271  return SCIP_OKAY;
4272 
4273  /* get constraint data */
4274  consdata = SCIPconsGetData(cons);
4275  assert(consdata != NULL);
4276 
4277  /* check, if the constraint is already normalized */
4278  if( consdata->normalized )
4279  return SCIP_OKAY;
4280 
4281  /* get coefficient arrays */
4282  vals = consdata->vals;
4283  nvars = consdata->nvars;
4284  assert(nvars == 0 || vals != NULL);
4285 
4286  if( nvars == 0 )
4287  {
4288  consdata->normalized = TRUE;
4289  return SCIP_OKAY;
4290  }
4291 
4292  assert(vals != NULL);
4293 
4294  /* get maximum and minimum absolute coefficient */
4295  maxabsval = consdataGetMaxAbsval(consdata);
4296  minabsval = consdataGetMinAbsval(consdata);
4297 
4298  /* return if scaling by maxval will eliminate coefficients */
4299  if( SCIPisZero(scip, minabsval/maxabsval) )
4300  return SCIP_OKAY;
4301 
4302  /* return if scaling by maxval will eliminate or generate non-zero sides */
4303  if( !SCIPisInfinity(scip, consdata->lhs) && SCIPisFeasZero(scip, consdata->lhs) != SCIPisFeasZero(scip, consdata->lhs/maxabsval) )
4304  return SCIP_OKAY;
4305  if( !SCIPisInfinity(scip, consdata->rhs) && SCIPisFeasZero(scip, consdata->rhs) != SCIPisFeasZero(scip, consdata->rhs/maxabsval) )
4306  return SCIP_OKAY;
4307 
4308  /* check if not all absolute coefficients are near 1.0 but scaling could do */
4309  if( SCIPisLT(scip, minabsval, 1.0) != SCIPisGT(scip, maxabsval, 1.0) )
4310  {
4311  SCIP_Real scalar;
4312 
4313  /* calculate scale of the average minimum and maximum absolute coefficient to 1.0 */
4314  scalar = 2.0 / (minabsval + maxabsval);
4315 
4316  /* check if all scaled absolute coefficients are near 1.0
4317  * we can relax EQ(x,1.0) to LE(x,1.0), as LT(x,1.0) is not possible
4318  */
4319  if( SCIPisLE(scip, scalar * maxabsval, 1.0) )
4320  {
4321  SCIPdebugMsg(scip, "divide linear constraint with %g, because all coefficients are in absolute value the same\n", maxabsval);
4322  SCIPdebugPrintCons(scip, cons, NULL);
4323  SCIP_CALL( scaleCons(scip, cons, scalar) );
4324 
4325  /* get new consdata information, because scaleCons() might have deleted variables */
4326  vals = consdata->vals;
4327  nvars = consdata->nvars;
4328 
4329  assert(nvars == 0 || vals != NULL);
4330  }
4331  }
4332 
4333  /* nvars might have changed */
4334  if( nvars == 0 )
4335  {
4336  consdata->normalized = TRUE;
4337  return SCIP_OKAY;
4338  }
4339 
4340  assert(vals != NULL);
4341 
4342  /* calculate the maximal multiplier for common divisor calculation:
4343  * |p/q - val| < epsilon and q < feastol/epsilon => |p - q*val| < feastol
4344  * which means, a value of feastol/epsilon should be used as maximal multiplier;
4345  * additionally, we don't want to scale the constraint if this would lead to too
4346  * large coefficients
4347  */
4348  epsilon = SCIPepsilon(scip) * 0.9; /* slightly decrease epsilon to be safe in rational conversion below */
4349  feastol = SCIPfeastol(scip);
4350  maxmult = (SCIP_Longint)(feastol/epsilon + feastol);
4351 
4352  if( !consdata->hasnonbinvalid )
4353  consdataCheckNonbinvar(consdata);
4354 
4355  /* get maximum absolute coefficient */
4356  maxabsval = consdataGetMaxAbsval(consdata);
4357 
4358  /* if all variables are of integral type we will allow a greater multiplier */
4359  if( !consdata->hascontvar )
4360  maxmult = MIN(maxmult, (SCIP_Longint) (MAXSCALEDCOEFINTEGER / MAX(maxabsval, 1.0))); /*lint !e835*/
4361  else
4362  maxmult = MIN(maxmult, (SCIP_Longint) (MAXSCALEDCOEF / MAX(maxabsval, 1.0))); /*lint !e835*/
4363 
4364  /*
4365  * multiplication with +1 or -1
4366  */
4367  mult = 0;
4368 
4369  /* 1. the right hand side must not be negative */
4370  if( SCIPisPositive(scip, consdata->lhs) )
4371  mult = +1;
4372  else if( SCIPisNegative(scip, consdata->rhs) )
4373  mult = -1;
4374 
4375  if( mult == 0 )
4376  {
4377  /* 2. the right hand side must not be infinite */
4378  if( SCIPisInfinity(scip, -consdata->lhs) )
4379  mult = +1;
4380  else if( SCIPisInfinity(scip, consdata->rhs) )
4381  mult = -1;
4382  }
4383 
4384  if( mult == 0 )
4385  {
4386  /* 3. the absolute value of the right hand side must be greater than that of the left hand side */
4387  if( SCIPisGT(scip, REALABS(consdata->rhs), REALABS(consdata->lhs)) )
4388  mult = +1;
4389  else if( SCIPisLT(scip, REALABS(consdata->rhs), REALABS(consdata->lhs)) )
4390  mult = -1;
4391  }
4392 
4393  if( mult == 0 )
4394  {
4395  /* 4. the number of positive coefficients must not be smaller than the number of negative coefficients */
4396  nposcoeffs = 0;
4397  nnegcoeffs = 0;
4398  for( i = 0; i < nvars; ++i )
4399  {
4400  if( vals[i] > 0.0 )
4401  nposcoeffs++;
4402  else
4403  nnegcoeffs++;
4404  }
4405  if( nposcoeffs > nnegcoeffs )
4406  mult = +1;
4407  else if( nposcoeffs < nnegcoeffs )
4408  mult = -1;
4409  }
4410 
4411  if( mult == 0 )
4412  {
4413  /* 5. multiply with +1 */
4414  mult = +1;
4415  }
4416 
4417  assert(mult == +1 || mult == -1);
4418  if( mult == -1 )
4419  {
4420  /* scale the constraint with -1 */
4421  SCIPdebugMsg(scip, "multiply linear constraint with -1.0\n");
4422  SCIPdebugPrintCons(scip, cons, NULL);
4423  SCIP_CALL( scaleCons(scip, cons, -1.0) );
4424 
4425  /* scalecons() can delete variables, but scaling with -1 should not do that */
4426  assert(nvars == consdata->nvars);
4427  }
4428 
4429  /*
4430  * rationals to integrals
4431  *
4432  * @todo try scaling only on behalf of non-continuous variables
4433  */
4434  success = TRUE;
4435  scm = 1;
4436  for( i = 0; i < nvars && success && scm <= maxmult; ++i )
4437  {
4438  if( !SCIPisIntegral(scip, vals[i]) )
4439  {
4440  /* epsilon has been slightly decreased above - to be on the safe side */
4441  success = SCIPrealToRational(vals[i], -epsilon, epsilon , maxmult, &nominator, &denominator);
4442  if( success )
4443  scm = SCIPcalcSmaComMul(scm, denominator);
4444  }
4445  }
4446  assert(scm >= 1);
4447 
4448  /* it might be that we have really big coefficients, but all are integral, in that case we want to divide them by
4449  * their greatest common divisor
4450  */
4451  onlyintegral = TRUE;
4452  if( scm == 1 )
4453  {
4454  for( i = nvars - 1; i >= 0; --i )
4455  {
4456  if( !SCIPisIntegral(scip, vals[i]) )
4457  {
4458  onlyintegral = FALSE;
4459  break;
4460  }
4461  }
4462  }
4463 
4464  success = success && (scm <= maxmult || (scm == 1 && onlyintegral));
4465  if( success && scm != 1 )
4466  {
4467  /* scale the constraint with the smallest common multiple of all denominators */
4468  SCIPdebugMsg(scip, "scale linear constraint with %" SCIP_LONGINT_FORMAT " to make coefficients integral\n", scm);
4469  SCIPdebugPrintCons(scip, cons, NULL);
4470  SCIP_CALL( scaleCons(scip, cons, (SCIP_Real)scm) );
4471 
4472  if( consdata->validmaxabsval )
4473  {
4474  consdata->maxabsval *= REALABS((SCIP_Real)scm);
4475  if( !SCIPisIntegral(scip, consdata->maxabsval) )
4476  {
4477  consdata->validmaxabsval = FALSE;
4478  consdata->maxabsval = SCIP_INVALID;
4479  consdataCalcMaxAbsval(consdata);
4480  }
4481  }
4482 
4483  if( consdata->validminabsval )
4484  {
4485  consdata->minabsval *= REALABS((SCIP_Real)scm);
4486  if( !SCIPisIntegral(scip, consdata->minabsval) )
4487  {
4488  consdata->validminabsval = FALSE;
4489  consdata->minabsval = SCIP_INVALID;
4490  consdataCalcMinAbsval(consdata);
4491  }
4492  }
4493 
4494  /* get new consdata information, because scalecons() might have deleted variables */
4495  vals = consdata->vals;
4496  nvars = consdata->nvars;
4497  assert(nvars == 0 || vals != NULL);
4498  }
4499 
4500  /*
4501  * division by greatest common divisor
4502  */
4503  if( success && nvars >= 1 )
4504  {
4505  /* all coefficients are integral: divide them by their greatest common divisor */
4506  assert(SCIPisIntegral(scip, vals[0]));
4507 
4508  gcd = (SCIP_Longint)(REALABS(vals[0]) + feastol);
4509  for( i = 1; i < nvars && gcd > 1; ++i )
4510  {
4511  assert(SCIPisIntegral(scip, vals[i]));
4512  gcd = SCIPcalcGreComDiv(gcd, (SCIP_Longint)(REALABS(vals[i]) + feastol));
4513  }
4514 
4515  if( gcd > 1 )
4516  {
4517  /* since the lhs/rhs is not respected for gcd calculation it can happen that we detect infeasibility */
4518  if( !consdata->hascontvar && onlyintegral )
4519  {
4520  if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) && !SCIPisFeasIntegral(scip, consdata->rhs / gcd) )
4521  {
4522  *infeasible = TRUE;
4523 
4524  SCIPdebugMsg(scip, "detected infeasibility of constraint after scaling with gcd=%" SCIP_LONGINT_FORMAT ":\n", gcd);
4525  SCIPdebugPrintCons(scip, cons, NULL);
4526 
4527  return SCIP_OKAY;
4528  }
4529  }
4530 
4531  /* divide the constraint by the greatest common divisor of the coefficients */
4532  SCIPdebugMsg(scip, "divide linear constraint by greatest common divisor %" SCIP_LONGINT_FORMAT "\n", gcd);
4533  SCIPdebugPrintCons(scip, cons, NULL);
4534  SCIP_CALL( scaleCons(scip, cons, 1.0/(SCIP_Real)gcd) );
4535 
4536  if( consdata->validmaxabsval )
4537  {
4538  consdata->maxabsval /= REALABS((SCIP_Real)gcd);
4539  }
4540  if( consdata->validminabsval )
4541  {
4542  consdata->minabsval /= REALABS((SCIP_Real)gcd);
4543  }
4544  }
4545  }
4546 
4547  /* mark constraint to be normalized */
4548  consdata->normalized = TRUE;
4549 
4550  SCIPdebugMsg(scip, "normalized constraint:\n");
4551  SCIPdebugPrintCons(scip, cons, NULL);
4552 
4553  return SCIP_OKAY;
4554 }
4555 
4556 /** replaces multiple occurrences of a variable by a single coefficient */
4557 static
4559  SCIP* scip, /**< SCIP data structure */
4560  SCIP_CONS* cons /**< linear constraint */
4561  )
4562 {
4563  SCIP_CONSDATA* consdata;
4564  SCIP_VAR* var;
4565  SCIP_Real valsum;
4566  int v;
4567 
4568  assert(scip != NULL);
4569  assert(cons != NULL);
4570 
4571  consdata = SCIPconsGetData(cons);
4572  assert(consdata != NULL);
4573 
4574  if( consdata->merged )
4575  return SCIP_OKAY;
4576 
4577  /* sort the constraint */
4578  SCIP_CALL( consdataSort(scip, consdata) );
4579 
4580  /* go backwards through the constraint looking for multiple occurrences of the same variable;
4581  * backward direction is necessary, since delCoefPos() modifies the given position and
4582  * the subsequent ones
4583  */
4584  v = consdata->nvars-1;
4585  while( v >= 1 )
4586  {
4587  var = consdata->vars[v];
4588  if( consdata->vars[v-1] == var )
4589  {
4590  valsum = consdata->vals[v];
4591  do
4592  {
4593  SCIP_CALL( delCoefPos(scip, cons, v) );
4594  --v;
4595  valsum += consdata->vals[v];
4596  }
4597  while( v >= 1 && consdata->vars[v-1] == var );
4598 
4599  /* modify the last existing occurrence of the variable */
4600  assert(consdata->vars[v] == var);
4601  if( SCIPisZero(scip, valsum) )
4602  {
4603  SCIP_CALL( delCoefPos(scip, cons, v) );
4604 
4605  /* if the variable defining the maximal activity delta was removed from the constraint, the maximal activity
4606  * delta needs to be recalculated on the next real propagation
4607  */
4608  if( consdata->maxactdeltavar == var )
4609  {
4610  consdata->maxactdelta = SCIP_INVALID;
4611  consdata->maxactdeltavar = NULL;
4612  }
4613  }
4614  else
4615  {
4616  SCIP_CALL( chgCoefPos(scip, cons, v, valsum) );
4617  }
4618  }
4619  --v;
4620  }
4621 
4622  consdata->merged = TRUE;
4623 
4624  return SCIP_OKAY;
4625 }
4626 
4627 /** replaces all fixed and aggregated variables by their non-fixed counterparts */
4628 static
4630  SCIP* scip, /**< SCIP data structure */
4631  SCIP_CONS* cons, /**< linear constraint */
4632  SCIP_Bool* infeasible /**< pointer to store if infeasibility is detected; or NULL if this
4633  * information is not needed; in this case, we apply all fixings
4634  * instead of stopping after the first infeasible one */
4635  )
4636 {
4637  SCIP_CONSDATA* consdata;
4638  SCIP_VAR* var;
4639  SCIP_VAR** aggrvars;
4640  SCIP_Real val;
4641  SCIP_Real* aggrscalars;
4642  SCIP_Real fixedval;
4643  SCIP_Real aggrconst;
4644  int v;
4645  int naggrvars;
4646  int i;
4647 
4648  assert(scip != NULL);
4649  assert(cons != NULL);
4650 
4651  if( infeasible != NULL )
4652  *infeasible = FALSE;
4653 
4654  consdata = SCIPconsGetData(cons);
4655  assert(consdata != NULL);
4656 
4657  if( consdata->eventdata == NULL )
4658  {
4659  SCIP_CONSHDLR* conshdlr;
4660  SCIP_CONSHDLRDATA* conshdlrdata;
4661 
4662  conshdlr = SCIPconsGetHdlr(cons);
4663  assert(conshdlr != NULL);
4664 
4665  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4666  assert(conshdlrdata != NULL);
4667 
4668  /* catch bound change events of variables */
4669  SCIP_CALL( consCatchAllEvents(scip, cons, conshdlrdata->eventhdlr) );
4670  assert(consdata->eventdata != NULL);
4671  }
4672 
4673  if( !consdata->removedfixings )
4674  {
4675  SCIP_Real lhssubtrahend;
4676  SCIP_Real rhssubtrahend;
4677 
4678  /* if an unmodifiable row has been added to the LP, then we cannot apply fixing anymore (cannot change a row)
4679  * this should not happen, as applyFixings is called in addRelaxation() before creating and adding a row
4680  */
4681  assert(consdata->row == NULL || !SCIProwIsInLP(consdata->row) || SCIProwIsModifiable(consdata->row));
4682 
4683  lhssubtrahend = 0.0;
4684  rhssubtrahend = 0.0;
4685 
4686  SCIPdebugMsg(scip, "applying fixings:\n");
4687  SCIPdebugPrintCons(scip, cons, NULL);
4688 
4689  v = 0;
4690  while( v < consdata->nvars )
4691  {
4692  var = consdata->vars[v];
4693  val = consdata->vals[v];
4694  assert(SCIPvarIsTransformed(var));
4695 
4696  switch( SCIPvarGetStatus(var) )
4697  {
4699  SCIPerrorMessage("original variable in transformed linear constraint\n");
4700  return SCIP_INVALIDDATA;
4701 
4702  case SCIP_VARSTATUS_LOOSE:
4703  case SCIP_VARSTATUS_COLUMN:
4704  ++v;
4705  break;
4706 
4707  case SCIP_VARSTATUS_FIXED:
4708  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)));
4709  fixedval = SCIPvarGetLbGlobal(var);
4710  if( !SCIPisInfinity(scip, -consdata->lhs) )
4711  {
4712  if( SCIPisInfinity(scip, ABS(fixedval)) )
4713  {
4714  /* if lhs gets infinity it means that the problem is infeasible */
4715  if( ( val > 0.0 ) != ( fixedval > 0.0 ) )
4716  {
4717  SCIP_CALL( chgLhs(scip, cons, SCIPinfinity(scip)) );
4718 
4719  if( infeasible != NULL )
4720  {
4721  *infeasible = TRUE;
4722  return SCIP_OKAY;
4723  }
4724  }
4725  else
4726  {
4727  SCIP_CALL( chgLhs(scip, cons, -SCIPinfinity(scip)) );
4728  }
4729  }
4730  else
4731  lhssubtrahend += val * fixedval;
4732  }
4733  if( !SCIPisInfinity(scip, consdata->rhs) )
4734  {
4735  if( SCIPisInfinity(scip, ABS(fixedval)) )
4736  {
4737  /* if rhs gets -infinity it means that the problem is infeasible */
4738  if( ( val > 0.0 ) == ( fixedval > 0.0 ) )
4739  {
4740  SCIP_CALL( chgRhs(scip, cons, -SCIPinfinity(scip)) );
4741 
4742  if( infeasible != NULL )
4743  {
4744  *infeasible = TRUE;
4745  return SCIP_OKAY;
4746  }
4747  }
4748  else
4749  {
4750  SCIP_CALL( chgRhs(scip, cons, SCIPinfinity(scip)) );
4751  }
4752  }
4753  else
4754  rhssubtrahend += val * fixedval;
4755  }
4756  SCIP_CALL( delCoefPos(scip, cons, v) );
4757  break;
4758 
4760  {
4761  SCIP_VAR* activevar = SCIPvarGetAggrVar(var);
4762  SCIP_Real activescalar = val * SCIPvarGetAggrScalar(var);
4763  SCIP_Real activeconstant = val * SCIPvarGetAggrConstant(var);
4764 
4765  assert(activevar != NULL);
4766  SCIP_CALL( SCIPgetProbvarSum(scip, &activevar, &activescalar, &activeconstant) );
4767  assert(activevar != NULL);
4768 
4769  if( !SCIPisZero(scip, activescalar) )
4770  {
4771  SCIP_CALL( addCoef(scip, cons, activevar, activescalar) );
4772  }
4773 
4774  if( !SCIPisZero(scip, activeconstant) )
4775  {
4776  if( !SCIPisInfinity(scip, -consdata->lhs) )
4777  lhssubtrahend += activeconstant;
4778  if( !SCIPisInfinity(scip, consdata->rhs) )
4779  rhssubtrahend += activeconstant;
4780  }
4781 
4782  SCIP_CALL( delCoefPos(scip, cons, v) );
4783  break;
4784  }
4787  naggrvars = SCIPvarGetMultaggrNVars(var);
4788  aggrvars = SCIPvarGetMultaggrVars(var);
4789  aggrscalars = SCIPvarGetMultaggrScalars(var);
4790  for( i = 0; i < naggrvars; ++i )
4791  {
4792  SCIP_CALL( addCoef(scip, cons, aggrvars[i], val * aggrscalars[i]) );
4793  }
4794  aggrconst = SCIPvarGetMultaggrConstant(var);
4795 
4796  if( !SCIPisInfinity(scip, -consdata->lhs) )
4797  lhssubtrahend += val * aggrconst;
4798  if( !SCIPisInfinity(scip, consdata->rhs) )
4799  rhssubtrahend += val * aggrconst;
4800 
4801  SCIP_CALL( delCoefPos(scip, cons, v) );
4802  break;
4803 
4805  SCIP_CALL( addCoef(scip, cons, SCIPvarGetNegationVar(var), -val) );
4806  aggrconst = SCIPvarGetNegationConstant(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 
4816  default:
4817  SCIPerrorMessage("unknown variable status\n");
4818  SCIPABORT();
4819  return SCIP_INVALIDDATA; /*lint !e527*/
4820  }
4821  }
4822 
4823  if( !SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->lhs) )
4824  {
4825  /* check left hand side of unmodifiable empty constraint with former feasibility tolerance */
4826  if( !SCIPconsIsModifiable(cons) && consdata->nvars == 0 )
4827  {
4828  if( SCIPisFeasLT(scip, lhssubtrahend, consdata->lhs) )
4829  {
4830  SCIP_CALL( chgLhs(scip, cons, SCIPinfinity(scip)) );
4831 
4832  if( infeasible != NULL )
4833  {
4834  *infeasible = TRUE;
4835  return SCIP_OKAY;
4836  }
4837  }
4838  else
4839  {
4840  SCIP_CALL( chgLhs(scip, cons, -SCIPinfinity(scip)) );
4841  }
4842  }
4843  /* for large numbers that are relatively equal, subtraction can lead to cancellation,
4844  * causing wrong fixings of other variables --> better use a real zero here
4845  */
4846  else if( SCIPisEQ(scip, lhssubtrahend, consdata->lhs) )
4847  {
4848  SCIP_CALL( chgLhs(scip, cons, 0.0) );
4849  }
4850  else
4851  {
4852  SCIP_CALL( chgLhs(scip, cons, consdata->lhs - lhssubtrahend) );
4853  }
4854  }
4855  if( !SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, -consdata->rhs) )
4856  {
4857  /* check right hand side of unmodifiable empty constraint with former feasibility tolerance */
4858  if( !SCIPconsIsModifiable(cons) && consdata->nvars == 0 )
4859  {
4860  if( SCIPisFeasGT(scip, rhssubtrahend, consdata->rhs) )
4861  {
4862  SCIP_CALL( chgRhs(scip, cons, -SCIPinfinity(scip)) );
4863 
4864  if( infeasible != NULL )
4865  {
4866  *infeasible = TRUE;
4867  return SCIP_OKAY;
4868  }
4869  }
4870  else
4871  {
4872  SCIP_CALL( chgRhs(scip, cons, SCIPinfinity(scip)) );
4873  }
4874  }
4875  /* for large numbers that are relatively equal, substraction can lead to cancellation,
4876  * causing wrong fixings of other variables --> better use a real zero here
4877  */
4878  else if( SCIPisEQ(scip, rhssubtrahend, consdata->rhs) )
4879  {
4880  SCIP_CALL( chgRhs(scip, cons, 0.0) );
4881  }
4882  else
4883  {
4884  SCIP_CALL( chgRhs(scip, cons, consdata->rhs - rhssubtrahend) );
4885  }
4886  }
4887  consdata->removedfixings = TRUE;
4888 
4889  SCIPdebugMsg(scip, "after fixings:\n");
4890  SCIPdebugPrintCons(scip, cons, NULL);
4891 
4892  /* if aggregated variables have been replaced, multiple entries of the same variable are possible and we have
4893  * to clean up the constraint
4894  */
4895  SCIP_CALL( mergeMultiples(scip, cons) );
4896 
4897  SCIPdebugMsg(scip, "after merging:\n");
4898  SCIPdebugPrintCons(scip, cons, NULL);
4899  }
4900  assert(consdata->removedfixings);
4901 
4902 #ifndef NDEBUG
4903  /* check, if all fixings are applied */
4904  for( v = 0; v < consdata->nvars; ++v )
4905  assert(SCIPvarIsActive(consdata->vars[v]));
4906 #endif
4907 
4908  return SCIP_OKAY;
4909 }
4910 
4911 /** for each variable in the linear constraint, except the inferred variable, adds one bound to the conflict analysis'
4912  * candidate store (bound depends on sign of coefficient and whether the left or right hand side was the reason for the
4913  * inference variable's bound change); the conflict analysis can be initialized with the linear constraint being the
4914  * conflict detecting constraint by using NULL as inferred variable
4915  */
4916 static
4918  SCIP* scip, /**< SCIP data structure */
4919  SCIP_CONS* cons, /**< constraint that inferred the bound change */
4920  SCIP_VAR* infervar, /**< variable that was deduced, or NULL */
4921  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4922  int inferpos, /**< position of the inferred variable in the vars array */
4923  SCIP_Bool reasonisrhs /**< is the right hand side responsible for the bound change? */
4924  )
4925 {
4926  SCIP_CONSDATA* consdata;
4927  SCIP_VAR** vars;
4928  SCIP_Real* vals;
4929  int nvars;
4930  int i;
4931 
4932  assert(scip != NULL);
4933  assert(cons != NULL);
4934 
4935  consdata = SCIPconsGetData(cons);
4937  assert(consdata != NULL);
4938 
4939  vars = consdata->vars;
4940  vals = consdata->vals;
4941  nvars = consdata->nvars;
4942 
4943  assert(vars != NULL || nvars == 0);
4944  assert(vals != NULL || nvars == 0);
4945 
4946  assert(-1 <= inferpos && inferpos < nvars);
4947  assert((infervar == NULL) == (inferpos == -1));
4948  assert(inferpos == -1 || vars[inferpos] == infervar); /*lint !e613*/
4949 
4950  /* for each variable, add the bound to the conflict queue, that is responsible for the minimal or maximal
4951  * residual value, depending on whether the left or right hand side is responsible for the bound change:
4952  * - if the right hand side is the reason, the minimal residual activity is responsible
4953  * - if the left hand side is the reason, the maximal residual activity is responsible
4954  */
4955 
4956  /* if the variable is integral we only need to add reason bounds until the propagation could be applied */
4957  if( infervar == NULL || SCIPvarIsIntegral(infervar) )
4958  {
4959  SCIP_Real minresactivity;
4960  SCIP_Real maxresactivity;
4961  SCIP_Bool ismintight;
4962  SCIP_Bool ismaxtight;
4963  SCIP_Bool isminsettoinfinity;
4964  SCIP_Bool ismaxsettoinfinity;
4965 
4966  minresactivity = -SCIPinfinity(scip);
4967  maxresactivity = SCIPinfinity(scip);
4968 
4969  /* calculate the minimal and maximal global activity of all other variables involved in the constraint */
4970  if( infervar != NULL )
4971  {
4972  assert(vals != NULL); /* for flexelint */
4973  if( reasonisrhs )
4974  consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, &minresactivity, NULL,
4975  &ismintight, NULL, &isminsettoinfinity, NULL);
4976  else
4977  consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, NULL, &maxresactivity,
4978  NULL, &ismaxtight, NULL, &ismaxsettoinfinity);
4979  }
4980  else
4981  {
4982  if( reasonisrhs )
4983  consdataGetGlbActivityBounds(scip, consdata, FALSE, &minresactivity, NULL,
4984  &ismintight, NULL, &isminsettoinfinity, NULL);
4985  else
4986  consdataGetGlbActivityBounds(scip, consdata, FALSE, NULL, &maxresactivity,
4987  NULL, &ismaxtight, NULL, &ismaxsettoinfinity);
4988  }
4989 
4990  /* we can only do something clever, if the residual activity is finite and not relaxed */
4991  if( (reasonisrhs && !isminsettoinfinity && ismintight) || (!reasonisrhs && !ismaxsettoinfinity && ismaxtight) ) /*lint !e644*/
4992  {
4993  SCIP_Real rescap;
4994  SCIP_Bool resactisinf;
4995 
4996  resactisinf = FALSE;
4997 
4998  /* calculate the residual capacity that would be left, if the variable would be set to one more / one less
4999  * than its inferred bound
5000  */
5001  if( infervar != NULL )
5002  {
5003  assert(vals != NULL); /* for flexelint */
5004 
5005  if( reasonisrhs )
5006  {
5007  if( SCIPisUpdateUnreliable(scip, minresactivity, consdata->lastglbminactivity) )
5008  {
5009  consdataGetReliableResidualActivity(scip, consdata, infervar, &minresactivity, TRUE, TRUE);
5010  if( SCIPisInfinity(scip, -minresactivity) )
5011  resactisinf = TRUE;
5012  }
5013  rescap = consdata->rhs - minresactivity;
5014  }
5015  else
5016  {
5017  if( SCIPisUpdateUnreliable(scip, maxresactivity, consdata->lastglbmaxactivity) )
5018  {
5019  consdataGetReliableResidualActivity(scip, consdata, infervar, &maxresactivity, FALSE, TRUE);
5020  if( SCIPisInfinity(scip, maxresactivity) )
5021  resactisinf = TRUE;
5022  }
5023  rescap = consdata->lhs - maxresactivity;
5024  }
5025 
5026  if( reasonisrhs == (vals[inferpos] > 0.0) )
5027  rescap -= vals[inferpos] * (SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) + 1.0);
5028  else
5029  rescap -= vals[inferpos] * (SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) - 1.0);
5030  }
5031  else
5032  rescap = (reasonisrhs ? consdata->rhs - minresactivity : consdata->lhs - maxresactivity);
5033 
5034  if( !resactisinf )
5035  {
5036  /* now add bounds as reasons until the residual capacity is exceeded */
5037  for( i = 0; i < nvars; ++i )
5038  {
5039  assert( vars != NULL && vals != NULL ); /* for lint */
5040 
5041  /* zero coefficients and the inferred variable can be ignored */
5042  if( vars[i] == infervar || SCIPisZero(scip, vals[i]) )
5043  continue;
5044 
5045  /* check if the residual capacity is exceeded */
5046  if( (reasonisrhs && SCIPisFeasNegative(scip, rescap))
5047  || (!reasonisrhs && SCIPisFeasPositive(scip, rescap)) )
5048  break;
5049 
5050  /* update the residual capacity due to the local bound of this variable */
5051  if( reasonisrhs == (vals[i] > 0.0) )
5052  {
5053  /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound */
5054  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
5055  rescap -= vals[i] * (SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetLbGlobal(vars[i]));
5056  }
5057  else
5058  {
5059  /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound */
5060  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
5061  rescap -= vals[i] * (SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetUbGlobal(vars[i]));
5062  }
5063  }
5064  return SCIP_OKAY;
5065  }
5066  }
5067  }
5068 
5069  /* for a bound change on a continuous variable, all locally changed bounds are responsible */
5070  for( i = 0; i < nvars; ++i )
5071  {
5072  assert(vars != NULL); /* for flexelint */
5073  assert(vals != NULL); /* for flexelint */
5074 
5075  /* zero coefficients and the inferred variable can be ignored */
5076  if( vars[i] == infervar || SCIPisZero(scip, vals[i]) )
5077  continue;
5078 
5079  if( reasonisrhs == (vals[i] > 0.0) )
5080  {
5081  /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound is responsible */
5082  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
5083  }
5084  else
5085  {
5086  /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound is responsible */
5087  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
5088  }
5089  }
5090 
5091  return SCIP_OKAY;
5092 }
5093 
5094 /** for each variable in the linear ranged row constraint, except the inferred variable, adds the bounds of all fixed
5095  * variables to the conflict analysis' candidate store; the conflict analysis can be initialized
5096  * with the linear constraint being the conflict detecting constraint by using NULL as inferred variable
5097  */
5098 static
5100  SCIP* scip, /**< SCIP data structure */
5101  SCIP_CONS* cons, /**< constraint that inferred the bound change */
5102  SCIP_VAR* infervar, /**< variable that was deduced, or NULL */
5103  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
5104  int inferpos /**< position of the inferred variable in the vars array, or -1 */
5105  )
5106 {
5107  SCIP_CONSDATA* consdata;
5108  SCIP_VAR** vars;
5109  int nvars;
5110  int v;
5111 
5112  assert(scip != NULL);
5113  assert(cons != NULL);
5114 
5115  consdata = SCIPconsGetData(cons);
5116  assert(consdata != NULL);
5117  vars = consdata->vars;
5118  nvars = consdata->nvars;
5119  assert(vars != NULL || nvars == 0);
5120  assert(-1 <= inferpos && inferpos < nvars);
5121  assert((infervar == NULL) == (inferpos == -1));
5122  assert(inferpos == -1 || vars != NULL);
5123  assert(inferpos == -1 || vars[inferpos] == infervar); /*lint !e613*/
5124 
5125  /* collect all fixed variables */
5126  for( v = nvars - 1; v >= 0; --v )
5127  {
5128  assert(vars != NULL); /* for flexelint */
5129 
5130  /* need to add old bounds before propagation of inferrence variable */
5131  if( vars[v] == infervar )
5132  {
5133  assert(vars[v] != NULL);
5134 
5135  if( !SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetLbGlobal(vars[v])) )
5136  {
5137  /* @todo get boundchange index before this last boundchange and correct the index */
5138  SCIP_CALL( SCIPaddConflictLb(scip, vars[v], bdchgidx) );
5139  }
5140 
5141  if( !SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetUbGlobal(vars[v])) )
5142  {
5143  /* @todo get boundchange index before this last boundchange and correct the index */
5144  SCIP_CALL( SCIPaddConflictUb(scip, vars[v], bdchgidx) );
5145  }
5146 
5147  continue;
5148  }
5149 
5150  /* check for fixed variables */
5151  if( SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE)) )
5152  {
5153  /* add all bounds of fixed variables which lead to the boundchange of the given inference variable */
5154  SCIP_CALL( SCIPaddConflictLb(scip, vars[v], bdchgidx) );
5155  SCIP_CALL( SCIPaddConflictUb(scip, vars[v], bdchgidx) );
5156  }
5157  }
5158 
5159  return SCIP_OKAY;
5160 }
5161 
5162 /** add reasoning variables to conflict candidate queue which led to the conflict */
5163 static
5165  SCIP* scip, /**< SCIP data structure */
5166  SCIP_VAR** vars, /**< variables reasoning the infeasibility */
5167  int nvars, /**< number of variables reasoning the infeasibility */
5168  SCIP_VAR* var, /**< variable which was tried to fix/tighten, or NULL */
5169  SCIP_Real bound /**< bound of variable which was tried to apply, or SCIP_INVALID */
5170  )
5171 {
5172  int v;
5173 
5174  assert(scip != NULL);
5175 
5176  /* collect all variables for which the local bounds differ from their global bounds */
5177  for( v = nvars - 1; v >= 0; --v )
5178  {
5179  assert(vars != NULL);
5180 
5181  /* check for local bound changes variables */
5182  if( !SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetLbGlobal(vars[v])) )
5183  {
5184  /* add conflict bound */
5185  SCIP_CALL( SCIPaddConflictLb(scip, vars[v], 0) );
5186  }
5187 
5188  if( !SCIPisEQ(scip, SCIPvarGetUbLocal(vars[v]), SCIPvarGetUbGlobal(vars[v])) )
5189  {
5190  SCIP_CALL( SCIPaddConflictUb(scip, vars[v], 0) );
5191  }
5192  }
5193 
5194  if( var != NULL )
5195  {
5196  if( bound < SCIPvarGetLbLocal(var) )
5197  {
5198  SCIP_CALL( SCIPaddConflictLb(scip, var, 0) );
5199  }
5200 
5201  if( bound > SCIPvarGetUbLocal(var) )
5202  {
5203  SCIP_CALL( SCIPaddConflictUb(scip, var, 0) );
5204  }
5205  }
5206 
5207  return SCIP_OKAY;
5208 }
5209 
5210 /** resolves a propagation on the given variable by supplying the variables needed for applying the corresponding
5211  * propagation rule (see propagateCons()):
5212  * (1) activity residuals of all other variables tighten bounds of single variable
5213  */
5214 static
5216  SCIP* scip, /**< SCIP data structure */
5217  SCIP_CONS* cons, /**< constraint that inferred the bound change */
5218  SCIP_VAR* infervar, /**< variable that was deduced */
5219  INFERINFO inferinfo, /**< inference information */
5220  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
5221  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
5222  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
5223  )
5224 {
5225  SCIP_CONSDATA* consdata;
5226  SCIP_VAR** vars;
5227 #ifndef NDEBUG
5228  SCIP_Real* vals;
5229 #endif
5230  int nvars;
5231  int inferpos;
5232 
5233  assert(scip != NULL);
5234  assert(cons != NULL);
5235  assert(result != NULL);
5236 
5237  consdata = SCIPconsGetData(cons);
5238  assert(consdata != NULL);
5239  vars = consdata->vars;
5240  nvars = consdata->nvars;
5241 #ifndef NDEBUG
5242  vals = consdata->vals;
5243  assert(vars != NULL);
5244  assert(vals != NULL);
5245 #endif
5246 
5247  /* get the position of the inferred variable in the vars array */
5248  inferpos = inferInfoGetPos(inferinfo);
5249  if( inferpos >= nvars || vars[inferpos] != infervar )
5250  {
5251  /* find inference variable in constraint */
5252  /**@todo use a binary search here; the variables can be sorted by variable index */
5253  for( inferpos = 0; inferpos < nvars && vars[inferpos] != infervar; ++inferpos )
5254  {}
5255  }
5256  assert(inferpos < nvars);
5257  assert(vars[inferpos] == infervar);
5258  assert(!SCIPisZero(scip, vals[inferpos]));
5259 
5260  switch( inferInfoGetProprule(inferinfo) )
5261  {
5262  case PROPRULE_1_RHS:
5263  /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
5264  * constraint (only taking the other variables into account) didn't leave enough space for a larger
5265  * domain in order to not exceed the right hand side of the inequality
5266  */
5267  assert((vals[inferpos] > 0.0) == (boundtype == SCIP_BOUNDTYPE_UPPER));
5268  SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, inferpos, TRUE) );
5269  *result = SCIP_SUCCESS;
5270  break;
5271 
5272  case PROPRULE_1_LHS:
5273  /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
5274  * constraint (only taking the other variables into account) didn't leave enough space for a larger
5275  * domain in order to not fall below the left hand side of the inequality
5276  */
5277  assert((vals[inferpos] > 0.0) == (boundtype == SCIP_BOUNDTYPE_LOWER));
5278  SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, inferpos, FALSE) );
5279  *result = SCIP_SUCCESS;
5280  break;
5281 
5282  case PROPRULE_1_RANGEDROW:
5283  /* the bound of the variable was tightened, because some variables were already fixed and the leftover only allow
5284  * the given inference variable to their bounds in this given ranged row
5285  */
5286 
5287  /* check that we really have a ranged row here */
5288  assert(!SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs));
5289  SCIP_CALL( addConflictFixedVars(scip, cons, infervar, bdchgidx, inferpos) );
5290  *result = SCIP_SUCCESS;
5291  break;
5292 
5293  case PROPRULE_INVALID:
5294  default:
5295  SCIPerrorMessage("invalid inference information %d in linear constraint <%s> at position %d for %s bound of variable <%s>\n",
5296  inferInfoGetProprule(inferinfo), SCIPconsGetName(cons), inferInfoGetPos(inferinfo),
5297  boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(infervar));
5298  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
5299  SCIPinfoMessage(scip, NULL, ";\n");
5300  return SCIP_INVALIDDATA;
5301  }
5302 
5303  return SCIP_OKAY;
5304 }
5305 
5306 /** analyzes conflicting bounds on given constraint, and adds conflict constraint to problem */
5307 static
5309  SCIP* scip, /**< SCIP data structure */
5310  SCIP_CONS* cons, /**< conflict detecting constraint */
5311  SCIP_Bool reasonisrhs /**< is the right hand side responsible for the conflict? */
5312  )
5313 {
5314  /* conflict analysis can only be applied in solving stage and if it is turned on */
5316  return SCIP_OKAY;
5317 
5318  /* initialize conflict analysis */
5320 
5321  /* add the conflicting bound for each variable of infeasible constraint to conflict candidate queue */
5322  SCIP_CALL( addConflictBounds(scip, cons, NULL, NULL, -1, reasonisrhs) );
5323 
5324  /* analyze the conflict */
5325  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
5326 
5327  return SCIP_OKAY;
5328 }
5329 
5330 /** check if there is any hope of tightening some bounds */
5331 static
5333  SCIP_CONS* cons /**< linear constraint */
5334  )
5335 {
5336  SCIP_CONSDATA* consdata;
5337  int infcountmin;
5338  int infcountmax;
5339 
5340  consdata = SCIPconsGetData(cons);
5341  assert(consdata != NULL);
5342 
5343  infcountmin = consdata->minactivityneginf
5344  + consdata->minactivityposinf
5345  + consdata->minactivityneghuge
5346  + consdata->minactivityposhuge;
5347  infcountmax = consdata->maxactivityneginf
5348  + consdata->maxactivityposinf
5349  + consdata->maxactivityneghuge
5350  + consdata->maxactivityposhuge;
5352  if( infcountmin > 1 && infcountmax > 1 )
5353  return FALSE;
5354 
5355  return TRUE;
5356 }
5357 
5358 /** tighten upper bound */
5359 static
5361  SCIP* scip, /**< SCIP data structure */
5362  SCIP_CONS* cons, /**< linear constraint */
5363  int pos, /**< variable position */
5364  PROPRULE proprule, /**< propagation rule that deduced the value */
5365  SCIP_Real newub, /**< new upper bound */
5366  SCIP_Real oldub, /**< old upper bound */
5367  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
5368  int* nchgbds, /**< pointer to count the total number of tightened bounds */
5369  SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5370  )
5371 {
5372  SCIP_CONSDATA* consdata;
5373  SCIP_VAR* var;
5374  SCIP_Real lb;
5375  SCIP_Bool infeasible;
5376  SCIP_Bool tightened;
5377 
5378  assert(cons != NULL);
5379  assert(!SCIPisInfinity(scip, newub));
5380 
5381  consdata = SCIPconsGetData(cons);
5382  assert(consdata != NULL);
5383  var = consdata->vars[pos];
5384  assert(var != NULL);
5385 
5386  lb = SCIPvarGetLbLocal(var);
5387  newub = SCIPadjustedVarUb(scip, var, newub);
5388 
5389  if( force || SCIPisUbBetter(scip, newub, lb, oldub) )
5390  {
5391  SCIP_VARTYPE vartype;
5392 
5393  SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, old bds=[%.15g,%.15g], val=%.15g, activity=[%.15g,%.15g], sides=[%.15g,%.15g] -> newub=%.15g\n",
5394  SCIPconsGetName(cons), SCIPvarGetName(var), lb, oldub, consdata->vals[pos],
5395  QUAD_TO_DBL(consdata->minactivity), QUAD_TO_DBL(consdata->maxactivity), consdata->lhs, consdata->rhs, newub);
5396 
5397  vartype = SCIPvarGetType(var);
5398 
5399  /* tighten upper bound */
5400  SCIP_CALL( SCIPinferVarUbCons(scip, var, newub, cons, getInferInt(proprule, pos), force, &infeasible, &tightened) );
5401 
5402  if( infeasible )
5403  {
5404  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5405  SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);
5406 
5407  /* analyze conflict */
5408  SCIP_CALL( analyzeConflict(scip, cons, TRUE) );
5409 
5410  *cutoff = TRUE;
5411  }
5412  else if( tightened )
5413  {
5414  assert(SCIPisFeasLE(scip, SCIPvarGetUbLocal(var), oldub));
5415  SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, new bds=[%.15g,%.15g]\n",
5416  SCIPconsGetName(cons), SCIPvarGetName(var), lb, SCIPvarGetUbLocal(var));
5417 
5418  (*nchgbds)++;
5419 
5420  /* if variable type was changed we might be able to upgrade the constraint */
5421  if( vartype != SCIPvarGetType(var) )
5422  consdata->upgradetried = FALSE;
5423  }
5424  }
5425  return SCIP_OKAY;
5426 }
5427 
5428 /** tighten lower bound */
5429 static
5431  SCIP* scip, /**< SCIP data structure */
5432  SCIP_CONS* cons, /**< linear constraint */
5433  int pos, /**< variable position */
5434  PROPRULE proprule, /**< propagation rule that deduced the value */
5435  SCIP_Real newlb, /**< new lower bound */
5436  SCIP_Real oldlb, /**< old lower bound */
5437  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
5438  int* nchgbds, /**< pointer to count the total number of tightened bounds */
5439  SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5440  )
5441 {
5442  SCIP_CONSDATA* consdata;
5443  SCIP_VAR* var;
5444  SCIP_Real ub;
5445  SCIP_Bool infeasible;
5446  SCIP_Bool tightened;
5447 
5448  assert(cons != NULL);
5449  assert(!SCIPisInfinity(scip, newlb));
5450 
5451  consdata = SCIPconsGetData(cons);
5452  assert(consdata != NULL);
5453  var = consdata->vars[pos];
5454  assert(var != NULL);
5455 
5456  ub = SCIPvarGetUbLocal(var);
5457  newlb = SCIPadjustedVarLb(scip, var, newlb);
5458 
5459  if( force || SCIPisLbBetter(scip, newlb, oldlb, ub) )
5460  {
5461  SCIP_VARTYPE vartype;
5462 
5463  SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, old bds=[%.15g,%.15g], val=%.15g, activity=[%.15g,%.15g], sides=[%.15g,%.15g] -> newlb=%.15g\n",
5464  SCIPconsGetName(cons), SCIPvarGetName(var), oldlb, ub, consdata->vals[pos],
5465  QUAD_TO_DBL(consdata->minactivity), QUAD_TO_DBL(consdata->maxactivity), consdata->lhs, consdata->rhs, newlb);
5466 
5467  vartype = SCIPvarGetType(var);
5468 
5469  /* tighten lower bound */
5470  SCIP_CALL( SCIPinferVarLbCons(scip, var, newlb, cons, getInferInt(proprule, pos), force, &infeasible, &tightened) );
5471 
5472  if( infeasible )
5473  {
5474  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5475  SCIPconsGetName(cons), SCIPvarGetName(var), newlb, ub);
5476 
5477  /* analyze conflict */
5478  SCIP_CALL( analyzeConflict(scip, cons, FALSE) );
5479 
5480  *cutoff = TRUE;
5481  }
5482  else if( tightened )
5483  {
5484  assert(SCIPisFeasGE(scip, SCIPvarGetLbLocal(var), oldlb));
5485  SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, new bds=[%.15g,%.15g]\n",
5486  SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetLbLocal(var), ub);
5487 
5488  (*nchgbds)++;
5489 
5490  /* if variable type was changed we might be able to upgrade the constraint */
5491  if( vartype != SCIPvarGetType(var) )
5492  consdata->upgradetried = FALSE;
5493  }
5494  }
5495  return SCIP_OKAY;
5496 }
5497 
5498 /** tightens bounds of a single variable due to activity bounds (easy case) */
5499 static
5501  SCIP* scip, /**< SCIP data structure */
5502  SCIP_CONS* cons, /**< linear constraint */
5503  int pos, /**< position of the variable in the vars array */
5504  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
5505  int* nchgbds, /**< pointer to count the total number of tightened bounds */
5506  SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5507  )
5508 {
5509  SCIP_CONSDATA* consdata;
5510  SCIP_VAR* var;
5511  SCIP_Real val;
5512  SCIP_Real lb;
5513  SCIP_Real ub;
5514  SCIP_Real lhs;
5515  SCIP_Real rhs;
5516 
5517  assert(scip != NULL);
5518  assert(cons != NULL);
5519  assert(cutoff != NULL);
5520  assert(nchgbds != NULL);
5521 
5522  /* we cannot tighten variables' bounds, if the constraint may be not complete */
5523  if( SCIPconsIsModifiable(cons) )
5524  return SCIP_OKAY;
5525 
5526  consdata = SCIPconsGetData(cons);
5527  assert(consdata != NULL);
5528  assert(0 <= pos && pos < consdata->nvars);
5529 
5530  *cutoff = FALSE;
5531 
5532  var = consdata->vars[pos];
5533  assert(var != NULL);
5534 
5535  /* we cannot tighten bounds of multi-aggregated variables */
5537  return SCIP_OKAY;
5538 
5539  val = consdata->vals[pos];
5540  lhs = consdata->lhs;
5541  rhs = consdata->rhs;
5542  assert(!SCIPisZero(scip, val));
5543  assert(!SCIPisInfinity(scip, lhs));
5544  assert(!SCIPisInfinity(scip, -rhs));
5545 
5546  lb = SCIPvarGetLbLocal(var);
5547  ub = SCIPvarGetUbLocal(var);
5548  assert(SCIPisLE(scip, lb, ub));
5549 
5550  /* recompute activities if needed */
5551  if( !consdata->validactivities )
5552  consdataCalcActivities(scip, consdata);
5553  assert(consdata->validactivities);
5554  if( !consdata->validminact )
5555  consdataRecomputeMinactivity(scip, consdata);
5556  assert(consdata->validminact);
5557 
5558  if( val > 0.0 )
5559  {
5560  /* check, if we can tighten the variable's upper bound */
5561  if( !SCIPisInfinity(scip, rhs) )
5562  {
5563  SCIP_Real slack;
5564  SCIP_Real alpha;
5565 
5566  /* min activity should be valid at this point (if this is not true, then some decisions might be wrong!) */
5567  assert(consdata->validminact);
5568 
5569  /* if the minactivity is larger than the right hand side by feasibility epsilon, the constraint is infeasible */
5570  if( SCIPisFeasLT(scip, rhs, QUAD_TO_DBL(consdata->minactivity)) )
5571  {
5572  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, minactivity=%.15g > rhs=%.15g\n",
5573  SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->minactivity), rhs);
5574 
5575  *cutoff = TRUE;
5576  return SCIP_OKAY;
5577  }
5578 
5579  slack = rhs - QUAD_TO_DBL(consdata->minactivity);
5580 
5581  /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5582  * it to zero
5583  */
5584  if( !SCIPisPositive(scip, slack) )
5585  slack = 0.0;
5586 
5587  alpha = val * (ub - lb);
5588  assert(!SCIPisNegative(scip, alpha));
5589 
5590  if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
5591  {
5592  SCIP_Real newub;
5593 
5594  /* compute new upper bound */
5595  newub = lb + (slack / val);
5596 
5597  SCIP_CALL( tightenVarUb(scip, cons, pos, PROPRULE_1_RHS, newub, ub, cutoff, nchgbds, force) );
5598 
5599  if( *cutoff )
5600  {
5601  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5602  SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);
5603 
5604  return SCIP_OKAY;
5605  }
5606 
5607  /* collect the new upper bound which is needed for the lower bound computation */
5608  ub = SCIPvarGetUbLocal(var);
5609  }
5610  }
5611 
5612  /* check, if we can tighten the variable's lower bound */
5613  if( !SCIPisInfinity(scip, -lhs) )
5614  {
5615  SCIP_Real slack;
5616  SCIP_Real alpha;
5617 
5618  /* make sure the max activity is reliable */
5619  if( !consdata->validmaxact )
5620  {
5621  consdataRecomputeMaxactivity(scip, consdata);
5622  }
5623  assert(consdata->validmaxact);
5624 
5625  /* if the maxactivity is smaller than the left hand side by feasibility epsilon, the constraint is infeasible */
5626  if( SCIPisFeasLT(scip, QUAD_TO_DBL(consdata->maxactivity), lhs) )
5627  {
5628  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, maxactivity=%.15g < lhs=%.15g\n",
5629  SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->maxactivity), lhs);
5630 
5631  *cutoff = TRUE;
5632  return SCIP_OKAY;
5633  }
5634 
5635  slack = QUAD_TO_DBL(consdata->maxactivity) - lhs;
5636 
5637  /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5638  * it to zero
5639  */
5640  if( !SCIPisPositive(scip, slack) )
5641  slack = 0.0;
5642 
5643  alpha = val * (ub - lb);
5644  assert(!SCIPisNegative(scip, alpha));
5645 
5646  if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
5647  {
5648  SCIP_Real newlb;
5649 
5650  /* compute new lower bound */
5651  newlb = ub - (slack / val);
5652 
5653  SCIP_CALL( tightenVarLb(scip, cons, pos, PROPRULE_1_LHS, newlb, lb, cutoff, nchgbds, force) );
5654 
5655  if( *cutoff )
5656  {
5657  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5658  SCIPconsGetName(cons), SCIPvarGetName(var), newlb, ub);
5659 
5660  return SCIP_OKAY;
5661  }
5662  }
5663  }
5664  }
5665  else
5666  {
5667  /* check, if we can tighten the variable's lower bound */
5668  if( !SCIPisInfinity(scip, rhs) )
5669  {
5670  SCIP_Real slack;
5671  SCIP_Real alpha;
5672 
5673  /* min activity should be valid at this point (if this is not true, then some decisions might be wrong!) */
5674  assert(consdata->validminact);
5675 
5676  /* if the minactivity is larger than the right hand side by feasibility epsilon, the constraint is infeasible */
5677  if( SCIPisFeasLT(scip, rhs, QUAD_TO_DBL(consdata->minactivity)) )
5678  {
5679  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, minactivity=%.15g > rhs=%.15g\n",
5680  SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->minactivity), rhs);
5681 
5682  *cutoff = TRUE;
5683  return SCIP_OKAY;
5684  }
5685 
5686  slack = rhs - QUAD_TO_DBL(consdata->minactivity);
5687 
5688  /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5689  * it to zero
5690  */
5691  if( !SCIPisPositive(scip, slack) )
5692  slack = 0.0;
5693 
5694  alpha = val * (lb - ub);
5695  assert(!SCIPisNegative(scip, alpha));
5696 
5697  if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
5698  {
5699  SCIP_Real newlb;
5700 
5701  /* compute new lower bound */
5702  newlb = ub + slack / val;
5703 
5704  SCIP_CALL( tightenVarLb(scip, cons, pos, PROPRULE_1_RHS, newlb, lb, cutoff, nchgbds, force) );
5705 
5706  if( *cutoff )
5707  {
5708  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5709  SCIPconsGetName(cons), SCIPvarGetName(var), newlb, ub);
5710 
5711  return SCIP_OKAY;
5712  }
5713  /* collect the new lower bound which is needed for the upper bound computation */
5714  lb = SCIPvarGetLbLocal(var);
5715  }
5716  }
5717 
5718  /* check, if we can tighten the variable's upper bound */
5719  if( !SCIPisInfinity(scip, -lhs) )
5720  {
5721  SCIP_Real slack;
5722  SCIP_Real alpha;
5723 
5724  /* make sure the max activity is reliable */
5725  if( !consdata->validmaxact )
5726  {
5727  consdataRecomputeMaxactivity(scip, consdata);
5728  }
5729  assert(consdata->validmaxact);
5730 
5731  /* if the maxactivity is smaller than the left hand side by feasibility epsilon, the constraint is infeasible */
5732  if( SCIPisFeasLT(scip, QUAD_TO_DBL(consdata->maxactivity), lhs) )
5733  {
5734  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, maxactivity=%.15g < lhs=%.15g\n",
5735  SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->maxactivity), lhs);
5736 
5737  *cutoff = TRUE;
5738  return SCIP_OKAY;
5739  }
5740 
5741  slack = QUAD_TO_DBL(consdata->maxactivity) - lhs;
5742 
5743  /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
5744  * it to zero
5745  */
5746  if( !SCIPisPositive(scip, slack) )
5747  slack = 0.0;
5748 
5749  alpha = val * (lb - ub);
5750  assert(!SCIPisNegative(scip, alpha));
5751 
5752  if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
5753  {
5754  SCIP_Real newub;
5755 
5756  /* compute new upper bound */
5757  newub = lb - (slack / val);
5758 
5759  SCIP_CALL( tightenVarUb(scip, cons, pos, PROPRULE_1_LHS, newub, ub, cutoff, nchgbds, force) );
5760 
5761  if( *cutoff )
5762  {
5763  SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5764  SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);
5765 
5766  return SCIP_OKAY;
5767  }
5768  }
5769  }
5770  }
5771 
5772  return SCIP_OKAY;
5773 }
5774 
5775 /** analyzes conflicting bounds on given ranged row constraint, and adds conflict constraint to problem */
5776 static
5778  SCIP* scip, /**< SCIP data structure */
5779  SCIP_CONS* cons, /**< conflict detecting constraint */
5780  SCIP_VAR** vars, /**< variables reasoning the infeasibility */
5781  int nvars, /**< number of variables reasoning the infeasibility */
5782  SCIP_VAR* var, /**< variable which was tried to fix/tighten, or NULL */
5783  SCIP_Real bound /**< bound of variable which was tried to apply, or SCIP_INVALID */
5784  )
5785 {
5786 #ifndef NDEBUG
5787  SCIP_CONSDATA* consdata;
5788 
5789  assert(scip != NULL);
5790  assert(cons != NULL);
5791 
5792  consdata = SCIPconsGetData(cons);
5793  assert(consdata != NULL);
5794  assert(!SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs));
5795 #endif
5797  /* conflict analysis can only be applied in solving stage and if it is turned on */
5799  return SCIP_OKAY;
5800 
5801  /* initialize conflict analysis */
5803 
5804  /* add the conflicting fixed variables of this ranged row constraint to conflict candidate queue */
5805  SCIP_CALL( addConflictFixedVars(scip, cons, NULL, NULL, -1) );
5806 
5807  /* add reasoning variables to conflict candidate queue which led to the conflict */
5808  SCIP_CALL( addConflictReasonVars(scip, vars, nvars, var, bound) );
5809 
5810  /* analyze the conflict */
5811  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
5812 
5813  return SCIP_OKAY;
5814 }
5815 
5816 /** propagate ranged rows
5817  *
5818  * Check ranged rows for possible solutions, possibly detect infeasibility, fix variables due to having only one possible
5819  * solution, tighten bounds if having only two possible solutions or add constraints which propagate a subset of
5820  * variables better.
5821  *
5822  * Example:
5823  * c1: 12 x1 + 9 x2 - x3 = 0 with x1, x2 free and 1 <= x3 <= 2
5824  *
5825  * x3 needs to be a multiple of 3, so the instance is infeasible.
5826  *
5827  * Example:
5828  * c1: 12 x1 + 9 x2 - x3 = 1 with x1, x2 free and 1 <= x3 <= 2
5829  *
5830  * The only possible value for x3 is 2, so the variable will be fixed.
5831  *
5832  * @todo add holes if possible
5833  */
5834 static
5836  SCIP* scip, /**< SCIP data structure */
5837  SCIP_CONS* cons, /**< linear constraint */
5838  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
5839  int* nfixedvars, /**< pointer to count number of fixed variables */
5840  int* nchgbds, /**< pointer to count the number of bound changes */
5841  int* naddconss /**< pointer to count number of added constraints */
5842  )
5843 {
5844  SCIP_CONSHDLRDATA* conshdlrdata;
5845  SCIP_CONSHDLR* conshdlr;
5846  SCIP_CONSDATA* consdata;
5847  SCIP_VAR** infcheckvars;
5848  SCIP_Real* infcheckvals;
5849  SCIP_Real minactinfvars;
5850  SCIP_Real maxactinfvars;
5851  SCIP_Real lb;
5852  SCIP_Real ub;
5853  SCIP_Real feastol;
5854  SCIP_Real fixedact;
5855  SCIP_Real lhs;
5856  SCIP_Real rhs;
5857  SCIP_Real absminbincoef;
5858  SCIP_Longint gcd;
5859  SCIP_Longint gcdtmp;
5860  SCIP_Bool minactinfvarsinvalid;
5861  SCIP_Bool maxactinfvarsinvalid;
5862  SCIP_Bool possiblegcd;
5863  SCIP_Bool gcdisone;
5864  SCIP_Bool addartconss;
5865  int ninfcheckvars;
5866  int nunfixedvars;
5867  int nfixedconsvars;
5868  int ncontvars;
5869  int pos;
5870  int v;
5871 
5872  assert(scip != NULL);
5873  assert(cons != NULL);
5874  assert(cutoff != NULL);
5875  assert(nfixedvars != NULL);
5876  assert(nchgbds != NULL);
5877  assert(naddconss != NULL);
5878 
5879  /* modifiable constraint can be changed so we do not have all necessary information */
5880  if( SCIPconsIsModifiable(cons) )
5881  return SCIP_OKAY;
5882 
5883  consdata = SCIPconsGetData(cons);
5884  assert(consdata != NULL);
5885 
5886  /* we already did full ranged row propagation */
5887  if( consdata->rangedrowpropagated == 2 )
5888  return SCIP_OKAY;
5889 
5890  /* at least three variables are needed */
5891  if( consdata->nvars < 3 )
5892  return SCIP_OKAY;
5893 
5894  /* do nothing on normal inequalities */
5895  if( SCIPisInfinity(scip, -consdata->lhs) || SCIPisInfinity(scip, consdata->rhs) )
5896  return SCIP_OKAY;
5897 
5898  /* get constraint handler data */
5899  conshdlr = SCIPconsGetHdlr(cons);
5900  assert(conshdlr != NULL);
5901  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5902  assert(conshdlrdata != NULL);
5903 
5904  addartconss = conshdlrdata->rangedrowartcons && SCIPgetDepth(scip) < 1 && !SCIPinProbing(scip) && !SCIPinRepropagation(scip);
5905 
5906  /* we may add artificial constraints */
5907  if( addartconss )
5908  consdata->rangedrowpropagated = 2;
5909  /* we are not allowed to add artificial constraints during propagation; if nothing changed on this constraint since
5910  * the last rangedrowpropagation, we can stop; otherwise, we mark this constraint to be rangedrowpropagated without
5911  * artificial constraints
5912  */
5913  else
5914  {
5915  if( consdata->rangedrowpropagated > 0 )
5916  return SCIP_OKAY;
5917 
5918  consdata->rangedrowpropagated = 1;
5919  }
5920  fixedact = 0;
5921  nfixedconsvars = 0;
5922  /* calculate fixed activity and number of fixed variables */
5923  for( v = consdata->nvars - 1; v >= 0; --v )
5924  {
5925  /* all zero coefficients should be eliminated */
5926  assert(!SCIPisZero(scip, consdata->vals[v]));
5927 
5928  if( SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->vars[v]), SCIPvarGetUbLocal(consdata->vars[v])) )
5929  {
5930  fixedact += SCIPvarGetLbLocal(consdata->vars[v]) * consdata->vals[v];
5931  ++nfixedconsvars;
5932  }
5933  }
5934 
5935  /* do not work with huge fixed activities */
5936  if( SCIPisHugeValue(scip, REALABS(fixedact)) )
5937  return SCIP_OKAY;
5938 
5939  /* compute lhs and rhs for unfixed variables only and get number of unfixed variables */
5940  assert(!SCIPisInfinity(scip, -fixedact) && !SCIPisInfinity(scip, fixedact));
5941  lhs = consdata->lhs - fixedact;
5942  rhs = consdata->rhs - fixedact;
5943  nunfixedvars = consdata->nvars - nfixedconsvars;
5944 
5945  /* allocate temporary memory for variables and coefficients which may lead to infeasibility */