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
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"
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? */
109
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
112
113#define EVENTHDLR_NAME "linear"
114#define EVENTHDLR_DESC "bound change event handler for linear constraints"
115
116#define CONFLICTHDLR_NAME "linear"
117#define CONFLICTHDLR_DESC "conflict handler creating linear constraints"
118#define CONFLICTHDLR_PRIORITY -1000000
119
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 */
175
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 */
178
179
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 */
188struct 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 */
270struct 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 */
278struct 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 */
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
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 */
355typedef enum Proprule PROPRULE;
356
357/** inference information */
358struct 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};
370typedef struct InferInfo INFERINFO;
371
372/** converts an integer into an inference information */
373static
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 */
386static
388 INFERINFO inferinfo /**< inference information to convert */
389 )
390{
391 return inferinfo.val.asint;
392}
393
394/** returns the propagation rule stored in the inference information */
395static
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 */
404static
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 */
413static
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));
424
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 */
432static
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 */
447static
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);
467
468 return SCIP_OKAY;
469}
470
471/** ensures, that vars and vals arrays can store at least num entries */
472static
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 */
507static
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 */
528static
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 */
542static
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 */
566static
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}
586
587/** creates a linear constraint upgrade data object */
588static
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 */
618static
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 */
650static
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( val < 0.0 )
669 {
670 SCIP_CALL( SCIPlockVarCons(scip, var, cons,
671 !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
672 }
673 else
674 {
675 SCIP_CALL( SCIPlockVarCons(scip, var, cons,
676 !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
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 */
683static
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( val < 0.0 )
702 {
703 SCIP_CALL( SCIPunlockVarCons(scip, var, cons,
704 !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
705 }
706 else
707 {
708 SCIP_CALL( SCIPunlockVarCons(scip, var, cons,
709 !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
710 }
711
712 return SCIP_OKAY;
713}
714
715/** creates event data for variable at given position, and catches events */
716/**! [SnippetDebugAssertions] */
717static
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 */
756static
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 */
790static
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 */
822static
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 */
853static
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 SCIP_VAR** varsbuffer;
902 SCIP_Real* valsbuffer;
903
904 /* copy variables into temporary buffer */
905 SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) );
906 SCIP_CALL( SCIPallocBufferArray(scip, &valsbuffer, nvars) );
907 nvars = 0;
908
909 /* loop over variables and sort out fixed ones */
910 for( v = 0; v < (*consdata)->nvars; ++v )
911 {
912 SCIP_VAR* var;
913 SCIP_Real val;
914
915 var = vars[v];
916 val = vals[v];
917
918 assert(var != NULL);
919 if( !SCIPisZero(scip, val) )
920 {
921 /* treat fixed variable as a constant if problem compression is enabled */
923 {
924 constant += SCIPvarGetLbGlobal(var) * val;
925 }
926 else
927 {
928 varsbuffer[nvars] = var;
929 valsbuffer[nvars] = val;
930 ++nvars;
931
932 /* update hascontvar and hasnonbinvar flags */
933 if( !(*consdata)->hascontvar )
934 {
935 SCIP_VARTYPE vartype = SCIPvarGetType(var);
936
937 if( vartype != SCIP_VARTYPE_BINARY )
938 {
939 (*consdata)->hasnonbinvar = TRUE;
940
941 if( vartype == SCIP_VARTYPE_CONTINUOUS )
942 (*consdata)->hascontvar = TRUE;
943 }
944 }
945 }
946 }
947 }
948 (*consdata)->nvars = nvars;
949
950 if( nvars > 0 )
951 {
952 /* copy the possibly reduced buffer arrays into block */
953 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, nvars) );
954 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vals, valsbuffer, nvars) );
955 (*consdata)->varssize = nvars;
956 }
957 /* free temporary buffer */
958 SCIPfreeBufferArray(scip, &valsbuffer);
959 SCIPfreeBufferArray(scip, &varsbuffer);
960 }
961
962 (*consdata)->eventdata = NULL;
963
964 /* due to compressed copying, we may have fixed variables contributing to the left and right hand side */
965 if( !SCIPisZero(scip, constant) )
966 {
967 if( !SCIPisInfinity(scip, REALABS(lhs)) )
968 lhs -= constant;
969
970 if( !SCIPisInfinity(scip, REALABS(rhs)) )
971 rhs -= constant;
972 }
973
974 (*consdata)->row = NULL;
975 (*consdata)->nlrow = NULL;
976 (*consdata)->lhs = lhs;
977 (*consdata)->rhs = rhs;
978 (*consdata)->maxabsval = SCIP_INVALID;
979 (*consdata)->minabsval = SCIP_INVALID;
980 QUAD_ASSIGN((*consdata)->minactivity, SCIP_INVALID);
981 QUAD_ASSIGN((*consdata)->maxactivity, SCIP_INVALID);
982 (*consdata)->lastminactivity = SCIP_INVALID;
983 (*consdata)->lastmaxactivity = SCIP_INVALID;
984 (*consdata)->maxactdelta = SCIP_INVALID;
985 (*consdata)->maxactdeltavar = NULL;
986 (*consdata)->minactivityneginf = -1;
987 (*consdata)->minactivityposinf = -1;
988 (*consdata)->maxactivityneginf = -1;
989 (*consdata)->maxactivityposinf = -1;
990 (*consdata)->minactivityneghuge = -1;
991 (*consdata)->minactivityposhuge = -1;
992 (*consdata)->maxactivityneghuge = -1;
993 (*consdata)->maxactivityposhuge = -1;
994 QUAD_ASSIGN((*consdata)->glbminactivity, SCIP_INVALID);
995 QUAD_ASSIGN((*consdata)->glbmaxactivity, SCIP_INVALID);
996 (*consdata)->lastglbminactivity = SCIP_INVALID;
997 (*consdata)->lastglbmaxactivity = SCIP_INVALID;
998 (*consdata)->glbminactivityneginf = -1;
999 (*consdata)->glbminactivityposinf = -1;
1000 (*consdata)->glbmaxactivityneginf = -1;
1001 (*consdata)->glbmaxactivityposinf = -1;
1002 (*consdata)->glbminactivityneghuge = -1;
1003 (*consdata)->glbminactivityposhuge = -1;
1004 (*consdata)->glbmaxactivityneghuge = -1;
1005 (*consdata)->glbmaxactivityposhuge = -1;
1006 (*consdata)->possignature = 0;
1007 (*consdata)->negsignature = 0;
1008 (*consdata)->validmaxabsval = FALSE;
1009 (*consdata)->validminabsval = FALSE;
1010 (*consdata)->validactivities = FALSE;
1011 (*consdata)->validminact = FALSE;
1012 (*consdata)->validmaxact = FALSE;
1013 (*consdata)->validglbminact = FALSE;
1014 (*consdata)->validglbmaxact = FALSE;
1015 (*consdata)->boundstightened = 0;
1016 (*consdata)->presolved = FALSE;
1017 (*consdata)->removedfixings = FALSE;
1018 (*consdata)->validsignature = FALSE;
1019 (*consdata)->changed = TRUE;
1020 (*consdata)->normalized = FALSE;
1021 (*consdata)->upgradetried = FALSE;
1022 (*consdata)->upgraded = FALSE;
1023 (*consdata)->indexsorted = (nvars <= 1);
1024 (*consdata)->merged = (nvars <= 1);
1025 (*consdata)->cliquesadded = FALSE;
1026 (*consdata)->implsadded = FALSE;
1027 (*consdata)->coefsorted = FALSE;
1028 (*consdata)->nbinvars = -1;
1029 (*consdata)->varsdeleted = FALSE;
1030 (*consdata)->rangedrowpropagated = 0;
1031 (*consdata)->checkabsolute = FALSE;
1032
1033 if( SCIPisTransformed(scip) )
1034 {
1035 /* get transformed variables */
1036 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
1037 }
1038
1039 /* capture variables */
1040 for( v = 0; v < (*consdata)->nvars; v++ )
1041 {
1042 /* likely implies a deleted variable */
1043 if( (*consdata)->vars[v] == NULL )
1044 {
1045 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
1046 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vals, (*consdata)->varssize);
1047 SCIPfreeBlockMemory(scip, consdata);
1048 return SCIP_INVALIDDATA;
1049 }
1050
1051 assert(!SCIPisZero(scip, (*consdata)->vals[v]));
1052 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
1053 }
1054
1055 return SCIP_OKAY;
1056}
1057
1058/** frees a linear constraint data */
1059static
1061 SCIP* scip, /**< SCIP data structure */
1062 SCIP_CONSDATA** consdata /**< pointer to linear constraint data */
1063 )
1064{
1065 int v;
1066
1067 assert(scip != NULL);
1068 assert(consdata != NULL);
1069 assert(*consdata != NULL);
1070 assert((*consdata)->varssize >= 0);
1071
1072 /* release the row */
1073 if( (*consdata)->row != NULL )
1074 {
1075 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
1076 }
1077
1078 /* release the nlrow */
1079 if( (*consdata)->nlrow != NULL )
1080 {
1081 SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow) );
1082 }
1083
1084 /* release variables */
1085 for( v = 0; v < (*consdata)->nvars; v++ )
1086 {
1087 assert((*consdata)->vars[v] != NULL);
1088 assert(!SCIPisZero(scip, (*consdata)->vals[v]));
1089 SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
1090 }
1091
1092 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
1093 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vals, (*consdata)->varssize);
1094 SCIPfreeBlockMemory(scip, consdata);
1095
1096 return SCIP_OKAY;
1097}
1098
1099/** prints linear constraint in CIP format to file stream */
1100static
1102 SCIP* scip, /**< SCIP data structure */
1103 SCIP_CONSDATA* consdata, /**< linear constraint data */
1104 FILE* file /**< output file (or NULL for standard output) */
1105 )
1106{
1107 assert(scip != NULL);
1108 assert(consdata != NULL);
1109
1110 /* print left hand side for ranged rows */
1111 if( !SCIPisInfinity(scip, -consdata->lhs)
1112 && !SCIPisInfinity(scip, consdata->rhs)
1113 && !SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
1114 SCIPinfoMessage(scip, file, "%.15g <= ", consdata->lhs);
1115
1116 /* print coefficients and variables */
1117 if( consdata->nvars == 0 )
1118 SCIPinfoMessage(scip, file, "0");
1119 else
1120 {
1121 /* post linear sum of the linear constraint */
1122 SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, consdata->vars, consdata->vals, consdata->nvars, TRUE) );
1123 }
1124
1125 /* print right hand side */
1126 if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
1127 SCIPinfoMessage(scip, file, " == %.15g", consdata->rhs);
1128 else if( !SCIPisInfinity(scip, consdata->rhs) )
1129 SCIPinfoMessage(scip, file, " <= %.15g", consdata->rhs);
1130 else if( !SCIPisInfinity(scip, -consdata->lhs) )
1131 SCIPinfoMessage(scip, file, " >= %.15g", consdata->lhs);
1132 else
1133 SCIPinfoMessage(scip, file, " [free]");
1134
1135 return SCIP_OKAY;
1136}
1137
1138/** prints linear constraint and contained solution values of variables to file stream */
1139static
1141 SCIP* scip, /**< SCIP data structure */
1142 SCIP_CONS* cons, /**< linear constraint */
1143 SCIP_SOL* sol, /**< solution to print */
1144 FILE* file /**< output file (or NULL for standard output) */
1145 )
1146{
1147 SCIP_CONSDATA* consdata;
1148
1149 assert(scip != NULL);
1150 assert(cons != NULL);
1151
1152 consdata = SCIPconsGetData(cons);
1153 assert(consdata != NULL);
1154
1156
1157 /* print left hand side for ranged rows */
1158 if( !SCIPisInfinity(scip, -consdata->lhs)
1159 && !SCIPisInfinity(scip, consdata->rhs)
1160 && !SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
1161 SCIPinfoMessage(scip, file, "%.15g <= ", consdata->lhs);
1162
1163 /* print coefficients and variables */
1164 if( consdata->nvars == 0 )
1165 SCIPinfoMessage(scip, file, "0");
1166 else
1167 {
1168 int v;
1169
1170 /* post linear sum of the linear constraint */
1171 for( v = 0; v < consdata->nvars; ++v )
1172 {
1173 if( consdata->vals != NULL )
1174 {
1175 if( consdata->vals[v] == 1.0 )
1176 {
1177 if( v > 0 )
1178 SCIPinfoMessage(scip, file, " +");
1179 }
1180 else if( consdata->vals[v] == -1.0 )
1181 SCIPinfoMessage(scip, file, " -");
1182 else
1183 SCIPinfoMessage(scip, file, " %+.9g", consdata->vals[v]);
1184 }
1185 else if( consdata->nvars > 0 )
1186 SCIPinfoMessage(scip, file, " +");
1187
1188 /* print variable name */
1189 SCIP_CALL( SCIPwriteVarName(scip, file, consdata->vars[v], TRUE) );
1190
1191 SCIPinfoMessage(scip, file, " (%+.9g)", SCIPgetSolVal(scip, sol, consdata->vars[v]));
1192 }
1193 }
1194
1195 /* print right hand side */
1196 if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
1197 SCIPinfoMessage(scip, file, " == %.15g", consdata->rhs);
1198 else if( !SCIPisInfinity(scip, consdata->rhs) )
1199 SCIPinfoMessage(scip, file, " <= %.15g", consdata->rhs);
1200 else if( !SCIPisInfinity(scip, -consdata->lhs) )
1201 SCIPinfoMessage(scip, file, " >= %.15g", consdata->lhs);
1202 else
1203 SCIPinfoMessage(scip, file, " [free]");
1204
1205 SCIPinfoMessage(scip, file, ";\n");
1206
1207 return SCIP_OKAY;
1208}
1209
1210/** invalidates activity bounds, such that they are recalculated in next get */
1211static
1213 SCIP_CONSDATA* consdata /**< linear constraint */
1214 )
1215{
1216 assert(consdata != NULL);
1217
1218 consdata->validactivities = FALSE;
1219 consdata->validminact = FALSE;
1220 consdata->validmaxact = FALSE;
1221 consdata->validglbminact = FALSE;
1222 consdata->validglbmaxact = FALSE;
1223 consdata->validmaxabsval = FALSE;
1224 consdata->validminabsval = FALSE;
1225 consdata->hasnonbinvalid = FALSE;
1226 QUAD_ASSIGN(consdata->minactivity, SCIP_INVALID);
1227 QUAD_ASSIGN(consdata->maxactivity, SCIP_INVALID);
1228 consdata->lastminactivity = SCIP_INVALID;
1229 consdata->lastmaxactivity = SCIP_INVALID;
1230 consdata->maxabsval = SCIP_INVALID;
1231 consdata->minabsval = SCIP_INVALID;
1232 consdata->maxactdelta = SCIP_INVALID;
1233 consdata->maxactdeltavar = NULL;
1234 consdata->minactivityneginf = -1;
1235 consdata->minactivityposinf = -1;
1236 consdata->maxactivityneginf = -1;
1237 consdata->maxactivityposinf = -1;
1238 consdata->minactivityneghuge = -1;
1239 consdata->minactivityposhuge = -1;
1240 consdata->maxactivityneghuge = -1;
1241 consdata->maxactivityposhuge = -1;
1242 QUAD_ASSIGN(consdata->glbminactivity, SCIP_INVALID);
1243 QUAD_ASSIGN(consdata->glbmaxactivity, SCIP_INVALID);
1244 consdata->lastglbminactivity = SCIP_INVALID;
1245 consdata->lastglbmaxactivity = SCIP_INVALID;
1246 consdata->glbminactivityneginf = -1;
1247 consdata->glbminactivityposinf = -1;
1248 consdata->glbmaxactivityneginf = -1;
1249 consdata->glbmaxactivityposinf = -1;
1250 consdata->glbminactivityneghuge = -1;
1251 consdata->glbminactivityposhuge = -1;
1252 consdata->glbmaxactivityneghuge = -1;
1253 consdata->glbmaxactivityposhuge = -1;
1254}
1255
1256/** compute the pseudo activity of a constraint */
1257static
1259 SCIP* scip, /**< SCIP data structure */
1260 SCIP_CONSDATA* consdata /**< linear constraint data */
1261 )
1262{
1263 int i;
1264 int pseudoactivityposinf;
1265 int pseudoactivityneginf;
1266 SCIP_Real pseudoactivity;
1268 SCIP_Real val;
1269
1270 pseudoactivity = 0;
1271 pseudoactivityposinf = 0;
1272 pseudoactivityneginf = 0;
1273
1274 for( i = consdata->nvars - 1; i >= 0; --i )
1275 {
1276 val = consdata->vals[i];
1277 bound = (SCIPvarGetBestBoundType(consdata->vars[i]) == SCIP_BOUNDTYPE_LOWER) ? SCIPvarGetLbLocal(consdata->vars[i]) : SCIPvarGetUbLocal(consdata->vars[i]);
1278 if( SCIPisInfinity(scip, bound) )
1279 {
1280 if( val > 0.0 )
1281 pseudoactivityposinf++;
1282 else
1283 pseudoactivityneginf++;
1284 }
1285 else
1286 {
1287 if( SCIPisInfinity(scip, -bound) )
1288 {
1289 if( val > 0.0 )
1290 pseudoactivityneginf++;
1291 else
1292 pseudoactivityposinf++;
1293 }
1294 else
1295 pseudoactivity += val * bound;
1296 }
1297 }
1298
1299 if( pseudoactivityneginf > 0 && pseudoactivityposinf > 0 )
1300 return SCIP_INVALID;
1301 else if( pseudoactivityneginf > 0 )
1302 return -SCIPinfinity(scip);
1303 else if( pseudoactivityposinf > 0 )
1304 return SCIPinfinity(scip);
1305
1306 return pseudoactivity;
1307}
1308
1309/** recompute the minactivity of a constraint */
1310static
1312 SCIP* scip, /**< SCIP data structure */
1313 SCIP_CONSDATA* consdata /**< linear constraint data */
1314 )
1315{
1316 int i;
1318
1319 QUAD_ASSIGN(consdata->minactivity, 0.0);
1320
1321 for( i = consdata->nvars - 1; i >= 0; --i )
1322 {
1323 bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetLbLocal(consdata->vars[i]) : SCIPvarGetUbLocal(consdata->vars[i]);
1325 && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1326 SCIPquadprecSumQD(consdata->minactivity, consdata->minactivity, consdata->vals[i] * bound);
1327 }
1328
1329 /* the activity was just computed from scratch and is valid now */
1330 consdata->validminact = TRUE;
1331
1332 /* the activity was just computed from scratch, mark it to be reliable */
1333 consdata->lastminactivity = QUAD_TO_DBL(consdata->minactivity);
1334}
1335
1336/** recompute the maxactivity of a constraint */
1337static
1339 SCIP* scip, /**< SCIP data structure */
1340 SCIP_CONSDATA* consdata /**< linear constraint data */
1341 )
1342{
1343 int i;
1345
1346 QUAD_ASSIGN(consdata->maxactivity, 0.0);
1347
1348 for( i = consdata->nvars - 1; i >= 0; --i )
1349 {
1350 bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetUbLocal(consdata->vars[i]) : SCIPvarGetLbLocal(consdata->vars[i]);
1352 && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1353 SCIPquadprecSumQD(consdata->maxactivity, consdata->maxactivity, consdata->vals[i] * bound);
1354 }
1355
1356 /* the activity was just computed from scratch and is valid now */
1357 consdata->validmaxact = TRUE;
1358
1359 /* the activity was just computed from scratch, mark it to be reliable */
1360 consdata->lastmaxactivity = QUAD_TO_DBL(consdata->maxactivity);
1361}
1362
1363/** recompute the global minactivity of a constraint */
1364static
1366 SCIP* scip, /**< SCIP data structure */
1367 SCIP_CONSDATA* consdata /**< linear constraint data */
1368 )
1369{
1370 int i;
1372
1373 QUAD_ASSIGN(consdata->glbminactivity, 0.0);
1374
1375 for( i = consdata->nvars - 1; i >= 0; --i )
1376 {
1377 bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetLbGlobal(consdata->vars[i]) : SCIPvarGetUbGlobal(consdata->vars[i]);
1379 && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1380 SCIPquadprecSumQD(consdata->glbminactivity, consdata->glbminactivity, consdata->vals[i] * bound);
1381 }
1382
1383 /* the activity was just computed from scratch and is valid now */
1384 consdata->validglbminact = TRUE;
1385
1386 /* the activity was just computed from scratch, mark it to be reliable */
1387 consdata->lastglbminactivity = QUAD_TO_DBL(consdata->glbminactivity);
1388}
1389
1390/** recompute the global maxactivity of a constraint */
1391static
1393 SCIP* scip, /**< SCIP data structure */
1394 SCIP_CONSDATA* consdata /**< linear constraint data */
1395 )
1396{
1397 int i;
1399
1400 QUAD_ASSIGN(consdata->glbmaxactivity, 0.0);
1401
1402 for( i = consdata->nvars - 1; i >= 0; --i )
1403 {
1404 bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetUbGlobal(consdata->vars[i]) : SCIPvarGetLbGlobal(consdata->vars[i]);
1406 && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
1407 SCIPquadprecSumQD(consdata->glbmaxactivity, consdata->glbmaxactivity, consdata->vals[i] * bound);
1408 }
1409
1410 /* the activity was just computed from scratch and is valid now */
1411 consdata->validglbmaxact = TRUE;
1412
1413 /* the activity was just computed from scratch, mark it to be reliable */
1414 consdata->lastglbmaxactivity = QUAD_TO_DBL(consdata->glbmaxactivity);
1415}
1416
1417/** calculates maximum absolute value of coefficients */
1418static
1420 SCIP_CONSDATA* consdata /**< linear constraint data */
1421 )
1422{
1423 SCIP_Real absval;
1424 int i;
1425
1426 assert(consdata != NULL);
1427 assert(!consdata->validmaxabsval);
1428 assert(consdata->maxabsval >= SCIP_INVALID);
1429
1430 consdata->validmaxabsval = TRUE;
1431 consdata->maxabsval = 0.0;
1432 for( i = 0; i < consdata->nvars; ++i )
1433 {
1434 absval = consdata->vals[i];
1435 absval = REALABS(absval);
1436 if( absval > consdata->maxabsval )
1437 consdata->maxabsval = absval;
1438 }
1439}
1440
1441/** calculates minimum absolute value of coefficients */
1442static
1444 SCIP_CONSDATA* consdata /**< linear constraint data */
1445 )
1446{
1447 SCIP_Real absval;
1448 int i;
1449
1450 assert(consdata != NULL);
1451 assert(!consdata->validminabsval);
1452 assert(consdata->minabsval >= SCIP_INVALID);
1453
1454 consdata->validminabsval = TRUE;
1455
1456 if( consdata->nvars > 0 )
1457 consdata->minabsval = REALABS(consdata->vals[0]);
1458 else
1459 consdata->minabsval = 0.0;
1460
1461 for( i = 1; i < consdata->nvars; ++i )
1462 {
1463 absval = consdata->vals[i];
1464 absval = REALABS(absval);
1465 if( absval < consdata->minabsval )
1466 consdata->minabsval = absval;
1467 }
1468}
1469
1470/** checks the type of all variables of the constraint and sets hasnonbinvar and hascontvar flags accordingly */
1471static
1473 SCIP_CONSDATA* consdata /**< linear constraint data */
1474 )
1475{
1476 int v;
1477
1478 assert(!consdata->hasnonbinvalid);
1479 consdata->hasnonbinvar = FALSE;
1480 consdata->hascontvar = FALSE;
1481
1482 for( v = consdata->nvars - 1; v >= 0; --v )
1483 {
1484 SCIP_VARTYPE vartype = SCIPvarGetType(consdata->vars[v]);
1485
1486 if( vartype != SCIP_VARTYPE_BINARY )
1487 {
1488 consdata->hasnonbinvar = TRUE;
1489
1490 if( vartype == SCIP_VARTYPE_CONTINUOUS )
1491 {
1492 consdata->hascontvar = TRUE;
1493 break;
1494 }
1495 }
1496 }
1497 assert(consdata->hascontvar || v < 0);
1498
1499 consdata->hasnonbinvalid = TRUE;
1500}
1501
1502
1503#ifdef CHECKMAXACTDELTA
1504/** checks that the stored maximal activity delta (if not invalid) is correct */
1505static
1507 SCIP* scip, /**< SCIP data structure */
1508 SCIP_CONSDATA* consdata /**< linear constraint data */
1509 )
1510{
1511 if( consdata->maxactdelta != SCIP_INVALID )
1512 {
1513 SCIP_Real maxactdelta = 0.0;
1514 SCIP_Real domain;
1515 SCIP_Real delta;
1516 SCIP_Real lb;
1517 SCIP_Real ub;
1518 int v;
1519
1520 for( v = consdata->nvars - 1; v >= 0; --v )
1521 {
1522 lb = SCIPvarGetLbLocal(consdata->vars[v]);
1523 ub = SCIPvarGetUbLocal(consdata->vars[v]);
1524
1525 if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
1526 {
1527 maxactdelta = SCIPinfinity(scip);
1528 break;
1529 }
1530
1531 domain = ub - lb;
1532 delta = REALABS(consdata->vals[v]) * domain;
1533
1534 if( delta > maxactdelta )
1535 {
1536 maxactdelta = delta;
1537 }
1538 }
1539 assert(SCIPisFeasEQ(scip, maxactdelta, consdata->maxactdelta));
1540 }
1541}
1542#else
1543#define checkMaxActivityDelta(scip, consdata) /**/
1544#endif
1545
1546/** recompute maximal activity contribution for a single variable */
1547static
1549 SCIP* scip, /**< SCIP data structure */
1550 SCIP_CONSDATA* consdata /**< linear constraint data */
1551 )
1552{
1553 SCIP_Real delta;
1554 int v;
1555
1556 consdata->maxactdelta = 0.0;
1557
1558 if( !consdata->hasnonbinvalid )
1559 consdataCheckNonbinvar(consdata);
1560
1561 /* easy case, the problem consists only of binary variables */
1562 if( !consdata->hasnonbinvar )
1563 {
1564 for( v = consdata->nvars - 1; v >= 0; --v )
1565 {
1566 if( SCIPvarGetLbLocal(consdata->vars[v]) < 0.5 && SCIPvarGetUbLocal(consdata->vars[v]) > 0.5 )
1567 {
1568 delta = REALABS(consdata->vals[v]);
1569
1570 if( delta > consdata->maxactdelta )
1571 {
1572 consdata->maxactdelta = delta;
1573 consdata->maxactdeltavar = consdata->vars[v];
1574 }
1575 }
1576 }
1577 return;
1578 }
1579
1580 for( v = consdata->nvars - 1; v >= 0; --v )
1581 {
1582 SCIP_Real domain;
1583 SCIP_Real lb;
1584 SCIP_Real ub;
1585
1586 lb = SCIPvarGetLbLocal(consdata->vars[v]);
1587 ub = SCIPvarGetUbLocal(consdata->vars[v]);
1588
1589 if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
1590 {
1591 consdata->maxactdelta = SCIPinfinity(scip);
1592 consdata->maxactdeltavar = consdata->vars[v];
1593 break;
1594 }
1595
1596 domain = ub - lb;
1597 delta = REALABS(consdata->vals[v]) * domain;
1598
1599 if( delta > consdata->maxactdelta )
1600 {
1601 consdata->maxactdelta = delta;
1602 consdata->maxactdeltavar = consdata->vars[v];
1603 }
1604 }
1605}
1606
1607
1608/** updates activities for a change in a bound */
1609static
1611 SCIP* scip, /**< SCIP data structure */
1612 SCIP_CONSDATA* consdata, /**< linear constraint data */
1613 SCIP_VAR* var, /**< variable that has been changed; can be NULL for global bound changes */
1614 SCIP_Real oldbound, /**< old bound of variable */
1615 SCIP_Real newbound, /**< new bound of variable */
1616 SCIP_Real val, /**< coefficient of constraint entry */
1617 SCIP_BOUNDTYPE boundtype, /**< type of the bound change */
1618 SCIP_Bool global, /**< is it a global or a local bound change? */
1619 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
1620 )
1621{
1622 QUAD_MEMBER(SCIP_Real* activity);
1623 QUAD_MEMBER(SCIP_Real delta);
1624 SCIP_Real* lastactivity;
1625 int* activityposinf;
1626 int* activityneginf;
1627 int* activityposhuge;
1628 int* activityneghuge;
1629 SCIP_Real oldcontribution;
1630 SCIP_Real newcontribution;
1631 SCIP_Bool validact;
1632 SCIP_Bool finitenewbound;
1633 SCIP_Bool hugevalnewcont;
1634
1635 assert(scip != NULL);
1636 assert(consdata != NULL);
1637 assert(global || (var != NULL));
1638 assert(consdata->validactivities);
1639 assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
1640 assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
1641 assert(consdata->lastminactivity < SCIP_INVALID);
1642 assert(consdata->lastmaxactivity < SCIP_INVALID);
1643 assert(consdata->minactivityneginf >= 0);
1644 assert(consdata->minactivityposinf >= 0);
1645 assert(consdata->maxactivityneginf >= 0);
1646 assert(consdata->maxactivityposinf >= 0);
1647 assert(consdata->minactivityneghuge >= 0);
1648 assert(consdata->minactivityposhuge >= 0);
1649 assert(consdata->maxactivityneghuge >= 0);
1650 assert(consdata->maxactivityposhuge >= 0);
1651 assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
1652 assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
1653 assert(consdata->lastglbminactivity < SCIP_INVALID);
1654 assert(consdata->lastglbmaxactivity < SCIP_INVALID);
1655 assert(consdata->glbminactivityneginf >= 0);
1656 assert(consdata->glbminactivityposinf >= 0);
1657 assert(consdata->glbmaxactivityneginf >= 0);
1658 assert(consdata->glbmaxactivityposinf >= 0);
1659 assert(consdata->glbminactivityneghuge >= 0);
1660 assert(consdata->glbminactivityposhuge >= 0);
1661 assert(consdata->glbmaxactivityneghuge >= 0);
1662 assert(consdata->glbmaxactivityposhuge >= 0);
1663
1664 QUAD_ASSIGN(delta, 0.0);
1665
1666 /* we are updating global activities */
1667 if( global )
1668 {
1669 /* depending on the boundtype and the coefficient, we choose the activity to be updated:
1670 * lower bound + pos. coef: update minactivity
1671 * lower bound + neg. coef: update maxactivity, positive and negative infinity counters have to be switched
1672 * upper bound + pos. coef: update maxactivity
1673 * upper bound + neg. coef: update minactivity, positive and negative infinity counters have to be switched
1674 */
1675 if( boundtype == SCIP_BOUNDTYPE_LOWER )
1676 {
1677 if( val > 0.0 )
1678 {
1679 QUAD_ASSIGN_Q(activity, &consdata->glbminactivity);
1680 lastactivity = &(consdata->lastglbminactivity);
1681 activityposinf = &(consdata->glbminactivityposinf);
1682 activityneginf = &(consdata->glbminactivityneginf);
1683 activityposhuge = &(consdata->glbminactivityposhuge);
1684 activityneghuge = &(consdata->glbminactivityneghuge);
1685 validact = consdata->validglbminact;
1686 }
1687 else
1688 {
1689 QUAD_ASSIGN_Q(activity, &consdata->glbmaxactivity);
1690 lastactivity = &(consdata->lastglbmaxactivity);
1691 activityposinf = &(consdata->glbmaxactivityneginf);
1692 activityneginf = &(consdata->glbmaxactivityposinf);
1693 activityposhuge = &(consdata->glbmaxactivityposhuge);
1694 activityneghuge = &(consdata->glbmaxactivityneghuge);
1695 validact = consdata->validglbmaxact;
1696 }
1697 }
1698 else
1699 {
1700 if( val > 0.0 )
1701 {
1702 QUAD_ASSIGN_Q(activity, &consdata->glbmaxactivity);
1703 lastactivity = &(consdata->lastglbmaxactivity);
1704 activityposinf = &(consdata->glbmaxactivityposinf);
1705 activityneginf = &(consdata->glbmaxactivityneginf);
1706 activityposhuge = &(consdata->glbmaxactivityposhuge);
1707 activityneghuge = &(consdata->glbmaxactivityneghuge);
1708 validact = consdata->validglbmaxact;
1709 }
1710 else
1711 {
1712 QUAD_ASSIGN_Q(activity, &consdata->glbminactivity);
1713 lastactivity = &(consdata->lastglbminactivity);
1714 activityposinf = &(consdata->glbminactivityneginf);
1715 activityneginf = &(consdata->glbminactivityposinf);
1716 activityposhuge = &(consdata->glbminactivityposhuge);
1717 activityneghuge = &(consdata->glbminactivityneghuge);
1718 validact = consdata->validglbminact;
1719 }
1720 }
1721 }
1722 /* we are updating local activities */
1723 else
1724 {
1725 /* depending on the boundtype and the coefficient, we choose the activity to be updated:
1726 * lower bound + pos. coef: update minactivity
1727 * lower bound + neg. coef: update maxactivity, positive and negative infinity counters have to be switched
1728 * upper bound + pos. coef: update maxactivity
1729 * upper bound + neg. coef: update minactivity, positive and negative infinity counters have to be switched
1730 */
1731 if( boundtype == SCIP_BOUNDTYPE_LOWER )
1732 {
1733 if( val > 0.0 )
1734 {
1735 QUAD_ASSIGN_Q(activity, &consdata->minactivity);
1736 lastactivity = &(consdata->lastminactivity);
1737 activityposinf = &(consdata->minactivityposinf);
1738 activityneginf = &(consdata->minactivityneginf);
1739 activityposhuge = &(consdata->minactivityposhuge);
1740 activityneghuge = &(consdata->minactivityneghuge);
1741 validact = consdata->validminact;
1742 }
1743 else
1744 {
1745 QUAD_ASSIGN_Q(activity, &consdata->maxactivity);
1746 lastactivity = &(consdata->lastmaxactivity);
1747 activityposinf = &(consdata->maxactivityneginf);
1748 activityneginf = &(consdata->maxactivityposinf);
1749 activityposhuge = &(consdata->maxactivityposhuge);
1750 activityneghuge = &(consdata->maxactivityneghuge);
1751 validact = consdata->validmaxact;
1752 }
1753 }
1754 else
1755 {
1756 if( val > 0.0 )
1757 {
1758 QUAD_ASSIGN_Q(activity, &consdata->maxactivity);
1759 lastactivity = &(consdata->lastmaxactivity);
1760 activityposinf = &(consdata->maxactivityposinf);
1761 activityneginf = &(consdata->maxactivityneginf);
1762 activityposhuge = &(consdata->maxactivityposhuge);
1763 activityneghuge = &(consdata->maxactivityneghuge);
1764 validact = consdata->validmaxact;
1765 }
1766 else
1767 {
1768 QUAD_ASSIGN_Q(activity, &consdata->minactivity);
1769 lastactivity = &(consdata->lastminactivity);
1770 activityposinf = &(consdata->minactivityneginf);
1771 activityneginf = &(consdata->minactivityposinf);
1772 activityposhuge = &(consdata->minactivityposhuge);
1773 activityneghuge = &(consdata->minactivityneghuge);
1774 validact = consdata->validminact;
1775 }
1776 }
1777 }
1778
1779 oldcontribution = val * oldbound;
1780 newcontribution = val * newbound;
1781 hugevalnewcont = SCIPisHugeValue(scip, REALABS(newcontribution));
1782 finitenewbound = !SCIPisInfinity(scip, REALABS(newbound));
1783
1784 if( SCIPisInfinity(scip, REALABS(oldbound)) )
1785 {
1786 /* old bound was +infinity */
1787 if( oldbound > 0.0 )
1788 {
1789 assert((*activityposinf) >= 1);
1790
1791 /* we only have to do something if the new bound is not again +infinity */
1792 if( finitenewbound || newbound < 0.0 )
1793 {
1794 /* decrease the counter for positive infinite contributions */
1795 (*activityposinf)--;
1796
1797 /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
1798 if( !finitenewbound && newbound < 0.0 )
1799 (*activityneginf)++;
1800 else if( hugevalnewcont )
1801 {
1802 /* if the contribution of this variable is too large, increase the counter for huge values */
1803 if( newcontribution > 0.0 )
1804 (*activityposhuge)++;
1805 else
1806 (*activityneghuge)++;
1807 }
1808 /* "normal case": just add the contribution to the activity */
1809 else
1810 QUAD_ASSIGN(delta, newcontribution);
1811 }
1812 }
1813 /* old bound was -infinity */
1814 else
1815 {
1816 assert(oldbound < 0.0);
1817 assert((*activityneginf) >= 1);
1818
1819 /* we only have to do something ig the new bound is not again -infinity */
1820 if( finitenewbound || newbound > 0.0 )
1821 {
1822 /* decrease the counter for negative infinite contributions */
1823 (*activityneginf)--;
1824
1825 /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
1826 if( !finitenewbound && newbound > 0.0 )
1827 (*activityposinf)++;
1828 else if( hugevalnewcont )
1829 {
1830 /* if the contribution of this variable is too large, increase the counter for huge values */
1831 if( newcontribution > 0.0 )
1832 (*activityposhuge)++;
1833 else
1834 (*activityneghuge)++;
1835 }
1836 /* "normal case": just add the contribution to the activity */
1837 else
1838 QUAD_ASSIGN(delta, newcontribution);
1839 }
1840 }
1841 }
1842 else if( SCIPisHugeValue(scip, REALABS(oldcontribution)) )
1843 {
1844 /* old contribution was too large and positive */
1845 if( oldcontribution > 0.0 )
1846 {
1847 assert((*activityposhuge) >= 1);
1848
1849 /* decrease the counter for huge positive contributions; it might be increased again later,
1850 * but checking here that the bound is not huge again would not handle a change from a huge to an infinite bound
1851 */
1852 (*activityposhuge)--;
1853
1854 if( !finitenewbound )
1855 {
1856 /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
1857 if( newbound > 0.0 )
1858 (*activityposinf)++;
1859 /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
1860 else
1861 (*activityneginf)++;
1862 }
1863 else if( hugevalnewcont )
1864 {
1865 /* if the contribution of this variable is too large and positive, increase the corresponding counter */
1866 if( newcontribution > 0.0 )
1867 (*activityposhuge)++;
1868 /* if the contribution of this variable is too large and negative, increase the corresponding counter */
1869 else
1870 (*activityneghuge)++;
1871 }
1872 /* "normal case": just add the contribution to the activity */
1873 else
1874 QUAD_ASSIGN(delta, newcontribution);
1875 }
1876 /* old contribution was too large and negative */
1877 else
1878 {
1879 assert(oldcontribution < 0.0);
1880 assert((*activityneghuge) >= 1);
1881
1882 /* decrease the counter for huge negative contributions; it might be increased again later,
1883 * but checking here that the bound is not huge again would not handle a change from a huge to an infinite bound
1884 */
1885 (*activityneghuge)--;
1886
1887 if( !finitenewbound )
1888 {
1889 /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
1890 if( newbound > 0.0 )
1891 (*activityposinf)++;
1892 /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
1893 else
1894 (*activityneginf)++;
1895 }
1896 else if( hugevalnewcont )
1897 {
1898 /* if the contribution of this variable is too large and positive, increase the corresponding counter */
1899 if( newcontribution > 0.0 )
1900 (*activityposhuge)++;
1901 /* if the contribution of this variable is too large and negative, increase the corresponding counter */
1902 else
1903 (*activityneghuge)++;
1904 }
1905 /* "normal case": just add the contribution to the activity */
1906 else
1907 QUAD_ASSIGN(delta, newcontribution);
1908 }
1909 }
1910 /* old bound was finite and not too large */
1911 else
1912 {
1913 if( !finitenewbound )
1914 {
1915 /* if the new bound is +infinity, the old contribution has to be subtracted
1916 * and the counter for positive infinite contributions has to be increased
1917 */
1918 if( newbound > 0.0 )
1919 {
1920 (*activityposinf)++;
1921 QUAD_ASSIGN(delta, -oldcontribution);
1922 }
1923 /* if the new bound is -infinity, the old contribution has to be subtracted
1924 * and the counter for negative infinite contributions has to be increased
1925 */
1926 else
1927 {
1928 assert(newbound < 0.0 );
1929
1930 (*activityneginf)++;
1931 QUAD_ASSIGN(delta, -oldcontribution);
1932 }
1933 }
1934 /* if the contribution of this variable is too large, increase the counter for huge values */
1935 else if( hugevalnewcont )
1936 {
1937 if( newcontribution > 0.0 )
1938 {
1939 (*activityposhuge)++;
1940 QUAD_ASSIGN(delta, -oldcontribution);
1941 }
1942 else
1943 {
1944 (*activityneghuge)++;
1945 QUAD_ASSIGN(delta, -oldcontribution);
1946 }
1947 }
1948 /* "normal case": just update the activity */
1949 else
1950 {
1951 QUAD_ASSIGN(delta, newcontribution);
1952 SCIPquadprecSumQD(delta, delta, -oldcontribution);
1953 }
1954 }
1955
1956 /* update the activity, if the current value is valid and there was a change in the finite part */
1957 if( validact && (QUAD_TO_DBL(delta) != 0.0) )
1958 {
1959 SCIP_Real curractivity;
1960
1961 /* if the absolute value of the activity is increased, this is regarded as reliable,
1962 * otherwise, we check whether we can still trust the updated value
1963 */
1964 SCIPquadprecSumQD(*activity, *activity, QUAD_TO_DBL(delta));
1965
1966 curractivity = QUAD_TO_DBL(*activity);
1967 assert(!SCIPisInfinity(scip, -curractivity) && !SCIPisInfinity(scip, curractivity));
1968
1969 if( REALABS((*lastactivity)) < REALABS(curractivity) )
1970 {
1971 (*lastactivity) = curractivity;
1972 }
1973 else
1974 {
1975 if( checkreliability && SCIPisUpdateUnreliable(scip, curractivity, (*lastactivity)) )
1976 {
1977 SCIPdebugMsg(scip, "%s activity of linear constraint unreliable after update: %16.9g\n",
1978 (global ? "global " : ""), curractivity);
1979
1980 /* mark the activity that was just changed and is not reliable anymore to be invalid */
1981 if( global )
1982 {
1983 if( (boundtype == SCIP_BOUNDTYPE_LOWER) == (val > 0.0) )
1984 consdata->validglbminact = FALSE;
1985 else
1986 consdata->validglbmaxact = FALSE;
1987 }
1988 else
1989 {
1990 if( (boundtype == SCIP_BOUNDTYPE_LOWER) == (val > 0.0) )
1991 consdata->validminact = FALSE;
1992 else
1993 consdata->validmaxact = FALSE;
1994 }
1995 }
1996 }
1997 }
1998}
1999
2000/** updates minimum and maximum activity for a change in lower bound */
2001static
2003 SCIP* scip, /**< SCIP data structure */
2004 SCIP_CONSDATA* consdata, /**< linear constraint data */
2005 SCIP_VAR* var, /**< variable that has been changed */
2006 SCIP_Real oldlb, /**< old lower bound of variable */
2007 SCIP_Real newlb, /**< new lower bound of variable */
2008 SCIP_Real val, /**< coefficient of constraint entry */
2009 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2010 )
2011{
2012 assert(scip != NULL);
2013 assert(consdata != NULL);
2014 assert(var != NULL);
2015
2016 if( consdata->validactivities )
2017 {
2018 consdataUpdateActivities(scip, consdata, var, oldlb, newlb, val, SCIP_BOUNDTYPE_LOWER, FALSE, checkreliability);
2019
2020 assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->minactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->minactivity)));
2021 assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->maxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->maxactivity)));
2022 }
2023}
2024
2025/** updates minimum and maximum activity for a change in upper bound */
2026static
2028 SCIP* scip, /**< SCIP data structure */
2029 SCIP_CONSDATA* consdata, /**< linear constraint data */
2030 SCIP_VAR* var, /**< variable that has been changed */
2031 SCIP_Real oldub, /**< old upper bound of variable */
2032 SCIP_Real newub, /**< new upper bound of variable */
2033 SCIP_Real val, /**< coefficient of constraint entry */
2034 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2035 )
2036{
2037 assert(scip != NULL);
2038 assert(consdata != NULL);
2039 assert(var != NULL);
2040
2041 if( consdata->validactivities )
2042 {
2043 consdataUpdateActivities(scip, consdata, var, oldub, newub, val, SCIP_BOUNDTYPE_UPPER, FALSE, checkreliability);
2044
2045 assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->minactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->minactivity)));
2046 assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->maxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->maxactivity)));
2047 }
2048}
2049
2050/** updates minimum and maximum global activity for a change in the global lower bound */
2051static
2053 SCIP* scip, /**< SCIP data structure */
2054 SCIP_CONSDATA* consdata, /**< linear constraint data */
2055 SCIP_Real oldlb, /**< old lower bound of variable */
2056 SCIP_Real newlb, /**< new lower bound of variable */
2057 SCIP_Real val, /**< coefficient of constraint entry */
2058 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2059 )
2060{
2061 assert(scip != NULL);
2062 assert(consdata != NULL);
2063
2064 if( consdata->validactivities )
2065 {
2066 consdataUpdateActivities(scip, consdata, NULL, oldlb, newlb, val, SCIP_BOUNDTYPE_LOWER, TRUE, checkreliability);
2067
2068 assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbminactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbminactivity)));
2069 assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbmaxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbmaxactivity)));
2070 }
2071}
2072
2073/** updates minimum and maximum global activity for a change in global upper bound */
2074static
2076 SCIP* scip, /**< SCIP data structure */
2077 SCIP_CONSDATA* consdata, /**< linear constraint data */
2078 SCIP_Real oldub, /**< old upper bound of variable */
2079 SCIP_Real newub, /**< new upper bound of variable */
2080 SCIP_Real val, /**< coefficient of constraint entry */
2081 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2082 )
2083{
2084 assert(scip != NULL);
2085 assert(consdata != NULL);
2086
2087 if( consdata->validactivities )
2088 {
2089 consdataUpdateActivities(scip, consdata, NULL, oldub, newub, val, SCIP_BOUNDTYPE_UPPER, TRUE, checkreliability);
2090
2091 assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbminactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbminactivity)));
2092 assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbmaxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbmaxactivity)));
2093 }
2094}
2095
2096/** updates minimum and maximum activity and maximum absolute value for coefficient addition */
2097static
2099 SCIP* scip, /**< SCIP data structure */
2100 SCIP_CONSDATA* consdata, /**< linear constraint data */
2101 SCIP_VAR* var, /**< variable of constraint entry */
2102 SCIP_Real val, /**< coefficient of constraint entry */
2103 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2104 )
2105{
2106 assert(scip != NULL);
2107 assert(consdata != NULL);
2108 assert(var != NULL);
2109 assert(!SCIPisZero(scip, val));
2110
2111 /* update maximum absolute value */
2112 if( consdata->validmaxabsval )
2113 {
2114 SCIP_Real absval;
2115
2116 assert(consdata->maxabsval < SCIP_INVALID);
2117
2118 absval = REALABS(val);
2119 consdata->maxabsval = MAX(consdata->maxabsval, absval);
2120 }
2121
2122 /* update minimum absolute value */
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 minimum and maximum 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 /* update maximum activity delta */
2148 if( consdata->maxactdeltavar == NULL || !SCIPisInfinity(scip, consdata->maxactdelta) )
2149 {
2150 SCIP_Real lb = SCIPvarGetLbLocal(var);
2151 SCIP_Real ub = SCIPvarGetUbLocal(var);
2152
2153 if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
2154 {
2155 consdata->maxactdelta = SCIPinfinity(scip);
2156 consdata->maxactdeltavar = var;
2157 }
2158 else if( consdata->maxactdeltavar != NULL )
2159 {
2160 SCIP_Real domain = ub - lb;
2161 SCIP_Real delta = REALABS(val) * domain;
2162
2163 if( delta > consdata->maxactdelta )
2164 {
2165 consdata->maxactdelta = delta;
2166 consdata->maxactdeltavar = var;
2167 }
2168 }
2169 }
2170}
2171
2172/** updates minimum and maximum activity for coefficient deletion, invalidates maximum absolute value if necessary */
2173static
2175 SCIP* scip, /**< SCIP data structure */
2176 SCIP_CONSDATA* consdata, /**< linear constraint data */
2177 SCIP_VAR* var, /**< variable of constraint entry */
2178 SCIP_Real val, /**< coefficient of constraint entry */
2179 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2180 )
2181{
2182 assert(scip != NULL);
2183 assert(consdata != NULL);
2184 assert(var != NULL);
2185 assert(!SCIPisZero(scip, val));
2186
2187 /* invalidate maximum absolute value, if this coefficient was the maximum */
2188 if( consdata->validmaxabsval )
2189 {
2190 SCIP_Real absval;
2191
2192 absval = REALABS(val);
2193
2194 if( SCIPisEQ(scip, absval, consdata->maxabsval) )
2195 {
2196 consdata->validmaxabsval = FALSE;
2197 consdata->maxabsval = SCIP_INVALID;
2198 }
2199 }
2200
2201 /* invalidate minimum absolute value, if this coefficient was the minimum */
2202 if( consdata->validminabsval )
2203 {
2204 SCIP_Real absval;
2205
2206 absval = REALABS(val);
2207
2208 if( SCIPisEQ(scip, absval, consdata->minabsval) )
2209 {
2210 consdata->validminabsval = FALSE;
2211 consdata->minabsval = SCIP_INVALID;
2212 }
2213 }
2214
2215 /* update minimum and maximum activity */
2216 if( consdata->validactivities )
2217 {
2218 assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
2219 assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
2220 assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
2221 assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
2222
2223 consdataUpdateActivitiesLb(scip, consdata, var, SCIPvarGetLbLocal(var), 0.0, val, checkreliability);
2224 consdataUpdateActivitiesUb(scip, consdata, var, SCIPvarGetUbLocal(var), 0.0, val, checkreliability);
2225 consdataUpdateActivitiesGlbLb(scip, consdata, SCIPvarGetLbGlobal(var), 0.0, val, checkreliability);
2226 consdataUpdateActivitiesGlbUb(scip, consdata, SCIPvarGetUbGlobal(var), 0.0, val, checkreliability);
2227 }
2228
2229 /* reset maximum activity delta so that it will be recalculated on the next real propagation */
2230 if( consdata->maxactdeltavar == var )
2231 {
2232 consdata->maxactdelta = SCIP_INVALID;
2233 consdata->maxactdeltavar = NULL;
2234 }
2235}
2236
2237/** updates minimum and maximum activity for coefficient change, invalidates maximum absolute value if necessary */
2238static
2240 SCIP* scip, /**< SCIP data structure */
2241 SCIP_CONSDATA* consdata, /**< linear constraint data */
2242 SCIP_VAR* var, /**< variable of constraint entry */
2243 SCIP_Real oldval, /**< old coefficient of constraint entry */
2244 SCIP_Real newval, /**< new coefficient of constraint entry */
2245 SCIP_Bool checkreliability /**< should the reliability of the recalculated activity be checked? */
2246 )
2247{
2248 /* @todo do something more clever here, e.g. if oldval * newval >= 0, do the update directly */
2249 consdataUpdateDelCoef(scip, consdata, var, oldval, checkreliability);
2250 consdataUpdateAddCoef(scip, consdata, var, newval, checkreliability);
2251}
2252
2253/** returns the maximum absolute value of all coefficients in the constraint */
2254static
2256 SCIP_CONSDATA* consdata /**< linear constraint data */
2257 )
2258{
2259 assert(consdata != NULL);
2260
2261 if( !consdata->validmaxabsval )
2262 consdataCalcMaxAbsval(consdata);
2263 assert(consdata->validmaxabsval);
2264 assert(consdata->maxabsval < SCIP_INVALID);
2265
2266 return consdata->maxabsval;
2267}
2268
2269/** returns the minimum absolute value of all coefficients in the constraint */
2270static
2272 SCIP_CONSDATA* consdata /**< linear constraint data */
2273 )
2274{
2275 assert(consdata != NULL);
2276
2277 if( !consdata->validminabsval )
2278 consdataCalcMinAbsval(consdata);
2279 assert(consdata->validminabsval);
2280 assert(consdata->minabsval < SCIP_INVALID);
2281
2282 return consdata->minabsval;
2283}
2284
2285/** calculates minimum and maximum local and global activity for constraint from scratch;
2286 * additionally recalculates maximum absolute value of coefficients
2287 */
2288static
2290 SCIP* scip, /**< SCIP data structure */
2291 SCIP_CONSDATA* consdata /**< linear constraint data */
2292 )
2293{
2294 int i;
2295
2296 assert(scip != NULL);
2297 assert(consdata != NULL);
2298 assert(!consdata->validactivities);
2299 assert(QUAD_TO_DBL(consdata->minactivity) >= SCIP_INVALID || consdata->validminact);
2300 assert(QUAD_TO_DBL(consdata->maxactivity) >= SCIP_INVALID || consdata->validmaxact);
2301 assert(QUAD_TO_DBL(consdata->glbminactivity) >= SCIP_INVALID || consdata->validglbminact);
2302 assert(QUAD_TO_DBL(consdata->glbmaxactivity) >= SCIP_INVALID || consdata->validglbmaxact);
2303
2304 consdata->validmaxabsval = TRUE;
2305 consdata->validminabsval = TRUE;
2306 consdata->validactivities = TRUE;
2307 consdata->validminact = TRUE;
2308 consdata->validmaxact = TRUE;
2309 consdata->validglbminact = TRUE;
2310 consdata->validglbmaxact = TRUE;
2311 consdata->maxabsval = 0.0;
2312 consdata->minabsval = (consdata->nvars == 0 ? 0.0 : REALABS(consdata->vals[0]));
2313 QUAD_ASSIGN(consdata->minactivity, 0.0);
2314 QUAD_ASSIGN(consdata->maxactivity, 0.0);
2315 consdata->lastminactivity = 0.0;
2316 consdata->lastmaxactivity = 0.0;
2317 consdata->minactivityneginf = 0;
2318 consdata->minactivityposinf = 0;
2319 consdata->maxactivityneginf = 0;
2320 consdata->maxactivityposinf = 0;
2321 consdata->minactivityneghuge = 0;
2322 consdata->minactivityposhuge = 0;
2323 consdata->maxactivityneghuge = 0;
2324 consdata->maxactivityposhuge = 0;
2325 QUAD_ASSIGN(consdata->glbminactivity, 0.0);
2326 QUAD_ASSIGN(consdata->glbmaxactivity, 0.0);
2327 consdata->lastglbminactivity = 0.0;
2328 consdata->lastglbmaxactivity = 0.0;
2329 consdata->glbminactivityneginf = 0;
2330 consdata->glbminactivityposinf = 0;
2331 consdata->glbmaxactivityneginf = 0;
2332 consdata->glbmaxactivityposinf = 0;
2333 consdata->glbminactivityneghuge = 0;
2334 consdata->glbminactivityposhuge = 0;
2335 consdata->glbmaxactivityneghuge = 0;
2336 consdata->glbmaxactivityposhuge = 0;
2337
2338 for( i = 0; i < consdata->nvars; ++i )
2339 consdataUpdateAddCoef(scip, consdata, consdata->vars[i], consdata->vals[i], FALSE);
2340
2341 consdata->lastminactivity = QUAD_TO_DBL(consdata->minactivity);
2342 consdata->lastmaxactivity = QUAD_TO_DBL(consdata->maxactivity);
2343 consdata->lastglbminactivity = QUAD_TO_DBL(consdata->glbminactivity);
2344 consdata->lastglbmaxactivity = QUAD_TO_DBL(consdata->glbmaxactivity);
2345}
2346
2347/** gets minimal activity for constraint and given values of counters for infinite and huge contributions
2348 * and (if needed) delta to subtract from stored finite part of activity in case of a residual activity
2349 */
2350static
2352 SCIP* scip, /**< SCIP data structure */
2353 SCIP_CONSDATA* consdata, /**< linear constraint */
2354 int posinf, /**< number of coefficients contributing pos. infinite value */
2355 int neginf, /**< number of coefficients contributing neg. infinite value */
2356 int poshuge, /**< number of coefficients contributing huge pos. value */
2357 int neghuge, /**< number of coefficients contributing huge neg. value */
2358 SCIP_Real delta, /**< value to subtract from stored minactivity
2359 * (contribution of the variable set to zero when getting residual activity) */
2360 SCIP_Bool global, /**< should the global or local minimal activity be returned? */
2361 SCIP_Bool goodrelax, /**< should a good relaxation be computed or are relaxed acticities ignored, anyway? */
2362 SCIP_Real* minactivity, /**< pointer to store the minimal activity */
2363 SCIP_Bool* istight, /**< pointer to store whether activity bound is tight to variable bounds
2364 * i.e. is the actual minactivity (otherwise a lower bound is provided) */
2365 SCIP_Bool* issettoinfinity /**< pointer to store whether minactivity was set to infinity or calculated */
2366 )
2367{
2368 assert(scip != NULL);
2369 assert(consdata != NULL);
2370 assert(posinf >= 0);
2371 assert(neginf >= 0);
2372 assert(poshuge >= 0);
2373 assert(neghuge >= 0);
2374 assert(minactivity != NULL);
2375 assert(istight != NULL);
2376 assert(issettoinfinity != NULL);
2377
2378 /* if we have neg. infinite contributions, the minactivity is -infty */
2379 if( neginf > 0 )
2380 {
2381 *minactivity = -SCIPinfinity(scip);
2382 *issettoinfinity = TRUE;
2383 *istight = posinf == 0;
2384 }
2385 /* if we have pos. (and no neg.) infinite contributions, the minactivity is +infty */
2386 else if( posinf > 0 )
2387 {
2388 *minactivity = SCIPinfinity(scip);
2389 *issettoinfinity = TRUE;
2390 *istight = TRUE;
2391 }
2392 /* if we have neg. huge contributions or do not need a good relaxation, we just return -infty as minactivity */
2393 else if( neghuge > 0 || ( poshuge > 0 && !goodrelax ) )
2394 {
2395 *minactivity = -SCIPinfinity(scip);
2396 *issettoinfinity = TRUE;
2397 *istight = FALSE;
2398 }
2399 else
2400 {
2401 SCIP_Real QUAD(tmpactivity);
2402
2403 /* recompute minactivity if it is not valid */
2404 if( global )
2405 {
2406 if( !consdata->validglbminact )
2408 assert(consdata->validglbminact);
2409
2410 QUAD_ASSIGN_Q(tmpactivity, consdata->glbminactivity);
2411 }
2412 else
2413 {
2414 if( !consdata->validminact )
2416 assert(consdata->validminact);
2417
2418 QUAD_ASSIGN_Q(tmpactivity, consdata->minactivity);
2419 }
2420
2421 /* calculate residual minactivity */
2422 SCIPquadprecSumQD(tmpactivity, tmpactivity, -delta);
2423
2424 /* we have no infinite and no neg. huge contributions, but pos. huge contributions; a feasible relaxation of the
2425 * minactivity is given by adding the number of positive huge contributions times the huge value
2426 */
2427 if( poshuge > 0 )
2428 {
2429 SCIPquadprecSumQD(tmpactivity, tmpactivity, poshuge * SCIPgetHugeValue(scip));
2430 *istight = FALSE;
2431 }
2432 /* all counters are zero, so the minactivity is tight */
2433 else
2434 *istight = TRUE;
2435
2436 /* round residual minactivity */
2437 *minactivity = QUAD_TO_DBL(tmpactivity);
2438 *issettoinfinity = FALSE;
2439 }
2440}
2441
2442/** gets maximal activity for constraint and given values of counters for infinite and huge contributions
2443 * and (if needed) delta to subtract from stored finite part of activity in case of a residual activity
2444 */
2445static
2447 SCIP* scip, /**< SCIP data structure */
2448 SCIP_CONSDATA* consdata, /**< linear constraint */
2449 int posinf, /**< number of coefficients contributing pos. infinite value */
2450 int neginf, /**< number of coefficients contributing neg. infinite value */
2451 int poshuge, /**< number of coefficients contributing huge pos. value */
2452 int neghuge, /**< number of coefficients contributing huge neg. value */
2453 SCIP_Real delta, /**< value to subtract from stored maxactivity
2454 * (contribution of the variable set to zero when getting residual activity) */
2455 SCIP_Bool global, /**< should the global or local maximal activity be returned? */
2456 SCIP_Bool goodrelax, /**< should a good relaxation be computed or are relaxed acticities ignored, anyway? */
2457 SCIP_Real* maxactivity, /**< pointer to store the maximal activity */
2458 SCIP_Bool* istight, /**< pointer to store whether activity bound is tight to variable bounds
2459 * i.e. is the actual maxactivity (otherwise an upper bound is provided) */
2460 SCIP_Bool* issettoinfinity /**< pointer to store whether maxactivity was set to infinity or calculated */
2461 )
2462{
2463 assert(scip != NULL);
2464 assert(consdata != NULL);
2465 assert(posinf >= 0);
2466 assert(neginf >= 0);
2467 assert(poshuge >= 0);
2468 assert(neghuge >= 0);
2469 assert(maxactivity != NULL);
2470 assert(istight != NULL);
2471 assert(issettoinfinity != NULL);
2472
2473 /* if we have pos. infinite contributions, the maxactivity is +infty */
2474 if( posinf > 0 )
2475 {
2476 *maxactivity = SCIPinfinity(scip);
2477 *issettoinfinity = TRUE;
2478 *istight = neginf == 0;
2479 }
2480 /* if we have neg. (and no pos.) infinite contributions, the maxactivity is -infty */
2481 else if( neginf > 0 )
2482 {
2483 *maxactivity = -SCIPinfinity(scip);
2484 *issettoinfinity = TRUE;
2485 *istight = TRUE;
2486 }
2487 /* if we have pos. huge contributions or do not need a good relaxation, we just return +infty as maxactivity */
2488 else if( poshuge > 0 || ( neghuge > 0 && !goodrelax ) )
2489 {
2490 *maxactivity = SCIPinfinity(scip);
2491 *issettoinfinity = TRUE;
2492 *istight = FALSE;
2493 }
2494 else
2495 {
2496 SCIP_Real QUAD(tmpactivity);
2497
2498 /* recompute maxactivity if it is not valid */
2499 if( global )
2500 {
2501 if( !consdata->validglbmaxact )
2503 assert(consdata->validglbmaxact);
2504
2505 QUAD_ASSIGN_Q(tmpactivity, consdata->glbmaxactivity);
2506 }
2507 else
2508 {
2509 if( !consdata->validmaxact )
2511 assert(consdata->validmaxact);
2512
2513 QUAD_ASSIGN_Q(tmpactivity, consdata->maxactivity);
2514 }
2515
2516 /* calculate residual maxactivity */
2517 SCIPquadprecSumQD(tmpactivity, tmpactivity, -delta);
2518
2519 /* we have no infinite and no pos. huge contributions, but neg. huge contributions; a feasible relaxation of the
2520 * maxactivity is given by subtracting the number of negative huge contributions times the huge value
2521 */
2522 if( neghuge > 0 )
2523 {
2524 SCIPquadprecSumQD(tmpactivity, tmpactivity, -neghuge * SCIPgetHugeValue(scip));
2525 *istight = FALSE;
2526 }
2527 /* all counters are zero, so the maxactivity is tight */
2528 else
2529 *istight = TRUE;
2530
2531 /* round residual maxactivity */
2532 *maxactivity = QUAD_TO_DBL(tmpactivity);
2533 *issettoinfinity = FALSE;
2534 }
2535}
2536
2537/** gets activity bounds for constraint */
2538static
2540 SCIP* scip, /**< SCIP data structure */
2541 SCIP_CONSDATA* consdata, /**< linear constraint */
2542 SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2543 * relaxed activities ignored, anyway? */
2544 SCIP_Real* minactivity, /**< pointer to store the minimal activity */
2545 SCIP_Real* maxactivity, /**< pointer to store the maximal activity */
2546 SCIP_Bool* ismintight, /**< pointer to store whether the minactivity bound is tight
2547 * i.e. is the actual minactivity (otherwise a lower bound is provided) */
2548 SCIP_Bool* ismaxtight, /**< pointer to store whether the maxactivity bound is tight
2549 * i.e. is the actual maxactivity (otherwise an upper bound is provided) */
2550 SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minactivity was set to infinity or calculated */
2551 SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxactivity was set to infinity or calculated */
2552
2553 )
2554{
2555 assert(scip != NULL);
2556 assert(consdata != NULL);
2557 assert(minactivity != NULL);
2558 assert(maxactivity != NULL);
2559 assert(isminsettoinfinity != NULL);
2560 assert(ismaxsettoinfinity != NULL);
2561
2562 if( !consdata->validactivities )
2563 {
2564 consdataCalcActivities(scip, consdata);
2565 assert(consdata->validminact);
2566 assert(consdata->validmaxact);
2567 }
2568 assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
2569 assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
2570 assert(consdata->minactivityneginf >= 0);
2571 assert(consdata->minactivityposinf >= 0);
2572 assert(consdata->maxactivityneginf >= 0);
2573 assert(consdata->maxactivityposinf >= 0);
2574
2575 getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2576 consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2577 minactivity, ismintight, isminsettoinfinity);
2578
2579 getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2580 consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2581 maxactivity, ismaxtight, ismaxsettoinfinity);
2582}
2583
2584/** calculates activity bounds for constraint after setting variable to zero */
2585static
2587 SCIP* scip, /**< SCIP data structure */
2588 SCIP_CONSDATA* consdata, /**< linear constraint */
2589 SCIP_VAR* cancelvar, /**< variable to calculate activity residual for */
2590 SCIP_Real* resactivity, /**< pointer to store the residual activity */
2591 SCIP_Bool isminresact, /**< should minimal or maximal residual activity be calculated? */
2592 SCIP_Bool useglobalbounds /**< should global or local bounds be used? */
2593 )
2594{
2595 SCIP_VAR* var;
2596 SCIP_Real val;
2597 SCIP_Real lb;
2598 SCIP_Real ub;
2599 int v;
2600
2601 assert(scip != NULL);
2602 assert(consdata != NULL);
2603 assert(cancelvar != NULL);
2604 assert(resactivity != NULL);
2605
2606 *resactivity = 0.0;
2607
2608 for( v = 0; v < consdata->nvars; ++v )
2609 {
2610 var = consdata->vars[v];
2611 assert(var != NULL);
2612 if( var == cancelvar )
2613 continue;
2614
2615 val = consdata->vals[v];
2616
2617 if( useglobalbounds )
2618 {
2619 lb = SCIPvarGetLbGlobal(var);
2620 ub = SCIPvarGetUbGlobal(var);
2621 }
2622 else
2623 {
2624 lb = SCIPvarGetLbLocal(var);
2625 ub = SCIPvarGetUbLocal(var);
2626 }
2627
2628 assert(!SCIPisZero(scip, val));
2629 assert(SCIPisLE(scip, lb, ub));
2630
2631 if( val > 0.0 )
2632 {
2633 if( isminresact )
2634 {
2635 assert(!SCIPisInfinity(scip, -lb));
2636 assert(!SCIPisHugeValue(scip, REALABS(val*lb)));
2637 *resactivity += val*lb;
2638 }
2639 else
2640 {
2641 assert(!SCIPisInfinity(scip, ub));
2642 assert(!SCIPisHugeValue(scip, REALABS(val*ub)));
2643 *resactivity += val*ub;
2644 }
2645 }
2646 else
2647 {
2648 if( isminresact)
2649 {
2650 assert(!SCIPisInfinity(scip, ub));
2651 assert(!SCIPisHugeValue(scip, REALABS(val*ub)));
2652 *resactivity += val*ub;
2653 }
2654 else
2655 {
2656 assert(!SCIPisInfinity(scip, -lb));
2657 assert(!SCIPisHugeValue(scip, REALABS(val*lb)));
2658 *resactivity += val*lb;
2659 }
2660 }
2661 }
2662 assert(!SCIPisInfinity(scip, *resactivity) && !SCIPisInfinity(scip, -(*resactivity)));
2663}
2664
2665/** gets activity bounds for constraint after setting variable to zero */
2666static
2668 SCIP* scip, /**< SCIP data structure */
2669 SCIP_CONSDATA* consdata, /**< linear constraint */
2670 SCIP_VAR* var, /**< variable to calculate activity residual for */
2671 SCIP_Real val, /**< coefficient value of variable in linear constraint */
2672 SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2673 * relaxed acticities ignored, anyway? */
2674 SCIP_Real* minresactivity, /**< pointer to store the minimal residual activity */
2675 SCIP_Real* maxresactivity, /**< pointer to store the maximal residual activity */
2676 SCIP_Bool* ismintight, /**< pointer to store whether the residual minactivity bound is tight
2677 * i.e. is the actual residual minactivity (otherwise a lower bound is provided) */
2678 SCIP_Bool* ismaxtight, /**< pointer to store whether the residual maxactivity bound is tight
2679 * i.e. is the actual residual maxactivity (otherwise an upper bound is provided) */
2680 SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2681 SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2682 )
2683{
2684 SCIP_Real minactbound;
2685 SCIP_Real maxactbound;
2686 SCIP_Real absval;
2687
2688 assert(scip != NULL);
2689 assert(consdata != NULL);
2690 assert(var != NULL);
2691 assert(minresactivity != NULL);
2692 assert(maxresactivity != NULL);
2693 assert(ismintight != NULL);
2694 assert(ismaxtight != NULL);
2695 assert(isminsettoinfinity != NULL);
2696 assert(ismaxsettoinfinity != NULL);
2697
2698 /* get activity bounds of linear constraint */
2699 if( !consdata->validactivities )
2700 {
2701 consdataCalcActivities(scip, consdata);
2702 assert(consdata->validminact);
2703 assert(consdata->validmaxact);
2704 }
2705 assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
2706 assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
2707 assert(consdata->minactivityneginf >= 0);
2708 assert(consdata->minactivityposinf >= 0);
2709 assert(consdata->maxactivityneginf >= 0);
2710 assert(consdata->maxactivityposinf >= 0);
2711 assert(consdata->minactivityneghuge >= 0);
2712 assert(consdata->minactivityposhuge >= 0);
2713 assert(consdata->maxactivityneghuge >= 0);
2714 assert(consdata->maxactivityposhuge >= 0);
2715
2716 if( val > 0.0 )
2717 {
2718 minactbound = SCIPvarGetLbLocal(var);
2719 maxactbound = SCIPvarGetUbLocal(var);
2720 absval = val;
2721 }
2722 else
2723 {
2724 minactbound = -SCIPvarGetUbLocal(var);
2725 maxactbound = -SCIPvarGetLbLocal(var);
2726 absval = -val;
2727 }
2728
2729 /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
2730 * and contribution of variable set to zero that has to be subtracted from finite part of activity
2731 */
2732 if( SCIPisInfinity(scip, minactbound) )
2733 {
2734 assert(consdata->minactivityposinf >= 1);
2735
2736 getMinActivity(scip, consdata, consdata->minactivityposinf - 1, consdata->minactivityneginf,
2737 consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2738 minresactivity, ismintight, isminsettoinfinity);
2739 }
2740 else if( SCIPisInfinity(scip, -minactbound) )
2741 {
2742 assert(consdata->minactivityneginf >= 1);
2743
2744 getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf - 1,
2745 consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2746 minresactivity, ismintight, isminsettoinfinity);
2747 }
2748 else if( SCIPisHugeValue(scip, minactbound * absval) )
2749 {
2750 assert(consdata->minactivityposhuge >= 1);
2751
2752 getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2753 consdata->minactivityposhuge - 1, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
2754 minresactivity, ismintight, isminsettoinfinity);
2755 }
2756 else if( SCIPisHugeValue(scip, -minactbound * absval) )
2757 {
2758 assert(consdata->minactivityneghuge >= 1);
2759
2760 getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2761 consdata->minactivityposhuge, consdata->minactivityneghuge - 1, 0.0, FALSE, goodrelax,
2762 minresactivity, ismintight, isminsettoinfinity);
2763 }
2764 else
2765 {
2766 getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
2767 consdata->minactivityposhuge, consdata->minactivityneghuge, absval * minactbound, FALSE, goodrelax,
2768 minresactivity, ismintight, isminsettoinfinity);
2769 }
2770
2771 /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
2772 * and contribution of variable set to zero that has to be subtracted from finite part of activity
2773 */
2774 if( SCIPisInfinity(scip, -maxactbound) )
2775 {
2776 assert(consdata->maxactivityneginf >= 1);
2777
2778 getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf - 1,
2779 consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2780 maxresactivity, ismaxtight, ismaxsettoinfinity);
2781 }
2782 else if( SCIPisInfinity(scip, maxactbound) )
2783 {
2784 assert(consdata->maxactivityposinf >= 1);
2785
2786 getMaxActivity(scip, consdata, consdata->maxactivityposinf - 1, consdata->maxactivityneginf,
2787 consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2788 maxresactivity, ismaxtight, ismaxsettoinfinity);
2789 }
2790 else if( SCIPisHugeValue(scip, absval * maxactbound) )
2791 {
2792 assert(consdata->maxactivityposhuge >= 1);
2793
2794 getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2795 consdata->maxactivityposhuge - 1, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
2796 maxresactivity, ismaxtight, ismaxsettoinfinity);
2797 }
2798 else if( SCIPisHugeValue(scip, -absval * maxactbound) )
2799 {
2800 assert(consdata->maxactivityneghuge >= 1);
2801
2802 getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2803 consdata->maxactivityposhuge, consdata->maxactivityneghuge - 1, 0.0, FALSE, goodrelax,
2804 maxresactivity, ismaxtight, ismaxsettoinfinity);
2805 }
2806 else
2807 {
2808 getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
2809 consdata->maxactivityposhuge, consdata->maxactivityneghuge, absval * maxactbound, FALSE, goodrelax,
2810 maxresactivity, ismaxtight, ismaxsettoinfinity);
2811 }
2812}
2813
2814/** gets global activity bounds for constraint */
2815static
2817 SCIP* scip, /**< SCIP data structure */
2818 SCIP_CONSDATA* consdata, /**< linear constraint */
2819 SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2820 * relaxed acticities ignored, anyway? */
2821 SCIP_Real* glbminactivity, /**< pointer to store the minimal activity, or NULL, if not needed */
2822 SCIP_Real* glbmaxactivity, /**< pointer to store the maximal activity, or NULL, if not needed */
2823 SCIP_Bool* ismintight, /**< pointer to store whether the minactivity bound is tight
2824 * i.e. is the actual minactivity (otherwise a lower bound is provided) */
2825 SCIP_Bool* ismaxtight, /**< pointer to store whether the maxactivity bound is tight
2826 * i.e. is the actual maxactivity (otherwise an upper bound is provided) */
2827 SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2828 SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2829 )
2830{
2831 assert(scip != NULL);
2832 assert(consdata != NULL);
2833 assert((glbminactivity != NULL && ismintight != NULL && isminsettoinfinity != NULL)
2834 || (glbmaxactivity != NULL && ismaxtight != NULL && ismaxsettoinfinity != NULL));
2835
2836 if( !consdata->validactivities )
2837 {
2838 consdataCalcActivities(scip, consdata);
2839 assert(consdata->validglbminact);
2840 assert(consdata->validglbmaxact);
2841 }
2842 assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
2843 assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
2844 assert(consdata->glbminactivityneginf >= 0);
2845 assert(consdata->glbminactivityposinf >= 0);
2846 assert(consdata->glbmaxactivityneginf >= 0);
2847 assert(consdata->glbmaxactivityposinf >= 0);
2848 assert(consdata->glbminactivityneghuge >= 0);
2849 assert(consdata->glbminactivityposhuge >= 0);
2850 assert(consdata->glbmaxactivityneghuge >= 0);
2851 assert(consdata->glbmaxactivityposhuge >= 0);
2852
2853 if( glbminactivity != NULL )
2854 {
2855 assert(isminsettoinfinity != NULL);
2856 assert(ismintight != NULL);
2857
2858 getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
2859 consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
2860 glbminactivity, ismintight, isminsettoinfinity);
2861 }
2862
2863 if( glbmaxactivity != NULL )
2864 {
2865 assert(ismaxsettoinfinity != NULL);
2866 assert(ismaxtight != NULL);
2867
2868 getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
2869 consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
2870 glbmaxactivity, ismaxtight, ismaxsettoinfinity);
2871 }
2872}
2873
2874/** gets global activity bounds for constraint after setting variable to zero */
2875static
2877 SCIP* scip, /**< SCIP data structure */
2878 SCIP_CONSDATA* consdata, /**< linear constraint */
2879 SCIP_VAR* var, /**< variable to calculate activity residual for */
2880 SCIP_Real val, /**< coefficient value of variable in linear constraint */
2881 SCIP_Bool goodrelax, /**< if we have huge contributions, do we need a good relaxation or are
2882 * relaxed acticities ignored, anyway? */
2883 SCIP_Real* minresactivity, /**< pointer to store the minimal residual activity, or NULL, if not needed */
2884 SCIP_Real* maxresactivity, /**< pointer to store the maximal residual activity, or NULL, if not needed */
2885 SCIP_Bool* ismintight, /**< pointer to store whether the residual minactivity bound is tight
2886 * i.e. is the actual residual minactivity (otherwise a lower bound is provided) */
2887 SCIP_Bool* ismaxtight, /**< pointer to store whether the residual maxactivity bound is tight
2888 * i.e. is the actual residual maxactivity (otherwise an upper bound is provided) */
2889 SCIP_Bool* isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
2890 SCIP_Bool* ismaxsettoinfinity /**< pointer to store whether maxresactivity was set to infinity or calculated */
2891 )
2892{
2893 SCIP_Real minactbound;
2894 SCIP_Real maxactbound;
2895 SCIP_Real absval;
2896
2897 assert(scip != NULL);
2898 assert(consdata != NULL);
2899 assert(var != NULL);
2900 assert((minresactivity != NULL && ismintight != NULL && isminsettoinfinity != NULL )
2901 || (maxresactivity != NULL && ismaxtight != NULL && ismaxsettoinfinity != NULL));
2902
2903 /* get activity bounds of linear constraint */
2904 if( !consdata->validactivities )
2905 consdataCalcActivities(scip, consdata);
2906
2907 assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
2908 assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
2909 assert(consdata->glbminactivityneginf >= 0);
2910 assert(consdata->glbminactivityposinf >= 0);
2911 assert(consdata->glbmaxactivityneginf >= 0);
2912 assert(consdata->glbmaxactivityposinf >= 0);
2913
2914 if( val > 0.0 )
2915 {
2916 minactbound = SCIPvarGetLbGlobal(var);
2917 maxactbound = SCIPvarGetUbGlobal(var);
2918 absval = val;
2919 }
2920 else
2921 {
2922 minactbound = -SCIPvarGetUbGlobal(var);
2923 maxactbound = -SCIPvarGetLbGlobal(var);
2924 absval = -val;
2925 }
2926
2927 if( minresactivity != NULL )
2928 {
2929 assert(isminsettoinfinity != NULL);
2930 assert(ismintight != NULL);
2931
2932 /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
2933 * and contribution of variable set to zero that has to be subtracted from finite part of activity
2934 */
2935 if( SCIPisInfinity(scip, minactbound) )
2936 {
2937 assert(consdata->glbminactivityposinf >= 1);
2938
2939 getMinActivity(scip, consdata, consdata->glbminactivityposinf - 1, consdata->glbminactivityneginf,
2940 consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
2941 minresactivity, ismintight, isminsettoinfinity);
2942 }
2943 else if( SCIPisInfinity(scip, -minactbound) )
2944 {
2945 assert(consdata->glbminactivityneginf >= 1);
2946
2947 getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf - 1,
2948 consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
2949 minresactivity, ismintight, isminsettoinfinity);
2950 }
2951 else if( SCIPisHugeValue(scip, minactbound * absval) )
2952 {
2953 assert(consdata->glbminactivityposhuge >= 1);
2954
2955 getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
2956 consdata->glbminactivityposhuge - 1, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
2957 minresactivity, ismintight, isminsettoinfinity);
2958 }
2959 else if( SCIPisHugeValue(scip, -minactbound * absval) )
2960 {
2961 assert(consdata->glbminactivityneghuge >= 1);
2962
2963 getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
2964 consdata->glbminactivityposhuge, consdata->glbminactivityneghuge - 1, 0.0, TRUE, goodrelax,
2965 minresactivity, ismintight, isminsettoinfinity);
2966 }
2967 else
2968 {
2969 getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
2970 consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, absval * minactbound, TRUE,
2971 goodrelax, minresactivity, ismintight, isminsettoinfinity);
2972 }
2973 }
2974
2975 if( maxresactivity != NULL )
2976 {
2977 assert(ismaxsettoinfinity != NULL);
2978 assert(ismaxtight != NULL);
2979
2980 /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
2981 * and contribution of variable set to zero that has to be subtracted from finite part of activity
2982 */
2983 if( SCIPisInfinity(scip, -maxactbound) )
2984 {
2985 assert(consdata->glbmaxactivityneginf >= 1);
2986
2987 getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf - 1,
2988 consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
2989 maxresactivity, ismaxtight, ismaxsettoinfinity);
2990 }
2991 else if( SCIPisInfinity(scip, maxactbound) )
2992 {
2993 assert(consdata->glbmaxactivityposinf >= 1);
2994
2995 getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf - 1, consdata->glbmaxactivityneginf,
2996 consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
2997 maxresactivity, ismaxtight, ismaxsettoinfinity);
2998 }
2999 else if( SCIPisHugeValue(scip, absval * maxactbound) )
3000 {
3001 assert(consdata->glbmaxactivityposhuge >= 1);
3002
3003 getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
3004 consdata->glbmaxactivityposhuge - 1, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
3005 maxresactivity, ismaxtight, ismaxsettoinfinity);
3006 }
3007 else if( SCIPisHugeValue(scip, -absval * maxactbound) )
3008 {
3009 assert(consdata->glbmaxactivityneghuge >= 1);
3010
3011 getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
3012 consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge - 1, 0.0, TRUE, goodrelax,
3013 maxresactivity, ismaxtight, ismaxsettoinfinity);
3014 }
3015 else
3016 {
3017 getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
3018 consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, absval * maxactbound, TRUE,
3019 goodrelax, maxresactivity, ismaxtight, ismaxsettoinfinity);
3020 }
3021 }
3022}
3023
3024/** calculates the activity of the linear constraint for given solution */
3025static
3027 SCIP* scip, /**< SCIP data structure */
3028 SCIP_CONSDATA* consdata, /**< linear constraint data */
3029 SCIP_SOL* sol /**< solution to get activity for, NULL to current solution */
3030 )
3031{
3032 SCIP_Real activity;
3033
3034 assert(scip != NULL);
3035 assert(consdata != NULL);
3036
3037 if( sol == NULL && !SCIPhasCurrentNodeLP(scip) )
3038 activity = consdataComputePseudoActivity(scip, consdata);
3039 else
3040 {
3041 SCIP_Real solval;
3042 int nposinf;
3043 int nneginf;
3044 SCIP_Bool negsign;
3045 int v;
3046
3047 activity = 0.0;
3048 nposinf = 0;
3049 nneginf = 0;
3050
3051 for( v = 0; v < consdata->nvars; ++v )
3052 {
3053 solval = SCIPgetSolVal(scip, sol, consdata->vars[v]);
3054
3055 if( consdata->vals[v] < 0 )
3056 negsign = TRUE;
3057 else
3058 negsign = FALSE;
3059
3060 if( (SCIPisInfinity(scip, solval) && !negsign) || (SCIPisInfinity(scip, -solval) && negsign) )
3061 ++nposinf;
3062 else if( (SCIPisInfinity(scip, solval) && negsign) || (SCIPisInfinity(scip, -solval) && !negsign) )
3063 ++nneginf;
3064 else
3065 activity += consdata->vals[v] * solval;
3066 }
3067 assert(nneginf >= 0 && nposinf >= 0);
3068
3069 SCIPdebugMsg(scip, "activity of linear constraint: %.15g, %d positive infinity values, %d negative infinity values \n", activity, nposinf, nneginf);
3070
3071 /* check for amount of infinity values and correct the activity */
3072 if( nposinf > 0 && nneginf > 0 )
3073 activity = (consdata->rhs + consdata->lhs) / 2;
3074 else if( nposinf > 0 )
3075 activity = SCIPinfinity(scip);
3076 else if( nneginf > 0 )
3077 activity = -SCIPinfinity(scip);
3078
3079 SCIPdebugMsg(scip, "corrected activity of linear constraint: %.15g\n", activity);
3080 }
3081
3082 if( activity == SCIP_INVALID ) /*lint !e777*/
3083 return activity;
3084 else if( activity < 0 )
3085 activity = MAX(activity, -SCIPinfinity(scip)); /*lint !e666*/
3086 else
3087 activity = MIN(activity, SCIPinfinity(scip)); /*lint !e666*/
3088
3089 return activity;
3090}
3091
3092/** calculates the feasibility of the linear constraint for given solution */
3093static
3095 SCIP* scip, /**< SCIP data structure */
3096 SCIP_CONSDATA* consdata, /**< linear constraint data */
3097 SCIP_SOL* sol /**< solution to get feasibility for, NULL to current solution */
3098 )
3099{
3100 SCIP_Real activity;
3101
3102 assert(scip != NULL);
3103 assert(consdata != NULL);
3104
3105 activity = consdataGetActivity(scip, consdata, sol);
3106
3107 if( activity == SCIP_INVALID ) /*lint !e777*/
3108 return -SCIPinfinity(scip);
3109
3110 return MIN(consdata->rhs - activity, activity - consdata->lhs);
3111}
3112
3113/** updates bit signatures after adding a single coefficient */
3114static
3116 SCIP_CONSDATA* consdata, /**< linear constraint data */
3117 int pos /**< position of coefficient to update signatures for */
3118 )
3119{
3120 uint64_t varsignature;
3121 SCIP_Real lb;
3122 SCIP_Real ub;
3123 SCIP_Real val;
3124
3125 assert(consdata != NULL);
3126 assert(consdata->validsignature);
3127
3128 varsignature = SCIPhashSignature64(SCIPvarGetIndex(consdata->vars[pos]));
3129 lb = SCIPvarGetLbGlobal(consdata->vars[pos]);
3130 ub = SCIPvarGetUbGlobal(consdata->vars[pos]);
3131 val = consdata->vals[pos];
3132 if( (val > 0.0 && ub > 0.0) || (val < 0.0 && lb < 0.0) )
3133 consdata->possignature |= varsignature;
3134 if( (val > 0.0 && lb < 0.0) || (val < 0.0 && ub > 0.0) )
3135 consdata->negsignature |= varsignature;
3136}
3137
3138/** calculates the bit signatures of the given constraint data */
3139static
3141 SCIP_CONSDATA* consdata /**< linear constraint data */
3142 )
3143{
3144 assert(consdata != NULL);
3145
3146 if( !consdata->validsignature )
3147 {
3148 int i;
3149
3150 consdata->validsignature = TRUE;
3151 consdata->possignature = 0;
3152 consdata->negsignature = 0;
3153 for( i = 0; i < consdata->nvars; ++i )
3154 consdataUpdateSignatures(consdata, i);
3155 }
3156}
3157
3158/** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
3159static
3161{ /*lint --e{715}*/
3162 SCIP_CONSDATA* consdata = (SCIP_CONSDATA*)dataptr;
3163 SCIP_VAR* var1;
3164 SCIP_VAR* var2;
3165
3166 assert(consdata != NULL);
3167 assert(0 <= ind1 && ind1 < consdata->nvars);
3168 assert(0 <= ind2 && ind2 < consdata->nvars);
3169
3170 var1 = consdata->vars[ind1];
3171 var2 = consdata->vars[ind2];
3172
3173 /* exactly one variable is binary */
3174 if( SCIPvarIsBinary(var1) != SCIPvarIsBinary(var2) )
3175 {
3176 return (SCIPvarIsBinary(var1) ? -1 : +1);
3177 }
3178 /* both variables are binary */
3179 else if( SCIPvarIsBinary(var1) )
3180 {
3181 return SCIPvarCompare(var1, var2);
3182 }
3183 else
3184 {
3185 SCIP_VARTYPE vartype1 = SCIPvarGetType(var1);
3186 SCIP_VARTYPE vartype2 = SCIPvarGetType(var2);
3187
3188 if( vartype1 < vartype2 )
3189 return -1;
3190 else if( vartype1 > vartype2 )
3191 return +1;
3192 else
3193 return SCIPvarCompare(var1, var2);
3194 }
3195}
3196
3197/** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
3198static
3199SCIP_DECL_SORTINDCOMP(consdataCompVarProp)
3200{ /*lint --e{715}*/
3201 SCIP_CONSDATA* consdata = (SCIP_CONSDATA*)dataptr;
3202 SCIP_VAR* var1;
3203 SCIP_VAR* var2;
3204
3205 assert(consdata != NULL);
3206 assert(0 <= ind1 && ind1 < consdata->nvars);
3207 assert(0 <= ind2 && ind2 < consdata->nvars);
3208
3209 var1 = consdata->vars[ind1];
3210 var2 = consdata->vars[ind2];
3211
3212 /* exactly one variable is binary */
3213 if( SCIPvarIsBinary(var1) != SCIPvarIsBinary(var2) )
3214 {
3215 return (SCIPvarIsBinary(var1) ? -1 : +1);
3216 }
3217 /* both variables are binary */
3218 else if( SCIPvarIsBinary(var1) )
3219 {
3220 SCIP_Real abscoef1 = REALABS(consdata->vals[ind1]);
3221 SCIP_Real abscoef2 = REALABS(consdata->vals[ind2]);
3222
3223 if( EPSGT(abscoef1, abscoef2, 1e-9) )
3224 return -1;
3225 else if( EPSGT(abscoef2, abscoef1, 1e-9) )
3226 return +1;
3227 else
3228 return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
3229 }
3230 else
3231 {
3232 SCIP_VARTYPE vartype1 = SCIPvarGetType(var1);
3233 SCIP_VARTYPE vartype2 = SCIPvarGetType(var2);
3234
3235 if( vartype1 < vartype2 )
3236 {
3237 return -1;
3238 }
3239 else if( vartype1 > vartype2 )
3240 {
3241 return +1;
3242 }
3243 else
3244 {
3245 /* both variables are continuous */
3246 if( !SCIPvarIsIntegral(var1) )
3247 {
3248 assert(!SCIPvarIsIntegral(var2));
3249 return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
3250 }
3251 else
3252 {
3253 SCIP_Real abscont1 = REALABS(consdata->vals[ind1] * (SCIPvarGetUbGlobal(var1) - SCIPvarGetLbGlobal(var1)));
3254 SCIP_Real abscont2 = REALABS(consdata->vals[ind2] * (SCIPvarGetUbGlobal(var2) - SCIPvarGetLbGlobal(var2)));
3255
3256 if( EPSGT(abscont1, abscont2, 1e-9) )
3257 return -1;
3258 else if( EPSGT(abscont2, abscont1, 1e-9) )
3259 return +1;
3260 else
3261 return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
3262 }
3263 }
3264 }
3265}
3266
3267/** permutes the constraint's variables according to a given permutation. */
3268static
3270 SCIP_CONSDATA* consdata, /**< the constraint data */
3271 int* perm, /**< the target permutation */
3272 int nvars /**< the number of variables */
3273 )
3274{ /*lint --e{715}*/
3275 SCIP_VAR* varv;
3276 SCIP_EVENTDATA* eventdatav;
3277 SCIP_Real valv;
3278 int v;
3279 int i;
3280 int nexti;
3281
3282 assert(perm != NULL);
3283 assert(consdata != NULL);
3284
3285 /* permute the variables in the linear constraint according to the target permutation */
3286 eventdatav = NULL;
3287 for( v = 0; v < nvars; ++v )
3288 {
3289 if( perm[v] != v )
3290 {
3291 varv = consdata->vars[v];
3292 valv = consdata->vals[v];
3293 if( consdata->eventdata != NULL )
3294 eventdatav = consdata->eventdata[v];
3295 i = v;
3296 do
3297 {
3298 assert(0 <= perm[i] && perm[i] < nvars);
3299 assert(perm[i] != i);
3300 consdata->vars[i] = consdata->vars[perm[i]];
3301 consdata->vals[i] = consdata->vals[perm[i]];
3302 if( consdata->eventdata != NULL )
3303 {
3304 consdata->eventdata[i] = consdata->eventdata[perm[i]];
3305 consdata->eventdata[i]->varpos = i;
3306 }
3307 nexti = perm[i];
3308 perm[i] = i;
3309 i = nexti;
3310 }
3311 while( perm[i] != v );
3312 consdata->vars[i] = varv;
3313 consdata->vals[i] = valv;
3314 if( consdata->eventdata != NULL )
3315 {
3316 consdata->eventdata[i] = eventdatav;
3317 consdata->eventdata[i]->varpos = i;
3318 }
3319 perm[i] = i;
3320 }
3321 }
3322#ifdef SCIP_DEBUG
3323 /* check sorting */
3324 for( v = 0; v < nvars; ++v )
3325 {
3326 assert(perm[v] == v);
3327 assert(consdata->eventdata == NULL || consdata->eventdata[v]->varpos == v);
3328 }
3329#endif
3330}
3331
3332/** sorts linear constraint's variables depending on the stage of the solving process:
3333 * - during PRESOLVING
3334 * sorts variables by binaries, integers, implicit integers, and continuous variables,
3335 * and the variables of the same type by non-decreasing variable index
3336 *
3337 * - during SOLVING
3338 * sorts variables of the remaining problem by binaries, integers, implicit integers, and continuous variables,
3339 * and binary and integer variables by their global max activity delta (within each group),
3340 * ties within a group are broken by problem index of the variable.
3341 *
3342 * This fastens the propagation time of the constraint handler.
3343 */
3344static
3346 SCIP* scip, /**< SCIP data structure */
3347 SCIP_CONSDATA* consdata /**< linear constraint data */
3348 )
3349{
3350 assert(scip != NULL);
3351 assert(consdata != NULL);
3352
3353 /* check if there are variables for sorting */
3354 if( consdata->nvars <= 1 )
3355 {
3356 consdata->indexsorted = TRUE;
3357 consdata->coefsorted = TRUE;
3358 consdata->nbinvars = (consdata->nvars == 1 ? (int)SCIPvarIsBinary(consdata->vars[0]) : 0);
3359 }
3360 else if( (!consdata->indexsorted && SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE)
3361 || (!consdata->coefsorted && SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE) )
3362 {
3363 int* perm;
3364 int v;
3365
3366 /* get temporary memory to store the sorted permutation */
3367 SCIP_CALL( SCIPallocBufferArray(scip, &perm, consdata->nvars) );
3368
3369 /* call sorting method */
3371 SCIPsort(perm, consdataCompVar, (void*)consdata, consdata->nvars);
3372 else
3373 SCIPsort(perm, consdataCompVarProp, (void*)consdata, consdata->nvars);
3374
3375 permSortConsdata(consdata, perm, consdata->nvars);
3376
3377 /* free temporary memory */
3378 SCIPfreeBufferArray(scip, &perm);
3379
3381 {
3382 consdata->indexsorted = FALSE;
3383 consdata->coefsorted = TRUE;
3384
3385 /* count binary variables in the sorted vars array */
3386 consdata->nbinvars = 0;
3387 for( v = 0; v < consdata->nvars; ++v )
3388 {
3389 if( SCIPvarIsBinary(consdata->vars[v]) )
3390 ++consdata->nbinvars;
3391 else
3392 break;
3393 }
3394 }
3395 else
3396 {
3397 consdata->indexsorted = TRUE;
3398 consdata->coefsorted = FALSE;
3399 }
3400 }
3401
3402 return SCIP_OKAY;
3403}
3404
3405
3406/*
3407 * local linear constraint handler methods
3408 */
3409
3410/** sets left hand side of linear constraint */
3411static
3413 SCIP* scip, /**< SCIP data structure */
3414 SCIP_CONS* cons, /**< linear constraint */
3415 SCIP_Real lhs /**< new left hand side */
3416 )
3417{
3418 SCIP_CONSDATA* consdata;
3419 SCIP_Bool locked;
3420 int i;
3421
3422 assert(scip != NULL);
3423 assert(cons != NULL);
3424
3425 /* adjust value to be not beyond infinity */
3426 if( SCIPisInfinity(scip, -lhs) )
3427 lhs = -SCIPinfinity(scip);
3428 else if( SCIPisInfinity(scip, lhs) )
3429 lhs = SCIPinfinity(scip);
3430
3431 consdata = SCIPconsGetData(cons);
3432 assert(consdata != NULL);
3433 assert(consdata->nvars == 0 || (consdata->vars != NULL && consdata->vals != NULL));
3434
3435 /* check whether the side is not changed */
3436 if( SCIPisEQ(scip, consdata->lhs, lhs) )
3437 return SCIP_OKAY;
3438
3439 assert(!SCIPisInfinity(scip, ABS(consdata->lhs)) || !SCIPisInfinity(scip, ABS(lhs)));
3440
3441 /* ensure that rhs >= lhs is satisfied without numerical tolerance */
3442 if( SCIPisEQ(scip, lhs, consdata->rhs) )
3443 {
3444 consdata->rhs = lhs;
3445 assert(consdata->row == NULL);
3446 }
3447
3448 locked = FALSE;
3449 for( i = 0; i < NLOCKTYPES && !locked; i++ )
3450 locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
3451
3452 /* if necessary, update the rounding locks of variables */
3453 if( locked )
3454 {
3455 if( SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, -lhs) )
3456 {
3457 SCIP_VAR** vars;
3458 SCIP_Real* vals;
3459 int v;
3460
3461 /* the left hand side switched from -infinity to a non-infinite value -> install rounding locks */
3462 vars = consdata->vars;
3463 vals = consdata->vals;
3464
3465 for( v = 0; v < consdata->nvars; ++v )
3466 {
3467 assert(vars[v] != NULL);
3468 assert(!SCIPisZero(scip, vals[v]));
3469
3470 if( SCIPisPositive(scip, vals[v]) )
3471 {
3472 SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3473 }
3474 else
3475 {
3476 SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3477 }
3478 }
3479 }
3480 else if( !SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -lhs) )
3481 {
3482 SCIP_VAR** vars;
3483 SCIP_Real* vals;
3484 int v;
3485
3486 /* the left hand side switched from a non-infinite value to -infinity -> remove rounding locks */
3487 vars = consdata->vars;
3488 vals = consdata->vals;
3489
3490 for( v = 0; v < consdata->nvars; ++v )
3491 {
3492 assert(vars[v] != NULL);
3493 assert(!SCIPisZero(scip, vals[v]));
3494
3495 if( SCIPisPositive(scip, vals[v]) )
3496 {
3497 SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3498 }
3499 else
3500 {
3501 SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3502 }
3503 }
3504 }
3505 }
3506
3507 /* 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 */
3508 if( !SCIPisInfinity(scip, ABS(lhs)) && SCIPisGT(scip, lhs, consdata->lhs) )
3509 {
3510 consdata->boundstightened = 0;
3511 consdata->presolved = FALSE;
3512 consdata->cliquesadded = FALSE;
3513 consdata->implsadded = FALSE;
3514
3515 /* mark the constraint for propagation */
3516 if( SCIPconsIsTransformed(cons) )
3517 {
3519 }
3520 }
3521
3522 /* set new left hand side and update constraint data */
3523 consdata->lhs = lhs;
3524 consdata->changed = TRUE;
3525 consdata->normalized = FALSE;
3526 consdata->upgradetried = FALSE;
3527 consdata->rangedrowpropagated = 0;
3528
3529 /* update the lhs of the LP row */
3530 if( consdata->row != NULL )
3531 {
3532 SCIP_CALL( SCIPchgRowLhs(scip, consdata->row, lhs) );
3533 }
3534
3535 return SCIP_OKAY;
3536}
3537
3538/** sets right hand side of linear constraint */
3539static
3541 SCIP* scip, /**< SCIP data structure */
3542 SCIP_CONS* cons, /**< linear constraint */
3543 SCIP_Real rhs /**< new right hand side */
3544 )
3545{
3546 SCIP_CONSDATA* consdata;
3547 SCIP_Bool locked;
3548 int i;
3549
3550 assert(scip != NULL);
3551 assert(cons != NULL);
3552
3553 /* adjust value to be not beyond infinity */
3554 if( SCIPisInfinity(scip, rhs) )
3555 rhs = SCIPinfinity(scip);
3556 else if( SCIPisInfinity(scip, -rhs) )
3557 rhs = -SCIPinfinity(scip);
3558
3559 consdata = SCIPconsGetData(cons);
3560 assert(consdata != NULL);
3561 assert(consdata->nvars == 0 || (consdata->vars != NULL && consdata->vals != NULL));
3562
3563 /* check whether the side is not changed */
3564 if( SCIPisEQ(scip, consdata->rhs, rhs) )
3565 return SCIP_OKAY;
3566
3567 assert(!SCIPisInfinity(scip, ABS(consdata->rhs)) || !SCIPisInfinity(scip, ABS(rhs)));
3568
3569 /* ensure that rhs >= lhs is satisfied without numerical tolerance */
3570 if( SCIPisEQ(scip, rhs, consdata->lhs) )
3571 {
3572 consdata->lhs = rhs;
3573 assert(consdata->row == NULL);
3574 }
3575
3576 locked = FALSE;
3577 for( i = 0; i < NLOCKTYPES && !locked; i++ )
3578 locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
3579
3580 /* if necessary, update the rounding locks of variables */
3581 if( locked )
3582 {
3583 assert(SCIPconsIsTransformed(cons));
3584
3585 if( SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, rhs) )
3586 {
3587 SCIP_VAR** vars;
3588 SCIP_Real* vals;
3589 int v;
3590
3591 /* the right hand side switched from infinity to a non-infinite value -> install rounding locks */
3592 vars = consdata->vars;
3593 vals = consdata->vals;
3594
3595 for( v = 0; v < consdata->nvars; ++v )
3596 {
3597 assert(vars[v] != NULL);
3598 assert(!SCIPisZero(scip, vals[v]));
3599
3600 if( SCIPisPositive(scip, vals[v]) )
3601 {
3602 SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3603 }
3604 else
3605 {
3606 SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3607 }
3608 }
3609 }
3610 else if( !SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, rhs) )
3611 {
3612 SCIP_VAR** vars;
3613 SCIP_Real* vals;
3614 int v;
3615
3616 /* the right hand side switched from a non-infinite value to infinity -> remove rounding locks */
3617 vars = consdata->vars;
3618 vals = consdata->vals;
3619
3620 for( v = 0; v < consdata->nvars; ++v )
3621 {
3622 assert(vars[v] != NULL);
3623 assert(!SCIPisZero(scip, vals[v]));
3624
3625 if( SCIPisPositive(scip, vals[v]) )
3626 {
3627 SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
3628 }
3629 else
3630 {
3631 SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
3632 }
3633 }
3634 }
3635 }
3636
3637 /* 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 */
3638 if( !SCIPisInfinity(scip, ABS(rhs)) && SCIPisLT(scip, rhs, consdata->rhs) )
3639 {
3640 consdata->boundstightened = 0;
3641 consdata->presolved = FALSE;
3642 consdata->cliquesadded = FALSE;
3643 consdata->implsadded = FALSE;
3644
3645 /* mark the constraint for propagation */
3646 if( SCIPconsIsTransformed(cons) )
3647 {
3649 }
3650 }
3651
3652 /* set new right hand side and update constraint data */
3653 consdata->rhs = rhs;
3654 consdata->changed = TRUE;
3655 consdata->normalized = FALSE;
3656 consdata->upgradetried = FALSE;
3657 consdata->rangedrowpropagated = 0;
3658
3659 /* update the rhs of the LP row */
3660 if( consdata->row != NULL )
3661 {
3662 SCIP_CALL( SCIPchgRowRhs(scip, consdata->row, rhs) );
3663 }
3664
3665 return SCIP_OKAY;
3666}
3667
3668/** adds coefficient in linear constraint */
3669static
3671 SCIP* scip, /**< SCIP data structure */
3672 SCIP_CONS* cons, /**< linear constraint */
3673 SCIP_VAR* var, /**< variable of constraint entry */
3674 SCIP_Real val /**< coefficient of constraint entry */
3675 )
3676{
3677 SCIP_CONSDATA* consdata;
3678 SCIP_Bool transformed;
3679
3680 assert(scip != NULL);
3681 assert(cons != NULL);
3682 assert(var != NULL);
3683
3684 /* relaxation-only variables must not be used in checked or enforced constraints */
3685 assert(!SCIPvarIsRelaxationOnly(var) || (!SCIPconsIsChecked(cons) && !SCIPconsIsEnforced(cons)));
3686 consdata = SCIPconsGetData(cons);
3687 assert(consdata != NULL);
3688
3689 /* are we in the transformed problem? */
3690 transformed = SCIPconsIsTransformed(cons);
3691
3692 /* always use transformed variables in transformed constraints */
3693 if( transformed )
3694 {
3695 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
3696 }
3697 assert(var != NULL);
3698 assert(transformed == SCIPvarIsTransformed(var));
3699
3700 SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
3701 consdata->vars[consdata->nvars] = var;
3702 consdata->vals[consdata->nvars] = val;
3703 consdata->nvars++;
3704
3705 /* capture variable */
3706 SCIP_CALL( SCIPcaptureVar(scip, var) );
3707
3708 /* if we are in transformed problem, the variable needs an additional event data */
3709 if( transformed )
3710 {
3711 if( consdata->eventdata != NULL )
3712 {
3713 SCIP_CONSHDLR* conshdlr;
3714 SCIP_CONSHDLRDATA* conshdlrdata;
3715
3716 /* check for event handler */
3717 conshdlr = SCIPconsGetHdlr(cons);
3718 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3719 assert(conshdlrdata != NULL);
3720 assert(conshdlrdata->eventhdlr != NULL);
3721
3722 /* initialize eventdata array */
3723 consdata->eventdata[consdata->nvars-1] = NULL;
3724
3725 /* catch bound change events of variable */
3726 SCIP_CALL( consCatchEvent(scip, cons, conshdlrdata->eventhdlr, consdata->nvars-1) );
3727 }
3728
3729 /* update minimum and maximum activities */
3730 if( !SCIPisZero(scip, val) )
3731 consdataUpdateAddCoef(scip, consdata, var, val, FALSE);
3732 }
3733
3734 /* install rounding locks for new variable with non-zero coefficient */
3735 if( !SCIPisZero(scip, val) )
3736 {
3737 SCIP_CALL( lockRounding(scip, cons, var, val) );
3738 }
3739
3740 /* mark the constraint for propagation */
3741 if( transformed )
3742 {
3744 }
3745
3746 consdata->boundstightened = 0;
3747 consdata->presolved = FALSE;
3748 consdata->removedfixings = consdata->removedfixings && SCIPvarIsActive(var);
3749
3750 if( consdata->validsignature )
3751 consdataUpdateSignatures(consdata, consdata->nvars-1);
3752
3753 consdata->changed = TRUE;
3754 consdata->normalized = FALSE;
3755 consdata->upgradetried = FALSE;
3756 consdata->cliquesadded = FALSE;
3757 consdata->implsadded = FALSE;
3758 consdata->rangedrowpropagated = 0;
3759 consdata->merged = FALSE;
3760
3761 if( consdata->nvars == 1 )
3762 {
3763 consdata->indexsorted = TRUE;
3764 consdata->coefsorted = TRUE;
3765 }
3766 else
3767 {
3769 {
3770 consdata->indexsorted = consdata->indexsorted && (consdataCompVar((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
3771 consdata->coefsorted = FALSE;
3772 }
3773 else
3774 {
3775 consdata->indexsorted = FALSE;
3776 consdata->coefsorted = consdata->coefsorted && (consdataCompVarProp((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
3777 }
3778 }
3779
3780 /* update hascontvar and hasnonbinvar flags */
3781 if( consdata->hasnonbinvalid && !consdata->hascontvar )
3782 {
3783 SCIP_VARTYPE vartype = SCIPvarGetType(var);
3784
3785 if( vartype != SCIP_VARTYPE_BINARY )
3786 {
3787 consdata->hasnonbinvar = TRUE;
3788
3789 if( vartype == SCIP_VARTYPE_CONTINUOUS )
3790 consdata->hascontvar = TRUE;
3791 }
3792 }
3793
3794 /* add the new coefficient to the LP row */
3795 if( consdata->row != NULL )
3796 {
3797 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, val) );
3798 }
3799
3800 return SCIP_OKAY;
3801}
3802
3803/** deletes coefficient at given position from linear constraint data */
3804static
3806 SCIP* scip, /**< SCIP data structure */
3807 SCIP_CONS* cons, /**< linear constraint */
3808 int pos /**< position of coefficient to delete */
3809 )
3810{
3811 SCIP_CONSDATA* consdata;
3812 SCIP_VAR* var;
3813 SCIP_Real val;
3814
3815 assert(scip != NULL);
3816 assert(cons != NULL);
3817
3818 consdata = SCIPconsGetData(cons);
3819 assert(consdata != NULL);
3820 assert(0 <= pos && pos < consdata->nvars);
3821
3822 var = consdata->vars[pos];
3823 val = consdata->vals[pos];
3824 assert(var != NULL);
3825
3826 /* remove rounding locks for deleted variable with non-zero coefficient */
3827 if( !SCIPisZero(scip, val) )
3828 {
3829 SCIP_CALL( unlockRounding(scip, cons, var, val) );
3830 }
3831
3832 /* if we are in transformed problem, delete the event data of the variable */
3833 if( SCIPconsIsTransformed(cons) )
3834 {
3835 SCIP_CONSHDLR* conshdlr;
3836 SCIP_CONSHDLRDATA* conshdlrdata;
3837
3838 /* check for event handler */
3839 conshdlr = SCIPconsGetHdlr(cons);
3840 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3841 assert(conshdlrdata != NULL);
3842 assert(conshdlrdata->eventhdlr != NULL);
3843
3844 /* drop bound change events of variable */
3845 if( consdata->eventdata != NULL )
3846 {
3847 SCIP_CALL( consDropEvent(scip, cons, conshdlrdata->eventhdlr, pos) );
3848 assert(consdata->eventdata[pos] == NULL);
3849 }
3850 }
3851
3852 /* move the last variable to the free slot */
3853 if( pos != consdata->nvars - 1 )
3854 {
3855 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
3856 consdata->vals[pos] = consdata->vals[consdata->nvars-1];
3857
3858 if( consdata->eventdata != NULL )
3859 {
3860 consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
3861 assert(consdata->eventdata[pos] != NULL);
3862 consdata->eventdata[pos]->varpos = pos;
3863 }
3864
3865 consdata->indexsorted = consdata->indexsorted && (pos + 2 >= consdata->nvars);
3866 consdata->coefsorted = consdata->coefsorted && (pos + 2 >= consdata->nvars);
3867 }
3868 consdata->nvars--;
3869
3870 /* if at most one variable is left, the activities should be recalculated (to correspond exactly to the bounds
3871 * of the remaining variable, or give exactly 0.0)
3872 */
3873 if( consdata->nvars <= 1 )
3875 else
3876 {
3877 /* if we are in transformed problem, update minimum and maximum activities */
3878 if( SCIPconsIsTransformed(cons) && !SCIPisZero(scip, val) )
3879 consdataUpdateDelCoef(scip, consdata, var, val, TRUE);
3880 }
3881
3882 /* mark the constraint for propagation */
3883 if( SCIPconsIsTransformed(cons) )
3884 {
3886 }
3887
3888 consdata->boundstightened = 0;
3889 consdata->presolved = FALSE;
3890 consdata->validsignature = FALSE;
3891 consdata->changed = TRUE;
3892 consdata->normalized = FALSE;
3893 consdata->upgradetried = FALSE;
3894 consdata->cliquesadded = FALSE;
3895 consdata->implsadded = FALSE;
3896 consdata->rangedrowpropagated = 0;
3897
3898 /* check if hasnonbinvar flag might be incorrect now */
3899 if( consdata->hasnonbinvar && SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
3900 {
3901 consdata->hasnonbinvalid = FALSE;
3902 }
3903
3904 /* delete coefficient from the LP row */
3905 if( consdata->row != NULL )
3906 {
3907 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, -val) );
3908 }
3909
3910 /* release variable */
3911 SCIP_CALL( SCIPreleaseVar(scip, &var) );
3912
3913 return SCIP_OKAY;
3914}
3915
3916/** changes coefficient value at given position of linear constraint data */
3917static
3919 SCIP* scip, /**< SCIP data structure */
3920 SCIP_CONS* cons, /**< linear constraint */
3921 int pos, /**< position of coefficient to delete */
3922 SCIP_Real newval /**< new value of coefficient */
3923 )
3924{
3925 SCIP_CONSDATA* consdata;
3926 SCIP_VAR* var;
3927 SCIP_Real val;
3928 SCIP_Bool locked;
3929 int i;
3930
3931 assert(scip != NULL);
3932 assert(cons != NULL);
3933 consdata = SCIPconsGetData(cons);
3934 assert(consdata != NULL);
3935 assert(0 <= pos && pos < consdata->nvars);
3936 var = consdata->vars[pos];
3937 assert(var != NULL);
3938 assert(SCIPvarIsTransformed(var) == SCIPconsIsTransformed(cons));
3939 val = consdata->vals[pos];
3940 assert(!SCIPisZero(scip, val) || !SCIPisZero(scip, newval));
3941
3942 locked = FALSE;
3943 for( i = 0; i < NLOCKTYPES && !locked; i++ )
3944 locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
3945
3946 /* if necessary, update the rounding locks of the variable */
3947 if( locked && ( !SCIPisNegative(scip, val) || !SCIPisNegative(scip, newval) )
3948 && ( !SCIPisPositive(scip, val) || !SCIPisPositive(scip, newval) ) )
3949 {
3950 assert(SCIPconsIsTransformed(cons));
3951
3952 /* remove rounding locks for variable with old non-zero coefficient */
3953 if( !SCIPisZero(scip, val) )
3954 {
3955 SCIP_CALL( unlockRounding(scip, cons, var, val) );
3956 }
3957
3958 /* install rounding locks for variable with new non-zero coefficient */
3959 if( !SCIPisZero(scip, newval) )
3960 {
3961 SCIP_CALL( lockRounding(scip, cons, var, newval) );
3962 }
3963 }
3964
3965 /* change the value */
3966 consdata->vals[pos] = newval;
3967
3968 if( consdata->coefsorted )
3969 {
3970 if( pos > 0 )
3971 consdata->coefsorted = (consdataCompVarProp((void*)consdata, pos - 1, pos) <= 0);
3972 if( consdata->coefsorted && pos < consdata->nvars - 1 )
3973 consdata->coefsorted = (consdataCompVarProp((void*)consdata, pos, pos + 1) <= 0);
3974 }
3975
3976 /* update minimum and maximum activities */
3977 if( SCIPconsIsTransformed(cons) )
3978 {
3979 if( SCIPisZero(scip, val) )
3980 consdataUpdateAddCoef(scip, consdata, var, newval, TRUE);
3981 else if( SCIPisZero(scip, newval) )
3982 consdataUpdateDelCoef(scip, consdata, var, val, TRUE);
3983 else
3984 consdataUpdateChgCoef(scip, consdata, var, val, newval, TRUE);
3985 }
3986
3987 /* mark the constraint for propagation */
3988 if( SCIPconsIsTransformed(cons) )
3989 {
3991 }
3992
3993 consdata->boundstightened = 0;
3994 consdata->presolved = FALSE;
3995 consdata->validsignature = consdata->validsignature && (newval * val > 0.0);
3996 consdata->changed = TRUE;
3997 consdata->normalized = FALSE;
3998 consdata->upgradetried = FALSE;
3999 consdata->cliquesadded = FALSE;
4000 consdata->implsadded = FALSE;
4001 consdata->rangedrowpropagated = 0;
4002
4003 return SCIP_OKAY;
4004}
4005
4006/** scales a linear constraint with a constant scalar */
4007static
4009 SCIP* scip, /**< SCIP data structure */
4010 SCIP_CONS* cons, /**< linear constraint to scale */
4011 SCIP_Real scalar /**< value to scale constraint with */
4012 )
4013{
4014 SCIP_CONSDATA* consdata;
4015 SCIP_Real newval;
4016 SCIP_Real absscalar;
4017 int i;
4018
4019 assert(scip != NULL);
4020 assert(cons != NULL);
4021
4022 consdata = SCIPconsGetData(cons);
4023 assert(consdata != NULL);
4024 assert(consdata->row == NULL);
4025 assert(scalar != 1.0);
4026
4027 if( (!SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -consdata->lhs * scalar))
4028 || (!SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, consdata->rhs * scalar)) )
4029 {
4030 SCIPwarningMessage(scip, "skipped scaling for linear constraint <%s> to avoid numerical troubles (scalar: %.15g)\n",
4031 SCIPconsGetName(cons), scalar);
4032
4033 return SCIP_OKAY;
4034 }
4035
4036 /* scale the coefficients */
4037 for( i = consdata->nvars - 1; i >= 0; --i )
4038 {
4039 newval = scalar * consdata->vals[i];
4040
4041 /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
4042 * flooring down our new value
4043 */
4044 if( SCIPisScalingIntegral(scip, consdata->vals[i], scalar) )
4045 newval = SCIPfeasFloor(scip, newval + 0.5);
4046
4047 if( SCIPisZero(scip, newval) )
4048 {
4049 SCIPwarningMessage(scip, "coefficient %.15g of variable <%s> in linear constraint <%s> scaled to zero (scalar: %.15g)\n",
4050 consdata->vals[i], SCIPvarGetName(consdata->vars[i]), SCIPconsGetName(cons), scalar);
4051 SCIP_CALL( delCoefPos(scip, cons, i) );
4052 }
4053 else
4054 consdata->vals[i] = newval;
4055 }
4056
4057 /* scale the sides */
4058 if( scalar < 0.0 )
4059 {
4060 SCIP_Real lhs;
4061
4062 lhs = consdata->lhs;
4063 consdata->lhs = -consdata->rhs;
4064 consdata->rhs = -lhs;
4065 }
4066 absscalar = REALABS(scalar);
4067 if( !SCIPisInfinity(scip, -consdata->lhs) )
4068 {
4069 newval = absscalar * consdata->lhs;
4070
4071 /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
4072 * flooring down our new value
4073 */
4074 if( SCIPisScalingIntegral(scip, consdata->lhs, absscalar) )
4075 consdata->lhs = SCIPfeasFloor(scip, newval + 0.5);
4076 else
4077 consdata->lhs = newval;
4078 }
4079 if( !SCIPisInfinity(scip, consdata->rhs) )
4080 {
4081 newval = absscalar * consdata->rhs;
4082
4083 /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasCeil, we subtract 0.5 before ceiling up
4084 * our new value
4085 */
4086 if( SCIPisScalingIntegral(scip, consdata->rhs, absscalar) )
4087 consdata->rhs = SCIPfeasCeil(scip, newval - 0.5);
4088 else
4089 consdata->rhs = newval;
4090 }
4091
4093 consdata->cliquesadded = FALSE;
4094 consdata->implsadded = FALSE;
4095
4096 return SCIP_OKAY;
4097}
4098
4099/** perform deletion of variables in all constraints of the constraint handler */
4100static
4102 SCIP* scip, /**< SCIP data structure */
4103 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4104 SCIP_CONS** conss, /**< array of constraints */
4105 int nconss /**< number of constraints */
4106 )
4107{
4108 SCIP_CONSDATA* consdata;
4109 int i;
4110 int v;
4111
4112 assert(scip != NULL);
4113 assert(conshdlr != NULL);
4114 assert(conss != NULL);
4115 assert(nconss >= 0);
4116 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4117
4118 /* iterate over all constraints */
4119 for( i = 0; i < nconss; i++ )
4120 {
4121 consdata = SCIPconsGetData(conss[i]);
4122
4123 /* constraint is marked, that some of its variables were deleted */
4124 if( consdata->varsdeleted )
4125 {
4126 /* iterate over all variables of the constraint and delete them from the constraint */
4127 for( v = consdata->nvars - 1; v >= 0; --v )
4128 {
4129 if( SCIPvarIsDeleted(consdata->vars[v]) )
4130 {
4131 SCIP_CALL( delCoefPos(scip, conss[i], v) );
4132 }
4133 }
4134 consdata->varsdeleted = FALSE;
4135 }
4136 }
4137
4138 return SCIP_OKAY;
4139}
4140
4141
4142/** normalizes a linear constraint with the following rules:
4143 * - if all coefficients have them same absolute value, change them to (-)1.0
4144 * - multiplication with +1 or -1:
4145 * Apply the following rules in the given order, until the sign of the factor is determined. Later rules only apply,
4146 * if the current rule doesn't determine the sign):
4147 * 1. the right hand side must not be negative
4148 * 2. the right hand side must not be infinite
4149 * 3. the absolute value of the right hand side must be greater than that of the left hand side
4150 * 4. the number of positive coefficients must not be smaller than the number of negative coefficients
4151 * 5. multiply with +1
4152 * - rationals to integrals
4153 * Try to identify a rational representation of the fractional coefficients, and multiply all coefficients
4154 * by the smallest common multiple of all denominators to get integral coefficients.
4155 * Forbid large denominators due to numerical stability.
4156 * - division by greatest common divisor
4157 * If all coefficients are integral, divide them by the greatest common divisor.
4158 */
4159static
4161 SCIP* scip, /**< SCIP data structure */
4162 SCIP_CONS* cons, /**< linear constraint to normalize */
4163 SCIP_Bool* infeasible /**< pointer to store whether infeasibility was detected */
4164 )
4165{
4166 SCIP_CONSDATA* consdata;
4167 SCIP_Real* vals;
4168 SCIP_Longint scm;
4169 SCIP_Longint nominator;
4170 SCIP_Longint denominator;
4171 SCIP_Longint gcd;
4172 SCIP_Longint maxmult;
4173 SCIP_Real epsilon;
4174 SCIP_Real feastol;
4175 SCIP_Real maxabsval;
4176 SCIP_Real minabsval;
4177 SCIP_Bool success;
4178 SCIP_Bool onlyintegral;
4179 int nvars;
4180 int mult;
4181 int nposcoeffs;
4182 int nnegcoeffs;
4183 int i;
4184
4185 assert(scip != NULL);
4186 assert(cons != NULL);
4187 assert(infeasible != NULL);
4188
4189 *infeasible = FALSE;
4190
4191 /* we must not change a modifiable constraint in any way */
4192 if( SCIPconsIsModifiable(cons) )
4193 return SCIP_OKAY;
4194
4195 /* get constraint data */
4196 consdata = SCIPconsGetData(cons);
4197 assert(consdata != NULL);
4198
4199 /* check, if the constraint is already normalized */
4200 if( consdata->normalized )
4201 return SCIP_OKAY;
4202
4203 /* get coefficient arrays */
4204 vals = consdata->vals;
4205 nvars = consdata->nvars;
4206 assert(nvars == 0 || vals != NULL);
4207
4208 if( nvars == 0 )
4209 {
4210 consdata->normalized = TRUE;
4211 return SCIP_OKAY;
4212 }
4213
4214 assert(vals != NULL);
4215
4216 /* get maximum and minimum absolute coefficient */
4217 maxabsval = consdataGetMaxAbsval(consdata);
4218 minabsval = consdataGetMinAbsval(consdata);
4219
4220 /* return if scaling by maxval will eliminate coefficients */
4221 if( SCIPisZero(scip, minabsval/maxabsval) )
4222 return SCIP_OKAY;
4223
4224 /* return if scaling by maxval will eliminate or generate non-zero sides */
4225 if( !SCIPisInfinity(scip, consdata->lhs) && SCIPisFeasZero(scip, consdata->lhs) != SCIPisFeasZero(scip, consdata->lhs/maxabsval) )
4226 return SCIP_OKAY;
4227 if( !SCIPisInfinity(scip, consdata->rhs) && SCIPisFeasZero(scip, consdata->rhs) != SCIPisFeasZero(scip, consdata->rhs/maxabsval) )
4228 return SCIP_OKAY;
4229
4230 /* check if not all absolute coefficients are near 1.0 but scaling could do */
4231 if( SCIPisLT(scip, minabsval, 1.0) != SCIPisGT(scip, maxabsval, 1.0) )
4232 {
4233 SCIP_Real scalar;
4234
4235 /* calculate scale of the average minimum and maximum absolute coefficient to 1.0 */
4236 scalar = 2.0 / (minabsval + maxabsval);
4237
4238 /* check if all scaled absolute coefficients are near 1.0
4239 * we can relax EQ(x,1.0) to LE(x,1.0), as LT(x,1.0) is not possible
4240 */
4241 if( SCIPisLE(scip, scalar * maxabsval, 1.0) )
4242 {
4243 SCIPdebugMsg(scip, "divide linear constraint with %g, because all coefficients are in absolute value the same\n", maxabsval);
4245 SCIP_CALL( scaleCons(scip, cons, scalar) );
4246
4247 /* get new consdata information, because scaleCons() might have deleted variables */
4248 vals = consdata->vals;
4249 nvars = consdata->nvars;
4250
4251 assert(nvars == 0 || vals != NULL);
4252 }
4253 }
4254
4255 /* nvars might have changed */
4256 if( nvars == 0 )
4257 {
4258 consdata->normalized = TRUE;
4259 return SCIP_OKAY;
4260 }
4261
4262 assert(vals != NULL);
4263
4264 /* calculate the maximal multiplier for common divisor calculation:
4265 * |p/q - val| < epsilon and q < feastol/epsilon => |p - q*val| < feastol
4266 * which means, a value of feastol/epsilon should be used as maximal multiplier;
4267 * additionally, we don't want to scale the constraint if this would lead to too
4268 * large coefficients
4269 */
4270 epsilon = SCIPepsilon(scip) * 0.9; /* slightly decrease epsilon to be safe in rational conversion below */
4271 feastol = SCIPfeastol(scip);
4272 maxmult = (SCIP_Longint)(feastol/epsilon + feastol);
4273
4274 if( !consdata->hasnonbinvalid )
4275 consdataCheckNonbinvar(consdata);
4276
4277 /* get maximum absolute coefficient */
4278 maxabsval = consdataGetMaxAbsval(consdata);
4279
4280 /* if all variables are of integral type we will allow a greater multiplier */
4281 if( !consdata->hascontvar )
4282 maxmult = MIN(maxmult, (SCIP_Longint) (MAXSCALEDCOEFINTEGER / MAX(maxabsval, 1.0))); /*lint !e835*/
4283 else
4284 maxmult = MIN(maxmult, (SCIP_Longint) (MAXSCALEDCOEF / MAX(maxabsval, 1.0))); /*lint !e835*/
4285
4286 /*
4287 * multiplication with +1 or -1
4288 */
4289 mult = 0;
4290
4291 /* 1. the right hand side must not be negative */
4292 if( SCIPisPositive(scip, consdata->lhs) )
4293 mult = +1;
4294 else if( SCIPisNegative(scip, consdata->rhs) )
4295 mult = -1;
4296
4297 if( mult == 0 )
4298 {
4299 /* 2. the right hand side must not be infinite */
4300 if( SCIPisInfinity(scip, -consdata->lhs) )
4301 mult = +1;
4302 else if( SCIPisInfinity(scip, consdata->rhs) )
4303 mult = -1;
4304 }
4305
4306 if( mult == 0 )
4307 {
4308 /* 3. the absolute value of the right hand side must be greater than that of the left hand side */
4309 if( SCIPisGT(scip, REALABS(consdata->rhs), REALABS(consdata->lhs)) )
4310 mult = +1;
4311 else if( SCIPisLT(scip, REALABS(consdata->rhs), REALABS(consdata->lhs)) )
4312 mult = -1;
4313 }
4314
4315 if( mult == 0 )
4316 {
4317 /* 4. the number of positive coefficients must not be smaller than the number of negative coefficients */
4318 nposcoeffs = 0;
4319 nnegcoeffs = 0;
4320 for( i = 0; i < nvars; ++i )
4321 {
4322 if( vals[i] > 0.0 )
4323 nposcoeffs++;
4324 else
4325 nnegcoeffs++;
4326 }
4327 if( nposcoeffs > nnegcoeffs )
4328 mult = +1;
4329 else if( nposcoeffs < nnegcoeffs )
4330 mult = -1;
4331 }
4332
4333 if( mult == 0 )
4334 {
4335 /* 5. multiply with +1 */
4336 mult = +1;
4337 }
4338
4339 assert(mult == +1 || mult == -1);
4340 if( mult == -1 )
4341 {
4342 /* scale the constraint with -1 */
4343 SCIPdebugMsg(scip, "multiply linear constraint with -1.0\n");
4345 SCIP_CALL( scaleCons(scip, cons, -1.0) );
4346
4347 /* scalecons() can delete variables, but scaling with -1 should not do that */
4348 assert(nvars == consdata->nvars);
4349 }
4350
4351 /*
4352 * rationals to integrals
4353 *
4354 * @todo try scaling only on behalf of non-continuous variables
4355 */
4356 success = TRUE;
4357 scm = 1;
4358 for( i = 0; i < nvars && success && scm <= maxmult; ++i )
4359 {
4360 if( !SCIPisIntegral(scip, vals[i]) )
4361 {
4362 /* epsilon has been slightly decreased above - to be on the safe side */
4363 success = SCIPrealToRational(vals[i], -epsilon, epsilon , maxmult, &nominator, &denominator);
4364 if( success )
4365 scm = SCIPcalcSmaComMul(scm, denominator);
4366 }
4367 }
4368 assert(scm >= 1);
4369
4370 /* it might be that we have really big coefficients, but all are integral, in that case we want to divide them by
4371 * their greatest common divisor
4372 */
4373 onlyintegral = TRUE;
4374 if( scm == 1 )
4375 {
4376 for( i = nvars - 1; i >= 0; --i )
4377 {
4378 if( !SCIPisIntegral(scip, vals[i]) )
4379 {
4380 onlyintegral = FALSE;
4381 break;
4382 }
4383 }
4384 }
4385
4386 success = success && (scm <= maxmult || (scm == 1 && onlyintegral));
4387 if( success && scm != 1 )
4388 {
4389 /* scale the constraint with the smallest common multiple of all denominators */
4390 SCIPdebugMsg(scip, "scale linear constraint with %" SCIP_LONGINT_FORMAT " to make coefficients integral\n", scm);
4392 SCIP_CALL( scaleCons(scip, cons, (SCIP_Real)scm) );
4393
4394 if( consdata->validmaxabsval )
4395 {
4396 consdata->maxabsval *= REALABS((SCIP_Real)scm);
4397 if( !SCIPisIntegral(scip, consdata->maxabsval) )
4398 {
4399 consdata->validmaxabsval = FALSE;
4400 consdata->maxabsval = SCIP_INVALID;
4401 consdataCalcMaxAbsval(consdata);
4402 }
4403 }
4404
4405 if( consdata->validminabsval )
4406 {
4407 consdata->minabsval *= REALABS((SCIP_Real)scm);
4408 if( !SCIPisIntegral(scip, consdata->minabsval) )
4409 {
4410 consdata->validminabsval = FALSE;
4411 consdata->minabsval = SCIP_INVALID;
4412 consdataCalcMinAbsval(consdata);
4413 }
4414 }
4415
4416 /* get new consdata information, because scalecons() might have deleted variables */
4417 vals = consdata->vals;
4418 nvars = consdata->nvars;
4419 assert(nvars == 0 || vals != NULL);
4420 }
4421
4422 /*
4423 * division by greatest common divisor
4424 */
4425 if( success && nvars >= 1 )
4426 {
4427 /* all coefficients are integral: divide them by their greatest common divisor */
4428 assert(SCIPisIntegral(scip, vals[0]));
4429
4430 gcd = (SCIP_Longint)(REALABS(vals[0]) + feastol);
4431 for( i = 1; i < nvars && gcd > 1; ++i )
4432 {
4433 assert(SCIPisIntegral(scip, vals[i]));
4434 gcd = SCIPcalcGreComDiv(gcd, (SCIP_Longint)(REALABS(vals[i]) + feastol));
4435 }
4436
4437 if( gcd > 1 )
4438 {
4439 /* since the lhs/rhs is not respected for gcd calculation it can happen that we detect infeasibility */
4440 if( !consdata->hascontvar && onlyintegral )
4441 {
4442 if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) && !SCIPisFeasIntegral(scip, consdata->rhs / gcd) )
4443 {
4444 *infeasible = TRUE;
4445
4446 SCIPdebugMsg(scip, "detected infeasibility of constraint after scaling with gcd=%" SCIP_LONGINT_FORMAT ":\n", gcd);
4448
4449 return SCIP_OKAY;
4450 }
4451 }
4452
4453 /* divide the constraint by the greatest common divisor of the coefficients */
4454 SCIPdebugMsg(scip, "divide linear constraint by greatest common divisor %" SCIP_LONGINT_FORMAT "\n", gcd);
4456 SCIP_CALL( scaleCons(scip, cons, 1.0/(SCIP_Real)gcd) );
4457
4458 if( consdata->validmaxabsval )
4459 {
4460 consdata->maxabsval /= REALABS((SCIP_Real)gcd);
4461 }
4462 if( consdata->validminabsval )
4463 {
4464 consdata->minabsval /= REALABS((SCIP_Real)gcd);
4465 }
4466 }
4467 }
4468
4469 /* mark constraint to be normalized */
4470 consdata->normalized = TRUE;
4471
4472 SCIPdebugMsg(scip, "normalized constraint:\n");
4474
4475 return SCIP_OKAY;
4476}
4477
4478/** replaces multiple occurrences of a variable by a single non-zero coefficient */
4479static
4481 SCIP* scip, /**< SCIP data structure */
4482 SCIP_CONS* cons /**< linear constraint */
4483 )
4484{
4485 SCIP_CONSDATA* consdata;
4486 SCIP_VAR* var;
4487 SCIP_Real valsum;
4488 int v;
4489
4490 assert(scip != NULL);
4491 assert(cons != NULL);
4492
4493 consdata = SCIPconsGetData(cons);
4494 assert(consdata != NULL);
4495
4496 if( consdata->merged )
4497 return SCIP_OKAY;
4498
4499 /* sort the constraint */
4500 SCIP_CALL( consdataSort(scip, consdata) );
4501
4502 v = consdata->nvars - 1;
4503
4504 /* go backwards through the constraint looking for multiple occurrences of the same variable;
4505 * backward direction is necessary, since delCoefPos() modifies the given position and
4506 * the subsequent ones
4507 */
4508 while( v >= 0 )
4509 {
4510 var = consdata->vars[v];
4511 valsum = consdata->vals[v];
4512
4513 /* sum multiple occurrences */
4514 while( v >= 1 && consdata->vars[v-1] == var )
4515 {
4516 SCIP_CALL( delCoefPos(scip, cons, v) );
4517 --v;
4518 valsum += consdata->vals[v];
4519 }
4520
4521 assert(consdata->vars[v] == var);
4522
4523 /* modify the last existing occurrence of the variable */
4524 if( SCIPisZero(scip, valsum) )
4525 {
4526 SCIP_CALL( delCoefPos(scip, cons, v) );
4527 }
4528 else if( valsum != consdata->vals[v] ) /*lint !e777*/
4529 {
4530 SCIP_CALL( chgCoefPos(scip, cons, v, valsum) );
4531 }
4532
4533 --v;
4534 }
4535
4536 consdata->merged = TRUE;
4537
4538 return SCIP_OKAY;
4539}
4540
4541/** replaces all fixed and aggregated variables by their non-fixed counterparts */
4542static
4544 SCIP* scip, /**< SCIP data structure */
4545 SCIP_CONS* cons, /**< linear constraint */
4546 SCIP_Bool* infeasible /**< pointer to store if infeasibility is detected; or NULL if this
4547 * information is not needed; in this case, we apply all fixings
4548 * instead of stopping after the first infeasible one */
4549 )
4550{
4551 SCIP_CONSDATA* consdata;
4552 SCIP_VAR* var;
4553 SCIP_VAR** aggrvars;
4554 SCIP_Real val;
4555 SCIP_Real* aggrscalars;
4556 SCIP_Real fixedval;
4557 SCIP_Real aggrconst;
4558 int v;
4559 int naggrvars;
4560 int i;
4561
4562 assert(scip != NULL);
4563 assert(cons != NULL);
4564
4565 if( infeasible != NULL )
4566 *infeasible = FALSE;
4567
4568 consdata = SCIPconsGetData(cons);
4569 assert(consdata != NULL);
4570
4571 if( consdata->eventdata == NULL )
4572 {
4573 SCIP_CONSHDLR* conshdlr;
4574 SCIP_CONSHDLRDATA* conshdlrdata;
4575
4576 conshdlr = SCIPconsGetHdlr(cons);
4577 assert(conshdlr != NULL);
4578
4579 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4580 assert(conshdlrdata != NULL);
4581
4582 /* catch bound change events of variables */
4583 SCIP_CALL( consCatchAllEvents(scip, cons, conshdlrdata->eventhdlr) );
4584 assert(consdata->eventdata != NULL);
4585 }
4586
4587 if( !consdata->removedfixings )
4588 {
4589 SCIP_Real lhssubtrahend;
4590 SCIP_Real rhssubtrahend;
4591
4592 /* if an unmodifiable row has been added to the LP, then we cannot apply fixing anymore (cannot change a row)
4593 * this should not happen, as applyFixings is called in addRelaxation() before creating and adding a row
4594 */
4595 assert(consdata->row == NULL || !SCIProwIsInLP(consdata->row) || SCIProwIsModifiable(consdata->row));
4596
4597 lhssubtrahend = 0.0;
4598 rhssubtrahend = 0.0;
4599
4600 SCIPdebugMsg(scip, "applying fixings:\n");
4602
4603 v = 0;
4604 while( v < consdata->nvars )
4605 {
4606 var = consdata->vars[v];
4607 val = consdata->vals[v];
4608 assert(SCIPvarIsTransformed(var));
4609
4610 switch( SCIPvarGetStatus(var) )
4611 {
4613 SCIPerrorMessage("original variable in transformed linear constraint\n");
4614 return SCIP_INVALIDDATA;
4615
4618 ++v;
4619 break;
4620
4623 fixedval = SCIPvarGetLbGlobal(var);
4624 if( !SCIPisInfinity(scip, -consdata->lhs) )
4625 {
4626 if( SCIPisInfinity(scip, ABS(fixedval)) )
4627 {
4628 /* if lhs gets infinity it means that the problem is infeasible */
4629 if( ( val > 0.0 ) != ( fixedval > 0.0 ) )
4630 {
4632
4633 if( infeasible != NULL )
4634 {
4635 *infeasible = TRUE;
4636 return SCIP_OKAY;
4637 }
4638 }
4639 else
4640 {
4641 SCIP_CALL( chgLhs(scip, cons, -SCIPinfinity(scip)) );
4642 }
4643 }
4644 else
4645 lhssubtrahend += val * fixedval;
4646 }
4647 if( !SCIPisInfinity(scip, consdata->rhs) )
4648 {
4649 if( SCIPisInfinity(scip, ABS(fixedval)) )
4650 {
4651 /* if rhs gets -infinity it means that the problem is infeasible */
4652 if( ( val > 0.0 ) == ( fixedval > 0.0 ) )
4653 {
4654 SCIP_CALL( chgRhs(scip, cons, -SCIPinfinity(scip)) );
4655
4656 if( infeasible != NULL )
4657 {
4658 *infeasible = TRUE;
4659 return SCIP_OKAY;
4660 }
4661 }
4662 else
4663 {
4665 }
4666 }
4667 else
4668 rhssubtrahend += val * fixedval;
4669 }
4670 SCIP_CALL( delCoefPos(scip, cons, v) );
4671 break;
4672
4674 {
4675 SCIP_VAR* activevar = SCIPvarGetAggrVar(var);
4676 SCIP_Real activescalar = SCIPvarGetAggrScalar(var);
4677 SCIP_Real activeconstant = SCIPvarGetAggrConstant(var);
4678
4679 assert(activevar != NULL);
4680 SCIP_CALL( SCIPgetProbvarSum(scip, &activevar, &activescalar, &activeconstant) );
4681 assert(activevar != NULL);
4682 SCIP_CALL( addCoef(scip, cons, activevar, val * activescalar) );
4683
4684 if( activeconstant != 0.0 )
4685 {
4686 if( !SCIPisInfinity(scip, -consdata->lhs) )
4687 lhssubtrahend += val * activeconstant;
4688 if( !SCIPisInfinity(scip, consdata->rhs) )
4689 rhssubtrahend += val * activeconstant;
4690 }
4691
4692 SCIP_CALL( delCoefPos(scip, cons, v) );
4693 break;
4694 }
4697 naggrvars = SCIPvarGetMultaggrNVars(var);
4698 aggrvars = SCIPvarGetMultaggrVars(var);
4699 aggrscalars = SCIPvarGetMultaggrScalars(var);
4700 aggrconst = SCIPvarGetMultaggrConstant(var);
4701
4702 for( i = 0; i < naggrvars; ++i )
4703 {
4704 SCIP_CALL( addCoef(scip, cons, aggrvars[i], val * aggrscalars[i]) );
4705 }
4706
4707 if( aggrconst != 0.0 )
4708 {
4709 if( !SCIPisInfinity(scip, -consdata->lhs) )
4710 lhssubtrahend += val * aggrconst;
4711 if( !SCIPisInfinity(scip, consdata->rhs) )
4712 rhssubtrahend += val * aggrconst;
4713 }
4714
4715 SCIP_CALL( delCoefPos(scip, cons, v) );
4716 break;
4717
4719 SCIP_CALL( addCoef(scip, cons, SCIPvarGetNegationVar(var), -val) );
4720 aggrconst = SCIPvarGetNegationConstant(var);
4721
4722 if( !SCIPisInfinity(scip, -consdata->lhs) )
4723 lhssubtrahend += val * aggrconst;
4724 if( !SCIPisInfinity(scip, consdata->rhs) )
4725 rhssubtrahend += val * aggrconst;
4726
4727 SCIP_CALL( delCoefPos(scip, cons, v) );
4728 break;
4729
4730 default:
4731 SCIPerrorMessage("unknown variable status\n");
4732 SCIPABORT();
4733 return SCIP_INVALIDDATA; /*lint !e527*/
4734 }
4735 }
4736
4737 if( !SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->lhs) )
4738 {
4739 /* check left hand side of unmodifiable empty constraint with former feasibility tolerance */
4740 if( !SCIPconsIsModifiable(cons) && consdata->nvars == 0 )
4741 {
4742 if( SCIPisFeasLT(scip, lhssubtrahend, consdata->lhs) )
4743 {
4745
4746 if( infeasible != NULL )
4747 {
4748 *infeasible = TRUE;
4749 return SCIP_OKAY;
4750 }
4751 }
4752 else
4753 {
4754 SCIP_CALL( chgLhs(scip, cons, -SCIPinfinity(scip)) );
4755 }
4756 }
4757 /* for normal numbers that are relatively equal, subtraction can lead to cancellation,
4758 * causing wrong fixings of other variables --> better use a real zero here
4759 */
4760 else if( SCIPisGE(scip, ABS(consdata->lhs), 1.0) && SCIPisEQ(scip, lhssubtrahend, consdata->lhs) )
4761 {
4762 SCIP_CALL( chgLhs(scip, cons, 0.0) );
4763 }
4764 else
4765 {
4766 SCIP_CALL( chgLhs(scip, cons, consdata->lhs - lhssubtrahend) );
4767 }
4768 }
4769 if( !SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, -consdata->rhs) )
4770 {
4771 /* check right hand side of unmodifiable empty constraint with former feasibility tolerance */
4772 if( !SCIPconsIsModifiable(cons) && consdata->nvars == 0 )
4773 {
4774 if( SCIPisFeasGT(scip, rhssubtrahend, consdata->rhs) )
4775 {
4776 SCIP_CALL( chgRhs(scip, cons, -SCIPinfinity(scip)) );
4777
4778 if( infeasible != NULL )
4779 {
4780 *infeasible = TRUE;
4781 return SCIP_OKAY;
4782 }
4783 }
4784 else
4785 {
4787 }
4788 }
4789 /* for normal numbers that are relatively equal, subtraction can lead to cancellation,
4790 * causing wrong fixings of other variables --> better use a real zero here
4791 */
4792 else if( SCIPisGE(scip, ABS(consdata->rhs), 1.0) && SCIPisEQ(scip, rhssubtrahend, consdata->rhs) )
4793 {
4794 SCIP_CALL( chgRhs(scip, cons, 0.0) );
4795 }
4796 else
4797 {
4798 SCIP_CALL( chgRhs(scip, cons, consdata->rhs - rhssubtrahend) );
4799 }
4800 }
4801 consdata->removedfixings = TRUE;
4802
4803 SCIPdebugMsg(scip, "after fixings:\n");
4805
4806 /* if aggregated variables have been replaced, multiple entries of the same variable are possible and we have
4807 * to clean up the constraint
4808 */
4809 SCIP_CALL( mergeMultiples(scip, cons) );
4810
4811 SCIPdebugMsg(scip, "after merging:\n");
4813 }
4814 assert(consdata->removedfixings);
4815
4816#ifndef NDEBUG
4817 /* check, if all fixings are applied */
4818 for( v = 0; v < consdata->nvars; ++v )
4819 assert(SCIPvarIsActive(consdata->vars[v]));
4820#endif
4821
4822 return SCIP_OKAY;
4823}
4824
4825/** for each variable in the linear constraint, except the inferred variable, adds one bound to the conflict analysis'
4826 * candidate store (bound depends on sign of coefficient and whether the left or right hand side was the reason for the
4827 * inference variable's bound change); the conflict analysis can be initialized with the linear constraint being the
4828 * conflict detecting constraint by using NULL as inferred variable
4829 */
4830static
4832 SCIP* scip, /**< SCIP data structure */
4833 SCIP_CONS* cons, /**< constraint that inferred the bound change */
4834 SCIP_VAR* infervar, /**< variable that was deduced, or NULL */
4835 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4836 int inferpos, /**< position of the inferred variable in the vars array */
4837 SCIP_Bool reasonisrhs /**< is the right hand side responsible for the bound change? */
4838 )
4839{
4840 SCIP_CONSDATA* consdata;
4841 SCIP_VAR** vars;
4842 SCIP_Real* vals;
4843 int nvars;
4844 int i;
4845
4846 assert(scip != NULL);
4847 assert(cons != NULL);
4848
4849 consdata = SCIPconsGetData(cons);
4850
4851 assert(consdata != NULL);
4852
4853 vars = consdata->vars;
4854 vals = consdata->vals;
4855 nvars = consdata->nvars;
4856
4857 assert(vars != NULL || nvars == 0);
4858 assert(vals != NULL || nvars == 0);
4859
4860 assert(-1 <= inferpos && inferpos < nvars);
4861 assert((infervar == NULL) == (inferpos == -1));
4862 assert(inferpos == -1 || vars[inferpos] == infervar); /*lint !e613*/
4863
4864 /* for each variable, add the bound to the conflict queue, that is responsible for the minimal or maximal
4865 * residual value, depending on whether the left or right hand side is responsible for the bound change:
4866 * - if the right hand side is the reason, the minimal residual activity is responsible
4867 * - if the left hand side is the reason, the maximal residual activity is responsible
4868 */
4869
4870 /* if the variable is integral we only need to add reason bounds until the propagation could be applied */
4871 if( infervar == NULL || SCIPvarIsIntegral(infervar) )
4872 {
4873 SCIP_Real minresactivity;
4874 SCIP_Real maxresactivity;
4875 SCIP_Bool ismintight;
4876 SCIP_Bool ismaxtight;
4877 SCIP_Bool isminsettoinfinity;
4878 SCIP_Bool ismaxsettoinfinity;
4879
4880 minresactivity = -SCIPinfinity(scip);
4881 maxresactivity = SCIPinfinity(scip);
4882
4883 /* calculate the minimal and maximal global activity of all other variables involved in the constraint */
4884 if( infervar != NULL )
4885 {
4886 assert(vals != NULL); /* for flexelint */
4887 if( reasonisrhs )
4888 consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, &minresactivity, NULL,
4889 &ismintight, NULL, &isminsettoinfinity, NULL);
4890 else
4891 consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, NULL, &maxresactivity,
4892 NULL, &ismaxtight, NULL, &ismaxsettoinfinity);
4893 }
4894 else
4895 {
4896 if( reasonisrhs )
4897 consdataGetGlbActivityBounds(scip, consdata, FALSE, &minresactivity, NULL,
4898 &ismintight, NULL, &isminsettoinfinity, NULL);
4899 else
4900 consdataGetGlbActivityBounds(scip, consdata, FALSE, NULL, &maxresactivity,
4901 NULL, &ismaxtight, NULL, &ismaxsettoinfinity);
4902 }
4903
4904 /* we can only do something clever, if the residual activity is finite and not relaxed */
4905 if( (reasonisrhs && !isminsettoinfinity && ismintight) || (!reasonisrhs && !ismaxsettoinfinity && ismaxtight) ) /*lint !e644*/
4906 {
4907 SCIP_Real rescap;
4908 SCIP_Bool resactisinf;
4909
4910 resactisinf = FALSE;
4911
4912 /* calculate the residual capacity that would be left, if the variable would be set to one more / one less
4913 * than its inferred bound
4914 */
4915 if( infervar != NULL )
4916 {
4917 assert(vals != NULL); /* for flexelint */
4918
4919 if( reasonisrhs )
4920 {
4921 if( SCIPisUpdateUnreliable(scip, minresactivity, consdata->lastglbminactivity) )
4922 {
4923 consdataGetReliableResidualActivity(scip, consdata, infervar, &minresactivity, TRUE, TRUE);
4924 if( SCIPisInfinity(scip, -minresactivity) )
4925 resactisinf = TRUE;
4926 }
4927 rescap = consdata->rhs - minresactivity;
4928 }
4929 else
4930 {
4931 if( SCIPisUpdateUnreliable(scip, maxresactivity, consdata->lastglbmaxactivity) )
4932 {
4933 consdataGetReliableResidualActivity(scip, consdata, infervar, &maxresactivity, FALSE, TRUE);
4934 if( SCIPisInfinity(scip, maxresactivity) )
4935 resactisinf = TRUE;
4936 }
4937 rescap = consdata->lhs - maxresactivity;
4938 }
4939
4940 if( reasonisrhs == (vals[inferpos] > 0.0) )
4941 rescap -= vals[inferpos] * (SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) + 1.0);
4942 else
4943 rescap -= vals[inferpos] * (SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) - 1.0);
4944 }
4945 else
4946 rescap = (reasonisrhs ? consdata->rhs - minresactivity : consdata->lhs - maxresactivity);
4947
4948 if( !resactisinf )
4949 {
4950 /* now add bounds as reasons until the residual capacity is exceeded */
4951 for( i = 0; i < nvars; ++i )
4952 {
4953 assert( vars != NULL && vals != NULL ); /* for lint */
4954
4955 /* zero coefficients and the inferred variable can be ignored */
4956 if( vars[i] == infervar || SCIPisZero(scip, vals[i]) )
4957 continue;
4958
4959 /* check if the residual capacity is exceeded */
4960 if( (reasonisrhs && SCIPisFeasNegative(scip, rescap))
4961 || (!reasonisrhs && SCIPisFeasPositive(scip, rescap)) )
4962 break;
4963
4964 /* update the residual capacity due to the local bound of this variable */
4965 if( reasonisrhs == (vals[i] > 0.0) )
4966 {
4967 /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound */
4968 SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
4969 rescap -= vals[i] * (SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetLbGlobal(vars[i]));
4970 }
4971 else
4972 {
4973 /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound */
4974 SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
4975 rescap -= vals[i] * (SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetUbGlobal(vars[i]));
4976 }
4977 }
4978 return SCIP_OKAY;
4979 }
4980 }
4981 }
4982
4983 /* for a bound change on a continuous variable, all locally changed bounds are responsible */
4984 for( i = 0; i < nvars; ++i )
4985 {
4986 assert(vars != NULL); /* for flexelint */
4987 assert(vals != NULL); /* for flexelint */
4988
4989 /* zero coefficients and the inferred variable can be ignored */
4990 if( vars[i] == infervar || SCIPisZero(scip, vals[i]) )
4991 continue;
4992
4993 if( reasonisrhs == (vals[i] > 0.0) )
4994 {
4995 /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound is responsible */
4996 SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
4997 }
4998 else
4999 {
5000 /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound is responsible */
5001 SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
5002 }
5003 }
5004
5005 return SCIP_OKAY;
5006}
5007
5008/** for each variable in the linear ranged row constraint, except the inferred variable, adds the bounds of all fixed
5009 * variables to the conflict analysis' candidate store; the conflict analysis can be initialized
5010 * with the linear constraint being the conflict detecting constraint by using NULL as inferred variable
5011 */
5012static
5014 SCIP* scip, /**< SCIP data structure */
5015 SCIP_CONS* cons, /**< constraint that inferred the bound change */
5016 SCIP_VAR* infervar, /**< variable that was deduced, or NULL */
5017 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
5018 int inferpos /**< position of the inferred variable in the vars array, or -1 */
5019 )
5020{
5021 SCIP_CONSDATA* consdata;
5022 SCIP_VAR** vars;
5023 int nvars;
5024 int v;
5025
5026 assert(scip != NULL);
5027 assert(cons != NULL);
5028
5029 consdata = SCIPconsGetData(cons);
5030 assert(consdata != NULL);
5031 vars = consdata->vars;
5032 nvars = consdata->nvars;
5033 assert(vars != NULL || nvars == 0);
5034 assert(-1 <= inferpos && inferpos < nvars);
5035 assert((infervar == NULL) == (inferpos == -1));
5036 assert(inferpos == -1 || vars != NULL);
5037 assert(inferpos == -1 || vars[inferpos] == infervar); /*lint !e613*/
5038
5039 /* collect all fixed variables */
5040 for( v = nvars - 1; v >= 0; --v )
5041 {
5042 assert(vars != NULL); /* for flexelint */
5043
5044 /* need to add old bounds before propagation of inferrence variable */
5045 if( vars[v] == infervar )
5046 {
5047 assert(vars[v] != NULL);
5048
5049 if( !SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetLbGlobal(vars[v])) )
5050 {
5051 /* @todo get boundchange index before this last boundchange and correct the index */
5052 SCIP_CALL( SCIPaddConflictLb(scip, vars[v], bdchgidx) );
5053 }
5054
5055 if( !SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetUbGlobal(vars[v])) )
5056 {
5057 /* @todo get boundchange index before this last boundchange and correct the index */
5058 SCIP_CALL( SCIPaddConflictUb(scip, vars[v], bdchgidx) );
5059 }
5060
5061 continue;
5062 }
5063
5064 /* check for fixed variables */
5065 if( SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE)) )
5066 {
5067 /* add all bounds of fixed variables which lead to the boundchange of the given inference variable */
5068 SCIP_CALL( SCIPaddConflictLb(scip, vars[v], bdchgidx) );
5069 SCIP_CALL( SCIPaddConflictUb(scip, vars[v], bdchgidx) );
5070 }
5071 }
5072
5073 return SCIP_OKAY;
5074}
5075
5076/** add reasoning variables to conflict candidate queue which led to the conflict */
5077static
5079 SCIP* scip, /**< SCIP data structure */
5080 SCIP_VAR** vars, /**< variables reasoning the infeasibility */
5081 int nvars, /**< number of variables reasoning the infeasibility */
5082 SCIP_VAR* var, /**< variable which was tried to fix/tighten, or NULL */
5083 SCIP_Real bound /**< bound of variable which was tried to apply, or SCIP_INVALID */
5084 )
5085{
5086 int v;
5087
5088 assert(scip != NULL);
5089
5090 /* collect all variables for which the local bounds differ from their global bounds */
5091 for( v = nvars - 1; v >= 0; --v )
5092 {
5093 assert(vars != NULL);
5094
5095 /* check for local bound changes variables */
5096 if( !SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetLbGlobal(vars[v])) )
5097 {
5098 /* add conflict bound */
5099 SCIP_CALL( SCIPaddConflictLb(scip, vars[v], 0) );
5100 }
5101
5102 if( !SCIPisEQ(scip, SCIPvarGetUbLocal(vars[v]), SCIPvarGetUbGlobal(vars[v])) )
5103 {
5104 SCIP_CALL( SCIPaddConflictUb(scip, vars[v], 0) );
5105 }
5106 }
5107
5108 if( var != NULL )
5109 {
5110 if( bound < SCIPvarGetLbLocal(var) )
5111 {
5112 SCIP_CALL( SCIPaddConflictLb(scip, var, 0) );
5113 }
5114
5115 if( bound > SCIPvarGetUbLocal(var) )
5116 {
5117 SCIP_CALL( SCIPaddConflictUb(scip, var, 0) );
5118 }
5119 }
5120
5121 return SCIP_OKAY;
5122}
5123
5124/** resolves a propagation on the given variable by supplying the variables needed for applying the corresponding
5125 * propagation rule (see propagateCons()):
5126 * (1) activity residuals of all other variables tighten bounds of single variable
5127 */
5128static
5130 SCIP* scip, /**< SCIP data structure */
5131 SCIP_CONS* cons, /**< constraint that inferred the bound change */
5132 SCIP_VAR* infervar, /**< variable that was deduced */
5133 INFERINFO inferinfo, /**< inference information */
5134 SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
5135 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
5136 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
5137 )
5138{
5139 SCIP_CONSDATA* consdata;
5140 SCIP_VAR** vars;
5141#ifndef NDEBUG
5142 SCIP_Real* vals;
5143#endif
5144 int nvars;
5145 int inferpos;
5146
5147 assert(scip != NULL);
5148 assert(cons != NULL);
5149 assert(result != NULL);
5150
5151 consdata = SCIPconsGetData(cons);
5152 assert(consdata != NULL);
5153 vars = consdata->vars;
5154 nvars = consdata->nvars;
5155#ifndef NDEBUG
5156 vals = consdata->vals;
5157 assert(vars != NULL);
5158 assert(vals != NULL);
5159#endif
5160
5161 /* get the position of the inferred variable in the vars array */
5162 inferpos = inferInfoGetPos(inferinfo);
5163 if( inferpos >= nvars || vars[inferpos] != infervar )
5164 {
5165 /* find inference variable in constraint */
5166 /**@todo use a binary search here; the variables can be sorted by variable index */
5167 for( inferpos = 0; inferpos < nvars && vars[inferpos] != infervar; ++inferpos )
5168 {}
5169 }
5170 assert(inferpos < nvars);
5171 assert(vars[inferpos] == infervar);
5172 assert(!SCIPisZero(scip, vals[inferpos]));
5173
5174 switch( inferInfoGetProprule(inferinfo) )
5175 {
5176 case PROPRULE_1_RHS:
5177 /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
5178 * constraint (only taking the other variables into account) didn't leave enough space for a larger
5179 * domain in order to not exceed the right hand side of the inequality
5180 */
5181 assert((vals[inferpos] > 0.0) == (boundtype == SCIP_BOUNDTYPE_UPPER));
5182 SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, inferpos, TRUE) );
5183 *result = SCIP_SUCCESS;
5184 break;
5185
5186 case PROPRULE_1_LHS:
5187 /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
5188 * constraint (only taking the other variables into account) didn't leave enough space for a larger
5189 * domain in order to not fall below the left hand side of the inequality
5190 */
5191 assert((vals[inferpos] > 0.0) == (boundtype == SCIP_BOUNDTYPE_LOWER));
5192 SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, inferpos, FALSE) );
5193 *result = SCIP_SUCCESS;
5194 break;
5195
5197 /* the bound of the variable was tightened, because some variables were already fixed and the leftover only allow
5198 * the given inference variable to their bounds in this given ranged row
5199 */
5200
5201 /* check that we really have a ranged row here */
5202 assert(!SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs));
5203 SCIP_CALL( addConflictFixedVars(scip, cons, infervar, bdchgidx, inferpos) );
5204 *result = SCIP_SUCCESS;
5205 break;
5206
5207 case PROPRULE_INVALID:
5208 default:
5209 SCIPerrorMessage("invalid inference information %d in linear constraint <%s> at position %d for %s bound of variable <%s>\n",
5210 inferInfoGetProprule(inferinfo), SCIPconsGetName(cons), inferInfoGetPos(inferinfo),
5211 boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(infervar));
5212 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
5213 SCIPinfoMessage(scip, NULL, ";\n");
5214 return SCIP_INVALIDDATA;
5215 }
5216
5217 return SCIP_OKAY;
5218}
5219
5220/** analyzes conflicting bounds on given constraint, and adds conflict constraint to problem */
5221static
5223 SCIP* scip, /**< SCIP data structure */
5224 SCIP_CONS* cons, /**< conflict detecting constraint */
5225 SCIP_Bool reasonisrhs /**< is the right hand side responsible for the conflict? */
5226 )
5227{
5228 /* conflict analysis can only be applied in solving stage and if it is turned on */
5230 return SCIP_OKAY;
5231
5232 /* initialize conflict analysis */
5234
5235 /* add the conflicting bound for each variable of infeasible constraint to conflict candidate queue */
5236 SCIP_CALL( addConflictBounds(scip, cons, NULL, NULL, -1, reasonisrhs) );
5237
5238 /* analyze the conflict */
5240
5241 return SCIP_OKAY;
5242}
5243
5244/** check if there is any hope of tightening some bounds */
5245static
5247 SCIP_CONS* cons /**< linear constraint */
5248 )
5249{
5250 SCIP_CONSDATA* consdata;
5251 int infcountmin;
5252 int infcountmax;
5253
5254 consdata = SCIPconsGetData(cons);
5255 assert(consdata != NULL);
5256
5257 infcountmin = consdata->minactivityneginf
5258 + consdata->minactivityposinf
5259 + consdata->minactivityneghuge
5260 + consdata->minactivityposhuge;
5261 infcountmax = consdata->maxactivityneginf
5262 + consdata->maxactivityposinf
5263 + consdata->maxactivityneghuge
5264 + consdata->maxactivityposhuge;
5265
5266 if( infcountmin > 1 && infcountmax > 1 )
5267 return FALSE;
5268
5269 return TRUE;
5270}
5271
5272/** tighten upper bound */
5273static
5275 SCIP* scip, /**< SCIP data structure */
5276 SCIP_CONS* cons, /**< linear constraint */
5277 int pos, /**< variable position */
5278 PROPRULE proprule, /**< propagation rule that deduced the value */
5279 SCIP_Real newub, /**< new upper bound */
5280 SCIP_Real oldub, /**< old upper bound */
5281 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
5282 int* nchgbds, /**< pointer to count the total number of tightened bounds */
5283 SCIP_Bool force /**< should a possible bound change be forced even if below bound strengthening tolerance */
5284 )
5285{
5286 SCIP_CONSDATA* consdata;
5287 SCIP_VAR* var;
5288 SCIP_Real lb;
5289 SCIP_Bool infeasible;
5290 SCIP_Bool tightened;
5291
5292 assert(cons != NULL);
5293 assert(!SCIPisInfinity(scip, newub));
5294
5295 consdata = SCIPconsGetData(cons);
5296 assert(consdata != NULL);
5297 var = consdata->vars[pos];
5298 assert(var != NULL);
5299
5300 lb = SCIPvarGetLbLocal(var);
5301 newub = SCIPadjustedVarUb(scip, var, newub);
5302
5303 if( force || SCIPisUbBetter(scip, newub, lb, oldub) )
5304 {
5305 SCIP_VARTYPE vartype;
5306
5307 SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, old bds=[%.15g,%.15g], val=%.15g, activity=[%.15g,%.15g], sides=[%.15g,%.15g] -> newub=%.15g\n",
5308 SCIPconsGetName(cons), SCIPvarGetName(var), lb, oldub, consdata->vals[pos],
5309 QUAD_TO_DBL(consdata->minactivity), QUAD_TO_DBL(consdata->maxactivity), consdata->lhs, consdata->rhs, newub);
5310
5311 vartype = SCIPvarGetType(var);
5312
5313 /* tighten upper bound */
5314 SCIP_CALL( SCIPinferVarUbCons(scip, var, newub, cons, getInferInt(proprule, pos), force, &infeasible, &tightened) );
5315
5316 if( infeasible )
5317 {
5318 SCIPdebugMsg(scip, "linear constraint <%s>: cutoff <%s>, new bds=[%.15g,%.15g]\n",
5319 SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);
5320
5321 /* analyze conflict */
5323
5324 *cutoff = TRUE;
5325 }
5326 else if( tightened )
5327 {
5328 assert(SCIPisFeasLE(scip, SCIPvarGetUbLocal(var), oldub));