1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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    prop_genvbounds.c
26   	 * @ingroup DEFPLUGINS_PROP
27   	 * @brief   generalized variable bounds propagator
28   	 * @author  Stefan Weltge
29   	 * @author  Ambros Gleixner
30   	 * @author  Benjamin Mueller
31   	 */
32   	
33   	/**@todo should we only discard events catched from nodes that are not the current node's ancestors? */
34   	/**@todo improve computation of minactivity */
35   	/**@todo for multaggr vars on left-hand side, create a linear constraint, probably in exitpre */
36   	
37   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38   	
39   	#include "blockmemshell/memory.h"
40   	#include "scip/cons_linear.h"
41   	#include "scip/debug.h"
42   	#include "scip/prop_genvbounds.h"
43   	#include "scip/pub_event.h"
44   	#include "scip/pub_message.h"
45   	#include "scip/pub_misc.h"
46   	#include "scip/pub_prop.h"
47   	#include "scip/pub_var.h"
48   	#include "scip/scip_conflict.h"
49   	#include "scip/scip_cons.h"
50   	#include "scip/scip_datastructures.h"
51   	#include "scip/scip_event.h"
52   	#include "scip/scip_general.h"
53   	#include "scip/scip_mem.h"
54   	#include "scip/scip_message.h"
55   	#include "scip/scip_numerics.h"
56   	#include "scip/scip_param.h"
57   	#include "scip/scip_prob.h"
58   	#include "scip/scip_probing.h"
59   	#include "scip/scip_prop.h"
60   	#include "scip/scip_sol.h"
61   	#include "scip/scip_solve.h"
62   	#include "scip/scip_solvingstats.h"
63   	#include "scip/scip_tree.h"
64   	#include "scip/scip_var.h"
65   	#include <string.h>
66   	
67   	#define PROP_NAME                            "genvbounds"
68   	#define PROP_DESC                            "generalized variable bounds propagator"
69   	#define PROP_TIMING   SCIP_PROPTIMING_ALWAYS
70   	#define PROP_PRIORITY                3000000 /**< propagator priority */
71   	#define PROP_FREQ                          1 /**< propagator frequency */
72   	#define PROP_DELAY                     FALSE /**< should propagation method be delayed, if other propagators
73   	                                              *   found reductions? */
74   	#define PROP_PRESOL_PRIORITY        -2000000 /**< priority of the presolving method (>= 0: before, < 0: after
75   	                                              *   constraint handlers); combined with presolvers */
76   	#define PROP_PRESOLTIMING           SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
77   	#define PROP_PRESOL_MAXROUNDS             -1 /**< maximal number of presolving rounds the presolver participates
78   	                                              *   in (-1: no limit) */
79   	#define DEFAULT_GLOBAL_PROPAGATION      TRUE /**< apply global propagation? */
80   	#define DEFAULT_PROPAGATE_IN_ROOT_NODE  TRUE /**< apply genvbounds in root node if no new incumbent was found? */
81   	#define DEFAULT_SORT                    TRUE /**< sort genvbounds and wait for bound change events? (otherwise all
82   	                                              *   genvbounds are applied in each node) */
83   	#define DEFAULT_PROPASCONSS            FALSE /**< should genvbounds be transformed to (linear) constraints? */
84   	
85   	#define EVENTHDLR_NAME                       "genvbounds"
86   	#define EVENTHDLR_DESC                       "event handler for generalized variable bounds propagator"
87   	
88   	
89   	/*
90   	 * Data structures
91   	 */
92   	
93   	/** GenVBound data */
94   	struct GenVBound
95   	{
96   	   SCIP_VAR**            vars;               /**< pointers to variables x_j occurring in this generalized variable
97   	                                              *   bound */
98   	   SCIP_VAR*             var;                /**< pointer to variable x_i */
99   	   SCIP_Real*            coefs;              /**< coefficients a_j of the variables listed in vars */
100  	   SCIP_Real             constant;           /**< constant term in generalized variable bound */
101  	   SCIP_Real             cutoffcoef;         /**< cutoff bound's coefficient */
102  	   int                   coefssize;          /**< size of coefs array */
103  	   int                   index;              /**< index of this genvbound in genvboundstore array */
104  	   int                   ncoefs;             /**< number of nonzero coefficients a_j */
105  	   SCIP_BOUNDTYPE        boundtype;          /**< type of bound provided by the genvbound, SCIP_BOUNDTYPE_LOWER/UPPER
106  	                                              *   if +/- x_i on left-hand side */
107  	   SCIP_Bool             relaxonly;          /**< contains a relaxation-only variable */
108  	};
109  	typedef struct GenVBound GENVBOUND;
110  	
111  	/** starting indices data structure */
112  	struct SCIP_EventData
113  	{
114  	   SCIP_PROP*            prop;               /**< pointer to genvbounds propagator */
115  	   SCIP_VAR*             var;                /**< variable */
116  	   int*                  startindices;       /**< array to store the first indices of genvbounds in components that are
117  	                                              *   impacted by a change of this bound */
118  	   int*                  startcomponents;    /**< array to store the components corresponding to startindices array */
119  	   int                   nstarts;            /**< number of indices stored in startindices array */
120  	   int                   startindicessize;   /**< size of the startindices and startcomponents arrays */
121  	};
122  	
123  	/** propagator data */
124  	struct SCIP_PropData
125  	{
126  	   GENVBOUND**           genvboundstore;     /**< array to store genvbounds; fast access is provided by hashmaps
127  	                                              *   lbgenvbounds and ubgenvbounds */
128  	   SCIP_EVENTDATA**      lbevents;           /**< array of lower bound event data */
129  	   SCIP_EVENTDATA**      ubevents;           /**< array of upper bound event data */
130  	   SCIP_EVENTHDLR*       eventhdlr;          /**< genvbounds propagator event handler */
131  	   SCIP_HASHMAP*         lbgenvbounds;       /**< hashmap to provide fast access to lower bound genvbounds in
132  	                                              *   genvboundstore array */
133  	   SCIP_HASHMAP*         ubgenvbounds;       /**< hashmap to provide fast access to upper bound genvbounds in
134  	                                              *   genvboundstore array */
135  	   SCIP_HASHMAP*         lbeventsmap;        /**< hashmap to provide fast access to lbevents array */
136  	   SCIP_HASHMAP*         ubeventsmap;        /**< hashmap to provide fast access to ubevents array */
137  	   SCIP_HASHMAP*         startmap;           /**< hashmap to provide fast access to startindices array */
138  	   SCIP_PROP*            prop;               /**< pointer to genvbounds propagator */
139  	   SCIP_NODE*            lastnodecaught;     /**< last node where events for starting indices were caught */
140  	   SCIP_VAR*             cutoffboundvar;     /**< artificial variable representing primal cutoff bound */
141  	   int*                  componentsstart;    /**< stores the components starting indices in genvboundstore array; the
142  	                                              *   entry componentsstart[ncomponents] is equal to ngenvbounds, which
143  	                                              *   makes it easier to iterate over all components */
144  	   int                   componentsstartsize;/**< size of componentsstart array */
145  	   int*                  startindices;       /**< storing indices of components where local propagation should start */
146  	   int*                  startcomponents;    /**< components corresponding to indices stored in startindices array */
147  	   int                   startindicessize;   /**< size of startindices and startcomponents arrays */
148  	   int*                  gstartindices;      /**< storing indices of components where global propagation, i.e.,
149  	                                              *   propagation of an improved primal bound, should start */
150  	   int*                  gstartcomponents;   /**< components corresponding to indices stored in gstartindices array */
151  	   int                   gstartindicessize;  /**< size of gstartindices and gstartcomponents arrays */
152  	   SCIP_Real             lastcutoff;         /**< cutoff bound's value last time genvbounds propagator was called */
153  	   int                   genvboundstoresize; /**< size of genvboundstore array */
154  	   int                   ngenvbounds;        /**< number of genvbounds stored in genvboundstore array */
155  	   int                   ncomponents;        /**< number of components in genvboundstore array */
156  	   int                   nindices;           /**< number of indices stored in startindices array */
157  	   int                   ngindices;          /**< number of indices stored in gstartindices array */
158  	   int                   nlbevents;          /**< number of data entries in lbevents array */
159  	   int                   nubevents;          /**< number of data entries in ubevents array */
160  	   SCIP_Bool             issorted;           /**< stores wether array genvboundstore is topologically sorted */
161  	   SCIP_Bool             global;             /**< apply global propagation? */
162  	   SCIP_Bool             propinrootnode;     /**< apply genvbounds in root node if no new incumbent was found? */
163  	   SCIP_Bool             sort;               /**< sort genvbounds and wait for bound change events? (otherwise all
164  	                                              *   genvbounds are applied in each node) */
165  	   SCIP_Bool             propasconss;        /**< should genvbounds be transformed to (linear) constraints? */
166  	};
167  	
168  	
169  	/*
170  	 * Local methods
171  	 */
172  	
173  	/** returns correct cutoff bound value */
174  	static
175  	SCIP_Real getCutoffboundGenVBound(
176  	   SCIP*                 scip                /**< SCIP data structure */
177  	   )
178  	{
179  	   assert(scip != NULL);
180  	
181  	   SCIPdebugMsg(scip, "cutoff = %.9g (%.9g + %.9g * %.9g)\n",
182  	      (SCIPgetCutoffbound(scip) + SCIPgetTransObjoffset(scip)) * SCIPgetTransObjscale(scip),
183  	      SCIPgetCutoffbound(scip), SCIPgetTransObjoffset(scip), SCIPgetTransObjscale(scip));
184  	
185  	   /* the cutoff bound is valid w.r.t. the current objective function in the transformed problem; during presolving,
186  	    * however, the objective function can change (e.g., when a variable is fixed, its contribution in the objective is
187  	    * subtracted from the cutoff bound and added to the objective offset); we solve this by transforming the
188  	    * contribution of the cutoff bound in the generalized variable bound to the original problem as described in
189  	    * function SCIPgenVBoundAdd()
190  	    */
191  	   return (SCIPgetCutoffbound(scip) + SCIPgetTransObjoffset(scip)) * SCIPgetTransObjscale(scip);
192  	}
193  	
194  	/** returns corresponding genvbound in genvboundstore if there is one, NULL otherwise */
195  	static
196  	GENVBOUND* getGenVBound(
197  	   SCIP*                 scip,               /**< SCIP data structure */
198  	   SCIP_PROPDATA*        propdata,           /**< data of the genvbounds propagator */
199  	   SCIP_VAR*             var,                /**< bounds variable */
200  	   SCIP_BOUNDTYPE        boundtype           /**< bounds type */
201  	   )
202  	{
203  	   SCIP_HASHMAP* hashmap;
204  	
205  	   assert(scip != NULL);
206  	   assert(propdata != NULL);
207  	   assert(var != NULL);
208  	
209  	   hashmap = boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
210  	
211  	   return (GENVBOUND*) SCIPhashmapGetImage(hashmap, var);
212  	}
213  	
214  	#ifdef SCIP_DEBUG
215  	/** prints a genvbound as debug message */
216  	static
217  	void printGenVBound(
218  	   SCIP*                 scip,               /**< SCIP data structure */
219  	   GENVBOUND*            genvbound           /**< genvbound to be printed */
220  	   )
221  	{
222  	   SCIP_Bool first;
223  	   int i;
224  	
225  	   assert(genvbound != NULL);
226  	
227  	   if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER )
228  	   {
229  	      SCIPdebugMsgPrint(scip, "- ");
230  	   }
231  	
232  	   SCIPdebugMsgPrint(scip, "<%s> >= ", SCIPvarGetName(genvbound->var));
233  	
234  	   first = TRUE;
235  	   for( i = 0; i < genvbound->ncoefs; i++ )
236  	   {
237  	      if( !first )
238  	      {
239  	         SCIPdebugMsgPrint(scip, " + ");
240  	      }
241  	
242  	      SCIPdebugMsgPrint(scip, "%g * <%s>", genvbound->coefs[i], SCIPvarGetName(genvbound->vars[i]));
243  	
244  	      first = FALSE;
245  	   }
246  	
247  	   if( !SCIPisZero(scip, genvbound->cutoffcoef) )
248  	   {
249  	      SCIPdebugMsgPrint(scip, " + %g * cutoff_bound", genvbound->cutoffcoef);
250  	   }
251  	
252  	   if( !SCIPisZero(scip, genvbound->constant) )
253  	   {
254  	      SCIPdebugMsgPrint(scip, " + %g", genvbound->constant);
255  	   }
256  	
257  	   SCIPdebugMsgPrint(scip, "\n");
258  	}
259  	#endif
260  	
261  	/** calculates the minactivity of a linear combination of variables stored in an array */
262  	static
263  	SCIP_Real getGenVBoundsMinActivity(
264  	   SCIP*                 scip,               /**< SCIP data structure */
265  	   SCIP_VAR**            vars,               /**< array of variables */
266  	   SCIP_Real*            coefs,              /**< array of coefficients */
267  	   int                   nvars,              /**< number of variables */
268  	   SCIP_Bool             global              /**< use global variable bounds? */
269  	   )
270  	{
271  	   SCIP_Real minval;
272  	   int i;
273  	
274  	   assert(scip != NULL);
275  	   assert(vars != NULL);
276  	   assert(coefs != NULL);
277  	   assert(nvars >= 0);
278  	
279  	   minval = 0.0;
280  	
281  	   for( i = 0; i < nvars; i++ )
282  	   {
283  	      SCIP_Real bound;
284  	
285  	      /* get global or local bound */
286  	      if( global )
287  	         bound = coefs[i] > 0.0 ? SCIPvarGetLbGlobal(vars[i]) : SCIPvarGetUbGlobal(vars[i]);
288  	      else
289  	         bound = coefs[i] > 0.0 ? SCIPvarGetLbLocal(vars[i]) : SCIPvarGetUbLocal(vars[i]);
290  	
291  	      /* with infinite bounds we cannot compute a valid minactivity and return minus infinity */
292  	      if( SCIPisInfinity(scip, bound) || SCIPisInfinity(scip, -bound) )
293  	         return -SCIPinfinity(scip);
294  	
295  	      /* add contribution to minactivity */
296  	      minval += coefs[i] * bound;
297  	   }
298  	
299  	   return minval;
300  	}
301  	
302  	/** calculates the minactivity of a linear combination of variables stored in the current conflict set */
303  	static
304  	SCIP_Real getGenVBoundsMinActivityConflict(
305  	   SCIP*                 scip,               /**< SCIP data structure */
306  	   SCIP_VAR**            vars,               /**< array of variables */
307  	   SCIP_Real*            coefs,              /**< array of coefficients */
308  	   int                   nvars,              /**< number of variables */
309  	   SCIP_BDCHGIDX*        bdchgidx            /**< bound change at which minactivity should be computed; if NULL use local bounds */
310  	   )
311  	{
312  	   SCIP_Real minval;
313  	   int i;
314  	
315  	   assert(scip != NULL);
316  	   assert(vars != NULL);
317  	   assert(coefs != NULL);
318  	   assert(nvars >= 0);
319  	
320  	   minval = 0.0;
321  	
322  	   for( i = 0; i < nvars; i++ )
323  	   {
324  	      SCIP_Real bound;
325  	
326  	      if( coefs[i] > 0.0 )
327  	      {
328  	         /* get bound at current bound change */
329  	         bound = SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE);
330  	
331  	         /* if bdchgidx is NULL, assert that we use local bounds */
332  	         assert(bdchgidx != NULL || SCIPisEQ(scip, bound, SCIPvarGetLbLocal(vars[i])));
333  	
334  	         /* if bdchgidx is not NULL, use the possibly tighter bound already in the current conflict set */
335  	         if( bdchgidx != NULL && SCIPgetConflictVarLb(scip, vars[i]) > bound )
336  	            bound = SCIPgetConflictVarLb(scip, vars[i]);
337  	      }
338  	      else
339  	      {
340  	         /* get bound at current bound change */
341  	         bound = SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE);
342  	
343  	         /* if bdchgidx is NULL, assert that we use local bounds */
344  	         assert(bdchgidx != NULL || SCIPisEQ(scip, bound, SCIPvarGetUbLocal(vars[i])));
345  	
346  	         /* if bdchgidx is not NULL, use the possibly tighter bound already in the current conflict set */
347  	         if( bdchgidx != NULL && SCIPgetConflictVarUb(scip, vars[i]) < bound )
348  	            bound = SCIPgetConflictVarUb(scip, vars[i]);
349  	      }
350  	
351  	      /* with infinite bounds we cannot compute a valid minactivity and return minus infinity */
352  	      if( SCIPisInfinity(scip, bound) || SCIPisInfinity(scip, -bound) )
353  	         return -SCIPinfinity(scip);
354  	
355  	      /* add contribution to minactivity */
356  	      minval += coefs[i] * bound;
357  	   }
358  	
359  	   return minval;
360  	}
361  	
362  	/** returns a valid bound given by a generalized variable bound */
363  	static
364  	SCIP_Real getGenVBoundsBound(
365  	   SCIP*                 scip,               /**< SCIP data structure */
366  	   GENVBOUND*            genvbound,          /**< generalized variable bound */
367  	   SCIP_Bool             global              /**< use global variable bounds? */
368  	   )
369  	{
370  	   SCIP_Real boundval;
371  	
372  	   assert(scip != NULL);
373  	   assert(genvbound != NULL);
374  	
375  	   boundval = getGenVBoundsMinActivity(scip, genvbound->vars, genvbound->coefs, genvbound->ncoefs, global);
376  	
377  	   if( SCIPisInfinity(scip, -boundval) )
378  	      return (genvbound->boundtype == SCIP_BOUNDTYPE_LOWER) ? -SCIPinfinity(scip) : SCIPinfinity(scip);
379  	
380  	   if( genvbound->cutoffcoef != 0.0 )
381  	      boundval += genvbound->cutoffcoef * getCutoffboundGenVBound(scip);
382  	
383  	   boundval += genvbound->constant;
384  	
385  	   if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER )
386  	      boundval *= -1.0;
387  	
388  	   return boundval;
389  	}
390  	
391  	#ifdef WITH_DEBUG_SOLUTION
392  	/** checks whether a generalized variable bound violates the debug solution */
393  	static
394  	SCIP_RETCODE checkDebugSolutionGenVBound(
395  	   SCIP*                 scip,               /**< SCIP data structure */
396  	   GENVBOUND*            genvbound           /**< generalized variable bound */
397  	   )
398  	{
399  	   SCIP_SOL* debugsol;
400  	   SCIP_Real activity;
401  	   SCIP_Real solval;
402  	   int i;
403  	
404  	   assert(scip != NULL);
405  	   assert(genvbound != NULL);
406  	
407  	   if( !SCIPdebugIsMainscip(scip) )
408  	      return SCIP_OKAY;
409  	
410  	   /* the genvbound must be valid for all cutoff bounds greater equal the objective value of the debug solution */
411  	   SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) );
412  	
413  	   /* check whether a debug solution is available */
414  	   if( debugsol == NULL )
415  	      return SCIP_OKAY;
416  	
417  	   activity = 0.0;
418  	   for( i = 0; i < genvbound->ncoefs; i++ )
419  	   {
420  	      SCIP_CALL( SCIPdebugGetSolVal(scip, genvbound->vars[i], &solval) );
421  	      if( solval != SCIP_UNKNOWN || solval != SCIP_INVALID )
422  	         activity += genvbound->coefs[i] * solval;
423  	      else
424  	         printf("***** debug: ignoring variable with %s value in debug solution\n",
425  	            solval == SCIP_UNKNOWN ? "unknown" : "invalid");
426  	   }
427  	
428  	   activity += genvbound->cutoffcoef *
429  	      (SCIPgetSolTransObj(scip, debugsol) + SCIPgetTransObjoffset(scip)) * SCIPgetTransObjscale(scip);
430  	   activity += genvbound->constant;
431  	
432  	   SCIP_CALL( SCIPdebugGetSolVal(scip, genvbound->var, &solval) );
433  	   if( solval != SCIP_UNKNOWN || solval != SCIP_INVALID )
434  	   {
435  	      if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
436  	      {
437  	         SCIP_CALL( SCIPdebugCheckLbGlobal(scip, genvbound->var, activity) );
438  	      }
439  	      else if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER )
440  	      {
441  	         SCIP_CALL( SCIPdebugCheckUbGlobal(scip, genvbound->var, -activity) );
442  	      }
443  	   }
444  	
445  	   return SCIP_OKAY;
446  	}
447  	#endif
448  	
449  	/** allocate local and global startindices, startcomponents and startmap */
450  	static
451  	SCIP_RETCODE createStartingData(
452  	   SCIP*                 scip,               /**< SCIP data structure */
453  	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
454  	   )
455  	{
456  	   assert(scip != NULL);
457  	   assert(propdata != NULL);
458  	
459  	   assert(propdata->startcomponents == NULL);
460  	   assert(propdata->startindices == NULL);
461  	   assert(propdata->startmap == NULL);
462  	   assert(propdata->nindices == -1);
463  	
464  	   assert(propdata->gstartindices == NULL);
465  	   assert(propdata->gstartcomponents == NULL);
466  	   assert(propdata->ngindices == -1);
467  	
468  	   assert(propdata->ngenvbounds >= 1);
469  	   assert(propdata->ncomponents >= 1);
470  	
471  	   SCIPdebugMsg(scip, "create starting data\n");
472  	
473  	   /* allocate memory for arrays */
474  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->startindices), propdata->ncomponents) );
475  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->startcomponents), propdata->ncomponents) );
476  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->gstartindices), propdata->ncomponents) );
477  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->ncomponents) );
478  	   propdata->startindicessize = propdata->ncomponents;
479  	   propdata->gstartindicessize = propdata->ncomponents;
480  	
481  	   /* create hashmap */
482  	   SCIP_CALL( SCIPhashmapCreate(&(propdata->startmap), SCIPblkmem(scip), propdata->ncomponents) );
483  	
484  	   propdata->nindices = 0;
485  	   propdata->ngindices = 0;
486  	
487  	   return SCIP_OKAY;
488  	}
489  	
490  	/** free local and global startindices, startcomponents and startmap */
491  	static
492  	SCIP_RETCODE freeStartingData(
493  	   SCIP*                 scip,               /**< SCIP data structure */
494  	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
495  	   )
496  	{
497  	   assert(scip != NULL);
498  	   assert(propdata != NULL);
499  	
500  	   SCIPdebugMsg(scip, "free starting data\n");
501  	
502  	   if( propdata->startcomponents != NULL )
503  	   {
504  	      assert(propdata->startindices != NULL);
505  	      assert(propdata->startmap != NULL);
506  	      assert(propdata->nindices >= 0);
507  	
508  	      SCIPfreeBlockMemoryArray(scip, &(propdata->startindices), propdata->startindicessize);
509  	      SCIPfreeBlockMemoryArray(scip, &(propdata->startcomponents), propdata->startindicessize);
510  	      propdata->startindicessize = 0;
511  	      SCIPhashmapFree(&(propdata->startmap));
512  	      propdata->nindices = -1;
513  	
514  	      assert(propdata->gstartindices != NULL);
515  	      assert(propdata->gstartcomponents != NULL);
516  	      assert(propdata->ngindices >= 0);
517  	
518  	      SCIPfreeBlockMemoryArray(scip, &(propdata->gstartindices), propdata->gstartindicessize);
519  	      SCIPfreeBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->gstartindicessize);
520  	      propdata->gstartindicessize = 0;
521  	      propdata->ngindices = -1;
522  	   }
523  	
524  	   assert(propdata->startcomponents == NULL);
525  	   assert(propdata->startindices == NULL);
526  	   assert(propdata->startmap == NULL);
527  	   assert(propdata->nindices == -1);
528  	
529  	   assert(propdata->gstartindices == NULL);
530  	   assert(propdata->gstartcomponents == NULL);
531  	   assert(propdata->ngindices == -1);
532  	
533  	   return SCIP_OKAY;
534  	}
535  	
536  	static
537  	SCIP_RETCODE fillGlobalStartingData(
538  	   SCIP*                 scip,               /**< SCIP data structure */
539  	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
540  	   )
541  	{
542  	   int i;
543  	
544  	   assert(scip != NULL);
545  	   assert(propdata != NULL);
546  	
547  	   assert(propdata->gstartindices != NULL);
548  	   assert(propdata->gstartcomponents != NULL);
549  	   assert(propdata->ngindices == 0);
550  	
551  	   SCIPdebugMsg(scip, "fill global starting data\n");
552  	
553  	   for( i = 0; i < propdata->ncomponents; i++ )
554  	   {
555  	      int j;
556  	
557  	      for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ ) /*lint !e679*/
558  	      {
559  	         assert(j < propdata->ngenvbounds);
560  	
561  	         if( !SCIPisZero(scip, propdata->genvboundstore[j]->cutoffcoef) )
562  	         {
563  	            assert(SCIPisNegative(scip, propdata->genvboundstore[j]->cutoffcoef));
564  	
565  	            propdata->gstartcomponents[propdata->ngindices] = i;
566  	            propdata->gstartindices[propdata->ngindices] = j;
567  	
568  	            /* go to next component */
569  	            propdata->ngindices++;
570  	            break;
571  	         }
572  	      }
573  	   }
574  	
575  	   /* resize arrays */
576  	   if( propdata->gstartindicessize != propdata->ngindices )
577  	   {
578  	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->gstartindices), propdata->gstartindicessize, \
579  	            propdata->ngindices) );
580  	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->gstartindicessize, \
581  	            propdata->ngindices) );
582  	      propdata->gstartindicessize = propdata->ngindices;
583  	   }
584  	
585  	   return SCIP_OKAY;
586  	}
587  	
588  	
589  	/** resets local starting data */
590  	static
591  	SCIP_RETCODE resetLocalStartingData(
592  	   SCIP*                 scip,               /**< SCIP data structure */
593  	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
594  	   )
595  	{
596  	   assert(scip != NULL);
597  	   assert(propdata != NULL);
598  	   assert(propdata->startcomponents != NULL);
599  	   assert(propdata->startindices != NULL);
600  	   assert(propdata->startmap != NULL);
601  	   assert(propdata->nindices >= 0);
602  	
603  	   SCIP_CALL( SCIPhashmapRemoveAll(propdata->startmap) );
604  	   propdata->nindices = 0;
605  	
606  	   return SCIP_OKAY;
607  	}
608  	
609  	/** frees sorted components data */
610  	static
611  	SCIP_RETCODE freeComponentsData(
612  	   SCIP*                 scip,               /**< SCIP data structure */
613  	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
614  	   )
615  	{
616  	   assert(scip != NULL);
617  	   assert(propdata != NULL);
618  	
619  	   SCIPdebugMsg(scip, "free components data\n");
620  	
621  	   if( propdata->componentsstart != NULL )
622  	   {
623  	      assert(propdata->ncomponents > 0);
624  	
625  	      SCIPfreeBlockMemoryArray(scip, &(propdata->componentsstart), propdata->componentsstartsize);
626  	      propdata->componentsstartsize = 0;
627  	      propdata->ncomponents = -1;
628  	   }
629  	
630  	   assert(propdata->componentsstart == NULL);
631  	   assert(propdata->ncomponents == -1);
632  	
633  	   return SCIP_OKAY;
634  	}
635  	
636  	/** frees memory allocated for a generalized variable bound */
637  	static
638  	SCIP_RETCODE freeGenVBound(
639  	   SCIP*                 scip,
640  	   GENVBOUND*            genvbound
641  	   )
642  	{
643  	   int i;
644  	
645  	   assert(scip != NULL);
646  	   assert(genvbound != NULL);
647  	   assert(genvbound->coefs != NULL);
648  	   assert(genvbound->vars != NULL);
649  	   assert(genvbound->var != NULL);
650  	
651  	   /* release variables */
652  	   for( i = 0; i < genvbound->ncoefs; ++i )
653  	   {
654  	      assert(genvbound->vars[i] != NULL);
655  	      SCIP_CALL( SCIPreleaseVar(scip, &(genvbound->vars[i])) );
656  	   }
657  	   SCIP_CALL( SCIPreleaseVar(scip, &genvbound->var) );
658  	
659  	   /* free memory */
660  	   SCIPfreeBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize);
661  	   SCIPfreeBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize);
662  	   SCIPfreeBlockMemory(scip, &genvbound);
663  	
664  	   return SCIP_OKAY;
665  	}
666  	
667  	/** helper function to release all genvbounds */
668  	static
669  	SCIP_RETCODE freeGenVBounds(
670  	   SCIP*                 scip,
671  	   SCIP_PROPDATA*        propdata
672  	   )
673  	{
674  	   int i;
675  	
676  	   assert(scip != NULL);
677  	   assert(propdata != NULL);
678  	
679  	   if( propdata->genvboundstore != NULL )
680  	   {
681  	      /* free genvbounds */
682  	      for( i = propdata->ngenvbounds - 1; i >= 0; i-- )
683  	      {
684  	         SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
685  	      }
686  	
687  	      /* free genvboundstore hashmaps */
688  	      SCIPhashmapFree(&(propdata->lbgenvbounds));
689  	      SCIPhashmapFree(&(propdata->ubgenvbounds));
690  	
691  	      /* free genvboundstore array */
692  	      SCIPfreeBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize);
693  	
694  	      /* set the number of genvbounds to zero */
695  	      propdata->ngenvbounds = 0;
696  	
697  	      /* free componentsstart array */
698  	      SCIP_CALL( freeComponentsData(scip, propdata) );
699  	
700  	      /* free starting indices data */
701  	      SCIP_CALL( freeStartingData(scip, propdata) );
702  	
703  	      /* release the cutoffboundvar and undo the locks */
704  	      if( propdata->cutoffboundvar != NULL )
705  	      {
706  	         SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, -1, -1) );
707  	         SCIP_CALL( SCIPreleaseVar(scip, &(propdata->cutoffboundvar)) );
708  	         propdata->cutoffboundvar = NULL;
709  	         SCIPdebugMsg(scip, "release cutoffboundvar!\n");
710  	      }
711  	   }
712  	
713  	   return SCIP_OKAY;
714  	}
715  	
716  	/** helper function to release relax-only genvbounds */
717  	static
718  	SCIP_RETCODE freeGenVBoundsRelaxOnly(
719  	   SCIP*                 scip,
720  	   SCIP_PROPDATA*        propdata
721  	   )
722  	{
723  	   SCIP_Bool freedgenvbound;
724  	   int i;
725  	
726  	   assert(scip != NULL);
727  	   assert(propdata != NULL);
728  	
729  	   if( propdata->genvboundstore == NULL )
730  	      return SCIP_OKAY;
731  	
732  	   /* free genvbounds */
733  	   freedgenvbound = FALSE;
734  	   for( i = 0 ; i < propdata->ngenvbounds; )
735  	   {
736  	      if( propdata->genvboundstore[i]->relaxonly )
737  	      {
738  	         SCIP_CALL( SCIPhashmapRemove(propdata->genvboundstore[i]->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds,
739  	            propdata->genvboundstore[i]->var) );
740  	
741  	         SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
742  	         if( i != propdata->ngenvbounds-1 )
743  	         {
744  	            propdata->genvboundstore[i] = propdata->genvboundstore[propdata->ngenvbounds-1];
745  	            propdata->genvboundstore[i]->index = i;
746  	         }
747  	         --propdata->ngenvbounds;
748  	
749  	         propdata->issorted = FALSE;
750  	         freedgenvbound = TRUE;
751  	      }
752  	      else
753  	         ++i;
754  	   }
755  	
756  	   if( freedgenvbound )
757  	   {
758  	      /* free componentsstart array */
759  	      SCIP_CALL( freeComponentsData(scip, propdata) );
760  	
761  	      /* free starting indices data */
762  	      SCIP_CALL( freeStartingData(scip, propdata) );
763  	   }
764  	
765  	   return SCIP_OKAY;
766  	}
767  	
768  	/** resolves propagation of lower bound on +/- left-hand side variable of a generalized variable bound */
769  	static
770  	SCIP_RETCODE resolveGenVBoundPropagation(
771  	   SCIP*                 scip,               /**< SCIP data structure */
772  	   GENVBOUND*            genvbound,          /**< genvbound data structure */
773  	   SCIP_BDCHGIDX*        bdchgidx,           /**< the index of the bound change, representing the point of time where the change took place */
774  	   SCIP_Real*            boundval,           /**< pointer to lower bound value on +/- left-hand side variable */
775  	   SCIP_Bool*            success             /**< was the explanation succesful? */
776  	   )
777  	{
778  	   SCIP_VAR* lhsvar;
779  	   SCIP_VAR** vars;
780  	   SCIP_Real minactivity;
781  	   SCIP_Real tmpboundval;
782  	   SCIP_Real slack;
783  	   int nvars;
784  	   int i;
785  	
786  	   assert(scip != NULL);
787  	   assert(genvbound != NULL);
788  	   assert(boundval != NULL);
789  	   assert(success != NULL);
790  	
791  	   *success = FALSE;
792  	
793  	   /* get left-hand side variable */
794  	   lhsvar = genvbound->var;
795  	   assert(lhsvar != NULL);
796  	
797  	   /* get right-hand side variables */
798  	   vars =  genvbound->vars;
799  	   nvars = genvbound->ncoefs;
800  	   assert(vars != NULL);
801  	
802  	   /* if only the primal bound participates in the propagation, it is globally valid and should not be analyzed */
803  	   assert(nvars > 0);
804  	
805  	   /* when resolving a propagation, bdchgidx is not NULL and boundval should be the bound change performed for the
806  	    * left-hand side variable
807  	    */
808  	   assert(bdchgidx == NULL || genvbound->boundtype != SCIP_BOUNDTYPE_LOWER || SCIPisEQ(scip,
809  	         SCIPvarIsIntegral(genvbound->var) ? SCIPfeasCeil(scip, *boundval) : *boundval, SCIPgetVarLbAtIndex(scip, lhsvar, bdchgidx, TRUE)));
810  	   assert(bdchgidx == NULL || genvbound->boundtype != SCIP_BOUNDTYPE_UPPER || SCIPisEQ(scip,
811  	         SCIPvarIsIntegral(genvbound->var) ? SCIPfeasCeil(scip, *boundval) : *boundval, -SCIPgetVarUbAtIndex(scip, lhsvar, bdchgidx, TRUE)));
812  	
813  	   /* when creating an initial conflict, bdchgidx is NULL and +/-boundval must exceed the upper/lower bound of the
814  	    * left-hand side variable
815  	    */
816  	   assert(bdchgidx != NULL || genvbound->boundtype != SCIP_BOUNDTYPE_LOWER
817  	      || SCIPisGT(scip, *boundval, SCIPvarGetUbLocal(lhsvar)));
818  	   assert(bdchgidx != NULL || genvbound->boundtype != SCIP_BOUNDTYPE_UPPER
819  	      || SCIPisGT(scip, *boundval, -SCIPvarGetLbLocal(lhsvar)));
820  	
821  	   SCIPdebugMsg(scip, "resolving genvbound propagation: lhs=%s<%s> >= boundval=%.15g\n",
822  	      genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? "+" : "-", SCIPvarGetName(lhsvar), *boundval);
823  	
824  	   /* subtract constant terms from bound value */
825  	   tmpboundval = *boundval;
826  	   tmpboundval -= genvbound->cutoffcoef * getCutoffboundGenVBound(scip);
827  	   tmpboundval -= genvbound->constant;
828  	
829  	   SCIPdebugMsg(scip, "subtracting constant terms gives boundval=%.15g\n", tmpboundval);
830  	
831  	   /* compute minimal activity; if bdchgidx is NULL, we create the initial conflict and use local bounds */
832  	   minactivity = getGenVBoundsMinActivityConflict(scip, genvbound->vars, genvbound->coefs, genvbound->ncoefs, bdchgidx);
833  	
834  	   SCIPdebugMsg(scip, "minactivity of right-hand side is minactivity=%.15g\n", minactivity);
835  	
836  	   /* a genvbound might have been replaced since the propagation took place, hence we have to check that the current
837  	    * genvbound can explain the propagation at the given bound change index; note that by now, with smaller cutoff
838  	    * bound, we might even perform a stronger propagation
839  	    */
840  	   if( SCIPisLT(scip, minactivity, tmpboundval) )
841  	   {
842  	      SCIPdebugMsg(scip, "minactivity is too small to explain propagation; was genvbound replaced?\n");
843  	      return SCIP_OKAY;
844  	   }
845  	
846  	   /* if bdchgidx is NULL, i.e., we create the initial conflict, we should be able to explain the bound change */
847  	   assert(SCIPisGE(scip, minactivity, tmpboundval));
848  	
849  	   slack = MAX(minactivity - tmpboundval, 0.0);
850  	
851  	   SCIPdebugMsg(scip, "slack=%.15g\n", slack);
852  	
853  	   /* add variables on the right-hand side as reasons for propagation */
854  	   for( i = 0; i < nvars; i++ )
855  	   {
856  	      assert(vars[i] != NULL);
857  	      assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE)));
858  	      assert(SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE)));
859  	
860  	      /* coefficient is positive */
861  	      if( genvbound->coefs[i] > 0.0 )
862  	      {
863  	         SCIP_Real lbatindex;
864  	         SCIP_Real conflictlb;
865  	
866  	         /* get bound at current bound change */
867  	         lbatindex = SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE);
868  	
869  	         /* get bound already enforced by conflict set */
870  	         conflictlb = SCIPgetConflictVarLb(scip, genvbound->vars[i]);
871  	         assert(SCIPisGE(scip, conflictlb, SCIPvarGetLbGlobal(genvbound->vars[i])));
872  	
873  	         SCIPdebugMsg(scip, "lower bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n",
874  	            SCIPvarGetName(genvbound->vars[i]), i, conflictlb, lbatindex);
875  	
876  	         /* if bound is already enforced by conflict set we do not need to add the bound change; since we used the
877  	          * tighest bound already when computing the initial minactivity, the slack is already correct
878  	          */
879  	         if( SCIPisLE(scip, lbatindex, conflictlb) )
880  	         {
881  	            SCIPdebugMsg(scip, "skipping lower bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n",
882  	               SCIPvarGetName(genvbound->vars[i]), i);
883  	         }
884  	         else
885  	         {
886  	            SCIP_Real relaxedlb;
887  	
888  	            /* compute relaxed bound that would suffice to explain the bound change */
889  	            relaxedlb = lbatindex - (slack / genvbound->coefs[i]);
890  	            assert(relaxedlb <= lbatindex);
891  	
892  	            /* add variable to conflict set */
893  	            SCIP_CALL( SCIPaddConflictRelaxedLb(scip, genvbound->vars[i], bdchgidx, relaxedlb ) );
894  	
895  	            /* get new bound of variable in conflict set; after possible bound widening in SCIPaddConflictLbRelaxed(),
896  	             * it should be between conflictlb and lbatindex
897  	             */
898  	            relaxedlb = SCIPgetConflictVarLb(scip, genvbound->vars[i]);
899  	            assert(SCIPisGE(scip, relaxedlb, conflictlb));
900  	            assert(SCIPisLE(scip, relaxedlb, lbatindex));
901  	
902  	            /* update slack and ensure that its nonegative */
903  	            slack -= genvbound->coefs[i] * (lbatindex - relaxedlb);
904  	            slack = MAX(slack, 0.0);
905  	
906  	            SCIPdebugMsg(scip, "added lower bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n",
907  	               SCIPvarGetName(genvbound->vars[i]), i, slack);
908  	         }
909  	      }
910  	      /* coefficient is negative */
911  	      else
912  	      {
913  	         SCIP_Real ubatindex;
914  	         SCIP_Real conflictub;
915  	
916  	         /* get bound at current bound change */
917  	         ubatindex = SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE);
918  	
919  	         /* get bound already enforced by conflict set */
920  	         conflictub = SCIPgetConflictVarUb(scip, genvbound->vars[i]);
921  	         assert(SCIPisLE(scip, conflictub, SCIPvarGetUbGlobal(genvbound->vars[i])));
922  	
923  	         SCIPdebugMsg(scip, "upper bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n",
924  	            SCIPvarGetName(genvbound->vars[i]), i, conflictub, ubatindex);
925  	
926  	         /* if bound is already enforced by conflict set we do not need to add the bound change; since we used the
927  	          * tighest bound already when computing the initial minactivity, the slack is already correct
928  	          */
929  	         if( SCIPisGE(scip, ubatindex, conflictub) )
930  	         {
931  	            SCIPdebugMsg(scip, "skipping upper bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n",
932  	               SCIPvarGetName(genvbound->vars[i]), i);
933  	         }
934  	         else
935  	         {
936  	            SCIP_Real relaxedub;
937  	
938  	            /* compute relaxed bound that would suffice to explain the bound change */
939  	            relaxedub = ubatindex - (slack / genvbound->coefs[i]);
940  	            assert(relaxedub >= ubatindex);
941  	
942  	            /* add variable to conflict set */
943  	            SCIP_CALL( SCIPaddConflictRelaxedUb(scip, genvbound->vars[i], bdchgidx, relaxedub ) );
944  	
945  	            /* get new bound of variable in conflict set; after possible bound widening in SCIPaddConflictUbRelaxed(),
946  	             * it should be between conflictub and ubatindex
947  	             */
948  	            relaxedub = SCIPgetConflictVarUb(scip, genvbound->vars[i]);
949  	            assert(SCIPisLE(scip, relaxedub, conflictub));
950  	            assert(SCIPisGE(scip, relaxedub, ubatindex));
951  	
952  	            /* update slack and ensure that its nonegative */
953  	            slack -= genvbound->coefs[i] * (ubatindex - relaxedub);
954  	            slack = MAX(slack, 0.0);
955  	
956  	            SCIPdebugMsg(scip, "added upper bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n",
957  	               SCIPvarGetName(genvbound->vars[i]), i, slack);
958  	         }
959  	      }
960  	   }
961  	
962  	   /* if slack is positive, return increased boundval */
963  	   if( SCIPisPositive(scip, slack) )
964  	      tmpboundval += slack;
965  	
966  	   /* add constant terms again */
967  	   tmpboundval += genvbound->cutoffcoef * getCutoffboundGenVBound(scip);
968  	   tmpboundval += genvbound->constant;
969  	
970  	   /* boundval should not have been decreased; if this happened nevertheless, maybe due to numerical errors, we quit
971  	    * without success
972  	    */
973  	   if( SCIPisLT(scip, tmpboundval, *boundval) )
974  	   {
975  	      SCIPdebugMsg(scip, "boundval was reduced from %.15g to %.15g; propagation not resolved\n", *boundval, tmpboundval);
976  	      return SCIP_OKAY;
977  	   }
978  	
979  	   /* return widened boundval */
980  	   *boundval = tmpboundval;
981  	   *success = TRUE;
982  	
983  	   return SCIP_OKAY;
984  	}
985  	
986  	/** create initial conflict */
987  	static
988  	SCIP_RETCODE analyzeGenVBoundConflict(
989  	   SCIP*                 scip,               /**< SCIP data structure */
990  	   GENVBOUND*            genvbound           /**< genvbound data structure */
991  	   )
992  	{
993  	   SCIP_Bool success;
994  	
995  	   assert(scip != NULL);
996  	   assert(genvbound != NULL);
997  	
998  	   /* check if conflict analysis is applicable */
999  	   if( !SCIPisConflictAnalysisApplicable(scip) )
1000 	      return SCIP_OKAY;
1001 	
1002 	   /* initialize conflict analysis */
1003 	   SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, !SCIPisInfinity(scip, REALABS(SCIPgetCutoffbound(scip)))) );
1004 	
1005 	   /* left-hand side variable >= ... */
1006 	   if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
1007 	   {
1008 	      SCIP_Real infeasthreshold;
1009 	      SCIP_Real bound;
1010 	
1011 	      /* get minimal right-hand side bound that leads to infeasibility; first try with a factor of 2 for robustness */
1012 	      bound = REALABS(SCIPvarGetUbLocal(genvbound->var));
1013 	      infeasthreshold = MAX(bound, 1.0) * 2 * SCIPfeastol(scip);
1014 	      bound = SCIPvarGetUbLocal(genvbound->var) + infeasthreshold;
1015 	
1016 	      /* add right-hand side variables that force the lower bound of the left-hand side variable above its upper bound
1017 	       * to conflict set
1018 	       */
1019 	      SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1020 	      assert(!success || SCIPisFeasGT(scip, bound, SCIPvarGetUbLocal(genvbound->var)));
1021 	
1022 	      /* if infeasibility cannot be proven with the tighter bound, try with actual bound */
1023 	      if( !success )
1024 	      {
1025 	         bound = REALABS(SCIPvarGetUbLocal(genvbound->var));
1026 	         infeasthreshold = MAX(bound, 1.0) * SCIPfeastol(scip);
1027 	         bound = SCIPvarGetUbLocal(genvbound->var) + infeasthreshold;
1028 	
1029 	         SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1030 	         success = success && SCIPisFeasGT(scip, bound, SCIPvarGetUbLocal(genvbound->var));
1031 	      }
1032 	
1033 	      /* compute upper bound on left-hand side variable that leads to infeasibility */
1034 	      bound -= infeasthreshold;
1035 	      success = success && SCIPisGE(scip, bound, SCIPvarGetUbLocal(genvbound->var));
1036 	
1037 	      /* initial reason could not be constructed, maybe due to numerics; do not apply conflict analysis */
1038 	      if( !success )
1039 	      {
1040 	         SCIPdebugMsg(scip, "strange: could not create initial reason to start conflict analysis\n");
1041 	         return SCIP_OKAY;
1042 	      }
1043 	
1044 	      /* if bound is already enforced by conflict set we do not have to add it */
1045 	      if( SCIPisGE(scip, bound, SCIPgetConflictVarUb(scip, genvbound->var)) )
1046 	      {
1047 	         SCIPdebugMsg(scip, "skipping upper bound of left-hand side variable <%s> already enforced in conflict set\n",
1048 	            SCIPvarGetName(genvbound->var));
1049 	      }
1050 	      else
1051 	      {
1052 	         SCIPdebugMsg(scip, "adding upper bound of left-hand side variable <%s>\n", SCIPvarGetName(genvbound->var));
1053 	
1054 	         SCIP_CALL( SCIPaddConflictRelaxedUb(scip, genvbound->var, NULL, bound) );
1055 	      }
1056 	   }
1057 	   /* left-hand side variable <= ..., i.e., - left-hand side variable >= ... */
1058 	   else
1059 	   {
1060 	      SCIP_Real infeasthreshold;
1061 	      SCIP_Real bound;
1062 	
1063 	      /* get minimal right-hand side bound that leads to infeasibility; try with a factor of 2 first for robustness */
1064 	      bound = REALABS(SCIPvarGetLbLocal(genvbound->var));
1065 	      infeasthreshold = MAX(bound, 1.0) * 2 * SCIPfeastol(scip);
1066 	      bound = -SCIPvarGetLbLocal(genvbound->var) + infeasthreshold;
1067 	
1068 	      /* add right-hand side variables that force the upper bound of the left-hand side variable below its lower bound
1069 	       * to conflict set
1070 	       */
1071 	      SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1072 	      assert(!success || SCIPisFeasLT(scip, -bound, SCIPvarGetLbLocal(genvbound->var)));
1073 	
1074 	      /* if infeasibility cannot be proven with the tighter bound, try with actual bound */
1075 	      if( !success )
1076 	      {
1077 	         bound = REALABS(SCIPvarGetLbLocal(genvbound->var));
1078 	         infeasthreshold = MAX(bound, 1.0) * SCIPfeastol(scip);
1079 	         bound = -SCIPvarGetLbLocal(genvbound->var) + infeasthreshold;
1080 	
1081 	         SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1082 	         success = success && SCIPisFeasLT(scip, -bound, SCIPvarGetLbLocal(genvbound->var));
1083 	      }
1084 	
1085 	      /* compute lower bound on left-hand side variable that leads to infeasibility */
1086 	      bound = -bound + infeasthreshold;
1087 	      success = success && SCIPisLE(scip, bound, SCIPvarGetLbLocal(genvbound->var));
1088 	
1089 	      /* initial reason could not be constructed, maybe due to numerics; do not apply conflict analysis */
1090 	      if( !success )
1091 	      {
1092 	         SCIPdebugMsg(scip, "strange: could not create initial reason to start conflict analysis\n");
1093 	         return SCIP_OKAY;
1094 	      }
1095 	
1096 	      /* if bound is already enforced by conflict set we do not have to add it */
1097 	      if( SCIPisLE(scip, bound, SCIPgetConflictVarLb(scip, genvbound->var)) )
1098 	      {
1099 	         SCIPdebugMsg(scip, "skipping lower bound of left-hand side variable <%s> already enforced in conflict set\n",
1100 	            SCIPvarGetName(genvbound->var));
1101 	      }
1102 	      else
1103 	      {
1104 	         SCIPdebugMsg(scip, "adding lower bound of left-hand side variable <%s>\n", SCIPvarGetName(genvbound->var));
1105 	
1106 	         SCIP_CALL( SCIPaddConflictRelaxedLb(scip, genvbound->var, NULL, bound) );
1107 	      }
1108 	   }
1109 	
1110 	   /* analyze the conflict */
1111 	   SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1112 	
1113 	   return SCIP_OKAY;
1114 	}
1115 	
1116 	/** apply propagation for one generalized variable bound; also if the left-hand side variable is locally fixed, we
1117 	 *  compute the right-hand side minactivity to possibly detect infeasibility
1118 	 */
1119 	static
1120 	SCIP_RETCODE applyGenVBound(
1121 	   SCIP*                 scip,               /**< SCIP data structure */
1122 	   SCIP_PROP*            prop,               /**< genvbounds propagator */
1123 	   GENVBOUND*            genvbound,          /**< genvbound data structure */
1124 	   SCIP_Bool             global,             /**< apply global bound changes? (global: true, local: false)*/
1125 	   SCIP_RESULT*          result,             /**< result pointer */
1126 	   int*                  nchgbds             /**< counter to increment if bound was tightened */
1127 	   )
1128 	{
1129 	   SCIP_Real boundval;
1130 	   SCIP_Bool infeas;
1131 	   SCIP_Bool tightened;
1132 	
1133 	   assert(scip != NULL);
1134 	   assert(genvbound != NULL);
1135 	   assert(genvbound->var != NULL);
1136 	   assert(SCIPvarGetStatus(genvbound->var) != SCIP_VARSTATUS_MULTAGGR);
1137 	   assert(result != NULL);
1138 	   assert(*result != SCIP_DIDNOTRUN);
1139 	
1140 	   /* get bound value provided by genvbound */
1141 	   boundval = getGenVBoundsBound(scip, genvbound, global);
1142 	
1143 	   if( SCIPisInfinity(scip, REALABS(boundval)) )
1144 	      return SCIP_OKAY;
1145 	
1146 	#ifdef SCIP_DEBUG
1147 	   {
1148 	      SCIP_Real lb;
1149 	      SCIP_Real ub;
1150 	      SCIP_Real new_lb;
1151 	      SCIP_Real new_ub;
1152 	
1153 	      lb = global ? SCIPvarGetLbGlobal(genvbound->var) : SCIPvarGetLbLocal(genvbound->var);
1154 	      ub = global ? SCIPvarGetUbGlobal(genvbound->var) : SCIPvarGetUbLocal(genvbound->var);
1155 	      new_lb = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? boundval : lb;
1156 	      new_ub = genvbound->boundtype == SCIP_BOUNDTYPE_UPPER ? boundval : ub;
1157 	
1158 	      SCIPdebugMsg(scip, "  %s genvbound propagation for <%s>\n", global ?
1159 	         "global" : "local", SCIPvarGetName(genvbound->var));
1160 	      SCIPdebugMsg(scip, "  genvbound: ");
1161 	      printGenVBound(scip, genvbound);
1162 	      SCIPdebugMsg(scip, "    [%.15g,%.15g] -> [%.15g,%.15g]\n", lb, ub, new_lb, new_ub);
1163 	   }
1164 	#endif
1165 	
1166 	   /* tighten bound globally */
1167 	   if( global || genvbound->ncoefs <= 0 )
1168 	   {
1169 	      if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
1170 	      {
1171 	         SCIP_CALL( SCIPtightenVarLbGlobal(scip, genvbound->var, boundval, FALSE, &infeas, &tightened) );
1172 	      }
1173 	      else
1174 	      {
1175 	         SCIP_CALL( SCIPtightenVarUbGlobal(scip, genvbound->var, boundval, FALSE, &infeas, &tightened) );
1176 	      }
1177 	   }
1178 	   /* tighten bound locally and start conflict analysis in case of infeasibility; as inferinfo we pass the index of the
1179 	    * genvbound that was used for propagation
1180 	    */
1181 	   else
1182 	   {
1183 	      if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
1184 	      {
1185 	         SCIP_CALL( SCIPinferVarLbProp(scip, genvbound->var, boundval, prop, genvbound->index, FALSE, &infeas, &tightened) );
1186 	
1187 	         /* initialize conflict analysis if infeasible */
1188 	         if( infeas )
1189 	         {
1190 	            SCIPdebugMsg(scip, " -> lower bound tightening on variable <%s> led to infeasibility\n",
1191 	                  SCIPvarGetName(genvbound->var));
1192 	
1193 	            SCIP_CALL( analyzeGenVBoundConflict(scip, genvbound) );
1194 	         }
1195 	      }
1196 	      else
1197 	      {
1198 	         SCIP_CALL( SCIPinferVarUbProp(scip, genvbound->var, boundval, prop, genvbound->index, FALSE, &infeas, &tightened) );
1199 	
1200 	         /* initialize conflict analysis if infeasible */
1201 	         if( infeas )
1202 	         {
1203 	            SCIPdebugMsg(scip, " -> upper bound tightening on variable <%s> led to infeasibility\n",
1204 	                  SCIPvarGetName(genvbound->var));
1205 	
1206 	            SCIP_CALL( analyzeGenVBoundConflict(scip, genvbound) );
1207 	         }
1208 	      }
1209 	   }
1210 	
1211 	   /* handle result */
1212 	   if( infeas )
1213 	   {
1214 	      *result = SCIP_CUTOFF;
1215 	      SCIPdebugMsg(scip, "    cutoff!\n");
1216 	   }
1217 	   else if( tightened )
1218 	   {
1219 	      *result = SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING ? SCIP_SUCCESS : SCIP_REDUCEDDOM;
1220 	      if( nchgbds != NULL )
1221 	         ++(*nchgbds);
1222 	      SCIPdebugMsg(scip, "    tightened!\n");
1223 	   }
1224 	
1225 	   return SCIP_OKAY;
1226 	}
1227 	
1228 	#ifdef SCIP_DEBUG
1229 	/** prints event data as debug message */
1230 	static
1231 	void printEventData(
1232 	   SCIP_EVENTDATA*       eventdata,
1233 	   SCIP_BOUNDTYPE        boundtype
1234 	   )
1235 	{
1236 	   int i;
1237 	
1238 	   SCIPdebugMessage("event data: %s bound of <%s> tightened ==> start propagating at ",
1239 	      boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(eventdata->var));
1240 	
1241 	   /* if there is eventdata it should contain at least one starting index */
1242 	   assert(eventdata->nstarts > 0);
1243 	
1244 	   for( i = 0; i < eventdata->nstarts; i++ )
1245 	   {
1246 	      SCIPdebugPrintf("(component %d, index %d) ", eventdata->startcomponents[i], eventdata->startindices[i]);
1247 	   }
1248 	   SCIPdebugPrintf("\n");
1249 	}
1250 	#endif
1251 	
1252 	/** frees event data */
1253 	static
1254 	SCIP_RETCODE freeEventData(
1255 	   SCIP*                 scip,               /**< SCIP data structure */
1256 	   SCIP_EVENTDATA**      eventdata           /**< event data to be freed */
1257 	   )
1258 	{
1259 	   assert(scip != NULL);
1260 	   assert(eventdata != NULL);
1261 	   assert(*eventdata != NULL);
1262 	
1263 	   SCIPfreeBlockMemoryArray(scip, &((*eventdata)->startcomponents), (*eventdata)->startindicessize);
1264 	   SCIPfreeBlockMemoryArray(scip, &((*eventdata)->startindices), (*eventdata)->startindicessize);
1265 	
1266 	   (*eventdata)->startindicessize = 0;
1267 	   (*eventdata)->nstarts = -1;
1268 	   (*eventdata)->var = NULL;
1269 	   (*eventdata)->prop = NULL;
1270 	
1271 	   SCIPfreeBlockMemory(scip, eventdata);
1272 	
1273 	   return SCIP_OKAY;
1274 	}
1275 	
1276 	/** frees all eventdata stored */
1277 	static
1278 	SCIP_RETCODE freeAllEventData(
1279 	   SCIP*                 scip,               /**< SCIP data structure */
1280 	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
1281 	   )
1282 	{
1283 	   int i;
1284 	
1285 	   assert(scip != NULL);
1286 	   assert(propdata != NULL);
1287 	
1288 	   if( propdata->lbevents != NULL )
1289 	   {
1290 	      assert(propdata->ubevents != NULL);
1291 	      assert(propdata->lbeventsmap != NULL);
1292 	      assert(propdata->ubeventsmap != NULL);
1293 	
1294 	      SCIPhashmapFree(&(propdata->lbeventsmap));
1295 	      SCIPhashmapFree(&(propdata->ubeventsmap));
1296 	
1297 	      for( i = propdata->nlbevents - 1; i >= 0; i-- )
1298 	      {
1299 	         SCIP_CALL( freeEventData(scip, &(propdata->lbevents[i])) );
1300 	      }
1301 	
1302 	      for( i = propdata->nubevents - 1; i >= 0; i-- )
1303 	      {
1304 	         SCIP_CALL( freeEventData(scip, &(propdata->ubevents[i])) );
1305 	      }
1306 	
1307 	      SCIPfreeBlockMemoryArray(scip, &(propdata->ubevents), propdata->nubevents);
1308 	      SCIPfreeBlockMemoryArray(scip, &(propdata->lbevents), propdata->nlbevents);
1309 	      propdata->nlbevents = -1;
1310 	      propdata->nubevents = -1;
1311 	   }
1312 	
1313 	   assert(propdata->lbevents == NULL);
1314 	   assert(propdata->ubevents == NULL);
1315 	   assert(propdata->lbeventsmap == NULL);
1316 	   assert(propdata->ubeventsmap == NULL);
1317 	   assert(propdata->nlbevents == -1);
1318 	   assert(propdata->nubevents == -1);
1319 	
1320 	   return SCIP_OKAY;
1321 	}
1322 	
1323 	/** drops all events caught by genvbounds propagator and frees their data */
1324 	static
1325 	SCIP_RETCODE dropAndFreeEvents(
1326 	   SCIP*                 scip,               /**< SCIP data structure */
1327 	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
1328 	   )
1329 	{
1330 	   int i;
1331 	
1332 	   SCIPdebugMsg(scip, "drop and free events\n");
1333 	
1334 	   assert(scip != NULL);
1335 	   assert(propdata != NULL);
1336 	   assert(propdata->eventhdlr != NULL);
1337 	
1338 	   if( propdata->lbevents != NULL )
1339 	   {
1340 	      assert(propdata->ubevents != NULL);
1341 	      assert(propdata->nlbevents >= 0);
1342 	      assert(propdata->nubevents >= 0);
1343 	
1344 	      for( i = propdata->nlbevents - 1; i >= 0; i-- )
1345 	      {
1346 	         /* drop event */
1347 	         SCIP_CALL( SCIPdropVarEvent(scip, propdata->lbevents[i]->var, SCIP_EVENTTYPE_LBTIGHTENED, propdata->eventhdlr,
1348 	               propdata->lbevents[i], -1) );
1349 	      }
1350 	
1351 	      for( i = propdata->nubevents - 1; i >= 0; i-- )
1352 	      {
1353 	         /* drop event */
1354 	         SCIP_CALL( SCIPdropVarEvent(scip, propdata->ubevents[i]->var, SCIP_EVENTTYPE_UBTIGHTENED, propdata->eventhdlr,
1355 	               propdata->ubevents[i], -1) );
1356 	      }
1357 	
1358 	      /* free event data */
1359 	      SCIP_CALL( freeAllEventData(scip, propdata) );
1360 	   }
1361 	
1362 	   assert(propdata->lbevents == NULL);
1363 	   assert(propdata->ubevents == NULL);
1364 	   assert(propdata->nlbevents == -1);
1365 	   assert(propdata->nubevents == -1);
1366 	
1367 	   return SCIP_OKAY;
1368 	}
1369 	
1370 	/** returns the corresponding event data entry in the corresponding array, if there is one; if not: allocates a new
1371 	 *  event data entry, stores it in the array and returns its adress
1372 	 */
1373 	static
1374 	SCIP_RETCODE getEventData(
1375 	   SCIP*                 scip,               /**< SCIP data structure */
1376 	   SCIP_PROPDATA*        propdata,           /**< data of the genvbounds propagator */
1377 	   SCIP_VAR*             var,                /**< variable */
1378 	   SCIP_BOUNDTYPE        boundtype,          /**< type of bound */
1379 	   SCIP_EVENTDATA**      eventdata           /**< event data to return */
1380 	   )
1381 	{
1382 	   SCIP_HASHMAP* hashmap;
1383 	
1384 	   assert(scip != NULL);
1385 	   assert(propdata != NULL);
1386 	   assert(var != NULL);
1387 	
1388 	   hashmap = boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbeventsmap : propdata->ubeventsmap;
1389 	
1390 	   if( SCIPhashmapExists(hashmap, var) )
1391 	      *eventdata = (SCIP_EVENTDATA*) SCIPhashmapGetImage(hashmap, var);
1392 	   else
1393 	   {
1394 	      /* set up new eventdata entry */
1395 	      SCIP_CALL( SCIPallocBlockMemory(scip, eventdata) );
1396 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*eventdata)->startcomponents), propdata->ncomponents) );
1397 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*eventdata)->startindices), propdata->ncomponents) );
1398 	      (*eventdata)->startindicessize = propdata->ncomponents;
1399 	      (*eventdata)->nstarts = 0;
1400 	      (*eventdata)->var = var;
1401 	      (*eventdata)->prop = propdata->prop;
1402 	
1403 	      /* store event data in eventarray */
1404 	      if( boundtype == SCIP_BOUNDTYPE_LOWER )
1405 	      {
1406 	         propdata->lbevents[propdata->nlbevents] = *eventdata;
1407 	         propdata->nlbevents++;
1408 	      }
1409 	      else
1410 	      {
1411 	         propdata->ubevents[propdata->nubevents] = *eventdata;
1412 	         propdata->nubevents++;
1413 	      }
1414 	
1415 	      /* store hashmap entry */
1416 	      SCIP_CALL( SCIPhashmapInsert(hashmap, var, (*eventdata)) );
1417 	   }
1418 	
1419 	   return SCIP_OKAY;
1420 	}
1421 	
1422 	/** adds an event to the event array lbevents (if boundtype == SCIP_BOUNDTYPE_LOWER) or ubevents (if boundtype ==
1423 	 *  SCIP_BOUNDTYPE_UPPER)
1424 	 */
1425 	static
1426 	SCIP_RETCODE addEventData(
1427 	   SCIP*                 scip,               /**< SCIP data structure */
1428 	   SCIP_PROPDATA*        propdata,           /**< data of the genvbounds propagator */
1429 	   SCIP_VAR*             var,                /**< variable thats event to be added */
1430 	   int                   startindex,         /**< starting index */
1431 	   int                   startcomponent,     /**< starting components index */
1432 	   SCIP_BOUNDTYPE        boundtype           /**< type of bound */
1433 	   )
1434 	{
1435 	   SCIP_EVENTDATA* eventdata;
1436 	
1437 	   assert(scip != NULL);
1438 	   assert(propdata != NULL);
1439 	   assert(var != NULL);
1440 	   assert(startindex >= 0);
1441 	   assert(startcomponent >= 0);
1442 	
1443 	   /* get eventdata entry */
1444 	   SCIP_CALL( getEventData(scip, propdata, var, boundtype, &eventdata) );
1445 	   assert(eventdata != NULL);
1446 	
1447 	   if( eventdata->nstarts > 0 && eventdata->startcomponents[eventdata->nstarts - 1] == startcomponent )
1448 	   {
1449 	      /* if there is already a starting index for startcomponent stored at the last entry of eventdata->startindices,
1450 	       * it should be smaller; this relies on the implementation of setUpEvents(), calling addEventData() in
1451 	       * topological order
1452 	       */
1453 	      assert(eventdata->startindices[eventdata->nstarts - 1] < startindex);
1454 	   }
1455 	   else
1456 	   {
1457 	      /* append starting information */
1458 	      eventdata->startcomponents[eventdata->nstarts] = startcomponent;
1459 	      eventdata->startindices[eventdata->nstarts] = startindex;
1460 	
1461 	      /* increase counter */
1462 	      eventdata->nstarts++;
1463 	   }
1464 	
1465 	   return SCIP_OKAY;
1466 	}
1467 	
1468 	static
1469 	SCIP_RETCODE setUpEvents(
1470 	   SCIP*                 scip,               /**< SCIP data structure */
1471 	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
1472 	   )
1473 	{
1474 	   int nprobvars;
1475 	   int i;
1476 	
1477 	   assert(scip != NULL);
1478 	   assert(propdata != NULL);
1479 	   assert(propdata->eventhdlr != NULL);
1480 	   assert(propdata->lbevents == NULL);
1481 	   assert(propdata->ubevents == NULL);
1482 	   assert(propdata->issorted);
1483 	   assert(propdata->nlbevents == -1);
1484 	   assert(propdata->nubevents == -1);
1485 	
1486 	   SCIPdebugMsg(scip, "set up events\n");
1487 	
1488 	   /* allocate lbevents, ubevents, and their hashmaps */
1489 	   nprobvars = SCIPgetNVars(scip) + SCIPgetNFixedVars(scip);
1490 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->lbevents), nprobvars) );
1491 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->ubevents), nprobvars) );
1492 	   SCIP_CALL( SCIPhashmapCreate(&(propdata->lbeventsmap), SCIPblkmem(scip), nprobvars) );
1493 	   SCIP_CALL( SCIPhashmapCreate(&(propdata->ubeventsmap), SCIPblkmem(scip), nprobvars) );
1494 	   propdata->nlbevents = 0;
1495 	   propdata->nubevents = 0;
1496 	
1497 	   /* loop over all components of genvboundstore */
1498 	   for( i = 0; i < propdata->ncomponents; i++ )
1499 	   {
1500 	      int j;
1501 	
1502 	      /* loop over all genvbounds in this component */
1503 	      for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ ) /*lint !e679*/
1504 	      {
1505 	         GENVBOUND* genvbound;
1506 	         int k;
1507 	
1508 	         assert(j < propdata->ngenvbounds);
1509 	
1510 	         genvbound = propdata->genvboundstore[j];
1511 	         assert(genvbound != NULL);
1512 	
1513 	         /* loop over all coefficients in this genvbound */
1514 	         for( k = 0; k < genvbound->ncoefs; k++ )
1515 	         {
1516 	            if( SCIPisPositive(scip, genvbound->coefs[k]) )
1517 	            {
1518 	               SCIP_CALL( addEventData(scip, propdata, genvbound->vars[k], j, i, SCIP_BOUNDTYPE_LOWER) );
1519 	            }
1520 	            else
1521 	            {
1522 	               SCIP_CALL( addEventData(scip, propdata, genvbound->vars[k], j, i, SCIP_BOUNDTYPE_UPPER) );
1523 	            }
1524 	         }
1525 	      }
1526 	   }
1527 	
1528 	   /* resize lbevents and ubevents array */
1529 	   assert(propdata->nlbevents <= nprobvars);
1530 	   assert(propdata->nubevents <= nprobvars);
1531 	   if( propdata->nlbevents < nprobvars )
1532 	   {
1533 	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->lbevents), nprobvars, propdata->nlbevents) );
1534 	   }
1535 	   if( propdata->nubevents < nprobvars )
1536 	   {
1537 	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->ubevents), nprobvars, propdata->nubevents) );
1538 	   }
1539 	
1540 	   /* resize and register lower bound events */
1541 	   for( i = 0; i < propdata->nlbevents; i++ )
1542 	   {
1543 	      SCIP_EVENTDATA* eventdata = propdata->lbevents[i];
1544 	
1545 	      assert(eventdata != NULL);
1546 	      assert(eventdata->nstarts > 0);
1547 	      assert(eventdata->startcomponents != NULL);
1548 	      assert(eventdata->startindices != NULL);
1549 	
1550 	      /* resize arrays stored in eventdata */
1551 	      if( eventdata->startindicessize != eventdata->nstarts )
1552 	      {
1553 	         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startcomponents), eventdata->startindicessize, \
1554 	               eventdata->nstarts) );
1555 	         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startindices), eventdata->startindicessize, \
1556 	               eventdata->nstarts) );
1557 	         eventdata->startindicessize = eventdata->nstarts;
1558 	      }
1559 	
1560 	      /* register event */
1561 	      SCIP_CALL( SCIPcatchVarEvent(scip, eventdata->var, SCIP_EVENTTYPE_LBTIGHTENED, propdata->eventhdlr, eventdata, \
1562 	            NULL) );
1563 	   }
1564 	
1565 	   /* resize and register upper bound events */
1566 	   for( i = 0; i < propdata->nubevents; i++ )
1567 	   {
1568 	      SCIP_EVENTDATA* eventdata = propdata->ubevents[i];
1569 	
1570 	      assert(eventdata != NULL);
1571 	      assert(eventdata->nstarts > 0);
1572 	      assert(eventdata->startcomponents != NULL);
1573 	      assert(eventdata->startindices != NULL);
1574 	
1575 	      /* resize arrays stored in eventdata */
1576 	      if( eventdata->startindicessize != eventdata->nstarts )
1577 	      {
1578 	         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startcomponents), eventdata->startindicessize, \
1579 	               eventdata->nstarts) );
1580 	         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startindices), eventdata->startindicessize, \
1581 	               eventdata->nstarts) );
1582 	         eventdata->startindicessize = eventdata->nstarts;
1583 	      }
1584 	      /* register event */
1585 	      SCIP_CALL( SCIPcatchVarEvent(scip, eventdata->var, SCIP_EVENTTYPE_UBTIGHTENED, propdata->eventhdlr, eventdata,
1586 	            NULL) );
1587 	   }
1588 	
1589 	   return SCIP_OKAY;
1590 	}
1591 	
1592 	/** performs a topological sort on genvboundstore array
1593 	 *
1594 	 *  The genvbounds graph is defined as follows: Given two genvbounds
1595 	 *
1596 	 *    (genvbound1)      c1 * x_i1 >= RHS1
1597 	 *
1598 	 *  and
1599 	 *
1600 	 *    (genvbound2)      c2 * x_i2 >= RHS2,
1601 	 *
1602 	 *  there is an arc from genvbound1 to genvbound2 iff c1 = +1 and x_i1 appears with positive coefficient in RHS2 or
1603 	 *  c1 = -1 and x_i1 appears with negative coefficient in RHS2; in this case, a bound change of x_i1 deduced from
1604 	 *  genvbound1 improves genvbound2's minactivity in RHS2.
1605 	 *
1606 	 *  The method computes the strongly connected components and sorts them topologically. The order of the nodes in an
1607 	 *  strongly connected component is arbitrary.
1608 	 */
1609 	static
1610 	SCIP_RETCODE sortGenVBounds(
1611 	   SCIP*                 scip,               /**< SCIP data structure */
1612 	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
1613 	   )
1614 	{
1615 	   GENVBOUND** genvboundssorted;            /* array to store the sorted genvbounds */
1616 	   SCIP_DIGRAPH* graph;
1617 	   int* strongcomponents;
1618 	   int* strongcompstartidx;
1619 	   int sortedindex;
1620 	   int i;
1621 	
1622 	   assert(scip != NULL);
1623 	   assert(propdata != NULL);
1624 	   assert(propdata->componentsstart == NULL);
1625 	
1626 	   SCIPdebugMsg(scip, "(re-)sort genvbounds topologically\n");
1627 	
1628 	   /* create digraph */
1629 	   SCIP_CALL( SCIPcreateDigraph(scip, &graph, propdata->ngenvbounds) );
1630 	
1631 	   /* add outgoing arcs for each genvbound */
1632 	   for( i = 0; i < propdata->ngenvbounds; i++ )
1633 	   {
1634 	      GENVBOUND* genvbound;
1635 	      int j;
1636 	
1637 	      assert(i < propdata->ngenvbounds);
1638 	
1639 	      genvbound = propdata->genvboundstore[i];
1640 	
1641 	      for( j = 0; j < genvbound->ncoefs; j++ )
1642 	      {
1643 	         if( SCIPisPositive(scip, genvbound->coefs[j]) &&
1644 	            SCIPhashmapExists(propdata->lbgenvbounds, genvbound->vars[j]) )
1645 	         {
1646 	            int from = ((GENVBOUND*) SCIPhashmapGetImage(propdata->lbgenvbounds, genvbound->vars[j]))->index;
1647 	            SCIP_CALL( SCIPdigraphAddArc(graph, from, i, NULL) );
1648 	         }
1649 	         else if( SCIPisNegative(scip, genvbound->coefs[j]) &&
1650 	            SCIPhashmapExists(propdata->ubgenvbounds, genvbound->vars[j]) )
1651 	         {
1652 	            int from = ((GENVBOUND*) SCIPhashmapGetImage(propdata->ubgenvbounds, genvbound->vars[j]))->index;
1653 	            SCIP_CALL( SCIPdigraphAddArc(graph, from, i, NULL) );
1654 	         }
1655 	      }
1656 	   }
1657 	
1658 	   /* perform the topological sort */
1659 	   SCIP_CALL( SCIPdigraphComputeUndirectedComponents(graph, 1, NULL, &(propdata->ncomponents)) );
1660 	   SCIP_CALL( SCIPdigraphTopoSortComponents(graph) );
1661 	   assert(SCIPdigraphGetNComponents(graph) == propdata->ncomponents);
1662 	
1663 	   /* allocate memory for genvboundssorted and componentsstart array */
1664 	   SCIP_CALL( SCIPallocBufferArray(scip, &genvboundssorted, propdata->ngenvbounds) );
1665 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->componentsstart), propdata->ncomponents + 1) );
1666 	   propdata->componentsstartsize = propdata->ncomponents + 1;
1667 	
1668 	   /* allocate memory for strong component arrays */
1669 	   SCIP_CALL( SCIPallocBufferArray(scip, &strongcomponents, SCIPdigraphGetNNodes(graph)) ); /*lint !e666*/
1670 	   SCIP_CALL( SCIPallocBufferArray(scip, &strongcompstartidx, SCIPdigraphGetNNodes(graph) + 1) ); /*lint !e666*/
1671 	
1672 	   /* compute sorted genvbounds array, fill componentsstart array */
1673 	   sortedindex = 0;
1674 	   propdata->componentsstart[propdata->ncomponents] = propdata->ngenvbounds;
1675 	   for( i = 0; i < propdata->ncomponents; i++ )
1676 	   {
1677 	      int j;
1678 	      int *nodes;
1679 	      int nnodes;
1680 	      int nstrongcomponents;
1681 	
1682 	      SCIPdigraphGetComponent(graph, i, &nodes, &nnodes);
1683 	      propdata->componentsstart[i] = sortedindex;
1684 	
1685 	      /* compute the strong components of the i-th undirected component */
1686 	      if( nnodes > 2 )
1687 	      {
1688 	         SCIP_CALL( SCIPdigraphComputeDirectedComponents(graph, i, strongcomponents, strongcompstartidx,
1689 	               &nstrongcomponents) );
1690 	
1691 	         for( j = 0; j < nnodes; ++j )
1692 	         {
1693 	            int node;
1694 	
1695 	            /* take the nodes at the end of the strong components array first to respect the topological
1696 	             * order of the different strong components
1697 	             */
1698 	            node = strongcomponents[nnodes - j - 1];
1699 	
1700 	            assert(node < propdata->ngenvbounds);
1701 	            genvboundssorted[sortedindex] = propdata->genvboundstore[node];
1702 	            sortedindex++;
1703 	         }
1704 	      }
1705 	      else
1706 	      {
1707 	         for( j = 0; j < nnodes; j++ )
1708 	         {
1709 	            assert(nodes[j] < propdata->ngenvbounds);
1710 	            genvboundssorted[sortedindex] = propdata->genvboundstore[nodes[j]];
1711 	            sortedindex++;
1712 	         }
1713 	      }
1714 	   }
1715 	   assert(sortedindex == propdata->ngenvbounds);
1716 	
1717 	   /* copy sorted genvbounds into genvboundstore */
1718 	   for( i = 0; i < propdata->ngenvbounds; i++ )
1719 	   {
1720 	      assert(genvboundssorted[i] != NULL);
1721 	
1722 	      propdata->genvboundstore[i] = genvboundssorted[i];
1723 	      propdata->genvboundstore[i]->index = i;
1724 	   }
1725 	
1726 	   /* free strong component arrays */
1727 	   SCIPfreeBufferArray(scip, &strongcompstartidx);
1728 	   SCIPfreeBufferArray(scip, &strongcomponents);
1729 	
1730 	   SCIPfreeBufferArray(scip, &(genvboundssorted));
1731 	
1732 	   /* free digraph */
1733 	   SCIPdigraphFree(&graph);
1734 	
1735 	   /* remember genvboundstore as sorted */
1736 	   propdata->issorted = TRUE;
1737 	
1738 	#ifdef SCIP_DEBUG
1739 	   SCIPdebugMsg(scip, "genvbounds got: %d\n", propdata->ngenvbounds);
1740 	   for( i = 0; i < propdata->ncomponents; i++ )
1741 	   {
1742 	      int j;
1743 	
1744 	      SCIPdebugMsg(scip, "{\n");
1745 	
1746 	      for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ )
1747 	      {
1748 	         SCIPdebugMsg(scip, "  [%d] ", j);
1749 	         printGenVBound(scip, propdata->genvboundstore[j]);
1750 	      }
1751 	
1752 	      SCIPdebugMsg(scip, "}\n");
1753 	   }
1754 	#endif
1755 	
1756 	   return SCIP_OKAY;
1757 	}
1758 	
1759 	/** apply propagation of generalized variable bounds */
1760 	static
1761 	SCIP_RETCODE applyGenVBounds(
1762 	   SCIP*                 scip,               /**< SCIP data structure */
1763 	   SCIP_PROP*            prop,               /**< genvbounds propagator */
1764 	   SCIP_Bool             global,             /**< use global variable bounds for propagation? */
1765 	   SCIP_RESULT*          result,             /**< result pointer */
1766 	   int*                  nchgbds             /**< counter to increase by the number of changed bounds */
1767 	   )
1768 	{
1769 	   SCIP_PROPDATA* propdata;
1770 	   int* startingcomponents;
1771 	   int* startingindices;
1772 	   int nindices;
1773 	   int i;
1774 	
1775 	   SCIPdebugMsg(scip, "applying %s genvbound propagation in depth %d\n", global ?
1776 	      "global" : "local", SCIPgetDepth(scip));
1777 	
1778 	   assert(scip != NULL);
1779 	   assert(prop != NULL);
1780 	   assert(result != NULL);
1781 	
1782 	   propdata = SCIPpropGetData(prop);
1783 	   assert(propdata != NULL);
1784 	   assert(propdata->genvboundstore != NULL);
1785 	
1786 	   if( *result == SCIP_DIDNOTRUN )
1787 	      *result = SCIP_DIDNOTFIND;
1788 	
1789 	   /* if the genvbounds are not sorted, i.e. if root node processing has not been finished, yet, we just propagate in
1790 	    * the order in which they have been added to genvboundstore
1791 	    */
1792 	   if( !propdata->issorted )
1793 	   {
1794 	      int j;
1795 	
1796 	      assert(!propdata->sort || SCIPinProbing(scip) || SCIPgetDepth(scip) == 0);
1797 	
1798 	      for( j = 0; j < propdata->ngenvbounds && *result != SCIP_CUTOFF; j++ )
1799 	      {
1800 	         if( ! SCIPvarIsActive(propdata->genvboundstore[j]->var) )
1801 	         {
1802 	            /**@todo resolve multiaggregation in exitpre */
1803 	         }
1804 	         else
1805 	         {
1806 	            SCIPdebugMsg(scip, "applying genvbound with index %d (unsorted mode)\n", j);
1807 	            SCIP_CALL( applyGenVBound(scip, prop, propdata->genvboundstore[j], global, result, nchgbds) );
1808 	         }
1809 	      }
1810 	
1811 	      return SCIP_OKAY;
1812 	   }
1813 	
1814 	   /* otherwise, we propagate only components affected by the latest bound changes */
1815 	   startingcomponents = global ? propdata->gstartcomponents : propdata->startcomponents;
1816 	   startingindices = global ? propdata->gstartindices : propdata->startindices;
1817 	   nindices = global ? propdata->ngindices : propdata->nindices;
1818 	
1819 	   for( i = 0; i < nindices && *result != SCIP_CUTOFF; i++ )
1820 	   {
1821 	      int j;
1822 	
1823 	      SCIPdebugMsg(scip, "starting in component %d at index %d\n", startingcomponents[i], startingindices[i]);
1824 	      for( j = startingindices[i]; j < propdata->componentsstart[startingcomponents[i] + 1] &&
1825 	         *result != SCIP_CUTOFF; j++ ) /*lint !e679*/
1826 	      {
1827 	         assert(j < propdata->ngenvbounds);
1828 	
1829 	         if( ! SCIPvarIsActive(propdata->genvboundstore[j]->var) )
1830 	         {
1831 	            /**@todo resolve multiaggregation in exitpre */
1832 	         }
1833 	         else
1834 	         {
1835 	            SCIPdebugMsg(scip, "applying genvbound with index %d, component %d\n", j, startingcomponents[i]);
1836 	            SCIP_CALL( applyGenVBound(scip, prop, propdata->genvboundstore[j], global, result, nchgbds) );
1837 	         }
1838 	      }
1839 	   }
1840 	
1841 	   /* we dont want to run again caused by this starting data */
1842 	   if( !global )
1843 	   {
1844 	      SCIP_CALL( resetLocalStartingData(scip, propdata) );
1845 	   }
1846 	
1847 	   return SCIP_OKAY;
1848 	}
1849 	
1850 	/** initialize propagator data */
1851 	static
1852 	SCIP_RETCODE initPropdata(
1853 	   SCIP*                 scip,               /**< SCIP data structure */
1854 	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
1855 	   )
1856 	{
1857 	   int nprobvars;
1858 	
1859 	   assert(scip != NULL);
1860 	   assert(propdata != NULL);
1861 	   assert(propdata->eventhdlr != NULL);
1862 	
1863 	   SCIPdebugMsg(scip, "init propdata\n");
1864 	
1865 	   nprobvars = SCIPgetNVars(scip);
1866 	
1867 	   /* init genvboundstore */
1868 	   propdata->genvboundstoresize = 2 * nprobvars;
1869 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize) );
1870 	   BMSclearMemoryArray(propdata->genvboundstore, propdata->genvboundstoresize);
1871 	   propdata->ngenvbounds = 0;
1872 	
1873 	   /* init genvboundstore hashmaps */
1874 	   SCIP_CALL( SCIPhashmapCreate(&(propdata->lbgenvbounds), SCIPblkmem(scip), nprobvars) );
1875 	   SCIP_CALL( SCIPhashmapCreate(&(propdata->ubgenvbounds), SCIPblkmem(scip), nprobvars) );
1876 	
1877 	   return SCIP_OKAY;
1878 	}
1879 	
1880 	/** adds a new genvbound to genvboundstore array and sets a hashmap entry */
1881 	static
1882 	SCIP_RETCODE addNewGenVBound(
1883 	   SCIP*                 scip,               /**< SCIP data structure */
1884 	   SCIP_PROPDATA*        propdata,           /**< data of the genvbounds propagator */
1885 	   GENVBOUND*            genvbound           /**< genvbound to be added */
1886 	   )
1887 	{
1888 	   SCIP_HASHMAP* hashmap;
1889 	
1890 	   assert(scip != NULL);
1891 	   assert(propdata != NULL);
1892 	   assert(genvbound != NULL);
1893 	   assert(getGenVBound(scip, propdata, genvbound->var, genvbound->boundtype) == NULL);
1894 	
1895 	   hashmap = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
1896 	
1897 	   /* e.g., during presolving after a restart, new variables might have been created; in this case, we need to extend
1898 	    * the genvboundstore; the new size may even exceed 2*SCIPgetNVars() if we have genvbounds with nonactive left-hand
1899 	    * side variables
1900 	    */
1901 	   assert(propdata->ngenvbounds <= propdata->genvboundstoresize);
1902 	   if( propdata->ngenvbounds == propdata->genvboundstoresize )
1903 	   {
1904 	      int oldsize = propdata->genvboundstoresize;
1905 	      propdata->genvboundstoresize = 2*propdata->genvboundstoresize + 1;
1906 	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->genvboundstore), oldsize, propdata->genvboundstoresize) );
1907 	   }
1908 	
1909 	   /* new index is propdata->ngenvbounds */
1910 	   SCIP_CALL( SCIPhashmapInsert(hashmap, genvbound->var, genvbound) );
1911 	   propdata->genvboundstore[propdata->ngenvbounds] = genvbound;
1912 	   genvbound->index = propdata->ngenvbounds;
1913 	   propdata->ngenvbounds++;
1914 	
1915 	   assert(propdata->ngenvbounds <= propdata->genvboundstoresize);
1916 	
1917 	   return SCIP_OKAY;
1918 	}
1919 	
1920 	/** runs propagation routine */
1921 	static
1922 	SCIP_RETCODE execGenVBounds(
1923 	   SCIP*                 scip,               /**< SCIP data structure */
1924 	   SCIP_PROPDATA*        propdata,           /**< data of the genvbounds propagator */
1925 	   SCIP_RESULT*          result,             /**< result pointer */
1926 	   SCIP_Bool             local,              /**< should local propagation be applied? */
1927 	   int*                  nchgbds             /**< counter to increase by the number of changed bounds */
1928 	   )
1929 	{
1930 	   assert(scip != NULL);
1931 	   assert(propdata != NULL);
1932 	   assert(propdata->prop != NULL);
1933 	   assert(result != NULL);
1934 	
1935 	   /* we only sort after the root node is finished; this avoids having to sort again after adding more genvbounds; if
1936 	    * the genvbounds are not sorted, we will simply propagate all of them in the order given
1937 	    */
1938 	   if( propdata->sort && !SCIPinProbing(scip) && SCIPgetDepth(scip) > 0 )
1939 	   {
1940 	      if( !propdata->issorted )
1941 	      {
1942 	         *result = SCIP_DIDNOTFIND;
1943 	
1944 	         SCIPdebugMsg(scip, "genvbounds are not sorted\n");
1945 	
1946 	         /* drop and free old events */
1947 	         SCIP_CALL( dropAndFreeEvents(scip, propdata) );
1948 	
1949 	         /* free old starting data */
1950 	         SCIP_CALL( freeStartingData(scip, propdata) );
1951 	
1952 	         /* free sorted components data */
1953 	         SCIP_CALL( freeComponentsData(scip, propdata) );
1954 	
1955 	         /* sort genvbounds */
1956 	         SCIP_CALL( sortGenVBounds(scip, propdata) );
1957 	
1958 	         /* create starting data */
1959 	         SCIP_CALL( createStartingData(scip, propdata) );
1960 	
1961 	         /* fill global starting data */
1962 	         SCIP_CALL( fillGlobalStartingData(scip, propdata) );
1963 	      }
1964 	
1965 	      /* set up new events to catch (if not done so far) */
1966 	      if( propdata->lbevents == NULL )
1967 	      {
1968 	         SCIP_CALL( setUpEvents(scip, propdata) );
1969 	      }
1970 	   }
1971 	
1972 	   /* apply global propagation if primal bound has improved */
1973 	   if( propdata->global && SCIPgetDepth(scip) > 0 && SCIPisFeasLT(scip, SCIPgetCutoffbound(scip), propdata->lastcutoff) )
1974 	   {
1975 	      if( propdata->ngindices > 0 )
1976 	      {
1977 	         SCIP_CALL( applyGenVBounds(scip, propdata->prop, TRUE, result, nchgbds) );
1978 	         assert(*result != SCIP_DIDNOTRUN);
1979 	      }
1980 	
1981 	      /* within the tree, the objective function should not change anymore, hence the cutoff bound should be a stable
1982 	       * point of reference
1983 	       */
1984 	      propdata->lastcutoff = SCIPgetCutoffbound(scip);
1985 	   }
1986 	
1987 	   /* apply local propagation if allowed */
1988 	   if( local && *result != SCIP_CUTOFF )
1989 	   {
1990 	      /* check if local propagation in root node is allowed */
1991 	      if( SCIPgetDepth(scip) > 0 || propdata->propinrootnode )
1992 	      {
1993 	         /* if genvbounds are already sorted, check if bound change events were caught; otherwise apply all genvbounds */
1994 	         if( !propdata->issorted || ( SCIPgetCurrentNode(scip) == propdata->lastnodecaught && propdata->nindices > 0 ) )
1995 	         {
1996 	            SCIP_CALL( applyGenVBounds(scip, propdata->prop, FALSE, result, nchgbds) );
1997 	            assert(*result != SCIP_DIDNOTRUN);
1998 	         }
1999 	      }
2000 	   }
2001 	
2002 	   return SCIP_OKAY;
2003 	}
2004 	
2005 	/* adds all genvbounds in the genvboundstore as constraints to the problem; afterwards clears the genvboundstore */
2006 	static
2007 	SCIP_RETCODE createConstraints(
2008 	   SCIP*                 scip,               /**< SCIP data structure */
2009 	   SCIP_PROPDATA*        propdata            /**< data of the genvbounds propagator */
2010 	   )
2011 	{
2012 	   int i;
2013 	
2014 	   assert(scip != NULL);
2015 	   assert(propdata != NULL);
2016 	   assert(propdata->propasconss);
2017 	
2018 	   /* ensure that the cutoffboundvar is available */
2019 	   if( propdata->cutoffboundvar == NULL )
2020 	   {
2021 	      SCIP_Real ub;
2022 	      char name[16];
2023 	
2024 	      /* set the upper bound to the best primal value in the original problem */
2025 	      ub = getCutoffboundGenVBound(scip);
2026 	
2027 	      SCIPdebugMsg(scip, "initialize cutoffboundvar with UB = %e\n", ub);
2028 	
2029 	      (void) SCIPsnprintf(name, 16, "cutoffboundvar");
2030 	      SCIP_CALL( SCIPcreateVarBasic(scip, &propdata->cutoffboundvar, name, -SCIPinfinity(scip), ub, 0.0, SCIP_VARTYPE_CONTINUOUS) );
2031 	      SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, propdata->cutoffboundvar) );
2032 	
2033 	      SCIP_CALL( SCIPaddVar(scip, propdata->cutoffboundvar) );
2034 	
2035 	      /* lock the variable because it should not be subject to dual presolving reductions; because we create the
2036 	       * linear constraints as non-check constraints, the cutoffboundvar will not be locked by the linear constraint
2037 	       * handler
2038 	       */
2039 	      SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, 1, 1) );
2040 	   }
2041 	
2042 	   assert(propdata->cutoffboundvar != NULL);
2043 	
2044 	   /* now iterate over all genvbounds in the store and construct a linear constraint for each of them */
2045 	   for( i = 0; i < propdata->ngenvbounds; ++i )
2046 	   {
2047 	      GENVBOUND* genvbound;
2048 	      SCIP_CONS* cons;
2049 	      SCIP_VAR** vars;
2050 	      SCIP_Real* vals;
2051 	      char name[SCIP_MAXSTRLEN];
2052 	      int nvars;
2053 	      int j;
2054 	
2055 	      genvbound = propdata->genvboundstore[i];
2056 	      assert(genvbound != NULL);
2057 	
2058 	      nvars = genvbound->ncoefs + 2;
2059 	      SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2060 	      SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
2061 	
2062 	      SCIPdebugMsgPrint(scip, "add cons: ");
2063 	
2064 	      /* copy the coefs/vars array */
2065 	      for( j = 0; j < genvbound->ncoefs; j++ )
2066 	      {
2067 	         vars[j] = genvbound->vars[j];
2068 	         vals[j] = genvbound->coefs[j];
2069 	         SCIPdebugMsgPrint(scip, "%e%s + ", vals[j], SCIPvarGetName(vars[j]));
2070 	      }
2071 	
2072 	      /* add the variable and the coefficient of the genvbound */
2073 	      vars[genvbound->ncoefs] = genvbound->var;
2074 	      vals[genvbound->ncoefs] = (genvbound->boundtype == SCIP_BOUNDTYPE_LOWER) ? -1.0 : 1.0;
2075 	
2076 	      SCIPdebugMsgPrint(scip, "%e%s + ", vals[genvbound->ncoefs], SCIPvarGetName(vars[genvbound->ncoefs]));
2077 	
2078 	      /* add cutoffcoef * cutoffboundvar */
2079 	      vars[genvbound->ncoefs + 1] = propdata->cutoffboundvar;
2080 	      vals[genvbound->ncoefs + 1] = genvbound->cutoffcoef;
2081 	
2082 	      SCIPdebugMsgPrint(scip, "%e%s <= %e\n", vals[genvbound->ncoefs + 1], SCIPvarGetName(vars[genvbound->ncoefs + 1]), -1.0*genvbound->constant);
2083 	
2084 	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "genvbound_cons%d", genvbound->index);
2085 	
2086 	      /* create linear constraint with only propagate flag as TRUE */
2087 	      SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nvars, vars, vals, -SCIPinfinity(scip), -genvbound->constant,
2088 	            FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2089 	
2090 	      SCIP_CALL( SCIPaddCons(scip, cons) );
2091 	      SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2092 	
2093 	      /* free memory */
2094 	      SCIPfreeBufferArray(scip, &vars);
2095 	      SCIPfreeBufferArray(scip, &vals);
2096 	   }
2097 	
2098 	   /* now delete all genvbounds in the genvboundstore */
2099 	   if( propdata->ngenvbounds > 0 )
2100 	   {
2101 	      assert(propdata->genvboundstore != NULL);
2102 	
2103 	      for( i = propdata->ngenvbounds - 1; i >= 0; i-- )
2104 	      {
2105 	         SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
2106 	      }
2107 	
2108 	      /* free genvboundstore hashmaps */
2109 	      SCIPhashmapFree(&(propdata->lbgenvbounds));
2110 	      SCIPhashmapFree(&(propdata->ubgenvbounds));
2111 	
2112 	      /* drop and free all events */
2113 	      SCIP_CALL( dropAndFreeEvents(scip, propdata) );
2114 	
2115 	      /* free componentsstart array */
2116 	      SCIP_CALL( freeComponentsData(scip, propdata) );
2117 	
2118 	      /* free starting indices data */
2119 	      SCIP_CALL( freeStartingData(scip, propdata) );
2120 	
2121 	      SCIPfreeBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize);
2122 	      propdata->genvboundstore = NULL;
2123 	      propdata->genvboundstoresize = 0;
2124 	      propdata->ngenvbounds = 0;
2125 	   }
2126 	
2127 	   return SCIP_OKAY;
2128 	}
2129 	
2130 	
2131 	
2132 	/*
2133 	 * Public methods
2134 	 */
2135 	
2136 	/** adds a generalized variable bound to the genvbounds propagator; if there is already a genvbound for the bound
2137 	 *  "boundtype" of variable "var", it will be replaced
2138 	 */
2139 	SCIP_RETCODE SCIPgenVBoundAdd(
2140 	   SCIP*                 scip,               /**< SCIP data structure */
2141 	   SCIP_PROP*            genvboundprop,      /**< genvbound propagator */
2142 	   SCIP_VAR**            vars,               /**< array of RHSs variables */
2143 	   SCIP_VAR*             var,                /**< LHSs variable */
2144 	   SCIP_Real*            coefs,              /**< array of coefficients for the RHSs variables */
2145 	   int                   ncoefs,             /**< size of coefs array */
2146 	   SCIP_Real             coefcutoffbound,    /**< nonpositive value of the cutoff bounds multiplier */
2147 	   SCIP_Real             constant,           /**< constant term */
2148 	   SCIP_BOUNDTYPE        boundtype           /**< type of bound provided by the genvbound */
2149 	   )
2150 	{
2151 	   /**@todo in debug mode: check if genvbound is nontrivial */
2152 	
2153 	   SCIP_PROPDATA* propdata;
2154 	   GENVBOUND* genvbound;
2155 	   SCIP_Bool newgenvbound;
2156 	   int i;
2157 	
2158 	   assert(scip != NULL);
2159 	   assert(genvboundprop != NULL);
2160 	   assert(strcmp(SCIPpropGetName(genvboundprop), PROP_NAME) == 0);
2161 	   assert(vars != NULL);
2162 	   assert(var != NULL);
2163 	   assert(coefs != NULL);
2164 	   assert(ncoefs >= 0);
2165 	   assert(coefcutoffbound <= 0.0);
2166 	   assert(!SCIPisInfinity(scip, -constant));
2167 	
2168 	   if( ncoefs < 0 || coefcutoffbound > 0.0 || SCIPisInfinity(scip, -constant) )
2169 	   {
2170 	      SCIPerrorMessage("cannot create generalized variable bound from invalid data\n");
2171 	      return SCIP_INVALIDDATA;
2172 	   }
2173 	
2174 	   propdata = SCIPpropGetData(genvboundprop);
2175 	   assert(propdata != NULL);
2176 	
2177 	   /* initialize propdata if not done yet */
2178 	   if( propdata->genvboundstore == NULL )
2179 	   {
2180 	      SCIP_CALL( initPropdata(scip, propdata) );
2181 	   }
2182 	
2183 	   genvbound = getGenVBound(scip, propdata, var, boundtype);
2184 	   newgenvbound = (genvbound == NULL);
2185 	
2186 	   /* release previous variables */
2187 	   if( !newgenvbound )
2188 	   {
2189 	      for( i = 0; i < genvbound->ncoefs; ++i )
2190 	      {
2191 	         assert(genvbound->vars[i] != NULL);
2192 	         SCIP_CALL( SCIPreleaseVar(scip, &(genvbound->vars[i])) );
2193 	      }
2194 	   }
2195 	
2196 	   /* check if there already is a genvbound corresponding to this bound, freeing its data and overwriting it */
2197 	   if( !newgenvbound && genvbound->ncoefs < ncoefs )
2198 	   {
2199 	      /* do not realloc since we do not want to keep and possibly copy the old entries */
2200 	      SCIPfreeBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize);
2201 	      SCIPfreeBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize);
2202 	
2203 	      /* allocate and copy arrays in genvbound */
2204 	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->coefs), coefs, ncoefs) );
2205 	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->vars), vars, ncoefs) );
2206 	      genvbound->coefssize = ncoefs;
2207 	   }
2208 	   else if( !newgenvbound && genvbound->ncoefs == ncoefs )
2209 	   {
2210 	      /* just update entries */
2211 	      for( i = 0; i < ncoefs; i++ )
2212 	      {
2213 	         genvbound->coefs[i] = coefs[i];
2214 	         genvbound->vars[i] = vars[i];
2215 	      }
2216 	   }
2217 	   else if( !newgenvbound && genvbound->ncoefs > ncoefs )
2218 	   {
2219 	      /* reallocate memory for arrays in genvbound to free unused memory */
2220 	      if( genvbound->coefssize < ncoefs )
2221 	      {
2222 	         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize, ncoefs) );
2223 	         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize, ncoefs) );
2224 	         genvbound->coefssize = ncoefs;
2225 	      }
2226 	
2227 	      /* update entries */
2228 	      for( i = 0; i < ncoefs; i++ )
2229 	      {
2230 	         genvbound->coefs[i] = coefs[i];
2231 	         genvbound->vars[i] = vars[i];
2232 	      }
2233 	   }
2234 	   else if( newgenvbound )
2235 	   {
2236 	      /* allocate memory for genvbound data */
2237 	      SCIP_CALL( SCIPallocBlockMemory(scip, &genvbound) );
2238 	
2239 	      /* allocate and copy arrays in genvbound */
2240 	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->coefs), coefs, ncoefs) );
2241 	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->vars), vars, ncoefs) );
2242 	      genvbound->coefssize = ncoefs;
2243 	   }
2244 	
2245 	   /* set up data for genvbound */
2246 	   genvbound->boundtype = boundtype;
2247 	   genvbound->var = var;
2248 	   genvbound->ncoefs = ncoefs;
2249 	   genvbound->constant = constant;
2250 	   genvbound->relaxonly = SCIPvarIsRelaxationOnly(genvbound->var);
2251 	
2252 	   /* capture variables and check for relax-only vars */
2253 	   for( i = 0; i < genvbound->ncoefs; ++i )
2254 	   {
2255 	      assert(genvbound->vars[i] != NULL);
2256 	      SCIP_CALL( SCIPcaptureVar(scip, genvbound->vars[i]) );
2257 	      if( SCIPvarIsRelaxationOnly(genvbound->vars[i]) )
2258 	         genvbound->relaxonly = TRUE;
2259 	   }
2260 	   if( newgenvbound )
2261 	   {
2262 	      assert(genvbound->var != NULL);
2263 	      SCIP_CALL( SCIPcaptureVar(scip, genvbound->var) );
2264 	   }
2265 	
2266 	   /* the cutoff bound is valid w.r.t. the current objective function in the transformed problem; during presolving,
2267 	    * however, the objective function can change (e.g., when a variable is fixed, its contribution in the objective
2268 	    * is subtracted from the cutoff bound and added to the objective offset); we solve this by transforming the
2269 	    * contribution of the cutoff bound in the generalized variable bound to the original problem as follows:
2270 	    *
2271 	    *    +/- var >= ... + z * SCIPgetCutoffbound() + constant
2272 	    *
2273 	    * becomes
2274 	    *
2275 	    *    +/- var >= ... + (z / SCIPgetTransObjscale()) * origcutoffbound + (constant - z * SCIPgetTransObjoffset())
2276 	    *
2277 	    * with SCIPgetCutoffbound() = origcutoffbound / SCIPgetTransObjscale() - SCIPgetTransObjoffset(); in the
2278 	    * propagation later, we will use (SCIPgetCutoffbound() + SCIPgetTransObjoffset()) * SCIPgetTransObjscale(), see
2279 	    * function getCutoffboundGenVBound()
2280 	    */
2281 	   if( SCIPisNegative(scip, coefcutoffbound) )
2282 	   {
2283 	      assert(SCIPisPositive(scip, SCIPgetTransObjscale(scip)));
2284 	      genvbound->cutoffcoef = coefcutoffbound / SCIPgetTransObjscale(scip);
2285 	      genvbound->constant -= (coefcutoffbound * SCIPgetTransObjoffset(scip));
2286 	   }
2287 	   else
2288 	      genvbound->cutoffcoef = 0.0;
2289 	
2290 	   /* if genvbound is not overwritten, create a new entry in genvboundstore */
2291 	   if( newgenvbound )
2292 	   {
2293 	      SCIP_CALL( addNewGenVBound(scip, propdata, genvbound) );
2294 	   }
2295 	
2296 	   /* mark genvbounds array to be resorted */
2297 	   propdata->issorted = FALSE;
2298 	
2299 	   /* debug message */
2300 	   SCIPdebugMsg(scip, "added genvbound ");
2301 	   SCIPdebug( printGenVBound(scip, genvbound) );
2302 	#ifdef WITH_DEBUG_SOLUTION
2303 	   SCIP_CALL( checkDebugSolutionGenVBound(scip, genvbound) );
2304 	#endif
2305 	
2306 	   return SCIP_OKAY;
2307 	}
2308 	
2309 	
2310 	/*
2311 	 * Callback methods of propagator
2312 	 */
2313 	
2314 	/** copy method for propagator plugins (called when SCIP copies plugins)
2315 	 *
2316 	 *  @note The UG framework assumes that all default plug-ins of SCIP implement a copy callback.
2317 	 */
2318 	static
2319 	SCIP_DECL_PROPCOPY(propCopyGenvbounds)
2320 	{  /*lint --e{715}*/
2321 	   assert(scip != NULL);
2322 	   assert(prop != NULL);
2323 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2324 	
2325 	   /* call inclusion method of constraint handler */
2326 	   SCIP_CALL( SCIPincludePropGenvbounds(scip) );
2327 	
2328 	   return SCIP_OKAY;
2329 	}
2330 	
2331 	/** initialization method of propagator (called after problem was transformed) */
2332 	static
2333 	SCIP_DECL_PROPINIT(propInitGenvbounds)
2334 	{  /*lint --e{715}*/
2335 	   SCIP_PROPDATA* propdata;
2336 	
2337 	   assert(scip != NULL);
2338 	   assert(prop != NULL);
2339 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2340 	
2341 	   /* get propagator data */
2342 	   propdata = SCIPpropGetData(prop);
2343 	   assert(propdata != NULL);
2344 	
2345 	   propdata->genvboundstore = NULL;
2346 	   propdata->genvboundstoresize = 0;
2347 	   propdata->lbevents = NULL;
2348 	   propdata->ubevents = NULL;
2349 	   propdata->lbgenvbounds = NULL;
2350 	   propdata->ubgenvbounds = NULL;
2351 	   propdata->lbeventsmap = NULL;
2352 	   propdata->ubeventsmap = NULL;
2353 	   propdata->startmap = NULL;
2354 	   propdata->componentsstart = NULL;
2355 	   propdata->startindices = NULL;
2356 	   propdata->startcomponents = NULL;
2357 	   propdata->gstartindices = NULL;
2358 	   propdata->gstartcomponents = NULL;
2359 	   propdata->lastcutoff = SCIPinfinity(scip);
2360 	   propdata->lastnodecaught = NULL;
2361 	   propdata->cutoffboundvar = NULL;
2362 	   propdata->ngenvbounds = -1;
2363 	   propdata->ncomponents = -1;
2364 	   propdata->nindices = -1;
2365 	   propdata->ngindices = -1;
2366 	   propdata->nlbevents = -1;
2367 	   propdata->nubevents = -1;
2368 	   propdata->issorted = FALSE;
2369 	
2370 	   propdata->prop = prop;
2371 	
2372 	   return SCIP_OKAY;
2373 	}
2374 	
2375 	
2376 	/** presolving method of propagator */
2377 	static
2378 	SCIP_DECL_PROPPRESOL(propPresolGenvbounds)
2379 	{  /*lint --e{715}*/
2380 	   SCIP_PROPDATA* propdata;
2381 	
2382 	   assert(scip != NULL);
2383 	   assert(prop != NULL);
2384 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2385 	
2386 	   *result = SCIP_DIDNOTRUN;
2387 	
2388 	   if( !SCIPallowStrongDualReds(scip) )
2389 	      return SCIP_OKAY;
2390 	
2391 	   /* get propagator data */
2392 	   propdata = SCIPpropGetData(prop);
2393 	   assert(propdata != NULL);
2394 	
2395 	   SCIPdebugMsg(scip, "proppresol in problem <%s>\n", SCIPgetProbName(scip));
2396 	
2397 	   /* do not run if no genvbounds were added yet */
2398 	   if( propdata->ngenvbounds < 1 )
2399 	   {
2400 	      SCIPdebugMsg(scip, "no bounds were added yet\n");
2401 	      return SCIP_OKAY;
2402 	   }
2403 	
2404 	   /* propagate */
2405 	   SCIP_CALL( execGenVBounds(scip, propdata, result, TRUE, nchgbds) );
2406 	
2407 	   return SCIP_OKAY;
2408 	}
2409 	
2410 	
2411 	/** presolving initialization method of propagator (called when presolving is about to begin) */
2412 	static
2413 	SCIP_DECL_PROPINITPRE(propInitpreGenvbounds)
2414 	{  /*lint --e{715}*/
2415 	   SCIP_PROPDATA* propdata;
2416 	
2417 	   assert(scip != NULL);
2418 	   assert(prop != NULL);
2419 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2420 	
2421 	   /* get propagator data */
2422 	   propdata = SCIPpropGetData(prop);
2423 	   assert(propdata != NULL);
2424 	
2425 	   /* lock the variable because it should not be deleted after a restart */
2426 	   if( propdata->cutoffboundvar != NULL )
2427 	   {
2428 	      SCIPdebugMsg(scip, "propinitpre in problem <%s>: locking cutoffboundvar (current downlocks=%d, uplocks=%d)\n",
2429 	         SCIPgetProbName(scip), SCIPvarGetNLocksDownType(propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL),
2430 	         SCIPvarGetNLocksUpType(propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL));
2431 	
2432 	      SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, 1, 1) );
2433 	   }
2434 	
2435 	   return SCIP_OKAY;
2436 	}
2437 	
2438 	
2439 	/** presolving deinitialization method of propagator (called after presolving has been finished) */
2440 	static
2441 	SCIP_DECL_PROPEXITPRE(propExitpreGenvbounds)
2442 	{  /*lint --e{715}*/
2443 	   SCIP_VAR** vars;
2444 	   SCIP_PROPDATA* propdata;
2445 	   int i;
2446 	
2447 	   assert(scip != NULL);
2448 	   assert(prop != NULL);
2449 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2450 	
2451 	   SCIPdebugMsg(scip, "propexitpre in problem <%s>: removing fixed, aggregated, negated, and multi-aggregated variables from right-hand side\n",
2452 	      SCIPgetProbName(scip));
2453 	
2454 	   /* get propagator data */
2455 	   propdata = SCIPpropGetData(prop);
2456 	   assert(propdata != NULL);
2457 	
2458 	   /* there should be no events on the right-hand side variables */
2459 	   assert(propdata->lbevents == NULL);
2460 	   assert(propdata->ubevents == NULL);
2461 	
2462 	   /* allocate memory to store new variables */
2463 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars, SCIPgetNTotalVars(scip)) );
2464 	
2465 	   for( i = 0; i < propdata->ngenvbounds; )
2466 	   {
2467 	      GENVBOUND* genvbound;
2468 	      int requiredsize;
2469 	      int nvars;
2470 	      int j;
2471 	
2472 	      genvbound = propdata->genvboundstore[i];
2473 	      assert(genvbound != NULL);
2474 	
2475 	      /* store variables of the genvbound to release them properly */
2476 	      assert(genvbound->ncoefs <= SCIPgetNTotalVars(scip));
2477 	      BMScopyMemoryArray(vars, genvbound->vars, genvbound->ncoefs);
2478 	      nvars = genvbound->ncoefs;
2479 	
2480 	      /* replace non-active by active variables and update constant; note that this may result in coefficients where
2481 	       * SCIPisZero() is true; this should not create any problems
2482 	       */
2483 	      SCIP_CALL( SCIPgetProbvarLinearSum(scip, genvbound->vars, genvbound->coefs, &genvbound->ncoefs, genvbound->ncoefs, &genvbound->constant, &requiredsize, TRUE) );
2484 	
2485 	      /* if space was not enough we need to resize the buffers */
2486 	      if( requiredsize > genvbound->ncoefs )
2487 	      {
2488 	         /* reallocate memory for arrays in genvbound to free unused memory */
2489 	         if( genvbound->coefssize < requiredsize )
2490 	         {
2491 	            SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize, requiredsize) );
2492 	            SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize, requiredsize) );
2493 	            genvbound->coefssize = requiredsize;
2494 	         }
2495 	
2496 	         SCIP_CALL( SCIPgetProbvarLinearSum(scip, genvbound->vars, genvbound->coefs, &genvbound->ncoefs, requiredsize, &genvbound->constant, &requiredsize, TRUE) );
2497 	         assert(requiredsize <= genvbound->ncoefs);
2498 	      }
2499 	
2500 	      /* capture new and release old variables */
2501 	      for( j = 0; j < genvbound->ncoefs; ++j )
2502 	      {
2503 	         assert(genvbound->vars[j] != NULL);
2504 	         SCIP_CALL( SCIPcaptureVar(scip, genvbound->vars[j]) );
2505 	      }
2506 	      for( j = 0; j < nvars; ++j )
2507 	      {
2508 	         assert(vars[j] != NULL);
2509 	         SCIP_CALL( SCIPreleaseVar(scip, &vars[j]) );
2510 	      }
2511 	
2512 	      /* if the resulting genvbound is trivial, remove it */
2513 	      /* we remove all genvbounds with an aggregated or multi-aggregated genvbound->var; tightening aggregated variables
2514 	       * might lead to some asserts in tree.c if the active variable has been already tightened (see !398);
2515 	       *
2516 	       * @todo replace aggregated variable by their active part
2517 	       */
2518 	      if( (genvbound->ncoefs == 0 && SCIPisZero(scip, genvbound->cutoffcoef))
2519 	         || SCIPvarGetStatus(genvbound->var) == SCIP_VARSTATUS_MULTAGGR
2520 	         || SCIPvarGetStatus(genvbound->var) == SCIP_VARSTATUS_AGGREGATED )
2521 	      {
2522 	         SCIP_HASHMAP* hashmap;
2523 	
2524 	         hashmap = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
2525 	
2526 	         /* remove genvbound from hashmap */
2527 	         assert(SCIPhashmapExists(hashmap, genvbound->var));
2528 	         SCIP_CALL( SCIPhashmapRemove(hashmap, genvbound->var) );
2529 	
2530 	         /* free genvbound and fill gap */
2531 	         SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
2532 	         --(propdata->ngenvbounds);
2533 	
2534 	         /* move the last genvbound to the i-th position */
2535 	         if( i < propdata->ngenvbounds )
2536 	         {
2537 	            propdata->genvboundstore[i] = propdata->genvboundstore[propdata->ngenvbounds];
2538 	            propdata->genvboundstore[i]->index = i;
2539 	
2540 	            /* mark genvbounds array to be resorted */
2541 	            propdata->issorted = FALSE;
2542 	         }
2543 	      }
2544 	      else
2545 	         ++i;
2546 	   }
2547 	
2548 	   SCIPfreeBufferArray(scip, &vars);
2549 	
2550 	   return SCIP_OKAY;
2551 	}
2552 	
2553 	/** deinitialization method of propagator (called before transformed problem is freed) */
2554 	static
2555 	SCIP_DECL_PROPEXIT(propExitGenvbounds)
2556 	{
2557 	   SCIP_PROPDATA* propdata;
2558 	
2559 	   assert(scip != NULL);
2560 	   assert(prop != NULL);
2561 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2562 	
2563 	   /* get propagator data */
2564 	   propdata = SCIPpropGetData(prop);
2565 	   assert(propdata != NULL);
2566 	
2567 	   /* free remaining genvbounds */
2568 	   SCIP_CALL( freeGenVBounds(scip, propdata) );
2569 	
2570 	   return SCIP_OKAY;
2571 	}
2572 	
2573 	/** execution method of propagator */
2574 	static
2575 	SCIP_DECL_PROPEXEC(propExecGenvbounds)
2576 	{  /*lint --e{715}*/
2577 	   SCIP_PROPDATA* propdata;
2578 	
2579 	   assert(scip != NULL);
2580 	   assert(prop != NULL);
2581 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2582 	
2583 	   *result = SCIP_DIDNOTRUN;
2584 	
2585 	   /* do not run if propagation w.r.t. current objective is not allowed */
2586 	   if( !SCIPallowWeakDualReds(scip) )
2587 	      return SCIP_OKAY;
2588 	
2589 	   /* get propagator data */
2590 	   propdata = SCIPpropGetData(prop);
2591 	   assert(propdata != NULL);
2592 	
2593 	   /* update upper bound of the cutoffboundvar */
2594 	   if( propdata->cutoffboundvar != NULL )
2595 	   {
2596 	      SCIP_Real newub;
2597 	      SCIP_Real oldub;
2598 	      SCIP_Bool infeasible;
2599 	      SCIP_Bool tightened;
2600 	
2601 	      assert(propdata->propasconss);
2602 	
2603 	      /* compute the primal bound in the original problem */
2604 	      newub = getCutoffboundGenVBound(scip);
2605 	      oldub = SCIPvarGetUbLocal(propdata->cutoffboundvar);
2606 	
2607 	      if( SCIPisInfinity(scip, newub) == FALSE && SCIPisFeasLT(scip, newub, oldub) )
2608 	      {
2609 	         SCIP_CALL( SCIPtightenVarUbGlobal(scip, propdata->cutoffboundvar, newub, FALSE, &infeasible, &tightened) );
2610 	
2611 	         if( tightened )
2612 	         {
2613 	            SCIPdebugMsg(scip, "tightened UB of cutoffboundvar to %e (old: %e, infeas: %u, tightened: %u)\n",
2614 	               newub, oldub, infeasible, tightened);
2615 	         }
2616 	
2617 	         assert(infeasible == FALSE);
2618 	      }
2619 	   }
2620 	
2621 	   SCIPdebugMsg(scip, "propexec in problem <%s> at depth %d%s\n", SCIPgetProbName(scip), SCIPgetDepth(scip),
2622 	      SCIPinProbing(scip) ? " in probing" : "");
2623 	
2624 	   /* do not run if no genvbounds were added yet */
2625 	   if( propdata->ngenvbounds < 1 )
2626 	   {
2627 	      /**@todo is it really no performance issue to be called each time when there are no genvbounds, e.g., for MIPs? */
2628 	      SCIPdebugMsg(scip, "no bounds were added yet\n");
2629 	      return SCIP_OKAY;
2630 	   }
2631 	
2632 	   /* add the genvbounds in the genvboundstore as constraints to the problem; afterwards clear the genvboundstore */
2633 	   if( propdata->propasconss )
2634 	   {
2635 	      SCIP_CALL( createConstraints(scip, propdata) );
2636 	      return SCIP_OKAY;
2637 	   }
2638 	
2639 	   /* propagate locally and globally */
2640 	   SCIP_CALL( execGenVBounds(scip, propdata, result, !SCIPinProbing(scip), NULL) );
2641 	
2642 	   /* when called in presolving stage the result is set to SCIP_SUCCESS instead of SCIP_REDUCEDDOM, this is corrected
2643 	    * here
2644 	    */
2645 	   if( *result == SCIP_SUCCESS )
2646 	      *result = SCIP_REDUCEDDOM;
2647 	
2648 	   SCIPdebugMsg(scip, "end of exec\n");
2649 	
2650 	   return SCIP_OKAY;
2651 	}
2652 	
2653 	/** propagation conflict resolving method of propagator */
2654 	static
2655 	SCIP_DECL_PROPRESPROP(propRespropGenvbounds)
2656 	{  /*lint --e{715}*/
2657 	   SCIP_PROPDATA* propdata;
2658 	   GENVBOUND* genvbound;
2659 	   SCIP_Real boundval;
2660 	   SCIP_Bool success;
2661 	
2662 	   SCIPdebugMsg(scip, "explain %s bound change of variable <%s>\n",
2663 	      boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(infervar));
2664 	
2665 	   /* get propagator data */
2666 	   propdata = SCIPpropGetData(prop);
2667 	   assert(propdata != NULL);
2668 	   assert(propdata->genvboundstore != NULL);
2669 	
2670 	   /* as inferinfo we passed the index of the genvbound that was used for propagation; the genvbound might have been
2671 	    * replaced, but also the new genvbound at this position has the same variable on the left-hand side
2672 	    */
2673 	   assert(inferinfo >= 0);
2674 	   assert(inferinfo < propdata->ngenvbounds);
2675 	
2676 	   *result = SCIP_DIDNOTFIND;
2677 	
2678 	   /* check also in optimized mode that inferinfo is correct */
2679 	   if( inferinfo >= propdata->ngenvbounds)
2680 	   {
2681 	      SCIPerrorMessage("generalized variable bounds propagator received inferinfo out of range; propagation not resolved, safe to continue\n");
2682 	      return SCIP_OKAY;
2683 	   }
2684 	
2685 	   /* get genvbound responsible for the bound change */
2686 	   genvbound = propdata->genvboundstore[inferinfo];
2687 	   assert(genvbound != NULL);
2688 	   assert(genvbound->var == infervar);
2689 	
2690 	   /* check also in optimized mode that inferinfo is correct */
2691 	   if( genvbound->var != infervar )
2692 	   {
2693 	      SCIPerrorMessage("generalized variable bounds propagator received incorrect inferinfo; propagation not resolved, but it's safe to continue\n");
2694 	      return SCIP_OKAY;
2695 	   }
2696 	
2697 	   /* get value of bound change on left-hand side */
2698 	   boundval = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER
2699 	      ? SCIPgetVarLbAtIndex(scip, genvbound->var, bdchgidx, TRUE)
2700 	      : -SCIPgetVarUbAtIndex(scip, genvbound->var, bdchgidx, TRUE);
2701 	
2702 	   /* if left-hand side variable is integral, it suffices to explain a bound change greater than boundval - 1 */
2703 	   if( SCIPvarIsIntegral(genvbound->var) )
2704 	   {
2705 	      SCIP_Real roundedboundval;
2706 	
2707 	      assert(SCIPisIntegral(scip, boundval));
2708 	
2709 	      roundedboundval = SCIPfeasCeil(scip, boundval - 1.0) + 2 * SCIPfeastol(scip);
2710 	      boundval = MIN(boundval, roundedboundval);
2711 	   }
2712 	
2713 	   /* resolve propagation */
2714 	   SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, bdchgidx, &boundval, &success) );
2715 	
2716 	   if( success )
2717 	      *result = SCIP_SUCCESS;
2718 	
2719 	   return SCIP_OKAY;
2720 	}
2721 	
2722 	/** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2723 	static
2724 	SCIP_DECL_PROPEXITSOL(propExitsolGenvbounds)
2725 	{  /*lint --e{715}*/
2726 	   SCIP_PROPDATA* propdata;
2727 	
2728 	   assert(scip != NULL);
2729 	   assert(prop != NULL);
2730 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2731 	
2732 	   SCIPdebugMsg(scip, "propexitsol in problem <%s>\n", SCIPgetProbName(scip));
2733 	
2734 	   /* get propagator data */
2735 	   propdata = SCIPpropGetData(prop);
2736 	   assert(propdata != NULL);
2737 	
2738 	   if( !SCIPisInRestart(scip) )
2739 	   {
2740 	      /* free all genvbounds if we are not in a restart */
2741 	      SCIP_CALL( freeGenVBounds(scip, propdata) );
2742 	   }
2743 	   else
2744 	   {
2745 	      /* free all genvbounds that use relax-only variables if we are in a restart */
2746 	      SCIP_CALL( freeGenVBoundsRelaxOnly(scip, propdata) );
2747 	   }
2748 	
2749 	   /* drop and free all events */
2750 	   SCIP_CALL( dropAndFreeEvents(scip, propdata) );
2751 	
2752 	   return SCIP_OKAY;
2753 	}
2754 	
2755 	/** destructor of propagator to free user data (called when SCIP is exiting) */
2756 	static
2757 	SCIP_DECL_PROPFREE(propFreeGenvbounds)
2758 	{  /*lint --e{715}*/
2759 	   SCIP_PROPDATA* propdata;
2760 	
2761 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2762 	
2763 	   /* free propagator data */
2764 	   propdata = SCIPpropGetData(prop);
2765 	   assert(propdata != NULL);
2766 	
2767 	   SCIPfreeBlockMemory(scip, &propdata);
2768 	
2769 	   SCIPpropSetData(prop, NULL);
2770 	
2771 	   return SCIP_OKAY;
2772 	}
2773 	
2774 	
2775 	/*
2776 	 * Callback methods of event handler
2777 	 */
2778 	
2779 	static
2780 	SCIP_DECL_EVENTEXEC(eventExecGenvbounds)
2781 	{  /*lint --e{715}*/
2782 	   SCIP_PROPDATA* propdata;
2783 	   int i;
2784 	
2785 	   assert(scip != NULL);
2786 	   assert(eventdata != NULL);
2787 	
2788 	   assert(SCIPeventGetType(event) == SCIP_EVENTTYPE_LBTIGHTENED || SCIPeventGetType(event) ==
2789 	      SCIP_EVENTTYPE_UBTIGHTENED);
2790 	
2791 	   assert(eventdata->startcomponents != NULL);
2792 	   assert(eventdata->startindices != NULL);
2793 	   assert(eventdata->nstarts > 0);
2794 	   assert(eventdata->prop != NULL);
2795 	
2796 	   propdata = SCIPpropGetData(eventdata->prop);
2797 	   assert(propdata != NULL);
2798 	
2799 	   assert(propdata->startcomponents != NULL);
2800 	   assert(propdata->startmap != NULL);
2801 	   assert(propdata->startindices != NULL);
2802 	
2803 	   SCIPdebugMsg(scip, "catching eventdata:\n");
2804 	   SCIPdebug( printEventData(eventdata, SCIPeventGetType(event) == SCIP_EVENTTYPE_LBTIGHTENED ?
2805 	         SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) );
2806 	
2807 	   /* check if we need to reset old local starting indices data */
2808 	   if( SCIPgetCurrentNode(scip) != propdata->lastnodecaught )
2809 	   {
2810 	      SCIP_CALL( resetLocalStartingData(scip, propdata) );
2811 	      propdata->lastnodecaught = SCIPgetCurrentNode(scip);
2812 	   }
2813 	
2814 	   for( i = 0; i < eventdata->nstarts; i++ )
2815 	   {
2816 	      int component;
2817 	      int startidx;
2818 	
2819 	      component = eventdata->startcomponents[i];
2820 	      assert(component >= 0);
2821 	      startidx = eventdata->startindices[i];
2822 	
2823 	      /* there is already an entry for this component */
2824 	      if( SCIPhashmapExists(propdata->startmap, (void*)(size_t) (component + 1)) )
2825 	      {
2826 	         int componentidx;
2827 	
2828 	         /* get its index */
2829 	         componentidx = (SCIPhashmapGetImageInt(propdata->startmap, (void*)(size_t) (component + 1))) - 1; /*lint !e571 !e776*/
2830 	         assert(componentidx >= 0);
2831 	         assert(propdata->startcomponents[componentidx] == component);
2832 	
2833 	         if( propdata->startindices[componentidx] > startidx )
2834 	            propdata->startindices[componentidx] = startidx;
2835 	      }
2836 	      else
2837 	      {
2838 	         /* get a new entry */
2839 	         int componentidx;
2840 	         componentidx = propdata->nindices;
2841 	
2842 	         /* store index */
2843 	         propdata->startcomponents[componentidx] = component;
2844 	         propdata->startindices[componentidx] = startidx;
2845 	
2846 	         /* store component in hashmap */
2847 	         SCIP_CALL( SCIPhashmapInsertInt(propdata->startmap, (void*)(size_t) (component + 1), componentidx + 1) ); /*lint !e571 !e776*/
2848 	
2849 	         /* increase number of starting indices */
2850 	         propdata->nindices++;
2851 	      }
2852 	   }
2853 	
2854 	   return SCIP_OKAY;
2855 	}
2856 	
2857 	/*
2858 	 * propagator specific interface methods
2859 	 */
2860 	
2861 	/** creates the genvbounds propagator and includes it in SCIP */
2862 	SCIP_RETCODE SCIPincludePropGenvbounds(
2863 	   SCIP*                 scip                /**< SCIP data structure */
2864 	   )
2865 	{
2866 	   SCIP_PROPDATA* propdata;
2867 	   SCIP_PROP* prop;
2868 	
2869 	   /* create genvbounds propagator data */
2870 	   SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
2871 	
2872 	   /* include propagator */
2873 	   SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
2874 	         propExecGenvbounds, propdata) );
2875 	
2876 	   SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyGenvbounds) );
2877 	   SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeGenvbounds) );
2878 	   SCIP_CALL( SCIPsetPropInit(scip, prop, propInitGenvbounds) );
2879 	   SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreGenvbounds) );
2880 	   SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreGenvbounds) );
2881 	   SCIP_CALL( SCIPsetPropExit(scip, prop, propExitGenvbounds) );
2882 	   SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolGenvbounds) );
2883 	   SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolGenvbounds, PROP_PRESOL_PRIORITY,
2884 	         PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
2885 	   SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropGenvbounds) );
2886 	
2887 	   SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/global",
2888 	         "apply global propagation?",
2889 	         &propdata->global, TRUE, DEFAULT_GLOBAL_PROPAGATION, NULL, NULL) );
2890 	
2891 	   SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/propinrootnode",
2892 	         "apply genvbounds in root node if no new incumbent was found?",
2893 	         &propdata->propinrootnode, TRUE, DEFAULT_PROPAGATE_IN_ROOT_NODE, NULL, NULL) );
2894 	
2895 	   SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/sort",
2896 	         "sort genvbounds and wait for bound change events?",
2897 	         &propdata->sort, TRUE, DEFAULT_SORT, NULL, NULL) );
2898 	
2899 	   SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/propasconss",
2900 	         "should genvbounds be transformed to (linear) constraints?",
2901 	         &propdata->propasconss, TRUE, DEFAULT_PROPASCONSS, NULL, NULL) );
2902 	
2903 	   /* include event handler */
2904 	   SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecGenvbounds, NULL) );
2905 	
2906 	   return SCIP_OKAY;
2907 	}
2908