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_pseudoobj.c
26   	 * @ingroup DEFPLUGINS_PROP
27   	 * @brief  Pseudo objective propagator
28   	 * @author Tobias Achterberg
29   	 * @author Stefan Heinz
30   	 *
31   	 * This propagator propagates the objective function using the cutoff bound and the pseudo objective value. The pseudo
32   	 * objective value can be seen as minimum activity of the linear objective function. Using this, this propagator checks
33   	 * if variables with non-zero objective coefficients can exceed the cutoff bound. If this is the case the corresponding
34   	 * bound can be tightened.
35   	 *
36   	 * @todo use the complete implication to initialize the objective implication data structure
37   	 */
38   	
39   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40   	
41   	#include "blockmemshell/memory.h"
42   	#include "scip/prop_pseudoobj.h"
43   	#include "scip/pub_event.h"
44   	#include "scip/pub_implics.h"
45   	#include "scip/pub_message.h"
46   	#include "scip/pub_misc.h"
47   	#include "scip/pub_misc_sort.h"
48   	#include "scip/pub_prop.h"
49   	#include "scip/pub_var.h"
50   	#include "scip/scip_conflict.h"
51   	#include "scip/scip_event.h"
52   	#include "scip/scip_general.h"
53   	#include "scip/scip_lp.h"
54   	#include "scip/scip_mem.h"
55   	#include "scip/scip_message.h"
56   	#include "scip/scip_numerics.h"
57   	#include "scip/scip_param.h"
58   	#include "scip/scip_pricer.h"
59   	#include "scip/scip_prob.h"
60   	#include "scip/scip_probing.h"
61   	#include "scip/scip_prop.h"
62   	#include "scip/scip_solvingstats.h"
63   	#include "scip/scip_tree.h"
64   	#include "scip/scip_var.h"
65   	#include "scip/dbldblarith.h"
66   	#include <string.h>
67   	
68   	#define PROP_NAME              "pseudoobj"
69   	#define PROP_DESC              "pseudo objective function propagator"
70   	#define PROP_TIMING             SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
71   	#define PROP_PRIORITY           3000000 /**< propagator priority */
72   	#define PROP_FREQ                     1 /**< propagator frequency */
73   	#define PROP_DELAY                FALSE /**< should propagation method be delayed, if other propagators found reductions? */
74   	#define PROP_PRESOL_PRIORITY   +6000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
75   	#define PROP_PRESOL_MAXROUNDS        -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
76   	                                         *   limit) */
77   	#define PROP_PRESOLTIMING           SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
78   	
79   	#define EVENTHDLR_NAME         "pseudoobj"
80   	#define EVENTHDLR_DESC         "bound change event handler for pseudo objective function propagator"
81   	
82   	#define DEFAULT_MINUSELESS          100 /**< minimal number of successive non-binary variable propagator whithout a
83   	                                         *   bound reduction before aborted */
84   	#define DEFAULT_MAXVARSFRAC         0.1 /**< maximal fraction of non-binary variables with non-zero objective
85   	                                         *   without a bound reduction before aborted */
86   	#define DEFAULT_PROPFULLINROOT     TRUE /**< do we want to propagate all non-binary variables if we are propagating the root node? */
87   	#define DEFAULT_PROPCUTOFFBOUND    TRUE /**< propagate new cutoff bound directly globally */
88   	#define DEFAULT_FORCE             FALSE /**< should the propagator be forced even if active pricer are present? Note that
89   	                                         *   can be done if it is known that the pseudo objective activity is given by
90   	                                         *   the zero bound for all variables which are currently not present in the
91   	                                         *   problem */
92   	#define DEFAULT_MAXNEWVARS         1000 /**< number of variable added after the propagator is reinitialized? */
93   	#define DEFAULT_PROPUSEIMPLICS     TRUE /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */
94   	#define DEFAULT_RESPROPUSEIMPLICS  TRUE /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */
95   	#define DEFAULT_MAXIMPLVARS       50000 /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */
96   	
97   	
98   	/*
99   	 * Data structures
100  	 */
101  	
102  	/** implication data structure for objective contributions of a binary variable */
103  	struct SCIP_ObjImplics
104  	{
105  	   SCIP_VAR**            objvars;            /**< variables y in implications y == 0 or y == 1, first we store the
106  	                                              *   implications by x == 0 and second the implications x == 1 */
107  	   SCIP_Real             maxobjchg;          /**< maximum objective contribution if variables x is fixed to zero or one */
108  	   int                   nlbimpls;           /**< number of all implications result through for x == 0 */
109  	   int                   nubimpls;           /**< number of all implications result through for x == 1 */
110  	   int                   size;               /**< size of the objvars array */
111  	};
112  	typedef struct SCIP_ObjImplics SCIP_OBJIMPLICS; /**< implications in the form x == 0 or x == 1 ==> y == 0 or y == 1 for (x and y binary) */
113  	
114  	
115  	/** propagator data */
116  	struct SCIP_PropData
117  	{
118  	   SCIP_EVENTHDLR*       eventhdlr;          /**< event handler for global bound change events */
119  	   SCIP_VAR**            minactvars;         /**< binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */
120  	   SCIP_OBJIMPLICS**     minactimpls;        /**< implication data structure for the binary variables w.r.t. minimum activity */
121  	   SCIP_VAR**            maxactvars;         /**< binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */
122  	   SCIP_Real*            maxactchgs;         /**< the maximal potential change of the objective if the binary variable
123  	                                              *   is fixed to its best bound w.r.t. maximum activity of the objective function */
124  	
125  	   SCIP_VAR**            objintvars;         /**< non-binary variable with non-zero objective coefficient */
126  	   SCIP_HASHTABLE*       addedvars;          /**< hash table used during resolving of a bound change (conflict analysis) */
127  	   SCIP_Real             lastlowerbound;     /**< last lower bound which was propagated */
128  	   SCIP_Real             cutoffbound;        /**< last cutoff bound used for propagation */
129  	   SCIP_Real             glbpseudoobjval;    /**< last global pseudo objective used in presolving */
130  	   SCIP_Real             maxvarsfrac;        /**< maximal fraction of non-binary variables with non-zero objective
131  	                                              *   without a bound reduction before aborted
132  	                                              */
133  	   SCIP_Real             maxpseudoobjact;    /**< maximal global pseudo objective activity */
134  	   int                   maxpseudoobjactinf; /**< number of coefficients contributing with infinite value to maxpseudoobjact */
135  	   int                   nminactvars;        /**< number of binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */
136  	   int                   nmaxactvars;        /**< number of binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */
137  	   int                   nobjintvars;        /**< number of non-binary variables with non-zero objective */
138  	   int                   minuseless;         /**< minimal number of successive non-binary variable propagator whithout
139  	                                              *   a bound reduction before aborted
140  	                                              */
141  	   int                   lastvarnum;         /**< last non-binary variable number that was looked at */
142  	   int                   glbfirstnonfixed;   /**< index of first globally non-fixed binary variable in minactvars array */
143  	   int                   maxactfirstnonfixed;/**< index of first globally non-fixed binary variable in maxctvars array */
144  	   int                   firstnonfixed;      /**< index of first locally non-fixed binary variable in minactvars array */
145  	   int                   nnewvars;           /**< counter for counting number of new variables added */
146  	   int                   maxnewvars;         /**< number of variable added after the propagator is reinitialized? */
147  	   int                   maximplvars;        /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */
148  	   int                   minactsize;         /**< size of minactvars and minactimpls array */
149  	   int                   maxactsize;         /**< size of maxactvars and maxactchgs array */
150  	   int                   objintvarssize;     /**< size of objintvars array*/
151  	   SCIP_Bool             glbpropagated;      /**< are global domains propagated */
152  	   SCIP_Bool             propfullinroot;     /**< do we want to propagate all non-binary variables if we are propagating the root node */
153  	   SCIP_Bool             propcutoffbound;    /**< propagate new cutoff bound directly globally */
154  	   SCIP_Bool             force;              /**< should the propagator be forced even if active pricer are present? */
155  	   SCIP_Bool             catchvaradded;      /**< do we catch the variable added event? */
156  	   SCIP_Bool             propuseimplics;     /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */
157  	   SCIP_Bool             respropuseimplics;  /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */
158  	   SCIP_Bool             initialized;        /**< is propagator data structure initialized */
159  	};
160  	
161  	/*
162  	 * Debug methods
163  	 */
164  	
165  	#ifndef NDEBUG
166  	/** check that the implications are applied for a globally fixed variable */
167  	static
168  	void checkImplicsApplied(
169  	   SCIP*                 scip,               /**< SCIP data structure */
170  	   SCIP_VAR*             var                 /**< variable to check the implications */
171  	   )
172  	{
173  	   SCIP_VAR** vars;
174  	   SCIP_Real* bounds;
175  	   SCIP_BOUNDTYPE* boundtypes;
176  	   SCIP_Bool varfixing;
177  	   int nvars;
178  	   int v;
179  	
180  	   /* check that the given variable is locally or globally fixed */
181  	   assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
182  	
183  	   /* get fixed value */
184  	   varfixing = SCIPvarGetLbGlobal(var) > 0.5;
185  	
186  	   vars = SCIPvarGetImplVars(var, varfixing);
187  	   nvars = SCIPvarGetNImpls(var, varfixing);
188  	   bounds = SCIPvarGetImplBounds(var, varfixing);
189  	   boundtypes = SCIPvarGetImplTypes(var, varfixing);
190  	
191  	   /* check that each implication was applied */
192  	   for( v = 0; v < nvars; ++v )
193  	   {
194  	      if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
195  	      {
196  	         SCIP_Real lb;
197  	
198  	         lb = SCIPvarGetLbGlobal(vars[v]);
199  	         assert(SCIPisLE(scip, lb, bounds[v]));
200  	      }
201  	      else
202  	      {
203  	         SCIP_Real ub;
204  	
205  	         assert(boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
206  	
207  	         ub = SCIPvarGetLbGlobal(vars[v]);
208  	         assert(SCIPisGE(scip, ub, bounds[v]));
209  	      }
210  	   }
211  	}
212  	
213  	/** check if the global fixed indices are correct */
214  	static
215  	void checkGlbfirstnonfixed(
216  	   SCIP_PROPDATA*        propdata            /**< propagator data */
217  	   )
218  	{
219  	   SCIP_VAR* var;
220  	   int v;
221  	
222  	   for( v = 0; v < propdata->glbfirstnonfixed; ++v )
223  	   {
224  	      var = propdata->minactvars[v];
225  	      assert(var != NULL);
226  	
227  	      assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5);
228  	   }
229  	
230  	   for( v = 0; v < propdata->maxactfirstnonfixed; ++v )
231  	   {
232  	      var = propdata->maxactvars[v];
233  	      assert(var != NULL);
234  	
235  	      assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5);
236  	   }
237  	}
238  	#endif /* end of debug methods */
239  	
240  	/*
241  	 * Comparer
242  	 */
243  	
244  	/** compares objective implications w.r.t. their maximum contribution */
245  	static
246  	SCIP_DECL_SORTPTRCOMP(objimplicsComp)
247  	{
248  	   SCIP_OBJIMPLICS* objimplics1;
249  	   SCIP_OBJIMPLICS* objimplics2;
250  	
251  	   objimplics1 = (SCIP_OBJIMPLICS*)elem1;
252  	   objimplics2 = (SCIP_OBJIMPLICS*)elem2;
253  	
254  	   if( objimplics1->maxobjchg > objimplics2->maxobjchg )
255  	      return +1;
256  	
257  	   if( objimplics1->maxobjchg < objimplics2->maxobjchg )
258  	      return -1;
259  	
260  	   return 0;
261  	}
262  	
263  	/** compare variables w.r.t.
264  	 *  (i)   the absolute value the objective coefficient;
265  	 *  (ii)  the locks which indicate most effect -- for the variables with a positive (negative) objective coefficient the
266  	 *        down (up) lock is used since this lock indicates that tightened of the upper (lower) bound will triegger
267  	 *        further domain propagations;
268  	 *  (iii) the other locks;
269  	 *  (iv)  variable problem index;
270  	 */
271  	static
272  	SCIP_DECL_SORTPTRCOMP(varCompObj)
273  	{
274  	   SCIP_VAR* var1;
275  	   SCIP_VAR* var2;
276  	   int locks1;
277  	   int locks2;
278  	
279  	   var1 = (SCIP_VAR*)elem1;
280  	   var2 = (SCIP_VAR*)elem2;
281  	
282  	   assert(SCIPvarGetObj(var1) != 0.0);
283  	   assert(SCIPvarGetObj(var2) != 0.0);
284  	
285  	   /* first criteria is the absolute value of objective coefficient */
286  	   if( REALABS(SCIPvarGetObj(var1)) < REALABS(SCIPvarGetObj(var2)) )
287  	      return -1;
288  	   else if( REALABS(SCIPvarGetObj(var1)) > REALABS(SCIPvarGetObj(var2)) )
289  	      return +1;
290  	
291  	   /* second criteria the locks which indicate most effect */
292  	   if( SCIPvarGetObj(var1) > 0.0 )
293  	      locks1 = SCIPvarGetNLocksDownType(var1, SCIP_LOCKTYPE_MODEL);
294  	   else
295  	      locks1 = SCIPvarGetNLocksUpType(var1, SCIP_LOCKTYPE_MODEL);
296  	
297  	   if( SCIPvarGetObj(var2) > 0.0 )
298  	      locks2 = SCIPvarGetNLocksDownType(var2, SCIP_LOCKTYPE_MODEL);
299  	   else
300  	      locks2 = SCIPvarGetNLocksUpType(var2, SCIP_LOCKTYPE_MODEL);
301  	
302  	   if( locks1 < locks2 )
303  	      return -1;
304  	   if( locks1 > locks2 )
305  	      return 1;
306  	
307  	   /* third criteria the other locks */
308  	   if( SCIPvarGetObj(var1) > 0.0 )
309  	      locks1 = SCIPvarGetNLocksUpType(var1, SCIP_LOCKTYPE_MODEL);
310  	   else
311  	      locks1 = SCIPvarGetNLocksDownType(var1, SCIP_LOCKTYPE_MODEL);
312  	
313  	   if( SCIPvarGetObj(var2) >  0.0 )
314  	      locks2 = SCIPvarGetNLocksUpType(var2, SCIP_LOCKTYPE_MODEL);
315  	   else
316  	      locks2 = SCIPvarGetNLocksDownType(var2, SCIP_LOCKTYPE_MODEL);
317  	
318  	   if( locks1 < locks2 )
319  	      return -1;
320  	   if( locks1 > locks2 )
321  	      return 1;
322  	
323  	   /* forth criteria use the problem index */
324  	   return SCIPvarCompare(var1, var2);
325  	}
326  	
327  	/** hash key retrieval function for cliques*/
328  	static
329  	SCIP_DECL_HASHGETKEY(cliqueGetHashkey)
330  	{  /*lint --e{715}*/
331  	   return elem;
332  	}
333  	
334  	/** returns TRUE iff the cliques are equal */
335  	static
336  	SCIP_DECL_HASHKEYEQ(cliqueIsHashkeyEq)
337  	{  /*lint --e{715}*/
338  	   if( key1 == key2 )
339  	      return TRUE;
340  	   return FALSE;
341  	}
342  	
343  	/** returns the hash value of the key */
344  	static
345  	SCIP_DECL_HASHKEYVAL(cliqueGetHashkeyVal)
346  	{  /*lint --e{715}*/
347  	   return SCIPcliqueGetId((SCIP_CLIQUE*) key);
348  	}
349  	
350  	/*
351  	 * methods for SCIP_OBJIMPLICS data structure
352  	 */
353  	
354  	/** creates an objective implication data structure, fixes (globally) variables which are implied by lower and upper
355  	 *  bound fixing, and clears the collected arrays for lower and upper bound
356  	 */
357  	static
358  	SCIP_RETCODE objimplicsCreate(
359  	   SCIP*                 scip,               /**< SCIP data structure */
360  	   SCIP_OBJIMPLICS**     objimplics,         /**< pointer to objective implication data structure */
361  	   SCIP_VAR**            objvars,            /**< objective contributor variables, or NULL */
362  	   SCIP_HASHMAP*         binobjvarmap,       /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays, or NULL */
363  	   SCIP_Bool*            collectedlbvars,    /**< temporary buffer to mark collected variables for lower bound fixing, or NULL */
364  	   SCIP_Bool*            collectedubvars,    /**< temporary buffer to mark collected variables for upper bound fixing, or NULL */
365  	   SCIP_Real             maxlbobjchg,        /**< maximum objective contributor if variables id fixed to zero */
366  	   SCIP_Real             maxubobjchg,        /**< maximum objective contributor if variables id fixed to one */
367  	   int                   nlbimpls,           /**< number of variables contributing to to lower bound fix */
368  	   int                   nubimpls            /**< number of variables contributing to to upper bound fix */
369  	   )
370  	
371  	{
372  	   assert(scip != NULL);
373  	   assert(objimplics != NULL);
374  	   assert(!SCIPisNegative(scip, maxlbobjchg));
375  	   assert(!SCIPisNegative(scip, maxubobjchg));
376  	
377  	   /* allocate block memory for the implication data structure */
378  	   SCIP_CALL( SCIPallocBlockMemory(scip, objimplics) );
379  	
380  	   if( nlbimpls + nubimpls == 0 )
381  	   {
382  	      assert(nlbimpls == 0);
383  	      assert(nubimpls == 0);
384  	      (*objimplics)->objvars = NULL;
385  	      (*objimplics)->maxobjchg = 0.0;
386  	      (*objimplics)->nlbimpls = 0;
387  	      (*objimplics)->nubimpls = 0;
388  	      (*objimplics)->size = 0;
389  	   }
390  	   else
391  	   {
392  	      SCIP_VAR* var;
393  	      int nvars;
394  	      int pos;
395  	      int v;
396  	
397  	      assert(objvars != NULL);
398  	      assert(binobjvarmap != NULL);
399  	      assert(collectedlbvars != NULL);
400  	      assert(collectedubvars != NULL);
401  	
402  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*objimplics)->objvars, nlbimpls + nubimpls) );
403  	      (*objimplics)->size = nlbimpls + nubimpls;
404  	
405  	      nvars = 0;
406  	
407  	      for( v = 0; v < nlbimpls; ++v )
408  	      {
409  	         var = objvars[v];
410  	         assert(var != NULL);
411  	         assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
412  	
413  	         assert(SCIPhashmapExists(binobjvarmap, var));
414  	         pos = SCIPhashmapGetImageInt(binobjvarmap, (void*)var);
415  	         assert(pos > 0);
416  	         assert(collectedlbvars[pos]);
417  	
418  	         if( collectedubvars[pos] )
419  	         {
420  	            SCIP_Bool infeasible;
421  	            SCIP_Bool tightened;
422  	
423  	            if( SCIPvarGetBestBoundType(var) == SCIP_BOUNDTYPE_LOWER )
424  	            {
425  	               SCIPdebugMsg(scip, "fix variables <%s> to 1.0 due to implications\n", SCIPvarGetName(var));
426  	
427  	               SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 1.0, FALSE, &infeasible, &tightened) );
428  	               maxlbobjchg -= SCIPvarGetObj(var);
429  	            }
430  	            else
431  	            {
432  	               SCIPdebugMsg(scip, "fix variables <%s> to 0.0 due to implications\n", SCIPvarGetName(var));
433  	
434  	               SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, 0.0, FALSE, &infeasible, &tightened) );
435  	               maxlbobjchg += SCIPvarGetObj(var);
436  	            }
437  	            assert(!infeasible);
438  	            assert(tightened);
439  	         }
440  	         else
441  	         {
442  	            (*objimplics)->objvars[nvars] = var;
443  	            nvars++;
444  	         }
445  	         collectedlbvars[pos] = FALSE;
446  	      }
447  	      (*objimplics)->nlbimpls = nvars;
448  	
449  	      for( v = 0; v < nubimpls; ++v )
450  	      {
451  	         var = objvars[nlbimpls + v];
452  	         assert(var != NULL);
453  	         assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
454  	
455  	         assert(SCIPhashmapExists(binobjvarmap, var));
456  	         pos = SCIPhashmapGetImageInt(binobjvarmap, (void*)var);
457  	         assert(pos > 0);
458  	         assert(collectedubvars[pos]);
459  	
460  	         if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
461  	         {
462  	            if( SCIPvarGetBestBoundType(var) == SCIP_BOUNDTYPE_LOWER )
463  	               maxubobjchg -= SCIPvarGetObj(var);
464  	            else
465  	               maxubobjchg += SCIPvarGetObj(var);
466  	         }
467  	         else
468  	         {
469  	            (*objimplics)->objvars[nvars] = var;
470  	            nvars++;
471  	         }
472  	         collectedubvars[pos] = FALSE;
473  	      }
474  	      (*objimplics)->nubimpls = nvars - (*objimplics)->nlbimpls;
475  	
476  	      /* capture the variables */
477  	      for( v = 0; v < nvars; ++v )
478  	      {
479  	         assert(SCIPvarIsBinary((*objimplics)->objvars[v]));
480  	         assert(!SCIPisZero(scip, SCIPvarGetObj((*objimplics)->objvars[v])));
481  	         SCIP_CALL( SCIPcaptureVar(scip, (*objimplics)->objvars[v]) );
482  	      }
483  	   }
484  	
485  	   (*objimplics)->maxobjchg = MAX(maxlbobjchg, maxubobjchg);
486  	
487  	   return SCIP_OKAY;
488  	}
489  	
490  	/** frees an objective implication data structure */
491  	static
492  	SCIP_RETCODE objimplicsFree(
493  	   SCIP*                 scip,               /**< SCIP data structure */
494  	   SCIP_OBJIMPLICS**     objimplics          /**< pointer to objective implication data structure */
495  	   )
496  	{
497  	   int v;
498  	
499  	   assert(scip != NULL);
500  	   assert(objimplics != NULL);
501  	   assert(*objimplics != NULL);
502  	
503  	   /* release all variables */
504  	   for( v = 0; v < (*objimplics)->nlbimpls + (*objimplics)->nubimpls; ++v )
505  	   {
506  	      SCIP_CALL( SCIPreleaseVar(scip, &(*objimplics)->objvars[v]) );
507  	   }
508  	
509  	   /* free objective variable array */
510  	   SCIPfreeBlockMemoryArrayNull(scip, &(*objimplics)->objvars, (*objimplics)->size);
511  	
512  	   /* frees block memory for the implication data structure */
513  	   SCIPfreeBlockMemory(scip, objimplics);
514  	
515  	   return SCIP_OKAY;
516  	}
517  	
518  	/** remove the given variable at the given pos from the objective implication data structure */
519  	static
520  	SCIP_RETCODE objimplicsDelPos(
521  	   SCIP*                 scip,               /**< SCIP data structure */
522  	   SCIP_OBJIMPLICS*      objimplics,         /**< objective implication data structure */
523  	   int                   pos                 /**< position */
524  	   )
525  	{
526  	   assert(0 <= pos);
527  	   assert(pos < objimplics->nlbimpls + objimplics->nubimpls);
528  	
529  	   SCIPdebugMsg(scip, "variable <%s> ", SCIPvarGetName(objimplics->objvars[pos]));
530  	
531  	   /* release variable */
532  	   SCIP_CALL( SCIPreleaseVar(scip, &objimplics->objvars[pos]) );
533  	
534  	   /* copy last lower bound variable to that position */
535  	   if( pos < objimplics->nlbimpls )
536  	   {
537  	      objimplics->nlbimpls--;
538  	      assert(objimplics->nlbimpls >= 0);
539  	
540  	      /* copy last lower bound variable to that position */
541  	      objimplics->objvars[pos] = objimplics->objvars[objimplics->nlbimpls];
542  	
543  	      /* copy last upper bound variable to open slot */
544  	      objimplics->objvars[objimplics->nlbimpls] = objimplics->objvars[objimplics->nlbimpls + objimplics->nubimpls];
545  	
546  	      SCIPdebugMsgPrint(scip, "remove lower bound implication\n");
547  	   }
548  	   else
549  	   {
550  	      objimplics->nubimpls--;
551  	      assert(objimplics->nubimpls >= 0);
552  	
553  	      /* copy last upper bound variable to that position */
554  	      objimplics->objvars[pos] = objimplics->objvars[objimplics->nlbimpls + objimplics->nubimpls];
555  	
556  	      SCIPdebugMsgPrint(scip, "remove upper bound implication\n");
557  	   }
558  	
559  	   return SCIP_OKAY;
560  	}
561  	
562  	/*
563  	 * Local methods
564  	 */
565  	
566  	
567  	/** catch bound change events if the variable has a non-zero objective coefficient to check if the maximum activity of
568  	 *  the objective function changed
569  	 */
570  	static
571  	SCIP_RETCODE catchObjEvent(
572  	   SCIP*                 scip,               /**< SCIP data structure */
573  	   SCIP_PROPDATA*        propdata,           /**< propagator data */
574  	   SCIP_EVENTHDLR*       eventhdlr,          /**< event handler for global bound change events */
575  	   SCIP_VAR*             var                 /**< variable for which the event should be dropped */
576  	   )
577  	{
578  	   SCIP_Real objval;
579  	
580  	   assert(propdata != NULL);
581  	   assert(eventhdlr != NULL);
582  	
583  	   objval = SCIPvarGetObj(var);
584  	
585  	   if( !SCIPisZero(scip, objval) )
586  	   {
587  	      if( objval > 0.0 )
588  	      {
589  	         SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GUBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
590  	      }
591  	      else
592  	      {
593  	         SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GLBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
594  	      }
595  	   }
596  	
597  	   return SCIP_OKAY;
598  	}
599  	
600  	/** drop variable event w.r.t. objective coefficient */
601  	static
602  	SCIP_RETCODE dropObjEvent(
603  	   SCIP*                 scip,               /**< SCIP data structure */
604  	   SCIP_PROPDATA*        propdata,           /**< propagator data */
605  	   SCIP_EVENTHDLR*       eventhdlr,          /**< event handler for global bound change events */
606  	   SCIP_VAR*             var                 /**< variable for which the event should be dropped */
607  	   )
608  	{
609  	   SCIP_Real objval;
610  	
611  	   assert(propdata != NULL);
612  	   assert(eventhdlr != NULL);
613  	
614  	   objval = SCIPvarGetObj(var);
615  	
616  	   /* drop bound change event */
617  	   if( !SCIPisZero(scip, objval) )
618  	   {
619  	      if( objval > 0.0 )
620  	      {
621  	         SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GUBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
622  	      }
623  	      else
624  	      {
625  	         SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GLBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
626  	      }
627  	   }
628  	   return SCIP_OKAY;
629  	}
630  	
631  	/** drop all variable events */
632  	static
633  	SCIP_RETCODE dropVarEvents(
634  	   SCIP*                 scip,               /**< SCIP data structure */
635  	   SCIP_PROPDATA*        propdata            /**< propagator data */
636  	   )
637  	{
638  	   SCIP_EVENTHDLR* eventhdlr;
639  	   SCIP_VAR* var;
640  	   int k;
641  	
642  	   assert(scip != NULL);
643  	   assert(propdata != NULL);
644  	
645  	   eventhdlr = propdata->eventhdlr;
646  	   assert(eventhdlr != NULL);
647  	
648  	   /* drop all events and release variables */
649  	   for( k = 0; k < propdata->nminactvars; ++k )
650  	   {
651  	      var =  propdata->minactvars[k];
652  	      assert(var != NULL);
653  	      assert(SCIPvarIsBinary(var));
654  	
655  	      /* drop bound relax event which is caught for all binary variables which are used for propagation the objective
656  	       * function via the minimum activity of the objective function
657  	       */
658  	      SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDRELAXED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
659  	
660  	      /* release variable */
661  	      SCIP_CALL( SCIPreleaseVar(scip, &var) );
662  	   }
663  	
664  	   /* release variables */
665  	   for( k = 0; k < propdata->nmaxactvars; ++k )
666  	   {
667  	      var = propdata->maxactvars[k];
668  	      assert(var != NULL);
669  	      assert(SCIPvarIsBinary(var));
670  	
671  	      /* drop events which are needed for evaluating the maximum activity of the objective function */
672  	      SCIP_CALL( dropObjEvent(scip, propdata, eventhdlr, var) );
673  	
674  	      /* release variable */
675  	      SCIP_CALL( SCIPreleaseVar(scip, &var) );
676  	   }
677  	
678  	   /* drop all events and release variables */
679  	   for( k = 0; k < propdata->nobjintvars; ++k )
680  	   {
681  	      var = propdata->objintvars[k];
682  	      assert(var != NULL);
683  	
684  	      /* drop events which are needed for evaluating the maximum activity of the objective function */
685  	      SCIP_CALL( dropObjEvent(scip, propdata, eventhdlr, var) );
686  	
687  	      /* release variable */
688  	      SCIP_CALL( SCIPreleaseVar(scip, &var) );
689  	   }
690  	
691  	   return SCIP_OKAY;
692  	}
693  	
694  	/** reset propagatore data structure */
695  	static
696  	void propdataReset(
697  	   SCIP_PROPDATA*        propdata            /**< propagator data */
698  	   )
699  	{
700  	   propdata->minactvars = NULL;
701  	   propdata->minactimpls = NULL;
702  	   propdata->maxactvars = NULL;
703  	   propdata->maxactchgs = NULL;
704  	   propdata->objintvars = NULL;
705  	   propdata->nminactvars = 0;
706  	   propdata->nmaxactvars = 0;
707  	   propdata->nobjintvars = 0;
708  	   propdata->maxpseudoobjact = SCIP_INVALID;
709  	   propdata->maxpseudoobjactinf = 0;
710  	   propdata->lastvarnum = -1;
711  	   propdata->glbpropagated = FALSE;
712  	   propdata->cutoffbound = SCIP_INVALID;
713  	   propdata->lastlowerbound = -SCIP_INVALID;
714  	   propdata->glbpseudoobjval = -SCIP_INVALID;
715  	   propdata->glbfirstnonfixed = 0;
716  	   propdata->maxactfirstnonfixed = 0;
717  	   propdata->firstnonfixed = 0;
718  	   propdata->nnewvars = 0;
719  	   propdata->minactsize = 0;
720  	   propdata->maxactsize = 0;
721  	   propdata->objintvarssize = 0;
722  	   propdata->catchvaradded = FALSE;
723  	   propdata->initialized = FALSE;
724  	}
725  	
726  	/** free propagator data */
727  	static
728  	SCIP_RETCODE propdataExit(
729  	   SCIP*                 scip,               /**< SCIP data structure */
730  	   SCIP_PROPDATA*        propdata            /**< propagator data */
731  	   )
732  	{
733  	   int v;
734  	
735  	   if( !propdata->initialized )
736  	      return SCIP_OKAY;
737  	
738  	   if( propdata->addedvars != NULL )
739  	      SCIPhashtableFree(&propdata->addedvars);
740  	
741  	   /* drop events for the variables */
742  	   SCIP_CALL( dropVarEvents(scip, propdata) );
743  	
744  	   for( v = 0; v < propdata->nminactvars; ++v )
745  	   {
746  	      SCIP_CALL( objimplicsFree(scip, &(propdata->minactimpls[v])) );
747  	   }
748  	
749  	   /* free memory for non-zero objective variables */
750  	   SCIPfreeBlockMemoryArrayNull(scip, &propdata->minactvars, propdata->minactsize);
751  	   SCIPfreeBlockMemoryArrayNull(scip, &propdata->minactimpls, propdata->minactsize);
752  	   SCIPfreeBlockMemoryArrayNull(scip, &propdata->maxactvars, propdata->maxactsize);
753  	   SCIPfreeBlockMemoryArrayNull(scip, &propdata->maxactchgs, propdata->maxactsize);
754  	   SCIPfreeBlockMemoryArrayNull(scip, &propdata->objintvars, propdata->objintvarssize);
755  	
756  	   /* reset propagator data structure */
757  	   propdataReset(propdata);
758  	
759  	   return SCIP_OKAY;
760  	}
761  	
762  	/** returns the objective change for the given binary variable */
763  	static
764  	SCIP_Real getVarObjchg(
765  	   SCIP_VAR*             var,                /**< variable to get objective change for */
766  	   SCIP_BOUNDTYPE        boundtype,          /**< bound type to consider */
767  	   SCIP_BOUNDTYPE        bound               /**< fixing bound */
768  	   )
769  	{
770  	   assert(SCIPvarIsBinary(var));
771  	   assert((int)SCIP_BOUNDTYPE_LOWER == 0); /*lint !e506*/
772  	   assert((int)SCIP_BOUNDTYPE_UPPER == 1); /*lint !e506*/
773  	
774  	   /* collect contribution of variable itself */
775  	   return (SCIP_Real)((int)bound - (int)(boundtype == SCIP_BOUNDTYPE_UPPER)) * SCIPvarGetObj(var);
776  	}
777  	
778  	/** returns the objective change provided by the implication variable by fixing it to the given bound
779  	 *  w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective
780  	 *  change;
781  	 */
782  	static
783  	SCIP_Real collectMinactImplicVar(
784  	   SCIP*                 scip,               /**< SCIP data structure */
785  	   SCIP_VAR*             var,                /**< variable to computes the objective contribution */
786  	   SCIP_HASHMAP*         binobjvarmap,       /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
787  	   SCIP_Bool*            collectedvars,      /**< temporary buffer to mark collected variables */
788  	   int                   nbinobjvars,        /**< number of binary variables with non-zero objective coefficient */
789  	   SCIP_VAR**            contributors,       /**< array to store the contributors */
790  	   int*                  ncontributors       /**< pointer to store number of contributor to the objective contribution */
791  	   )
792  	{
793  	   SCIP_Real objval;
794  	   int pos;
795  	
796  	   assert(scip != NULL);
797  	   assert(var != NULL);
798  	   assert(binobjvarmap != NULL);
799  	   assert(collectedvars != NULL);
800  	   assert(contributors != NULL);
801  	   assert(ncontributors != NULL);
802  	
803  	   /* ignore global fixed variables */
804  	   if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
805  	      return 0.0;
806  	
807  	   objval = SCIPvarGetObj(var);
808  	
809  	   /* ignore variables with zero objective coefficient */
810  	   if( SCIPisZero(scip, objval) )
811  	      return 0.0;
812  	
813  	   assert(SCIPhashmapExists(binobjvarmap, var));
814  	   pos = SCIPhashmapGetImageInt(binobjvarmap, var);
815  	   assert(pos > 0);
816  	
817  	   /* check if the variables was already collected through other cliques */
818  	   if( collectedvars[pos] )
819  	      return 0.0;
820  	
821  	   /* collect variable */
822  	   assert(*ncontributors < nbinobjvars);
823  	   contributors[*ncontributors] = var;
824  	   (*ncontributors)++;
825  	
826  	   /* mark variable to be collected */
827  	   collectedvars[pos] = TRUE;
828  	
829  	   /* return the absolute value of the objective coefficient as constriction */
830  	   return REALABS(objval);
831  	}
832  	
833  	#define MAX_CLIQUELENGTH 50
834  	/** returns the objective change provided by the implications of the given variable by fixing it to the given bound
835  	 *  w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective
836  	 *  change;
837  	 *
838  	 *  Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to
839  	 *  fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the
840  	 *  implications are:
841  	 *
842  	 *  \f[
843  	 *  \displaystyle
844  	 *  sum_{x\in I(1)} (1 - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{bestbound}(x) \cdot \mbox{objval}(x)
845  	 *  =
846  	 *  sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x)
847  	 *  \f]
848  	 */
849  	static
850  	SCIP_RETCODE collectMinactImplicVars(
851  	   SCIP*                 scip,               /**< SCIP data structure */
852  	   SCIP_VAR*             var,                /**< variable to computes the objective contribution */
853  	   SCIP_BOUNDTYPE        bound,              /**< bound to check for */
854  	   SCIP_HASHMAP*         binobjvarmap,       /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
855  	   SCIP_Bool*            collectedvars,      /**< temporary buffer to mark collected variables */
856  	   int                   nbinobjvars,        /**< number of binary variables with non-zero objective coefficient */
857  	   SCIP_VAR**            contributors,       /**< array to store the contributors */
858  	   SCIP_HASHTABLE*       uselesscliques,     /**< hash table to store useless cliques, or NULL */
859  	   int*                  ncontributors,      /**< pointer to store number of contributor to the objective contribution */
860  	   SCIP_Real*            objchg              /**< pointer to store the objective change */
861  	   )
862  	{
863  	   SCIP_CLIQUE** cliques;
864  	   SCIP_CLIQUE* clique;
865  	   SCIP_VAR** vars;
866  	   SCIP_VAR* implvar;
867  	   SCIP_Bool* values;
868  	   SCIP_Bool varfixing;
869  	   int nbinvars;
870  	   int ncliques;
871  	   int c;
872  	   int v;
873  	
874  	   assert(SCIPvarIsBinary(var));
875  	   assert(SCIPvarGetLbGlobal(var) < 0.5);
876  	   assert(SCIPvarGetUbGlobal(var) > 0.5);
877  	   assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER);
878  	   assert(objchg != NULL);
879  	   assert(contributors != NULL);
880  	   assert(ncontributors != NULL);
881  	   assert(*ncontributors == 0);
882  	
883  	   assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e506*/
884  	   assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);  /*lint !e506*/
885  	   varfixing = (SCIP_Bool)bound;
886  	
887  	   cliques = SCIPvarGetCliques(var, varfixing);
888  	   ncliques = SCIPvarGetNCliques(var, varfixing);
889  	
890  	   if( uselesscliques == NULL )
891  	      return SCIP_INVALIDDATA;
892  	
893  	#ifndef NDEBUG
894  	   /* check that the marker array is reset */
895  	   for( c = 0; c < nbinobjvars; ++c )
896  	      assert(collectedvars[c] == FALSE);
897  	#endif
898  	
899  	   /* collect all implication which are given via cliques */
900  	   for( c = 0; c < ncliques; ++c )
901  	   {
902  	      SCIP_Bool useless;
903  	
904  	      clique = cliques[c];
905  	      assert(clique != NULL);
906  	
907  	      /* check if the clique was previously detected to be useless with respect to minimum activity */
908  	      if( SCIPhashtableExists(uselesscliques, (void*)clique) )
909  	         continue;
910  	
911  	      nbinvars = SCIPcliqueGetNVars(clique);
912  	
913  	      if( nbinvars > MAX_CLIQUELENGTH )
914  	      {
915  	         SCIP_CALL( SCIPhashtableInsert(uselesscliques, (void*)clique) );
916  	         continue;
917  	      }
918  	
919  	      vars = SCIPcliqueGetVars(clique);
920  	      values = SCIPcliqueGetValues(clique);
921  	      useless = TRUE;
922  	
923  	      for( v = 0; v < nbinvars; ++v )
924  	      {
925  	         implvar = vars[v];
926  	         assert(implvar != NULL);
927  	
928  	         if( implvar == var )
929  	         {
930  	            /* check if the clique is useful at all */
931  	            if( useless )
932  	            {
933  	               SCIP_Real objval;
934  	
935  	               objval = SCIPvarGetObj(var);
936  	
937  	               if( varfixing == (SCIP_Bool)SCIPvarGetBestBoundType(var) && !SCIPisZero(scip, objval) )
938  	                  useless = FALSE;
939  	            }
940  	         }
941  	         else if( values[v] == (SCIP_Bool)SCIPvarGetBestBoundType(implvar) )
942  	         {
943  	            useless = FALSE;
944  	            (*objchg) += collectMinactImplicVar(scip, implvar, binobjvarmap, collectedvars, nbinobjvars, contributors, ncontributors);
945  	         }
946  	      }
947  	
948  	      /* if the clique is useless store it in the hash table to skip it later */
949  	      if( useless )
950  	      {
951  	         assert(!SCIPhashtableExists(uselesscliques, (void*)clique));
952  	         SCIP_CALL( SCIPhashtableInsert(uselesscliques, (void*)clique) );
953  	      }
954  	   }
955  	
956  	   return SCIP_OKAY;
957  	}
958  	
959  	/** returns the objective change provided by the implications of the given variable by fixing it to the given bound
960  	 *  w.r.t. minimum activity of the objective function
961  	 *
962  	 *  Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to
963  	 *  fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the
964  	 *  implications are:
965  	 *
966  	 *  \f[
967  	 *  \displaystyle
968  	 *  sum_{x\in I(1)} (1 - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{bestbound}(x) \cdot \mbox{objval}(x)
969  	 *  =
970  	 *  sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x)
971  	 *  \f]
972  	 *
973  	 *  This can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local variable bounds (local == TRUE &&
974  	 *  bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL)
975  	 */
976  	static
977  	SCIP_RETCODE getMinactImplicObjchg(
978  	   SCIP*                 scip,               /**< SCIP data structure */
979  	   SCIP_VAR*             var,                /**< variable to computes the objective contribution */
980  	   SCIP_OBJIMPLICS*      objimplics,         /**< objective implication data for the given variable */
981  	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index representing time on path to current node, or NULL */
982  	   SCIP_BOUNDTYPE        bound,              /**< bound to check for */
983  	   SCIP_Bool             local,              /**< propagate local bounds, otherwise global bounds */
984  	   SCIP_Real*            objchg              /**< pointer to store the objective change */
985  	   )
986  	{
987  	   SCIP_VAR* implvar;
988  	   SCIP_Bool lb;
989  	   SCIP_Bool ub;
990  	   int nbinvars;
991  	   int v;
992  	
993  	   assert(SCIPvarIsBinary(var));
994  	   assert(!local || SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE) < 0.5);
995  	   assert(!local || SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE) > 0.5);
996  	   assert(SCIPvarGetLbGlobal(var) < 0.5);
997  	   assert(SCIPvarGetUbGlobal(var) > 0.5);
998  	   assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER);
999  	
1000 	   if( bound == SCIP_BOUNDTYPE_LOWER )
1001 	   {
1002 	      v = 0;
1003 	      nbinvars = objimplics->nlbimpls;
1004 	   }
1005 	   else
1006 	   {
1007 	      assert(bound == SCIP_BOUNDTYPE_UPPER);
1008 	      v = objimplics->nlbimpls;
1009 	      nbinvars = objimplics->nlbimpls + objimplics->nubimpls;
1010 	   }
1011 	
1012 	   /* loop over all implications */
1013 	   while( v < nbinvars )
1014 	   {
1015 	      implvar = objimplics->objvars[v];
1016 	      assert(implvar != NULL);
1017 	      assert(!SCIPisZero(scip, SCIPvarGetObj(implvar)));
1018 	
1019 	      if( local )
1020 	      {
1021 	         lb = SCIPgetVarLbAtIndex(scip, implvar, bdchgidx, FALSE) > 0.5;
1022 	         ub = SCIPgetVarUbAtIndex(scip, implvar, bdchgidx, FALSE) > 0.5;
1023 	
1024 	         /* check if variable is fixed */
1025 	         if( lb == TRUE || ub == FALSE )
1026 	         {
1027 	            v++;
1028 	            continue;
1029 	         }
1030 	      }
1031 	      else
1032 	      {
1033 	         lb = SCIPvarGetLbGlobal(implvar) > 0.5;
1034 	         ub = SCIPvarGetUbGlobal(implvar) > 0.5;
1035 	
1036 	         /* check if variable is global fixed; if so remove it from the objective implication data structure and
1037 	          * continue with the next candidate
1038 	          */
1039 	         if( lb == TRUE || ub == FALSE )
1040 	         {
1041 	            SCIP_CALL( objimplicsDelPos(scip, objimplics, v) );
1042 	            nbinvars--;
1043 	            continue;
1044 	         }
1045 	      }
1046 	
1047 	      assert(SCIPvarGetObj(implvar) > 0.0 || SCIPvarsHaveCommonClique(var, (SCIP_Bool) bound, implvar, TRUE, TRUE));
1048 	      assert(SCIPvarGetObj(implvar) < 0.0 || SCIPvarsHaveCommonClique(var, (SCIP_Bool) bound, implvar, FALSE, TRUE));
1049 	
1050 	      /* add objective change */
1051 	      (*objchg) += REALABS(SCIPvarGetObj(implvar));
1052 	      v++;
1053 	   }
1054 	
1055 	   return SCIP_OKAY;
1056 	}
1057 	
1058 	/** computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum
1059 	 *  activity of the objective function; additionally it collects all contributors for that objective change;
1060 	 */
1061 	static
1062 	SCIP_RETCODE collectMinactObjchg(
1063 	   SCIP*                 scip,               /**< SCIP data structure */
1064 	   SCIP_VAR*             var,                /**< variable to computes the objective contribution */
1065 	   SCIP_BOUNDTYPE        bound,              /**< bound to check for */
1066 	   SCIP_HASHMAP*         binobjvarmap,       /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
1067 	   SCIP_Bool*            collectedvars,      /**< temporary buffer to mark collected variables */
1068 	   int                   nbinobjvars,        /**< number of binary variables with non-zero objective coefficient */
1069 	   SCIP_VAR**            contributors,       /**< array to store the contriboters */
1070 	   SCIP_HASHTABLE*       uselesscliques,     /**< hash table to store useless cliques, or NULL */
1071 	   int*                  ncontributors,      /**< pointer to store number of contributor to the objective contribution */
1072 	   SCIP_Real*            objchg              /**< pointer to store the objective change */
1073 	   )
1074 	{
1075 	   assert(SCIPvarIsBinary(var));
1076 	   assert(contributors != NULL);
1077 	   assert(ncontributors != NULL);
1078 	
1079 	   /* collects the contribution of the variable itself w.r.t. the best bound */
1080 	   (*objchg) = getVarObjchg(var, SCIPvarGetBestBoundType(var), bound);
1081 	
1082 	   (*ncontributors) = 0;
1083 	
1084 	   /* add the objective contribution from the implication variable */
1085 	   SCIP_CALL( collectMinactImplicVars(scip, var, bound, binobjvarmap, collectedvars, nbinobjvars, contributors, uselesscliques, ncontributors, objchg) );
1086 	
1087 	   return SCIP_OKAY;
1088 	}
1089 	
1090 	/** computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum
1091 	 *  activity of the objective function; this can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local
1092 	 *  variable bounds (local == TRUE && bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL)
1093 	 */
1094 	static
1095 	SCIP_RETCODE getMinactObjchg(
1096 	   SCIP*                 scip,               /**< SCIP data structure */
1097 	   SCIP_VAR*             var,                /**< variable to computes the objective contribution */
1098 	   SCIP_OBJIMPLICS*      objimplics,         /**< objective implication data for the given variable */
1099 	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index representing time on path to current node, or NULL */
1100 	   SCIP_BOUNDTYPE        bound,              /**< bound to check for */
1101 	   SCIP_Bool             local,              /**< propagate local bounds, otherwise global bounds */
1102 	   SCIP_Real*            objchg              /**< pointer to store the objective change */
1103 	   )
1104 	{
1105 	   assert(SCIPvarIsBinary(var));
1106 	
1107 	   /* collects the contribution of the variable itself w.r.t. the best bound */
1108 	   (*objchg) = getVarObjchg(var, SCIPvarGetBestBoundType(var), bound);
1109 	
1110 	   /* add the objective contribution from the implication variable */
1111 	   SCIP_CALL( getMinactImplicObjchg(scip, var, objimplics, bdchgidx, bound, local, objchg) );
1112 	
1113 	   return SCIP_OKAY;
1114 	}
1115 	
1116 	/** returns the global (that means w.r.t. global bounds of the variables) objective change provided by all cliques of
1117 	 *  the given variable by fixing it to the given bound w.r.t. maximum activity of the objective function
1118 	 *
1119 	 *  Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to
1120 	 *  fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by these
1121 	 *  implications are:
1122 	 *
1123 	 *  \f[
1124 	 *  \displaystyle
1125 	 *  sum_{x\in I(1)} (1 - \mbox{worstbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{worst}(x) \cdot \mbox{objval}(x)
1126 	 *  =
1127 	 *  sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{worstbound}(x)) \cdot \mbox{objval}(x)
1128 	 *  \f]
1129 	 */
1130 	static
1131 	SCIP_RETCODE getMaxactImplicObjchg(
1132 	   SCIP*                 scip,               /**< SCIP data structure */
1133 	   SCIP_VAR*             var,                /**< variable to computes the objective contribution */
1134 	   SCIP_BOUNDTYPE        bound,              /**< bound to check for */
1135 	   SCIP_Real*            objchg              /**< pointer to store the objective change */
1136 	   )
1137 	{
1138 	   SCIP_Bool varfixing;
1139 	   int ncliques;
1140 	   int nvars;
1141 	
1142 	   assert(scip != NULL);
1143 	   assert(SCIPvarIsBinary(var));
1144 	   assert(SCIPvarGetLbGlobal(var) < 0.5);
1145 	   assert(SCIPvarGetUbGlobal(var) > 0.5);
1146 	   assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER);
1147 	   assert(objchg != NULL);
1148 	
1149 	   varfixing = (SCIP_Bool)bound;
1150 	   assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e506*/
1151 	   assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);  /*lint !e506*/
1152 	
1153 	   *objchg = 0.0;
1154 	   ncliques = SCIPvarGetNCliques(var, varfixing);
1155 	
1156 	   if( ncliques > 0 )
1157 	   {
1158 	      SCIP_CLIQUE** cliques;
1159 	      SCIP_CLIQUE* clique;
1160 	      SCIP_VAR** clqvars;
1161 	      SCIP_VAR** probvars;
1162 	      SCIP_VAR* clqvar;
1163 	      SCIP_Bool* clqvalues;
1164 	      int* entries;
1165 	      int* ids;
1166 	      SCIP_Real obj;
1167 	      int nclqvars;
1168 	      int nentries;
1169 	      int objmult;
1170 	      int nids;
1171 	      int id;
1172 	      int c;
1173 	      int v;
1174 	
1175 	      assert(SCIPisTransformed(scip));
1176 	
1177 	      nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip) + 1;
1178 	
1179 	      SCIP_CALL( SCIPallocBufferArray(scip, &ids, 2*nentries) );
1180 	      nids = 0;
1181 	      /* @todo move this memory allocation to SCIP_SET and add a memory list there, to decrease the number of
1182 	       *       allocations and clear ups
1183 	       */
1184 	      SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
1185 	      BMSclearMemoryArray(entries, nentries);
1186 	
1187 	      cliques = SCIPvarGetCliques(var, varfixing);
1188 	      assert(cliques != NULL);
1189 	
1190 	      /* iterate over all cliques and determine all importantimplications */
1191 	      for( c = ncliques - 1; c >= 0; --c )
1192 	      {
1193 	         clique = cliques[c];
1194 	         clqvars = SCIPcliqueGetVars(clique);
1195 	         clqvalues = SCIPcliqueGetValues(clique);
1196 	         nclqvars = SCIPcliqueGetNVars(clique);
1197 	         assert(nclqvars > 0);
1198 	         assert(clqvars != NULL);
1199 	         assert(clqvalues != NULL);
1200 	
1201 	         if( nclqvars > MAX_CLIQUELENGTH )
1202 	            continue;
1203 	
1204 	         /* iterate over all clique variables */
1205 	         for( v = nclqvars - 1; v >= 0; --v )
1206 	         {
1207 	            clqvar = clqvars[v];
1208 	            assert(clqvar != NULL);
1209 	
1210 	            objmult = (int)!clqvalues[v] - (int)SCIPvarGetWorstBoundType(clqvar);
1211 	            assert(-1 <= objmult && objmult <= 1);
1212 	
1213 	            /* ignore binary variable which are either fixed and were the objective contribution will not be zero */
1214 	            if( clqvar != var && objmult != 0 && SCIPvarIsActive(clqvar) &&
1215 	               (SCIPvarGetLbGlobal(clqvar) < 0.5 && SCIPvarGetUbGlobal(clqvar) > 0.5) && !SCIPisZero(scip, SCIPvarGetObj(clqvar)) )
1216 	            {
1217 	               int probindex = SCIPvarGetProbindex(clqvar) + 1;
1218 	               assert(0 < probindex && probindex < nentries);
1219 	
1220 	               /* check that the variable was not yet visited  */
1221 	               assert(entries[probindex] == 0 || entries[probindex] == objmult);
1222 	               if( entries[probindex] == 0 )
1223 	               {
1224 	                  /* memorize probindex */
1225 	                  ids[nids] = probindex;
1226 	                  ++nids;
1227 	
1228 	                  assert(ABS(objmult) == 1);
1229 	
1230 	                  /* mark variable as visited */
1231 	                  entries[probindex] = objmult;
1232 	               }
1233 	            }
1234 	         }
1235 	      }
1236 	
1237 	      probvars = SCIPgetVars(scip);
1238 	      assert(probvars != NULL);
1239 	
1240 	      /* add all implied objective values */
1241 	      for( v = nids - 1; v >= 0; --v )
1242 	      {
1243 	         id = ids[v];
1244 	         assert(0 < id && id < nentries);
1245 	         assert(entries[id] != 0);
1246 	
1247 	         clqvar = probvars[id - 1];
1248 	         assert(clqvar != NULL);
1249 	         assert(SCIPvarIsBinary(clqvar));
1250 	         assert(SCIPvarIsActive(clqvar));
1251 	         assert(SCIPvarGetLbGlobal(clqvar) < 0.5);
1252 	         assert(SCIPvarGetUbGlobal(clqvar) > 0.5);
1253 	
1254 	         obj = SCIPvarGetObj(clqvar);
1255 	         assert(!SCIPisZero(scip, obj));
1256 	
1257 	         *objchg += entries[id] * obj;
1258 	      }
1259 	
1260 	      /* free temporary memory */
1261 	      SCIPfreeBufferArray(scip, &entries);
1262 	      SCIPfreeBufferArray(scip, &ids);
1263 	   }
1264 	
1265 	#ifdef SCIP_MORE_DEBUG
1266 	   SCIPdebugMsg(scip, "objective contribution when variable <%s> fixed to %u using cliques is %g\n", SCIPvarGetName(var),
1267 	      varfixing, *objchg);
1268 	#endif
1269 	
1270 	   /* collect non-binary implication information */
1271 	   nvars = SCIPvarGetNImpls(var, varfixing);
1272 	
1273 	   if( nvars > 0 )
1274 	   {
1275 	      SCIP_VAR** vars;
1276 	      SCIP_VAR* implvar;
1277 	      SCIP_Real* bounds;
1278 	      SCIP_BOUNDTYPE* boundtypes;
1279 	      SCIP_Real obj;
1280 	      SCIP_Real lb;
1281 	      SCIP_Real ub;
1282 	      int v;
1283 	
1284 	      vars =  SCIPvarGetImplVars(var, varfixing);
1285 	      boundtypes = SCIPvarGetImplTypes(var, varfixing);
1286 	      bounds = SCIPvarGetImplBounds(var, varfixing);
1287 	
1288 	      for( v = nvars - 1; v >= 0; --v )
1289 	      {
1290 	         implvar = vars[v];
1291 	         assert(implvar != NULL);
1292 	
1293 	         lb = SCIPvarGetLbLocal(implvar);
1294 	         ub = SCIPvarGetUbLocal(implvar);
1295 	         obj = SCIPvarGetObj(implvar);
1296 	
1297 	         /* ignore binary variable which are fixed or not of column status */
1298 	         if( SCIPisZero(scip, obj) )
1299 	            continue;
1300 	
1301 	         /* add up objective change if applicable */
1302 	         if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && SCIPvarGetWorstBoundType(implvar) == SCIP_BOUNDTYPE_LOWER && SCIPisFeasGT(scip, bounds[v], lb) )
1303 	            *objchg += (bounds[v] - lb)*obj;
1304 	         else if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && SCIPvarGetWorstBoundType(implvar) == SCIP_BOUNDTYPE_UPPER && SCIPisFeasLT(scip, bounds[v], ub) )
1305 	            *objchg += (bounds[v] - ub)*obj;
1306 	      }
1307 	   }
1308 	
1309 	#ifdef SCIP_MORE_DEBUG
1310 	   SCIPdebugMsg(scip, "objective contribution when variable <%s> fixed to %u using cliques and implications is %g\n", SCIPvarGetName(var),
1311 	      varfixing, *objchg);
1312 	#endif
1313 	
1314 	   return SCIP_OKAY;
1315 	}
1316 	
1317 	/** computes for the given binary variable the gloabl (that means w.r.t. global bounds of the variables) objective
1318 	 *  contribution by fixing it to given bound w.r.t. maximum activity of the objective function
1319 	 */
1320 	static
1321 	SCIP_RETCODE getMaxactObjchg(
1322 	   SCIP*                 scip,               /**< SCIP data structure */
1323 	   SCIP_VAR*             var,                /**< variable to computes the objective contribution */
1324 	   SCIP_BOUNDTYPE        bound,              /**< bound to check for */
1325 	   SCIP_Bool             useimplics,         /**< should implications be used */
1326 	   SCIP_Real*            objchg              /**< pointer to store the objective change */
1327 	   )
1328 	{
1329 	   assert(scip != NULL);
1330 	   assert(SCIPvarIsBinary(var));
1331 	   assert(objchg != NULL);
1332 	
1333 	   *objchg = 0;
1334 	
1335 	   /* check if the implications should be used to increase the objective contribution for given variable */
1336 	   if( useimplics )
1337 	   {
1338 	      /* using cliques and @todo other implications */
1339 	      SCIP_CALL( getMaxactImplicObjchg(scip, var, bound, objchg) );
1340 	   }
1341 	
1342 	   /* collects the contribution of the variable itself w.r.t. the worst bound */
1343 	   *objchg += getVarObjchg(var, SCIPvarGetWorstBoundType(var), bound);
1344 	
1345 	   return SCIP_OKAY;
1346 	}
1347 	
1348 	/** reset variables array which marks variables which are collected */
1349 	static
1350 	void resetContributors(
1351 	   SCIP_HASHMAP*         binobjvarmap,       /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
1352 	   SCIP_Bool*            collectedvars,      /**< temporary buffer to mark collected variables which should be reset */
1353 	   SCIP_VAR**            contributors,       /**< temporary buffer to use for collecting contributors */
1354 	   int                   ncontributors       /**< number of contributors */
1355 	   )
1356 	{
1357 	   SCIP_VAR* var;
1358 	   int pos;
1359 	   int c;
1360 	
1361 	   for( c = 0; c < ncontributors; ++c )
1362 	   {
1363 	      var = contributors[c];
1364 	      assert(var != NULL);
1365 	
1366 	      assert(SCIPhashmapExists(binobjvarmap, var));
1367 	      pos = SCIPhashmapGetImageInt(binobjvarmap, var);
1368 	      assert(pos > 0);
1369 	      collectedvars[pos] = FALSE;
1370 	   }
1371 	}
1372 	
1373 	/** check if the given variable should be collected for the minimum activity propagation */
1374 	static
1375 	SCIP_RETCODE collectMinactVar(
1376 	   SCIP*                 scip,               /**< SCIP data structure */
1377 	   SCIP_VAR*             var,                /**< variable to check */
1378 	   SCIP_OBJIMPLICS**     objimplics,         /**< pointer to store the objective implication data structure w.r.t. minimum activity */
1379 	   SCIP_Bool             useimplics,         /**< should implications be used */
1380 	   SCIP_HASHMAP*         binobjvarmap,       /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
1381 	   SCIP_Bool*            collectedlbvars,    /**< temporary buffer to mark collected variables for lower bound fixing */
1382 	   SCIP_Bool*            collectedubvars,    /**< temporary buffer to mark collected variables for upper bound fixing */
1383 	   int                   nbinobjvars,        /**< number of binary variables with non-zero objective coefficient */
1384 	   SCIP_VAR**            contributors,       /**< temporary buffer to use for collecting contributors */
1385 	   SCIP_HASHTABLE*       uselesscliques,     /**< hash table to store useless cliques, or NULL */
1386 	   SCIP_Bool*            collect             /**< pointer to store if the variable should be stored */
1387 	   )
1388 	{
1389 	   SCIP_Real lbobjchg;
1390 	   SCIP_Real ubobjchg;
1391 	   SCIP_Real objval;
1392 	   int nlbcliques;
1393 	   int nubcliques;
1394 	
1395 	   assert(objimplics != NULL);
1396 	
1397 	   objval = SCIPvarGetObj(var);
1398 	   (*objimplics) = NULL;
1399 	
1400 	   if( SCIPisZero(scip, objval) )
1401 	      (*collect) = FALSE;
1402 	   else
1403 	      (*collect) = TRUE;
1404 	
1405 	   nlbcliques = SCIPvarGetNCliques(var,  FALSE);
1406 	   nubcliques = SCIPvarGetNCliques(var,  TRUE);
1407 	
1408 	   /* check if implications should be used and if implications are existing */
1409 	   if( useimplics && nlbcliques + nubcliques > 0 )
1410 	   {
1411 	      int nlbcontributors;
1412 	      int nubcontributors;
1413 	
1414 	      assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e506*/
1415 	      assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);  /*lint !e506*/
1416 	
1417 	      /* get contribution of variable by fixing it to its lower bound w.r.t. minimum activity of the objective function */
1418 	      SCIP_CALL( collectMinactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, binobjvarmap, collectedlbvars, nbinobjvars,
1419 	            contributors, uselesscliques, &nlbcontributors, &lbobjchg) );
1420 	      assert(!SCIPisNegative(scip, lbobjchg));
1421 	
1422 	      SCIPdebugMsg(scip, "variable <%s> fixed to bound=%d implies %d(%d)\n", SCIPvarGetName(var),
1423 	         SCIP_BOUNDTYPE_LOWER, 0, nlbcontributors);
1424 	
1425 	      /* ignore implications if the variable has a zero objective coefficient and implications only one variable, since
1426 	       * this is covered by that implied variable
1427 	       */
1428 	      if( !(*collect) && nlbcontributors == 1 )
1429 	      {
1430 	         /* reset lower bound contributors */
1431 	         resetContributors(binobjvarmap, collectedlbvars, contributors, nlbcontributors);
1432 	
1433 	         assert(SCIPisZero(scip, objval));
1434 	         nlbcontributors = 0;
1435 	      }
1436 	
1437 	      /* get contribution of variable by fixing it to its upper bound w.r.t. minimum activity of the objective function */
1438 	      SCIP_CALL( collectMinactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, binobjvarmap, collectedubvars, nbinobjvars,
1439 	            &contributors[nlbcontributors], uselesscliques, &nubcontributors, &ubobjchg) );
1440 	      assert(!SCIPisNegative(scip, ubobjchg));
1441 	
1442 	      SCIPdebugMsg(scip, "variable <%s> fixed to bound=%d implies %d(%d)\n", SCIPvarGetName(var),
1443 	         SCIP_BOUNDTYPE_UPPER, 0, nubcontributors);
1444 	
1445 	      /* ignore implications if the variable has a zero objective coefficient and implications only one variable, since
1446 	       * this is covered by that implied variable
1447 	       */
1448 	      if( !(*collect) && nubcontributors == 1 )
1449 	      {
1450 	         /* reset upper bound contributors */
1451 	         resetContributors(binobjvarmap, collectedubvars, &contributors[nlbcontributors], nubcontributors);
1452 	
1453 	         assert(SCIPisZero(scip, objval));
1454 	         nubcontributors = 0;
1455 	      }
1456 	
1457 	      if( (*collect) || nlbcontributors > 1 || nubcontributors > 1 )
1458 	      {
1459 	         /* creates an objective implication data structure, fixes (globally) variables which are implied by lower and upper
1460 	          * bound fixing, and clears the collected arrays for lower and upper bound
1461 	          */
1462 	         SCIP_CALL( objimplicsCreate(scip, objimplics, contributors, binobjvarmap, collectedlbvars, collectedubvars, lbobjchg, ubobjchg, nlbcontributors, nubcontributors) );
1463 	         (*collect) = TRUE;
1464 	      }
1465 	      else
1466 	      {
1467 	         /* reset lower bound contributors */
1468 	         resetContributors(binobjvarmap, collectedlbvars, contributors, nlbcontributors);
1469 	
1470 	         /* reset upper bound contributors */
1471 	         resetContributors(binobjvarmap, collectedubvars, &contributors[nlbcontributors], nubcontributors);
1472 	      }
1473 	   }
1474 	   else if( (*collect) )
1475 	   {
1476 	      lbobjchg = getVarObjchg(var, SCIPvarGetBestBoundType(var), SCIP_BOUNDTYPE_LOWER);
1477 	      ubobjchg = getVarObjchg(var, SCIPvarGetBestBoundType(var), SCIP_BOUNDTYPE_UPPER);
1478 	      assert(!SCIPisZero(scip, lbobjchg) || !SCIPisZero(scip, ubobjchg));
1479 	      assert(!SCIPisNegative(scip, lbobjchg));
1480 	      assert(!SCIPisNegative(scip, ubobjchg));
1481 	
1482 	      /* creates an "empty" objective implication data structure */
1483 	      SCIP_CALL( objimplicsCreate(scip, objimplics, NULL, NULL, NULL, NULL, lbobjchg, ubobjchg, 0, 0) );
1484 	   }
1485 	
1486 	   return SCIP_OKAY;
1487 	}
1488 	
1489 	/** check if the given variable should be collected for the maximum activity propagation */
1490 	static
1491 	SCIP_RETCODE collectMaxactVar(
1492 	   SCIP*                 scip,               /**< SCIP data structure */
1493 	   SCIP_VAR*             var,                /**< variable to check */
1494 	   SCIP_Bool             useimplics,         /**< should implications be used */
1495 	   SCIP_Real*            objchg,             /**< pointer to store the objective change w.r.t. maximum activity */
1496 	   SCIP_Bool*            isnotzero           /**< pointer to store if the objective change is unequal to zero or not */
1497 	   )
1498 	{
1499 	   SCIP_Real lbobjchg;
1500 	   SCIP_Real ubobjchg;
1501 	
1502 	   assert(scip != NULL);
1503 	   assert(SCIPvarIsBinary(var));
1504 	   assert(objchg != NULL);
1505 	   assert(isnotzero != NULL);
1506 	
1507 	   /* get contribution of variable by fixing it to its lower bound w.r.t. maximum activity of the objective function */
1508 	   SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, useimplics, &lbobjchg) );
1509 	   assert(!SCIPisPositive(scip, lbobjchg));
1510 	
1511 	   /* get contribution of variable by fixing it to its upper bound w.r.t. maximum activity of the objective function */
1512 	   SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, useimplics, &ubobjchg) );
1513 	   assert(!SCIPisPositive(scip, ubobjchg));
1514 	
1515 	   (*objchg) = MIN(lbobjchg, ubobjchg);
1516 	
1517 	   /* only consider variables with non-zero objective contribution */
1518 	   if( SCIPisZero(scip, (*objchg)) )
1519 	      *isnotzero = FALSE;
1520 	   else
1521 	      *isnotzero = TRUE;
1522 	
1523 	   return SCIP_OKAY;
1524 	}
1525 	
1526 	/** initializate the propagator */
1527 	static
1528 	SCIP_RETCODE propdataInit(
1529 	   SCIP*                 scip,               /**< SCIP data structure */
1530 	   SCIP_PROPDATA*        propdata            /**< propagator data */
1531 	   )
1532 	{
1533 	   SCIP_VAR** vars;
1534 	   SCIP_VAR* var;
1535 	   SCIP_HASHMAP* binobjvarmap;
1536 	   int nvars;
1537 	   int nbinvars;
1538 	   int nintvars;
1539 	   int nminactvars;
1540 	   int nmaxactvars;
1541 	   int nobjintvars;
1542 	   int nobjcontvars;
1543 	   int nobjvars;
1544 	   int nbinobjvars;
1545 	   int v;
1546 	
1547 	   assert(scip != NULL);
1548 	   assert(propdata != NULL);
1549 	
1550 	   /* get problem variables */
1551 	   vars = SCIPgetVars(scip);
1552 	   nvars = SCIPgetNVars(scip);
1553 	   nintvars = nvars - SCIPgetNContVars(scip);
1554 	
1555 	   nbinvars = 0;
1556 	   nobjvars = 0;
1557 	   nbinobjvars = 0;
1558 	
1559 	   SCIP_CALL( SCIPhashmapCreate(&binobjvarmap, SCIPblkmem(scip), SCIPgetNObjVars(scip)) );
1560 	
1561 	   /* count and collect variable problem indices of variables with non-zero objective coefficient */
1562 	   for( v = 0; v < nvars; ++v )
1563 	   {
1564 	      var = vars[v];
1565 	      assert(var != NULL);
1566 	
1567 	      if( !SCIPisZero(scip, SCIPvarGetObj(var)) )
1568 	      {
1569 	         nobjvars++;
1570 	
1571 	         if( SCIPvarIsBinary(var) )
1572 	         {
1573 	            SCIP_CALL( SCIPhashmapInsertInt(binobjvarmap, (void*)var, nbinobjvars + 1) );
1574 	            nbinobjvars++;
1575 	         }
1576 	      }
1577 	
1578 	      if( SCIPvarIsBinary(var) )
1579 	         nbinvars++;
1580 	   }
1581 	
1582 	   nminactvars = 0;
1583 	   nmaxactvars = 0;
1584 	   nobjintvars = 0;
1585 	   nobjcontvars = 0;
1586 	
1587 	   if( nobjvars > 0 )
1588 	   {
1589 	      SCIP_EVENTHDLR* eventhdlr;
1590 	      SCIP_OBJIMPLICS* objimplics;
1591 	      SCIP_HASHTABLE* uselesscliques;
1592 	      SCIP_VAR** contributors;
1593 	      SCIP_Bool* collectedlbvars;
1594 	      SCIP_Bool* collectedubvars;
1595 	      SCIP_Bool collect;
1596 	      SCIP_Bool useimplics;
1597 	      SCIP_Real objval;
1598 	      SCIP_Real objchg;
1599 	
1600 	      eventhdlr = propdata->eventhdlr;
1601 	      assert(eventhdlr != NULL);
1602 	
1603 	      useimplics = (propdata->propuseimplics && nbinobjvars < propdata->maximplvars);
1604 	
1605 	      /* allocate memory for all arrays */
1606 	      propdata->minactsize = nbinvars;
1607 	      propdata->maxactsize = nbinvars;
1608 	      propdata->objintvarssize = nobjvars - nbinobjvars;
1609 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->minactvars, propdata->minactsize) );
1610 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->minactimpls, propdata->minactsize) );
1611 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->maxactvars, propdata->maxactsize) );
1612 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->maxactchgs, propdata->maxactsize) );
1613 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->objintvars, propdata->objintvarssize) );
1614 	
1615 	      if( useimplics )
1616 	      {
1617 	         int ncliques;
1618 	
1619 	         /* create temporary buffer */
1620 	         /* we store both lb and ub contributors in array contributors, and both could be nbinobjvars, we need twice that size */
1621 	         SCIP_CALL( SCIPallocBufferArray(scip, &contributors, 2 * nbinobjvars) );
1622 	         /* @todo: use SCIPallocCleanBufferArray instead? */
1623 	         SCIP_CALL( SCIPallocClearBufferArray(scip, &collectedlbvars, nbinobjvars+1) );
1624 	         /* @todo: use SCIPallocCleanBufferArray instead? */
1625 	         SCIP_CALL( SCIPallocClearBufferArray(scip, &collectedubvars, nbinobjvars+1) );
1626 	
1627 	         ncliques = SCIPgetNCliques(scip);
1628 	
1629 	         if( ncliques > 0 )
1630 	         {
1631 	            SCIP_CALL( SCIPhashtableCreate(&uselesscliques, SCIPblkmem(scip), ncliques,
1632 	                  cliqueGetHashkey, cliqueIsHashkeyEq, cliqueGetHashkeyVal, NULL) );
1633 	         }
1634 	         else
1635 	            uselesscliques = NULL;
1636 	      }
1637 	      else
1638 	      {
1639 	         contributors = NULL;
1640 	         collectedlbvars = NULL;
1641 	         collectedubvars = NULL;
1642 	         uselesscliques = NULL;
1643 	      }
1644 	
1645 	      /* collect the variables with non-zero objective contribution and catch global bound tighten events that decrease the
1646 	       * maximal pseudo objective activity
1647 	       */
1648 	      for( v = 0; v < nvars && (nobjintvars == 0 || nobjintvars < propdata->objintvarssize); ++v )
1649 	      {
1650 	         var = vars[v];
1651 	         assert(var != NULL);
1652 	
1653 	         objval = SCIPvarGetObj(var);
1654 	
1655 	         if( SCIPvarIsBinary(var) )
1656 	         {
1657 	            /* ignore variables which are globally fixed */
1658 	            if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
1659 	            {
1660 	#ifndef NDEBUG
1661 	               /* check that the binary implications are applied for binary variables which are globally fixed */
1662 	               checkImplicsApplied(scip, var);
1663 	#endif
1664 	               continue;
1665 	            }
1666 	
1667 	            /* check if the variable should be collected for the minimum activity propagation */
1668 	            SCIP_CALL( collectMinactVar(scip, var, &objimplics, useimplics, binobjvarmap, collectedlbvars, collectedubvars,
1669 	                  nbinobjvars, contributors, uselesscliques, &collect) );
1670 	
1671 	            if( collect )
1672 	            {
1673 	               assert(nminactvars < nbinvars);
1674 	               assert(objimplics != NULL);
1675 	               assert(objimplics->nlbimpls + objimplics->nubimpls <= nbinobjvars);
1676 	
1677 	               /* collect the binary variable with non-zero objective contribution */
1678 	               propdata->minactvars[nminactvars] = var;
1679 	               propdata->minactimpls[nminactvars] = objimplics;
1680 	               nminactvars++;
1681 	
1682 	               /* catch bound relax event for the binary variable to handel the firstnonfixed index correctly */
1683 	               SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDRELAXED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
1684 	
1685 	               SCIPdebugMsg(scip, "variable <%s>[obj: <%g>] implicit objective change %g\n",
1686 	                  SCIPvarGetName(var), objval, objimplics->maxobjchg);
1687 	
1688 	               /* captures the variable */
1689 	               SCIP_CALL( SCIPcaptureVar(scip, var) ) ;
1690 	            }
1691 	            /* check if the variable should be collected for the maximum activity propagation */
1692 	            SCIP_CALL( collectMaxactVar(scip, var, useimplics, &objchg, &collect) );
1693 	
1694 	            if( collect )
1695 	            {
1696 	               assert(nmaxactvars < nbinvars);
1697 	
1698 	               /* collect the binary variable with non-zero objective contribution */
1699 	               propdata->maxactvars[nmaxactvars] = var;
1700 	               propdata->maxactchgs[nmaxactvars] = -objchg;
1701 	               nmaxactvars++;
1702 	
1703 	               /* catch bound change events if the variable has a non-zero objective coefficient to check if the maximum
1704 	                * activity of the objective function changed
1705 	                */
1706 	               SCIP_CALL( catchObjEvent(scip, propdata, eventhdlr, var) );
1707 	
1708 	               /* captures the variable */
1709 	               SCIP_CALL( SCIPcaptureVar(scip, var) ) ;
1710 	            }
1711 	         }
1712 	         else
1713 	         {
1714 	            /* only consider non-binary variables with a non-zero objective */
1715 	            if( SCIPisZero(scip, objval) )
1716 	               continue;
1717 	
1718 	            assert(nobjintvars < propdata->objintvarssize);
1719 	
1720 	            propdata->objintvars[nobjintvars] = var;
1721 	            nobjintvars++;
1722 	
1723 	            if( v >= nintvars )
1724 	               nobjcontvars++;
1725 	
1726 	            /* catch bound change events if the variable has a non-zero objective coefficient to check if the maximum
1727 	             * activity of the objective function changed
1728 	             */
1729 	            SCIP_CALL( catchObjEvent(scip, propdata, eventhdlr, var) );
1730 	
1731 	            /* captures the variable */
1732 	            SCIP_CALL( SCIPcaptureVar(scip, var) );
1733 	         }
1734 	      }
1735 	
1736 	      if( useimplics )
1737 	      {
1738 	         if( uselesscliques != NULL )
1739 	            SCIPhashtableFree(&uselesscliques);
1740 	
1741 	         SCIPfreeBufferArray(scip, &collectedubvars);
1742 	         SCIPfreeBufferArray(scip, &collectedlbvars);
1743 	         SCIPfreeBufferArray(scip, &contributors);
1744 	      }
1745 	
1746 	      if( nminactvars == 0 )
1747 	      {
1748 	         SCIPfreeBlockMemoryArray(scip, &propdata->minactvars, propdata->minactsize);
1749 	         SCIPfreeBlockMemoryArray(scip, &propdata->minactimpls, propdata->minactsize);
1750 	         propdata->minactsize = 0;
1751 	         propdata->minactvars = NULL;
1752 	         propdata->minactimpls = NULL;
1753 	      }
1754 	      else
1755 	      {
1756 	         /* sort binary variables with respect to the absolute value of their maximal potential objective contribution for
1757 	          * the minimum activity of the objective function
1758 	          */
1759 	         SCIPsortDownPtrPtr((void**)propdata->minactimpls, (void**)propdata->minactvars, objimplicsComp, nminactvars);
1760 	
1761 	         SCIPdebugMsg(scip, "%d binary variables with non-zero objective contribution w.r.t. the minimum activity of the objective function\n", nminactvars);
1762 	      }
1763 	
1764 	      if( nmaxactvars == 0 )
1765 	      {
1766 	         SCIPfreeBlockMemoryArray(scip, &propdata->maxactvars, propdata->maxactsize);
1767 	         SCIPfreeBlockMemoryArray(scip, &propdata->maxactchgs, propdata->maxactsize);
1768 	         propdata->maxactsize = 0;
1769 	         propdata->maxactvars = NULL;
1770 	         propdata->maxactchgs = NULL;
1771 	      }
1772 	      else
1773 	      {
1774 	         /* sort binary variables with respect to the absolute value of their maximal potential objective contribution for
1775 	          * the maximum activity of the objective function
1776 	          */
1777 	         SCIPsortDownRealPtr(propdata->maxactchgs, (void**)propdata->maxactvars, nmaxactvars);
1778 	
1779 	         SCIPdebugMsg(scip, "%d binary variables with non-zero objective contribution w.r.t. the maximum activity of the objective function\n", nmaxactvars);
1780 	      }
1781 	
1782 	      if( nobjintvars == 0 )
1783 	      {
1784 	         SCIPfreeBlockMemoryArray(scip, &propdata->objintvars, propdata->objintvarssize);
1785 	         propdata->objintvarssize = 0;
1786 	         propdata->objintvars = NULL;
1787 	      }
1788 	      else
1789 	      {
1790 	         /* sort integer variables with respect to the absolute value of their objective coefficient */
1791 	         SCIPsortDownPtr((void**)propdata->objintvars, varCompObj, nobjintvars - nobjcontvars);
1792 	
1793 	         /* sort continuous variables with respect to the absolute value of their objective coefficient */
1794 	         SCIPsortDownPtr((void**)(&propdata->objintvars[nobjintvars - nobjcontvars]), varCompObj, nobjcontvars);
1795 	
1796 	         SCIPdebugMsg(scip, "%d integer variables and %d continuous variables with non-zero objective contribution\n",
1797 	            nobjintvars - nobjcontvars, nobjcontvars);
1798 	      }
1799 	   }
1800 	
1801 	   SCIPhashmapFree(&binobjvarmap);
1802 	
1803 	   propdata->nminactvars = nminactvars;
1804 	   propdata->nmaxactvars = nmaxactvars;
1805 	   propdata->nobjintvars = nobjintvars;
1806 	   propdata->maxpseudoobjact = SCIP_INVALID;
1807 	   propdata->maxpseudoobjactinf = 0;
1808 	   propdata->lastvarnum = -1;
1809 	   propdata->glbfirstnonfixed = 0;
1810 	   propdata->maxactfirstnonfixed = 0;
1811 	   propdata->firstnonfixed = 0;
1812 	   propdata->nnewvars = 0;
1813 	   propdata->cutoffbound = SCIPinfinity(scip);
1814 	   propdata->lastlowerbound = -SCIPinfinity(scip);
1815 	   propdata->glbpseudoobjval = -SCIPinfinity(scip);
1816 	
1817 	   propdata->initialized = TRUE;
1818 	
1819 	   /* due to scaling after presolving we need to update the global pseudoactivity and the cutoffbound */
1820 	   propdata->glbpropagated = FALSE;
1821 	   propdata->glbpseudoobjval = SCIPgetGlobalPseudoObjval(scip);
1822 	   propdata->cutoffbound = SCIPgetCutoffbound(scip);
1823 	   assert(SCIPgetDepth(scip) > 0 || SCIPisFeasEQ(scip, propdata->glbpseudoobjval, SCIPgetPseudoObjval(scip)));
1824 	
1825 	   /* create hash table which is used for resolving bound changes */
1826 	   if( nminactvars > 0 )
1827 	   {
1828 	      SCIP_CALL( SCIPhashtableCreate(&propdata->addedvars, SCIPblkmem(scip), nvars,
1829 	            SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) );
1830 	   }
1831 	   else
1832 	      propdata->addedvars = NULL;
1833 	
1834 	   return SCIP_OKAY;
1835 	}
1836 	
1837 	/** adds for the given non-binary variable a conflict bound depending on its objective contribution */
1838 	static
1839 	SCIP_RETCODE addConflictBounds(
1840 	   SCIP*                 scip,               /**< SCIP data structure */
1841 	   SCIP_VAR*             var,                /**< variable to check for objective contribution */
1842 	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index (time stamp of bound change), or NULL for current time */
1843 	   SCIP_Real*            reqpseudoobjval     /**< pointer to store the remaining minimum activity which has to be proven */
1844 	   )
1845 	{
1846 	   SCIP_Real objval;
1847 	
1848 	   objval = SCIPvarGetObj(var);
1849 	   assert(!SCIPisZero(scip, objval));
1850 	
1851 	   if( objval > 0.0 )
1852 	   {
1853 	      SCIP_Real loclb;
1854 	      SCIP_Real glblb;
1855 	
1856 	      glblb = SCIPvarGetLbGlobal(var);
1857 	      loclb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE);
1858 	      assert(SCIPisFeasGE(scip, loclb, glblb));
1859 	
1860 	      /* check if the local lower bound (at time stamp bdchgidx) is larger than the global lower bound */
1861 	      if( SCIPisGT(scip, loclb, glblb) )
1862 	      {
1863 	         SCIPdebugMsg(scip, "  add bound change <%s>[%g] >= <%g>\n", SCIPvarGetName(var), objval, loclb);
1864 	         SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
1865 	
1866 	         /* hard comparison  is enough to make requiredpseudoobjval nonincreasing */
1867 	         assert((loclb - glblb) * objval > 0.0);
1868 	
1869 	         (*reqpseudoobjval) -= (loclb - glblb) * objval;
1870 	      }
1871 	   }
1872 	   else
1873 	   {
1874 	      SCIP_Real locub;
1875 	      SCIP_Real glbub;
1876 	
1877 	      glbub = SCIPvarGetUbGlobal(var);
1878 	      locub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE);
1879 	      assert(SCIPisFeasLE(scip, locub, glbub));
1880 	
1881 	      /* check if the local upper bound (at time stamp bdchgidx) is smaller than the global upper bound */
1882 	      if( SCIPisLT(scip, locub, glbub) )
1883 	      {
1884 	         SCIPdebugMsg(scip, "  add bound change <%s>[%g] <= <%g>\n", SCIPvarGetName(var), objval, locub);
1885 	         SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
1886 	
1887 	         /* hard comparison  is enough to make requiredpseudoobjval nonincreasing */
1888 	         assert((locub - glbub) * objval > 0.0);
1889 	
1890 	         (*reqpseudoobjval) -= (locub - glbub) * objval;
1891 	      }
1892 	   }
1893 	
1894 	   return SCIP_OKAY;
1895 	}
1896 	
1897 	/** check for the given implication variables if they also contribute to the required minimum activity */
1898 	static
1899 	SCIP_RETCODE getConflictImplics(
1900 	   SCIP*                 scip,               /**< SCIP data structure */
1901 	   SCIP_VAR**            vars,               /**< variable to check for objective contribution */
1902 	   int                   start,              /**< start index */
1903 	   int                   end,                /**< end index */
1904 	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index (time stamp of bound change), or NULL for current time */
1905 	   SCIP_HASHTABLE*       addedvars,          /**< hash table containing variables which are already added directly or implicitly due to implications */
1906 	   SCIP_Real*            reqpseudoobjval,    /**< pointer to store the remaining minimum activity which has to be proven */
1907 	   SCIP_Bool*            foundimplics        /**< pointer to store if an implication is found */
1908 	   )
1909 	{
1910 	   SCIP_VAR* var;
1911 	   SCIP_Real lb;
1912 	   SCIP_Real ub;
1913 	   int v;
1914 	
1915 	   assert(foundimplics != NULL);
1916 	   assert(*foundimplics == FALSE);
1917 	
1918 	   for( v = start; v < end; ++v )
1919 	   {
1920 	      var = vars[v];
1921 	      assert(var != NULL);
1922 	      assert(SCIPvarIsBinary(var));
1923 	
1924 	      /* we need to take the bounds after the bdchgidx here, since the variable of the bound change may be the implied one;
1925 	       * we already counted its contribution before, so we want to see it as fixed here, which it is after the bound change.
1926 	       */
1927 	      lb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE);
1928 	      ub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE);
1929 	
1930 	      if( lb < 0.5 && ub > 0.5 && !SCIPhashtableExists(addedvars, (void*)var) )
1931 	      {
1932 	         (*reqpseudoobjval) -= REALABS(SCIPvarGetObj(var));
1933 	         SCIPdebugMsg(scip, "  implicated variables <%s>[%g] bdchgidx [%g,%g] -> remaining <%g>\n", SCIPvarGetName(var), SCIPvarGetObj(var), lb, ub, *reqpseudoobjval);
1934 	
1935 	         SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
1936 	         assert(SCIPhashtableExists(addedvars, (void*)var));
1937 	         (*foundimplics) = TRUE;
1938 	      }
1939 	   }
1940 	
1941 	   return SCIP_OKAY;
1942 	}
1943 	
1944 	/** adds for the given binary variable a conflict bound depending on its objective contribution */
1945 	static
1946 	SCIP_RETCODE addConflictBinvar(
1947 	   SCIP*                 scip,               /**< SCIP data structure */
1948 	   SCIP_VAR*             var,                /**< variable to check for objective contribution */
1949 	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index (time stamp of bound change), or NULL for current time */
1950 	   SCIP_OBJIMPLICS*      objimplics,         /**< objective implication data for the given variable */
1951 	   SCIP_HASHTABLE*       addedvars,          /**< hash table containing variables which are already add directly or implicitly due to implications */
1952 	   SCIP_Bool             respropuseimplics,  /**< should implications be used */
1953 	   SCIP_Real*            reqpseudoobjval     /**< pointer to store the remaining minimum activity which has to be proven */
1954 	   )
1955 	{
1956 	   SCIP_Real objval;
1957 	   SCIP_Real lb;
1958 	   SCIP_Real ub;
1959 	   SCIP_Bool foundimplics;
1960 	
1961 	   assert(SCIPvarIsBinary(var));
1962 	
1963 	   if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
1964 	      return SCIP_OKAY;
1965 	
1966 	   lb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE);
1967 	   ub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE);
1968 	
1969 	   objval = SCIPvarGetObj(var);
1970 	   foundimplics = FALSE;
1971 	
1972 	   /* only consider variables which are fixed */
1973 	   if( lb > 0.5 )
1974 	   {
1975 	      if( respropuseimplics )
1976 	      {
1977 	         assert(objimplics != NULL);
1978 	         SCIP_CALL( getConflictImplics(scip, objimplics->objvars, objimplics->nlbimpls, objimplics->nlbimpls + objimplics->nubimpls,
1979 	               bdchgidx, addedvars, reqpseudoobjval, &foundimplics) );
1980 	      }
1981 	
1982 	      /* check if the binary variable has a positive contribution (positive objective coefficient since it is fixed to
1983 	       * one) or is needed due a positive contribution of an implied variable
1984 	       */
1985 	      if( foundimplics || SCIPisPositive(scip, objval) )
1986 	      {
1987 	         SCIPdebugMsg(scip, "  add bound change <%s>[%g] >= <%g> bdchgidx [%g,%g]\n", SCIPvarGetName(var), objval, lb, lb, ub);
1988 	         SCIP_CALL( SCIPaddConflictLb(scip, var, NULL) );
1989 	
1990 	         (*reqpseudoobjval) -= MAX(0.0, objval);
1991 	
1992 	         if( addedvars != NULL )
1993 	         {
1994 	            assert(!SCIPhashtableExists(addedvars, (void*)var));
1995 	            SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
1996 	         }
1997 	      }
1998 	   }
1999 	   else if( ub < 0.5 )
2000 	   {
2001 	      if( respropuseimplics )
2002 	      {
2003 	         assert(objimplics != NULL);
2004 	         SCIP_CALL( getConflictImplics(scip, objimplics->objvars, 0, objimplics->nlbimpls,
2005 	               bdchgidx, addedvars, reqpseudoobjval, &foundimplics) );
2006 	      }
2007 	
2008 	      /* check if the binary variable has a positive contribution (negative objective coefficient since it is fixed to
2009 	       * zero) or is needed due a positive contribution of an implied variable
2010 	       */
2011 	      if( foundimplics || SCIPisNegative(scip, objval) )
2012 	      {
2013 	         SCIPdebugMsg(scip, "  add bound change <%s>[%g] <= <%g> bdchgidx=[%g,%g]\n", SCIPvarGetName(var), objval, ub, lb, ub);
2014 	         SCIP_CALL( SCIPaddConflictUb(scip, var, NULL) );
2015 	
2016 	         (*reqpseudoobjval) +=  MIN(0.0, objval);
2017 	
2018 	         if( addedvars != NULL )
2019 	         {
2020 	            assert(!SCIPhashtableExists(addedvars, (void*)var));
2021 	            SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
2022 	         }
2023 	      }
2024 	   }
2025 	
2026 	   return SCIP_OKAY;
2027 	}
2028 	
2029 	
2030 	/** resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the
2031 	 *  cutoff bound
2032 	 */
2033 	static
2034 	SCIP_RETCODE adjustCutoffbound(
2035 	   SCIP*                 scip,               /**< SCIP data structure */
2036 	   SCIP_PROPDATA*        propdata,           /**< propagator data */
2037 	   SCIP_VAR*             var,                /**< variable that was deduced */
2038 	   int                   inferinfo,          /**< inference information */
2039 	   SCIP_BOUNDTYPE        boundtype,          /**< the type of the changed bound (lower or upper bound) */
2040 	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index (time stamp of bound change), or NULL for current time */
2041 	   SCIP_HASHTABLE*       addedvars,          /**< hash table which contains variables which are already added or implicitly given as reason for the resolve, or NULL */
2042 	   SCIP_Real*            cutoffbound         /**< pointer to store the adjusted cutoff bound */
2043 	   )
2044 	{
2045 	   if( inferinfo != -1 )
2046 	   {
2047 	      SCIP_OBJIMPLICS* objimplics;
2048 	      int start;
2049 	      int end;
2050 	
2051 	      assert(var != NULL);
2052 	      assert(SCIPvarIsBinary(var));
2053 	      assert(bdchgidx != NULL);
2054 	      assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)));
2055 	      assert(inferinfo >= 0);
2056 	      assert(inferinfo < propdata->nminactvars);
2057 	      assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e506*/
2058 	      assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);  /*lint !e506*/
2059 	
2060 	      objimplics = propdata->minactimpls[inferinfo];
2061 	      assert(objimplics != NULL);
2062 	
2063 	      /* get the objective contribution if we would fix the binary inference variable to its other bound */
2064 	      (*cutoffbound) -= getVarObjchg(var, SCIPvarGetBestBoundType(var), boundtype);
2065 	
2066 	      if( boundtype == SCIP_BOUNDTYPE_LOWER )
2067 	      {
2068 	         start = 0;
2069 	         end = objimplics->nlbimpls;
2070 	      }
2071 	      else
2072 	      {
2073 	         start = objimplics->nlbimpls;
2074 	         end = objimplics->nlbimpls + objimplics->nubimpls;
2075 	      }
2076 	
2077 	      if( addedvars != NULL )
2078 	      {
2079 	         SCIP_Bool foundimplics = FALSE;
2080 	         SCIP_CALL( getConflictImplics(scip, objimplics->objvars, start, end, bdchgidx, addedvars, cutoffbound, &foundimplics) );
2081 	      } /*lint !e438*/
2082 	   }
2083 	   else
2084 	   {
2085 	      SCIP_Real glbbound;
2086 	      SCIP_Real newbound;
2087 	      SCIP_Real objval;
2088 	
2089 	      objval = SCIPvarGetObj(var);
2090 	
2091 	      assert(!SCIPisZero(scip, objval));
2092 	
2093 	      if( objval > 0.0 )
2094 	      {
2095 	         newbound = SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE);
2096 	         glbbound = SCIPvarGetLbGlobal(var);
2097 	      }
2098 	      else
2099 	      {
2100 	         newbound = SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE);
2101 	         glbbound = SCIPvarGetUbGlobal(var);
2102 	      }
2103 	
2104 	      /* in case the variable is integral we just need to prove the newbound plus/minus (1 - epsilon) since the this bound
2105 	       * would be rounded to newbound due to integrability which is global information
2106 	       */
2107 	      if( SCIPvarIsIntegral(var) )
2108 	      {
2109 	         if( objval > 0.0 )
2110 	            newbound += 1 - 10 * SCIPfeastol(scip);
2111 	         else
2112 	            newbound -= 1 - 10 * SCIPfeastol(scip);
2113 	      }
2114 	
2115 	      /* adjust the cutoff bound by the portion the inference variable contributes to the presudo objective activity
2116 	       * (minactivity)
2117 	       */
2118 	      assert(!SCIPisNegative(scip, objval * (newbound - glbbound)));
2119 	      (*cutoffbound) -= objval * (newbound - glbbound);
2120 	   }
2121 	
2122 	   return SCIP_OKAY;
2123 	}
2124 	
2125 	
2126 	/** resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the
2127 	 *  cutoff bound
2128 	 */
2129 	static
2130 	SCIP_RETCODE resolvePropagation(
2131 	   SCIP*                 scip,               /**< SCIP data structure */
2132 	   SCIP_PROPDATA*        propdata,           /**< propagator data */
2133 	   SCIP_Real             cutoffbound,        /**< the global cutoff */
2134 	   SCIP_VAR*             infervar,           /**< variable that was deduced, or NULL for conflict analysis initialization */
2135 	   int                   inferinfo,          /**< inference information */
2136 	   SCIP_BOUNDTYPE        boundtype,          /**< the type of the changed bound (lower or upper bound) */
2137 	   SCIP_BDCHGIDX*        bdchgidx            /**< bound change index (time stamp of bound change), or NULL for current time */
2138 	   )
2139 	{
2140 	   SCIP_HASHTABLE* addedvars;
2141 	   SCIP_VAR** vars;
2142 	   SCIP_VAR* var;
2143 	   SCIP_Real glbpseudoobjval;
2144 	   SCIP_Real reqpseudoobjval;
2145 	   SCIP_Bool infinity;
2146 	   int nvars;
2147 	   int v;
2148 	
2149 	   infinity = FALSE;
2150 	   addedvars = NULL;
2151 	   nvars = propdata->nminactvars;
2152 	
2153 	   /* the global pseudo value gives us a global valid minimal activity
2154 	    *
2155 	    * @note The global pseudo objective activity can be minus infinity. In that case all variable are part of the
2156 	    *       reason/explanation
2157 	    *
2158 	    * @note If the global pseudo objective activity is greater than the required minactivity, the local bound change
2159 	    *       which has to explained is actually (now) a global one. That means, the reason/explanation is empty
2160 	    */
2161 	   glbpseudoobjval = SCIPgetGlobalPseudoObjval(scip);
2162 	
2163 	   if( SCIPisInfinity(scip, -glbpseudoobjval) )
2164 	   {
2165 	      infinity = TRUE;
2166 	      reqpseudoobjval = cutoffbound;
2167 	   }
2168 	   else
2169 	   {
2170 	      /* clear hash table for storing variables which are not needed to add the reason due to global implications or
2171 	       * already added
2172 	       */
2173 	      if( nvars > 0 )
2174 	      {
2175 	         addedvars = propdata->addedvars;
2176 	         SCIPhashtableRemoveAll(addedvars);
2177 	      }
2178 	
2179 	      if( infervar != NULL )
2180 	      {
2181 	         SCIP_CALL( adjustCutoffbound(scip, propdata, infervar, inferinfo, boundtype, bdchgidx, addedvars, &cutoffbound) );
2182 	      }
2183 	
2184 	      reqpseudoobjval = cutoffbound - glbpseudoobjval;
2185 	   }
2186 	
2187 	   SCIPdebugMsg(scip, "resolve propagation global pseudo objective <%g>, cutoff bounda <%g>, required minactivity <%g>\n",
2188 	      glbpseudoobjval, cutoffbound, reqpseudoobjval);
2189 	
2190 	   /* the variables responsible for the propagation are the ones with
2191 	    *  - obj > 0 and local lb > global lb
2192 	    *  - obj < 0 and local ub < global ub
2193 	    *
2194 	    * collect all variables which contribute positively to the pseudo objective value (minimum activity) until we
2195 	    * reached the (adjusted) required minimum activity for the inference bound change
2196 	    */
2197 	
2198 	   /* first, consider the binary variables */
2199 	   if( nvars > 0 )
2200 	   {
2201 	      SCIP_OBJIMPLICS** minactimpls;
2202 	
2203 	      vars = propdata->minactvars;
2204 	      assert(vars != NULL);
2205 	
2206 	      minactimpls = propdata->minactimpls;
2207 	      assert(minactimpls != NULL);
2208 	
2209 	#ifndef NDEBUG
2210 	      checkGlbfirstnonfixed(propdata);
2211 	#endif
2212 	
2213 	      if( infinity )
2214 	      {
2215 	         /* if the required minimum activity is minus infinity, we have to add all variables which contribute the local
2216 	          * pseudo objective activity
2217 	          */
2218 	
2219 	         for( v = propdata->glbfirstnonfixed; v < nvars; ++v )
2220 	         {
2221 	            var = vars[v];
2222 	            assert(var != NULL);
2223 	
2224 	            /* @note binary variables can have a zero objective value */
2225 	
2226 	            if( var == infervar )
2227 	               continue;
2228 	
2229 	            SCIP_CALL( addConflictBinvar(scip, var, bdchgidx, NULL, NULL, FALSE, &reqpseudoobjval) );
2230 	         }
2231 	      }
2232 	      else
2233 	      {
2234 	         assert(addedvars != NULL);
2235 	
2236 	         for( v = propdata->glbfirstnonfixed; v < nvars && SCIPisPositive(scip, reqpseudoobjval); ++v )
2237 	         {
2238 	            var = vars[v];
2239 	            assert(var != NULL);
2240 	
2241 	            /* @note binary variables can have a zero objective value */
2242 	
2243 	            if( var == infervar )
2244 	               continue;
2245 	
2246 	            if( SCIPhashtableExists(addedvars, (void*)var) )
2247 	               continue;
2248 	
2249 	            SCIP_CALL( addConflictBinvar(scip, var, bdchgidx, minactimpls[v], addedvars, propdata->respropuseimplics, &reqpseudoobjval) );
2250 	         }
2251 	      }
2252 	   }
2253 	
2254 	   vars = propdata->objintvars;
2255 	   nvars = propdata->nobjintvars;
2256 	   assert(nvars == 0 || vars != NULL);
2257 	
2258 	   /* second, consider the non-binary variables */
2259 	   for( v = 0; v < nvars && (infinity || SCIPisPositive(scip, reqpseudoobjval)); ++v )
2260 	   {
2261 	      var = vars[v];
2262 	      assert(var != NULL);
2263 	      assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
2264 	
2265 	      if( var == infervar )
2266 	         continue;
2267 	
2268 	      SCIP_CALL( addConflictBounds(scip, var, bdchgidx, &reqpseudoobjval) );
2269 	   }
2270 	
2271 	   return SCIP_OKAY;
2272 	}
2273 	
2274 	/** propagates the given variable against the cutoff bound */
2275 	static
2276 	SCIP_RETCODE propagateCutoffboundVar(
2277 	   SCIP*                 scip,               /**< SCIP data structure */
2278 	   SCIP_PROP*            prop,               /**< propagator, or NULL */
2279 	   SCIP_VAR*             var,                /**< variable to propagate */
2280 	   int                   inferinfo,          /**< inference information to store with the bound change */
2281 	   SCIP_Real             objchg,             /**< objective change */
2282 	   SCIP_Real             cutoffbound,        /**< cutoff bound to use */
2283 	   SCIP_Real             pseudoobjval,       /**< pseudo objective value to use */
2284 	   SCIP_Bool             local,              /**< local or global propagation */
2285 	   SCIP_Bool*            tightened           /**< pointer to store if the variable domain was tightened */
2286 	   )
2287 	{
2288 	   SCIP_Real lb;
2289 	   SCIP_Real ub;
2290 	   SCIP_Real newbd;
2291 	   SCIP_Bool infeasible;
2292 	
2293 	   assert(!SCIPisZero(scip, objchg));
2294 	   assert(!SCIPisInfinity(scip, -pseudoobjval));
2295 	   assert(!SCIPisInfinity(scip, cutoffbound));
2296 	   assert(SCIPisLT(scip, pseudoobjval, cutoffbound) );
2297 	   assert(tightened != NULL);
2298 	
2299 	   *tightened = FALSE;
2300 	
2301 	   /* collect bounds of the variable */
2302 	   if( local )
2303 	   {
2304 	      assert(prop != NULL);
2305 	      lb = SCIPvarGetLbLocal(var);
2306 	      ub = SCIPvarGetUbLocal(var);
2307 	   }
2308 	   else
2309 	   {
2310 	      lb = SCIPvarGetLbGlobal(var);
2311 	      ub = SCIPvarGetUbGlobal(var);
2312 	   }
2313 	
2314 	   if( SCIPisFeasEQ(scip, lb, ub) )
2315 	      return SCIP_OKAY;
2316 	
2317 	   /* depending on the objective contribution we can try to tighten the lower or upper bound of the variable */
2318 	   if( objchg > 0.0 )
2319 	   {
2320 	      SCIP_Real QUAD(newbdq);
2321 	
2322 	      /* the new variable bound is lb + (cutoffbound - pseudoobjval) / objchg */
2323 	      SCIPquadprecSumDD(newbdq, cutoffbound, -pseudoobjval);
2324 	      SCIPquadprecDivQD(newbdq, newbdq, objchg);
2325 	      SCIPquadprecSumQD(newbdq, newbdq, lb);
2326 	      newbd = QUAD_TO_DBL(newbdq);
2327 	
2328 	      if( local )
2329 	      {
2330 	         SCIP_CALL( SCIPinferVarUbProp(scip, var, newbd, prop, inferinfo, FALSE, &infeasible, tightened) );
2331 	         assert(!infeasible);
2332 	
2333 	         if( *tightened ) /* might not be tightened due to numerical reasons */
2334 	         {
2335 	            SCIPdebugMsg(scip, " -> new (local) upper bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2336 	               SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2337 	         }
2338 	      }
2339 	      else
2340 	      {
2341 	         SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, &infeasible, tightened) );
2342 	         assert(!infeasible);
2343 	
2344 	         if( *tightened )
2345 	         {
2346 	            SCIPdebugMsg(scip, " -> new (global) upper bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2347 	               SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2348 	         }
2349 	      }
2350 	   }
2351 	   else
2352 	   {
2353 	      SCIP_Real QUAD(newbdq);
2354 	
2355 	      /* the new variable bound is ub + (cutoffbound - pseudoobjval) / objchg */
2356 	      SCIPquadprecSumDD(newbdq, cutoffbound, -pseudoobjval);
2357 	      SCIPquadprecDivQD(newbdq, newbdq, objchg);
2358 	      SCIPquadprecSumQD(newbdq, newbdq, ub);
2359 	      newbd = QUAD_TO_DBL(newbdq);
2360 	
2361 	      if( local )
2362 	      {
2363 	         SCIP_CALL( SCIPinferVarLbProp(scip, var, newbd, prop, inferinfo, FALSE, &infeasible, tightened) );
2364 	         assert(!infeasible);
2365 	
2366 	         if( *tightened ) /* might not be tightened due to numerical reasons */
2367 	         {
2368 	            SCIPdebugMsg(scip, " -> new (local) lower bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2369 	               SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2370 	         }
2371 	      }
2372 	      else
2373 	      {
2374 	         SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, &infeasible, tightened) );
2375 	         assert(!infeasible);
2376 	
2377 	         if( *tightened )
2378 	         {
2379 	            SCIPdebugMsg(scip, " -> new (global) lower bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2380 	               SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2381 	         }
2382 	      }
2383 	   }
2384 	
2385 	   return SCIP_OKAY;
2386 	}
2387 	
2388 	/** propagates the given binary variable against the cutoff bound */
2389 	static
2390 	SCIP_RETCODE propagateCutoffboundBinvar(
2391 	   SCIP*                 scip,               /**< SCIP data structure */
2392 	   SCIP_PROP*            prop,               /**< propagator, or NULL */
2393 	   SCIP_VAR*             var,                /**< variable to propagate */
2394 	   int                   pos,                /**< position of the variable in the corresponding propdata variable array */
2395 	   SCIP_Real             cutoffbound,        /**< cutoff bound to use */
2396 	   SCIP_Real             pseudoobjval,       /**< pseudo objective value to use */
2397 	   SCIP_Bool*            tightened,          /**< pointer to store if the variable domain was tightened */
2398 	   SCIP_Bool*            cutoff,             /**< pointer to store if a cutoff was detected */
2399 	   SCIP_Bool             local               /**< propagate local bounds, otherwise global bounds */
2400 	   )
2401 	{
2402 	   SCIP_PROPDATA* propdata;
2403 	   SCIP_OBJIMPLICS* objimplics;
2404 	   SCIP_Real lbobjchg;
2405 	   SCIP_Real ubobjchg;
2406 	   SCIP_Real objchg;
2407 	
2408 	   assert(SCIPvarIsBinary(var));
2409 	
2410 	   propdata = SCIPpropGetData(prop);
2411 	   assert(propdata != NULL);
2412 	
2413 	   objimplics = propdata->minactimpls[pos];
2414 	   assert(objimplics != NULL);
2415 	
2416 	   /* get objective change in case of fixing the variable to its lower bound (that is zero) */
2417 	   SCIP_CALL( getMinactObjchg(scip, var, objimplics, NULL, SCIP_BOUNDTYPE_LOWER, local, &lbobjchg) );
2418 	   assert(!SCIPisNegative(scip, lbobjchg));
2419 	
2420 	   /* get objective change in case of fixing the variable to its upper bound (that is one) */
2421 	   SCIP_CALL( getMinactObjchg(scip, var, objimplics, NULL, SCIP_BOUNDTYPE_UPPER, local, &ubobjchg) );
2422 	   assert(!SCIPisNegative(scip, ubobjchg));
2423 	
2424 	   (*tightened) = FALSE;
2425 	
2426 	   /* nothing can be done if the objective contribution is zero independently of the bound */
2427 	   if( SCIPisZero(scip, lbobjchg) && SCIPisZero(scip, ubobjchg) )
2428 	      return SCIP_OKAY;
2429 	
2430 	   /* if the lbobjchg and ubobjchg are both able to fix the variable to its upper (1.0) or lower (0.0) bound,
2431 	    * respectively, we detected an cutoff
2432 	    *
2433 	    * @note There is no need to use SCIPisFeasLT() in case the objective is integral since the cutoff bound in that case
2434 	    *       is the upper bound minus 1 plus the SCIPcutoffbounddelta() (which is MIN(100.0 * feastol, 0.0001)). However,
2435 	    *       if the objective is not integral we have to check w.r.t. an epsilon to avoid numerical problems.
2436 	    */
2437 	   if( SCIPisFeasLT(scip, cutoffbound, pseudoobjval + ubobjchg) && SCIPisFeasLT(scip, cutoffbound, pseudoobjval + lbobjchg) )
2438 	   {
2439 	      /* check if conflict analysis is applicable */
2440 	      if( local && SCIPisConflictAnalysisApplicable(scip) )
2441 	      {
2442 	         assert(SCIPgetDepth(scip) > 0);
2443 	
2444 	         /* initialize conflict analysis */
2445 	         SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, TRUE) );
2446 	
2447 	         /* add all variable whose best bound changes increased the pseudo objective value above to cutoff bound */
2448 	         SCIP_CALL( resolvePropagation(scip, propdata, pseudoobjval, NULL, -1, SCIP_BOUNDTYPE_UPPER, NULL) );
2449 	
2450 	         /* analyze the conflict */
2451 	         SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
2452 	      }
2453 	
2454 	      (*cutoff) = TRUE;
2455 	   }
2456 	   else
2457 	   {
2458 	      /* try to tighten the variable bound use the larger objective contribution */
2459 	      if( lbobjchg > ubobjchg )
2460 	         objchg = -lbobjchg;
2461 	      else
2462 	         objchg = ubobjchg;
2463 	
2464 	      SCIP_CALL( propagateCutoffboundVar(scip, prop, var, pos, objchg, cutoffbound, pseudoobjval, local, tightened) );
2465 	   }
2466 	
2467 	   return SCIP_OKAY;
2468 	}
2469 	
2470 	/** globally propagates if a new cutoff bound or global pseudo objective value (minimum activity of the objective
2471 	 *  function) is available
2472 	 */
2473 	static
2474 	SCIP_RETCODE propagateCutoffboundGlobally(
2475 	   SCIP*                 scip,               /**< SCIP data structure */
2476 	   SCIP_PROP*            prop,               /**< propagator */
2477 	   int*                  nchgbds,            /**< pointer to store the number of bound changes */
2478 	   SCIP_Bool*            cutoff              /**< pointer to store if a cutoff was detected */
2479 	   )
2480 	{
2481 	   SCIP_PROPDATA* propdata;
2482 	   SCIP_VAR** minactvars;
2483 	   SCIP_VAR** objintvars;
2484 	   SCIP_VAR* var;
2485 	   SCIP_Bool tightened;
2486 	   SCIP_Real pseudoobjval;
2487 	   SCIP_Real cutoffbound;
2488 	   int nminactvars;
2489 	   int nobjintvars;
2490 	   int v;
2491 	
2492 	   /* this method should not be called in the root node of the search tree since the standard propagation already does
2493 	    * the job
2494 	    */
2495 	   assert(SCIPgetDepth(scip) > 0);
2496 	
2497 	   propdata = SCIPpropGetData(prop);
2498 	   assert(propdata != NULL);
2499 	
2500 	   pseudoobjval = SCIPgetGlobalPseudoObjval(scip);
2501 	   cutoffbound = propdata->cutoffbound;
2502 	
2503 	   /* nothing can be done if the global pseudo objective is minus infinity */
2504 	   if( SCIPisInfinity(scip, -pseudoobjval) )
2505 	      return SCIP_OKAY;
2506 	
2507 	   /* check if the global pseudo objective value (minimum activity of the objective function) is greater or equal to
2508 	    * the cutoff bound
2509 	    */
2510 	   if( SCIPisGE(scip, pseudoobjval, cutoffbound) )
2511 	   {
2512 	      *cutoff = TRUE;
2513 	      return SCIP_OKAY;
2514 	   }
2515 	
2516 	   minactvars = propdata->minactvars;
2517 	   objintvars = propdata->objintvars;
2518 	   nminactvars = propdata->nminactvars;
2519 	   nobjintvars = propdata->nobjintvars;
2520 	
2521 	#ifndef NDEBUG
2522 	   checkGlbfirstnonfixed(propdata);
2523 	#endif
2524 	
2525 	   *cutoff = FALSE;
2526 	
2527 	   /* always propagate the binary variables completely */
2528 	   for( v = propdata->glbfirstnonfixed; v < nminactvars; ++v )
2529 	   {
2530 	      var = minactvars[v];
2531 	      assert(var != NULL);
2532 	
2533 	      /* check if the variables is already globally fixed; if so continue with the potential candidate */
2534 	      if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
2535 	         continue;
2536 	
2537 	      /* propagates the cutoff bound for the given binary variable */
2538 	      SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) );
2539 	
2540 	      /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective
2541 	       * contribution w.r.t. minimum activity (pseudo objective value) of the objective function; these values are the
2542 	       * increase in the pseudo objective activity we would get if we fix the variable to its worse bound; hence, we can
2543 	       * stop if for a variable this potential increase is not enough too exceed the cutoff bound;
2544 	       */
2545 	      if( !tightened )
2546 	      {
2547 	         SCIPdebugMsg(scip, "interrupt global pseudo objective propagation w.r.t. cutoff bound <%.15g> for binary variables after %d from %d binary variables\n",
2548 	            cutoffbound, v, nminactvars);
2549 	         break;
2550 	      }
2551 	
2552 	      if( *cutoff )
2553 	         return SCIP_OKAY;
2554 	
2555 	      /* @note The variable might not be globally fixed right away since this would destroy the local internal
2556 	       *       data structure of a search node; the bound change is in that case pending; hence we cannot assert
2557 	       *       that the variable is globally fixed
2558 	       */
2559 	      (*nchgbds)++;
2560 	   }
2561 	   propdata->glbfirstnonfixed = v;
2562 	   propdata->firstnonfixed = MAX(propdata->firstnonfixed, v);
2563 	
2564 	   /* check all binary variables which could potentially be fixed */
2565 	   for( ; v < nminactvars && cutoffbound - pseudoobjval <  propdata->minactimpls[v]->maxobjchg; ++v )
2566 	   {
2567 	      var = minactvars[v];
2568 	      assert(var != NULL);
2569 	
2570 	      /* check if the variables is already globally fixed; if so continue with the potential candidate */
2571 	      if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
2572 	         continue;
2573 	
2574 	      /* propagates the cutoff bound for the given binary variable */
2575 	      SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) );
2576 	
2577 	      /* check if the domain of the variable was reduced */
2578 	      if( tightened )
2579 	         (*nchgbds)++;
2580 	
2581 	      if( *cutoff )
2582 	         return SCIP_OKAY;
2583 	   }
2584 	
2585 	#if 0 /* might fail, but is not a real error, still need to investigate */
2586 	#ifndef NDEBUG
2587 	   /* check that the abort criteria for the binary variables works */
2588 	   for( ; v < nminactvars; ++v )
2589 	   {
2590 	      assert(cutoffbound - pseudoobjval >=  propdata->minactimpls[v]->maxobjchg);
2591 	
2592 	      var = minactvars[v];
2593 	      assert(var != NULL);
2594 	
2595 	      /* check if the variable is already locally fixed; in that case we just continue with the next potential
2596 	       * candidate
2597 	       */
2598 	      if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
2599 	         continue;
2600 	
2601 	      /* propagates the cutoff bound for the given binary variable */
2602 	      SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) );
2603 	      assert(!tightened);
2604 	      assert(!(*cutoff));
2605 	   }
2606 	#endif
2607 	#endif
2608 	
2609 	   /* propagate the non-binary variables completely */
2610 	   for( v = 0; v < nobjintvars; ++v )
2611 	   {
2612 	      var = objintvars[v];
2613 	      assert(var != NULL);
2614 	      assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
2615 	
2616 	      /* try to tighten the bound of the variable */
2617 	      SCIP_CALL( propagateCutoffboundVar(scip, NULL, var, -1, SCIPvarGetObj(var), cutoffbound, pseudoobjval, FALSE, &tightened) );
2618 	
2619 	      /* check if the domain of the variable was reduced */
2620 	      if( tightened )
2621 	         (*nchgbds)++;
2622 	   }
2623 	
2624 	   propdata->glbpropagated = TRUE;
2625 	
2626 	   return SCIP_OKAY;
2627 	}
2628 	
2629 	/** propagates the cutoff bound for binary variables (c*x <= cutoff) */
2630 	static
2631 	SCIP_RETCODE propagateCutoffboundBinvars(
2632 	   SCIP*                 scip,               /**< SCIP data structure */
2633 	   SCIP_PROP*            prop,               /**< propagator */
2634 	   SCIP_Real             cutoffbound,        /**< cutoff bound to use */
2635 	   SCIP_Real             pseudoobjval,       /**< pseudo objective value to use */
2636 	   int*                  nfixedvars,         /**< pointer to store the number of fixed variables */
2637 	   SCIP_Bool*            cutoff              /**< pointer to store if a cutoff was detected */
2638 	   )
2639 	{
2640 	   SCIP_PROPDATA* propdata;
2641 	   SCIP_VAR** minactvars;
2642 	   SCIP_VAR* var;
2643 	   SCIP_Bool tightened;
2644 	   int nminactvars;
2645 	   int v;
2646 	
2647 	   propdata = SCIPpropGetData(prop);
2648 	   assert(propdata != NULL);
2649 	
2650 	   minactvars = propdata->minactvars;
2651 	   nminactvars = propdata->nminactvars;
2652 	   assert(nminactvars == 0 || minactvars != NULL);
2653 	
2654 	   /* always propagate the binary variables completely; note that the variables before the firstnonfixed indexed are
2655 	    * already locally fixed and those before glbfirstnonfixed are already globally fixed
2656 	    */
2657 	
2658 	#ifndef NDEBUG
2659 	   /* check that the variables before glbfirstnonfixed are globally fixed */
2660 	   checkGlbfirstnonfixed(propdata);
2661 	
2662 	   /* check that the variables before firstnonfixed are locally fixed */
2663 	   for( v = propdata->glbfirstnonfixed; v < propdata->firstnonfixed; ++v )
2664 	   {
2665 	      var =  minactvars[v];
2666 	      assert(var != NULL);
2667 	
2668 	      assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
2669 	   }
2670 	#endif
2671 	
2672 	   (*cutoff) = FALSE;
2673 	
2674 	   for( v = propdata->firstnonfixed; v < nminactvars; ++v )
2675 	   {
2676 	      var =  minactvars[v];
2677 	      assert(var != NULL);
2678 	
2679 	      /* check if the variable is already locally fixed; in that case we just continue with the next potential
2680 	       * candidate
2681 	       */
2682 	      if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
2683 	         continue;
2684 	
2685 	      /* propagates the cutoff bound for the given binary variable */
2686 	      SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) );
2687 	
2688 	      /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective
2689 	       * contribution w.r.t. minimum activity of the objective function; These values are the increase in the pseudo
2690 	       * objective activity (minimum activity of the objective function) we would get if we fix the variable to its
2691 	       * worse bound; hence, we can stop if for a variable this potential increase is not enough too exceed the cutoff
2692 	       * bound;
2693 	       */
2694 	      if( !tightened )
2695 	      {
2696 	         SCIPdebugMsg(scip, "interrupt local pseudo objective propagation w.r.t. cutoff bound <%.15g> for binary variables after %d from %d binary variables\n",
2697 	            cutoffbound, v, nminactvars);
2698 	         break;
2699 	      }
2700 	
2701 	      if( *cutoff )
2702 	         return SCIP_OKAY;
2703 	
2704 	      /* check that the binary variable is locally fixed */
2705 	      assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
2706 	      (*nfixedvars)++;
2707 	   }
2708 	   propdata->firstnonfixed = v;
2709 	
2710 	   /* check all binary variables which could potentially be fixed */
2711 	   for( ; v < nminactvars && cutoffbound - pseudoobjval < propdata->minactimpls[v]->maxobjchg; ++v )
2712 	   {
2713 	      var =  minactvars[v];
2714 	      assert(var != NULL);
2715 	
2716 	      /* check if the variable is already locally fixed; in that case we just continue with the next potential
2717 	       * candidate
2718 	       */
2719 	      if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
2720 	         continue;
2721 	
2722 	      /* propagates the cutoff bound for the given binary variable */
2723 	      SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) );
2724 	
2725 	      if( tightened )
2726 	      {
2727 	         assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
2728 	         (*nfixedvars)++;
2729 	      }
2730 	
2731 	      if( *cutoff )
2732 	         return SCIP_OKAY;
2733 	   }
2734 	
2735 	#if 0 /* might fail, but is not a real error, still need to investigate */
2736 	#ifndef NDEBUG
2737 	   /* check that the abort criteria for the binary variables works */
2738 	   for( ; v < nminactvars; ++v )
2739 	   {
2740 	      var = minactvars[v];
2741 	      assert(var != NULL);
2742 	
2743 	      assert(cutoffbound - pseudoobjval >= propdata->minactimpls[v]->maxobjchg);
2744 	
2745 	      /* check if the variable is already locally fixed; in that case we just continue with the next potential
2746 	       * candidate
2747 	       */
2748 	      if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
2749 	         continue;
2750 	
2751 	      /* propagates the cutoff bound for the given binary variable */
2752 	      SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) );
2753 	      assert(!tightened);
2754 	      assert(!(*cutoff));
2755 	   }
2756 	#endif
2757 	#endif
2758 	
2759 	   return SCIP_OKAY;
2760 	}
2761 	
2762 	/** propagates the cutoff bound c*x <= cutoff */
2763 	static
2764 	SCIP_RETCODE propagateCutoffbound(
2765 	   SCIP*                 scip,               /**< SCIP data structure */
2766 	   SCIP_PROP*            prop,               /**< propagator */
2767 	   SCIP_RESULT*          result              /**< pointer to store the result of the callback method */
2768 	   )
2769 	{
2770 	   SCIP_PROPDATA* propdata;
2771 	   SCIP_Real pseudoobjval;
2772 	   SCIP_Real cutoffbound;
2773 	   SCIP_Bool cutoff;
2774 	   SCIP_Bool tightened;
2775 	   int nchgbds;
2776 	
2777 	   assert(result != NULL);
2778 	
2779 	   (*result) = SCIP_DIDNOTRUN;
2780 	
2781 	   propdata = SCIPpropGetData(prop);
2782 	   assert(propdata != NULL);
2783 	
2784 	   /* get current pseudo objective value (minimum activity of the objective function) and cutoff bound */
2785 	   pseudoobjval = SCIPgetPseudoObjval(scip);
2786 	   if( SCIPisInfinity(scip, -pseudoobjval) )
2787 	      return SCIP_OKAY;
2788 	   cutoffbound = SCIPgetCutoffbound(scip);
2789 	   if( SCIPisInfinity(scip, cutoffbound) )
2790 	      return SCIP_OKAY;
2791 	
2792 	   /* @note A new global pseudo objective value could be used to retrieve global fixings. There is, however, no need to
2793 	    *       check if a new global pseudo objective value is available. This is the case since a new (better) global
2794 	    *       pseudo activity implies that a global bound change was performed. That causes that the root node of the
2795 	    *       search tree gets marked for repropagation. That will result in a propagation call of the pseudo objective
2796 	    *       propagator.
2797 	    */
2798 	
2799 	   /* check current cutoff bound */
2800 	   if( cutoffbound < propdata->cutoffbound )
2801 	   {
2802 	      propdata->glbpropagated = FALSE;
2803 	      propdata->cutoffbound = cutoffbound;
2804 	   }
2805 	
2806 	   nchgbds = 0;
2807 	   cutoff = FALSE;
2808 	   (*result) = SCIP_DIDNOTFIND;
2809 	
2810 	   /* check if we have a new cutoff bound; in that case we globally propagate this new bound
2811 	    *
2812 	    * @note there is no need to propagate the cutoff bound if we are in the root node since this will be done by the
2813 	    *       standard local propagation
2814 	    */
2815 	   if( propdata->propcutoffbound && !propdata->glbpropagated && SCIPgetDepth(scip) > 0 )
2816 	   {
2817 	      /* first globally propagate new cutoff bound or pseudo objective activity */
2818 	      SCIP_CALL( propagateCutoffboundGlobally(scip, prop, &nchgbds, &cutoff) );
2819 	
2820 	      if( cutoff )
2821 	      {
2822 	         /* we are done with solving since a global pseudo activity is greater or equal to the cutoff bound */
2823 	         SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
2824 	
2825 	         (*result) = SCIP_CUTOFF;
2826 	         return SCIP_OKAY;
2827 	      }
2828 	
2829 	      /* check if the global propagation cut off the active/current node */
2830 	      if( SCIPgetCutoffdepth(scip) <= SCIPgetDepth(scip) )
2831 	      {
2832 	         (*result) = SCIP_CUTOFF;
2833 	         return SCIP_OKAY;
2834 	      }
2835 	   }
2836 	
2837 	   /* check if the pseudo objective value (minimum activity of the objective function) is greater or equal to the cutoff
2838 	    * bound
2839 	    */
2840 	   if( SCIPisGE(scip, pseudoobjval, cutoffbound) )
2841 	   {
2842 	      SCIPdebugMsg(scip, "pseudo objective value <%g> exceeds cutoff bound <%g>\n", pseudoobjval, cutoffbound);
2843 	
2844 	      /* check if conflict analysis is applicable */
2845 	      if( SCIPisConflictAnalysisApplicable(scip) )
2846 	      {
2847 	         assert(SCIPgetDepth(scip) > 0);
2848 	
2849 	         /* initialize conflict analysis */
2850 	         SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, TRUE) );
2851 	
2852 	         /* add all variable whose best bound changes increased the pseudo objective value above the cutoff bound */
2853 	         SCIP_CALL( resolvePropagation(scip, propdata, cutoffbound, NULL, -1, SCIP_BOUNDTYPE_UPPER, NULL) );
2854 	
2855 	         /* analyze the conflict */
2856 	         SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
2857 	      }
2858 	      (*result) = SCIP_CUTOFF;
2859 	
2860 	      return SCIP_OKAY;
2861 	   }
2862 	
2863 	   SCIPdebugMsg(scip, "propagating pseudo objective function (pseudoobj: %g, cutoffbound: %g)\n", pseudoobjval, cutoffbound);
2864 	
2865 	   /* propagate binary variables */
2866 	   SCIP_CALL( propagateCutoffboundBinvars(scip, prop, cutoffbound, pseudoobjval, &nchgbds, &cutoff) );
2867 	
2868 	   if( cutoff )
2869 	   {
2870 	      (*result) = SCIP_CUTOFF;
2871 	      return SCIP_OKAY;
2872 	   }
2873 	
2874 	   /* tighten domains of non-binary variables, if they would increase the pseudo objective value above the cutoff
2875 	    * bound
2876 	    */
2877 	   if( propdata->propfullinroot && SCIPgetDepth(scip) == 0 )
2878 	   {
2879 	      SCIP_VAR** objintvars;
2880 	      SCIP_VAR* var;
2881 	      SCIP_Real objval;
2882 	      int nobjintvars;
2883 	      int v;
2884 	
2885 	      objintvars = propdata->objintvars;
2886 	      nobjintvars = propdata->nobjintvars;
2887 	      assert(nobjintvars == 0 || objintvars != NULL);
2888 	
2889 	      /* propagate all non-binary variables */
2890 	      for( v = 0; v < nobjintvars; ++v )
2891 	      {
2892 	         var = objintvars[v];
2893 	         assert(var != NULL);
2894 	
2895 	         objval = SCIPvarGetObj(var);
2896 	         assert(!SCIPisZero(scip, objval));
2897 	
2898 	         /* try to tighten the bound of the variable */
2899 	         SCIP_CALL( propagateCutoffboundVar(scip, NULL, var, -1, objval, cutoffbound, pseudoobjval, FALSE, &tightened) );
2900 	
2901 	         /* check if the domain of the variable was reduced */
2902 	         if( tightened )
2903 	            nchgbds++;
2904 	      }
2905 	   }
2906 	   else
2907 	   {
2908 	      SCIP_VAR** objintvars;
2909 	      SCIP_VAR* var;
2910 	      SCIP_Real objval;
2911 	      int nobjintvars;
2912 	      int nmaxuseless;
2913 	      int nuseless;
2914 	      int c;
2915 	      int v;
2916 	
2917 	      objintvars = propdata->objintvars;
2918 	      nobjintvars = propdata->nobjintvars;
2919 	      assert(nobjintvars == 0 || objintvars != NULL);
2920 	
2921 	      /* compute maximum number of useless propagations before aborting */
2922 	      nmaxuseless = MAX(propdata->minuseless, (int)propdata->maxvarsfrac*(nobjintvars));
2923 	
2924 	      nuseless = 0;
2925 	      v = propdata->lastvarnum;
2926 	
2927 	      for( c = 0; c < nobjintvars && nuseless < nmaxuseless; ++c )
2928 	      {
2929 	         v++;
2930 	         if( v >= nobjintvars )
2931 	            v = 0;
2932 	
2933 	         var = objintvars[v];
2934 	         assert(var != NULL);
2935 	
2936 	         objval = SCIPvarGetObj(var);
2937 	         assert(!SCIPisZero(scip, objval));
2938 	
2939 	         /* try to tighten the bound of the variable */
2940 	         SCIP_CALL( propagateCutoffboundVar(scip, prop, var, -1, objval, cutoffbound, pseudoobjval, TRUE, &tightened) );
2941 	
2942 	         /* check if the domain of the variable was reduced */
2943 	         if( tightened )
2944 	            nchgbds++;
2945 	         else
2946 	            nuseless++;
2947 	      }
2948 	      propdata->lastvarnum = v;
2949 	   }
2950 	
2951 	   /* check if we chanced bounds */
2952 	   if( nchgbds > 0 )
2953 	      (*result) = SCIP_REDUCEDDOM;
2954 	
2955 	   return SCIP_OKAY;
2956 	}
2957 	
2958 	/** recalculates the maximum objective pseudoactivity */
2959 	static
2960 	void calcMaxObjPseudoactivity(
2961 	   SCIP*                 scip,               /**< SCIP data structure */
2962 	   SCIP_PROPDATA*        propdata            /**< propagator data */
2963 	   )
2964 	{
2965 	   SCIP_VAR** vars;
2966 	   SCIP_Real objval;
2967 	   SCIP_Real contrib;
2968 	   int nvars;
2969 	   int v;
2970 	
2971 	   assert(propdata != NULL);
2972 	
2973 	   /* get problem variables */
2974 	   vars = SCIPgetVars(scip);
2975 	   nvars = SCIPgetNVars(scip);
2976 	
2977 	   /* calculate current max pseudo activity and largest contribution */
2978 	   propdata->maxpseudoobjact = 0.0;
2979 	   propdata->maxpseudoobjactinf = 0;
2980 	
2981 	   for( v = 0; v < nvars; ++v )
2982 	   {
2983 	      objval = SCIPvarGetObj(vars[v]);
2984 	      if( SCIPisPositive(scip, objval) )
2985 	      {
2986 	         contrib = SCIPvarGetUbGlobal(vars[v]);
2987 	         if( !SCIPisInfinity(scip, contrib) )
2988 	            contrib *= objval;
2989 	      }
2990 	      else if( SCIPisNegative(scip, objval) )
2991 	      {
2992 	         contrib = SCIPvarGetLbGlobal(vars[v]);
2993 	         if( !SCIPisInfinity(scip, -contrib) )
2994 	            contrib *= objval;
2995 	         else
2996 	            contrib *= -1.0;
2997 	      }
2998 	      else
2999 	         continue;
3000 	
3001 	      if( SCIPisInfinity(scip, contrib) )
3002 	         propdata->maxpseudoobjactinf++;
3003 	      else
3004 	         propdata->maxpseudoobjact += contrib;
3005 	   }
3006 	}
3007 	
3008 	/** updates the pseudo objective activity if necessary */
3009 	static
3010 	void updateMaxObjPseudoactivity(
3011 	   SCIP*                 scip,               /**< SCIP data structure */
3012 	   SCIP_PROPDATA*        propdata            /**< propagator data */
3013 	   )
3014 	{
3015 	   assert(propdata != NULL);
3016 	
3017 	   /* if necessary, calculate the maximum pseudo objective activity */
3018 	   if( propdata->maxpseudoobjact == SCIP_INVALID ) /*lint !e777*/
3019 	      calcMaxObjPseudoactivity(scip, propdata);
3020 	   assert(propdata->maxpseudoobjact != SCIP_INVALID); /*lint !e777*/
3021 	}
3022 	
3023 	/** returns the residual pseudo objective activity without the given value */
3024 	static
3025 	SCIP_Real getMaxObjPseudoactivityResidualValue(
3026 	   SCIP*                 scip,               /**< SCIP data structure */
3027 	   SCIP_PROPDATA*        propdata,           /**< propagator data */
3028 	   SCIP_Real             contrib             /**< value to eliminate from pseudo objective activity */
3029 	   )
3030 	{
3031 	   SCIP_Real residual;
3032 	
3033 	   assert(propdata != NULL);
3034 	
3035 	   /* if necessary, calculate the maximum pseudo objective activity */
3036 	   if( propdata->maxpseudoobjact == SCIP_INVALID ) /*lint !e777*/
3037 	      calcMaxObjPseudoactivity(scip, propdata);
3038 	   assert(propdata->maxpseudoobjact != SCIP_INVALID); /*lint !e777*/
3039 	
3040 	   if( SCIPisInfinity(scip, contrib) )
3041 	   {
3042 	      assert(propdata->maxpseudoobjactinf >= 1);
3043 	      /* check if this variable yields the only infinite contribution */
3044 	      if( propdata->maxpseudoobjactinf == 1 )
3045 	         residual = propdata->maxpseudoobjact;
3046 	      else
3047 	         residual = SCIPinfinity(scip);
3048 	   }
3049 	   else
3050 	   {
3051 	      /* check if there is an infinite contribution */
3052 	      if( propdata->maxpseudoobjactinf >= 1 )
3053 	         residual = SCIPinfinity(scip);
3054 	      else
3055 	         residual = propdata->maxpseudoobjact - contrib;
3056 	   }
3057 	
3058 	   return residual;
3059 	}
3060 	
3061 	/** returns the residual pseudo objective activity */
3062 	static
3063 	SCIP_Real getMaxObjPseudoactivityResidual(
3064 	   SCIP*                 scip,               /**< SCIP data structure */
3065 	   SCIP_PROPDATA*        propdata,           /**< propagator data */
3066 	   SCIP_VAR*             var                 /**< variable to get residual activity for */
3067 	   )
3068 	{
3069 	   SCIP_Real objval;
3070 	   SCIP_Real contrib;
3071 	
3072 	   assert(propdata != NULL);
3073 	
3074 	   objval = SCIPvarGetObj(var);
3075 	   if( SCIPvarGetWorstBoundType(var) == SCIP_BOUNDTYPE_UPPER )
3076 	   {
3077 	      contrib = SCIPvarGetUbGlobal(var);
3078 	      if( !SCIPisInfinity(scip, contrib) )
3079 	         contrib *= objval;
3080 	   }
3081 	   else
3082 	   {
3083 	      assert(SCIPvarGetWorstBoundType(var) == SCIP_BOUNDTYPE_LOWER);
3084 	      contrib = SCIPvarGetLbGlobal(var);
3085 	      if( !SCIPisInfinity(scip, -contrib) )
3086 	         contrib *= objval;
3087 	      else
3088 	         contrib *= -1.0;
3089 	   }
3090 	
3091 	   return getMaxObjPseudoactivityResidualValue(scip, propdata, contrib);
3092 	}
3093 	
3094 	/** returns the maximum pseudo objective activity of the objective function */
3095 	static
3096 	SCIP_Real getMaxObjPseudoactivity(
3097 	   SCIP*                 scip,               /**< SCIP data structure */
3098 	   SCIP_PROPDATA*        propdata            /**< propagator data */
3099 	   )
3100 	{
3101 	   return getMaxObjPseudoactivityResidualValue(scip, propdata, 0.0);
3102 	}
3103 	
3104 	/** propagates the global domain of the given binary variable against the lower bound (c*x >= lowerbound) */
3105 	static
3106 	SCIP_RETCODE propagateLowerboundBinvar(
3107 	   SCIP*                 scip,               /**< SCIP data structure */
3108 	   SCIP_VAR*             var,                /**< variable to propagate */
3109 	   SCIP_Real             lowerbound,         /**< lower bound to use */
3110 	   SCIP_Real             maxpseudoobjact,    /**< maximum pseudo objective activity */
3111 	   SCIP_Bool             useimplics,         /**< should implications be used */
3112 	   SCIP_Bool*            infeasible,         /**< pointer to store if the variable domain got empty, infeasible */
3113 	   SCIP_Bool*            tightened           /**< pointer to store if the variable domain was tightened */
3114 	   )
3115 	{
3116 	   SCIP_Real lbobjchg;
3117 	   SCIP_Real ubobjchg;
3118 	
3119 	   assert(SCIPvarIsBinary(var));
3120 	   assert(SCIPisDualfeasLE(scip, lowerbound, maxpseudoobjact));
3121 	   assert(!SCIPisInfinity(scip, maxpseudoobjact));
3122 	
3123 	   /*@todo Instead of running always over all implications use SCIP_OBJIMPLICS in the same way as for the propagation of
3124 	    *      the minimum activity against the cutoff bound. If so we could use the cliques as well.
3125 	    */
3126 	
3127 	   /* get contribution of variable by fixing it to its lower bound w.r.t. maximum activity of the objective function */
3128 	   SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, useimplics, &lbobjchg) );
3129 	   assert(!SCIPisPositive(scip, lbobjchg));
3130 	
3131 	   /* get contribution of variable by fixing it to its upper bound w.r.t. maximum activity of the objective function */
3132 	   SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, useimplics, &ubobjchg) );
3133 	   assert(!SCIPisPositive(scip, ubobjchg));
3134 	
3135 	   (*infeasible) = FALSE;
3136 	   (*tightened) = FALSE;
3137 	
3138 	   /* if the maximum activity of the objective function without the contribution of the given variable shrinks below the
3139 	    * global lower bound, the contribution of the variable is need; hence, we can fix it to corresponding bound globally
3140 	    */
3141 	   if( SCIPisFeasLT(scip, maxpseudoobjact + lbobjchg, lowerbound) && SCIPisFeasLT(scip, maxpseudoobjact + ubobjchg, lowerbound) )
3142 	   {
3143 	      /* fixing the variable to zero or one leads to decreases of the maximum activity below the lower bound, hence, we
3144 	       * detected an cutoff
3145 	       */
3146 	      (*infeasible) = TRUE;
3147 	   }
3148 	   else if( SCIPisFeasLT(scip, maxpseudoobjact + lbobjchg, lowerbound) )
3149 	   {
3150 	      SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 1.0, FALSE, infeasible, tightened) );
3151 	   }
3152 	   else if( SCIPisFeasLT(scip, maxpseudoobjact + ubobjchg, lowerbound) )
3153 	   {
3154 	      SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 0.0, FALSE, infeasible, tightened) );
3155 	   }
3156 	
3157 	   return SCIP_OKAY;
3158 	}
3159 	
3160 	/** propagates the global domains of the given variable with non-zero objective coefficient against the lower bound
3161 	 *  (c*x >= lowerbound)
3162 	 */
3163 	static
3164 	SCIP_RETCODE propagateLowerboundVar(
3165 	   SCIP*                 scip,               /**< SCIP data structure */
3166 	   SCIP_PROPDATA*        propdata,           /**< propagator data */
3167 	   SCIP_VAR*             var,                /**< variable to propagate */
3168 	   SCIP_Real             lowerbound,         /**< lower bound to use */
3169 	   SCIP_Bool*            infeasible,         /**< pointer to store if the variable domain got empty, infeasible */
3170 	   SCIP_Bool*            tightened           /**< pointer to store if the variable domain was tightened */
3171 	   )
3172 	{
3173 	   SCIP_Real residual;
3174 	   SCIP_Real newbd;
3175 	   SCIP_Real objval;
3176 	
3177 	   objval = SCIPvarGetObj(var);
3178 	   assert(!SCIPisZero(scip, objval));
3179 	
3180 	   (*tightened) = FALSE;
3181 	
3182 	   /* get residual pseudo objective activity, that is the pseudo objective activity without the given variable */
3183 	   residual = getMaxObjPseudoactivityResidual(scip, propdata, var);
3184 	
3185 	   if( SCIPisInfinity(scip, residual) )
3186 	      return SCIP_OKAY;
3187 	
3188 	   /* compute potential mew bound */
3189 	   newbd = (lowerbound - residual) / objval;
3190 	
3191 	   /**@note In case the variable is integral we force the update of the new bound */
3192 	
3193 	   if( objval > 0.0 )
3194 	   {
3195 	      SCIP_Real lb;
3196 	
3197 	      lb = SCIPvarGetLbGlobal(var);
3198 	
3199 	      if( !SCIPvarIsIntegral(var) )
3200 	      {
3201 	         SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
3202 	      }
3203 	      else if( SCIPisFeasGT(scip, newbd, lb) )
3204 	      {
3205 	         SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, TRUE, infeasible, tightened) );
3206 	      }
3207 	   }
3208 	   else
3209 	   {
3210 	      SCIP_Real ub;
3211 	
3212 	      ub = SCIPvarGetUbGlobal(var);
3213 	
3214 	      if( !SCIPvarIsIntegral(var) )
3215 	      {
3216 	         SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
3217 	      }
3218 	      else if( SCIPisFeasLT(scip, newbd, ub) )
3219 	      {
3220 	         SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, TRUE, infeasible, tightened) );
3221 	      }
3222 	   }
3223 	
3224 	   return SCIP_OKAY;
3225 	}
3226 	
3227 	/** propagates the global lower (dual) bound c*x >= lowerbound */
3228 	static
3229 	SCIP_RETCODE propagateLowerbound(
3230 	   SCIP*                 scip,               /**< SCIP data structure */
3231 	   SCIP_PROP*            prop,               /**< propagator */
3232 	   SCIP_RESULT*          result              /**< pointer to store the result of the callback method */
3233 	   )
3234 	{  /*lint --e{715}*/
3235 	   SCIP_PROPDATA* propdata;
3236 	   SCIP_Real lowerbound;
3237 	   SCIP_Real maxpseudoobjact;
3238 	   SCIP_Bool cutoff;
3239 	   int nchgbds;
3240 	
3241 	   assert(result != NULL);
3242 	
3243 	   (*result) = SCIP_DIDNOTRUN;
3244 	   cutoff = FALSE;
3245 	   nchgbds = 0;
3246 	
3247 	   propdata = SCIPpropGetData(prop);
3248 	   assert(propdata != NULL);
3249 	   assert(propdata->nminactvars > 0 || propdata->nobjintvars > 0);
3250 	
3251 	   /* check if there is a chance to find a reduction */
3252 	   lowerbound = SCIPgetLowerbound(scip);
3253 	
3254 	   if( SCIPisInfinity(scip, -lowerbound) )
3255 	      return SCIP_OKAY;
3256 	
3257 	   /* if the lower bound did not change since the last propagation as well as the global bounds of the variables with a
3258 	    * non-zero objective coefficient we do nothing since there is no new information available
3259 	    */
3260 	   if( SCIPisLE(scip, lowerbound, propdata->lastlowerbound) && propdata->maxpseudoobjact < SCIP_INVALID )
3261 	      return SCIP_OKAY;
3262 	
3263 	   /* updates the pseudo objective activity if necessary */
3264 	   updateMaxObjPseudoactivity(scip, propdata);
3265 	
3266 	   /* if more than one variable contributes an infinity to the maximal pseudo activity we can do nothing */
3267 	   assert(propdata->maxpseudoobjact < SCIP_INVALID);
3268 	   if( propdata->maxpseudoobjactinf > 1 )
3269 	      return SCIP_OKAY;
3270 	
3271 	   maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata);
3272 	   assert(!SCIPisInfinity(scip, maxpseudoobjact) || !SCIPisInfinity(scip, lowerbound));
3273 	
3274 	#ifndef NDEBUG
3275 	   /* check that the global indices are correct */
3276 	   checkGlbfirstnonfixed(propdata);
3277 	#endif
3278 	
3279 	   /* if the maximum pseudo objective activity is smaller than the lower bound the problem is infeasible */
3280 	   if( SCIPisDualfeasLT(scip, maxpseudoobjact, lowerbound) )
3281 	      cutoff = TRUE;
3282 	   else
3283 	   {
3284 	      SCIP_VAR** objintvars;
3285 	      SCIP_VAR* var;
3286 	      SCIP_Bool tightened;
3287 	      int nobjintvars;
3288 	      int v;
3289 	
3290 	      if( propdata->maxpseudoobjactinf == 0 && !SCIPisInfinity(scip, maxpseudoobjact) )
3291 	      {
3292 	         SCIP_VAR** maxactvars;
3293 	         int nmaxactvars;
3294 	
3295 	         maxactvars = propdata->maxactvars;
3296 	         nmaxactvars = propdata->nmaxactvars;
3297 	         assert(nmaxactvars == 0 || maxactvars != NULL);
3298 	
3299 	         for( v = propdata->maxactfirstnonfixed; v < nmaxactvars; ++v )
3300 	         {
3301 	            var = maxactvars[v];
3302 	            assert(var != NULL);
3303 	            assert(SCIPvarIsBinary(var));
3304 	
3305 	            /* check if the variables is already globally fixed; if so continue with the next potential candidate */
3306 	            if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
3307 	               continue;
3308 	
3309 	            /* try to propagate variable domain globally */
3310 	            SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) );
3311 	
3312 	            /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective
3313 	             * contribution w.r.t. maximum activity of the objective function; These values are the decrease we would
3314 	             * get with the maximum pseudo objective activity if we fix the variable to its best bound; hence, we can
3315 	             * stop if for a variable this potential decrease is not enough anymore to fall below the lower bound.
3316 	             *
3317 	             * @note In case a fixing was performed. The variable might not be globally fixed right away since this would
3318 	             *       destroy the local internal data structure of a search node; the bound change is in that case pending;
3319 	             *       hence we cannot assert that the variable is globally fixed
3320 	             */
3321 	            if( !tightened )
3322 	            {
3323 	               assert(!SCIPisInfinity(scip, propdata->maxpseudoobjact));
3324 	               SCIPdebugMsg(scip, "interrupt pseudo objective propagation w.r.t. lower bound <%.15g> for binary variables after %d from %d binary variables\n",
3325 	                  lowerbound, v, nmaxactvars);
3326 	               break;
3327 	            }
3328 	
3329 	            if( cutoff )
3330 	               break;
3331 	
3332 	            /* update maximum pseudo activity since the previous global bound change might invalidated the maximum
3333 	             * pseudo activity
3334 	             */
3335 	            maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata);
3336 	            nchgbds++;
3337 	         }
3338 	
3339 	         /* update globally fixed index if abort criteria was applied */
3340 	         propdata->maxactfirstnonfixed = v;
3341 	
3342 	         /* check all binary variables which could potentially be fixed */
3343 	         for( ; v < nmaxactvars && maxpseudoobjact - lowerbound < propdata->maxactchgs[v] && !cutoff; ++v )
3344 	         {
3345 	            var =  maxactvars[v];
3346 	            assert(var != NULL);
3347 	            assert(SCIPvarIsBinary(var));
3348 	
3349 	            /* check if the variables is already globally fixed; if so continue with the potential candidate */
3350 	            if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
3351 	               continue;
3352 	
3353 	            /* propagates the cutoff bound for the given binary variable */
3354 	            SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) );
3355 	
3356 	            if( tightened )
3357 	            {
3358 	               /* update maximum pseudo activity since the previous global bound change might invalidated the maximum
3359 	                * pseudo activity
3360 	                */
3361 	               maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata);
3362 	               nchgbds++;
3363 	            }
3364 	         }
3365 	
3366 	#if 0 /* might fail, but is not a real error, still need to investigate */
3367 	#ifndef NDEBUG
3368 	         /* check that the abort criteria for the binary variables works */
3369 	         for( ; v < nmaxactvars && !cutoff; ++v )
3370 	         {
3371 	            var = maxactvars[v];
3372 	            assert(var != NULL);
3373 	            assert(SCIPvarIsBinary(var));
3374 	
3375 	            /* check if the variables is already globally fixed; if so continue with the next potential candidate */
3376 	            if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
3377 	               continue;
3378 	
3379 	            /* try to propagate variable domain globally */
3380 	            SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) );
3381 	            assert(!tightened);
3382 	            assert(!cutoff);
3383 	         }
3384 	#endif
3385 	#endif
3386 	      }
3387 	
3388 	      objintvars = propdata->objintvars;
3389 	      nobjintvars = propdata->nobjintvars;
3390 	      assert(nobjintvars == 0 || objintvars != NULL);
3391 	
3392 	      /* propagate c*x >= lowerbound for non-binary variables */
3393 	      for( v = 0; v < nobjintvars && !cutoff; ++v )
3394 	      {
3395 	         var = objintvars[v];
3396 	         assert(var != NULL);
3397 	         assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
3398 	
3399 	         /* try to propagate variable domain globally */
3400 	         SCIP_CALL( propagateLowerboundVar(scip, propdata, var, lowerbound, &cutoff, &tightened) );
3401 	
3402 	         if( tightened )
3403 	            nchgbds++;
3404 	      }
3405 	   }
3406 	
3407 	   /* evaluate propagation results */
3408 	   if( cutoff )
3409 	   {
3410 	      /* we are done with solving since a global bound change is infeasible: cutoff root node */
3411 	      SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
3412 	      (*result) = SCIP_CUTOFF;
3413 	   }
3414 	   else if( nchgbds > 0 )
3415 	      (*result) = SCIP_REDUCEDDOM;
3416 	
3417 	   /* remember the lower bound which we already propagated */
3418 	   propdata->lastlowerbound = lowerbound;
3419 	
3420 	   return SCIP_OKAY;
3421 	}
3422 	
3423 	
3424 	/*
3425 	 * Callback methods of propagator
3426 	 */
3427 	
3428 	/** copy method for propagator plugins (called when SCIP copies plugins) */
3429 	static
3430 	SCIP_DECL_PROPCOPY(propCopyPseudoobj)
3431 	{  /*lint --e{715}*/
3432 	   assert(scip != NULL);
3433 	   assert(prop != NULL);
3434 	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
3435 	
3436 	   /* call inclusion method of propagator */
3437 	   SCIP_CALL( SCIPincludePropPseudoobj(scip) );
3438 	
3439 	   return SCIP_OKAY;
3440 	}
3441 	
3442 	/** destructor of propagator to free user data (called when SCIP is exiting) */
3443 	static
3444 	SCIP_DECL_PROPFREE(propFreePseudoobj)
3445 	{  /*lint --e{715}*/
3446 	   SCIP_PROPDATA* propdata;
3447 	
3448 	   /* free propagator data */
3449 	   propdata = SCIPpropGetData(prop);
3450 	   SCIPfreeBlockMemory(scip, &propdata);
3451 	   SCIPpropSetData(prop, NULL);
3452 	
3453 	   return SCIP_OKAY;
3454 	}
3455 	
3456 	
3457 	/** solving process initialization method of propagator (called when branch and bound process is about to begin) */
3458 	static
3459 	SCIP_DECL_PROPINITSOL(propInitsolPseudoobj)
3460 	{
3461 	   SCIP_PROPDATA* propdata;
3462 	
3463 	   propdata = SCIPpropGetData(prop);
3464 	   assert(propdata != NULL);
3465 	
3466 	   /* do nothing if active pricer are present and force flag is not TRUE */
3467 	   if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
3468 	      return SCIP_OKAY;
3469 	
3470 	   /* if active pricer are present we want to catch the variable added event */
3471 	   if( SCIPgetNActivePricers(scip) > 0 )
3472 	   {
3473 	      assert(!propdata->catchvaradded);
3474 	      SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_VARADDED, propdata->eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
3475 	      propdata->catchvaradded = TRUE;
3476 	   }
3477 	
3478 	   return SCIP_OKAY;
3479 	}
3480 	
3481 	/** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
3482 	static
3483 	SCIP_DECL_PROPEXITSOL(propExitsolPseudoobj)
3484 	{  /*lint --e{715}*/
3485 	   SCIP_PROPDATA* propdata;
3486 	
3487 	   propdata = SCIPpropGetData(prop);
3488 	   assert(propdata != NULL);
3489 	
3490 	   if( propdata->catchvaradded )
3491 	   {
3492 	      /* drop the variable added event */
3493 	      SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_VARADDED, propdata->eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
3494 	      propdata->catchvaradded = FALSE;
3495 	   }
3496 	
3497 	   /* free propagator data */
3498 	   SCIP_CALL( propdataExit(scip, propdata) );
3499 	
3500 	   return SCIP_OKAY;
3501 	}
3502 	
3503 	
3504 	/** presolving method of propagator */
3505 	static
3506 	SCIP_DECL_PROPPRESOL(propPresolPseudoobj)
3507 	{  /*lint --e{715}*/
3508 	   SCIP_PROPDATA* propdata;
3509 	   SCIP_VAR** vars;
3510 	   SCIP_Real cutoffbound;
3511 	   SCIP_Real pseudoobjval;
3512 	   int oldnchgbds;
3513 	   int nvars;
3514 	   int v;
3515 	
3516 	   assert(result != NULL);
3517 	
3518 	   propdata = SCIPpropGetData(prop);
3519 	   assert(propdata != NULL);
3520 	
3521 	   (*result) = SCIP_DIDNOTRUN;
3522 	
3523 	   /* do nothing if active pricer are present and force flag is not TRUE */
3524 	   if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
3525 	      return SCIP_OKAY;
3526 	
3527 	   /* do nothing if objective propagation is not allowed */
3528 	   if( !SCIPallowWeakDualReds(scip) )
3529 	      return SCIP_OKAY;
3530 	
3531 	   pseudoobjval = SCIPgetGlobalPseudoObjval(scip);
3532 	   if( SCIPisInfinity(scip, -pseudoobjval) )
3533 	      return SCIP_OKAY;
3534 	
3535 	   cutoffbound = SCIPgetCutoffbound(scip);
3536 	   if( SCIPisInfinity(scip, cutoffbound) )
3537 	      return SCIP_OKAY;
3538 	
3539 	   if( SCIPisGE(scip, pseudoobjval, cutoffbound) )
3540 	   {
3541 	      (*result) = SCIP_CUTOFF;
3542 	      return SCIP_OKAY;
3543 	   }
3544 	
3545 	   /* only propagate if a new cutoff bound or global pseudo objective value is available */
3546 	   if( cutoffbound < propdata->cutoffbound || pseudoobjval > propdata->glbpseudoobjval )
3547 	   {
3548 	      SCIP_Real objval;
3549 	      SCIP_Bool tightened;
3550 	
3551 	      (*result) = SCIP_DIDNOTFIND;
3552 	      oldnchgbds = *nchgbds;
3553 	
3554 	      /* get the problem variables */
3555 	      vars = SCIPgetVars(scip);
3556 	      nvars = SCIPgetNVars(scip);
3557 	
3558 	      /* scan the variables for pseudoobj bound reductions
3559 	       * (loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array)
3560 	       */
3561 	      for( v = nvars - 1; v >= 0; --v )
3562 	      {
3563 	         objval = SCIPvarGetObj(vars[v]);
3564 	
3565 	         if( SCIPisZero(scip, objval) )
3566 	            continue;
3567 	
3568 	         SCIP_CALL( propagateCutoffboundVar(scip, NULL, vars[v], -1, objval, cutoffbound, pseudoobjval, FALSE, &tightened) );
3569 	
3570 	         if( tightened )
3571 	            (*nchgbds)++;
3572 	      }
3573 	
3574 	      /* evaluate if bound change was detected */
3575 	      if( *nchgbds > oldnchgbds )
3576 	         (*result) = SCIP_SUCCESS;
3577 	
3578 	      /* store the old values */
3579 	      propdata->cutoffbound = cutoffbound;
3580 	      propdata->glbpseudoobjval = pseudoobjval;
3581 	      propdata->glbpropagated = TRUE;
3582 	   }
3583 	
3584 	   return SCIP_OKAY;
3585 	}
3586 	
3587 	/** execution method of propagator */
3588 	static
3589 	SCIP_DECL_PROPEXEC(propExecPseudoobj)
3590 	{  /*lint --e{715}*/
3591 	   SCIP_PROPDATA* propdata;
3592 	
3593 	   propdata = SCIPpropGetData(prop);
3594 	   assert(propdata != NULL);
3595 	
3596 	   (*result) = SCIP_DIDNOTRUN;
3597 	
3598 	   if( SCIPinProbing(scip) )
3599 	      return SCIP_OKAY;
3600 	
3601 	   if( proptiming == SCIP_PROPTIMING_DURINGLPLOOP && SCIPgetDepth(scip) != 0 )
3602 	      return SCIP_OKAY;
3603 	
3604 	   /* do nothing if active pricer are present and force flag is not TRUE */
3605 	   if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
3606 	      return SCIP_OKAY;
3607 	
3608 	   /* do not run if propagation w.r.t. objective is not allowed */
3609 	   if( !SCIPallowWeakDualReds(scip) )
3610 	      return SCIP_OKAY;
3611 	
3612 	   /* check if enough new variable are added (due to column generation to reinitialized the propagator data) */
3613 	   if( !propdata->initialized || propdata->nnewvars > propdata->maxnewvars )
3614 	   {
3615 	      /* free current propdata data */
3616 	      SCIP_CALL( propdataExit(scip, propdata) );
3617 	
3618 	      /* initialize propdata data from scratch */
3619 	      SCIP_CALL( propdataInit(scip, propdata) );
3620 	   }
3621 	
3622 	   /* nothing to do for zero objective */
3623 	   if( propdata->nminactvars == 0 && propdata->nmaxactvars == 0 && propdata->nobjintvars == 0 )
3624 	      return SCIP_OKAY;
3625 	
3626 	   /* propagate c*x <= cutoff */
3627 	   SCIP_CALL( propagateCutoffbound(scip, prop, result) );
3628 	
3629 	   if( (*result) != SCIP_CUTOFF && (propdata->nmaxactvars > 0 || propdata->nobjintvars > 0) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
3630 	   {
3631 	      SCIP_RESULT dualresult;
3632 	
3633 	      /* propagates the global lower (dual) bound c*x >= lowerbound */
3634 	      SCIP_CALL( propagateLowerbound(scip, prop, &dualresult) );
3635 	
3636 	      if( dualresult == SCIP_REDUCEDDOM || dualresult == SCIP_CUTOFF )
3637 	         (*result) = dualresult;
3638 	   }
3639 	
3640 	   return SCIP_OKAY;
3641 	}
3642 	
3643 	/** propagation conflict resolving method of propagator */
3644 	static
3645 	SCIP_DECL_PROPRESPROP(propRespropPseudoobj)
3646 	{  /*lint --e{715}*/
3647 	   SCIP_PROPDATA* propdata;
3648 	   SCIP_Real cutoffbound;
3649 	
3650 	   assert(!SCIPisEQ(scip, SCIPvarGetLbGlobal(infervar), SCIPvarGetUbGlobal(infervar)));
3651 	
3652 	   propdata = SCIPpropGetData(prop);
3653 	   assert(propdata != NULL);
3654 	
3655 	   cutoffbound = SCIPgetCutoffbound(scip);
3656 	   assert(!SCIPisInfinity(scip, cutoffbound));
3657 	   assert(infervar != NULL);
3658 	
3659 	   SCIPdebugMsg(scip, "resolve bound change <%s> %s <%g>(%g), cutoff bound <%g>\n", SCIPvarGetName(infervar),
3660 	      boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE),
3661 	      SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, FALSE), cutoffbound);
3662 	
3663 	   /* resolve the propagation of the inference variable w.r.t. required minactivity */
3664 	   SCIP_CALL( resolvePropagation(scip, propdata, cutoffbound, infervar, inferinfo, boundtype, bdchgidx) );
3665 	
3666 	   (*result) = SCIP_SUCCESS;
3667 	
3668 	   return SCIP_OKAY;
3669 	}
3670 	
3671 	
3672 	/*
3673 	 * Event handler
3674 	 */
3675 	
3676 	/** execution method of bound change event handler */
3677 	static
3678 	SCIP_DECL_EVENTEXEC(eventExecPseudoobj)
3679 	{  /*lint --e{715}*/
3680 	   SCIP_PROPDATA* propdata;
3681 	   SCIP_EVENTTYPE eventtype;
3682 	
3683 	   propdata = (SCIP_PROPDATA*)eventdata;
3684 	   assert(propdata != NULL);
3685 	
3686 	   assert(eventhdlr != NULL);
3687 	   assert(eventdata != NULL);
3688 	   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
3689 	   assert(event != NULL);
3690 	
3691 	   eventtype = SCIPeventGetType(event);
3692 	
3693 	   switch( eventtype )
3694 	   {
3695 	   case SCIP_EVENTTYPE_LBRELAXED:
3696 	   case SCIP_EVENTTYPE_UBRELAXED:
3697 	      /* if bound got relaxed we need to start up front for trial of bound tightening */
3698 	      propdata->firstnonfixed = 0;
3699 	      break;
3700 	   case SCIP_EVENTTYPE_VARADDED:
3701 	      propdata->nnewvars++;
3702 	      break;
3703 	   default:
3704 	      assert(eventtype == SCIP_EVENTTYPE_GLBCHANGED || eventtype == SCIP_EVENTTYPE_GUBCHANGED);
3705 	
3706 	      /* invalidate the maximum pseudo objective activity */
3707 	      propdata->maxpseudoobjact = SCIP_INVALID;
3708 	      propdata->maxpseudoobjactinf = 0;
3709 	   }
3710 	
3711 	   return SCIP_OKAY;
3712 	}
3713 	
3714 	
3715 	/*
3716 	 * propagator specific interface methods
3717 	 */
3718 	
3719 	/** creates the pseudo objective function propagator and includes it in SCIP */
3720 	SCIP_RETCODE SCIPincludePropPseudoobj(
3721 	   SCIP*                 scip                /**< SCIP data structure */
3722 	   )
3723 	{
3724 	   SCIP_PROPDATA* propdata;
3725 	   SCIP_PROP* prop;
3726 	
3727 	   /* create pseudoobj propagator data */
3728 	   SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
3729 	
3730 	   /* reset propagator data structure */
3731 	   propdataReset(propdata);
3732 	
3733 	   propdata->eventhdlr = NULL;
3734 	   /* include event handler for gloabl bound change events and variable added event (in case of pricing) */
3735 	   SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3736 	         eventExecPseudoobj, NULL) );
3737 	
3738 	   if( propdata->eventhdlr == NULL )
3739 	   {
3740 	      SCIPerrorMessage("event handler for pseudo objective propagator not found\n");
3741 	      return SCIP_PLUGINNOTFOUND;
3742 	   }
3743 	
3744 	   /* include propagator */
3745 	   SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
3746 	         propExecPseudoobj,
3747 	         propdata) );
3748 	   assert(prop != NULL);
3749 	
3750 	   /* set optional callbacks via setter functions */
3751 	   SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyPseudoobj) );
3752 	   SCIP_CALL( SCIPsetPropFree(scip, prop, propFreePseudoobj) );
3753 	   SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolPseudoobj) );
3754 	   SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolPseudoobj) );
3755 	   SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolPseudoobj, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
3756 	   SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropPseudoobj) );
3757 	
3758 	   /* add pseudoobj propagator parameters */
3759 	   SCIP_CALL( SCIPaddIntParam(scip,
3760 	         "propagating/" PROP_NAME "/minuseless",
3761 	         "minimal number of successive non-binary variable propagations without a bound reduction before aborted",
3762 	         &propdata->minuseless, TRUE, DEFAULT_MINUSELESS, 0, INT_MAX, NULL, NULL) );
3763 	
3764 	   SCIP_CALL( SCIPaddRealParam(scip,
3765 	         "propagating/" PROP_NAME "/maxvarsfrac",
3766 	         "maximal fraction of non-binary variables with non-zero objective without a bound reduction before aborted",
3767 	         &propdata->maxvarsfrac, TRUE, DEFAULT_MAXVARSFRAC, 0.0, 1.0, NULL, NULL) );
3768 	
3769 	   SCIP_CALL( SCIPaddBoolParam(scip,
3770 	         "propagating/" PROP_NAME "/propfullinroot",
3771 	         "whether to propagate all non-binary variables when we are propagating the root node",
3772 	         &propdata->propfullinroot, TRUE, DEFAULT_PROPFULLINROOT, NULL, NULL) );
3773 	
3774 	   SCIP_CALL( SCIPaddBoolParam(scip,
3775 	         "propagating/" PROP_NAME "/propcutoffbound",
3776 	         "propagate new cutoff bound directly globally",
3777 	         &propdata->propcutoffbound, TRUE, DEFAULT_PROPCUTOFFBOUND, NULL, NULL) );
3778 	
3779 	   SCIP_CALL( SCIPaddBoolParam(scip,
3780 	         "propagating/" PROP_NAME "/force",
3781 	         "should the propagator be forced even if active pricer are present?",
3782 	         &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) );
3783 	
3784 	   SCIP_CALL( SCIPaddIntParam(scip,
3785 	         "propagating/" PROP_NAME "/maxnewvars",
3786 	         "number of variables added after the propagator is reinitialized?",
3787 	         &propdata->maxnewvars, TRUE, DEFAULT_MAXNEWVARS, 0, INT_MAX, NULL, NULL) );
3788 	
3789 	   SCIP_CALL( SCIPaddBoolParam(scip,
3790 	         "propagating/" PROP_NAME "/propuseimplics",
3791 	         "use implications to strengthen the propagation of binary variable (increasing the objective change)?",
3792 	         &propdata->propuseimplics, TRUE, DEFAULT_PROPUSEIMPLICS, NULL, NULL) );
3793 	
3794 	   SCIP_CALL( SCIPaddBoolParam(scip,
3795 	         "propagating/" PROP_NAME "/respropuseimplics",
3796 	         "use implications to strengthen the resolve propagation of binary variable (increasing the objective change)?",
3797 	         &propdata->respropuseimplics, TRUE, DEFAULT_RESPROPUSEIMPLICS, NULL, NULL) );
3798 	
3799 	   SCIP_CALL( SCIPaddIntParam(scip,
3800 	         "propagating/" PROP_NAME "/maximplvars",
3801 	         "maximum number of binary variables the implications are used if turned on (-1: unlimited)?",
3802 	         &propdata->maximplvars, TRUE, DEFAULT_MAXIMPLVARS, -1, INT_MAX, NULL, NULL) );
3803 	
3804 	   return SCIP_OKAY;
3805 	}
3806 	
3807 	/** propagates the cutoff bound for the given variables */
3808 	SCIP_RETCODE SCIPpropagateCutoffboundVar(
3809 	   SCIP*                 scip,               /**< SCIP data structure */
3810 	   SCIP_PROP*            prop,               /**< propagator, or NULL */
3811 	   SCIP_VAR*             var,                /**< variables to propagate */
3812 	   SCIP_Real             cutoffbound,        /**< cutoff bound to use */
3813 	   SCIP_Real             pseudoobjval,       /**< pseudo objective value to use */
3814 	   SCIP_Bool*            tightened           /**< pointer to if the domain was tightened */
3815 	   )
3816 	{
3817 	   SCIP_Real objval;
3818 	
3819 	   objval = SCIPvarGetObj(var);
3820 	
3821 	   SCIP_CALL( propagateCutoffboundVar(scip, prop, var, -1, objval, cutoffbound, pseudoobjval, TRUE, tightened) );
3822 	
3823 	   return SCIP_OKAY;
3824 	}
3825