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   branch.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  methods for branching rules and branching candidate storage
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 * @author Gerald Gamrath
31   	 * @author Stefan Heinz
32   	 * @author Michael Winkler
33   	 * @author Stefan Vigerske
34   	 */
35   	
36   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37   	
38   	#include <assert.h>
39   	#include <string.h>
40   	
41   	#include "scip/def.h"
42   	#include "blockmemshell/memory.h"
43   	#include "scip/set.h"
44   	#include "scip/stat.h"
45   	#include "scip/clock.h"
46   	#include "scip/paramset.h"
47   	#include "scip/event.h"
48   	#include "scip/lp.h"
49   	#include "scip/var.h"
50   	#include "scip/prob.h"
51   	#include "scip/tree.h"
52   	#include "scip/sepastore.h"
53   	#include "scip/scip.h"
54   	#include "scip/branch.h"
55   	#include "scip/solve.h"
56   	
57   	#include "scip/struct_branch.h"
58   	
59   	/*
60   	 * memory growing methods for dynamically allocated arrays
61   	 */
62   	
63   	/** ensures, that lpcands array can store at least num entries */
64   	static
65   	SCIP_RETCODE ensureLpcandsSize(
66   	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
67   	   SCIP_SET*             set,                /**< global SCIP settings */
68   	   int                   num                 /**< minimum number of entries to store */
69   	   )
70   	{
71   	   assert(branchcand->nlpcands <= branchcand->lpcandssize);
72   	
73   	   if( num > branchcand->lpcandssize )
74   	   {
75   	      int newsize;
76   	
77   	      newsize = SCIPsetCalcMemGrowSize(set, num);
78   	      SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcands, newsize) );
79   	      SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcandssol, newsize) );
80   	      SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcandsfrac, newsize) );
81   	      branchcand->lpcandssize = newsize;
82   	   }
83   	   assert(num <= branchcand->lpcandssize);
84   	
85   	   return SCIP_OKAY;
86   	}
87   	
88   	/** ensures, that pseudocands array can store at least num entries */
89   	static
90   	SCIP_RETCODE ensurePseudocandsSize(
91   	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
92   	   SCIP_SET*             set,                /**< global SCIP settings */
93   	   int                   num                 /**< minimum number of entries to store */
94   	   )
95   	{
96   	   assert(branchcand->npseudocands <= branchcand->pseudocandssize);
97   	
98   	   if( num > branchcand->pseudocandssize )
99   	   {
100  	      int newsize;
101  	
102  	      newsize = SCIPsetCalcMemGrowSize(set, num);
103  	      SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->pseudocands, newsize) );
104  	      branchcand->pseudocandssize = newsize;
105  	   }
106  	   assert(num <= branchcand->pseudocandssize);
107  	
108  	   return SCIP_OKAY;
109  	}
110  	
111  	/** ensures, that externcands array can store at least num entries */
112  	static
113  	SCIP_RETCODE ensureExterncandsSize(
114  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
115  	   SCIP_SET*             set,                /**< global SCIP settings */
116  	   int                   num                 /**< minimum number of entries to store */
117  	   )
118  	{
119  	   assert(branchcand->nexterncands <= branchcand->externcandssize);
120  	
121  	   if( num > branchcand->externcandssize )
122  	   {
123  	      int newsize;
124  	
125  	      newsize = SCIPsetCalcMemGrowSize(set, num);
126  	      SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcands, newsize) );
127  	      SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcandsscore, newsize) );
128  	      SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcandssol, newsize) );
129  	      branchcand->externcandssize = newsize;
130  	   }
131  	   assert(num <= branchcand->externcandssize);
132  	
133  	   return SCIP_OKAY;
134  	}
135  	
136  	
137  	
138  	/*
139  	 * branching candidate storage methods
140  	 */
141  	
142  	/** creates a branching candidate storage */
143  	SCIP_RETCODE SCIPbranchcandCreate(
144  	   SCIP_BRANCHCAND**     branchcand          /**< pointer to store branching candidate storage */
145  	   )
146  	{
147  	   assert(branchcand != NULL);
148  	
149  	   SCIP_ALLOC( BMSallocMemory(branchcand) );
150  	   (*branchcand)->lpcands = NULL;
151  	   (*branchcand)->lpcandssol = NULL;
152  	   (*branchcand)->lpcandsfrac = NULL;
153  	   (*branchcand)->externcands = NULL;
154  	   (*branchcand)->externcandssol = NULL;
155  	   (*branchcand)->externcandsscore = NULL;
156  	   (*branchcand)->pseudocands = NULL;
157  	   (*branchcand)->lpcandssize = 0;
158  	   (*branchcand)->nlpcands = 0;
159  	   (*branchcand)->nimpllpfracs = 0;
160  	   (*branchcand)->npriolpcands = 0;
161  	   (*branchcand)->npriolpbins = 0;
162  	   (*branchcand)->lpmaxpriority = INT_MIN;
163  	   (*branchcand)->externcandssize = 0;
164  	   (*branchcand)->nexterncands = 0;
165  	   (*branchcand)->nprioexterncands = 0;
166  	   (*branchcand)->nprioexternbins = 0;
167  	   (*branchcand)->nprioexternints = 0;
168  	   (*branchcand)->nprioexternimpls = 0;
169  	   (*branchcand)->externmaxpriority = INT_MIN;
170  	   (*branchcand)->pseudocandssize = 0;
171  	   (*branchcand)->npseudocands = 0;
172  	   (*branchcand)->npriopseudocands = 0;
173  	   (*branchcand)->npriopseudobins = 0;
174  	   (*branchcand)->npriopseudoints = 0;
175  	   (*branchcand)->pseudomaxpriority = INT_MIN;
176  	
177  	   SCIPbranchcandInvalidate(*branchcand);
178  	
179  	   return SCIP_OKAY;
180  	}
181  	
182  	/** frees branching candidate storage */
183  	SCIP_RETCODE SCIPbranchcandFree(
184  	   SCIP_BRANCHCAND**     branchcand          /**< pointer to store branching candidate storage */
185  	   )
186  	{
187  	   assert(branchcand != NULL);
188  	
189  	   BMSfreeMemoryArrayNull(&(*branchcand)->lpcands);
190  	   BMSfreeMemoryArrayNull(&(*branchcand)->lpcandssol);
191  	   BMSfreeMemoryArrayNull(&(*branchcand)->lpcandsfrac);
192  	   BMSfreeMemoryArrayNull(&(*branchcand)->pseudocands);
193  	   BMSfreeMemoryArrayNull(&(*branchcand)->externcands);
194  	   BMSfreeMemoryArrayNull(&(*branchcand)->externcandsscore);
195  	   BMSfreeMemoryArrayNull(&(*branchcand)->externcandssol);
196  	   BMSfreeMemory(branchcand);
197  	
198  	   return SCIP_OKAY;
199  	}
200  	
201  	/** resets branching candidates storage */
202  	void SCIPbranchcandInvalidate(
203  	   SCIP_BRANCHCAND*      branchcand          /**< pointer to store branching candidate storage */
204  	   )
205  	{
206  	   assert(branchcand != NULL);
207  	
208  	   branchcand->validlpcandslp = -1;
209  	}
210  	
211  	/** calculates branching candidates for LP solution branching (fractional variables) */
212  	static
213  	SCIP_RETCODE branchcandCalcLPCands(
214  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
215  	   SCIP_SET*             set,                /**< global SCIP settings */
216  	   SCIP_STAT*            stat,               /**< problem statistics */
217  	   SCIP_LP*              lp                  /**< current LP data */
218  	   )
219  	{
220  	   assert(branchcand != NULL);
221  	   assert(stat != NULL);
222  	   assert(branchcand->validlpcandslp <= stat->lpcount);
223  	   assert(lp != NULL);
224  	   assert(lp->solved);
225  	   assert(SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY);
226  	
227  	   SCIPsetDebugMsg(set, "calculating LP branching candidates: validlp=%" SCIP_LONGINT_FORMAT ", lpcount=%" SCIP_LONGINT_FORMAT "\n",
228  	      branchcand->validlpcandslp, stat->lpcount);
229  	
230  	   /* check, if the current LP branching candidate array is invalid */
231  	   if( branchcand->validlpcandslp < stat->lpcount )
232  	   {
233  	      SCIP_COL** cols;
234  	      SCIP_VAR* var;
235  	      SCIP_COL* col;
236  	      SCIP_Real primsol;
237  	      SCIP_Real frac;
238  	      SCIP_VARTYPE vartype;
239  	      int branchpriority;
240  	      int ncols;
241  	      int c;
242  	      int insertpos;
243  	
244  	      SCIPsetDebugMsg(set, " -> recalculating LP branching candidates\n");
245  	
246  	      cols = SCIPlpGetCols(lp);
247  	      ncols = SCIPlpGetNCols(lp);
248  	
249  	      /* construct the LP branching candidate set, moving the candidates with maximal priority to the front */
250  	      SCIP_CALL( ensureLpcandsSize(branchcand, set, ncols) );
251  	
252  	      branchcand->lpmaxpriority = INT_MIN / 2;
253  	      branchcand->nlpcands = 0;
254  	      branchcand->nimpllpfracs = 0;
255  	      branchcand->npriolpcands = 0;
256  	      branchcand->npriolpbins = 0;
257  	      for( c = 0; c < ncols; ++c )
258  	      {
259  	         col = cols[c];
260  	         assert(col != NULL);
261  	         assert(col->lppos == c);
262  	         assert(col->lpipos >= 0);
263  	
264  	         primsol = SCIPcolGetPrimsol(col);
265  	         assert(primsol != SCIP_INVALID);  /*lint !e777*/
266  	         assert(SCIPsetIsInfinity(set, -col->lb) || SCIPsetIsFeasGE(set, primsol, col->lb));
267  	         assert(SCIPsetIsInfinity(set, col->ub) || SCIPsetIsFeasLE(set, primsol, col->ub));
268  	
269  	         /* count values at infinity as integral */
270  	         if( SCIPsetIsInfinity(set, REALABS(primsol)) )
271  	            continue;
272  	
273  	         var = col->var;
274  	         assert(var != NULL);
275  	         assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
276  	         assert(SCIPvarGetCol(var) == col);
277  	
278  	         /* LP branching candidates are fractional binary and integer variables; implicit variables are kept at the end
279  	          * of the candidates array for some rounding heuristics
280  	          */
281  	         vartype = SCIPvarGetType(var);
282  	         if( vartype == SCIP_VARTYPE_CONTINUOUS )
283  	            continue;
284  	
285  	         /* ignore fixed variables (due to numerics, it is possible, that the LP solution of a fixed integer variable
286  	          * (with large fixed value) is fractional in terms of absolute feasibility measure)
287  	          */
288  	         if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
289  	            continue;
290  	
291  	         /* check, if the LP solution value is fractional */
292  	         frac = SCIPsetFeasFrac(set, primsol);
293  	
294  	         /* The fractionality should not be smaller than -feastol, however, if the primsol is large enough
295  	          * and close to an integer, fixed precision floating point arithmetic might give us values slightly
296  	          * smaller than -feastol. Originally, the "frac >= -feastol"-check was within SCIPsetIsFeasFracIntegral(),
297  	          * however, we relaxed it to "frac >= -2*feastol" and have the stricter check here for small-enough primsols.
298  	          */
299  	         assert(SCIPsetIsGE(set, frac, -SCIPsetFeastol(set)) || (primsol > 1e14 * SCIPsetFeastol(set)));
300  	
301  	         if( SCIPsetIsFeasFracIntegral(set, frac) )
302  	            continue;
303  	
304  	         /* insert candidate in candidate list */
305  	         branchpriority = SCIPvarGetBranchPriority(var);
306  	         insertpos = branchcand->nlpcands + branchcand->nimpllpfracs;
307  	         assert(insertpos < branchcand->lpcandssize);
308  	
309  	         if( vartype == SCIP_VARTYPE_IMPLINT )
310  	            branchpriority = INT_MIN;
311  	
312  	         assert(vartype == SCIP_VARTYPE_IMPLINT || branchpriority >= INT_MIN/2);
313  	         /* ensure that implicit variables are stored at the end of the array */
314  	         if( vartype != SCIP_VARTYPE_IMPLINT && branchcand->nimpllpfracs > 0 )
315  	         {
316  	            assert(branchcand->lpcands[branchcand->nlpcands] != NULL
317  	                  && SCIPvarGetType(branchcand->lpcands[branchcand->nlpcands]) == SCIP_VARTYPE_IMPLINT );
318  	
319  	            branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->nlpcands];
320  	            branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->nlpcands];
321  	            branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->nlpcands];
322  	
323  	            insertpos = branchcand->nlpcands;
324  	         }
325  	
326  	         if( branchpriority > branchcand->lpmaxpriority )
327  	         {
328  	            /* candidate has higher priority than the current maximum:
329  	             * move it to the front and declare it to be the single best candidate
330  	             */
331  	            if( insertpos != 0 )
332  	            {
333  	               branchcand->lpcands[insertpos] = branchcand->lpcands[0];
334  	               branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[0];
335  	               branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[0];
336  	               insertpos = 0;
337  	            }
338  	            branchcand->npriolpcands = 1;
339  	            branchcand->npriolpbins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0);
340  	            branchcand->lpmaxpriority = branchpriority;
341  	         }
342  	         else if( branchpriority == branchcand->lpmaxpriority )
343  	         {
344  	            /* candidate has equal priority as the current maximum:
345  	             * move away the first non-maximal priority candidate, move the current candidate to the correct
346  	             * slot (binaries first) and increase the number of maximal priority candidates
347  	             */
348  	            if( insertpos != branchcand->npriolpcands )
349  	            {
350  	               branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->npriolpcands];
351  	               branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->npriolpcands];
352  	               branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->npriolpcands];
353  	               insertpos = branchcand->npriolpcands;
354  	            }
355  	            branchcand->npriolpcands++;
356  	            if( vartype == SCIP_VARTYPE_BINARY )
357  	            {
358  	               if( insertpos != branchcand->npriolpbins )
359  	               {
360  	                  branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->npriolpbins];
361  	                  branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->npriolpbins];
362  	                  branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->npriolpbins];
363  	                  insertpos = branchcand->npriolpbins;
364  	               }
365  	               branchcand->npriolpbins++;
366  	            }
367  	         }
368  	         /* insert variable at the correct position of the candidates storage */
369  	         branchcand->lpcands[insertpos] = var;
370  	         branchcand->lpcandssol[insertpos] = primsol;
371  	         branchcand->lpcandsfrac[insertpos] = frac;
372  	
373  	         /* increase the counter depending on the variable type */
374  	         if( vartype != SCIP_VARTYPE_IMPLINT )
375  	            branchcand->nlpcands++;
376  	         else
377  	            branchcand->nimpllpfracs++;
378  	
379  	         SCIPsetDebugMsg(set, " -> candidate %d: var=<%s>, sol=%g, frac=%g, prio=%d (max: %d) -> pos %d\n",
380  	            branchcand->nlpcands, SCIPvarGetName(var), primsol, frac, branchpriority, branchcand->lpmaxpriority,
381  	            insertpos);
382  	      }
383  	
384  	#ifndef NDEBUG
385  	      /* in debug mode we assert that the variables are positioned correctly (binaries and integers first,
386  	       * implicit integers last)
387  	       */
388  	      for( c = 0; c < branchcand->nlpcands + branchcand->nimpllpfracs; ++c )
389  	      {
390  	         assert(c >= branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) != SCIP_VARTYPE_IMPLINT);
391  	         assert(c < branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) == SCIP_VARTYPE_IMPLINT);
392  	      }
393  	#endif
394  	
395  	      branchcand->validlpcandslp = stat->lpcount;
396  	   }
397  	   assert(0 <= branchcand->npriolpcands && branchcand->npriolpcands <= branchcand->nlpcands);
398  	
399  	   SCIPsetDebugMsg(set, " -> %d fractional variables (%d of maximal priority)\n", branchcand->nlpcands, branchcand->npriolpcands);
400  	
401  	   return SCIP_OKAY;
402  	}
403  	
404  	/** gets branching candidates for LP solution branching (fractional variables) */
405  	SCIP_RETCODE SCIPbranchcandGetLPCands(
406  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
407  	   SCIP_SET*             set,                /**< global SCIP settings */
408  	   SCIP_STAT*            stat,               /**< problem statistics */
409  	   SCIP_LP*              lp,                 /**< current LP data */
410  	   SCIP_VAR***           lpcands,            /**< pointer to store the array of LP branching candidates, or NULL */
411  	   SCIP_Real**           lpcandssol,         /**< pointer to store the array of LP candidate solution values, or NULL */
412  	   SCIP_Real**           lpcandsfrac,        /**< pointer to store the array of LP candidate fractionalities, or NULL */
413  	   int*                  nlpcands,           /**< pointer to store the number of LP branching candidates, or NULL */
414  	   int*                  npriolpcands,       /**< pointer to store the number of candidates with maximal priority, or NULL */
415  	   int*                  nfracimplvars       /**< pointer to store the number of implicit fractional variables, or NULL */
416  	   )
417  	{
418  	   /* calculate branching candidates */
419  	   SCIP_CALL( branchcandCalcLPCands(branchcand, set, stat, lp) );
420  	
421  	   /* assign return values */
422  	   if( lpcands != NULL )
423  	      *lpcands = branchcand->lpcands;
424  	   if( lpcandssol != NULL )
425  	      *lpcandssol = branchcand->lpcandssol;
426  	   if( lpcandsfrac != NULL )
427  	      *lpcandsfrac = branchcand->lpcandsfrac;
428  	   if( nlpcands != NULL )
429  	      *nlpcands = branchcand->nlpcands;
430  	   if( npriolpcands != NULL )
431  	      *npriolpcands = (set->branch_preferbinary && branchcand->npriolpbins > 0 ? branchcand->npriolpbins
432  	         : branchcand->npriolpcands);
433  	   if( nfracimplvars != NULL )
434  	      *nfracimplvars = branchcand->nimpllpfracs;
435  	
436  	   return SCIP_OKAY;
437  	}
438  	
439  	/** gets external branching candidates */
440  	SCIP_RETCODE SCIPbranchcandGetExternCands(
441  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
442  	   SCIP_VAR***           externcands,        /**< pointer to store the array of external branching candidates, or NULL */
443  	   SCIP_Real**           externcandssol,     /**< pointer to store the array of external candidate solution values, or NULL */
444  	   SCIP_Real**           externcandsscore,   /**< pointer to store the array of external candidate scores, or NULL */
445  	   int*                  nexterncands,       /**< pointer to store the number of external branching candidates, or NULL */
446  	   int*                  nprioexterncands,   /**< pointer to store the number of candidates with maximal priority, or NULL */
447  	   int*                  nprioexternbins,    /**< pointer to store the number of binary candidates with maximal priority, or NULL */
448  	   int*                  nprioexternints,    /**< pointer to store the number of integer candidates with maximal priority, or NULL */
449  	   int*                  nprioexternimpls    /**< pointer to store the number of implicit integer candidates with maximal priority, 
450  	                                              *   or NULL */
451  	   )
452  	{
453  	   assert(branchcand != NULL);
454  	
455  	   /* assign return values */
456  	   if( externcands != NULL )
457  	      *externcands = branchcand->externcands;
458  	   if( externcandssol != NULL )
459  	      *externcandssol = branchcand->externcandssol;
460  	   if( externcandsscore != NULL )
461  	      *externcandsscore = branchcand->externcandsscore;
462  	   if( nexterncands != NULL )
463  	      *nexterncands = branchcand->nexterncands;
464  	   if( nprioexterncands != NULL )
465  	      *nprioexterncands = branchcand->nprioexterncands;
466  	   if( nprioexternbins != NULL )
467  	      *nprioexternbins = branchcand->nprioexternbins;
468  	   if( nprioexternints != NULL )
469  	      *nprioexternints = branchcand->nprioexternints;
470  	   if( nprioexternimpls != NULL )
471  	      *nprioexternimpls = branchcand->nprioexternimpls;
472  	
473  	   return SCIP_OKAY;
474  	}
475  	
476  	/** gets maximal branching priority of LP branching candidates */
477  	int SCIPbranchcandGetLPMaxPrio(
478  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
479  	   )
480  	{
481  	   assert(branchcand != NULL);
482  	
483  	   return branchcand->lpmaxpriority;
484  	}
485  	
486  	/** gets number of LP branching candidates with maximal branch priority */
487  	int SCIPbranchcandGetNPrioLPCands(
488  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
489  	   )
490  	{
491  	   assert(branchcand != NULL);
492  	
493  	   return branchcand->npriolpcands;
494  	}
495  	
496  	/** gets maximal branching priority of external branching candidates */
497  	int SCIPbranchcandGetExternMaxPrio(
498  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
499  	   )
500  	{
501  	   assert(branchcand != NULL);
502  	
503  	   return branchcand->externmaxpriority;
504  	}
505  	
506  	/** gets number of external branching candidates */
507  	int SCIPbranchcandGetNExternCands(
508  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
509  	   )
510  	{
511  	   assert(branchcand != NULL);
512  	
513  	   return branchcand->nexterncands;
514  	}
515  	
516  	/** gets number of external branching candidates with maximal branch priority */
517  	int SCIPbranchcandGetNPrioExternCands(
518  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
519  	   )
520  	{
521  	   assert(branchcand != NULL);
522  	
523  	   return branchcand->nprioexterncands;
524  	}
525  	
526  	/** gets number of binary external branching candidates with maximal branch priority */
527  	int SCIPbranchcandGetNPrioExternBins(
528  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
529  	   )
530  	{
531  	   assert(branchcand != NULL);
532  	
533  	   return branchcand->nprioexternbins;
534  	}
535  	
536  	/** gets number of integer external branching candidates with maximal branch priority */
537  	int SCIPbranchcandGetNPrioExternInts(
538  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
539  	   )
540  	{
541  	   assert(branchcand != NULL);
542  	
543  	   return branchcand->nprioexternints;
544  	}
545  	
546  	/** gets number of implicit integer external branching candidates with maximal branch priority */
547  	int SCIPbranchcandGetNPrioExternImpls(
548  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
549  	   )
550  	{
551  	   assert(branchcand != NULL);
552  	
553  	   return branchcand->nprioexternimpls;
554  	}
555  	
556  	/** gets number of continuous external branching candidates with maximal branch priority */
557  	int SCIPbranchcandGetNPrioExternConts(
558  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
559  	   )
560  	{
561  	   assert(branchcand != NULL);
562  	
563  	   return branchcand->nprioexterncands - branchcand->nprioexternbins - branchcand->nprioexternints - branchcand->nprioexternimpls;
564  	}
565  	
566  	/** insert variable, its score and its solution value into the external branching candidate storage
567  	 * the absolute difference of the current lower and upper bounds of the variable must be at least epsilon
568  	 */
569  	SCIP_RETCODE SCIPbranchcandAddExternCand(
570  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
571  	   SCIP_SET*             set,                /**< global SCIP settings */
572  	   SCIP_VAR*             var,                /**< variable to insert */
573  	   SCIP_Real             score,              /**< score of external candidate, e.g. infeasibility */
574  	   SCIP_Real             solval              /**< value of the variable in the current solution */
575  	   )
576  	{
577  	   SCIP_VARTYPE vartype;
578  	   int branchpriority;
579  	   int insertpos;
580  	
581  	   assert(branchcand != NULL);
582  	   assert(var != NULL);
583  	   assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); /* the variable should not be fixed yet */
584  	   assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || !SCIPsetIsEQ(set, SCIPsetCeil(set, SCIPvarGetLbLocal(var)), SCIPsetFloor(set, SCIPvarGetUbLocal(var)))); /* a discrete variable should also not be fixed, even after rounding bounds to integral values */
585  	   assert(SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR || !SCIPsetIsEQ(set, SCIPvarGetMultaggrLbLocal(var, set), SCIPvarGetMultaggrUbLocal(var, set))); /* also the current bounds of a multi-aggregated variable should not be fixed yet */
586  	   assert(branchcand->nprioexterncands <= branchcand->nexterncands);
587  	   assert(branchcand->nexterncands <= branchcand->externcandssize);
588  	
589  	   vartype = SCIPvarGetType(var);
590  	   branchpriority = SCIPvarGetBranchPriority(var);
591  	   insertpos = branchcand->nexterncands;
592  	
593  	   SCIP_CALL( ensureExterncandsSize(branchcand, set, branchcand->nexterncands+1) );
594  	
595  	   SCIPsetDebugMsg(set, "inserting external candidate <%s> of type %d and priority %d into candidate set (maxprio: %d), score = %g, solval = %g\n",
596  	      SCIPvarGetName(var), vartype, branchpriority, branchcand->externmaxpriority, score, solval);
597  	
598  	   /* insert the variable into externcands, making sure, that the highest priority candidates are at the front
599  	    * and ordered binaries, integers, implicit integers, continuous
600  	    */
601  	   if( branchpriority > branchcand->externmaxpriority )
602  	   {
603  	      /* candidate has higher priority than the current maximum:
604  	       * move it to the front and declare it to be the single best candidate
605  	       */
606  	      branchcand->externcands[insertpos] = branchcand->externcands[0];
607  	      branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[0];
608  	      branchcand->externcandssol[insertpos] = branchcand->externcandssol[0];
609  	
610  	      insertpos = 0;
611  	
612  	      branchcand->nprioexterncands = 1;
613  	      branchcand->nprioexternbins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0);
614  	      branchcand->nprioexternints = (vartype == SCIP_VARTYPE_INTEGER ? 1 : 0);
615  	      branchcand->nprioexternimpls = (vartype == SCIP_VARTYPE_IMPLINT ? 1 : 0);
616  	      branchcand->externmaxpriority = branchpriority;
617  	   }
618  	   else if( branchpriority == branchcand->externmaxpriority )
619  	   {
620  	      /* candidate has equal priority as the current maximum:
621  	       * move away the first non-maximal priority candidate, move the current candidate to the correct
622  	       * slot (binaries first, integers next, implicit integers next, continuous last) and increase the number 
623  	       * of maximal priority candidates
624  	       */
625  	      if( insertpos != branchcand->nprioexterncands )
626  	      {
627  	         branchcand->externcands[insertpos] = branchcand->externcands[branchcand->nprioexterncands];
628  	         branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexterncands];
629  	         branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexterncands];
630  	
631  	         insertpos = branchcand->nprioexterncands;
632  	      }
633  	      branchcand->nprioexterncands++;
634  	      if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER || vartype == SCIP_VARTYPE_IMPLINT )
635  	      {
636  	         if( insertpos != branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls )
637  	         {
638  	            branchcand->externcands[insertpos] =
639  	               branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
640  	            branchcand->externcandsscore[insertpos] =
641  	               branchcand->externcandsscore[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
642  	            branchcand->externcandssol[insertpos] =
643  	               branchcand->externcandssol[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
644  	
645  	            insertpos = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls;
646  	         }
647  	         branchcand->nprioexternimpls++;
648  	
649  	         if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER )
650  	         {
651  	            if( insertpos != branchcand->nprioexternbins + branchcand->nprioexternints )
652  	            {
653  	               branchcand->externcands[insertpos] = 
654  	                  branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints];
655  	               branchcand->externcandsscore[insertpos] = 
656  	                  branchcand->externcandsscore[branchcand->nprioexternbins + branchcand->nprioexternints];
657  	               branchcand->externcandssol[insertpos] = 
658  	                  branchcand->externcandssol[branchcand->nprioexternbins + branchcand->nprioexternints];
659  	
660  	               insertpos = branchcand->nprioexternbins + branchcand->nprioexternints;
661  	            }
662  	            branchcand->nprioexternints++;
663  	            branchcand->nprioexternimpls--;
664  	
665  	            if( vartype == SCIP_VARTYPE_BINARY )
666  	            {
667  	               if( insertpos != branchcand->nprioexternbins )
668  	               {
669  	                  branchcand->externcands[insertpos] = branchcand->externcands[branchcand->nprioexternbins];
670  	                  branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexternbins];
671  	                  branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexternbins];
672  	
673  	                  insertpos = branchcand->nprioexternbins;
674  	               }
675  	               branchcand->nprioexternbins++;
676  	               branchcand->nprioexternints--;
677  	            }
678  	         }
679  	      }
680  	   }
681  	   branchcand->externcands[insertpos] = var;
682  	   branchcand->externcandsscore[insertpos] = score;
683  	   branchcand->externcandssol[insertpos] = solval;
684  	   branchcand->nexterncands++;
685  	
686  	   SCIPsetDebugMsg(set, " -> inserted at position %d (nprioexterncands=%d)\n", insertpos, branchcand->nprioexterncands);
687  	
688  	   assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands);
689  	   assert(0 <= branchcand->nprioexternbins && branchcand->nprioexternbins <= branchcand->nprioexterncands);
690  	   assert(0 <= branchcand->nprioexternints && branchcand->nprioexternints <= branchcand->nprioexterncands);
691  	   assert(0 <= branchcand->nprioexternimpls && branchcand->nprioexternimpls <= branchcand->nprioexterncands);
692  	
693  	   return SCIP_OKAY;
694  	}
695  	
696  	/** removes all external candidates from the storage for external branching */
697  	void SCIPbranchcandClearExternCands(
698  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
699  	   )
700  	{
701  	   assert(branchcand != NULL);
702  	
703  	   branchcand->nexterncands = 0;
704  	   branchcand->nprioexterncands = 0;
705  	   branchcand->nprioexternbins = 0;
706  	   branchcand->nprioexternints = 0;
707  	   branchcand->nprioexternimpls = 0;
708  	   branchcand->externmaxpriority = INT_MIN;
709  	}
710  	
711  	/** checks whether the given variable is contained in the candidate storage for external branching */
712  	SCIP_Bool SCIPbranchcandContainsExternCand(
713  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
714  	   SCIP_VAR*             var                 /**< variable to look for */
715  	   )
716  	{
717  	   int branchpriority;
718  	   int i;
719  	
720  	   assert(branchcand != NULL);
721  	   assert(var != NULL);
722  	   assert(branchcand->nprioexterncands <= branchcand->nexterncands);
723  	   assert(branchcand->nexterncands <= branchcand->externcandssize);
724  	
725  	   branchpriority = SCIPvarGetBranchPriority(var);
726  	
727  	   /* look for the variable in the externcands, using the fact, that the highest priority candidates are at the front
728  	    * and ordered binaries, integers, implicit integers, continuous
729  	    */
730  	   if( branchpriority > branchcand->externmaxpriority )
731  	   {
732  	      /* the branching priority of the variable is higher than the maximal priority contained in the array;
733  	       * the variable can thus not be contained */
734  	      return FALSE;
735  	   }
736  	   if( branchpriority == branchcand->externmaxpriority )
737  	   {
738  	      SCIP_VARTYPE vartype;
739  	
740  	      vartype = SCIPvarGetType(var);
741  	
742  	      /* variable has equal priority as the current maximum:
743  	       * look for it in the correct slot (binaries first, integers next, implicit integers next, continuous last)
744  	       */
745  	      if( vartype == SCIP_VARTYPE_BINARY )
746  	      {
747  	         /* the variable is binary, look at the first branchcand->nprioexternbins slots */
748  	         for( i = 0; i < branchcand->nprioexternbins; i++ )
749  	            if( branchcand->externcands[i] == var )
750  	               return TRUE;
751  	         return FALSE;
752  	      }
753  	      if( vartype == SCIP_VARTYPE_INTEGER )
754  	      {
755  	         /* the variable is integer, look at the slots containing integers */
756  	         for( i = 0; i < branchcand->nprioexternints; i++ )
757  	            if( branchcand->externcands[branchcand->nprioexternbins + i] == var )
758  	               return TRUE;
759  	         return FALSE;
760  	      }
761  	      if( vartype == SCIP_VARTYPE_IMPLINT )
762  	      {
763  	         /* the variable is implicit integer, look at the slots containing implicit integers */
764  	         for( i = 0; i < branchcand->nprioexternimpls; i++ )
765  	            if( branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + i] == var )
766  	               return TRUE;
767  	         return FALSE;
768  	      }
769  	      /* the variable is continuous, look at the slots containing continuous variables */
770  	      assert(vartype == SCIP_VARTYPE_CONTINUOUS);
771  	      for( i = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls; 
772  	           i < branchcand->nprioexterncands; i++ )
773  	         if( branchcand->externcands[i] == var )
774  	            return TRUE;
775  	      return FALSE;
776  	   }
777  	   /* the branching priority of the variable is lower than the maximal priority contained in the array;
778  	    * look for the variable in the candidates which do not have maximal priority */
779  	   assert(branchpriority < branchcand->externmaxpriority);
780  	
781  	   for( i = branchcand->nprioexterncands; i < branchcand->nexterncands; i++ )
782  	      if( branchcand->externcands[i] == var )
783  	         return TRUE;
784  	   return FALSE;
785  	}
786  	
787  	/** gets branching candidates for pseudo solution branching (non-fixed variables) */
788  	SCIP_RETCODE SCIPbranchcandGetPseudoCands(
789  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
790  	   SCIP_SET*             set,                /**< global SCIP settings */
791  	   SCIP_PROB*            prob,               /**< problem data */
792  	   SCIP_VAR***           pseudocands,        /**< pointer to store the array of pseudo branching candidates, or NULL */
793  	   int*                  npseudocands,       /**< pointer to store the number of pseudo branching candidates, or NULL */
794  	   int*                  npriopseudocands    /**< pointer to store the number of candidates with maximal priority, or NULL */
795  	   )
796  	{
797  	   assert(branchcand != NULL);
798  	
799  	#ifndef NDEBUG
800  	   /* check, if the current pseudo branching candidate array is correct */
801  	   {
802  	      SCIP_VAR* var;
803  	      int npcs;
804  	      int v;
805  	
806  	      assert(prob != NULL);
807  	
808  	      /* pseudo branching candidates are non-fixed binary, integer, and implicit integer variables */
809  	      npcs = 0;
810  	      for( v = 0; v < prob->nbinvars + prob->nintvars + prob->nimplvars; ++v )
811  	      {
812  	         var = prob->vars[v];
813  	         assert(var != NULL);
814  	         assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
815  	         assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY
816  	            || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER
817  	            || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
818  	         assert(SCIPsetIsFeasIntegral(set, SCIPvarGetLbLocal(var)));
819  	         assert(SCIPsetIsFeasIntegral(set, SCIPvarGetUbLocal(var)));
820  	         assert(SCIPsetIsLE(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
821  	
822  	         if( SCIPsetIsLT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
823  	         {
824  	            assert(0 <= var->pseudocandindex && var->pseudocandindex < branchcand->npseudocands);
825  	            assert(branchcand->pseudocands[var->pseudocandindex] == var);
826  	            npcs++;
827  	         }
828  	         else
829  	         {
830  	            assert(var->pseudocandindex == -1);
831  	         }
832  	      }
833  	      assert(branchcand->npseudocands == npcs);
834  	      for (v = 0; v < branchcand->npriopseudocands; ++v)
835  	         assert( branchcand->pseudocands[v]->branchpriority == branchcand->pseudomaxpriority );
836  	   }
837  	#endif
838  	
839  	   /* assign return values */
840  	   if( pseudocands != NULL )
841  	      *pseudocands = branchcand->pseudocands;
842  	   if( npseudocands != NULL )
843  	      *npseudocands = branchcand->npseudocands;
844  	   if( npriopseudocands != NULL )
845  	      *npriopseudocands = (set->branch_preferbinary && branchcand->npriopseudobins > 0 ? branchcand->npriopseudobins
846  	         : branchcand->npriopseudocands);
847  	
848  	   return SCIP_OKAY;
849  	}
850  	
851  	/** gets number of branching candidates for pseudo solution branching (non-fixed variables) */
852  	int SCIPbranchcandGetNPseudoCands(
853  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
854  	   )
855  	{
856  	   assert(branchcand != NULL);
857  	
858  	   return branchcand->npseudocands;
859  	}
860  	
861  	/** gets number of branching candidates with maximal branch priority for pseudo solution branching */
862  	int SCIPbranchcandGetNPrioPseudoCands(
863  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
864  	   )
865  	{
866  	   assert(branchcand != NULL);
867  	
868  	   return branchcand->npriopseudocands;
869  	}
870  	
871  	/** gets number of binary branching candidates with maximal branch priority for pseudo solution branching */
872  	int SCIPbranchcandGetNPrioPseudoBins(
873  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
874  	   )
875  	{
876  	   assert(branchcand != NULL);
877  	
878  	   return branchcand->npriopseudobins;
879  	}
880  	
881  	/** gets number of integer branching candidates with maximal branch priority for pseudo solution branching */
882  	int SCIPbranchcandGetNPrioPseudoInts(
883  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
884  	   )
885  	{
886  	   assert(branchcand != NULL);
887  	
888  	   return branchcand->npriopseudoints;
889  	}
890  	
891  	/** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching */
892  	int SCIPbranchcandGetNPrioPseudoImpls(
893  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
894  	   )
895  	{
896  	   assert(branchcand != NULL);
897  	
898  	   return branchcand->npriopseudocands - branchcand->npriopseudobins - branchcand->npriopseudoints;
899  	}
900  	
901  	/** insert pseudocand at given position, or to the first positions of the maximal priority candidates, using the
902  	 *  given position as free slot for the other candidates
903  	 */
904  	static
905  	void branchcandInsertPseudoCand(
906  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
907  	   SCIP_VAR*             var,                /**< variable to insert */
908  	   int                   insertpos           /**< free position to insert the variable */
909  	   )
910  	{
911  	   SCIP_VARTYPE vartype;
912  	   int branchpriority;
913  	
914  	   assert(branchcand != NULL);
915  	   assert(var != NULL);
916  	   assert(branchcand->npriopseudocands <= insertpos && insertpos < branchcand->npseudocands);
917  	   assert(branchcand->npseudocands <= branchcand->pseudocandssize);
918  	
919  	   vartype = SCIPvarGetType(var);
920  	   branchpriority = SCIPvarGetBranchPriority(var);
921  	
922  	   SCIPdebugMessage("inserting pseudo candidate <%s> of type %d and priority %d into candidate set at position %d (maxprio: %d)\n",
923  	      SCIPvarGetName(var), vartype, branchpriority, insertpos, branchcand->pseudomaxpriority);
924  	
925  	   /* insert the variable into pseudocands, making sure, that the highest priority candidates are at the front
926  	    * and ordered binaries, integers, implicit integers
927  	    */
928  	   if( branchpriority > branchcand->pseudomaxpriority )
929  	   {
930  	      /* candidate has higher priority than the current maximum:
931  	       * move it to the front and declare it to be the single best candidate
932  	       */
933  	      if( insertpos != 0 )
934  	      {
935  	         branchcand->pseudocands[insertpos] = branchcand->pseudocands[0];
936  	         branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
937  	         insertpos = 0;
938  	      }
939  	      branchcand->npriopseudocands = 1;
940  	      branchcand->npriopseudobins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0);
941  	      branchcand->npriopseudoints = (vartype == SCIP_VARTYPE_INTEGER ? 1 : 0);
942  	      branchcand->pseudomaxpriority = branchpriority;
943  	   }
944  	   else if( branchpriority == branchcand->pseudomaxpriority )
945  	   {
946  	      /* candidate has equal priority as the current maximum:
947  	       * move away the first non-maximal priority candidate, move the current candidate to the correct
948  	       * slot (binaries first, integers next, implicit integers last) and increase the number of maximal priority candidates
949  	       */
950  	      if( insertpos != branchcand->npriopseudocands )
951  	      {
952  	         branchcand->pseudocands[insertpos] = branchcand->pseudocands[branchcand->npriopseudocands];
953  	         branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
954  	         insertpos = branchcand->npriopseudocands;
955  	      }
956  	      branchcand->npriopseudocands++;
957  	      if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER )
958  	      {
959  	         if( insertpos != branchcand->npriopseudobins + branchcand->npriopseudoints )
960  	         {
961  	            branchcand->pseudocands[insertpos] =
962  	               branchcand->pseudocands[branchcand->npriopseudobins + branchcand->npriopseudoints];
963  	            branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
964  	            insertpos = branchcand->npriopseudobins + branchcand->npriopseudoints;
965  	         }
966  	         branchcand->npriopseudoints++;
967  	
968  	         if( vartype == SCIP_VARTYPE_BINARY )
969  	         {
970  	            if( insertpos != branchcand->npriopseudobins )
971  	            {
972  	               branchcand->pseudocands[insertpos] = branchcand->pseudocands[branchcand->npriopseudobins];
973  	               branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
974  	               insertpos = branchcand->npriopseudobins;
975  	            }
976  	            branchcand->npriopseudobins++;
977  	            branchcand->npriopseudoints--;
978  	         }
979  	      }
980  	   }
981  	   branchcand->pseudocands[insertpos] = var;
982  	   var->pseudocandindex = insertpos;
983  	
984  	   SCIPdebugMessage(" -> inserted at position %d (npriopseudocands=%d)\n", insertpos, branchcand->npriopseudocands);
985  	
986  	   assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
987  	   assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
988  	   assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
989  	}
990  	
991  	/** sorts the pseudo branching candidates, such that the candidates of maximal priority are at the front,
992  	 *  ordered by binaries, integers, implicit integers
993  	 */
994  	static
995  	void branchcandSortPseudoCands(
996  	   SCIP_BRANCHCAND*      branchcand          /**< branching candidate storage */
997  	   )
998  	{
999  	   SCIP_VAR* var;
1000 	   int i;
1001 	
1002 	   assert(branchcand != NULL);
1003 	   assert(branchcand->npriopseudocands == 0); /* is only be called after removal of last maximal candidate */
1004 	   assert(branchcand->npriopseudobins == 0);
1005 	   assert(branchcand->npriopseudoints == 0);
1006 	
1007 	   SCIPdebugMessage("resorting pseudo candidates\n");
1008 	
1009 	   branchcand->pseudomaxpriority = INT_MIN;
1010 	
1011 	   for( i = 0; i < branchcand->npseudocands; ++i )
1012 	   {
1013 	      var = branchcand->pseudocands[i];
1014 	      assert(var->pseudocandindex == i);
1015 	
1016 	      if( SCIPvarGetBranchPriority(var) >= branchcand->pseudomaxpriority )
1017 	         branchcandInsertPseudoCand(branchcand, var, i);
1018 	   }
1019 	
1020 	   assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
1021 	   assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
1022 	   assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
1023 	#ifndef NDEBUG
1024 	   {
1025 	      for (i = 0; i < branchcand->npriopseudocands; ++i)
1026 	         assert( branchcand->pseudocands[i]->branchpriority == branchcand->pseudomaxpriority );
1027 	   }
1028 	#endif
1029 	}
1030 	
1031 	/** removes pseudo candidate from pseudocands array
1032 	 */
1033 	static
1034 	void branchcandRemovePseudoCand(
1035 	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
1036 	   SCIP_VAR*             var                 /**< variable to remove */
1037 	   )
1038 	{
1039 	   int freepos;
1040 	
1041 	   assert(branchcand != NULL);
1042 	   assert(var != NULL);
1043 	   assert(var->pseudocandindex < branchcand->npseudocands);
1044 	   assert(branchcand->pseudocands[var->pseudocandindex] == var);
1045 	   assert(branchcand->pseudocands[branchcand->npseudocands-1] != NULL);
1046 	
1047 	   /* Note that the branching priority of the variable to be removed is not necessarily equal to pseudomaxpriority, since
1048 	    * the status of the variable might have changed, leading to a change in the branching priority. Moreover, if the
1049 	    * variable was part of an aggregation, even other variables might at this point have different priorities. */
1050 	   SCIPdebugMessage("removing pseudo candidate <%s> of type %d and priority %d at %d from candidate set (maxprio: %d)\n",
1051 	      SCIPvarGetName(var), SCIPvarGetType(var), SCIPvarGetBranchPriority(var), var->pseudocandindex,
1052 	      branchcand->pseudomaxpriority);
1053 	
1054 	   /* delete the variable from pseudocands, making sure, that the highest priority candidates are at the front
1055 	    * and ordered binaries, integers, implicit integers
1056 	    */
1057 	   freepos = var->pseudocandindex;
1058 	   var->pseudocandindex = -1;
1059 	   assert(0 <= freepos && freepos < branchcand->npseudocands);
1060 	
1061 	   if( freepos < branchcand->npriopseudobins )
1062 	   {
1063 	      /* a binary candidate of maximal priority was removed */
1064 	      assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
1065 	      if( freepos != branchcand->npriopseudobins - 1 )
1066 	      {
1067 	         branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npriopseudobins - 1];
1068 	         branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1069 	         freepos = branchcand->npriopseudobins - 1;
1070 	      }
1071 	      branchcand->npriopseudobins--;
1072 	      branchcand->npriopseudoints++;
1073 	   }
1074 	
1075 	   if( freepos < branchcand->npriopseudobins + branchcand->npriopseudoints )
1076 	   {
1077 	      /* a binary or integer candidate of maximal priority was removed */
1078 	      assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
1079 	      if( freepos != branchcand->npriopseudobins + branchcand->npriopseudoints - 1 )
1080 	      {
1081 	         branchcand->pseudocands[freepos] =
1082 	            branchcand->pseudocands[branchcand->npriopseudobins + branchcand->npriopseudoints - 1];
1083 	         branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1084 	         freepos = branchcand->npriopseudobins + branchcand->npriopseudoints - 1;
1085 	      }
1086 	      branchcand->npriopseudoints--;
1087 	   }
1088 	
1089 	   if( freepos < branchcand->npriopseudocands )
1090 	   {
1091 	      /* a candidate of maximal priority was removed */
1092 	      if( freepos != branchcand->npriopseudocands - 1 )
1093 	      {
1094 	         branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npriopseudocands - 1];
1095 	         branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1096 	         freepos = branchcand->npriopseudocands - 1;
1097 	      }
1098 	      branchcand->npriopseudocands--;
1099 	   }
1100 	   if( freepos != branchcand->npseudocands - 1 )
1101 	   {
1102 	      branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npseudocands - 1];
1103 	      branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1104 	   }
1105 	   branchcand->npseudocands--;
1106 	
1107 	   assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
1108 	   assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
1109 	   assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
1110 	
1111 	   /* if all maximal priority candidates were removed, resort the array s.t. the new maximal priority candidates
1112 	    * are at the front
1113 	    */
1114 	   if( branchcand->npriopseudocands == 0 )
1115 	      branchcandSortPseudoCands(branchcand);
1116 	}
1117 	
1118 	/** removes variable from branching candidate list */
1119 	SCIP_RETCODE SCIPbranchcandRemoveVar(
1120 	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
1121 	   SCIP_VAR*             var                 /**< variable that changed its bounds */
1122 	   )
1123 	{
1124 	   assert(var != NULL);
1125 	
1126 	   /* make sure, variable is not member of the pseudo branching candidate list */
1127 	   if( var->pseudocandindex >= 0 )
1128 	   {
1129 	      branchcandRemovePseudoCand(branchcand, var);
1130 	   }
1131 	
1132 	   return SCIP_OKAY;
1133 	}
1134 	
1135 	/** updates branching candidate list for a given variable */
1136 	SCIP_RETCODE SCIPbranchcandUpdateVar(
1137 	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
1138 	   SCIP_SET*             set,                /**< global SCIP settings */
1139 	   SCIP_VAR*             var                 /**< variable that changed its bounds */
1140 	   )
1141 	{
1142 	   assert(branchcand != NULL);
1143 	   assert(var != NULL);
1144 	
1145 	   if( (SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN)
1146 	      && SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS
1147 	      && SCIPsetIsLT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1148 	   {
1149 	      /* variable is neither continuous nor fixed and has non-empty domain: make sure it is member of the pseudo branching candidate list */
1150 	      if( var->pseudocandindex == -1 )
1151 	      {
1152 	         SCIP_CALL( ensurePseudocandsSize(branchcand, set, branchcand->npseudocands+1) );
1153 	
1154 	         branchcand->npseudocands++;
1155 	         branchcandInsertPseudoCand(branchcand, var, branchcand->npseudocands-1);
1156 	      }
1157 	   }
1158 	   else
1159 	   {
1160 	      assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_ORIGINAL
1161 	         || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED
1162 	         || SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED
1163 	         || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR
1164 	         || SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED
1165 	         || SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS
1166 	         || SCIPsetIsGE(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
1167 	
1168 	      /* variable is continuous or fixed or has empty domain: make sure it is not member of the pseudo branching candidate list */
1169 	      SCIP_CALL( SCIPbranchcandRemoveVar(branchcand, var) );
1170 	   }
1171 	
1172 	   return SCIP_OKAY;
1173 	}
1174 	
1175 	/** updates branching priority of the given variable and update the pseudo candidate array if needed */
1176 	SCIP_RETCODE SCIPbranchcandUpdateVarBranchPriority(
1177 	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
1178 	   SCIP_SET*             set,                /**< global SCIP settings */
1179 	   SCIP_VAR*             var,                /**< variable that changed its bounds */
1180 	   int                   branchpriority      /**< branch priority of the variable */
1181 	   )
1182 	{
1183 	   int oldbranchpriority;
1184 	   int pseudomaxpriority;
1185 	
1186 	   assert(branchcand != NULL);
1187 	
1188 	   oldbranchpriority = SCIPvarGetBranchPriority(var);
1189 	
1190 	   if( oldbranchpriority == branchpriority )
1191 	      return SCIP_OKAY;
1192 	
1193 	   pseudomaxpriority = branchcand->pseudomaxpriority;
1194 	
1195 	   /* if the variable currently belongs to the priority set or the new branching priority is larger than the current one,
1196 	    * remove it from the pseudo branch candidate array */
1197 	   if( oldbranchpriority == pseudomaxpriority || branchpriority > pseudomaxpriority )
1198 	   {
1199 	      SCIP_CALL( SCIPbranchcandRemoveVar(branchcand, var) );
1200 	      assert(var->pseudocandindex == -1);
1201 	   }
1202 	
1203 	   /* change the branching priority of the variable */
1204 	   SCIP_CALL( SCIPvarChgBranchPriority(var, branchpriority) );
1205 	
1206 	   /* if the variable is not part of the pseudo branching candidate array, check if it is a pseudo branching candidate
1207 	    * and add it if so */
1208 	   SCIP_CALL( SCIPbranchcandUpdateVar(branchcand, set, var) );
1209 	
1210 	   return SCIP_OKAY;
1211 	}
1212 	
1213 	
1214 	
1215 	/*
1216 	 * branching rule methods
1217 	 */
1218 	
1219 	/** compares two branching rules w. r. to their priority */
1220 	SCIP_DECL_SORTPTRCOMP(SCIPbranchruleComp)
1221 	{  /*lint --e{715}*/
1222 	   return ((SCIP_BRANCHRULE*)elem2)->priority - ((SCIP_BRANCHRULE*)elem1)->priority;
1223 	}
1224 	
1225 	/** comparison method for sorting branching rules w.r.t. to their name */
1226 	SCIP_DECL_SORTPTRCOMP(SCIPbranchruleCompName)
1227 	{
1228 	   return strcmp(SCIPbranchruleGetName((SCIP_BRANCHRULE*)elem1), SCIPbranchruleGetName((SCIP_BRANCHRULE*)elem2));
1229 	}
1230 	
1231 	/** method to call, when the priority of a branching rule was changed */
1232 	static
1233 	SCIP_DECL_PARAMCHGD(paramChgdBranchrulePriority)
1234 	{  /*lint --e{715}*/
1235 	   SCIP_PARAMDATA* paramdata;
1236 	
1237 	   paramdata = SCIPparamGetData(param);
1238 	   assert(paramdata != NULL);
1239 	
1240 	   /* use SCIPsetBranchrulePriority() to mark the branchrules unsorted */
1241 	   SCIP_CALL( SCIPsetBranchrulePriority(scip, (SCIP_BRANCHRULE*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
1242 	
1243 	   return SCIP_OKAY;
1244 	}
1245 	
1246 	/** copies the given branchrule to a new scip */
1247 	SCIP_RETCODE SCIPbranchruleCopyInclude(
1248 	   SCIP_BRANCHRULE*      branchrule,         /**< branchrule */
1249 	   SCIP_SET*             set                 /**< SCIP_SET of SCIP to copy to */
1250 	   )
1251 	{
1252 	   assert(branchrule != NULL);
1253 	   assert(set != NULL);
1254 	   assert(set->scip != NULL);
1255 	
1256 	   if( branchrule->branchcopy != NULL )
1257 	   {
1258 	      SCIPsetDebugMsg(set, "including branching rule %s in subscip %p\n", SCIPbranchruleGetName(branchrule), (void*)set->scip);
1259 	      SCIP_CALL( branchrule->branchcopy(set->scip, branchrule) );
1260 	   }
1261 	
1262 	   return SCIP_OKAY;
1263 	}
1264 	
1265 	/** internal method for creating a branching rule */
1266 	static
1267 	SCIP_RETCODE doBranchruleCreate(
1268 	   SCIP_BRANCHRULE**     branchrule,         /**< pointer to store branching rule */
1269 	   SCIP_SET*             set,                /**< global SCIP settings */
1270 	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
1271 	   BMS_BLKMEM*           blkmem,             /**< block memory for parameter settings */
1272 	   const char*           name,               /**< name of branching rule */
1273 	   const char*           desc,               /**< description of branching rule */
1274 	   int                   priority,           /**< priority of the branching rule */
1275 	   int                   maxdepth,           /**< maximal depth level, up to which this branching rule should be used (or -1) */
1276 	   SCIP_Real             maxbounddist,       /**< maximal relative distance from current node's dual bound to primal bound
1277 	                                              *   compared to best node's dual bound for applying branching rule
1278 	                                              *   (0.0: only on current best node, 1.0: on all nodes) */
1279 	   SCIP_DECL_BRANCHCOPY  ((*branchcopy)),    /**< copy method of branching rule */
1280 	   SCIP_DECL_BRANCHFREE  ((*branchfree)),    /**< destructor of branching rule */
1281 	   SCIP_DECL_BRANCHINIT  ((*branchinit)),    /**< initialize branching rule */
1282 	   SCIP_DECL_BRANCHEXIT  ((*branchexit)),    /**< deinitialize branching rule */
1283 	   SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
1284 	   SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
1285 	   SCIP_DECL_BRANCHEXECLP((*branchexeclp)),  /**< branching execution method for fractional LP solutions */
1286 	   SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */
1287 	   SCIP_DECL_BRANCHEXECPS((*branchexecps)),  /**< branching execution method for not completely fixed pseudo solutions */
1288 	   SCIP_BRANCHRULEDATA*  branchruledata      /**< branching rule data */
1289 	   )
1290 	{
1291 	   char paramname[SCIP_MAXSTRLEN];
1292 	   char paramdesc[SCIP_MAXSTRLEN];
1293 	
1294 	   assert(branchrule != NULL);
1295 	   assert(name != NULL);
1296 	   assert(desc != NULL);
1297 	
1298 	   SCIP_ALLOC( BMSallocMemory(branchrule) );
1299 	   BMSclearMemory(*branchrule);
1300 	
1301 	   SCIP_ALLOC( BMSduplicateMemoryArray(&(*branchrule)->name, name, strlen(name)+1) );
1302 	   SCIP_ALLOC( BMSduplicateMemoryArray(&(*branchrule)->desc, desc, strlen(desc)+1) );
1303 	   (*branchrule)->priority = priority;
1304 	   (*branchrule)->maxdepth = maxdepth;
1305 	   (*branchrule)->maxbounddist = maxbounddist;
1306 	   (*branchrule)->branchcopy = branchcopy;
1307 	   (*branchrule)->branchfree = branchfree;
1308 	   (*branchrule)->branchinit = branchinit;
1309 	   (*branchrule)->branchexit = branchexit;
1310 	   (*branchrule)->branchinitsol = branchinitsol;
1311 	   (*branchrule)->branchexitsol = branchexitsol;
1312 	   (*branchrule)->branchexeclp = branchexeclp;
1313 	   (*branchrule)->branchexecext = branchexecext;
1314 	   (*branchrule)->branchexecps = branchexecps;
1315 	   (*branchrule)->branchruledata = branchruledata;
1316 	   SCIP_CALL( SCIPclockCreate(&(*branchrule)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
1317 	   SCIP_CALL( SCIPclockCreate(&(*branchrule)->branchclock, SCIP_CLOCKTYPE_DEFAULT) );
1318 	   (*branchrule)->nlpcalls = 0;
1319 	   (*branchrule)->nexterncalls = 0;
1320 	   (*branchrule)->npseudocalls = 0;
1321 	   (*branchrule)->ncutoffs = 0;
1322 	   (*branchrule)->ncutsfound = 0;
1323 	   (*branchrule)->nconssfound = 0;
1324 	   (*branchrule)->ndomredsfound = 0;
1325 	   (*branchrule)->nchildren = 0;
1326 	   (*branchrule)->initialized = FALSE;
1327 	
1328 	   /* add parameters */
1329 	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/priority", name);
1330 	   (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of branching rule <%s>", name);
1331 	   SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
1332 	         &(*branchrule)->priority, FALSE, priority, INT_MIN/4, INT_MAX/4,
1333 	         paramChgdBranchrulePriority, (SCIP_PARAMDATA*)(*branchrule)) ); /*lint !e740*/
1334 	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/maxdepth", name);
1335 	   (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal depth level, up to which branching rule <%s> should be used (-1 for no limit)", name);
1336 	   SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
1337 	         &(*branchrule)->maxdepth, FALSE, maxdepth, -1, SCIP_MAXTREEDEPTH,
1338 	         NULL, NULL) ); /*lint !e740*/
1339 	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/maxbounddist", name);
1340 	   (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying branching rule (0.0: only on current best node, 1.0: on all nodes)");
1341 	   SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname, paramdesc,
1342 	         &(*branchrule)->maxbounddist, FALSE, maxbounddist, 0.0, 1.0,
1343 	         NULL, NULL) ); /*lint !e740*/
1344 	
1345 	   return SCIP_OKAY;
1346 	}
1347 	
1348 	/** creates a branching rule */
1349 	SCIP_RETCODE SCIPbranchruleCreate(
1350 	   SCIP_BRANCHRULE**     branchrule,         /**< pointer to store branching rule */
1351 	   SCIP_SET*             set,                /**< global SCIP settings */
1352 	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
1353 	   BMS_BLKMEM*           blkmem,             /**< block memory for parameter settings */
1354 	   const char*           name,               /**< name of branching rule */
1355 	   const char*           desc,               /**< description of branching rule */
1356 	   int                   priority,           /**< priority of the branching rule */
1357 	   int                   maxdepth,           /**< maximal depth level, up to which this branching rule should be used (or -1) */
1358 	   SCIP_Real             maxbounddist,       /**< maximal relative distance from current node's dual bound to primal bound
1359 	                                              *   compared to best node's dual bound for applying branching rule
1360 	                                              *   (0.0: only on current best node, 1.0: on all nodes) */
1361 	   SCIP_DECL_BRANCHCOPY  ((*branchcopy)),    /**< copy method of branching rule */
1362 	   SCIP_DECL_BRANCHFREE  ((*branchfree)),    /**< destructor of branching rule */
1363 	   SCIP_DECL_BRANCHINIT  ((*branchinit)),    /**< initialize branching rule */
1364 	   SCIP_DECL_BRANCHEXIT  ((*branchexit)),    /**< deinitialize branching rule */
1365 	   SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
1366 	   SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
1367 	   SCIP_DECL_BRANCHEXECLP((*branchexeclp)),  /**< branching execution method for fractional LP solutions */
1368 	   SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */
1369 	   SCIP_DECL_BRANCHEXECPS((*branchexecps)),  /**< branching execution method for not completely fixed pseudo solutions */
1370 	   SCIP_BRANCHRULEDATA*  branchruledata      /**< branching rule data */
1371 	   )
1372 	{
1373 	   assert(branchrule != NULL);
1374 	   assert(name != NULL);
1375 	   assert(desc != NULL);
1376 	
1377 	   SCIP_CALL_FINALLY( doBranchruleCreate(branchrule, set, messagehdlr, blkmem, name, desc, priority, maxdepth,
1378 	      maxbounddist, branchcopy, branchfree, branchinit, branchexit, branchinitsol, branchexitsol, branchexeclp,
1379 	      branchexecext, branchexecps, branchruledata), (void) SCIPbranchruleFree(branchrule, set) );
1380 	
1381 	   return SCIP_OKAY;
1382 	}
1383 	
1384 	/** frees memory of branching rule */
1385 	SCIP_RETCODE SCIPbranchruleFree(
1386 	   SCIP_BRANCHRULE**     branchrule,         /**< pointer to branching rule data structure */
1387 	   SCIP_SET*             set                 /**< global SCIP settings */
1388 	   )
1389 	{
1390 	   assert(branchrule != NULL);
1391 	   if( *branchrule == NULL )
1392 	      return SCIP_OKAY;
1393 	   assert(!(*branchrule)->initialized);
1394 	   assert(set != NULL);
1395 	
1396 	   /* call destructor of branching rule */
1397 	   if( (*branchrule)->branchfree != NULL )
1398 	   {
1399 	      SCIP_CALL( (*branchrule)->branchfree(set->scip, *branchrule) );
1400 	   }
1401 	
1402 	   SCIPclockFree(&(*branchrule)->branchclock);
1403 	   SCIPclockFree(&(*branchrule)->setuptime);
1404 	   BMSfreeMemoryArrayNull(&(*branchrule)->name);
1405 	   BMSfreeMemoryArrayNull(&(*branchrule)->desc);
1406 	   BMSfreeMemory(branchrule);
1407 	
1408 	   return SCIP_OKAY;
1409 	}
1410 	
1411 	/** initializes branching rule */
1412 	SCIP_RETCODE SCIPbranchruleInit(
1413 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1414 	   SCIP_SET*             set                 /**< global SCIP settings */
1415 	   )
1416 	{
1417 	   assert(branchrule != NULL);
1418 	   assert(set != NULL);
1419 	
1420 	   if( branchrule->initialized )
1421 	   {
1422 	      SCIPerrorMessage("branching rule <%s> already initialized\n", branchrule->name);
1423 	      return SCIP_INVALIDCALL;
1424 	   }
1425 	
1426 	   if( set->misc_resetstat )
1427 	   {
1428 	      SCIPclockReset(branchrule->setuptime);
1429 	      SCIPclockReset(branchrule->branchclock);
1430 	      branchrule->nlpcalls = 0;
1431 	      branchrule->nexterncalls = 0;
1432 	      branchrule->npseudocalls = 0;
1433 	      branchrule->ncutoffs = 0;
1434 	      branchrule->ncutsfound = 0;
1435 	      branchrule->nconssfound = 0;
1436 	      branchrule->ndomredsfound = 0;
1437 	      branchrule->nchildren = 0;
1438 	   }
1439 	
1440 	   if( branchrule->branchinit != NULL )
1441 	   {
1442 	      /* start timing */
1443 	      SCIPclockStart(branchrule->setuptime, set);
1444 	
1445 	      SCIP_CALL( branchrule->branchinit(set->scip, branchrule) );
1446 	
1447 	      /* stop timing */
1448 	      SCIPclockStop(branchrule->setuptime, set);
1449 	   }
1450 	   branchrule->initialized = TRUE;
1451 	
1452 	   return SCIP_OKAY;
1453 	}
1454 	
1455 	/** deinitializes branching rule */
1456 	SCIP_RETCODE SCIPbranchruleExit(
1457 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1458 	   SCIP_SET*             set                 /**< global SCIP settings */
1459 	   )
1460 	{
1461 	   assert(branchrule != NULL);
1462 	   assert(set != NULL);
1463 	
1464 	   if( !branchrule->initialized )
1465 	   {
1466 	      SCIPerrorMessage("branching rule <%s> not initialized\n", branchrule->name);
1467 	      return SCIP_INVALIDCALL;
1468 	   }
1469 	
1470 	   if( branchrule->branchexit != NULL )
1471 	   {
1472 	      /* start timing */
1473 	      SCIPclockStart(branchrule->setuptime, set);
1474 	
1475 	      SCIP_CALL( branchrule->branchexit(set->scip, branchrule) );
1476 	
1477 	      /* stop timing */
1478 	      SCIPclockStop(branchrule->setuptime, set);
1479 	   }
1480 	   branchrule->initialized = FALSE;
1481 	
1482 	   return SCIP_OKAY;
1483 	}
1484 	
1485 	/** informs branching rule that the branch and bound process is being started */
1486 	SCIP_RETCODE SCIPbranchruleInitsol(
1487 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1488 	   SCIP_SET*             set                 /**< global SCIP settings */
1489 	   )
1490 	{
1491 	   assert(branchrule != NULL);
1492 	   assert(set != NULL);
1493 	
1494 	   /* call solving process initialization method of branching rule */
1495 	   if( branchrule->branchinitsol != NULL )
1496 	   {
1497 	      /* start timing */
1498 	      SCIPclockStart(branchrule->setuptime, set);
1499 	
1500 	      SCIP_CALL( branchrule->branchinitsol(set->scip, branchrule) );
1501 	
1502 	      /* stop timing */
1503 	      SCIPclockStop(branchrule->setuptime, set);
1504 	   }
1505 	
1506 	   return SCIP_OKAY;
1507 	}
1508 	
1509 	/** informs branching rule that the branch and bound process data is being freed */
1510 	SCIP_RETCODE SCIPbranchruleExitsol(
1511 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1512 	   SCIP_SET*             set                 /**< global SCIP settings */
1513 	   )
1514 	{
1515 	   assert(branchrule != NULL);
1516 	   assert(set != NULL);
1517 	
1518 	   /* call solving process deinitialization method of branching rule */
1519 	   if( branchrule->branchexitsol != NULL )
1520 	   {
1521 	      /* start timing */
1522 	      SCIPclockStart(branchrule->setuptime, set);
1523 	
1524 	      SCIP_CALL( branchrule->branchexitsol(set->scip, branchrule) );
1525 	
1526 	      /* stop timing */
1527 	      SCIPclockStop(branchrule->setuptime, set);
1528 	   }
1529 	
1530 	   return SCIP_OKAY;
1531 	}
1532 	
1533 	/** executes branching rule for fractional LP solution */
1534 	SCIP_RETCODE SCIPbranchruleExecLPSol(
1535 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1536 	   SCIP_SET*             set,                /**< global SCIP settings */
1537 	   SCIP_STAT*            stat,               /**< problem statistics */
1538 	   SCIP_TREE*            tree,               /**< branch and bound tree */
1539 	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
1540 	   SCIP_Real             cutoffbound,        /**< global upper cutoff bound */
1541 	   SCIP_Bool             allowaddcons,       /**< should adding constraints be allowed to avoid a branching? */
1542 	   SCIP_RESULT*          result              /**< pointer to store the result of the callback method */
1543 	   )
1544 	{
1545 	   assert(branchrule != NULL);
1546 	   assert(set != NULL);
1547 	   assert(tree != NULL);
1548 	   assert(tree->focusnode != NULL);
1549 	   assert(tree->nchildren == 0);
1550 	   assert(result != NULL);
1551 	
1552 	   *result = SCIP_DIDNOTRUN;
1553 	   if( branchrule->branchexeclp != NULL
1554 	      && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) )
1555 	   {
1556 	      SCIP_Real loclowerbound;
1557 	      SCIP_Real glblowerbound;
1558 	      SCIP_Bool runbranchrule;
1559 	
1560 	      loclowerbound = SCIPnodeGetLowerbound(tree->focusnode);
1561 	      glblowerbound = SCIPtreeGetLowerbound(tree, set);
1562 	
1563 	      /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1564 	      if( SCIPsetIsInfinity(set, -glblowerbound) )
1565 	         runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1566 	      else
1567 	      {
1568 	         assert(!SCIPsetIsInfinity(set, -loclowerbound));
1569 	         runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1570 	      }
1571 	
1572 	      if( runbranchrule )
1573 	      {
1574 	         SCIP_Longint oldndomchgs;
1575 	         SCIP_Longint oldnprobdomchgs;
1576 	         SCIP_Longint oldnactiveconss;
1577 	         int oldncuts;
1578 	
1579 	         SCIPsetDebugMsg(set, "executing LP branching rule <%s>\n", branchrule->name);
1580 	
1581 	         oldndomchgs = stat->nboundchgs + stat->nholechgs;
1582 	         oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
1583 	         oldncuts = SCIPsepastoreGetNCuts(sepastore);
1584 	         oldnactiveconss = stat->nactiveconssadded;
1585 	
1586 	         /* start timing */
1587 	         SCIPclockStart(branchrule->branchclock, set);
1588 	
1589 	         /* call external method */
1590 	         SCIP_CALL( branchrule->branchexeclp(set->scip, branchrule, allowaddcons, result) );
1591 	
1592 	         /* stop timing */
1593 	         SCIPclockStop(branchrule->branchclock, set);
1594 	
1595 	         /* evaluate result */
1596 	         if( *result != SCIP_CUTOFF
1597 	            && *result != SCIP_CONSADDED
1598 	            && *result != SCIP_REDUCEDDOM
1599 	            && *result != SCIP_SEPARATED
1600 	            && *result != SCIP_BRANCHED
1601 	            && *result != SCIP_DIDNOTFIND
1602 	            && *result != SCIP_DIDNOTRUN )
1603 	         {
1604 	            SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from LP solution branching\n",
1605 	               branchrule->name, *result);
1606 	            return SCIP_INVALIDRESULT;
1607 	         }
1608 	         if( *result == SCIP_CONSADDED && !allowaddcons )
1609 	         {
1610 	            SCIPerrorMessage("branching rule <%s> added a constraint in LP solution branching without permission\n",
1611 	               branchrule->name);
1612 	            return SCIP_INVALIDRESULT;
1613 	         }
1614 	
1615 	         /* update statistics */
1616 	         if( *result != SCIP_DIDNOTRUN )
1617 	            branchrule->nlpcalls++;
1618 	         if( *result == SCIP_CUTOFF )
1619 	            branchrule->ncutoffs++;
1620 	         if( *result != SCIP_BRANCHED )
1621 	         {
1622 	            assert(tree->nchildren == 0);
1623 	
1624 	            /* update domain reductions; therefore remove the domain
1625 	             * reduction counts which were generated in probing mode */
1626 	            branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
1627 	            branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
1628 	
1629 	            branchrule->ncutsfound += SCIPsepastoreGetNCuts(sepastore) - oldncuts; /*lint !e776*/
1630 	            branchrule->nconssfound += stat->nactiveconssadded - oldnactiveconss; /*lint !e776*/
1631 	         }
1632 	         else
1633 	            branchrule->nchildren += tree->nchildren;
1634 	      }
1635 	   }
1636 	
1637 	   return SCIP_OKAY;
1638 	}
1639 	
1640 	/** executes branching rule for external branching candidates */
1641 	SCIP_RETCODE SCIPbranchruleExecExternSol(
1642 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1643 	   SCIP_SET*             set,                /**< global SCIP settings */
1644 	   SCIP_STAT*            stat,               /**< problem statistics */
1645 	   SCIP_TREE*            tree,               /**< branch and bound tree */
1646 	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
1647 	   SCIP_Real             cutoffbound,        /**< global upper cutoff bound */
1648 	   SCIP_Bool             allowaddcons,       /**< should adding constraints be allowed to avoid a branching? */
1649 	   SCIP_RESULT*          result              /**< pointer to store the result of the callback method */
1650 	   )
1651 	{
1652 	   assert(branchrule != NULL);
1653 	   assert(set != NULL);
1654 	   assert(tree != NULL);
1655 	   assert(tree->focusnode != NULL);
1656 	   assert(tree->nchildren == 0);
1657 	   assert(result != NULL);
1658 	
1659 	   *result = SCIP_DIDNOTRUN;
1660 	   if( branchrule->branchexecext != NULL
1661 	      && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) )
1662 	   {
1663 	      SCIP_Real loclowerbound;
1664 	      SCIP_Real glblowerbound;
1665 	      SCIP_Bool runbranchrule;
1666 	
1667 	      loclowerbound = SCIPnodeGetLowerbound(tree->focusnode);
1668 	      glblowerbound = SCIPtreeGetLowerbound(tree, set);
1669 	      assert(!SCIPsetIsInfinity(set, loclowerbound));
1670 	
1671 	      /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1672 	      if( SCIPsetIsInfinity(set, -glblowerbound) )
1673 	         runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1674 	      else
1675 	      {
1676 	         assert(!SCIPsetIsInfinity(set, -loclowerbound));
1677 	         runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1678 	      }
1679 	
1680 	      if( runbranchrule )
1681 	      {
1682 	         SCIP_Longint oldndomchgs;
1683 	         SCIP_Longint oldnprobdomchgs;
1684 	         int oldncuts;
1685 	         int oldnactiveconss;
1686 	
1687 	         SCIPsetDebugMsg(set, "executing external solution branching rule <%s>\n", branchrule->name);
1688 	
1689 	         oldndomchgs = stat->nboundchgs + stat->nholechgs;
1690 	         oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
1691 	         oldncuts = SCIPsepastoreGetNCuts(sepastore);
1692 	         oldnactiveconss = stat->nactiveconss;
1693 	
1694 	         /* start timing */
1695 	         SCIPclockStart(branchrule->branchclock, set);
1696 	
1697 	         /* call external method */
1698 	         SCIP_CALL( branchrule->branchexecext(set->scip, branchrule, allowaddcons, result) );
1699 	
1700 	         /* stop timing */
1701 	         SCIPclockStop(branchrule->branchclock, set);
1702 	
1703 	         /* evaluate result */
1704 	         if( *result != SCIP_CUTOFF
1705 	            && *result != SCIP_CONSADDED
1706 	            && *result != SCIP_REDUCEDDOM
1707 	            && *result != SCIP_SEPARATED
1708 	            && *result != SCIP_BRANCHED
1709 	            && *result != SCIP_DIDNOTFIND
1710 	            && *result != SCIP_DIDNOTRUN )
1711 	         {
1712 	            SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from external solution branching\n",
1713 	               branchrule->name, *result);
1714 	            return SCIP_INVALIDRESULT;
1715 	         }
1716 	         if( *result == SCIP_CONSADDED && !allowaddcons )
1717 	         {
1718 	            SCIPerrorMessage("branching rule <%s> added a constraint in external solution branching without permission\n",
1719 	               branchrule->name);
1720 	            return SCIP_INVALIDRESULT;
1721 	         }
1722 	
1723 	         /* update statistics */
1724 	         if( *result != SCIP_DIDNOTRUN )
1725 	            branchrule->nexterncalls++;
1726 	         if( *result == SCIP_CUTOFF )
1727 	            branchrule->ncutoffs++;
1728 	         if( *result != SCIP_BRANCHED )
1729 	         {
1730 	            assert(tree->nchildren == 0);
1731 	
1732 	            /* update domain reductions; therefore remove the domain
1733 	             * reduction counts which were generated in probing mode */
1734 	            branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
1735 	            branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
1736 	
1737 	            branchrule->ncutsfound += SCIPsepastoreGetNCuts(sepastore) - oldncuts; /*lint !e776*/
1738 	            branchrule->nconssfound += stat->nactiveconss - oldnactiveconss; /*lint !e776*/
1739 	         }
1740 	         else
1741 	            branchrule->nchildren += tree->nchildren;
1742 	      }
1743 	   }
1744 	   return SCIP_OKAY;
1745 	}
1746 	
1747 	/** executes branching rule for not completely fixed pseudo solution */
1748 	SCIP_RETCODE SCIPbranchruleExecPseudoSol(
1749 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1750 	   SCIP_SET*             set,                /**< global SCIP settings */
1751 	   SCIP_STAT*            stat,               /**< problem statistics */
1752 	   SCIP_TREE*            tree,               /**< branch and bound tree */
1753 	   SCIP_Real             cutoffbound,        /**< global upper cutoff bound */
1754 	   SCIP_Bool             allowaddcons,       /**< should adding constraints be allowed to avoid a branching? */
1755 	   SCIP_RESULT*          result              /**< pointer to store the result of the callback method */
1756 	   )
1757 	{
1758 	   assert(branchrule != NULL);
1759 	   assert(set != NULL);
1760 	   assert(tree != NULL);
1761 	   assert(tree->nchildren == 0);
1762 	   assert(result != NULL);
1763 	
1764 	   *result = SCIP_DIDNOTRUN;
1765 	   if( branchrule->branchexecps != NULL
1766 	      && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) )
1767 	   {
1768 	      SCIP_Real loclowerbound;
1769 	      SCIP_Real glblowerbound;
1770 	      SCIP_Bool runbranchrule;
1771 	
1772 	      loclowerbound = SCIPnodeGetLowerbound(tree->focusnode);
1773 	      glblowerbound = SCIPtreeGetLowerbound(tree, set);
1774 	
1775 	      /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1776 	      if( SCIPsetIsInfinity(set, -glblowerbound) )
1777 	         runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1778 	      else
1779 	      {
1780 	         assert(!SCIPsetIsInfinity(set, -loclowerbound));
1781 	         runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1782 	      }
1783 	
1784 	      if( runbranchrule )
1785 	      {
1786 	         SCIP_Longint oldndomchgs;
1787 	         SCIP_Longint oldnprobdomchgs;
1788 	         SCIP_Longint oldnactiveconss;
1789 	
1790 	         SCIPsetDebugMsg(set, "executing pseudo branching rule <%s>\n", branchrule->name);
1791 	
1792 	         oldndomchgs = stat->nboundchgs + stat->nholechgs;
1793 	         oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
1794 	         oldnactiveconss = stat->nactiveconss;
1795 	
1796 	         /* start timing */
1797 	         SCIPclockStart(branchrule->branchclock, set);
1798 	
1799 	         /* call external method */
1800 	         SCIP_CALL( branchrule->branchexecps(set->scip, branchrule, allowaddcons, result) );
1801 	
1802 	         /* stop timing */
1803 	         SCIPclockStop(branchrule->branchclock, set);
1804 	
1805 	         /* evaluate result */
1806 	         if( *result != SCIP_CUTOFF
1807 	            && *result != SCIP_CONSADDED
1808 	            && *result != SCIP_REDUCEDDOM
1809 	            && *result != SCIP_BRANCHED
1810 	            && *result != SCIP_DIDNOTFIND
1811 	            && *result != SCIP_DIDNOTRUN )
1812 	         {
1813 	            SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from pseudo solution branching\n",
1814 	               branchrule->name, *result);
1815 	            return SCIP_INVALIDRESULT;
1816 	         }
1817 	         if( *result == SCIP_CONSADDED && !allowaddcons )
1818 	         {
1819 	            SCIPerrorMessage("branching rule <%s> added a constraint in pseudo solution branching without permission\n",
1820 	               branchrule->name);
1821 	            return SCIP_INVALIDRESULT;
1822 	         }
1823 	
1824 	         /* update statistics */
1825 	         if( *result != SCIP_DIDNOTRUN )
1826 	            branchrule->npseudocalls++;
1827 	         if( *result == SCIP_CUTOFF )
1828 	            branchrule->ncutoffs++;
1829 	         if( *result != SCIP_BRANCHED )
1830 	         {
1831 	            assert(tree->nchildren == 0);
1832 	
1833 	            /* update domain reductions; therefore remove the domain
1834 	             * reduction counts which were generated in probing mode */
1835 	            branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
1836 	            branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
1837 	
1838 	            branchrule->nconssfound += stat->nactiveconss - oldnactiveconss;
1839 	         }
1840 	         else
1841 	            branchrule->nchildren += tree->nchildren;
1842 	      }
1843 	   }
1844 	
1845 	   return SCIP_OKAY;
1846 	}
1847 	
1848 	/** gets user data of branching rule */
1849 	SCIP_BRANCHRULEDATA* SCIPbranchruleGetData(
1850 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
1851 	   )
1852 	{
1853 	   assert(branchrule != NULL);
1854 	
1855 	   return branchrule->branchruledata;
1856 	}
1857 	
1858 	/** sets user data of branching rule; user has to free old data in advance! */
1859 	void SCIPbranchruleSetData(
1860 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1861 	   SCIP_BRANCHRULEDATA*  branchruledata      /**< new branching rule user data */
1862 	   )
1863 	{
1864 	   assert(branchrule != NULL);
1865 	
1866 	   branchrule->branchruledata = branchruledata;
1867 	}
1868 	
1869 	/** sets copy method of branching rule */
1870 	void SCIPbranchruleSetCopy(
1871 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1872 	   SCIP_DECL_BRANCHCOPY  ((*branchcopy))     /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
1873 	   )
1874 	{
1875 	   assert(branchrule != NULL);
1876 	
1877 	   branchrule->branchcopy = branchcopy;
1878 	}
1879 	
1880 	/** sets destructor method of branching rule */
1881 	void SCIPbranchruleSetFree(
1882 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1883 	   SCIP_DECL_BRANCHFREE  ((*branchfree))     /**< destructor of branching rule */
1884 	   )
1885 	{
1886 	   assert(branchrule != NULL);
1887 	
1888 	   branchrule->branchfree = branchfree;
1889 	}
1890 	
1891 	/** sets initialization method of branching rule */
1892 	void SCIPbranchruleSetInit(
1893 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1894 	   SCIP_DECL_BRANCHINIT  ((*branchinit))     /**< initialize branching rule */
1895 	   )
1896 	{
1897 	   assert(branchrule != NULL);
1898 	
1899 	   branchrule->branchinit = branchinit;
1900 	}
1901 	
1902 	/** sets deinitialization method of branching rule */
1903 	void SCIPbranchruleSetExit(
1904 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1905 	   SCIP_DECL_BRANCHEXIT  ((*branchexit))     /**< deinitialize branching rule */
1906 	   )
1907 	{
1908 	   assert(branchrule != NULL);
1909 	
1910 	   branchrule->branchexit = branchexit;
1911 	}
1912 	
1913 	/** sets solving process initialization method of branching rule */
1914 	void SCIPbranchruleSetInitsol(
1915 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1916 	   SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
1917 	   )
1918 	{
1919 	   assert(branchrule != NULL);
1920 	
1921 	   branchrule->branchinitsol = branchinitsol;
1922 	}
1923 	
1924 	/** sets solving process deinitialization method of branching rule */
1925 	void SCIPbranchruleSetExitsol(
1926 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1927 	   SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
1928 	   )
1929 	{
1930 	   assert(branchrule != NULL);
1931 	
1932 	   branchrule->branchexitsol = branchexitsol;
1933 	}
1934 	
1935 	
1936 	
1937 	/** sets branching execution method for fractional LP solutions */
1938 	void SCIPbranchruleSetExecLp(
1939 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1940 	   SCIP_DECL_BRANCHEXECLP((*branchexeclp))   /**< branching execution method for fractional LP solutions */
1941 	   )
1942 	{
1943 	   assert(branchrule != NULL);
1944 	
1945 	   branchrule->branchexeclp = branchexeclp;
1946 	}
1947 	
1948 	/** sets branching execution method for external candidates  */
1949 	void SCIPbranchruleSetExecExt(
1950 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1951 	   SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
1952 	   )
1953 	{
1954 	   assert(branchrule != NULL);
1955 	
1956 	   branchrule->branchexecext = branchexecext;
1957 	}
1958 	
1959 	/** sets branching execution method for not completely fixed pseudo solutions */
1960 	void SCIPbranchruleSetExecPs(
1961 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
1962 	   SCIP_DECL_BRANCHEXECPS((*branchexecps))   /**< branching execution method for not completely fixed pseudo solutions */
1963 	   )
1964 	{
1965 	   assert(branchrule != NULL);
1966 	
1967 	   branchrule->branchexecps = branchexecps;
1968 	}
1969 	
1970 	/** gets name of branching rule */
1971 	const char* SCIPbranchruleGetName(
1972 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
1973 	   )
1974 	{
1975 	   assert(branchrule != NULL);
1976 	
1977 	   return branchrule->name;
1978 	}
1979 	
1980 	/** gets description of branching rule */
1981 	const char* SCIPbranchruleGetDesc(
1982 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
1983 	   )
1984 	{
1985 	   assert(branchrule != NULL);
1986 	
1987 	   return branchrule->desc;
1988 	}
1989 	
1990 	/** gets priority of branching rule */
1991 	int SCIPbranchruleGetPriority(
1992 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
1993 	   )
1994 	{
1995 	   assert(branchrule != NULL);
1996 	
1997 	   return branchrule->priority;
1998 	}
1999 	
2000 	/** sets priority of branching rule */
2001 	void SCIPbranchruleSetPriority(
2002 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
2003 	   SCIP_SET*             set,                /**< global SCIP settings */
2004 	   int                   priority            /**< new priority of the branching rule */
2005 	   )
2006 	{
2007 	   assert(branchrule != NULL);
2008 	   assert(set != NULL);
2009 	
2010 	   branchrule->priority = priority;
2011 	   set->branchrulessorted = FALSE;
2012 	}
2013 	
2014 	/** gets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
2015 	int SCIPbranchruleGetMaxdepth(
2016 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2017 	   )
2018 	{
2019 	   assert(branchrule != NULL);
2020 	
2021 	   return branchrule->maxdepth;
2022 	}
2023 	
2024 	/** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
2025 	void SCIPbranchruleSetMaxdepth(
2026 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
2027 	   int                   maxdepth            /**< new maxdepth of the branching rule */
2028 	   )
2029 	{
2030 	   assert(branchrule != NULL);
2031 	   assert(maxdepth >= -1);
2032 	
2033 	   branchrule->maxdepth = maxdepth;
2034 	}
2035 	
2036 	/** gets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
2037 	SCIP_Real SCIPbranchruleGetMaxbounddist(
2038 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2039 	   )
2040 	{
2041 	   assert(branchrule != NULL);
2042 	
2043 	   return branchrule->maxbounddist;
2044 	}
2045 	
2046 	/** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
2047 	void SCIPbranchruleSetMaxbounddist(
2048 	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
2049 	   SCIP_Real             maxbounddist        /**< new maxbounddist of the branching rule */
2050 	   )
2051 	{
2052 	   assert(branchrule != NULL);
2053 	   assert(maxbounddist >= -1);
2054 	
2055 	   branchrule->maxbounddist = maxbounddist;
2056 	}
2057 	
2058 	/** enables or disables all clocks of \p branchrule, depending on the value of the flag */
2059 	void SCIPbranchruleEnableOrDisableClocks(
2060 	   SCIP_BRANCHRULE*      branchrule,         /**< the branching rule for which all clocks should be enabled or disabled */
2061 	   SCIP_Bool             enable              /**< should the clocks of the branching rule be enabled? */
2062 	   )
2063 	{
2064 	   assert(branchrule != NULL);
2065 	
2066 	   SCIPclockEnableOrDisable(branchrule->setuptime, enable);
2067 	   SCIPclockEnableOrDisable(branchrule->branchclock, enable);
2068 	}
2069 	
2070 	/** gets time in seconds used in this branching rule for setting up for next stages */
2071 	SCIP_Real SCIPbranchruleGetSetupTime(
2072 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2073 	   )
2074 	{
2075 	   assert(branchrule != NULL);
2076 	
2077 	   return SCIPclockGetTime(branchrule->setuptime);
2078 	}
2079 	
2080 	/** gets time in seconds used in this branching rule */
2081 	SCIP_Real SCIPbranchruleGetTime(
2082 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2083 	   )
2084 	{
2085 	   assert(branchrule != NULL);
2086 	
2087 	   return SCIPclockGetTime(branchrule->branchclock);
2088 	}
2089 	
2090 	/** gets the total number of times, the branching rule was called on an LP solution */
2091 	SCIP_Longint SCIPbranchruleGetNLPCalls(
2092 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2093 	   )
2094 	{
2095 	   assert(branchrule != NULL);
2096 	
2097 	   return branchrule->nlpcalls;
2098 	}
2099 	
2100 	/** gets the total number of times, the branching rule was called on an external solution */
2101 	SCIP_Longint SCIPbranchruleGetNExternCalls(
2102 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2103 	   )
2104 	{
2105 	   assert(branchrule != NULL);
2106 	
2107 	   return branchrule->nexterncalls;
2108 	}
2109 	
2110 	/** gets the total number of times, the branching rule was called on a pseudo solution */
2111 	SCIP_Longint SCIPbranchruleGetNPseudoCalls(
2112 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2113 	   )
2114 	{
2115 	   assert(branchrule != NULL);
2116 	
2117 	   return branchrule->npseudocalls;
2118 	}
2119 	
2120 	/** gets the total number of times, the branching rule detected a cutoff */
2121 	SCIP_Longint SCIPbranchruleGetNCutoffs(
2122 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2123 	   )
2124 	{
2125 	   assert(branchrule != NULL);
2126 	
2127 	   return branchrule->ncutoffs;
2128 	}
2129 	
2130 	/** gets the total number of cuts, the branching rule separated */
2131 	SCIP_Longint SCIPbranchruleGetNCutsFound(
2132 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2133 	   )
2134 	{
2135 	   assert(branchrule != NULL);
2136 	
2137 	   return branchrule->ncutsfound;
2138 	}
2139 	
2140 	/** gets the total number of constraints, the branching rule added to the respective local nodes (not counting constraints
2141 	 *  that were added to the child nodes as branching decisions)
2142 	 */
2143 	SCIP_Longint SCIPbranchruleGetNConssFound(
2144 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2145 	   )
2146 	{
2147 	   assert(branchrule != NULL);
2148 	
2149 	   return branchrule->nconssfound;
2150 	}
2151 	
2152 	/** gets the total number of domain reductions, the branching rule found */
2153 	SCIP_Longint SCIPbranchruleGetNDomredsFound(
2154 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2155 	   )
2156 	{
2157 	   assert(branchrule != NULL);
2158 	
2159 	   return branchrule->ndomredsfound;
2160 	}
2161 	
2162 	/** gets the total number of children, the branching rule created */
2163 	SCIP_Longint SCIPbranchruleGetNChildren(
2164 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2165 	   )
2166 	{
2167 	   assert(branchrule != NULL);
2168 	
2169 	   return branchrule->nchildren;
2170 	}
2171 	
2172 	/** is branching rule initialized? */
2173 	SCIP_Bool SCIPbranchruleIsInitialized(
2174 	   SCIP_BRANCHRULE*      branchrule          /**< branching rule */
2175 	   )
2176 	{
2177 	   assert(branchrule != NULL);
2178 	
2179 	   return branchrule->initialized;
2180 	}
2181 	
2182 	
2183 	
2184 	
2185 	/*
2186 	 * branching methods
2187 	 */
2188 	
2189 	/** calculates the branching score out of the gain predictions for a binary branching */
2190 	SCIP_Real SCIPbranchGetScore(
2191 	   SCIP_SET*             set,                /**< global SCIP settings */
2192 	   SCIP_VAR*             var,                /**< variable, of which the branching factor should be applied, or NULL */
2193 	   SCIP_Real             downgain,           /**< prediction of objective gain for rounding downwards */
2194 	   SCIP_Real             upgain              /**< prediction of objective gain for rounding upwards */
2195 	   )
2196 	{
2197 	   SCIP_Real score;
2198 	   SCIP_Real eps;
2199 	
2200 	   assert(set != NULL);
2201 	
2202 	   /* adjust scores near zero to always yield product score greater than 0 */
2203 	   eps = SCIPsetSumepsilon(set);
2204 	   if( set->branch_sumadjustscore )
2205 	   {
2206 	      /* adjust scores by adding eps to keep near zero score differences between variables */
2207 	      downgain = downgain + eps;
2208 	      upgain = upgain + eps;
2209 	   }
2210 	   else
2211 	   {
2212 	      /* disregard near zero score differences between variables and consider the branching factor for them */
2213 	      downgain = MAX(downgain, eps);
2214 	      upgain = MAX(upgain, eps);
2215 	   }
2216 	
2217 	   switch( set->branch_scorefunc )
2218 	   {
2219 	   case 's':  /* linear sum score function */
2220 	      /* weigh the two child nodes with branchscorefac and 1-branchscorefac */
2221 	      if( downgain > upgain )
2222 	         score = set->branch_scorefac * downgain + (1.0-set->branch_scorefac) * upgain;
2223 	      else
2224 	         score = set->branch_scorefac * upgain + (1.0-set->branch_scorefac) * downgain;
2225 	      break;
2226 	
2227 	   case 'p':  /* product score function */
2228 	      score = downgain * upgain;
2229 	      break;
2230 	   case 'q': /* quotient score function */
2231 	      if( downgain > upgain )
2232 	         score = upgain * upgain / downgain;
2233 	      else
2234 	         score = downgain * downgain / upgain;
2235 	      break;
2236 	   default:
2237 	      SCIPerrorMessage("invalid branching score function <%c>\n", set->branch_scorefunc);
2238 	      SCIPABORT();
2239 	      score = 0.0;
2240 	   }
2241 	
2242 	   /* apply the branch factor of the variable */
2243 	   if( var != NULL )
2244 	      score *= SCIPvarGetBranchFactor(var);
2245 	
2246 	   return score;
2247 	}
2248 	
2249 	/** calculates the branching score out of the gain predictions for a branching with arbitrary many children */
2250 	SCIP_Real SCIPbranchGetScoreMultiple(
2251 	   SCIP_SET*             set,                /**< global SCIP settings */
2252 	   SCIP_VAR*             var,                /**< variable, of which the branching factor should be applied, or NULL */
2253 	   int                   nchildren,          /**< number of children that the branching will create */
2254 	   SCIP_Real*            gains               /**< prediction of objective gain for each child */
2255 	   )
2256 	{
2257 	   SCIP_Real min1;
2258 	   SCIP_Real min2;
2259 	   int c;
2260 	
2261 	   assert(nchildren == 0 || gains != NULL);
2262 	
2263 	   /* search for the two minimal gains in the child list and use these to calculate the branching score */
2264 	   min1 = SCIPsetInfinity(set);
2265 	   min2 = SCIPsetInfinity(set);
2266 	   for( c = 0; c < nchildren; ++c )
2267 	   {
2268 	      if( gains[c] < min1 )
2269 	      {
2270 	         min2 = min1;
2271 	         min1 = gains[c];
2272 	      }
2273 	      else if( gains[c] < min2 )
2274 	         min2 = gains[c];
2275 	   }
2276 	
2277 	   return SCIPbranchGetScore(set, var, min1, min2);
2278 	}
2279 	
2280 	/** computes a branching point for a (not necessarily discrete) variable
2281 	 * a suggested branching point is first projected onto the box
2282 	 * if no point is suggested, then the value in the current LP or pseudo solution is used
2283 	 * if this value is at infinity, then 0.0 projected onto the bounds and then moved inside the interval is used 
2284 	 * for a discrete variable, it is ensured that the returned value is fractional
2285 	 * for a continuous variable, the parameter branching/clamp defines how far a branching point need to be from the bounds of a variable
2286 	 * the latter is only applied if no point has been suggested, or the suggested point is not inside the variable's interval
2287 	 */
2288 	SCIP_Real SCIPbranchGetBranchingPoint(
2289 	   SCIP_SET*             set,                /**< global SCIP settings */
2290 	   SCIP_TREE*            tree,               /**< branch and bound tree */
2291 	   SCIP_VAR*             var,                /**< variable, of which the branching point should be computed */
2292 	   SCIP_Real             suggestion          /**< suggestion for branching point, or SCIP_INVALID if no suggestion */
2293 	   )
2294 	{
2295 	   SCIP_Real branchpoint;
2296 	   SCIP_Real lb;
2297 	   SCIP_Real ub;
2298 	
2299 	   assert(set != NULL);
2300 	   assert(var != NULL);
2301 	
2302 	   lb = SCIPvarGetLbLocal(var);
2303 	   ub = SCIPvarGetUbLocal(var);
2304 	
2305 	   /* for a fixed variable, we cannot branch further */
2306 	   assert(!SCIPsetIsEQ(set, lb, ub));
2307 	
2308 	   if( !SCIPsetIsInfinity(set, REALABS(suggestion)) )
2309 	   {
2310 	      /* use user suggested branching point */
2311 	
2312 	      /* first, project it onto the current domain */
2313 	      branchpoint = MAX(lb, MIN(suggestion, ub));
2314 	
2315 	      if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
2316 	      {
2317 	         /* if it is a discrete variable, then round it down and up and accept this choice */
2318 	         if( SCIPsetIsEQ(set, branchpoint, ub) )
2319 	         {
2320 	            /* in the right branch, variable is fixed to its current upper bound */
2321 	            return SCIPsetFloor(set, branchpoint) - 0.5;
2322 	         }
2323 	         else
2324 	         {
2325 	            /* in the  left branch, variable is fixed to its current lower bound */
2326 	            return SCIPsetFloor(set, branchpoint) + 0.5;
2327 	         }
2328 	      }
2329 	      else if( (SCIPsetIsInfinity(set, -lb) || SCIPsetIsRelGT(set, branchpoint, lb)) &&
2330 	                (SCIPsetIsInfinity(set,  ub) || SCIPsetIsRelLT(set, branchpoint, ub)) )
2331 	      {
2332 	         /* if it is continuous and inside the box, then accept it */ 
2333 	         return branchpoint;
2334 	      }
2335 	      /* if it is continuous and suggestion is on of the bounds, continue below */
2336 	   }
2337 	   else
2338 	   {
2339 	      /* if no point is suggested, try the LP or pseudo solution */
2340 	      branchpoint = SCIPvarGetSol(var, SCIPtreeHasCurrentNodeLP(tree));
2341 	
2342 	      if( REALABS(branchpoint) > 1e+12 )
2343 	      {
2344 	         /* if the value in the LP or pseudosolution is large (here 1e+12), use 0.0 (will be projected onto bounds below) */
2345 	         branchpoint = 0.0;
2346 	      }
2347 	      else if( SCIPtreeHasCurrentNodeLP(tree) && set->branch_midpull > 0.0 && !SCIPsetIsInfinity(set, -lb) && !SCIPsetIsInfinity(set, ub) )
2348 	      {
2349 	         /* if the value is from the LP and midpull is activated, then push towards middle of domain */
2350 	         SCIP_Real midpull = set->branch_midpull;
2351 	         SCIP_Real glb;
2352 	         SCIP_Real gub;
2353 	         SCIP_Real reldomainwidth;
2354 	
2355 	         /* shrink midpull if width of local domain, relative to global domain, is small
2356 	          * that is, if there has been already one or several branchings on this variable, then give more emphasis on LP solution
2357 	          *
2358 	          * do this only if the relative domain width is below the minreldomainwidth value
2359 	          */
2360 	         glb = SCIPvarGetLbGlobal(var);
2361 	         gub = SCIPvarGetUbGlobal(var);
2362 	         assert(glb < gub);
2363 	
2364 	         if( !SCIPsetIsInfinity(set, -glb) && !SCIPsetIsInfinity(set, gub) )
2365 	            reldomainwidth = (ub - lb) / (gub - glb);
2366 	         else
2367 	            reldomainwidth = SCIPsetEpsilon(set);
2368 	
2369 	         if( reldomainwidth < set->branch_midpullreldomtrig )
2370 	            midpull *= reldomainwidth;
2371 	
2372 	         branchpoint = midpull * (lb+ub) / 2.0 + (1.0 - midpull) * branchpoint;
2373 	      }
2374 	
2375 	      /* make sure branchpoint is on interval, below we make sure that it is within bounds for continuous vars */
2376 	      branchpoint = MAX(lb, MIN(branchpoint, ub));
2377 	   }
2378 	
2379 	   /* if value is at +/- infty, then choose some value a bit off from bounds or 0.0 */
2380 	   if( SCIPsetIsInfinity(set, branchpoint) )
2381 	   {
2382 	      /* if value is at +infty, then the upper bound should be at infinity */
2383 	      assert(SCIPsetIsInfinity(set, ub));
2384 	
2385 	      /* choose 0.0 or something above lower bound if lower bound > 0 */
2386 	      if( SCIPsetIsPositive(set, lb) )
2387 	         branchpoint = lb + 1000.0;
2388 	      else
2389 	         branchpoint = 0.0;
2390 	   }
2391 	   else if( SCIPsetIsInfinity(set, -branchpoint) )
2392 	   { 
2393 	      /* if value is at -infty, then the lower bound should be at -infinity */
2394 	      assert(SCIPsetIsInfinity(set, -lb));
2395 	
2396 	      /* choose 0.0 or something below upper bound if upper bound < 0 */
2397 	      if( SCIPsetIsNegative(set, ub) )
2398 	         branchpoint = ub - 1000.0;
2399 	      else
2400 	         branchpoint = 0.0;
2401 	   }
2402 	
2403 	   assert(SCIPsetIsInfinity(set,  ub) || SCIPsetIsLE(set, branchpoint, ub));
2404 	   assert(SCIPsetIsInfinity(set, -lb) || SCIPsetIsGE(set, branchpoint, lb));
2405 	
2406 	   if( SCIPvarGetType(var) >= SCIP_VARTYPE_IMPLINT )
2407 	   {
2408 	      if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) )
2409 	      {
2410 	         /* if one bound is missing, we are temporarily guessing the other one, so we can apply the clamp below */
2411 	         if( SCIPsetIsInfinity(set, ub) )
2412 	         {
2413 	            ub = lb + MIN(MAX(0.5 * REALABS(lb), 1000), 0.9 * (SCIPsetInfinity(set) - lb)); /*lint !e666*/
2414 	         }
2415 	         else if( SCIPsetIsInfinity(set, -lb) )
2416 	         {
2417 	            lb = ub - MIN(MAX(0.5 * REALABS(ub), 1000), 0.9 * (SCIPsetInfinity(set) + ub)); /*lint !e666*/
2418 	         }
2419 	
2420 	         /* if branching point is too close to the bounds, move more into the middle of the interval */
2421 	         if( SCIPrelDiff(ub, lb) <= 2.02 * SCIPsetEpsilon(set) )
2422 	         {
2423 	            /* for very tiny intervals we set it exactly into the middle */
2424 	            branchpoint = (lb+ub)/2.0;
2425 	         }
2426 	         else
2427 	         {
2428 	            /* otherwise we project it away from the bounds */
2429 	            SCIP_Real minbrpoint;
2430 	            SCIP_Real maxbrpoint;
2431 	            SCIP_Real scale;
2432 	            SCIP_Real lbabs;
2433 	            SCIP_Real ubabs;
2434 	
2435 	            lbabs = REALABS(lb);
2436 	            ubabs = REALABS(ub);
2437 	
2438 	            scale = MAX3(lbabs, ubabs, 1.0);
2439 	
2440 	            /* the minimal branching point should be
2441 	             * - set->clamp away from the lower bound - relative to the local domain size
2442 	             * - SCIPsetEpsilon(set)*scale above the lower bound - in absolute value
2443 	             */
2444 	            minbrpoint = (1.0 - set->branch_clamp) * lb + set->branch_clamp * ub;
2445 	            minbrpoint = MAX(lb + 1.01*SCIPsetEpsilon(set)*scale, minbrpoint);  /*lint !e666*/
2446 	
2447 	            /* the maximal branching point should be
2448 	             * - set->clamp away from the upper bound - relative to the local domain size
2449 	             * - SCIPsetEpsilon(set)*scale below the upper bound - in absolute value
2450 	             */
2451 	            maxbrpoint = set->branch_clamp * lb + (1.0 - set->branch_clamp) * ub;
2452 	            maxbrpoint = MIN(ub - 1.01*SCIPsetEpsilon(set)*scale, maxbrpoint);  /*lint !e666*/
2453 	
2454 	            /* project branchpoint into [minbrpoint, maxbrpoint] */
2455 	            branchpoint = MAX(minbrpoint, MIN(branchpoint, maxbrpoint));
2456 	
2457 	            /* if selected branching point is close to 0.0 and bounds are away from 0.0, it often makes sense to branch exactly on 0.0 */
2458 	            if( SCIPsetIsFeasZero(set, branchpoint) && SCIPsetIsFeasNegative(set, lb) && SCIPsetIsFeasPositive(set, ub) )
2459 	               branchpoint = 0.0;
2460 	
2461 	            assert(SCIPsetIsRelLT(set, SCIPvarGetLbLocal(var), branchpoint));
2462 	            assert(SCIPsetIsRelLT(set, branchpoint, SCIPvarGetUbLocal(var)));
2463 	         }
2464 	      }
2465 	
2466 	      /* ensure fractional branching point for implicit integer variables */
2467 	      if( SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT && SCIPsetIsIntegral(set, branchpoint) )
2468 	      {
2469 	         /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */
2470 	         assert(SCIPsetIsGE(set, SCIPsetRound(set, branchpoint), lb + 1.0));
2471 	         assert(SCIPsetIsLE(set, SCIPsetRound(set, branchpoint), ub - 1.0));
2472 	         /* if branchpoint is integral, create one branch with x <= x'-1 and one with x >= x'
2473 	          * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better?
2474 	          */
2475 	         return branchpoint - 0.5;
2476 	      }
2477 	
2478 	      return branchpoint;
2479 	   }
2480 	   else
2481 	   {
2482 	      /* discrete variables */
2483 	      if( branchpoint <= lb + 0.5 )
2484 	      {
2485 	         /* if branchpoint is on lower bound, create one branch with x = lb and one with x >= lb+1 */
2486 	         return lb + 0.5;
2487 	      }
2488 	      else if( branchpoint >= ub - 0.5 )
2489 	      {
2490 	         /* if branchpoint is on upper bound, create one branch with x = ub and one with x <= ub-1 */
2491 	         return ub - 0.5;
2492 	      }
2493 	      else if( SCIPsetIsIntegral(set, branchpoint) )
2494 	      {
2495 	         /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */
2496 	         assert(SCIPsetIsGE(set, SCIPsetRound(set, branchpoint), lb + 1.0));
2497 	         assert(SCIPsetIsLE(set, SCIPsetRound(set, branchpoint), ub - 1.0));
2498 	         /* if branchpoint is integral, create one branch with x <= x'-1 and one with x >= x'
2499 	          * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better? */
2500 	         return branchpoint - 0.5;
2501 	      }
2502 	      else
2503 	      {
2504 	         /* branchpoint is somewhere between bounds and fractional, so just round down and up */
2505 	         return branchpoint;
2506 	      }
2507 	   }
2508 	}
2509 	
2510 	/** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
2511 	 *  if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
2512 	 *  variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
2513 	 */
2514 	SCIP_RETCODE SCIPbranchExecLP(
2515 	   BMS_BLKMEM*           blkmem,             /**< block memory for parameter settings */
2516 	   SCIP_SET*             set,                /**< global SCIP settings */
2517 	   SCIP_STAT*            stat,               /**< problem statistics */
2518 	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
2519 	   SCIP_PROB*            origprob,           /**< original problem */
2520 	   SCIP_TREE*            tree,               /**< branch and bound tree */
2521 	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
2522 	   SCIP_LP*              lp,                 /**< current LP data */
2523 	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
2524 	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
2525 	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
2526 	   SCIP_Real             cutoffbound,        /**< global upper cutoff bound */
2527 	   SCIP_Bool             allowaddcons,       /**< should adding constraints be allowed to avoid a branching? */
2528 	   SCIP_RESULT*          result              /**< pointer to store the result of the branching (s. branch.h) */
2529 	   )
2530 	{
2531 	   int i;
2532 	   int nalllpcands;  /* sum of binary, integer, and implicit branching candidates */
2533 	
2534 	   assert(branchcand != NULL);
2535 	   assert(result != NULL);
2536 	
2537 	   *result = SCIP_DIDNOTRUN;
2538 	
2539 	   /* calculate branching candidates */
2540 	   SCIP_CALL( branchcandCalcLPCands(branchcand, set, stat, lp) );
2541 	   assert(0 <= branchcand->npriolpcands && branchcand->npriolpcands <= branchcand->nlpcands);
2542 	   assert((branchcand->npriolpcands == 0) == (branchcand->nlpcands == 0));
2543 	
2544 	   SCIPsetDebugMsg(set, "branching on LP solution with %d (+%d) fractional (+implicit fractional) variables (%d of maximal priority)\n",
2545 	      branchcand->nlpcands, branchcand->nimpllpfracs, branchcand->npriolpcands);
2546 	
2547 	   nalllpcands = branchcand->nlpcands + branchcand->nimpllpfracs;
2548 	   /* do nothing, if no fractional variables exist */
2549 	   if( nalllpcands == 0 )
2550 	      return SCIP_OKAY;
2551 	
2552 	   /* if there is a non-fixed variable with higher priority than the maximal priority of the fractional candidates,
2553 	    * use pseudo solution branching instead
2554 	    */
2555 	   if( branchcand->pseudomaxpriority > branchcand->lpmaxpriority )
2556 	   {
2557 	      SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound,
2558 	            allowaddcons, result) );
2559 	      assert(*result != SCIP_DIDNOTRUN && *result != SCIP_DIDNOTFIND);
2560 	      return SCIP_OKAY;
2561 	   }
2562 	
2563 	   /* sort the branching rules by priority */
2564 	   SCIPsetSortBranchrules(set);
2565 	
2566 	   /* try all branching rules until one succeeded to branch */
2567 	   for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2568 	   {
2569 	      SCIP_CALL( SCIPbranchruleExecLPSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) );
2570 	   }
2571 	
2572 	   if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND )
2573 	   {
2574 	      SCIP_VAR* var;
2575 	      SCIP_Real factor;
2576 	      SCIP_Real bestfactor;
2577 	      int priority;
2578 	      int bestpriority;
2579 	      int bestcand;
2580 	
2581 	      /* no branching method succeeded in choosing a branching: just branch on the first fractional variable with maximal
2582 	       * priority, and out of these on the one with maximal branch factor
2583 	       */
2584 	      bestcand = -1;
2585 	      bestpriority = INT_MIN;
2586 	      bestfactor = SCIP_REAL_MIN;
2587 	      for( i = 0; i < nalllpcands; ++i )
2588 	      {
2589 	         priority = SCIPvarGetBranchPriority(branchcand->lpcands[i]);
2590 	         factor = SCIPvarGetBranchFactor(branchcand->lpcands[i]);
2591 	         if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) )
2592 	         {
2593 	            bestcand = i;
2594 	            bestpriority = priority;
2595 	            bestfactor = factor;
2596 	         }
2597 	      }
2598 	      assert(0 <= bestcand && bestcand < nalllpcands);
2599 	
2600 	      var = branchcand->lpcands[bestcand];
2601 	      assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
2602 	      assert(branchcand->nlpcands == 0 || SCIPvarGetType(var) != SCIP_VARTYPE_IMPLINT);
2603 	
2604 	      assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2605 	
2606 	      SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID,
2607 	            NULL, NULL, NULL) );
2608 	
2609 	      *result = SCIP_BRANCHED;
2610 	   }
2611 	
2612 	   return SCIP_OKAY;
2613 	}
2614 	
2615 	/** calls branching rules to branch on an external solution; if no external branching candidates exist, the result is SCIP_DIDNOTRUN */
2616 	SCIP_RETCODE SCIPbranchExecExtern(
2617 	   BMS_BLKMEM*           blkmem,             /**< block memory for parameter settings */
2618 	   SCIP_SET*             set,                /**< global SCIP settings */
2619 	   SCIP_STAT*            stat,               /**< problem statistics */
2620 	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
2621 	   SCIP_PROB*            origprob,           /**< original problem */
2622 	   SCIP_TREE*            tree,               /**< branch and bound tree */
2623 	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
2624 	   SCIP_LP*              lp,                 /**< current LP data */
2625 	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
2626 	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
2627 	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
2628 	   SCIP_Real             cutoffbound,        /**< global upper cutoff bound */
2629 	   SCIP_Bool             allowaddcons,       /**< should adding constraints be allowed to avoid a branching? */
2630 	   SCIP_RESULT*          result              /**< pointer to store the result of the branching (s. branch.h) */
2631 	   )
2632 	{
2633 	   int i;
2634 	
2635 	   assert(branchcand != NULL);
2636 	   assert(result != NULL);
2637 	   assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands);
2638 	   assert((branchcand->nprioexterncands == 0) == (branchcand->nexterncands == 0));
2639 	
2640 	   *result = SCIP_DIDNOTRUN;
2641 	
2642 	   SCIPsetDebugMsg(set, "branching on external solution with %d branching candidates (%d of maximal priority)\n",
2643 	      branchcand->nexterncands, branchcand->nprioexterncands);
2644 	
2645 	   /* do nothing, if no external candidates exist */
2646 	   if( branchcand->nexterncands == 0 )
2647 	      return SCIP_OKAY;
2648 	
2649 	   /* if there is a non-fixed variable with higher priority than the maximal priority of the external candidates,
2650 	    * use pseudo solution branching instead
2651 	    */
2652 	   if( branchcand->pseudomaxpriority > branchcand->externmaxpriority )
2653 	   {
2654 	      /* @todo: adjust this, that also LP branching might be called, if lpmaxpriority != externmaxpriority.
2655 	       * Therefor, it has to be clear which of both has the higher priority
2656 	       */
2657 	      SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound,
2658 	            allowaddcons, result) );
2659 	      assert(*result != SCIP_DIDNOTRUN && *result != SCIP_DIDNOTFIND);
2660 	      return SCIP_OKAY;
2661 	   }
2662 	
2663 	   /* sort the branching rules by priority */
2664 	   SCIPsetSortBranchrules(set);
2665 	
2666 	   /* try all branching rules until one succeeded to branch */
2667 	   for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2668 	   {
2669 	      SCIP_CALL( SCIPbranchruleExecExternSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) );
2670 	   }
2671 	
2672 	   if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND )
2673 	   {
2674 	      SCIP_VAR* var;
2675 	      SCIP_Real val;
2676 	      SCIP_Real bestfactor;
2677 	      SCIP_Real bestdomain;
2678 	      int bestpriority;
2679 	      int bestcand;
2680 	
2681 	      /* if all branching rules did nothing, then they should also not have cleared all branching candidates */
2682 	      assert(branchcand->nexterncands > 0);
2683 	
2684 	      /* no branching method succeeded in choosing a branching: just branch on the first branching candidates with maximal
2685 	       * priority, and out of these on the one with maximal branch factor, and out of these on the one with largest domain
2686 	       */
2687 	      bestcand = -1;
2688 	      bestpriority = INT_MIN;
2689 	      bestfactor = SCIP_REAL_MIN;
2690 	      bestdomain = 0.0;
2691 	      for( i = 0; i < branchcand->nexterncands; ++i )
2692 	      {
2693 	         SCIP_VAR* cand;
2694 	         SCIP_Real domain;
2695 	         SCIP_Real factor;
2696 	         int priority;
2697 	
2698 	         cand = branchcand->externcands[i];
2699 	         priority = SCIPvarGetBranchPriority(cand);
2700 	         factor = SCIPvarGetBranchFactor(cand);
2701 	
2702 	         /* the domain size is infinite, iff one of the bounds is infinite */
2703 	         if( SCIPsetIsInfinity(set, -SCIPvarGetLbLocal(cand)) || SCIPsetIsInfinity(set, SCIPvarGetUbLocal(cand)) )
2704 	            domain = SCIPsetInfinity(set);
2705 	         else
2706 	            domain = SCIPvarGetUbLocal(cand) - SCIPvarGetLbLocal(cand);
2707 	
2708 	         /* choose variable with higher priority, higher factor, larger domain (in that order) */
2709 	         if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) || (priority == bestpriority && factor == bestfactor && domain > bestdomain) ) /*lint !e777*/
2710 	         {
2711 	            bestcand = i;
2712 	            bestpriority = priority;
2713 	            bestfactor = factor;
2714 	            bestdomain = domain;
2715 	         }
2716 	      }
2717 	      assert(0 <= bestcand && bestcand < branchcand->nexterncands);
2718 	
2719 	      var = branchcand->externcands[bestcand];
2720 	      val = SCIPbranchGetBranchingPoint(set, tree, var, branchcand->externcandssol[bestcand]);
2721 	      assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2722 	      assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set)
2723 	         || SCIPsetIsLT(set, SCIPvarGetLbLocal(var), val));
2724 	      assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set)
2725 	         || SCIPsetIsLT(set, val, SCIPvarGetUbLocal(var)));
2726 	
2727 	      SCIPsetDebugMsg(set, "no branching method succeeded; fallback selected to branch on variable <%s> with bounds [%g, %g] on value %g\n",
2728 	         SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), val);
2729 	
2730 	      SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, val,
2731 	            NULL, NULL, NULL) );
2732 	
2733 	      if( tree->nchildren >= 1 )
2734 	         *result = SCIP_BRANCHED;
2735 	      /* if the bounds are too close, it may happen that we cannot branch but rather fix the variable */
2736 	      else
2737 	      {
2738 	         assert(SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2739 	         *result = SCIP_REDUCEDDOM;
2740 	      }
2741 	   }
2742 	
2743 	   return SCIP_OKAY;
2744 	}
2745 	
2746 	/** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN */
2747 	SCIP_RETCODE SCIPbranchExecPseudo(
2748 	   BMS_BLKMEM*           blkmem,             /**< block memory for parameter settings */
2749 	   SCIP_SET*             set,                /**< global SCIP settings */
2750 	   SCIP_STAT*            stat,               /**< problem statistics */
2751 	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
2752 	   SCIP_PROB*            origprob,           /**< original problem */
2753 	   SCIP_TREE*            tree,               /**< branch and bound tree */
2754 	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
2755 	   SCIP_LP*              lp,                 /**< current LP data */
2756 	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
2757 	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
2758 	   SCIP_Real             cutoffbound,        /**< global upper cutoff bound */
2759 	   SCIP_Bool             allowaddcons,       /**< should adding constraints be allowed to avoid a branching? */
2760 	   SCIP_RESULT*          result              /**< pointer to store the result of the branching (s. branch.h) */
2761 	   )
2762 	{
2763 	   int i;
2764 	
2765 	   assert(branchcand != NULL);
2766 	   assert(result != NULL);
2767 	
2768 	   SCIPsetDebugMsg(set, "branching on pseudo solution with %d unfixed variables\n", branchcand->npseudocands);
2769 	
2770 	   *result = SCIP_DIDNOTRUN;
2771 	
2772 	   /* do nothing, if no unfixed variables exist */
2773 	   if( branchcand->npseudocands == 0 )
2774 	      return SCIP_OKAY;
2775 	
2776 	   /* sort the branching rules by priority */
2777 	   SCIPsetSortBranchrules(set);
2778 	
2779 	   /* try all branching rules until one succeeded to branch */
2780 	   for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2781 	   {
2782 	      SCIP_CALL( SCIPbranchruleExecPseudoSol(set->branchrules[i], set, stat, tree, cutoffbound, allowaddcons, result) );
2783 	   }
2784 	
2785 	   if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND )
2786 	   {
2787 	      SCIP_VAR* var;
2788 	      SCIP_Real factor;
2789 	      SCIP_Real bestfactor;
2790 	      int priority;
2791 	      int bestpriority;
2792 	      int bestcand;
2793 	
2794 	      /* no branching method succeeded in choosing a branching: just branch on the first unfixed variable with maximal
2795 	       * priority, and out of these on the one with maximal branch factor
2796 	       */
2797 	      bestcand = -1;
2798 	      bestpriority = INT_MIN;
2799 	      bestfactor = SCIP_REAL_MIN;
2800 	      for( i = 0; i < branchcand->npseudocands; ++i )
2801 	      {
2802 	         priority = SCIPvarGetBranchPriority(branchcand->pseudocands[i]);
2803 	         factor = SCIPvarGetBranchFactor(branchcand->pseudocands[i]);
2804 	         if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) )
2805 	         {
2806 	            bestcand = i;
2807 	            bestpriority = priority;
2808 	            bestfactor = factor;
2809 	         }
2810 	      }
2811 	      assert(0 <= bestcand && bestcand < branchcand->npseudocands);
2812 	
2813 	      var = branchcand->pseudocands[bestcand];
2814 	      assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
2815 	      assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2816 	
2817 	      SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID,
2818 	            NULL, NULL, NULL) );
2819 	
2820 	      *result = SCIP_BRANCHED;
2821 	   }
2822 	
2823 	   return SCIP_OKAY;
2824 	}
2825 	
2826