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_relpscost.c
26   	 * @ingroup DEFPLUGINS_BRANCH
27   	 * @brief  reliable pseudo costs branching rule
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 * @author Gerald Gamrath
31   	 * @author Marc Pfetsch
32   	 */
33   	
34   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35   	
36   	#include "blockmemshell/memory.h"
37   	#include "scip/branch_relpscost.h"
38   	#include "scip/treemodel.h"
39   	#include "scip/cons_and.h"
40   	#include "scip/pub_branch.h"
41   	#include "scip/pub_cons.h"
42   	#include "scip/pub_message.h"
43   	#include "scip/pub_misc.h"
44   	#include "scip/pub_sol.h"
45   	#include "scip/pub_tree.h"
46   	#include "scip/pub_var.h"
47   	#include "scip/scip_branch.h"
48   	#include "scip/scip_cons.h"
49   	#include "scip/scip_general.h"
50   	#include "scip/scip_lp.h"
51   	#include "scip/scip_mem.h"
52   	#include "scip/scip_message.h"
53   	#include "scip/scip_nlp.h"
54   	#include "scip/scip_numerics.h"
55   	#include "scip/scip_param.h"
56   	#include "scip/scip_prob.h"
57   	#include "scip/scip_randnumgen.h"
58   	#include "scip/scip_sol.h"
59   	#include "scip/scip_solvingstats.h"
60   	#include "scip/scip_tree.h"
61   	#include "scip/scip_var.h"
62   	#include "scip/prop_symmetry.h"
63   	#include "scip/symmetry.h"
64   	#include <string.h>
65   	
66   	#define BRANCHRULE_NAME          "relpscost"
67   	#define BRANCHRULE_DESC          "reliability branching on pseudo cost values"
68   	#define BRANCHRULE_PRIORITY      10000
69   	#define BRANCHRULE_MAXDEPTH      -1
70   	#define BRANCHRULE_MAXBOUNDDIST  1.0
71   	
72   	#define DEFAULT_CONFLICTWEIGHT   0.01        /**< weight in score calculations for conflict score */
73   	#define DEFAULT_CONFLENGTHWEIGHT 0.0         /**< weight in score calculations for conflict length score*/
74   	#define DEFAULT_INFERENCEWEIGHT  0.0001      /**< weight in score calculations for inference score */
75   	#define DEFAULT_CUTOFFWEIGHT     0.0001      /**< weight in score calculations for cutoff score */
76   	#define DEFAULT_GMIAVGEFFWEIGHT  0.0         /**< weight in score calculations of average GMI cut normed efficacies */
77   	#define DEFAULT_GMILASTEFFWEIGHT 0.00001     /**< weight in score calculations of last GMI cut normed efficacy */
78   	#define DEFAULT_PSCOSTWEIGHT     1.0         /**< weight in score calculations for pseudo cost score */
79   	#define DEFAULT_NLSCOREWEIGHT    0.1         /**< weight in score calculations for nlcount score */
80   	#define DEFAULT_MINRELIABLE      1.0         /**< minimal value for minimum pseudo cost size to regard pseudo cost value as reliable */
81   	#define DEFAULT_MAXRELIABLE      5.0         /**< maximal value for minimum pseudo cost size to regard pseudo cost value as reliable */
82   	#define DEFAULT_SBITERQUOT       0.5         /**< maximal fraction of strong branching LP iterations compared to normal iterations */
83   	#define DEFAULT_SBITEROFS        100000      /**< additional number of allowed strong branching LP iterations */
84   	#define DEFAULT_MAXLOOKAHEAD     9           /**< maximal number of further variables evaluated without better score */
85   	#define DEFAULT_INITCAND         100         /**< maximal number of candidates initialized with strong branching per node */
86   	#define DEFAULT_INITITER         0           /**< iteration limit for strong branching initialization of pseudo cost entries (0: auto) */
87   	#define DEFAULT_MAXBDCHGS        5           /**< maximal number of bound tightenings before the node is reevaluated (-1: unlimited) */
88   	#define DEFAULT_MAXPROPROUNDS   -2           /**< maximum number of propagation rounds to be performed during strong branching
89   	                                              *   before solving the LP (-1: no limit, -2: parameter settings) */
90   	#define DEFAULT_PROBINGBOUNDS    TRUE        /**< should valid bounds be identified in a probing-like fashion during strong
91   	                                              *   branching (only with propagation)? */
92   	#define DEFAULT_USERELERRORFORRELIABILITY FALSE /**< should reliability be based on relative errors? */
93   	#define DEFAULT_LOWERRORTOL      0.05        /**< lowest tolerance beneath which relative errors are reliable */
94   	#define DEFAULT_HIGHERRORTOL     1.0         /**< highest tolerance beneath which relative errors are reliable */
95   	#define DEFAULT_USEHYPTESTFORRELIABILITY FALSE /**< should the strong branching decision be based on a hypothesis test? */
96   	#define DEFAULT_USEDYNAMICCONFIDENCE FALSE   /**< should the confidence level be adjusted dynamically? */
97   	#define DEFAULT_STORESEMIINITCOSTS FALSE     /**< should strong branching result be considered for pseudo costs if the other direction was infeasible? */
98   	#define DEFAULT_USESBLOCALINFO   FALSE       /**< should the scoring function use only local cutoff and inference information obtained for strong branching candidates? */
99   	#define DEFAULT_CONFIDENCELEVEL  2           /**< The confidence level for statistical methods, between 0 (Min) and 4 (Max). */
100  	#define DEFAULT_SKIPBADINITCANDS TRUE        /**< should branching rule skip candidates that have a low probability to be
101  	                                              *  better than the best strong-branching or pseudo-candidate? */
102  	#define DEFAULT_STARTRANDSEED    5           /**< start random seed for random number generation */
103  	#define DEFAULT_RANDINITORDER    FALSE       /**< should slight perturbation of scores be used to break ties in the prior scores? */
104  	#define DEFAULT_USESMALLWEIGHTSITLIM FALSE   /**< should smaller weights be used for pseudo cost updates after hitting the LP iteration limit? */
105  	#define DEFAULT_DYNAMICWEIGHTS   TRUE        /**< should the weights of the branching rule be adjusted dynamically during solving based
106  	                                              *   infeasible and objective leaf counters? */
107  	#define DEFAULT_DEGENERACYAWARE  1           /**< should degeneracy be taken into account to update weights and skip strong branching? (0: off, 1: after root, 2: always)*/
108  	
109  	/* symmetry handling */
110  	#define DEFAULT_FILTERCANDSSYM   FALSE       /**< Use symmetry to filter branching candidates? */
111  	#define DEFAULT_TRANSSYMPSCOST   FALSE       /**< Transfer pscost information to symmetric variables if filtering is performed? */
112  	
113  	/** branching rule data */
114  	struct SCIP_BranchruleData
115  	{
116  	   SCIP_Real             conflictweight;     /**< weight in score calculations for conflict score */
117  	   SCIP_Real             conflengthweight;   /**< weight in score calculations for conflict length score */
118  	   SCIP_Real             inferenceweight;    /**< weight in score calculations for inference score */
119  	   SCIP_Real             cutoffweight;       /**< weight in score calculations for cutoff score */
120  	   SCIP_Real             gmiavgeffweight;    /**< weight in score calculations of average GMI normed cut efficacies */
121  	   SCIP_Real             gmilasteffweight;   /**< weight in score calculations of last GMI cut normalized efficacy */
122  	   SCIP_Real             pscostweight;       /**< weight in score calculations for pseudo cost score */
123  	   SCIP_Real             nlscoreweight;      /**< weight in score calculations for nlcount score */
124  	   SCIP_Real             minreliable;        /**< minimal value for minimum pseudo cost size to regard pseudo cost value as reliable */
125  	   SCIP_Real             maxreliable;        /**< maximal value for minimum pseudo cost size to regard pseudo cost value as reliable */
126  	   SCIP_Real             sbiterquot;         /**< maximal fraction of strong branching LP iterations compared to normal iterations */
127  	   int                   sbiterofs;          /**< additional number of allowed strong branching LP iterations */
128  	   int                   maxlookahead;       /**< maximal number of further variables evaluated without better score */
129  	   int                   initcand;           /**< maximal number of candidates initialized with strong branching per node */
130  	   int                   inititer;           /**< iteration limit for strong branching initialization of pseudo cost entries (0: auto) */
131  	   int                   maxbdchgs;          /**< maximal number of bound tightenings before the node is reevaluated (-1: unlimited) */
132  	   int                   maxproprounds;      /**< maximum number of propagation rounds to be performed during strong branching
133  	                                              *   before solving the LP (-1: no limit, -2: parameter settings) */
134  	   SCIP_Bool             probingbounds;      /**< should valid bounds be identified in a probing-like fashion during strong
135  	                                              *   branching (only with propagation)? */
136  	   SCIP_Bool             userelerrorforreliability; /**< should reliability be based on relative errors? */
137  	   SCIP_Real             lowerrortol;        /**< lowest tolerance beneath which relative errors are reliable */
138  	   SCIP_Real             higherrortol;       /**< highest tolerance beneath which relative errors are reliable */
139  	   SCIP_Bool             usehyptestforreliability; /**< should the strong branching decision be based on a hypothesis test? */
140  	   SCIP_Bool             usedynamicconfidence; /**< should the confidence level be adjusted dynamically? */
141  	   SCIP_Bool             storesemiinitcosts; /**< should strong branching result be considered for pseudo costs if the
142  	                                              *   other direction was infeasible? */
143  	   SCIP_Bool             usesblocalinfo;     /**< should the scoring function disregard cutoffs for variable if sb-lookahead was feasible ? */
144  	   SCIP_Bool             skipbadinitcands;   /**< should branching rule skip candidates that have a low probability to be
145  	                                               *  better than the best strong-branching or pseudo-candidate? */
146  	   SCIP_Bool             dynamicweights;     /**< should the weights of the branching rule be adjusted dynamically during
147  	                                              *   solving based on objective and infeasible leaf counters? */
148  	   int                   degeneracyaware;    /**< should degeneracy be taken into account to update weights and skip strong branching? (0: off, 1: after root, 2: always) */
149  	   int                   confidencelevel;    /**< The confidence level for statistical methods, between 0 (Min) and 4 (Max). */
150  	   int*                  nlcount;            /**< array to store nonlinear count values */
151  	   int                   nlcountsize;        /**< length of nlcount array */
152  	   int                   nlcountmax;         /**< maximum entry in nlcount array or 1 if NULL */
153  	   SCIP_Bool             randinitorder;      /**< should slight perturbation of scores be used to break ties in the prior scores? */
154  	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator */
155  	   int                   startrandseed;      /**< start random seed for random number generation */
156  	   SCIP_Bool             usesmallweightsitlim; /**< should smaller weights be used for pseudo cost updates after hitting the LP iteration limit? */
157  	   SCIP_TREEMODEL*       treemodel;          /**< Parameters for the Treemodel branching rules */
158  	
159  	   /* for symmetry */
160  	   SCIP_Bool             filtercandssym;     /**< Use symmetry to filter branching candidates? */
161  	   SCIP_Bool             transsympscost;     /**< Transfer pscost information to symmetric variables? */
162  	
163  	   SCIP_Bool             nosymmetry;         /**< No symmetry present? */
164  	   int*                  orbits;             /**< array of non-trivial orbits */
165  	   int*                  orbitbegins;        /**< array containing begin positions of new orbits in orbits array */
166  	   int                   norbits;            /**< pointer to number of orbits currently stored in orbits */
167  	   int*                  varorbitmap;        /**< array for storing indices of the containing orbit for each variable */
168  	   int*                  orbitrep;           /**< representative variable of each orbit */
169  	   SCIP_VAR**            permvars;           /**< variables on which permutations act */
170  	   int                   npermvars;          /**< number of variables for permutations */
171  	   SCIP_HASHMAP*         permvarmap;         /**< map of variables to indices in permvars array */
172  	};
173  	
174  	/*
175  	 * local methods
176  	 */
177  	
178  	/** initialize orbits */
179  	static
180  	SCIP_RETCODE initOrbits(
181  	   SCIP*                 scip,               /**< SCIP data structure */
182  	   SCIP_BRANCHRULEDATA*  branchruledata      /**< branching rule data */
183  	   )
184  	{
185  	   int** permstrans = NULL;
186  	   int* components = NULL;
187  	   int* componentbegins = NULL;
188  	   int* vartocomponent = NULL;
189  	   int ncomponents = 0;
190  	   int nperms = -1;
191  	
192  	   assert( scip != NULL );
193  	   assert( branchruledata != NULL );
194  	   assert( branchruledata->filtercandssym );
195  	
196  	   /* exit if no symmetry or orbits already available */
197  	   if( branchruledata->nosymmetry || branchruledata->orbits != NULL )
198  	      return SCIP_OKAY;
199  	
200  	   assert( branchruledata->orbitbegins ==  NULL );
201  	   assert( branchruledata->varorbitmap == NULL );
202  	   assert( branchruledata->orbitrep == NULL );
203  	
204  	   /* obtain symmetry including permutations */
205  	   SCIP_CALL( SCIPgetSymmetry(scip, &branchruledata->npermvars, &branchruledata->permvars, &branchruledata->permvarmap,
206  	         &nperms, NULL, &permstrans, NULL, NULL, &components, &componentbegins, &vartocomponent, &ncomponents) );
207  	
208  	   /* turn off symmetry handling if there is no symmetry or the number of variables is not equal */
209  	   if( nperms <= 0 || branchruledata->npermvars != SCIPgetNVars(scip) )
210  	   {
211  	      branchruledata->nosymmetry = TRUE;
212  	      return SCIP_OKAY;
213  	   }
214  	   assert( branchruledata->permvars != NULL );
215  	   assert( branchruledata->permvarmap != NULL );
216  	   assert( branchruledata->npermvars > 0 );
217  	   assert( permstrans != NULL );
218  	   assert( components != NULL );
219  	   assert( componentbegins != NULL );
220  	   assert( vartocomponent != NULL );
221  	   assert( ncomponents > 0 );
222  	
223  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->orbits, branchruledata->npermvars) );
224  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->orbitbegins, branchruledata->npermvars) );
225  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->varorbitmap, branchruledata->npermvars) );
226  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->orbitrep, branchruledata->npermvars) );
227  	
228  	   /* Compute orbits on all variables, since this might help for branching and this computation is only done once. */
229  	   SCIP_CALL( SCIPcomputeOrbitsComponentsSym(scip, branchruledata->npermvars, permstrans, nperms,
230  	         components, componentbegins, vartocomponent, ncomponents,
231  	         branchruledata->orbits, branchruledata->orbitbegins, &branchruledata->norbits, branchruledata->varorbitmap) );
232  	   assert( branchruledata->norbits < branchruledata->npermvars );
233  	
234  	   return SCIP_OKAY;
235  	}
236  	
237  	/** filter out symmetric variables from branching variables */
238  	static
239  	SCIP_RETCODE filterSymmetricVariables(
240  	   SCIP*                 scip,               /**< SCIP data structure */
241  	   SCIP_BRANCHRULEDATA*  branchruledata,     /**< branching rule data */
242  	   SCIP_VAR**            origbranchcands,    /**< original branching candidates */
243  	   SCIP_Real*            origbranchcandssol, /**< original solution value for the branching candidates */
244  	   SCIP_Real*            origbranchcandsfrac,/**< original fractional part of the branching candidates */
245  	   int                   norigbranchcands,   /**< original number of branching candidates */
246  	   SCIP_VAR**            branchcands,        /**< branching candidates */
247  	   SCIP_Real*            branchcandssol,     /**< solution value for the branching candidates */
248  	   SCIP_Real*            branchcandsfrac,    /**< fractional part of the branching candidates */
249  	   int*                  branchorbitidx,     /**< array of indices of orbit of branching candidates */
250  	   int*                  nbranchcands        /**< pointer to store number of branching candidates */
251  	   )
252  	{
253  	   int i;
254  	
255  	   assert( scip != NULL );
256  	   assert( branchruledata != NULL );
257  	   assert( origbranchcands != NULL );
258  	   assert( origbranchcandssol != NULL );
259  	   assert( origbranchcandsfrac != NULL );
260  	   assert( branchcands != NULL );
261  	   assert( branchcandssol != NULL );
262  	   assert( branchcandsfrac != NULL );
263  	   assert( nbranchcands != NULL );
264  	
265  	   assert( ! branchruledata->nosymmetry );
266  	   assert( branchruledata->orbitbegins != NULL );
267  	   assert( branchruledata->orbits != NULL );
268  	   assert( branchruledata->permvarmap != NULL );
269  	   assert( branchruledata->varorbitmap != NULL );
270  	   assert( branchruledata->orbitrep != NULL );
271  	   assert( branchruledata->norbits < branchruledata->npermvars );
272  	
273  	   /* init representatives (used to see whether variable is the first in an orbit) */
274  	   for( i = 0; i < branchruledata->norbits; ++i )
275  	      branchruledata->orbitrep[i] = -1;
276  	
277  	   /* loop through branching variables, determine orbit and whether they are the first ones */
278  	   *nbranchcands = 0;
279  	   for( i = 0; i < norigbranchcands; ++i )
280  	   {
281  	      int orbitidx = -1;
282  	      int varidx;
283  	
284  	      varidx = SCIPhashmapGetImageInt(branchruledata->permvarmap, (void*) origbranchcands[i]);
285  	      if( varidx != INT_MAX )
286  	      {
287  	         assert( 0 <= varidx && varidx < branchruledata->npermvars );
288  	         orbitidx = branchruledata->varorbitmap[varidx];
289  	      }
290  	      assert( -1 <= orbitidx && orbitidx < branchruledata->norbits );
291  	
292  	      /* Check whether the variable is not present (can happen if variable was added after computing symmetries or is in
293  	       * a singleton orbit). */
294  	      if( orbitidx == -1 )
295  	      {
296  	         branchcands[*nbranchcands] = origbranchcands[i];
297  	         branchcandssol[*nbranchcands] = origbranchcandssol[i];
298  	         branchcandsfrac[*nbranchcands] = origbranchcandsfrac[i];
299  	         branchorbitidx[*nbranchcands] = -1;
300  	         ++(*nbranchcands);
301  	      }
302  	      else if( branchruledata->orbitrep[orbitidx] == -1 )
303  	      {
304  	         /* if variable is the first in a nontrivial orbit */
305  	         assert( 0 <= varidx && varidx < branchruledata->npermvars );
306  	         branchruledata->orbitrep[orbitidx] = varidx;
307  	         branchcands[*nbranchcands] = origbranchcands[i];
308  	         branchcandssol[*nbranchcands] = origbranchcandssol[i];
309  	         branchcandsfrac[*nbranchcands] = origbranchcandsfrac[i];
310  	         branchorbitidx[*nbranchcands] = orbitidx;
311  	         ++(*nbranchcands);
312  	      }
313  	   }
314  	
315  	   SCIPdebugMsg(scip, "Filtered out %d variables by symmetry.\n", norigbranchcands - *nbranchcands);
316  	
317  	   return SCIP_OKAY;
318  	}
319  	
320  	/** updates the pseudo costs of the given variable and all its symmetric variables */
321  	static
322  	SCIP_RETCODE SCIPupdateVarPseudocostSymmetric(
323  	   SCIP*                 scip,               /**< SCIP data structure */
324  	   SCIP_BRANCHRULEDATA*  branchruledata,     /**< branching rule data */
325  	   SCIP_VAR*             branchvar,          /**< branching variable candidate */
326  	   int*                  branchorbitidx,     /**< array of orbit indices */
327  	   int                   branchvaridx,       /**< index of variable in branchorbitidx */
328  	   SCIP_Real             solvaldelta,        /**< difference of variable's new LP value - old LP value */
329  	   SCIP_Real             objdelta,           /**< difference of new LP's objective value - old LP's objective value */
330  	   SCIP_Real             weight              /**< weight in (0,1] of this update in pseudo cost sum */
331  	   )
332  	{
333  	   int orbitidx;
334  	   int j;
335  	
336  	   assert( scip != NULL );
337  	   assert( branchruledata != NULL );
338  	
339  	   if( branchruledata->nosymmetry || ! branchruledata->transsympscost || branchorbitidx == NULL )
340  	   {
341  	      /* use original update function */
342  	      SCIP_CALL( SCIPupdateVarPseudocost(scip, branchvar, solvaldelta, objdelta, weight) );
343  	      return SCIP_OKAY;
344  	   }
345  	
346  	   assert( branchruledata->orbitbegins != NULL );
347  	   assert( branchruledata->orbits != NULL );
348  	   assert( 0 <= branchvaridx && branchvaridx < branchruledata->npermvars );
349  	
350  	   orbitidx = branchorbitidx[branchvaridx];
351  	   if( orbitidx < 0 )
352  	   {
353  	      /* only update given variable */
354  	      SCIP_CALL( SCIPupdateVarPseudocost(scip, branchvar, solvaldelta, objdelta, weight) );
355  	      return SCIP_OKAY;
356  	   }
357  	   assert( 0 <= orbitidx && orbitidx < branchruledata->norbits );
358  	
359  	   /* loop through orbit containing variable and update pseudo costs for all variables */
360  	   for( j = branchruledata->orbitbegins[orbitidx]; j < branchruledata->orbitbegins[orbitidx+1]; ++j )
361  	   {
362  	      SCIP_VAR* var;
363  	      int idx;
364  	
365  	      idx = branchruledata->orbits[j];
366  	      assert( 0 <= idx && idx < branchruledata->npermvars );
367  	
368  	      var = branchruledata->permvars[idx];
369  	      assert( var != NULL );
370  	
371  	      if( SCIPvarIsActive(var) )
372  	      {
373  	         SCIP_CALL( SCIPupdateVarPseudocost(scip, var, solvaldelta, objdelta, weight) );
374  	      }
375  	   }
376  	
377  	   return SCIP_OKAY;
378  	}
379  	
380  	/**! [SnippetCodeStyleStaticAsserts] */
381  	
382  	/** return probindex of variable or corresponding active variable (if negated or aggregated) or -1 (if multiaggregated) */
383  	static
384  	SCIP_RETCODE binvarGetActiveProbindex(
385  	   SCIP*                 scip,               /**< SCIP data structure */
386  	   SCIP_VAR*             var,                /**< binary variable */
387  	   int*                  probindex           /**< buffer to store probindex */
388  	   )
389  	{
390  	   assert(scip != NULL);
391  	   assert(var != NULL);
392  	   assert(SCIPvarIsBinary(var));
393  	   assert(probindex != NULL);
394  	
395  	/**! [SnippetCodeStyleStaticAsserts] */
396  	
397  	   *probindex = SCIPvarGetProbindex(var);
398  	
399  	   /* if variable is not active, try to find active representative */
400  	   if( *probindex == -1 )
401  	   {
402  	      SCIP_VAR* repvar;
403  	      SCIP_Bool negated;
404  	
405  	      SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
406  	      assert(repvar != NULL);
407  	      assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
408  	
409  	      if( SCIPvarIsActive(repvar) )
410  	         *probindex = SCIPvarGetProbindex(repvar);
411  	      else if( SCIPvarIsNegated(repvar) )
412  	         *probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
413  	   }
414  	
415  	   return SCIP_OKAY;
416  	}
417  	
418  	/**! [SnippetCodeStyleDeclaration] */
419  	
420  	/** counts number of nonlinear constraints in which each variable appears */
421  	static
422  	SCIP_RETCODE countNonlinearities(
423  	   SCIP*                 scip,               /**< SCIP data structure */
424  	   int*                  nlcount,            /**< pointer to array for storing count values */
425  	   int                   nlcountsize,        /**< buffer for storing length of nlcount array */
426  	   int*                  nlcountmax          /**< buffer for storing maximum value in nlcount array */
427  	   )
428  	{
429  	   SCIP_CONSHDLR* andconshdlr;
430  	   SCIP_VAR** vars;
431  	   int nvars;
432  	   int i;
433  	
434  	/**! [SnippetCodeStyleDeclaration] */
435  	
436  	   assert(scip != NULL);
437  	   assert(nlcount != NULL);
438  	   assert(nlcountmax != NULL);
439  	
440  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
441  	   assert(nlcountsize >= nvars);
442  	
443  	   /* get nonlinearity for constraints in NLP */
444  	   if( SCIPisNLPConstructed(scip) )
445  	   {
446  	      assert(SCIPgetNNLPVars(scip) == nvars);
447  	      SCIP_CALL( SCIPgetNLPVarsNonlinearity(scip, nlcount) );
448  	   }
449  	   else
450  	   {
451  	      BMSclearMemoryArray(nlcount, nvars);
452  	   }
453  	
454  	   /* increase counters for and constraints */
455  	   andconshdlr = SCIPfindConshdlr(scip, "and");
456  	   if( andconshdlr != NULL )
457  	   {
458  	      int c;
459  	
460  	      for( c = 0; c < SCIPconshdlrGetNActiveConss(andconshdlr); c++ )
461  	      {
462  	         SCIP_CONS* andcons;
463  	         SCIP_VAR** andvars;
464  	         SCIP_VAR* andres;
465  	         int probindex;
466  	         int nandvars;
467  	         int v;
468  	
469  	         /* get constraint and variables */
470  	         andcons = SCIPconshdlrGetConss(andconshdlr)[c];
471  	         nandvars = SCIPgetNVarsAnd(scip, andcons);
472  	         andvars = SCIPgetVarsAnd(scip, andcons);
473  	         andres = SCIPgetResultantAnd(scip, andcons);
474  	
475  	         probindex = -1;
476  	
477  	         /**! [SnippetCodeStyleIfFor] */
478  	
479  	         for( v = 0; v < nandvars; v++ )
480  	         {
481  	            /* don't rely on the and conshdlr removing fixed variables
482  	             * @todo fix the and conshdlr in that respect
483  	             */
484  	            if( SCIPvarGetStatus(andvars[v]) != SCIP_VARSTATUS_FIXED )
485  	            {
486  	               SCIP_CALL( binvarGetActiveProbindex(scip, andvars[v], &probindex) );
487  	               if( probindex >= 0 )
488  	                  nlcount[probindex]++;
489  	            }
490  	         }
491  	
492  	         /**! [SnippetCodeStyleIfFor] */
493  	
494  	         SCIP_CALL( binvarGetActiveProbindex(scip, andres, &probindex) );
495  	         if( probindex >= 0 )
496  	            nlcount[probindex]++;
497  	      }
498  	   }
499  	
500  	   /* compute maximum count value */
501  	   *nlcountmax = 1;
502  	   for( i = 0; i < nvars; i++ )
503  	   {
504  	      if( *nlcountmax < nlcount[i] )
505  	         *nlcountmax = nlcount[i];
506  	   }
507  	
508  	   return SCIP_OKAY;
509  	}
510  	
511  	static
512  	SCIP_RETCODE branchruledataEnsureNlcount(
513  	   SCIP*                 scip,               /**< SCIP data structure */
514  	   SCIP_BRANCHRULEDATA*  branchruledata      /**< branching rule data */
515  	   )
516  	{
517  	   int nvars;
518  	
519  	   assert(scip != NULL);
520  	   assert(branchruledata != NULL);
521  	
522  	   nvars = SCIPgetNVars(scip);
523  	
524  	   /**@todo test whether we want to apply this as if problem has only and constraints */
525  	   /**@todo update changes in and constraints */
526  	   if( branchruledata->nlscoreweight > 0.0 ) /*  && SCIPisNLPConstructed(scip) */
527  	   {
528  	      if( branchruledata->nlcount == NULL )
529  	      {
530  	         SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->nlcount, nvars) );
531  	         branchruledata->nlcountsize = nvars;
532  	
533  	         SCIP_CALL( countNonlinearities(scip, branchruledata->nlcount, branchruledata->nlcountsize, &branchruledata->nlcountmax) );
534  	      }
535  	      else if( branchruledata->nlcountsize < nvars )
536  	      {
537  	         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->nlcount, branchruledata->nlcountsize, nvars) );
538  	         /**@todo should we update nlcounts for new variables? */
539  	         BMSclearMemoryArray(&(branchruledata->nlcount[branchruledata->nlcountsize]), nvars - branchruledata->nlcountsize); /*lint !e866*/
540  	         branchruledata->nlcountsize = nvars;
541  	      }
542  	      assert(branchruledata->nlcount != NULL);
543  	      assert(branchruledata->nlcountsize == nvars);
544  	      assert(branchruledata->nlcountmax >= 1);
545  	   }
546  	   else
547  	   {
548  	      SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->nlcount, branchruledata->nlcountsize);
549  	      branchruledata->nlcountsize = 0;
550  	      branchruledata->nlcountmax = 1;
551  	   }
552  	
553  	   return SCIP_OKAY;
554  	}
555  	
556  	
557  	/** calculates nlscore value between 0 and 1 */
558  	static
559  	SCIP_Real calcNlscore(
560  	   SCIP*                 scip,               /**< SCIP data structure */
561  	   int*                  nlcount,            /**< array to store count values */
562  	   int                   nlcountmax,         /**< maximum value in nlcount array */
563  	   int                   probindex           /**< index of branching candidate */
564  	   )
565  	{
566  	   if( nlcountmax >= 1 && nlcount != NULL )
567  	   {
568  	      SCIP_Real nlscore;
569  	
570  	      assert(scip != NULL);
571  	      assert(probindex >= 0);
572  	      assert(probindex < SCIPgetNVars(scip));
573  	
574  	      nlscore = nlcount[probindex] / (SCIP_Real)nlcountmax;
575  	
576  	      assert(nlscore >= 0.0);
577  	      assert(nlscore <= 1.0);
578  	      return nlscore;
579  	   }
580  	   else
581  	      return 0.0;
582  	}
583  	
584  	/** calculates an overall score value for the given individual score values */
585  	static
586  	SCIP_Real calcScore(
587  	   SCIP*                 scip,               /**< SCIP data structure */
588  	   SCIP_BRANCHRULEDATA*  branchruledata,     /**< branching rule data */
589  	   SCIP_Real             conflictscore,      /**< conflict score of current variable */
590  	   SCIP_Real             avgconflictscore,   /**< average conflict score */
591  	   SCIP_Real             conflengthscore,    /**< conflict length score of current variable */
592  	   SCIP_Real             avgconflengthscore, /**< average conflict length score */
593  	   SCIP_Real             inferencescore,     /**< inference score of current variable */
594  	   SCIP_Real             avginferencescore,  /**< average inference score */
595  	   SCIP_Real             cutoffscore,        /**< cutoff score of current variable */
596  	   SCIP_Real             avgcutoffscore,     /**< average cutoff score */
597  	   SCIP_Real             gmieffscore,        /**< normalized-eff of avg GMI cuts from row when var was frac and basic */
598  	   SCIP_Real             lastgmieffscore,    /**< last normalized gmieffscore when var was frac and basic  */
599  	   SCIP_Real             pscostscore,        /**< pscost score of current variable */
600  	   SCIP_Real             avgpscostscore,     /**< average pscost score */
601  	   SCIP_Real             nlscore,            /**< nonlinear score of current variable between 0 and 1 */
602  	   SCIP_Real             frac,               /**< fractional value of variable in current solution */
603  	   SCIP_Real             degeneracyfactor    /**< factor to apply because of degeneracy */
604  	   )
605  	{
606  	   SCIP_Real score;
607  	   SCIP_Real dynamicfactor;
608  	
609  	   assert(branchruledata != NULL);
610  	   assert(0.0 < frac && frac < 1.0);
611  	
612  	   if( branchruledata->dynamicweights )
613  	   {
614  	      dynamicfactor = (SCIPgetNInfeasibleLeaves(scip) + 1.0) / (SCIPgetNObjlimLeaves(scip) + 1.0);
615  	   }
616  	   else
617  	      dynamicfactor = 1.0;
618  	
619  	   dynamicfactor *= degeneracyfactor;
620  	
621  	   score = dynamicfactor * (branchruledata->conflictweight * (1.0 - 1.0/(1.0+conflictscore/avgconflictscore))
622  	            + branchruledata->conflengthweight * (1.0 - 1.0/(1.0+conflengthscore/avgconflengthscore))
623  	            + branchruledata->inferenceweight * (1.0 - 1.0/(1.0+inferencescore/avginferencescore))
624  	            + branchruledata->cutoffweight * (1.0 - 1.0/(1.0+cutoffscore/avgcutoffscore))
625  	            + branchruledata->gmiavgeffweight * gmieffscore + branchruledata->gmilasteffweight * lastgmieffscore)
626  	         + branchruledata->pscostweight / dynamicfactor * (1.0 - 1.0/(1.0+pscostscore/avgpscostscore))
627  	         + branchruledata->nlscoreweight * nlscore;
628  	
629  	   /* avoid close to integral variables */
630  	   if( MIN(frac, 1.0 - frac) < 10.0 * SCIPfeastol(scip) )
631  	      score *= 1e-6;
632  	
633  	   return score;
634  	}
635  	
636  	/** adds given index and direction to bound change arrays */
637  	static
638  	SCIP_RETCODE addBdchg(
639  	   SCIP*                 scip,               /**< SCIP data structure */
640  	   int**                 bdchginds,          /**< pointer to bound change index array */
641  	   SCIP_BOUNDTYPE**      bdchgtypes,         /**< pointer to bound change types array */
642  	   SCIP_Real**           bdchgbounds,        /**< pointer to bound change new bounds array */
643  	   int*                  nbdchgs,            /**< pointer to number of bound changes */
644  	   int                   ind,                /**< index to store in bound change index array */
645  	   SCIP_BOUNDTYPE        type,               /**< type of the bound change to store in bound change type array */
646  	   SCIP_Real             bound               /**< new bound to store in bound change new bounds array */
647  	   )
648  	{
649  	   assert(bdchginds != NULL);
650  	   assert(bdchgtypes != NULL);
651  	   assert(bdchgbounds != NULL);
652  	   assert(nbdchgs != NULL);
653  	
654  	   SCIP_CALL( SCIPreallocBufferArray(scip, bdchginds, (*nbdchgs) + 1) );
655  	   SCIP_CALL( SCIPreallocBufferArray(scip, bdchgtypes, (*nbdchgs) + 1) );
656  	   SCIP_CALL( SCIPreallocBufferArray(scip, bdchgbounds, (*nbdchgs) + 1) );
657  	   assert(*bdchginds != NULL);
658  	   assert(*bdchgtypes != NULL);
659  	   assert(*bdchgbounds != NULL);
660  	
661  	   (*bdchginds)[*nbdchgs] = ind;
662  	   (*bdchgtypes)[*nbdchgs] = type;
663  	   (*bdchgbounds)[*nbdchgs] = bound;
664  	   (*nbdchgs)++;
665  	
666  	   return SCIP_OKAY;
667  	}
668  	
669  	/** frees bound change arrays */
670  	static
671  	void freeBdchgs(
672  	   SCIP*                 scip,               /**< SCIP data structure */
673  	   int**                 bdchginds,          /**< pointer to bound change index array */
674  	   SCIP_BOUNDTYPE**      bdchgtypes,         /**< pointer to bound change types array */
675  	   SCIP_Real**           bdchgbounds,        /**< pointer to bound change new bounds array */
676  	   int*                  nbdchgs             /**< pointer to number of bound changes */
677  	   )
678  	{
679  	   assert(bdchginds != NULL);
680  	   assert(bdchgtypes != NULL);
681  	   assert(bdchgbounds != NULL);
682  	   assert(nbdchgs != NULL);
683  	
684  	   SCIPfreeBufferArrayNull(scip, bdchgbounds);
685  	   SCIPfreeBufferArrayNull(scip, bdchgtypes);
686  	   SCIPfreeBufferArrayNull(scip, bdchginds);
687  	   *nbdchgs = 0;
688  	}
689  	
690  	/** applies bound changes stored in bound change arrays */
691  	static
692  	SCIP_RETCODE applyBdchgs(
693  	   SCIP*                 scip,               /**< SCIP data structure */
694  	   SCIP_VAR**            vars,               /**< problem variables */
695  	   int*                  bdchginds,          /**< bound change index array */
696  	   SCIP_BOUNDTYPE*       bdchgtypes,         /**< bound change types array */
697  	   SCIP_Real*            bdchgbounds,        /**< bound change new bound array */
698  	   int                   nbdchgs,            /**< number of bound changes */
699  	   SCIP_RESULT*          result              /**< result pointer */
700  	   )
701  	{
702  	#ifndef NDEBUG
703  	   SCIP_BRANCHRULE* branchrule;
704  	   SCIP_BRANCHRULEDATA* branchruledata;
705  	#endif
706  	   SCIP_Bool infeasible;
707  	   SCIP_Bool tightened;
708  	   int i;
709  	
710  	   assert(vars != NULL);
711  	
712  	#ifndef NDEBUG
713  	   /* find branching rule */
714  	   branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
715  	   assert(branchrule != NULL);
716  	
717  	   /* get branching rule data */
718  	   branchruledata = SCIPbranchruleGetData(branchrule);
719  	   assert(branchruledata != NULL);
720  	#endif
721  	
722  	   SCIPdebugMsg(scip, "applying %d bound changes\n", nbdchgs);
723  	
724  	   for( i = 0; i < nbdchgs; ++i )
725  	   {
726  	      int v;
727  	
728  	      v = bdchginds[i];
729  	
730  	      SCIPdebugMsg(scip, " -> <%s> [%g,%g]\n",
731  	         SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v]));
732  	
733  	      if( bdchgtypes[i] == SCIP_BOUNDTYPE_LOWER )
734  	      {
735  	         /* change lower bound of variable to given bound */
736  	         SCIP_CALL( SCIPtightenVarLb(scip, vars[v], bdchgbounds[i], TRUE, &infeasible, &tightened) );
737  	         if( infeasible )
738  	         {
739  	            *result = SCIP_CUTOFF;
740  	            return SCIP_OKAY;
741  	         }
742  	
743  	         /* if we did propagation, the bound change might already have been added */
744  	         assert(tightened || (branchruledata->maxproprounds != 0));
745  	      }
746  	      else
747  	      {
748  	         assert(bdchgtypes[i] == SCIP_BOUNDTYPE_UPPER);
749  	
750  	         /* change upper bound of variable to given bound */
751  	         SCIP_CALL( SCIPtightenVarUb(scip, vars[v], bdchgbounds[i], TRUE, &infeasible, &tightened) );
752  	         if( infeasible )
753  	         {
754  	            *result = SCIP_CUTOFF;
755  	            return SCIP_OKAY;
756  	         }
757  	
758  	         /* if we did propagation, the bound change might already have been added */
759  	         assert(tightened || (branchruledata->maxproprounds != 0));
760  	      }
761  	      SCIPdebugMsg(scip, "  -> [%g,%g]\n", SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v]));
762  	   }
763  	
764  	   return SCIP_OKAY;
765  	}
766  	
767  	/** execute reliability pseudo cost branching */
768  	static
769  	SCIP_RETCODE execRelpscost(
770  	   SCIP*                 scip,               /**< SCIP data structure */
771  	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
772  	   SCIP_VAR**            branchcands,        /**< branching candidates */
773  	   SCIP_Real*            branchcandssol,     /**< solution value for the branching candidates */
774  	   SCIP_Real*            branchcandsfrac,    /**< fractional part of the branching candidates */
775  	   int*                  branchorbitidx,     /**< indices of orbit (or NULL) */
776  	   int                   nbranchcands,       /**< number of branching candidates */
777  	   SCIP_Bool             executebranch,      /**< execute a branching step or run probing only */
778  	   SCIP_RESULT*          result              /**< pointer to the result of the execution */
779  	   )
780  	{  /*lint --e{715}*/
781  	   SCIP_BRANCHRULEDATA* branchruledata;
782  	   SCIP_Real lpobjval;
783  	   SCIP_Real bestsbdown;
784  	   SCIP_Real bestsbup;
785  	   SCIP_Real provedbound;
786  	   SCIP_Bool bestsbdownvalid;
787  	   SCIP_Bool bestsbupvalid;
788  	   SCIP_Bool bestsbdowncutoff;
789  	   SCIP_Bool bestsbupcutoff;
790  	   SCIP_Bool bestisstrongbranch;
791  	   SCIP_Bool allcolsinlp;
792  	   SCIP_Bool exactsolve;
793  	   int ninitcands;
794  	   int bestcand;
795  	
796  	   /* remember which variables strong branching is performed on, and the
797  	    * recorded lp bound changes that are observed */
798  	   SCIP_Bool* sbvars = NULL;
799  	   SCIP_Real* sbdown = NULL;
800  	   SCIP_Real* sbup = NULL;
801  	   SCIP_Bool* sbdownvalid = NULL;
802  	   SCIP_Bool* sbupvalid = NULL;
803  	
804  	   *result = SCIP_DIDNOTRUN;
805  	
806  	   assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
807  	
808  	   /* get branching rule data */
809  	   branchruledata = SCIPbranchruleGetData(branchrule);
810  	   assert(branchruledata != NULL);
811  	
812  	   /* get current LP objective bound of the local sub problem and global cutoff bound */
813  	   lpobjval = SCIPgetLPObjval(scip);
814  	
815  	   /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
816  	    * for cutting off sub problems and improving lower bounds of children
817  	    */
818  	   exactsolve = SCIPisExactSolve(scip);
819  	
820  	   /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
821  	   allcolsinlp = SCIPallColsInLP(scip);
822  	
823  	   bestcand = -1;
824  	   bestisstrongbranch = FALSE;
825  	   bestsbdown = SCIP_INVALID;
826  	   bestsbup = SCIP_INVALID;
827  	   bestsbdownvalid = FALSE;
828  	   bestsbupvalid = FALSE;
829  	   bestsbdowncutoff = FALSE;
830  	   bestsbupcutoff = FALSE;
831  	   provedbound = lpobjval;
832  	
833  	   /* Allocate memory to store the lp bounds of the up and down children
834  	    * for those of the variables that we performed sb on
835  	    */
836  	   SCIP_CALL( SCIPallocBufferArray(scip, &sbdown, nbranchcands) );
837  	   SCIP_CALL( SCIPallocBufferArray(scip, &sbup, nbranchcands) );
838  	   SCIP_CALL( SCIPallocBufferArray(scip, &sbdownvalid, nbranchcands) );
839  	   SCIP_CALL( SCIPallocBufferArray(scip, &sbupvalid, nbranchcands) );
840  	   SCIP_CALL( SCIPallocBufferArray(scip, &sbvars, nbranchcands) );
841  	
842  	   if( nbranchcands == 1 )
843  	   {
844  	      /* only one candidate: nothing has to be done */
845  	      bestcand = 0;
846  	      SCIPdebug(ninitcands = 0);
847  	      sbvars[0] = FALSE;
848  	   }
849  	   else
850  	   {
851  	      SCIP_VAR** vars;
852  	      int* initcands;
853  	      SCIP_Real* initcandscores;
854  	      SCIP_Real* newlbs = NULL;
855  	      SCIP_Real* newubs = NULL;
856  	      SCIP_Real* mingains = NULL;
857  	      SCIP_Real* maxgains = NULL;
858  	      /* scores computed from pseudocost branching */
859  	      SCIP_Real* scores = NULL;
860  	      SCIP_Real* scoresfrompc = NULL;
861  	      SCIP_Real* scoresfromothers = NULL;
862  	      int* bdchginds;
863  	      SCIP_BOUNDTYPE* bdchgtypes;
864  	      SCIP_Real* bdchgbounds;
865  	      int maxninitcands;
866  	      int nuninitcands;
867  	      int nbdchgs;
868  	      int nbdconflicts;
869  	      SCIP_Real avgconflictscore;
870  	      SCIP_Real avgconflengthscore;
871  	      SCIP_Real avginferencescore;
872  	      SCIP_Real avgcutoffscore;
873  	      SCIP_Real avgpscostscore;
874  	      SCIP_Real bestpsscore;
875  	      SCIP_Real bestpsfracscore;
876  	      SCIP_Real bestpsdomainscore;
877  	      SCIP_Real bestsbscore;
878  	      SCIP_Real bestuninitsbscore;
879  	      SCIP_Real bestsbfracscore;
880  	      SCIP_Real bestsbdomainscore;
881  	      SCIP_Real prio;
882  	      SCIP_Real reliable;
883  	      SCIP_Real maxlookahead;
884  	      SCIP_Real lookahead;
885  	      SCIP_Real relerrorthreshold;
886  	      SCIP_Bool initstrongbranching;
887  	      SCIP_Bool propagate;
888  	      SCIP_Bool probingbounds;
889  	      SCIP_Longint nodenum;
890  	      SCIP_Longint nlpiterationsquot;
891  	      SCIP_Longint nsblpiterations;
892  	      SCIP_Longint maxnsblpiterations;
893  	      int bestsolidx;
894  	      int maxbdchgs;
895  	      int bestpscand;
896  	      int bestsbcand;
897  	      int bestuninitsbcand;
898  	      int inititer;
899  	      int nvars;
900  	      int i;
901  	      int c;
902  	      SCIP_CONFIDENCELEVEL clevel;
903  	      SCIP_Real degeneracyfactor = 1.0;
904  	
905  	      /* get LP degeneracy information and compute a factor to change weighting of pseudo cost score vs. other scores */
906  	      if( branchruledata->degeneracyaware > 0 && (SCIPgetDepth(scip) > 0 || branchruledata->degeneracyaware > 1) )
907  	      {
908  	         SCIP_Real degeneracy;
909  	         SCIP_Real varconsratio;
910  	
911  	         /* get LP degeneracy information */
912  	         SCIP_CALL( SCIPgetLPDualDegeneracy(scip, &degeneracy, &varconsratio) );
913  	
914  	         assert(degeneracy >= 0.0);
915  	         assert(degeneracy <= 1.0);
916  	         assert(varconsratio >= 1.0);
917  	
918  	         /* increase factor for a degeneracy >= 80% */
919  	         if( degeneracy >= 0.8 )
920  	         {
921  	            degeneracy = 10.0 * (degeneracy - 0.7);
922  	            degeneracyfactor = degeneracyfactor * pow(10.0,degeneracy);
923  	         }
924  	         /* increase factor for a variable-constraint ratio >= 2.0 */
925  	         if( varconsratio >= 2.0 )
926  	         {
927  	            degeneracyfactor *= 10.0 * varconsratio;
928  	         }
929  	      }
930  	
931  	      vars = SCIPgetVars(scip);
932  	      nvars = SCIPgetNVars(scip);
933  	
934  	      bestsolidx = SCIPgetBestSol(scip) == NULL ? -1 : SCIPsolGetIndex(SCIPgetBestSol(scip));
935  	
936  	      /* get average conflict, inference, and pseudocost scores */
937  	      avgconflictscore = SCIPgetAvgConflictScore(scip);
938  	      avgconflictscore = MAX(avgconflictscore, 0.1);
939  	      avgconflengthscore = SCIPgetAvgConflictlengthScore(scip);
940  	      avgconflengthscore = MAX(avgconflengthscore, 0.1);
941  	      avginferencescore = SCIPgetAvgInferenceScore(scip);
942  	      avginferencescore = MAX(avginferencescore, 0.1);
943  	      avgcutoffscore = SCIPgetAvgCutoffScore(scip);
944  	      avgcutoffscore = MAX(avgcutoffscore, 0.1);
945  	      avgpscostscore = SCIPgetAvgPseudocostScore(scip);
946  	      avgpscostscore = MAX(avgpscostscore, 0.1);
947  	
948  	      /* get nonlinear counts according to parameters */
949  	      SCIP_CALL( branchruledataEnsureNlcount(scip, branchruledata) );
950  	
951  	      initstrongbranching = FALSE;
952  	
953  	      /* check whether propagation should be performed */
954  	      propagate = (branchruledata->maxproprounds != 0);
955  	
956  	      /* check whether valid bounds should be identified in probing-like fashion */
957  	      probingbounds = propagate && branchruledata->probingbounds;
958  	
959  	      /* get maximal number of candidates to initialize with strong branching; if the current solutions is not basic,
960  	       * we cannot warmstart the simplex algorithm and therefore don't initialize any candidates
961  	       */
962  	      maxninitcands = MIN(nbranchcands, branchruledata->initcand);
963  	      if( !SCIPisLPSolBasic(scip) )
964  	         maxninitcands = 0;
965  	
966  	      /* calculate maximal number of strong branching LP iterations; if we used too many, don't apply strong branching
967  	       * any more; also, if degeneracy is too high, don't run strong branching at this node
968  	       */
969  	      nlpiterationsquot = (SCIP_Longint)(branchruledata->sbiterquot * SCIPgetNNodeLPIterations(scip));
970  	      maxnsblpiterations = nlpiterationsquot + branchruledata->sbiterofs + SCIPgetNRootStrongbranchLPIterations(scip);
971  	      nsblpiterations = SCIPgetNStrongbranchLPIterations(scip);
972  	      if( nsblpiterations > maxnsblpiterations || degeneracyfactor >= 10.0 )
973  	         maxninitcands = 0;
974  	
975  	      /* get buffer for storing the unreliable candidates */
976  	      SCIP_CALL( SCIPallocBufferArray(scip, &initcands, maxninitcands+1) ); /* allocate one additional slot for convenience */
977  	      SCIP_CALL( SCIPallocBufferArray(scip, &initcandscores, maxninitcands+1) );
978  	      ninitcands = 0;
979  	
980  	      /* Allocate memory for the down and up gains, and the computed pseudocost scores */
981  	      SCIP_CALL( SCIPallocBufferArray(scip, &mingains, nbranchcands) );
982  	      SCIP_CALL( SCIPallocBufferArray(scip, &maxgains, nbranchcands) );
983  	      SCIP_CALL( SCIPallocBufferArray(scip, &scores, nbranchcands) );
984  	      SCIP_CALL( SCIPallocBufferArray(scip, &scoresfrompc, nbranchcands) );
985  	      SCIP_CALL( SCIPallocBufferArray(scip, &scoresfromothers, nbranchcands) );
986  	
987  	      /* get current node number */
988  	      nodenum = SCIPgetNNodes(scip);
989  	
990  	      /* initialize bound change arrays */
991  	      bdchginds = NULL;
992  	      bdchgtypes = NULL;
993  	      bdchgbounds = NULL;
994  	      nbdchgs = 0;
995  	      nbdconflicts = 0;
996  	      maxbdchgs = branchruledata->maxbdchgs;
997  	      if( maxbdchgs == -1 )
998  	         maxbdchgs = INT_MAX;
999  	
1000 	      /* calculate value used as reliability */
1001 	      prio = (maxnsblpiterations - nsblpiterations)/(nsblpiterations + 1.0);
1002 	      prio = MIN(prio, 1.0);
1003 	      prio = MAX(prio, (nlpiterationsquot - nsblpiterations)/(nsblpiterations + 1.0));
1004 	      reliable = (1.0-prio) * branchruledata->minreliable + prio * branchruledata->maxreliable;
1005 	
1006 	      /* calculate the threshold for the relative error in the same way; low tolerance is more strict than higher tolerance */
1007 	      relerrorthreshold = (1.0 - prio) * branchruledata->higherrortol + prio * branchruledata->lowerrortol;
1008 	
1009 	      clevel = (SCIP_CONFIDENCELEVEL)branchruledata->confidencelevel;
1010 	      /* determine the confidence level for hypothesis testing based on value of prio */
1011 	      if( branchruledata->usedynamicconfidence )
1012 	      {
1013 	         /* with decreasing priority, use a less strict confidence level */
1014 	         if( prio >= 0.9 )
1015 	            clevel = SCIP_CONFIDENCELEVEL_MAX;
1016 	         else if( prio >= 0.7 )
1017 	            clevel = SCIP_CONFIDENCELEVEL_HIGH;
1018 	         else if( prio >= 0.5 )
1019 	            clevel = SCIP_CONFIDENCELEVEL_MEDIUM;
1020 	         else if( prio >= 0.3 )
1021 	            clevel = SCIP_CONFIDENCELEVEL_LOW;
1022 	         else
1023 	            clevel = SCIP_CONFIDENCELEVEL_MIN;
1024 	      }
1025 	
1026 	      /* search for the best pseudo cost candidate, while remembering unreliable candidates in a sorted buffer */
1027 	      nuninitcands = 0;
1028 	      bestpscand = -1;
1029 	      bestpsscore = -SCIPinfinity(scip);
1030 	      bestpsfracscore = -SCIPinfinity(scip);
1031 	      bestpsdomainscore = -SCIPinfinity(scip);
1032 	
1033 	      /* search for the best candidate first */
1034 	      if( branchruledata->usehyptestforreliability )
1035 	      {
1036 	         for( c = 0; c < nbranchcands; ++c )
1037 	         {
1038 	            SCIP_Real conflictscore;
1039 	            SCIP_Real conflengthscore;
1040 	            SCIP_Real inferencescore;
1041 	            SCIP_Real cutoffscore;
1042 	            SCIP_Real gmieffscore;
1043 	            SCIP_Real lastgmieffscore;
1044 	            SCIP_Real pscostscore;
1045 	            SCIP_Real nlscore;
1046 	            SCIP_Real score;
1047 	
1048 	            conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1049 	            conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1050 	            inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1051 	            cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1052 	            gmieffscore = SCIPgetVarAvgGMIScore(scip, branchcands[c]);
1053 	            lastgmieffscore = SCIPgetVarLastGMIScore(scip, branchcands[c]);
1054 	            nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
1055 	            pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
1056 	
1057 	            /* replace the pseudo cost score with the already calculated one;
1058 	             * @todo: use old data for strong branching with propagation?
1059 	             */
1060 	            if( SCIPgetVarStrongbranchNode(scip, branchcands[c]) == nodenum )
1061 	            {
1062 	               SCIP_Real down;
1063 	               SCIP_Real up;
1064 	               SCIP_Real lastlpobjval;
1065 	               SCIP_Real downgain;
1066 	               SCIP_Real upgain;
1067 	
1068 	               /* use the score of the strong branching call at the current node */
1069 	               SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
1070 	               downgain = MAX(down - lastlpobjval, 0.0);
1071 	               upgain = MAX(up - lastlpobjval, 0.0);
1072 	               pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
1073 	
1074 	               SCIPdebugMsg(scip, " -> strong branching on variable <%s> already performed (down=%g (%+g), up=%g (%+g), pscostscore=%g)\n",
1075 	                  SCIPvarGetName(branchcands[c]), down, downgain, up, upgain, pscostscore);
1076 	            }
1077 	
1078 	            score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1079 	               inferencescore, avginferencescore, cutoffscore, avgcutoffscore, gmieffscore, lastgmieffscore,
1080 	               pscostscore, avgpscostscore, nlscore, branchcandsfrac[c], degeneracyfactor);
1081 	
1082 	            /* check for better score of candidate */
1083 	            if( SCIPisSumGE(scip, score, bestpsscore) )
1084 	            {
1085 	               SCIP_Real fracscore;
1086 	               SCIP_Real domainscore;
1087 	
1088 	               fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
1089 	               domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
1090 	               if( SCIPisSumGT(scip, score, bestpsscore)
1091 	                     || SCIPisSumGT(scip, fracscore, bestpsfracscore)
1092 	                     || (SCIPisSumGE(scip, fracscore, bestpsfracscore) && domainscore > bestpsdomainscore) )
1093 	               {
1094 	                  bestpscand = c;
1095 	                  bestpsscore = score;
1096 	                  bestpsfracscore = fracscore;
1097 	                  bestpsdomainscore = domainscore;
1098 	               }
1099 	            }
1100 	         }
1101 	      }
1102 	
1103 	      for( c = 0; c < nbranchcands; ++c )
1104 	      {
1105 	         SCIP_Real conflictscore;
1106 	         SCIP_Real conflengthscore;
1107 	         SCIP_Real inferencescore;
1108 	         SCIP_Real cutoffscore;
1109 	         SCIP_Real gmieffscore;
1110 	         SCIP_Real lastgmieffscore;
1111 	         SCIP_Real pscostscore;
1112 	         SCIP_Real nlscore;
1113 	         SCIP_Real score;
1114 	         SCIP_Bool usesb;
1115 	         SCIP_Real downgain;
1116 	         SCIP_Real upgain;
1117 	         SCIP_Real fracpart;
1118 	
1119 	         assert(branchcands[c] != NULL);
1120 	         assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
1121 	         assert(!SCIPisFeasIntegral(scip, SCIPvarGetLPSol(branchcands[c])));
1122 	
1123 	         /* Record the variables current pseudocosts. These may be overwritten if
1124 	          * strong branching is performed.
1125 	          */
1126 	         sbvars[c] = FALSE;
1127 	         fracpart = SCIPfeasFrac(scip, SCIPvarGetLPSol(branchcands[c]));
1128 	         downgain = SCIPgetVarPseudocostVal(scip, branchcands[c], 0.0 - fracpart);
1129 	         upgain = SCIPgetVarPseudocostVal(scip, branchcands[c], 1.0 - fracpart);
1130 	         mingains[c] = MIN(downgain, upgain);
1131 	         maxgains[c] = MAX(downgain, upgain);
1132 	
1133 	         /* get conflict, inference, cutoff, nonlinear, and pseudo cost scores for candidate */
1134 	         conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1135 	         conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1136 	         inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1137 	         cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1138 	         gmieffscore = SCIPgetVarAvgGMIScore(scip, branchcands[c]);
1139 	         lastgmieffscore = SCIPgetVarLastGMIScore(scip, branchcands[c]);
1140 	         nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
1141 	         pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
1142 	         usesb = FALSE;
1143 	
1144 	         /* don't use strong branching on variables that have already been initialized at the current node;
1145 	          * instead replace the pseudo cost score with the already calculated one;
1146 	          * @todo: use old data for strong branching with propagation?
1147 	          */
1148 	         if( SCIPgetVarStrongbranchNode(scip, branchcands[c]) == nodenum )
1149 	         {
1150 	            SCIP_Real down;
1151 	            SCIP_Real up;
1152 	            SCIP_Real lastlpobjval;
1153 	
1154 	            /* use the score of the strong branching call at the current node */
1155 	            SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
1156 	            downgain = MAX(down - lastlpobjval, 0.0);
1157 	            upgain = MAX(up - lastlpobjval, 0.0);
1158 	            pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
1159 	
1160 	            mingains[c] = MIN(downgain, upgain);
1161 	            maxgains[c] = MAX(downgain, upgain);
1162 	
1163 	            SCIPdebugMsg(scip, " -> strong branching on variable <%s> already performed (down=%g (%+g), up=%g (%+g), pscostscore=%g)\n",
1164 	               SCIPvarGetName(branchcands[c]), down, downgain, up, upgain, pscostscore);
1165 	         }
1166 	         else if( maxninitcands > 0 )
1167 	         {
1168 	            SCIP_Real downsize;
1169 	            SCIP_Real upsize;
1170 	            SCIP_Real size;
1171 	
1172 	            /* check, if the pseudo cost score of the variable is reliable */
1173 	            downsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_DOWNWARDS);
1174 	            upsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_UPWARDS);
1175 	            size = MIN(downsize, upsize);
1176 	
1177 	            /* determine if variable is considered reliable based on the current reliability setting */
1178 	            /* check fixed number threshold (aka original) reliability first */
1179 	            assert(!branchruledata->usehyptestforreliability || bestpscand >= 0);
1180 	            usesb = FALSE;
1181 	            if( size < reliable )
1182 	               usesb = TRUE;
1183 	            else if( branchruledata->userelerrorforreliability && branchruledata->usehyptestforreliability )
1184 	            {
1185 	               if( !SCIPisVarPscostRelerrorReliable(scip, branchcands[c], relerrorthreshold, clevel) &&
1186 	                     !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
1187 	                        branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE) &&
1188 	                     !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1 - branchcandsfrac[bestpscand],
1189 	                        branchcands[c], 1 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
1190 	                  usesb = TRUE;
1191 	            }
1192 	            /* check if relative error is tolerable */
1193 	            else if( branchruledata->userelerrorforreliability &&
1194 	                  !SCIPisVarPscostRelerrorReliable(scip, branchcands[c], relerrorthreshold, clevel))
1195 	               usesb = TRUE;
1196 	            /* check if best pseudo-candidate is significantly better in both directions, use strong-branching otherwise */
1197 	            else if( branchruledata->usehyptestforreliability &&
1198 	                  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
1199 	                        branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE) &&
1200 	                  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1 - branchcandsfrac[bestpscand],
1201 	                        branchcands[c], 1 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE))
1202 	               usesb = TRUE;
1203 	
1204 	            /* count the number of variables that are completely uninitialized */
1205 	            if( size < 0.1 )
1206 	               nuninitcands++;
1207 	         }
1208 	
1209 	         /* combine the five score values */
1210 	         scoresfrompc[c] =  calcScore(scip, branchruledata, 0.0, avgconflictscore, 0.0, avgconflengthscore,
1211 	                                      0.0, avginferencescore, 0.0, avgcutoffscore, 0.0, 0.0,
1212 	                                      pscostscore, avgpscostscore, 0.0, branchcandsfrac[c], degeneracyfactor);
1213 	         scoresfromothers[c] = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1214 	                                         inferencescore, avginferencescore, cutoffscore, avgcutoffscore, gmieffscore, lastgmieffscore,
1215 	                                         0.0, avgpscostscore, nlscore, branchcandsfrac[c], degeneracyfactor);
1216 	         score = scoresfrompc[c] + scoresfromothers[c];
1217 	         scores[c] = score;
1218 	         /*score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1219 	            inferencescore, avginferencescore, cutoffscore, avgcutoffscore, gmieffscore, lastgmieffscore,
1220 	            pscostscore, avgpscostscore, nlscore, branchcandsfrac[c], degeneracyfactor);*/
1221 	         if( usesb )
1222 	         {
1223 	            int j;
1224 	
1225 	            mingains[c] = 0;
1226 	            maxgains[c] = 0;
1227 	            scoresfrompc[c] = 0;
1228 	            scoresfromothers[c] = 0;
1229 	
1230 	            /* assign a random score to this uninitialized candidate */
1231 	            if( branchruledata->randinitorder )
1232 	               score += SCIPrandomGetReal(branchruledata->randnumgen, 0.0, 1e-4);
1233 	
1234 	            /* pseudo cost of variable is not reliable: insert candidate in initcands buffer */
1235 	            for( j = ninitcands; j > 0 && score > initcandscores[j-1]; --j )
1236 	            {
1237 	               initcands[j] = initcands[j-1];
1238 	               initcandscores[j] = initcandscores[j-1];
1239 	            }
1240 	            initcands[j] = c;
1241 	            initcandscores[j] = score;
1242 	            ninitcands++;
1243 	            ninitcands = MIN(ninitcands, maxninitcands);
1244 	         }
1245 	         /* in the case of hypothesis reliability, the best pseudo candidate has been determined already */
1246 	         else if( !branchruledata->usehyptestforreliability )
1247 	         {
1248 	            /* variable will keep its pseudo cost value: check for better score of candidate */
1249 	            if( SCIPisSumGE(scip, score, bestpsscore) )
1250 	            {
1251 	               SCIP_Real fracscore;
1252 	               SCIP_Real domainscore;
1253 	
1254 	               fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
1255 	               domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
1256 	               if( SCIPisSumGT(scip, score, bestpsscore)
1257 	                  || SCIPisSumGT(scip, fracscore, bestpsfracscore)
1258 	                  || (SCIPisSumGE(scip, fracscore, bestpsfracscore) && domainscore > bestpsdomainscore) )
1259 	               {
1260 	                  bestpscand = c;
1261 	                  bestpsscore = score;
1262 	                  bestpsfracscore = fracscore;
1263 	                  bestpsdomainscore = domainscore;
1264 	               }
1265 	            }
1266 	         }
1267 	      }
1268 	
1269 	      /* in the special case that only the best pseudo candidate was selected for strong branching, skip the strong branching */
1270 	      if( branchruledata->usehyptestforreliability && ninitcands == 1 )
1271 	      {
1272 	         ninitcands = 0;
1273 	         SCIPdebugMsg(scip, "Only one single candidate for initialization-->Skipping strong branching\n");
1274 	      }
1275 	
1276 	      /* initialize unreliable candidates with strong branching until maxlookahead is reached,
1277 	       * search best strong branching candidate
1278 	       */
1279 	      maxlookahead = (SCIP_Real)branchruledata->maxlookahead * (1.0 + (SCIP_Real)nuninitcands/(SCIP_Real)nbranchcands);
1280 	      inititer = branchruledata->inititer;
1281 	      if( inititer == 0 )
1282 	      {
1283 	         SCIP_Longint nlpiterations;
1284 	         SCIP_Longint nlps;
1285 	
1286 	         /* iteration limit is set to twice the average number of iterations spent to resolve a dual feasible SCIP_LP;
1287 	          * at the first few nodes, this average is not very exact, so we better increase the iteration limit on
1288 	          * these very important nodes
1289 	          */
1290 	         nlpiterations = SCIPgetNDualResolveLPIterations(scip);
1291 	         nlps = SCIPgetNDualResolveLPs(scip);
1292 	         if( nlps == 0 )
1293 	         {
1294 	            nlpiterations = SCIPgetNNodeInitLPIterations(scip);
1295 	            nlps = SCIPgetNNodeInitLPs(scip);
1296 	            if( nlps == 0 )
1297 	            {
1298 	               nlpiterations = 1000;
1299 	               nlps = 1;
1300 	            }
1301 	         }
1302 	         assert(nlps >= 1);
1303 	         inititer = (int)(2*nlpiterations / nlps);
1304 	         inititer = (int)((SCIP_Real)inititer * (1.0 + 20.0/nodenum));
1305 	         inititer = MAX(inititer, 10);
1306 	         inititer = MIN(inititer, 500);
1307 	      }
1308 	
1309 	      SCIPdebugMsg(scip, "strong branching (reliable=%g, %d/%d cands, %d uninit, maxcands=%d, maxlookahead=%g, maxbdchgs=%d, inititer=%d, iterations:%" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", basic:%u)\n",
1310 	         reliable, ninitcands, nbranchcands, nuninitcands, maxninitcands, maxlookahead, maxbdchgs, inititer,
1311 	         SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations, SCIPisLPSolBasic(scip));
1312 	
1313 	      bestsbcand = -1;
1314 	      bestsbscore = -SCIPinfinity(scip);
1315 	      bestsbfracscore = -SCIPinfinity(scip);
1316 	      bestsbdomainscore = -SCIPinfinity(scip);
1317 	      bestuninitsbscore = -SCIPinfinity(scip);
1318 	      bestuninitsbcand = -1;
1319 	      lookahead = 0.0;
1320 	      for( i = 0; i < ninitcands && lookahead < maxlookahead && nbdchgs + nbdconflicts < maxbdchgs
1321 	              && (i < (int) maxlookahead || SCIPgetNStrongbranchLPIterations(scip) < maxnsblpiterations); ++i )
1322 	      {
1323 	         SCIP_Real down;
1324 	         SCIP_Real up;
1325 	         SCIP_Real downgain;
1326 	         SCIP_Real upgain;
1327 	         SCIP_Bool downvalid;
1328 	         SCIP_Bool upvalid;
1329 	         SCIP_Longint ndomredsdown;
1330 	         SCIP_Longint ndomredsup;
1331 	         SCIP_Bool lperror;
1332 	         SCIP_Bool downinf;
1333 	         SCIP_Bool upinf;
1334 	         SCIP_Bool downconflict;
1335 	         SCIP_Bool upconflict;
1336 	
1337 	         /* get candidate number to initialize */
1338 	         c = initcands[i];
1339 	         assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
1340 	
1341 	         if( branchruledata->skipbadinitcands )
1342 	         {
1343 	            SCIP_Bool skipsb = FALSE;
1344 	            /* if the current best candidate is a candidate found by strong branching, determine if candidate pseudo-costs are
1345 	             * significantly smaller in at least one direction, in which case we safe the execution of strong-branching for now
1346 	             */
1347 	            if( bestsbscore > bestpsscore && bestsbscore > bestuninitsbscore && bestsbupvalid && bestsbdownvalid )
1348 	            {
1349 	               assert(bestsbcand != -1);
1350 	               assert(bestsbup != SCIP_INVALID && bestsbdown != SCIP_INVALID); /*lint !e777 lint doesn't like comparing floats */
1351 	
1352 	               /* test if the variable is unlikely to produce a better gain than the currently best one. Skip strong-branching
1353 	                * in such a case
1354 	                */
1355 	               if( SCIPpscostThresholdProbabilityTest(scip, branchcands[c], branchcandsfrac[c], bestsbdown,
1356 	                     SCIP_BRANCHDIR_DOWNWARDS, clevel)
1357 	                     || SCIPpscostThresholdProbabilityTest(scip, branchcands[c], 1.0 - branchcandsfrac[c], bestsbup,
1358 	                           SCIP_BRANCHDIR_UPWARDS, clevel) )
1359 	                  skipsb = TRUE;
1360 	            }
1361 	            /* the currently best candidate is also a pseudo-candidate; apply significance test and skip candidate if it
1362 	             * is significantly worse in at least one direction
1363 	             */
1364 	            else if( bestpscand != -1 && bestpsscore > bestuninitsbscore )
1365 	            {
1366 	               if( SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
1367 	                     branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE)
1368 	                     || SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1.0 - branchcandsfrac[bestpscand],
1369 	                           branchcands[c], 1.0 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
1370 	                  skipsb = TRUE;
1371 	            }
1372 	            /* compare against the best init cand that has been skipped already */
1373 	            else if( bestuninitsbcand != -1 )
1374 	            {
1375 	               if( SCIPsignificantVarPscostDifference(scip, branchcands[bestuninitsbcand], branchcandsfrac[bestuninitsbcand],
1376 	                     branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE)
1377 	                     || SCIPsignificantVarPscostDifference(scip, branchcands[bestuninitsbcand], 1.0 - branchcandsfrac[bestuninitsbcand],
1378 	                           branchcands[c], 1.0 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
1379 	                  skipsb = TRUE;
1380 	            }
1381 	
1382 	            /* skip candidate, update the best score of an unitialized candidate */
1383 	            if( skipsb )
1384 	            {
1385 	               if( bestuninitsbcand == -1 )
1386 	               {
1387 	                  bestuninitsbcand = c;
1388 	                  bestuninitsbscore = initcandscores[i];
1389 	               }
1390 	               continue;
1391 	            }
1392 	         }
1393 	         SCIPdebugMsg(scip, "init pseudo cost (%g/%g) of <%s> at %g (score:%g) with strong branching (%d iterations) -- %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " iterations\n",
1394 	            SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_DOWNWARDS),
1395 	            SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_UPWARDS),
1396 	            SCIPvarGetName(branchcands[c]), branchcandssol[c], initcandscores[i],
1397 	            inititer, SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations);
1398 	
1399 	         /* use strong branching on candidate */
1400 	         if( !initstrongbranching )
1401 	         {
1402 	            initstrongbranching = TRUE;
1403 	
1404 	            SCIP_CALL( SCIPstartStrongbranch(scip, propagate) );
1405 	
1406 	            /* create arrays for probing-like bound tightening */
1407 	            if( probingbounds )
1408 	            {
1409 	               SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newlbs, nvars) );
1410 	               SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newubs, nvars) );
1411 	            }
1412 	         }
1413 	
1414 	         if( propagate )
1415 	         {
1416 	            /* apply strong branching */
1417 	            SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, branchcands[c], branchcandssol[c], lpobjval, inititer,
1418 	                  branchruledata->maxproprounds, &down, &up, &downvalid, &upvalid, &ndomredsdown, &ndomredsup, &downinf, &upinf,
1419 	                  &downconflict, &upconflict, &lperror, newlbs, newubs) );
1420 	         }
1421 	         else
1422 	         {
1423 	            /* apply strong branching */
1424 	            SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, branchcands[c], inititer, FALSE,
1425 	                  &down, &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
1426 	
1427 	            ndomredsdown = ndomredsup = 0;
1428 	         }
1429 	
1430 	         /* check for an error in strong branching */
1431 	         if( lperror )
1432 	         {
1433 	            if( !SCIPisStopped(scip) )
1434 	            {
1435 	               SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1436 	                  "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
1437 	                  SCIPgetNNodes(scip), SCIPvarGetName(branchcands[c]), branchcandssol[c]);
1438 	            }
1439 	            break;
1440 	         }
1441 	
1442 	         /* Strong branching might have found a new primal solution which updated the cutoff bound. In this case, the
1443 	          * provedbound computed before can be higher than the cutoffbound and the current node can be cut off.
1444 	          * Additionally, also if the value for the current best candidate is valid and exceeds the new cutoff bound,
1445 	          * we want to change the domain of this variable rather than branching on it.
1446 	          */
1447 	         if( SCIPgetBestSol(scip) != NULL && SCIPsolGetIndex(SCIPgetBestSol(scip)) != bestsolidx )
1448 	         {
1449 	            bestsolidx = SCIPsolGetIndex(SCIPgetBestSol(scip));
1450 	
1451 	            SCIPdebugMsg(scip, " -> strong branching on variable <%s> lead to a new incumbent\n",
1452 	               SCIPvarGetName(branchcands[c]));
1453 	
1454 	            /* proved bound for current node is larger than new cutoff bound -> cut off current node */
1455 	            if( SCIPisGE(scip, provedbound, SCIPgetCutoffbound(scip)) )
1456 	            {
1457 	               SCIPdebugMsg(scip, " -> node can be cut off (provedbound=%g, cutoff=%g)\n", provedbound, SCIPgetCutoffbound(scip));
1458 	
1459 	               *result = SCIP_CUTOFF;
1460 	               break; /* terminate initialization loop, because node is infeasible */
1461 	            }
1462 	            /* proved bound for down child of best candidate is larger than cutoff bound
1463 	             *  -> increase lower bound of best candidate
1464 	             * we must only do this if the LP is complete, i.e., we are not doing column generation
1465 	             */
1466 	
1467 	            else if( bestsbcand != -1  && allcolsinlp )
1468 	            {
1469 	               if( !bestsbdowncutoff && bestsbdownvalid && SCIPisGE(scip, bestsbdown, SCIPgetCutoffbound(scip)) )
1470 	               {
1471 	                  bestsbdowncutoff = TRUE;
1472 	
1473 	                  SCIPdebugMsg(scip, " -> valid dual bound for down child of best candidate <%s> is higher than new cutoff bound (valid=%u, bestsbdown=%g, cutoff=%g)\n",
1474 	                     SCIPvarGetName(branchcands[bestsbcand]), bestsbdownvalid, bestsbdown, SCIPgetCutoffbound(scip));
1475 	
1476 	                  SCIPdebugMsg(scip, " -> increase lower bound of best candidate <%s> to %g\n",
1477 	                     SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasCeil(scip, branchcandssol[bestsbcand]));
1478 	
1479 	                  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
1480 	                        SCIP_BOUNDTYPE_LOWER, SCIPfeasCeil(scip, branchcandssol[bestsbcand])) );
1481 	               }
1482 	               /* proved bound for up child of best candidate is larger than cutoff bound -> decrease upper bound of best candidate */
1483 	               else if( !bestsbupcutoff && bestsbupvalid && SCIPisGE(scip, bestsbup, SCIPgetCutoffbound(scip)) )
1484 	               {
1485 	                  bestsbupcutoff = TRUE;
1486 	
1487 	                  SCIPdebugMsg(scip, " -> valid dual bound for up child of best candidate <%s> is higher than new cutoff bound (valid=%u, bestsbup=%g, cutoff=%g)\n",
1488 	                     SCIPvarGetName(branchcands[bestsbcand]), bestsbupvalid, bestsbup, SCIPgetCutoffbound(scip));
1489 	
1490 	                  SCIPdebugMsg(scip, " -> decrease upper bound of best candidate <%s> to %g\n",
1491 	                     SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasFloor(scip, branchcandssol[bestsbcand]));
1492 	
1493 	                  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
1494 	                        SCIP_BOUNDTYPE_UPPER, SCIPfeasFloor(scip, branchcandssol[bestsbcand])) );
1495 	               }
1496 	            }
1497 	         }
1498 	
1499 	         /* evaluate strong branching */
1500 	         down = MAX(down, lpobjval);
1501 	         up = MAX(up, lpobjval);
1502 	         downgain = down - lpobjval;
1503 	         upgain = up - lpobjval;
1504 	         assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
1505 	         assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
1506 	         assert(downinf || !downconflict);
1507 	         assert(upinf || !upconflict);
1508 	
1509 	         /* @todo: store pseudo cost only for valid bounds?
1510 	          * depending on the user parameter choice of storesemiinitcosts, pseudo costs are also updated in single directions,
1511 	          * if the node in the other direction was infeasible or cut off
1512 	          */
1513 	         if( !downinf
1514 	#ifdef WITH_LPSOLSTAT
1515 	               && SCIPgetLastStrongbranchLPSolStat(scip, SCIP_BRANCHDIR_DOWNWARDS) != SCIP_LPSOLSTAT_ITERLIMIT
1516 	#endif
1517 	               && (!upinf || branchruledata->storesemiinitcosts) )
1518 	         {
1519 	            SCIP_Real weight;
1520 	
1521 	            /* smaller weights are given if the strong branching hit the time limit in the corresponding direction */
1522 	            if( branchruledata->usesmallweightsitlim )
1523 	               weight = SCIPgetLastStrongbranchLPSolStat(scip, SCIP_BRANCHDIR_DOWNWARDS) != SCIP_LPSOLSTAT_ITERLIMIT ? 1.0 : 0.5;
1524 	            else
1525 	               weight = 1.0;
1526 	
1527 	            /* update pseudo cost values */
1528 	            SCIP_CALL( SCIPupdateVarPseudocostSymmetric(scip, branchruledata, branchcands[c], branchorbitidx, c, 0.0 - branchcandsfrac[c], downgain, weight) );
1529 	         }
1530 	         if( !upinf
1531 	#ifdef WITH_LPSOLSTAT
1532 	               && SCIPgetLastStrongbranchLPSolStat(scip, SCIP_BRANCHDIR_UPWARDS) != SCIP_LPSOLSTAT_ITERLIMIT
1533 	#endif
1534 	               && (!downinf || branchruledata->storesemiinitcosts)  )
1535 	         {
1536 	            SCIP_Real weight;
1537 	
1538 	            /* smaller weights are given if the strong branching hit the time limit in the corresponding direction */
1539 	            if( branchruledata->usesmallweightsitlim )
1540 	               weight = SCIPgetLastStrongbranchLPSolStat(scip, SCIP_BRANCHDIR_UPWARDS) != SCIP_LPSOLSTAT_ITERLIMIT ? 1.0 : 0.5;
1541 	            else
1542 	               weight = 1.0;
1543 	
1544 	            /* update pseudo cost values */
1545 	            SCIP_CALL( SCIPupdateVarPseudocostSymmetric(scip, branchruledata, branchcands[c], branchorbitidx, c, 1.0 - branchcandsfrac[c], upgain, weight) );
1546 	         }
1547 	
1548 	         /* the minimal lower bound of both children is a proved lower bound of the current subtree */
1549 	         if( allcolsinlp && !exactsolve && downvalid && upvalid )
1550 	         {
1551 	            SCIP_Real minbound;
1552 	
1553 	            minbound = MIN(down, up);
1554 	            provedbound = MAX(provedbound, minbound);
1555 	            assert((downinf && upinf) || SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1556 	
1557 	            /* save probing-like bounds detected during strong branching */
1558 	            if( probingbounds )
1559 	            {
1560 	               int v;
1561 	
1562 	               assert(newlbs != NULL);
1563 	               assert(newubs != NULL);
1564 	
1565 	               for( v = 0; v < nvars; ++v )
1566 	               {
1567 	                  if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) )
1568 	                  {
1569 	                     SCIPdebugMsg(scip, "better lower bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
1570 	                        SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(branchcands[c]));
1571 	
1572 	                     SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
1573 	                           SCIP_BOUNDTYPE_LOWER, newlbs[v]) );
1574 	                  }
1575 	                  if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) )
1576 	                  {
1577 	                     SCIPdebugMsg(scip, "better upper bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
1578 	                        SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(branchcands[c]));
1579 	
1580 	                     SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
1581 	                           SCIP_BOUNDTYPE_UPPER, newubs[v]) );
1582 	                  }
1583 	               }
1584 	            }
1585 	         }
1586 	
1587 	         /* check if there are infeasible roundings */
1588 	         if( downinf || upinf )
1589 	         {
1590 	            assert(allcolsinlp || propagate);
1591 	            assert(!exactsolve);
1592 	
1593 	            if( downinf && upinf )
1594 	            {
1595 	               /* both roundings are infeasible -> node is infeasible */
1596 	               SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions (conflict: %u/%u)\n",
1597 	                  SCIPvarGetName(branchcands[c]), downconflict, upconflict);
1598 	               *result = SCIP_CUTOFF;
1599 	               break; /* terminate initialization loop, because node is infeasible */
1600 	            }
1601 	            else
1602 	            {
1603 	               /* rounding is infeasible in one direction -> round variable in other direction */
1604 	               SCIPdebugMsg(scip, " -> variable <%s> is infeasible in %s branch (conflict: %u/%u)\n",
1605 	                  SCIPvarGetName(branchcands[c]), downinf ? "downward" : "upward", downconflict, upconflict);
1606 	               SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[c]),
1607 	                     (downinf ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER),
1608 	                     (downinf ? SCIPfeasCeil(scip, branchcandssol[c]) : SCIPfeasFloor(scip, branchcandssol[c]))) );
1609 	               if( nbdchgs + nbdconflicts >= maxbdchgs )
1610 	                  break; /* terminate initialization loop, because enough roundings are performed */
1611 	            }
1612 	         }
1613 	         else
1614 	         {
1615 	            SCIP_Real conflictscore;
1616 	            SCIP_Real conflengthscore;
1617 	            SCIP_Real inferencescore;
1618 	            SCIP_Real cutoffscore;
1619 	            SCIP_Real gmieffscore;
1620 	            SCIP_Real lastgmieffscore;
1621 	            SCIP_Real pscostscore;
1622 	            SCIP_Real nlscore;
1623 	            SCIP_Real score;
1624 	
1625 	            mingains[c] = MIN(downgain, upgain);
1626 	            maxgains[c] = MAX(downgain, upgain);
1627 	
1628 	            sbdown[c] = down;
1629 	            sbup[c] = up;
1630 	            sbdownvalid[c] = downvalid;
1631 	            sbupvalid[c] = upvalid;
1632 	            sbvars[c] = TRUE;
1633 	
1634 	            /* check for a better score */
1635 	            conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1636 	            conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1637 	            nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
1638 	
1639 	            /* optionally, use only local information obtained via strong branching for this candidate, i.e., local
1640 	             * domain reductions and no cutoff score
1641 	             */
1642 	            inferencescore = branchruledata->usesblocalinfo ? SCIPgetBranchScore(scip, branchcands[c], (SCIP_Real)ndomredsdown, (SCIP_Real)ndomredsup)
1643 	                  : SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1644 	            cutoffscore = branchruledata->usesblocalinfo ? 0.0 : SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1645 	            gmieffscore = branchruledata->usesblocalinfo ? 0.0 : SCIPgetVarAvgGMIScore(scip, branchcands[c]);
1646 	            lastgmieffscore = branchruledata->usesblocalinfo ? 0.0 : SCIPgetVarLastGMIScore(scip, branchcands[c]);
1647 	            pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
1648 	
1649 	            scoresfrompc[c] =  calcScore(scip, branchruledata, 0.0, avgconflictscore, 0.0, avgconflengthscore,
1650 	                                         0.0, avginferencescore, 0.0, avgcutoffscore, 0.0, 0.0, pscostscore,
1651 	                                         avgpscostscore, 0.0, branchcandsfrac[c], degeneracyfactor);
1652 	            scoresfromothers[c] = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1653 	                                            inferencescore, avginferencescore, cutoffscore, avgcutoffscore, gmieffscore,
1654 	                                            lastgmieffscore, 0.0, avgpscostscore, nlscore, branchcandsfrac[c],
1655 	                                            degeneracyfactor);
1656 	            score = scoresfrompc[c] + scoresfromothers[c];
1657 	            scores[c] = score;
1658 	            /*score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1659 	               inferencescore, avginferencescore, cutoffscore, avgcutoffscore, gmieffscore, lastgmieffscore,
1660 	               pscostscore, avgpscostscore, nlscore, branchcandsfrac[c], degeneracyfactor);*/
1661 	
1662 	            if( SCIPisSumGE(scip, score, bestsbscore) )
1663 	            {
1664 	               SCIP_Real fracscore;
1665 	               SCIP_Real domainscore;
1666 	
1667 	               fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
1668 	               domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
1669 	               if( SCIPisSumGT(scip, score, bestsbscore)
1670 	                  || SCIPisSumGT(scip, fracscore, bestsbfracscore)
1671 	                  || (SCIPisSumGE(scip, fracscore, bestsbfracscore) && domainscore > bestsbdomainscore) )
1672 	               {
1673 	                  bestsbcand = c;
1674 	                  bestsbscore = score;
1675 	                  bestsbdown = down;
1676 	                  bestsbup = up;
1677 	                  bestsbdownvalid = downvalid;
1678 	                  bestsbupvalid = upvalid;
1679 	                  bestsbdowncutoff = FALSE;
1680 	                  bestsbupcutoff = FALSE;
1681 	                  bestsbfracscore = fracscore;
1682 	                  bestsbdomainscore = domainscore;
1683 	                  lookahead = 0.0;
1684 	               }
1685 	               else
1686 	                  lookahead += 0.5;
1687 	            }
1688 	            else
1689 	               lookahead += 1.0;
1690 	
1691 	            SCIPdebugMsg(scip, " -> variable <%s> (solval=%g, down=%g (%+g,valid=%u), up=%g (%+g,valid=%u), score=%g/ %g/%g %g/%g %g -> %g)\n",
1692 	               SCIPvarGetName(branchcands[c]), branchcandssol[c], down, downgain, downvalid, up, upgain, upvalid,
1693 	               pscostscore, conflictscore, conflengthscore, inferencescore, cutoffscore, gmieffscore, score);
1694 	         }
1695 	      }
1696 	#ifdef SCIP_DEBUG
1697 	      if( bestsbcand >= 0 )
1698 	      {
1699 	         SCIPdebugMsg(scip, " -> best: <%s> (%g / %g / %g), lookahead=%g/%g\n",
1700 	            SCIPvarGetName(branchcands[bestsbcand]), bestsbscore, bestsbfracscore, bestsbdomainscore,
1701 	            lookahead, maxlookahead);
1702 	      }
1703 	#endif
1704 	
1705 	      if( initstrongbranching )
1706 	      {
1707 	         if( probingbounds )
1708 	         {
1709 	            assert(newlbs != NULL);
1710 	            assert(newubs != NULL);
1711 	
1712 	            SCIPfreeBlockMemoryArray(scip, &newubs, nvars);
1713 	            SCIPfreeBlockMemoryArray(scip, &newlbs, nvars);
1714 	         }
1715 	
1716 	         SCIP_CALL( SCIPendStrongbranch(scip) );
1717 	
1718 	         if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OBJLIMIT || SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_INFEASIBLE )
1719 	         {
1720 	            assert(SCIPhasCurrentNodeLP(scip));
1721 	            *result = SCIP_CUTOFF;
1722 	         }
1723 	      }
1724 	
1725 	      if( *result != SCIP_CUTOFF )
1726 	      {
1727 	         /* get the score of the best uninitialized strong branching candidate */
1728 	         if( i < ninitcands && bestuninitsbcand == -1 )
1729 	            bestuninitsbscore = initcandscores[i];
1730 	
1731 	         /* if the best pseudo cost candidate is better than the best uninitialized strong branching candidate,
1732 	          * compare it to the best initialized strong branching candidate
1733 	          */
1734 	         if( bestpsscore > bestuninitsbscore && SCIPisSumGT(scip, bestpsscore, bestsbscore) )
1735 	         {
1736 	            bestcand = bestpscand;
1737 	            bestisstrongbranch = FALSE;
1738 	         }
1739 	         else if( bestsbcand >= 0 )
1740 	         {
1741 	            bestcand = bestsbcand;
1742 	            bestisstrongbranch = TRUE;
1743 	         }
1744 	         else
1745 	         {
1746 	            /* no candidate was initialized, and the best score is the one of the first candidate in the initialization
1747 	             * queue
1748 	             */
1749 	            assert(ninitcands >= 1);
1750 	            bestcand = initcands[0];
1751 	            bestisstrongbranch = FALSE;
1752 	         }
1753 	
1754 	         /* update lower bound of current node */
1755 	         if( allcolsinlp && !exactsolve )
1756 	         {
1757 	            assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1758 	            SCIP_CALL( SCIPupdateNodeLowerbound(scip, SCIPgetCurrentNode(scip), provedbound) );
1759 	         }
1760 	      }
1761 	
1762 	      /* apply domain reductions */
1763 	      if( nbdchgs > 0 )
1764 	      {
1765 	         if( *result != SCIP_CUTOFF )
1766 	         {
1767 	            SCIP_CALL( applyBdchgs(scip, vars, bdchginds, bdchgtypes, bdchgbounds, nbdchgs, result) );
1768 	            if( *result != SCIP_CUTOFF )
1769 	               *result = SCIP_REDUCEDDOM;
1770 	         }
1771 	         freeBdchgs(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs);
1772 	      }
1773 	
1774 	      /* Apply the Treemodel branching rule to potentially select a better branching candidate than the current one. */
1775 	      if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED && SCIPtreemodelIsEnabled(scip, branchruledata->treemodel) )
1776 	      {
1777 		 SCIP_Real smallpscost;
1778 		 SCIP_Bool usetreemodel;
1779 	
1780 		 usetreemodel = TRUE;
1781 	
1782 	         /* If the pseudocosts are zero, use SCIPs best variable since the Treemodel is not applicable */
1783 	         if( SCIPisZero(scip, maxgains[bestcand]))
1784 	         {
1785 	             usetreemodel = FALSE;
1786 	         }
1787 	
1788 	         /* If SCIPs best candidate was selected due to hybrid branching scores
1789 	          * rather than because of pseudocosts, then we keep it.
1790 	          */
1791 	         SCIP_CALL( SCIPgetRealParam(scip, "branching/treemodel/smallpscost", &smallpscost) );
1792 	         if( usetreemodel == TRUE && avgpscostscore <= smallpscost )
1793 	         {
1794 	            int cand;
1795 	            for( cand = 0; cand < nbranchcands; ++cand )
1796 	            {
1797 	               if( scoresfrompc[cand] > scoresfrompc[bestcand] )
1798 	               {
1799 	                  usetreemodel = FALSE;
1800 			  break;
1801 	               }
1802 	            }
1803 	         }
1804 	
1805 	         if( usetreemodel == TRUE )
1806 	         {
1807 	            SCIP_CALL( SCIPtreemodelSelectCandidate(
1808 	               scip,                        /* SCIP data structure */
1809 	               branchruledata->treemodel,   /* branching rule */
1810 	               branchcands,                 /* branching candidate storage */
1811 	               mingains,                    /* minimum gain of rounding downwards or upwards */
1812 	               maxgains,                    /* maximum gain of rounding downwards or upwards */
1813 	               scoresfromothers,            /* scores from other branching methods */
1814 	               nbranchcands,                /* the number of branching candidates */
1815 	               &bestcand                    /* the best branching candidate found by SCIP */
1816 	            ) );
1817 	         }
1818 	      }
1819 	
1820 	      /* free buffer for the lp gains and pseudocost scores */
1821 	      SCIPfreeBufferArray(scip, &scoresfromothers);
1822 	      SCIPfreeBufferArray(scip, &scoresfrompc);
1823 	      SCIPfreeBufferArray(scip, &scores);
1824 	      SCIPfreeBufferArray(scip, &maxgains);
1825 	      SCIPfreeBufferArray(scip, &mingains);
1826 	
1827 	      /* free buffer for the unreliable candidates */
1828 	      SCIPfreeBufferArray(scip, &initcandscores);
1829 	      SCIPfreeBufferArray(scip, &initcands);
1830 	   }
1831 	
1832 	   /* if no domain could be reduced, create the branching */
1833 	   if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED && executebranch )
1834 	   {
1835 	      SCIP_NODE* downchild;
1836 	      SCIP_NODE* upchild;
1837 	      SCIP_VAR* var;
1838 	      SCIP_Real val;
1839 	
1840 	      assert(*result == SCIP_DIDNOTRUN);
1841 	      assert(0 <= bestcand && bestcand < nbranchcands);
1842 	      assert(!SCIPisFeasIntegral(scip, branchcandssol[bestcand]));
1843 	      assert(!allcolsinlp || SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1844 	      assert(!bestsbdowncutoff && !bestsbupcutoff);
1845 	
1846 	      var = branchcands[bestcand];
1847 	      val = branchcandssol[bestcand];
1848 	
1849 	      /* perform the branching */
1850 	      SCIPdebugMsg(scip, " -> %d (%d) cands, sel cand %d: var <%s> (sol=%g, down=%g (%+g), up=%g (%+g), sb=%u, psc=%g/%g [%g])\n",
1851 	         nbranchcands, ninitcands, bestcand, SCIPvarGetName(var), branchcandssol[bestcand],
1852 	         bestsbdown, bestsbdown - lpobjval, bestsbup, bestsbup - lpobjval, bestisstrongbranch,
1853 	         SCIPgetVarPseudocostCurrentRun(scip, var, SCIP_BRANCHDIR_DOWNWARDS),
1854 	         SCIPgetVarPseudocostCurrentRun(scip, var, SCIP_BRANCHDIR_UPWARDS),
1855 	         SCIPgetVarPseudocostScoreCurrentRun(scip, var, branchcandssol[bestcand]));
1856 	      SCIP_UNUSED(bestisstrongbranch);
1857 	      SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, NULL, &upchild) );
1858 	      assert(downchild != NULL);
1859 	      assert(upchild != NULL);
1860 	
1861 	      /* update the lower bounds in the children */
1862 	      if( sbvars[bestcand] && allcolsinlp && !exactsolve )
1863 	      {
1864 	         if( sbdownvalid[bestcand] )
1865 	         {
1866 	            assert(SCIPisLT(scip, sbdown[bestcand], SCIPgetCutoffbound(scip)));
1867 	            SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, sbdown[bestcand]) );
1868 	            assert(SCIPisGE(scip, SCIPgetNodeLowerbound(scip, downchild), provedbound));
1869 	         }
1870 	         if( sbupvalid[bestcand] )
1871 	         {
1872 	            assert(SCIPisLT(scip, sbup[bestcand], SCIPgetCutoffbound(scip)));
1873 	            SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, sbup[bestcand]) );
1874 	            assert(SCIPisGE(scip, SCIPgetNodeLowerbound(scip, upchild), provedbound));
1875 	         }
1876 	      }
1877 	
1878 	      SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
1879 	      SCIPdebugMsg(scip, " -> up child's lowerbound  : %g\n", SCIPnodeGetLowerbound(upchild));
1880 	
1881 	      assert(SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_INFEASIBLE && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OBJLIMIT);
1882 	
1883 	      *result = SCIP_BRANCHED;
1884 	   }
1885 	
1886 	   /* free buffer for the strong branching lp gains */
1887 	   SCIPfreeBufferArray(scip, &sbvars);
1888 	   SCIPfreeBufferArray(scip, &sbupvalid);
1889 	   SCIPfreeBufferArray(scip, &sbdownvalid);
1890 	   SCIPfreeBufferArray(scip, &sbup);
1891 	   SCIPfreeBufferArray(scip, &sbdown);
1892 	
1893 	   return SCIP_OKAY;
1894 	}
1895 	
1896 	
1897 	/*
1898 	 * Callback methods
1899 	 */
1900 	
1901 	/** copy method for branchrule plugins (called when SCIP copies plugins) */
1902 	static
1903 	SCIP_DECL_BRANCHCOPY(branchCopyRelpscost)
1904 	{  /*lint --e{715}*/
1905 	   assert(scip != NULL);
1906 	   assert(branchrule != NULL);
1907 	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1908 	
1909 	   /* call inclusion method of branchrule */
1910 	   SCIP_CALL( SCIPincludeBranchruleRelpscost(scip) );
1911 	
1912 	   return SCIP_OKAY;
1913 	}
1914 	
1915 	/** destructor of branching rule to free user data (called when SCIP is exiting) */
1916 	static
1917 	SCIP_DECL_BRANCHFREE(branchFreeRelpscost)
1918 	{  /*lint --e{715}*/
1919 	   SCIP_BRANCHRULEDATA* branchruledata;
1920 	   branchruledata = SCIPbranchruleGetData(branchrule);
1921 	
1922 	   /* free Treemodel parameter data structure */
1923 	   SCIP_CALL( SCIPtreemodelFree(scip, &branchruledata->treemodel) );
1924 	
1925 	   /* free branching rule data */
1926 	   SCIPfreeBlockMemory(scip, &branchruledata);
1927 	   SCIPbranchruleSetData(branchrule, NULL);
1928 	
1929 	   return SCIP_OKAY;
1930 	}
1931 	
1932 	
1933 	/** solving process initialization method of branching rule (called when branch and bound process is about to begin) */
1934 	static
1935 	SCIP_DECL_BRANCHINITSOL(branchInitsolRelpscost)
1936 	{  /*lint --e{715}*/
1937 	   SCIP_BRANCHRULEDATA* branchruledata;
1938 	
1939 	   /* initialize branching rule data */
1940 	   branchruledata = SCIPbranchruleGetData(branchrule);
1941 	   branchruledata->nlcount = NULL;
1942 	   branchruledata->nlcountsize = 0;
1943 	   branchruledata->nlcountmax = 1;
1944 	   assert(branchruledata->startrandseed >= 0);
1945 	
1946 	   /* create a random number generator */
1947 	   SCIP_CALL( SCIPcreateRandom(scip, &branchruledata->randnumgen,
1948 	         (unsigned int)branchruledata->startrandseed, TRUE) );
1949 	
1950 	   return SCIP_OKAY;
1951 	}
1952 	
1953 	
1954 	/** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */
1955 	static
1956 	SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpscost)
1957 	{  /*lint --e{715}*/
1958 	   SCIP_BRANCHRULEDATA* branchruledata;
1959 	
1960 	   /* free memory in branching rule data */
1961 	   branchruledata = SCIPbranchruleGetData(branchrule);
1962 	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->nlcount, branchruledata->nlcountsize);
1963 	
1964 	   /* free random number generator */
1965 	   SCIPfreeRandom(scip, &branchruledata->randnumgen);
1966 	
1967 	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->orbitrep, branchruledata->npermvars);
1968 	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->varorbitmap, branchruledata->npermvars);
1969 	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->orbitbegins, branchruledata->npermvars);
1970 	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->orbits, branchruledata->npermvars);
1971 	   branchruledata->nosymmetry = FALSE;
1972 	   branchruledata->norbits = 0;
1973 	   branchruledata->permvars = NULL;
1974 	   branchruledata->permvarmap = NULL;
1975 	   branchruledata->npermvars = 0;
1976 	
1977 	   return SCIP_OKAY;
1978 	}
1979 	
1980 	
1981 	/** branching execution method for fractional LP solutions */
1982 	static
1983 	SCIP_DECL_BRANCHEXECLP(branchExeclpRelpscost)
1984 	{  /*lint --e{715}*/
1985 	   SCIP_BRANCHRULEDATA* branchruledata;
1986 	   SCIP_VAR** lpcands;
1987 	   SCIP_Real* lpcandssol;
1988 	   SCIP_Real* lpcandsfrac;
1989 	   SCIP_VAR** filteredlpcands;
1990 	   SCIP_Real* filteredlpcandssol;
1991 	   SCIP_Real* filteredlpcandsfrac;
1992 	   SCIP_Bool runfiltering;
1993 	   int* filteredlpcandsorbitidx = NULL;
1994 	   int nfilteredlpcands;
1995 	   int nlpcands;
1996 	
1997 	   assert(branchrule != NULL);
1998 	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1999 	   assert(scip != NULL);
2000 	   assert(result != NULL);
2001 	
2002 	   SCIPdebugMsg(scip, "Execlp method of relpscost branching in node %" SCIP_LONGINT_FORMAT "\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
2003 	
2004 	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2005 	   {
2006 	      *result = SCIP_DIDNOTRUN;
2007 	      SCIPdebugMsg(scip, "Could not apply relpscost branching, as the current LP was not solved to optimality.\n");
2008 	
2009 	      return SCIP_OKAY;
2010 	   }
2011 	
2012 	   /* get branching candidates */
2013 	   SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, NULL, &nlpcands, NULL) );
2014 	   assert(nlpcands > 0);
2015 	
2016 	   branchruledata = SCIPbranchruleGetData(branchrule);
2017 	   assert(branchruledata != NULL);
2018 	
2019 	   /* determine whether we should run filtering */
2020 	   runfiltering = ! branchruledata->nosymmetry && branchruledata->filtercandssym && SCIPgetSubscipDepth(scip) == 0 && ! SCIPinDive(scip) && ! SCIPinProbing(scip);
2021 	
2022 	   /* init orbits if necessary */
2023 	   if( runfiltering )
2024 	   {
2025 	      SCIP_CALL( initOrbits(scip, branchruledata) );
2026 	   }
2027 	
2028 	   /* determine fractional variables (possibly filter by using symmetries) */
2029 	   if( runfiltering && branchruledata->norbits != 0 )
2030 	   {
2031 	      SCIP_CALL( SCIPallocBufferArray(scip, &filteredlpcands, nlpcands) );
2032 	      SCIP_CALL( SCIPallocBufferArray(scip, &filteredlpcandssol, nlpcands) );
2033 	      SCIP_CALL( SCIPallocBufferArray(scip, &filteredlpcandsfrac, nlpcands) );
2034 	      SCIP_CALL( SCIPallocBufferArray(scip, &filteredlpcandsorbitidx, nlpcands) );
2035 	
2036 	      /* determine filtered fractional variables */
2037 	      SCIP_CALL( filterSymmetricVariables(scip, branchruledata, lpcands, lpcandssol, lpcandsfrac, nlpcands,
2038 	            filteredlpcands, filteredlpcandssol, filteredlpcandsfrac, filteredlpcandsorbitidx, &nfilteredlpcands) );
2039 	   }
2040 	   else
2041 	   {
2042 	      /* No orbits available. Copy all (unfiltered) branching candidates, because they will be updated w.r.t. the strong branching LP solution */
2043 	      SCIP_CALL( SCIPduplicateBufferArray(scip, &filteredlpcands, lpcands, nlpcands) );
2044 	      SCIP_CALL( SCIPduplicateBufferArray(scip, &filteredlpcandssol, lpcandssol, nlpcands) );
2045 	      SCIP_CALL( SCIPduplicateBufferArray(scip, &filteredlpcandsfrac, lpcandsfrac, nlpcands) );
2046 	      nfilteredlpcands = nlpcands;
2047 	   }
2048 	
2049 	   /* execute branching rule */
2050 	   SCIP_CALL( execRelpscost(scip, branchrule, filteredlpcands, filteredlpcandssol, filteredlpcandsfrac, filteredlpcandsorbitidx, nfilteredlpcands, TRUE, result) );
2051 	
2052 	   SCIPfreeBufferArrayNull(scip, &filteredlpcandsorbitidx);
2053 	   SCIPfreeBufferArray(scip, &filteredlpcandsfrac);
2054 	   SCIPfreeBufferArray(scip, &filteredlpcandssol);
2055 	   SCIPfreeBufferArray(scip, &filteredlpcands);
2056 	
2057 	   return SCIP_OKAY;
2058 	}
2059 	
2060 	
2061 	/*
2062 	 * branching specific interface methods
2063 	 */
2064 	
2065 	/** creates the reliable pseudo cost branching rule and includes it in SCIP */
2066 	SCIP_RETCODE SCIPincludeBranchruleRelpscost(
2067 	   SCIP*                 scip                /**< SCIP data structure */
2068 	   )
2069 	{
2070 	   SCIP_BRANCHRULEDATA* branchruledata;
2071 	   SCIP_BRANCHRULE* branchrule;
2072 	
2073 	   /* create relpscost branching rule data */
2074 	   SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
2075 	
2076 	   branchruledata->nosymmetry = FALSE;
2077 	   branchruledata->orbits = NULL;
2078 	   branchruledata->orbitbegins = NULL;
2079 	   branchruledata->orbitrep = NULL;
2080 	   branchruledata->varorbitmap = NULL;
2081 	   branchruledata->norbits = 0;
2082 	   branchruledata->permvars = NULL;
2083 	   branchruledata->npermvars = 0;
2084 	   branchruledata->permvarmap = NULL;
2085 	
2086 	   /* include branching rule */
2087 	   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
2088 	         BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
2089 	
2090 	   assert(branchrule != NULL);
2091 	
2092 	   /* set non-fundamental callbacks via specific setter functions*/
2093 	   SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyRelpscost) );
2094 	   SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeRelpscost) );
2095 	   SCIP_CALL( SCIPsetBranchruleInitsol(scip, branchrule, branchInitsolRelpscost) );
2096 	   SCIP_CALL( SCIPsetBranchruleExitsol(scip, branchrule, branchExitsolRelpscost) );
2097 	   SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpRelpscost) );
2098 	
2099 	   /* relpscost branching rule parameters */
2100 	   SCIP_CALL( SCIPaddRealParam(scip,
2101 	         "branching/relpscost/conflictweight",
2102 	         "weight in score calculations for conflict score",
2103 	         &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2104 	   SCIP_CALL( SCIPaddRealParam(scip,
2105 	         "branching/relpscost/conflictlengthweight",
2106 	         "weight in score calculations for conflict length score",
2107 	         &branchruledata->conflengthweight, TRUE, DEFAULT_CONFLENGTHWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2108 	   SCIP_CALL( SCIPaddRealParam(scip,
2109 	         "branching/relpscost/inferenceweight",
2110 	         "weight in score calculations for inference score",
2111 	         &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2112 	   SCIP_CALL( SCIPaddRealParam(scip,
2113 	         "branching/relpscost/cutoffweight",
2114 	         "weight in score calculations for cutoff score",
2115 	         &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2116 	   SCIP_CALL( SCIPaddRealParam(scip,
2117 	          "branching/relpscost/gmiavgeffweight",
2118 	          "weight in score calculations for average GMI cuts normalized efficacy",
2119 	          &branchruledata->gmiavgeffweight, TRUE, DEFAULT_GMIAVGEFFWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2120 	   SCIP_CALL( SCIPaddRealParam(scip,
2121 	          "branching/relpscost/gmilasteffweight",
2122 	          "weight in score calculations for last GMI cuts normalized efficacy",
2123 	          &branchruledata->gmilasteffweight, TRUE, DEFAULT_GMILASTEFFWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2124 	   SCIP_CALL( SCIPaddRealParam(scip,
2125 	         "branching/relpscost/pscostweight",
2126 	         "weight in score calculations for pseudo cost score",
2127 	         &branchruledata->pscostweight, TRUE, DEFAULT_PSCOSTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2128 	   SCIP_CALL( SCIPaddRealParam(scip,
2129 	         "branching/relpscost/nlscoreweight",
2130 	         "weight in score calculations for nlcount score",
2131 	         &branchruledata->nlscoreweight, TRUE, DEFAULT_NLSCOREWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2132 	   SCIP_CALL( SCIPaddRealParam(scip,
2133 	         "branching/relpscost/minreliable",
2134 	         "minimal value for minimum pseudo cost size to regard pseudo cost value as reliable",
2135 	         &branchruledata->minreliable, TRUE, DEFAULT_MINRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2136 	   SCIP_CALL( SCIPaddRealParam(scip,
2137 	         "branching/relpscost/maxreliable",
2138 	         "maximal value for minimum pseudo cost size to regard pseudo cost value as reliable",
2139 	         &branchruledata->maxreliable, TRUE, DEFAULT_MAXRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2140 	   SCIP_CALL( SCIPaddRealParam(scip,
2141 	         "branching/relpscost/sbiterquot",
2142 	         "maximal fraction of strong branching LP iterations compared to node relaxation LP iterations",
2143 	         &branchruledata->sbiterquot, FALSE, DEFAULT_SBITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2144 	   SCIP_CALL( SCIPaddIntParam(scip,
2145 	         "branching/relpscost/sbiterofs",
2146 	         "additional number of allowed strong branching LP iterations",
2147 	         &branchruledata->sbiterofs, FALSE, DEFAULT_SBITEROFS, 0, INT_MAX, NULL, NULL) );
2148 	   SCIP_CALL( SCIPaddIntParam(scip,
2149 	         "branching/relpscost/maxlookahead",
2150 	         "maximal number of further variables evaluated without better score",
2151 	         &branchruledata->maxlookahead, TRUE, DEFAULT_MAXLOOKAHEAD, 1, INT_MAX, NULL, NULL) );
2152 	   SCIP_CALL( SCIPaddIntParam(scip,
2153 	         "branching/relpscost/initcand",
2154 	         "maximal number of candidates initialized with strong branching per node",
2155 	         &branchruledata->initcand, FALSE, DEFAULT_INITCAND, 0, INT_MAX, NULL, NULL) );
2156 	   SCIP_CALL( SCIPaddIntParam(scip,
2157 	         "branching/relpscost/inititer",
2158 	         "iteration limit for strong branching initializations of pseudo cost entries (0: auto)",
2159 	         &branchruledata->inititer, FALSE, DEFAULT_INITITER, 0, INT_MAX, NULL, NULL) );
2160 	   SCIP_CALL( SCIPaddIntParam(scip,
2161 	         "branching/relpscost/maxbdchgs",
2162 	         "maximal number of bound tightenings before the node is reevaluated (-1: unlimited)",
2163 	         &branchruledata->maxbdchgs, TRUE, DEFAULT_MAXBDCHGS, -1, INT_MAX, NULL, NULL) );
2164 	   SCIP_CALL( SCIPaddIntParam(scip,
2165 	         "branching/relpscost/maxproprounds",
2166 	         "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
2167 	         &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
2168 	   SCIP_CALL( SCIPaddBoolParam(scip,
2169 	         "branching/relpscost/probingbounds",
2170 	         "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
2171 	         &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
2172 	
2173 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/userelerrorreliability",
2174 	         "should reliability be based on relative errors?", &branchruledata->userelerrorforreliability, TRUE, DEFAULT_USERELERRORFORRELIABILITY,
2175 	         NULL, NULL) );
2176 	
2177 	   SCIP_CALL( SCIPaddRealParam(scip, "branching/relpscost/lowerrortol", "low relative error tolerance for reliability",
2178 	         &branchruledata->lowerrortol, TRUE, DEFAULT_LOWERRORTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2179 	
2180 	   SCIP_CALL( SCIPaddRealParam(scip, "branching/relpscost/higherrortol", "high relative error tolerance for reliability",
2181 	         &branchruledata->higherrortol, TRUE, DEFAULT_HIGHERRORTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2182 	
2183 	/**! [SnippetCodeStyleParenIndent] */
2184 	
2185 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/storesemiinitcosts",
2186 	         "should strong branching result be considered for pseudo costs if the other direction was infeasible?",
2187 	         &branchruledata->storesemiinitcosts, TRUE, DEFAULT_STORESEMIINITCOSTS,
2188 	         NULL, NULL) );
2189 	
2190 	/**! [SnippetCodeStyleParenIndent] */
2191 	
2192 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usesblocalinfo",
2193 	         "should the scoring function use only local cutoff and inference information obtained for strong branching candidates?",
2194 	         &branchruledata->usesblocalinfo, TRUE, DEFAULT_USESBLOCALINFO,
2195 	         NULL, NULL) );
2196 	
2197 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usehyptestforreliability",
2198 	         "should the strong branching decision be based on a hypothesis test?",
2199 	         &branchruledata->usehyptestforreliability, TRUE, DEFAULT_USEHYPTESTFORRELIABILITY,
2200 	         NULL, NULL) );
2201 	
2202 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usedynamicconfidence",
2203 	         "should the confidence level be adjusted dynamically?",
2204 	         &branchruledata->usedynamicconfidence, TRUE, DEFAULT_USEDYNAMICCONFIDENCE,
2205 	         NULL, NULL) );
2206 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/skipbadinitcands",
2207 	         "should branching rule skip candidates that have a low probability to "
2208 	         "be better than the best strong-branching or pseudo-candidate?",
2209 	         &branchruledata->skipbadinitcands, TRUE, DEFAULT_SKIPBADINITCANDS,
2210 	         NULL, NULL) );
2211 	   SCIP_CALL( SCIPaddIntParam(scip,
2212 	         "branching/relpscost/confidencelevel",
2213 	         "the confidence level for statistical methods, between 0 (Min) and 4 (Max).",
2214 	         &branchruledata->confidencelevel, TRUE, DEFAULT_CONFIDENCELEVEL, 0, 4, NULL, NULL) );
2215 	
2216 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/randinitorder",
2217 	         "should candidates be initialized in randomized order?",
2218 	         &branchruledata->randinitorder, TRUE, DEFAULT_RANDINITORDER,
2219 	         NULL, NULL) );
2220 	
2221 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usesmallweightsitlim",
2222 	         "should smaller weights be used for pseudo cost updates after hitting the LP iteration limit?",
2223 	         &branchruledata->usesmallweightsitlim, TRUE, DEFAULT_USESMALLWEIGHTSITLIM,
2224 	         NULL, NULL) );
2225 	
2226 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/dynamicweights",
2227 	         "should the weights of the branching rule be adjusted dynamically during solving based on objective and infeasible leaf counters?",
2228 	         &branchruledata->dynamicweights, TRUE, DEFAULT_DYNAMICWEIGHTS,
2229 	         NULL, NULL) );
2230 	   SCIP_CALL( SCIPaddIntParam(scip, "branching/relpscost/degeneracyaware",
2231 	         "should degeneracy be taken into account to update weights and skip strong branching? (0: off, 1: after root, 2: always)",
2232 	         &branchruledata->degeneracyaware, TRUE, DEFAULT_DEGENERACYAWARE, 0, 2,
2233 	         NULL, NULL) );
2234 	   SCIP_CALL( SCIPaddIntParam(scip, "branching/relpscost/startrandseed", "start seed for random number generation",
2235 	         &branchruledata->startrandseed, TRUE, DEFAULT_STARTRANDSEED, 0, INT_MAX, NULL, NULL) );
2236 	
2237 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/filtercandssym",
2238 	         "Use symmetry to filter branching candidates?",
2239 	         &branchruledata->filtercandssym, TRUE, DEFAULT_FILTERCANDSSYM, NULL, NULL) );
2240 	
2241 	   SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/transsympscost",
2242 	         "Transfer pscost information to symmetric variables?",
2243 	         &branchruledata->transsympscost, TRUE, DEFAULT_TRANSSYMPSCOST, NULL, NULL) );
2244 	
2245 	   /* initialise the Treemodel parameters */
2246 	   SCIP_CALL( SCIPtreemodelInit(scip, &branchruledata->treemodel) );
2247 	
2248 	   return SCIP_OKAY;
2249 	}
2250 	
2251 	/** execution reliability pseudo cost branching with the given branching candidates */
2252 	SCIP_RETCODE SCIPexecRelpscostBranching(
2253 	   SCIP*                 scip,               /**< SCIP data structure */
2254 	   SCIP_VAR**            branchcands,        /**< branching candidates */
2255 	   SCIP_Real*            branchcandssol,     /**< solution value for the branching candidates */
2256 	   SCIP_Real*            branchcandsfrac,    /**< fractional part of the branching candidates */
2257 	   int                   nbranchcands,       /**< number of branching candidates */
2258 	   SCIP_Bool             executebranching,   /**< perform a branching step after probing */
2259 	   SCIP_RESULT*          result              /**< pointer to the result of the execution */
2260 	   )
2261 	{
2262 	   SCIP_BRANCHRULE* branchrule;
2263 	
2264 	   assert(scip != NULL);
2265 	   assert(result != NULL);
2266 	
2267 	   /* find branching rule */
2268 	   branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
2269 	   assert(branchrule != NULL);
2270 	
2271 	   /* execute branching rule */
2272 	   SCIP_CALL( execRelpscost(scip, branchrule, branchcands, branchcandssol, branchcandsfrac, NULL, nbranchcands, executebranching, result) );
2273 	
2274 	   return SCIP_OKAY;
2275 	}
2276