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   	/**@file   branch_multaggr.c
25   	 * @ingroup DEFPLUGINS_BRANCH
26   	 * @brief  fullstrong branching on fractional and multi-aggregated variables
27   	 * @author Anna Melchiori
28   	 * @author Gerald Gamrath
29   	 *
30   	 * This branching rule uses all fractional binary and integer variables as candidates,
31   	 * as well as fractional multiaggregated binary and integer variables. Although not
32   	 * directly contained in the presolved problem anymore, the multi-aggregation provides
33   	 * an affine linear sum of integer variables, on which branching can be performed.
34   	 *
35   	 * For more details, see
36   	 * G.Gamrath, A.Melchiori, T.Berthold, A.M.Gleixner, D.Salvagnin: Branching on Multi-aggregated Variables
37   	 * (http://dx.doi.org/10.1007/978-3-319-18008-3_10)
38   	 */
39   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40   	
41   	#include "blockmemshell/memory.h"
42   	#include "scip/branch_fullstrong.h"
43   	#include "scip/branch_multaggr.h"
44   	#include "scip/cons_linear.h"
45   	#include "scip/pub_branch.h"
46   	#include "scip/pub_cons.h"
47   	#include "scip/pub_message.h"
48   	#include "scip/pub_tree.h"
49   	#include "scip/pub_var.h"
50   	#include "scip/scip_branch.h"
51   	#include "scip/scip_cons.h"
52   	#include "scip/scip_general.h"
53   	#include "scip/scip_lp.h"
54   	#include "scip/scip_mem.h"
55   	#include "scip/scip_message.h"
56   	#include "scip/scip_numerics.h"
57   	#include "scip/scip_param.h"
58   	#include "scip/scip_prob.h"
59   	#include "scip/scip_probing.h"
60   	#include "scip/scip_solvingstats.h"
61   	#include "scip/scip_timing.h"
62   	#include "scip/scip_tree.h"
63   	#include "scip/scip_var.h"
64   	#include "scip/set.h"
65   	#include "scip/struct_scip.h"
66   	#include "scip/var.h"
67   	#include <string.h>
68   	
69   	#define BRANCHRULE_NAME            "multaggr"
70   	#define BRANCHRULE_DESC            "fullstrong branching on fractional and multi-aggregated variables"
71   	#define BRANCHRULE_PRIORITY        0
72   	#define BRANCHRULE_MAXDEPTH        -1
73   	#define BRANCHRULE_MAXBOUNDDIST    1.0
74   	
75   	
76   	#define DEFAULT_REEVALAGE         0LL        /**< number of intermediate LPs solved to trigger reevaluation of strong branching
77   	                                              *   value for a variable that was already evaluated at the current node */
78   	#define DEFAULT_MAXPROPROUNDS       0        /**< maximum number of propagation rounds to be performed during multaggr branching
79   	                                              *   before solving the LP (-1: no limit, -2: parameter settings) */
80   	#define DEFAULT_PROBINGBOUNDS    TRUE        /**< should valid bounds be identified in a probing-like fashion during multi-aggr
81   	                                              *   branching (only with propagation)? */
82   	
83   	/*
84   	 * Data structures
85   	 */
86   	
87   	/** branching rule data */
88   	struct SCIP_BranchruleData
89   	{
90   	   SCIP_Longint          reevalage;          /**< number of intermediate LPs solved to trigger reevaluation of strong branching
91   	                                              *   value for a variable that was already evaluated at the current node */
92   	   SCIP_Bool             probingbounds;      /**< should valid bounds be identified in a probing-like fashion during strong
93   	                                              *   branching (only with propagation)? */
94   	   int                   lastcand;           /**< last evaluated candidate of last branching rule execution */
95   	   int                   maxproprounds;      /**< maximum number of propagation rounds to be performed during strong branching
96   	                                              *   before solving the LP (-1: no limit, -2: parameter settings) */
97   	   int                   skipsize;           /**< size of skipdown and skipup array */
98   	   SCIP_Bool*            skipdown;           /**< should be branching on down child be skipped? */
99   	   SCIP_Bool*            skipup;             /**< should be branching on up child be skipped? */
100  	#ifdef SCIP_STATISTIC
101  	   SCIP_CLOCK*           clckstrongbr;       /**< clock to store the time spent inside the strong branching function on fractional variables */
102  	   SCIP_CLOCK*           clckmultaggrbr;     /**< clock to store the time spent inside the strong branching function on multi-aggragated variables */
103  	   SCIP_Real*            ratioggain;         /**< for each occurence of a branching on a multi-aggregated variable we store the ratio of the gain that
104  	                                              *   we would have obtained branching on the best fractional variable over the gain obtained
105  	                                              *   branching on the current multi-aggregated variable */
106  	   SCIP_Real             ameanratio;         /**< arithmetic mean of the ratioggain array */
107  	   SCIP_Bool             noupdate;           /**< pointer to store if the probing LP has not been solved so we do not want to
108  	                                              *   update statistics */
109  	   int                   firstmultaggrdepth; /**< depth of the first branching on a multi-aggregated variable */
110  	   int                   rundepth;           /**< the run of the first multi-aggregated branching */
111  	   int                   nmultaggrbranch;    /**< number of branchings on multi-aggregated variables */
112  	   int                   nfracbranch;        /**< number of branchings on fractional variables */
113  	   int                   nEscore;            /**< number of times that the bestscore over all multi-aggregated variables is equal to the best
114  	                                              *   fractional variables score and thus we do not branch on the multi-aggregate variable */
115  	   int                   nmultaggrcutoff;    /**< number of cutoffs detected during the probing mode on multi-aggregated variables */
116  	   int                   nmultaggrconsadd;   /**< number of times that a probing constraint of a multi-aggregated variable has been
117  	                                              *   added to the original problem */
118  	   int                   nfractcutoff;       /**< number of cutoffs detected during strong branching on fractional variables */
119  	   int                   nfractconsadd;      /**< number of times that during strong branching on fractional variables a constraint has been
120  	                                              *   added to the original problem or a variables domain has been reduced */
121  	   int                   nmultaggrvars;      /**< number of multi-aggregated variables in the problem of the last run */
122  	   int                   nrun;               /**< number of restarts */
123  	   int                   size;               /**< size of the provided array to store the ratio gain */
124  	   int                   nstrongbrcall;      /**< number of times that the selectVarstrongBranching function has been called */
125  	   int                   nmultaggrbrcall;    /**< number of times that the selectVarMultAggrBranching function has been called */
126  	   int                   totallpcands;       /**< total number of observed lpcands over all selectVarstrongBranching function calls */
127  	   int                   totalmultaggrcands; /**< total number of observed multi-aggregregated candidates over all selectVarMultAggrBranching
128  	                                              *   function calls */
129  	#endif
130  	};
131  	
132  	
133  	/*
134  	 * Local methods
135  	 */
136  	
137  	/* this function ensures that the allocated memory is enough to store statistics data */
138  	#ifdef SCIP_STATISTIC
139  	static
140  	SCIP_RETCODE ensureArraySize(
141  	   SCIP*                 scip,               /**< original SCIP data structure */
142  	   SCIP_BRANCHRULEDATA*  branchruledata      /**< branching rule data */
143  	   )
144  	{
145  	   assert(scip != NULL);
146  	   assert(branchruledata != NULL);
147  	   assert(branchruledata->ratioggain != NULL);
148  	   assert(branchruledata->nmultaggrbranch >= 0);
149  	   assert(branchruledata->size >= 0);
150  	
151  	   /* check whether the size of the array is big enough; reallocate memory if needed */
152  	   if( branchruledata->nmultaggrbranch + 1 > branchruledata->size )
153  	   {
154  	      int newsize = SCIPcalcMemGrowSize(scip, branchruledata->nmultaggrbranch + 1);
155  	      assert(newsize >= branchruledata->nmultaggrbranch + 1);
156  	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->ratioggain, branchruledata->size, newsize) );
157  	      branchruledata->size = newsize;
158  	   }
159  	   return SCIP_OKAY;
160  	}
161  	#endif
162  	
163  	/* this function gives us the best candidate for branching among the multi-aggregated variables of the problem
164  	 * and the best fractional integer variable already selected by strong branching
165  	*/
166  	static
167  	SCIP_RETCODE selectVarMultAggrBranching(
168  	   SCIP*                 scip,               /**< original SCIP data structure */
169  	   SCIP_VAR**            bestcand,           /**< the best candidate variable selected by strong branching */
170  	   SCIP_Real*            bestscore,          /**< score of the best branching candidate */
171  	   SCIP_Real*            bestsol,            /**< solution value of the best branching candidate */
172  	   SCIP_Real*            bestdown,           /**< objective value of the down node when branching on bestcand */
173  	   SCIP_Real*            bestup,             /**< objective value of the up node when branching on bestcand */
174  	   SCIP_Bool*            bestdownvalid,      /**< is bestdown a valid dual bound for the down branch? */
175  	   SCIP_Bool*            bestupvalid,        /**< is bestup a valid dual bound for the up branch? */
176  	   SCIP_Real*            provedbound,        /**< proved dual bound for the current subtree */
177  	   SCIP_Real*            estimatedown,       /**< pointer to store the down child nodes estimate */
178  	   SCIP_Real*            estimateup,         /**< pointer to store the up child nodes estimate */
179  	#ifdef SCIP_STATISTIC
180  	   SCIP_Real*            bestmultaggrscore,  /**< pointer to store the multi aggregated score */
181  	#endif
182  	   SCIP_RESULT*          result              /**< pointer to store results of branching */
183  	   )
184  	{
185  	   SCIP_VAR** fixvars;
186  	   SCIP_CONS* probingconsdown;
187  	   SCIP_CONS* probingconsup;
188  	   SCIP_NODE* node;
189  	   SCIP_Real* fixvarssols;
190  	   SCIP_Real fixvarssol;
191  	   SCIP_Real lpobjval;
192  	   SCIP_Bool exactsolve;
193  	   SCIP_Bool allcolsinlp;
194  	   SCIP_Bool downnodeinf = FALSE;
195  	   SCIP_Bool startprobing = TRUE;
196  	   SCIP_Bool endprobing = FALSE;
197  	   int nfixvars;
198  	   int i;
199  	   int j;
200  	   int k;
201  	
202  	   /* import branchrule data for statistics */
203  	#ifdef SCIP_STATISTIC
204  	   SCIP_BRANCHRULE* branchrule;
205  	   SCIP_BRANCHRULEDATA* branchruledata;
206  	
207  	   branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
208  	   assert(branchrule != NULL);
209  	
210  	   branchruledata = SCIPbranchruleGetData(branchrule);
211  	   assert(branchruledata != NULL);
212  	#endif
213  	
214  	   assert(scip != NULL);
215  	   assert(bestcand != NULL);
216  	   assert(bestscore != NULL);
217  	
218  	   /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
219  	    * for cutting off sub problems and improving lower bounds of children
220  	    */
221  	   exactsolve = SCIPisExactSolve(scip);
222  	
223  	   /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
224  	   allcolsinlp = SCIPallColsInLP(scip);
225  	
226  	   /* get fixed variables */
227  	   fixvars = SCIPgetFixedVars(scip);
228  	   nfixvars = SCIPgetNFixedVars(scip);
229  	   SCIPdebugMsg(scip, " fractional variable: <%s> with value: %f is selected by strong branching\n", SCIPvarGetName(*bestcand), *bestsol);
230  	
231  	   /* check if we would exceed the depth limit */
232  	   if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
233  	   {
234  	      SCIPdebugMsg(scip, "cannot perform probing in selectVarMultAggrBranching, depth limit reached.\n");
235  	      *result = SCIP_DIDNOTRUN;
236  	      return SCIP_OKAY;
237  	   }
238  	
239  	   if( nfixvars != 0 )
240  	   {
241  	      assert(fixvars != NULL);
242  	
243  	      SCIP_CALL( SCIPallocBufferArray(scip, &fixvarssols, nfixvars) );
244  	      lpobjval = SCIPgetLPObjval(scip);
245  	
246  	      /* store the values of the fixed variables at the current optimal solution */
247  	      for( i = 0; i < nfixvars; i++ )
248  	      {
249  	         assert(fixvars[i] != NULL);
250  	         fixvarssols[i] = SCIPvarGetLPSol(fixvars[i]);
251  	      }
252  	
253  	      for( i = 0; i < nfixvars; i++ )
254  	      {
255  	         assert(fixvars[i] != NULL);
256  	
257  	         /* only integer and binary multi-aggregated variables are potential branching candidates */
258  	         if( SCIPvarGetStatus(fixvars[i]) == SCIP_VARSTATUS_MULTAGGR && (SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_INTEGER ||
259  	               SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_BINARY) )
260  	         {
261  	            fixvarssol = fixvarssols[i];
262  	
263  	            /* start probing mode for the fractional multi-aggregated variable */
264  	            if( !SCIPisFeasIntegral(scip, fixvarssol) )
265  	            {
266  	               SCIP_VAR** downvars = NULL;
267  	               SCIP_VAR** upvars = NULL;
268  	               SCIP_Real* downvarssols = NULL;
269  	               SCIP_Real* upvarssols = NULL;
270  	               SCIP_LPSOLSTAT solstatdown;
271  	               SCIP_LPSOLSTAT solstatup;
272  	               SCIP_Real downobjval;
273  	               SCIP_Real upobjval;
274  	               SCIP_Real estimateprobdown = 0.0;
275  	               SCIP_Real estimateprobup = 0.0;
276  	               SCIP_Bool downinf;
277  	               SCIP_Bool upinf;
278  	               SCIP_Bool lperror;
279  	               int ndownvars;
280  	               int nupvars;
281  	
282  	               /* start the probing mode if this is the first entrance */
283  	               if( startprobing )
284  	               {
285  	                  SCIP_CALL( SCIPstartProbing(scip) );
286  	                  startprobing = FALSE;
287  	                  endprobing = TRUE;
288  	
289  	                  SCIPdebugMsg(scip, "PROBING MODE:\n");
290  	               }
291  	
292  	               SCIPdebugMsg(scip, " multi-aggregated variable: <%s> with value: %f\n", SCIPvarGetName(fixvars[i]), fixvarssol);
293  	
294  	               SCIPstatistic(branchruledata->totalmultaggrcands += 1);
295  	
296  	               /* create the multi-aggregated rounded down constraint */
297  	               SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsdown, "probingconsdown", SCIPvarGetMultaggrNVars(fixvars[i]),
298  	                     SCIPvarGetMultaggrVars(fixvars[i]), SCIPvarGetMultaggrScalars(fixvars[i]), -SCIPinfinity(scip),
299  	                     SCIPfeasFloor(scip, fixvarssol) - SCIPvarGetMultaggrConstant(fixvars[i]), TRUE, TRUE, FALSE, FALSE,
300  	                     TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
301  	               assert(probingconsdown != NULL);
302  	
303  	               /* create the down child probing node */
304  	               SCIP_CALL( SCIPnewProbingNode(scip) );
305  	               node = SCIPgetCurrentNode(scip);
306  	               assert(node != NULL);
307  	
308  	               SCIP_CALL( SCIPaddConsNode(scip, node, probingconsdown, NULL) );
309  	               SCIP_CALL( SCIPreleaseCons(scip, &probingconsdown) );
310  	
311  	#ifdef PRINTNODECONS
312  	               SCIPdebugMsg(scip, " created down probing node with constraint:\n");
313  	               SCIP_CALL( SCIPprintCons(scip, probingconsdown, NULL) );
314  	               SCIPinfoMessage(scip, NULL, "\n");
315  	#endif
316  	
317  	               /* solve the down child probing node */
318  	               SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &downinf) );
319  	               solstatdown = SCIPgetLPSolstat(scip);
320  	               lperror = lperror || (solstatdown == SCIP_LPSOLSTAT_NOTSOLVED && downinf == 0) || (solstatdown == SCIP_LPSOLSTAT_ITERLIMIT) ||
321  	                  (solstatdown == SCIP_LPSOLSTAT_TIMELIMIT);
322  	               assert(solstatdown != SCIP_LPSOLSTAT_UNBOUNDEDRAY);
323  	
324  	               /* break the branching rule if an error occurred, problem was not solved, iteration or time limit was reached */
325  	               if( lperror )
326  	               {
327  	                  SCIPdebugMsg(scip, "error solving down node probing LP: status=%d\n", solstatdown);
328  	                  SCIPstatistic(branchruledata->noupdate = TRUE);
329  	                  break;
330  	               }
331  	
332  	               downobjval = SCIPgetLPObjval(scip);
333  	               downinf = downinf || SCIPisGE(scip, downobjval, SCIPgetCutoffbound(scip));
334  	               assert(((solstatdown != SCIP_LPSOLSTAT_INFEASIBLE) && (solstatdown != SCIP_LPSOLSTAT_OBJLIMIT)) || downinf);
335  	
336  	               if( !downinf )
337  	               {
338  	                  /* when an optimal solution has been found calculate down child's estimate based on pseudo costs */
339  	                  /* estimate = lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) */
340  	                  estimateprobdown = SCIPnodeGetLowerbound(node);
341  	                  SCIP_CALL( SCIPgetLPBranchCands(scip, &downvars, &downvarssols, NULL, &ndownvars, NULL, NULL) );
342  	
343  	                  for( j = 0 ; j < ndownvars; j++ )
344  	                  {
345  	                     SCIP_Real estimateincr;
346  	                     SCIP_Real pscdown;
347  	                     SCIP_Real pscup;
348  	
349  	                     assert(downvars != NULL);
350  	                     assert(downvars[j] != NULL);
351  	
352  	                     pscdown = SCIPvarGetPseudocost(downvars[j], scip->stat, SCIPsetFeasFloor(scip->set, downvarssols[j]) - downvarssols[j]);
353  	                     pscup = SCIPvarGetPseudocost(downvars[j], scip->stat, SCIPsetFeasCeil(scip->set, downvarssols[j]) - downvarssols[j]);
354  	                     estimateincr = MIN(pscdown, pscup);
355  	
356  	                     estimateprobdown += estimateincr;
357  	                  }
358  	               }
359  	               SCIP_CALL( SCIPbacktrackProbing(scip, 0) );
360  	
361  	               /* create the multi-aggregated rounded up constraint */
362  	               SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsup, "probingconsup", SCIPvarGetMultaggrNVars(fixvars[i]), SCIPvarGetMultaggrVars(fixvars[i]),
363  	                     SCIPvarGetMultaggrScalars(fixvars[i]),  SCIPfeasCeil(scip, fixvarssol) -  SCIPvarGetMultaggrConstant(fixvars[i]), SCIPinfinity(scip),
364  	                     TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
365  	               assert(probingconsup != NULL);
366  	
367  	               /* create the up child probing node */
368  	               SCIP_CALL( SCIPnewProbingNode(scip) );
369  	               node = SCIPgetCurrentNode(scip);
370  	
371  	               SCIP_CALL( SCIPaddConsNode(scip, node, probingconsup, NULL) );
372  	               SCIP_CALL( SCIPreleaseCons(scip, &probingconsup) );
373  	
374  	#ifdef PRINTNODECONS
375  	               SCIPdebugMsg(scip, " created up probing node with constraint:\n");
376  	               SCIP_CALL( SCIPprintCons(scip, probingconsup, NULL) );
377  	               SCIPinfoMessage(scip, NULL, "\n");
378  	#endif
379  	               /* solve the up child probing node */
380  	               SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &upinf) );
381  	               solstatup = SCIPgetLPSolstat(scip);
382  	               lperror = lperror ||  (solstatup == SCIP_LPSOLSTAT_NOTSOLVED && upinf == 0) || (solstatup == SCIP_LPSOLSTAT_ITERLIMIT) ||
383  	                  (solstatup == SCIP_LPSOLSTAT_TIMELIMIT);
384  	               assert(solstatup != SCIP_LPSOLSTAT_UNBOUNDEDRAY);
385  	
386  	               /* break the branching rule if an error occurred, problem was not solved, iteration or time limit was reached */
387  	               if( lperror )
388  	               {
389  	                  SCIPdebugMsg(scip, "error solving up node probing LP: status=%d\n", solstatup);
390  	                  SCIPstatistic(branchruledata->noupdate = TRUE);
391  	                  break;
392  	               }
393  	
394  	               upobjval = SCIPgetLPObjval(scip);
395  	               upinf = upinf || SCIPisGE(scip, upobjval, SCIPgetCutoffbound(scip));
396  	               assert(((solstatup != SCIP_LPSOLSTAT_INFEASIBLE) && (solstatup != SCIP_LPSOLSTAT_OBJLIMIT)) || upinf);
397  	
398  	               SCIPdebugMsg(scip, " down node objval: %g up node objval: %g\n", downobjval, upobjval);
399  	
400  	               if( !upinf )
401  	               {
402  	                  /* when an optimal solution has been found  calculate up child's estimate based on pseudo costs */
403  	                  /* estimate = lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) */
404  	                  estimateprobup = SCIPnodeGetLowerbound(node);
405  	                  SCIP_CALL( SCIPgetLPBranchCands(scip, &upvars, &upvarssols, NULL, &nupvars, NULL, NULL) );
406  	
407  	                  for( k = 0 ; k < nupvars; k++ )
408  	                  {
409  	                     SCIP_Real estimateincr;
410  	                     SCIP_Real pscdown;
411  	                     SCIP_Real pscup;
412  	
413  	                     assert(upvars != NULL);
414  	                     assert(upvars[k] != NULL);
415  	
416  	                     pscdown = SCIPvarGetPseudocost(upvars[k], scip->stat, SCIPsetFeasFloor(scip->set, upvarssols[k]) - upvarssols[k]);
417  	                     pscup = SCIPvarGetPseudocost(upvars[k], scip->stat, SCIPsetFeasCeil(scip->set, upvarssols[k]) - upvarssols[k]);
418  	                     estimateincr = MIN(pscdown, pscup);
419  	                     estimateprobup += estimateincr;
420  	                  }
421  	               }
422  	               SCIP_CALL( SCIPbacktrackProbing(scip, 0) );
423  	
424  	               /* check whether the children nodes are solved to optimality and give a valid new lower bound or not */
425  	               if( downinf || upinf )
426  	               {
427  	                  /* check if the LP is a valid relaxation and we can then collect new information */
428  	                  if( allcolsinlp )
429  	                  {
430  	                     /* cut off the node either when both children are infeasible or the objective limit was reached;
431  	                      * if only one child is feasible with LP value smaller than objective limit, add the corresponding
432  	                      * constraint to the problem and break the branching rule in order to solve the updated LP
433  	                      */
434  	                     if( downinf && upinf )
435  	                     {
436  	                        SCIPdebugMsg(scip, "node can be cut off due to strong branching on multi-aggregated variable <%s>\n",
437  	                           SCIPvarGetName(fixvars[i]));
438  	                        SCIPstatistic(branchruledata->nmultaggrcutoff += 1);
439  	
440  	                        *result = SCIP_CUTOFF;
441  	                        break;
442  	                     }
443  	                     else
444  	                     {
445  	                        assert(!lperror);
446  	
447  	                        if( downinf )
448  	                           downnodeinf = TRUE;
449  	
450  	                        SCIPdebugMsg(scip, "%s child of multi-aggregated variable <%s> is infeasible\n",
451  	                           downinf ? "down" : "up", SCIPvarGetName(fixvars[i]) );
452  	                        SCIPstatistic(branchruledata->nmultaggrconsadd += 1);
453  	
454  	                        *result = SCIP_CONSADDED;
455  	                        break;
456  	                     }
457  	                  }
458  	               }
459  	               else
460  	               {
461  	                  /* if both children are solved to optimality and they both give a new valid bound, calculate the score of the
462  	                   * multi-aggregated variable
463  	                   */
464  	                  SCIP_Real downgain;
465  	                  SCIP_Real upgain;
466  	                  SCIP_Real down;
467  	                  SCIP_Real up;
468  	                  SCIP_Real score;
469  	                  SCIP_Real minbound;
470  	
471  	                  assert(!downinf);
472  	                  assert(!upinf);
473  	                  assert(!lperror);
474  	
475  	                  SCIPdebugMsg(scip, " both probing nodes are valid while branching on multi-aggregated variable: <%s>\n ", SCIPvarGetName(fixvars[i]));
476  	
477  	                  down = MAX(downobjval, lpobjval);
478  	                  up = MAX(upobjval, lpobjval);
479  	                  downgain = down - lpobjval;
480  	                  upgain = up - lpobjval;
481  	                  score = SCIPgetBranchScore(scip, NULL, downgain, upgain);
482  	
483  	                  if( allcolsinlp && !exactsolve )
484  	                  {
485  	                     /* the minimal lower bound of both children is a proved lower bound of the current subtree */
486  	                     minbound = MIN(downobjval, upobjval);
487  	                     *provedbound = MAX(*provedbound, minbound);
488  	                  }
489  	
490  	                  SCIPstatistic(
491  	                     if( score > *bestmultaggrscore )
492  	                        *bestmultaggrscore = score;
493  	                     );
494  	
495  	                  /* update the best branching candidate and all its values if a strictly greater score has been found */
496  	                  if( score > *bestscore )
497  	                  {
498  	                     SCIPstatistic(
499  	                        if( branchruledata->nmultaggrbranch == 0 )
500  	                        {
501  	                           branchruledata->rundepth = SCIPgetNRuns(scip);
502  	                           branchruledata->firstmultaggrdepth = SCIPgetFocusDepth(scip);
503  	                        }
504  	                        )
505  	
506  	                     SCIPdebugMsg(scip, " <%s> is a better candidate for branching\n", SCIPvarGetName(fixvars[i]));
507  	
508  	                     *bestscore = MAX(score, *bestscore);
509  	                     *bestcand = fixvars[i];
510  	                     *bestsol = fixvarssol;
511  	                     *bestdown = downobjval;
512  	                     *bestup = upobjval;
513  	                     *bestdownvalid = TRUE;
514  	                     *bestupvalid = TRUE;
515  	                     *estimatedown = estimateprobdown;
516  	                     *estimateup = estimateprobup;
517  	                  }
518  	                  assert(bestscore != NULL);
519  	                  assert(bestcand != NULL);
520  	                  assert(bestup != NULL);
521  	                  assert(bestdown != NULL);
522  	               }
523  	            }
524  	         }
525  	      }
526  	
527  	      /* end probing mode */
528  	      if( endprobing )
529  	      {
530  	         SCIP_CALL( SCIPendProbing(scip) );
531  	      }
532  	
533  	      SCIPdebugMsg(scip, "\n");
534  	
535  	      /* one of the child nodes was infeasible, add the other constraint to the current node */
536  	      if( *result == SCIP_CONSADDED )
537  	      {
538  	         node = SCIPgetCurrentNode(scip);
539  	         if( downnodeinf )
540  	         {
541  	            SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsup, "infconsup", SCIPvarGetMultaggrNVars(fixvars[i]),
542  	                  SCIPvarGetMultaggrVars(fixvars[i]), SCIPvarGetMultaggrScalars(fixvars[i]),
543  	                  SCIPfeasCeil(scip, fixvarssols[i]) - SCIPvarGetMultaggrConstant(fixvars[i]), SCIPinfinity(scip),
544  	                  TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
545  	            assert(probingconsup != NULL);
546  	            SCIP_CALL( SCIPaddConsNode(scip, node, probingconsup, NULL) );
547  	            SCIPdebugMsg(scip, " <%s> new valid constraint has been added to the original problem\n", SCIPconsGetName(probingconsup));
548  	            SCIP_CALL( SCIPreleaseCons(scip, &probingconsup) );
549  	         }
550  	         else
551  	         {
552  	            SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsdown, "infconsdown", SCIPvarGetMultaggrNVars(fixvars[i]),
553  	                  SCIPvarGetMultaggrVars(fixvars[i]), SCIPvarGetMultaggrScalars(fixvars[i]), - SCIPinfinity(scip),
554  	                  SCIPfeasFloor(scip, fixvarssols[i]) - SCIPvarGetMultaggrConstant(fixvars[i]), TRUE, TRUE, FALSE, FALSE,
555  	                  TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
556  	            assert(probingconsdown != NULL);
557  	            SCIP_CALL( SCIPaddConsNode(scip, node, probingconsdown, NULL) );
558  	            SCIPdebugMsg(scip, " <%s> new valid constraint has been added to the original problem\n", SCIPconsGetName(probingconsdown));
559  	            SCIP_CALL( SCIPreleaseCons(scip, &probingconsdown) );
560  	         }
561  	      }
562  	      SCIPfreeBufferArray(scip, &fixvarssols);
563  	   }
564  	   return SCIP_OKAY;
565  	}
566  	
567  	
568  	/*
569  	 * Callback methods of branching rule
570  	 */
571  	
572  	/** copy method for branchrule plugins (called when SCIP copies plugins) */
573  	static
574  	SCIP_DECL_BRANCHCOPY(branchCopyMultAggr)
575  	{  /*lint --e{715}*/
576  	   assert(scip != NULL);
577  	   assert(branchrule != NULL);
578  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
579  	
580  	   /* call inclusion method of branchrule */
581  	   SCIP_CALL( SCIPincludeBranchruleMultAggr(scip) ) ;
582  	
583  	   return SCIP_OKAY;
584  	}
585  	
586  	/** destructor of branching rule to free user data (called when SCIP is exiting) */
587  	static
588  	SCIP_DECL_BRANCHFREE(branchFreeMultAggr)
589  	{  /*lint --e{715}*/
590  	   SCIP_BRANCHRULEDATA* branchruledata;
591  	
592  	   /* free branching rule data */
593  	   branchruledata = SCIPbranchruleGetData(branchrule);
594  	   assert(branchruledata != NULL);
595  	
596  	   SCIPstatistic(SCIPfreeBlockMemoryArrayNull(scip , &branchruledata->ratioggain, branchruledata->size));
597  	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize);
598  	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize);
599  	
600  	   SCIPfreeBlockMemory(scip, &branchruledata);
601  	   SCIPbranchruleSetData(branchrule, NULL);
602  	
603  	   return SCIP_OKAY;
604  	}
605  	
606  	/** initialization method of branching rule (called after problem was transformed) */
607  	static
608  	SCIP_DECL_BRANCHINIT(branchInitMultAggr)
609  	{  /*lint --e{715}*/
610  	   SCIP_BRANCHRULEDATA* branchruledata;
611  	
612  	   branchruledata = SCIPbranchruleGetData(branchrule);
613  	   assert(branchruledata != NULL);
614  	
615  	   branchruledata->lastcand = 0;
616  	   SCIPstatistic(
617  	      branchruledata->firstmultaggrdepth = 0;
618  	      branchruledata->nmultaggrbranch = 0;
619  	      branchruledata->nfracbranch = 0;
620  	      branchruledata->nEscore = 0;
621  	      branchruledata->nmultaggrcutoff = 0;
622  	      branchruledata->nmultaggrconsadd = 0;
623  	      branchruledata->nfractcutoff = 0;
624  	      branchruledata->nfractconsadd = 0;
625  	      branchruledata->nrun = 0;
626  	      branchruledata->size = 100;
627  	      branchruledata->ameanratio = 0.0;
628  	      branchruledata->noupdate = FALSE;
629  	      branchruledata->clckstrongbr = NULL;
630  	      branchruledata->clckmultaggrbr = NULL;
631  	      branchruledata->nstrongbrcall = 0;
632  	      branchruledata->nmultaggrbrcall = 0;
633  	      branchruledata->totalmultaggrcands = 0;
634  	      branchruledata->totallpcands = 0;
635  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->ratioggain, branchruledata->size) );
636  	      BMSclearMemoryArray(branchruledata->ratioggain, branchruledata->size);
637  	      SCIP_CALL( SCIPcreateClock(scip, &branchruledata->clckstrongbr) );
638  	      SCIP_CALL( SCIPcreateClock(scip, &branchruledata->clckmultaggrbr) );
639  	   )
640  	   return SCIP_OKAY;
641  	}
642  	
643  	/** deinitialization method of branching rule (called before transformed problem is freed) */
644  	static
645  	SCIP_DECL_BRANCHEXIT(branchExitMultAggr)
646  	{  /*lint --e{715}*/
647  	   SCIP_BRANCHRULEDATA* branchruledata;
648  	   SCIPstatistic(int j = 0);
649  	
650  	   /* initialize branching rule data */
651  	   branchruledata = SCIPbranchruleGetData(branchrule);
652  	   assert(branchruledata != NULL);
653  	   assert((branchruledata->skipdown != NULL) == (branchruledata->skipup != NULL));
654  	
655  	   /* print statistics */
656  	   SCIPstatistic(
657  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n");
658  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Multi-aggregated branching stats          : \n");
659  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  nmultaggrvars                           :  %d    (last run)\n",
660  	         branchruledata->nmultaggrvars);
661  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  firstmultaggrbranchdepth                :  %d    (in run %d)\n",
662  	         branchruledata->firstmultaggrdepth,
663  	         branchruledata->rundepth);
664  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  nmultaggrbranch                         :  %d    (tot %d)\n",
665  	         branchruledata->nmultaggrbranch, branchruledata->nmultaggrbranch +  branchruledata->nfracbranch);
666  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  nmultaggrcutoff                         :  %d\n", branchruledata->nmultaggrcutoff);
667  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  nmultaggrconsadd                        :  %d\n", branchruledata->nmultaggrconsadd);
668  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  nfractcutoff                            :  %d\n", branchruledata->nfractcutoff);
669  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  nfractconsadd                           :  %d\n", branchruledata->nfractconsadd);
670  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  nEscore                                 :  %d\n", branchruledata->nEscore);
671  	
672  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  Branching Time                          :    \n");
673  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  nstrongbrcall                           :  %d\n", branchruledata->nstrongbrcall);
674  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  totalstrongbrtime                       :  %g\n",
675  	         SCIPgetClockTime(scip, branchruledata->clckstrongbr));
676  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  totallpcands                            :  %d\n", branchruledata->totallpcands);
677  	
678  	      if( branchruledata->totallpcands != 0 )
679  	      {
680  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  averagetimestrongbr                     :  %g\n",
681  	         SCIPgetClockTime(scip, branchruledata->clckstrongbr) / branchruledata->totallpcands);
682  	      }
683  	      else
684  	      {
685  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  averagetimestrongbr                     :  %s\n", "--");
686  	      }
687  	
688  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  nmultaggrbrcall                         :  %d\n", branchruledata->nmultaggrbrcall);
689  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  totalmultaggrbrtime                     :  %g\n",
690  	         SCIPgetClockTime(scip, branchruledata->clckmultaggrbr));
691  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  totalmultaggrcands                      :  %d\n", branchruledata->totalmultaggrcands);
692  	
693  	     if( branchruledata->totalmultaggrcands != 0 )
694  	      {
695  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  averagetimemultaggrbr                   :  %g\n",
696  	         SCIPgetClockTime(scip, branchruledata->clckmultaggrbr) / branchruledata->totalmultaggrcands);
697  	      }
698  	      else
699  	      {
700  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  averagetimemultaggrbr                   :  %s\n", "--");
701  	      }
702  	
703  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  Ratioggain                              :\n");
704  	      if( branchruledata->nmultaggrbranch != 0 )
705  	      {
706  	         for( j = 0; j < branchruledata->nmultaggrbranch; j++ )
707  	         {
708  	            branchruledata->ameanratio += branchruledata->ratioggain[j];
709  	            SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  %g", branchruledata->ratioggain[j]);
710  	         }
711  	
712  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n");
713  	         branchruledata->ameanratio = branchruledata->ameanratio / branchruledata->nmultaggrbranch;
714  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n");
715  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  ameanratio                              :  %4.2f\n", branchruledata->ameanratio);
716  	      }
717  	      else
718  	      {
719  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "  ameanratio                              :  %s\n", "--");
720  	      }
721  	
722  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n");
723  	
724  	      /* free arrays */
725  	      SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->ratioggain, branchruledata->size);
726  	      SCIP_CALL( SCIPfreeClock(scip, &branchruledata->clckstrongbr) );
727  	      SCIP_CALL( SCIPfreeClock(scip, &branchruledata->clckmultaggrbr) );
728  	   )
729  	   if( branchruledata->skipdown != NULL )
730  	   {
731  	      SCIPfreeBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize);
732  	      SCIPfreeBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize);
733  	      branchruledata->skipdown = NULL;
734  	      branchruledata->skipup = NULL;
735  	      branchruledata->skipsize = 0;
736  	   }
737  	   return SCIP_OKAY;
738  	}
739  	
740  	/** branching execution method for fractional LP solutions */
741  	static
742  	SCIP_DECL_BRANCHEXECLP(branchExeclpMultAggr)
743  	{  /*lint --e{715}*/
744  	   SCIP_BRANCHRULEDATA* branchruledata;
745  	   SCIP_VAR** lpcands;
746  	   SCIP_VAR** tmplpcands;
747  	   SCIP_Real* lpcandssol;
748  	   SCIP_Real* lpcandsfrac;
749  	   SCIP_Real* tmplpcandssol;
750  	   SCIP_Real* tmplpcandsfrac;
751  	   SCIP_NODE* downchild;
752  	   SCIP_NODE* upchild;
753  	   SCIP_Real bestup;
754  	   SCIP_Real bestdown;
755  	   SCIP_Real bestscore;
756  	   SCIP_Real provedbound;
757  	   SCIP_Real estimatedown = 0.0;
758  	   SCIP_Real estimateup = 0.0;
759  	   SCIP_Bool bestdownvalid;
760  	   SCIP_Bool bestupvalid;
761  	   SCIP_Longint oldreevalage;
762  	   int bestcandpos;
763  	   int nlpcands;
764  	   int npriolpcands;
765  	   SCIPstatistic(
766  	      SCIP_Real lpobjval;
767  	      SCIP_Bool reoptimize;
768  	   )
769  	
770  	   assert(branchrule != NULL);
771  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
772  	   assert(scip != NULL);
773  	   assert(result != NULL);
774  	
775  	   SCIPdebugMsg(scip, "Execlp method of mult-aggreg branching\n ");
776  	   *result = SCIP_DIDNOTRUN;
777  	
778  	   /* get branching rule data */
779  	   branchruledata = SCIPbranchruleGetData(branchrule);
780  	   assert(branchruledata != NULL);
781  	
782  	   SCIP_CALL( SCIPgetLongintParam(scip, "branching/fullstrong/reevalage", &oldreevalage) );
783  	   SCIP_CALL( SCIPsetLongintParam(scip, "branching/fullstrong/reevalage", branchruledata->reevalage) );
784  	
785  	   /* get the lpobjval and the number of multi aggregated variables of the problem as a statistic counter */
786  	   SCIPstatistic(
787  	      reoptimize = FALSE;
788  	      lpobjval = SCIPgetLPObjval(scip);
789  	
790  	      if( SCIPgetNRuns(scip) != branchruledata->nrun )
791  	      {
792  	         SCIP_VAR** fixvars;
793  	         int nfixvars;
794  	         int i;
795  	
796  	         branchruledata->nmultaggrvars = 0;
797  	         fixvars = SCIPgetFixedVars(scip);
798  	         nfixvars = SCIPgetNFixedVars(scip);
799  	
800  	         if( nfixvars != 0 )
801  	         {
802  	            for( i = 0; i < nfixvars; i++ )
803  	            {
804  	               if( SCIPvarGetStatus(fixvars[i]) == SCIP_VARSTATUS_MULTAGGR && (SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_INTEGER ||
805  	                     SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_BINARY) )
806  	               {
807  	                  branchruledata->nmultaggrvars += 1;
808  	               }
809  	            }
810  	         }
811  	         branchruledata->nrun = SCIPgetNRuns(scip);
812  	      }
813  	   )
814  	
815  	   /* get all branching candidates */
816  	   SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, &nlpcands, &npriolpcands, NULL) );
817  	   assert(nlpcands > 0);
818  	   assert(npriolpcands > 0);
819  	
820  	   /* copy LP branching candidates and solution values, because they will be updated w.r.t. the strong branching LP
821  	    * solution
822  	    */
823  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) );
824  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) );
825  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) );
826  	
827  	   if( branchruledata->skipdown == NULL )
828  	   {
829  	      assert(branchruledata->skipup == NULL);
830  	
831  	      branchruledata->skipsize = SCIPgetNVars(scip);
832  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
833  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
834  	      BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
835  	      BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
836  	   }
837  	
838  	   /* start the clock to get the time spent inside the function */
839  	   SCIPstatistic(
840  	      SCIP_CALL( SCIPstartClock(scip, branchruledata->clckstrongbr) );
841  	      );
842  	
843  	   /* compute strong branching among the array of fractional variables in order to get the best one */
844  	   SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcands, lpcandssol, lpcandsfrac, branchruledata->skipdown,
845  	         branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand,
846  	         branchruledata->maxproprounds, branchruledata->probingbounds, TRUE,
847  	         &bestcandpos, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
848  	
849  	   SCIPstatistic(
850  	      SCIP_CALL( SCIPstopClock(scip, branchruledata->clckstrongbr) );
851  	      branchruledata->totallpcands += SCIPgetNLPBranchCands(scip);
852  	      branchruledata->nstrongbrcall += 1;
853  	      )
854  	
855  	   if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
856  	   {
857  	      SCIP_VAR* bestcand = lpcands[bestcandpos];
858  	      SCIP_Real bestsol = lpcandssol[bestcandpos];
859  	      SCIPstatistic( SCIP_Real bestmultaggrscore = -SCIPinfinity(scip); )
860  	
861  	      SCIPstatistic(
862  	         SCIP_Real fdowngain = 0.0;
863  	         SCIP_Real fupgain = 0.0;
864  	
865  		 /* reoptimize is set to true if strong branching on fractional variables did not explicitly evaluate the objective
866  	          * values of the probing child nodes and thus we do not have updated information
867  	          */
868  	         if( SCIPisLT(scip, SCIPgetVarStrongbranchLPAge(scip, bestcand), branchruledata->reevalage)
869  	            || branchruledata->maxproprounds != 0 )
870  	            reoptimize = TRUE;
871  	
872  	         /* store values needed for the ratioggain statistic */
873  	         if( !reoptimize )
874  	         {
875  	            SCIP_Real fdown;
876  	            SCIP_Real fup;
877  	
878  	            fdown = MAX(bestdown, lpobjval);
879  	            fup = MAX(bestup, lpobjval);
880  	            fdowngain = fdown - lpobjval;
881  	            fupgain = fup - lpobjval;
882  	         }
883  	
884  	         /* start and then stop the clock to get the time spent inside the function */
885  	         SCIP_CALL( SCIPstartClock(scip, branchruledata->clckmultaggrbr) );
886  	      )
887  	
888  	      /* compute strong branching among the multi-aggregated variables and the best fractional variable */
889  	#ifdef SCIP_STATISTIC
890  	      SCIP_CALL( selectVarMultAggrBranching(scip, &bestcand, &bestscore, &bestsol, &bestdown, &bestup, &bestdownvalid, &bestupvalid, &provedbound,
891  	            &estimatedown, &estimateup, &bestmultaggrscore, result) );
892  	#else
893  	      SCIP_CALL( selectVarMultAggrBranching(scip, &bestcand, &bestscore, &bestsol, &bestdown, &bestup, &bestdownvalid, &bestupvalid, &provedbound,
894  	            &estimatedown, &estimateup, result) );
895  	#endif
896  	      SCIPstatistic(
897  	         SCIP_CALL( SCIPstopClock(scip, branchruledata->clckmultaggrbr) );
898  	         branchruledata->nmultaggrbrcall += 1;
899  	      )
900  	
901  	      if( *result != SCIP_CUTOFF && *result != SCIP_CONSADDED )
902  	      {
903  	         SCIPstatistic(
904  	            if( !(branchruledata->noupdate) )
905  	            {
906  	               if( SCIPisEQ(scip, bestmultaggrscore, bestscore) )
907  	                  branchruledata->nEscore += 1;
908  	            }
909  	            )
910  	
911  	         assert(bestcand != NULL);
912  	         SCIPdebugMsg(scip, "BRANCHING MODE:\n");
913  	
914  	         /* perform branching on the best found candidate */
915  	         if( SCIPvarGetStatus(bestcand) == SCIP_VARSTATUS_MULTAGGR )
916  	         {
917  	            SCIP_CONS* multaggrconsdown;
918  	            SCIP_CONS* multaggrconsup;
919  	
920  	            SCIPstatistic(
921  	               if( !(branchruledata->noupdate) )
922  	               {
923  	                  branchruledata->nmultaggrbranch += 1;
924  	
925  	                  if( !reoptimize )
926  	                  {
927  	                     SCIP_Real gfractbranch;
928  	                     SCIP_Real gmultaggrbranch;
929  	                     SCIP_Real downgain;
930  	                     SCIP_Real upgain;
931  	                     SCIP_Real down;
932  	                     SCIP_Real up;
933  	                     int nmultaggrbranch;
934  	
935  	                     down = MAX(bestdown, lpobjval);
936  	                     up = MAX(bestup, lpobjval);
937  	                     downgain = down - lpobjval;
938  	                     upgain = up - lpobjval;
939  	
940  	                     SCIP_CALL( ensureArraySize(scip, branchruledata) );
941  	
942  	                     gfractbranch= SQRT(MAX(fdowngain,1e-06) * MAX(fupgain,1e-06));
943  	                     gmultaggrbranch = SQRT(MAX(downgain,1e-06) * MAX(upgain,1e-06));
944  	
945  	                     nmultaggrbranch = branchruledata->nmultaggrbranch;
946  	
947  	                     if( gmultaggrbranch == 0.0 )
948  	                     {
949  	                        branchruledata->ratioggain[nmultaggrbranch - 1] = 1;
950  	                     }
951  	                     else
952  	                     {
953  	                        branchruledata->ratioggain[nmultaggrbranch - 1] = gfractbranch / gmultaggrbranch;
954  	                     }
955  	                  }
956  	               }
957  	               )
958  	
959  	            /* create the multi-aggregated constraints rounded up and down */
960  	            SCIP_CALL( SCIPcreateConsLinear(scip, &multaggrconsdown, "consdown", SCIPvarGetMultaggrNVars(bestcand),
961  	                  SCIPvarGetMultaggrVars(bestcand), SCIPvarGetMultaggrScalars(bestcand), - SCIPinfinity(scip),
962  	                  SCIPfeasFloor(scip, bestsol) - SCIPvarGetMultaggrConstant(bestcand),
963  	                  TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
964  	
965  	            SCIP_CALL( SCIPcreateConsLinear(scip, &multaggrconsup, "consup", SCIPvarGetMultaggrNVars(bestcand),
966  	                  SCIPvarGetMultaggrVars(bestcand), SCIPvarGetMultaggrScalars(bestcand),
967  	                  SCIPfeasCeil(scip, bestsol) -  SCIPvarGetMultaggrConstant(bestcand), SCIPinfinity(scip),
968  	                  TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
969  	
970  	            /* create the child nodes */
971  	            SCIP_CALL( SCIPcreateChild(scip, &downchild, 1.0, estimatedown) );
972  	            SCIPdebugMsg(scip, " down node: lowerbound %f estimate %f\n", SCIPnodeGetLowerbound(downchild), SCIPnodeGetEstimate(downchild));
973  	
974  	            SCIP_CALL( SCIPcreateChild(scip, &upchild, 1.0, estimateup) );
975  	            SCIPdebugMsg(scip, " up node: lowerbound %f estimate %f\n", SCIPnodeGetLowerbound(upchild), SCIPnodeGetEstimate(upchild));
976  	
977  	            assert(downchild != NULL);
978  	            assert(upchild != NULL);
979  	
980  	            SCIP_CALL( SCIPaddConsNode(scip, downchild, multaggrconsdown, NULL) );
981  	            SCIP_CALL( SCIPaddConsNode(scip, upchild, multaggrconsup, NULL) );
982  	
983  	#ifdef PRINTNODECONS
984  	            SCIPdebugMsg(scip, "branching at node %lld\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
985  	
986  	            SCIPdebugMsg(scip, "created child node %lld with constraint:\n", SCIPnodeGetNumber(downchild));
987  	            SCIP_CALL( SCIPprintCons(scip, multaggrconsdown, NULL) );
988  	            SCIPinfoMessage(scip, NULL, "\n");
989  	
990  	            SCIPdebugMsg(scip, "created child node %lld with constraint:\n", SCIPnodeGetNumber(upchild));
991  	            SCIP_CALL( SCIPprintCons(scip, multaggrconsup, NULL) );
992  	            SCIPinfoMessage(scip, NULL, "\n");
993  	#endif
994  	
995  	            /* relase constraints */
996  	            SCIP_CALL( SCIPreleaseCons(scip, &multaggrconsdown) );
997  	            SCIP_CALL( SCIPreleaseCons(scip, &multaggrconsup) );
998  	
999  	            SCIPdebugMsg(scip, "BRANCHED on multi-aggregated variable <%s>\n", SCIPvarGetName(bestcand));
1000 	
1001 	            *result = SCIP_BRANCHED;
1002 	         }
1003 	         else
1004 	         {
1005 	            SCIPstatistic(
1006 	               if( !(branchruledata->noupdate) )
1007 	                  branchruledata->nfracbranch += 1
1008 	             );
1009 	
1010 	            assert(*result == SCIP_DIDNOTRUN);
1011 	            assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1012 	
1013 	            SCIP_CALL( SCIPbranchVarVal(scip, bestcand, bestsol, &downchild, NULL, &upchild) );
1014 	
1015 	            assert(downchild != NULL);
1016 	            assert(upchild != NULL);
1017 	
1018 	            SCIPdebugMsg(scip, "BRANCHED on fractional variable <%s>\n", SCIPvarGetName(bestcand));
1019 	
1020 	            *result = SCIP_BRANCHED;
1021 	         }
1022 	
1023 	         /* update the lower bounds in the children; we must not do this if columns are missing in the LP
1024 	          * (e.g., because we are doing branch-and-price) or the problem should be solved exactly
1025 	          */
1026 	         if( SCIPallColsInLP(scip) && !SCIPisExactSolve(scip) )
1027 	         {
1028 	            SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
1029 	            SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
1030 	         }
1031 	         SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
1032 	         SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
1033 	      }
1034 	   }
1035 	   else
1036 	   {
1037 	      SCIPdebugMsg(scip, "strong branching breaks\n" );
1038 	
1039 	      SCIPstatistic(
1040 	         if( *result == SCIP_CUTOFF )
1041 	         {
1042 	            branchruledata->nfractcutoff += 1;
1043 	         }
1044 	         else
1045 	         {
1046 	            branchruledata->nfractconsadd += 1;
1047 	         }
1048 	      )
1049 	   }
1050 	
1051 	   SCIPfreeBufferArray(scip, &lpcandsfrac);
1052 	   SCIPfreeBufferArray(scip, &lpcandssol);
1053 	   SCIPfreeBufferArray(scip, &lpcands);
1054 	
1055 	   SCIP_CALL( SCIPsetLongintParam(scip, "branching/fullstrong/reevalage", oldreevalage) );
1056 	
1057 	   return SCIP_OKAY;
1058 	}
1059 	
1060 	/*
1061 	 * branching rule specific interface methods
1062 	 */
1063 	
1064 	/** creates the multi-aggregated branching rule and includes it in SCIP */
1065 	SCIP_RETCODE SCIPincludeBranchruleMultAggr(
1066 	   SCIP*                 scip                /**< SCIP data structure */
1067 	   )
1068 	{
1069 	   SCIP_BRANCHRULEDATA* branchruledata;
1070 	   SCIP_BRANCHRULE* branchrule;
1071 	
1072 	   /* create multaggr branching rule data */
1073 	   SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
1074 	   branchruledata->lastcand = 0;
1075 	   branchruledata->skipsize = 0;
1076 	   branchruledata->skipup = NULL;
1077 	   branchruledata->skipdown = NULL;
1078 	   SCIPstatistic(branchruledata->ratioggain = NULL);
1079 	
1080 	   /* include branching rule */
1081 	   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
1082 	         BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1083 	
1084 	   assert(branchrule != NULL);
1085 	
1086 	   /* set non fundamental callbacks via setter functions */
1087 	   SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyMultAggr) );
1088 	   SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeMultAggr) );
1089 	   SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitMultAggr) );
1090 	   SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitMultAggr) );
1091 	   SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpMultAggr) );
1092 	
1093 	   /* multi-aggregated branching rule parameters */
1094 	   SCIP_CALL( SCIPaddLongintParam(scip,
1095 	         "branching/multaggr/reevalage",
1096 	         "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node",
1097 	         &branchruledata->reevalage, TRUE, DEFAULT_REEVALAGE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1098 	   SCIP_CALL( SCIPaddIntParam(scip,
1099 	         "branching/multaggr/maxproprounds",
1100 	         "maximum number of propagation rounds to be performed during multaggr branching before solving the LP (-1: no limit, -2: parameter settings)",
1101 	         &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
1102 	   SCIP_CALL( SCIPaddBoolParam(scip,
1103 	         "branching/multaggr/probingbounds",
1104 	         "should valid bounds be identified in a probing-like fashion during multaggr branching (only with propagation)?",
1105 	         &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
1106 	
1107 	   return SCIP_OKAY;
1108 	}
1109