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_cloud.c
26   	 * @ingroup DEFPLUGINS_BRANCH
27   	 * @brief  cloud branching rule
28   	 * @author Timo Berthold
29   	 * @author Domenico Salvagnin
30   	 *
31   	 * Branching rule based on muliple optimal solutions to the current LP relaxation. See@n
32   	 * Cloud Branching@n
33   	 * Timo Berthold and Domenico Salvagnin@n
34   	 * Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2013, LNCS 7874@n
35   	 * Preliminary version available as <a href="http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1730">ZIB-Report 13-01</a>.
36   	 */
37   	
38   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39   	
40   	#include "blockmemshell/memory.h"
41   	#include "scip/branch_allfullstrong.h"
42   	#include "scip/branch_cloud.h"
43   	#include "scip/branch_fullstrong.h"
44   	#include "scip/pub_branch.h"
45   	#include "scip/pub_lp.h"
46   	#include "scip/pub_message.h"
47   	#include "scip/pub_tree.h"
48   	#include "scip/pub_var.h"
49   	#include "scip/scip_branch.h"
50   	#include "scip/scip_general.h"
51   	#include "scip/scip_lp.h"
52   	#include "scip/scip_mem.h"
53   	#include "scip/scip_message.h"
54   	#include "scip/scip_numerics.h"
55   	#include "scip/scip_param.h"
56   	#include "scip/scip_prob.h"
57   	#include "scip/scip_sol.h"
58   	#include "scip/scip_solvingstats.h"
59   	#include "scip/scip_timing.h"
60   	#include "scip/scip_tree.h"
61   	#include "scip/scip_var.h"
62   	#include <string.h>
63   	
64   	
65   	#define BRANCHRULE_NAME            "cloud"
66   	#define BRANCHRULE_DESC            "branching rule that considers several alternative LP optima"
67   	#define BRANCHRULE_PRIORITY        0
68   	#define BRANCHRULE_MAXDEPTH        -1
69   	#define BRANCHRULE_MAXBOUNDDIST    1.0
70   	
71   	#define DEFAULT_USECLOUD           TRUE      /**< should a cloud of points be used? */
72   	#define DEFAULT_USEUNION           FALSE     /**< should the union of candidates be used? */
73   	#define DEFAULT_MAXPOINTS          -1        /**< maximum number of points for the cloud (-1 means no limit) */
74   	#define DEFAULT_MINSUCCESSRATE     0.0       /**< minimum success rate for the cloud */
75   	#define DEFAULT_MINSUCCESSUNION    0.0       /**< minimum success rate for the union */
76   	#define DEFAULT_MAXDEPTHUNION      65000     /**< maximum depth for the union */
77   	#define DEFAULT_ONLYF2             FALSE     /**< should only F2 be used? */
78   	
79   	/*
80   	 * Data structures
81   	 */
82   	
83   	/** branching rule data */
84   	struct SCIP_BranchruleData
85   	{
86   	   int                   lastcand;           /**< last evaluated candidate of last branching rule execution */
87   	   SCIP_Bool             usecloud;           /**< should a cloud of points be used? */
88   	   SCIP_Bool             useunion;           /**< should the union of candidates be used? */
89   	   SCIP_Bool             onlyF2;             /**< should only F2 be used? */
90   	   int                   maxpoints;          /**< maximum number of points for the cloud (-1 means no limit) */
91   	   SCIP_Real             minsuccessrate;     /**< minimum success rate for the cloud */
92   	   SCIP_Real             minsuccessunion;    /**< minimum success rate for the union */
93   	   SCIP_CLOCK*           cloudclock;         /**< clock for cloud diving */
94   	   SCIP_Bool*            skipdown;           /**< should down branch be skiped? */
95   	   SCIP_Bool*            skipup;             /**< should up branch be skiped? */
96   	   int                   ntried;             /**< number of times the cloud was tried */
97   	   int                   ntriedunions;       /**< number of times the cloud was tried */
98   	   int                   nuseful;            /**< number of times the cloud was useful (at least one LP skipped) */
99   	   int                   nusefulunions;      /**< number of times the union was useful (took candidate from new list) */
100  	   int                   ncloudpoints;       /**< sum of cloud points taken over all nodes with at least two poitns in cloud */
101  	   int                   nsavedlps;          /**< sum of saved LPs taken over all nodes with at least two points in cloud */
102  	   int                   maxdepthunion;      /**< maximum depth for the union */
103  	   int                   skipsize;           /**< size of skipdown and skipup array */
104  	};
105  	
106  	/*
107  	 * Callback methods of branching rule
108  	 */
109  	
110  	/** destructor of branching rule to free user data (called when SCIP is exiting) */
111  	static
112  	SCIP_DECL_BRANCHFREE(branchFreeCloud)
113  	{  /*lint --e{715}*/
114  	   SCIP_BRANCHRULEDATA* branchruledata;
115  	
116  	   /* free branching rule data */
117  	   branchruledata = SCIPbranchruleGetData(branchrule);
118  	
119  	   if( branchruledata->cloudclock != NULL)
120  	   {
121  	      SCIPstatistic(
122  	         int ntried;
123  	         int nuseful;
124  	         int ncloudpoints;
125  	         int nsavedlps;
126  	
127  	         ntried = branchruledata->ntried;
128  	         nuseful = branchruledata->nuseful;
129  	         ncloudpoints = branchruledata->ncloudpoints;
130  	         nsavedlps = branchruledata->nsavedlps;
131  	
132  	         SCIPstatisticMessage("time spent diving in cloud branching: %g\n", SCIPgetClockTime(scip, branchruledata->cloudclock));
133  	         SCIPstatisticMessage("cloud branching tried: %6d      found cloud: %6d \n", ntried, nuseful);
134  	         SCIPstatisticMessage("cloud used points: %6d      saved LPs: %6d \n", ncloudpoints, nsavedlps);
135  	         SCIPstatisticMessage("cloud success rates useful/tried: %8.6g points/useful: %8.6g  saved/useful: %8.6g \n",
136  	            ntried == 0 ? -1 : (SCIP_Real)nuseful / ntried,  nuseful == 0 ? -1 : (SCIP_Real)ncloudpoints / nuseful, nuseful == 0 ? -1 :  (SCIP_Real)nsavedlps / nuseful);
137  	      )
138  	
139  	      SCIP_CALL( SCIPfreeClock(scip, &(branchruledata->cloudclock)) );
140  	   }
141  	
142  	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize);
143  	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize);
144  	
145  	   SCIPfreeBlockMemory(scip, &branchruledata);
146  	   SCIPbranchruleSetData(branchrule, NULL);
147  	
148  	   return SCIP_OKAY;
149  	}
150  	
151  	
152  	/** initialization method of branching rule (called after problem was transformed) */
153  	static
154  	SCIP_DECL_BRANCHINIT(branchInitCloud)
155  	{  /*lint --e{715}*/
156  	   SCIP_BRANCHRULEDATA* branchruledata;
157  	
158  	   /* initialize branching rule data */
159  	   branchruledata = SCIPbranchruleGetData(branchrule);
160  	   branchruledata->lastcand = 0;
161  	   branchruledata->nuseful = 0;
162  	   branchruledata->nusefulunions = 0;
163  	   branchruledata->ntried = 0;
164  	   branchruledata->ntriedunions = 0;
165  	   branchruledata->ncloudpoints = 0;
166  	   branchruledata->nsavedlps = 0;
167  	
168  	   if( branchruledata->cloudclock != NULL)
169  	   {
170  	      SCIP_CALL( SCIPresetClock(scip, branchruledata->cloudclock) );
171  	   }
172  	
173  	   return SCIP_OKAY;
174  	}
175  	
176  	/** branching execution method for fractional LP solutions */
177  	static
178  	SCIP_DECL_BRANCHEXECLP(branchExeclpCloud)
179  	{  /*lint --e{715}*/
180  	   SCIP_BRANCHRULEDATA* branchruledata;
181  	
182  	   SCIP_VAR** lpcands;
183  	   SCIP_VAR** lpcandscopy;
184  	
185  	   SCIP_VAR** vars;
186  	   SCIP_ROW** lprows;
187  	   SCIP_Real* lpcandsfrac;
188  	   SCIP_Real* lpcandssol;
189  	   SCIP_Real* lpcandsfraccopy;
190  	   SCIP_Real* lpcandssolcopy;
191  	   SCIP_Real* lpcandsmin;
192  	   SCIP_Real* lpcandsmax;
193  	   SCIP_Real* newlpcandsmin;
194  	   SCIP_Real* newlpcandsmax;
195  	
196  	   SCIP_Real bestdown;
197  	   SCIP_Real bestup;
198  	   SCIP_Real bestscore;
199  	   SCIP_Real provedbound;
200  	
201  	   SCIP_Bool bestdownvalid;
202  	   SCIP_Bool bestupvalid;
203  	   SCIP_Bool newpoint;
204  	   SCIP_Bool lperror;
205  	
206  	   int nlpcands;
207  	   int npriolpcands;
208  	   int nvars;
209  	   int bestcand;
210  	   int nlprows;
211  	   int i;
212  	   int counter;
213  	   int ncomplete;
214  	   int ndiscvars;
215  	
216  	   assert(branchrule != NULL);
217  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
218  	   assert(scip != NULL);
219  	   assert(result != NULL);
220  	
221  	   if( !SCIPisLPSolBasic(scip) )
222  	      return SCIP_OKAY;
223  	
224  	   SCIPdebugMsg(scip, "Execlp method of " BRANCHRULE_NAME " branching\n");
225  	
226  	   /* get problem variables and LP row data */
227  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
228  	   ndiscvars = SCIPgetNBinVars(scip)+SCIPgetNIntVars(scip);
229  	   nlprows = SCIPgetNLPRows(scip);
230  	   lprows = SCIPgetLPRows(scip);
231  	
232  	   /* get branching candidates */
233  	   SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, &npriolpcands, NULL) );
234  	   nlpcands = SCIPgetNLPBranchCands(scip);
235  	   assert(nlpcands > 0);
236  	
237  	   /* get branching rule data */
238  	   branchruledata = SCIPbranchruleGetData(branchrule);
239  	   assert(branchruledata != NULL);
240  	
241  	   /* allocate skipping arrays on first call */
242  	   if( branchruledata->skipdown == NULL )
243  	   {
244  	      assert(branchruledata->skipup == NULL);
245  	
246  	      branchruledata->skipsize = nvars;
247  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
248  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
249  	   }
250  	
251  	   /* reset skipping arrays to zero */
252  	   BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
253  	   BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
254  	
255  	   /* allocate required data structures */
256  	   SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsmin, nlpcands) );
257  	   SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsmax, nlpcands) );
258  	   SCIP_CALL( SCIPallocBufferArray(scip, &lpcandscopy, nlpcands) );
259  	   SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsfraccopy, nlpcands) );
260  	   SCIP_CALL( SCIPallocBufferArray(scip, &lpcandssolcopy, nlpcands) );
261  	   newlpcandsmin = NULL;
262  	   newlpcandsmax = NULL;
263  	   if( branchruledata->useunion && SCIPgetDepth(scip) < branchruledata->maxdepthunion && !branchruledata->onlyF2)
264  	   {
265  	      SCIP_CALL( SCIPallocBufferArray(scip, &newlpcandsmin, ndiscvars) );
266  	      SCIP_CALL( SCIPallocBufferArray(scip, &newlpcandsmax, ndiscvars) );
267  	   }
268  	   BMScopyMemoryArray(lpcandsmin, lpcandssol, nlpcands);
269  	   BMScopyMemoryArray(lpcandsmax, lpcandssol, nlpcands);
270  	   BMScopyMemoryArray(lpcandssolcopy, lpcandssol, nlpcands);
271  	   BMScopyMemoryArray(lpcandsfraccopy, lpcandsfrac, nlpcands);
272  	   BMScopyMemoryArray(lpcandscopy, lpcands, nlpcands);
273  	
274  	   SCIP_CALL( SCIPstartClock(scip, branchruledata->cloudclock) );
275  	   branchruledata->ntried++;
276  	
277  	   /* start diving to calculate the solution cloud */
278  	   SCIP_CALL( SCIPstartDive(scip) );
279  	
280  	   /* fix variables with nonzero reduced costs to reduce LP to the optimal face */
281  	   for( i = 0; i < nvars; ++i )
282  	   {
283  	      SCIP_Real solval;
284  	      solval = SCIPgetSolVal(scip, NULL, vars[i]);
285  	
286  	      if( !SCIPisFeasZero(scip, SCIPgetVarRedcost(scip, vars[i])) )
287  	      {
288  	         SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], solval) );
289  	         SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], solval) );
290  	      }
291  	      else if( SCIPvarGetType(vars[i]) == SCIP_VARTYPE_INTEGER && !SCIPisIntegral(scip, solval) )
292  	      {
293  	         SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], SCIPfloor(scip, solval)) );
294  	         SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], SCIPceil(scip, solval)) );
295  	      }
296  	
297  	      SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], 0.0) );
298  	   }
299  	
300  	   /* fix LP rows with nonzero dual solution to reduce LP to the optimal face */
301  	   for( i = 0; i < nlprows; ++i )
302  	   {
303  	      SCIP_Real dualsol;
304  	      dualsol = SCIProwGetDualsol(lprows[i]);
305  	      if( !SCIPisZero(scip, dualsol) )
306  	      {
307  	         if( dualsol > 0 && SCIPisFeasEQ(scip, SCIProwGetLhs(lprows[i]), SCIPgetRowActivity(scip,lprows[i])) )
308  	         {
309  	            SCIP_CALL( SCIPchgRowRhsDive(scip, lprows[i], SCIProwGetLhs(lprows[i])) );
310  	         }
311  	         else if( dualsol < 0 && SCIPisFeasEQ(scip, SCIProwGetRhs(lprows[i]), SCIPgetRowActivity(scip,lprows[i])) )
312  	         {
313  	            SCIP_CALL( SCIPchgRowLhsDive(scip, lprows[i], SCIProwGetRhs(lprows[i])) );
314  	         }
315  	      }
316  	   }
317  	
318  	   newpoint = TRUE;
319  	   counter = 0;
320  	
321  	   if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion )
322  	   {
323  	      /* update cloud intervals for candidates that have been integral in original LP, but have been fractional in previous cloud points */
324  	      for( i = 0; i < ndiscvars; ++i)
325  	      {
326  	         SCIP_Real solval;
327  	         solval = SCIPgetSolVal(scip, NULL, vars[i]);
328  	
329  	         assert(newlpcandsmin != NULL);
330  	         assert(newlpcandsmax != NULL);
331  	
332  	         newlpcandsmin[i] = solval;
333  	         newlpcandsmax[i] = solval;
334  	      }
335  	   }
336  	
337  	   /* loop that generates new cloud point */
338  	   while( newpoint && branchruledata->usecloud )
339  	   {
340  	#ifdef NDEBUG
341  	      SCIP_RETCODE retcode;
342  	#endif
343  	
344  	      /* apply feasibility pump objective function to fractional variables */
345  	      for( i = 0; i < nlpcands; ++i )
346  	      {
347  	         SCIP_Real frac;
348  	         frac = SCIPfrac(scip, SCIPgetSolVal(scip, NULL, lpcandscopy[i]));
349  	
350  	         if( !SCIPisZero(scip, frac) && !SCIPisIntegral(scip, lpcandsmin[i]) && !SCIPisIntegral(scip, lpcandsmax[i]) )
351  	         {
352  	            if( frac < 0.5 )
353  	            {
354  	               SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], 1.0) );
355  	            }
356  	            else
357  	            {
358  	               SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], -1.0) );
359  	            }
360  	         }
361  	      }
362  	
363  	      /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
364  	       * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
365  	       */
366  	#ifdef NDEBUG
367  	      retcode = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
368  	      if( retcode != SCIP_OKAY )
369  	      {
370  	         SCIPwarningMessage(scip, "Error while solving LP in " BRANCHRULE_NAME "; LP solve terminated with code <%d>\n",retcode);
371  	      }
372  	#else
373  	      SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) );
374  	#endif
375  	
376  	      if( lperror || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
377  	         break;
378  	
379  	      /* check if a solution has been found */
380  	      if( SCIPgetNLPBranchCands(scip) == 0 )
381  	      {
382  	         SCIP_Bool success;
383  	         SCIP_SOL* sol;
384  	
385  	         /* create solution from diving LP */
386  	         SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
387  	         SCIP_CALL( SCIPlinkLPSol(scip, sol) );
388  	         SCIPdebugMsg(scip, "cloud branching found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, sol));
389  	
390  	         /* try to add solution to SCIP */
391  	         SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
392  	
393  	         /* check, if solution was feasible and good enough */
394  	         if( success )
395  	         {
396  	            SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
397  	            SCIP_CALL( SCIPendDive(scip) );
398  	            *result = SCIP_CUTOFF;
399  	            goto TERMINATE;
400  	         }
401  	      }
402  	
403  	      /* update cloud intervals for candidates that have been fractional in original LP */
404  	      newpoint = FALSE;
405  	      for( i = 0; i < nlpcands; ++i)
406  	      {
407  	         SCIP_Real solval;
408  	         solval = SCIPgetSolVal(scip, NULL, lpcandscopy[i]);
409  	
410  	         if( SCIPisFeasIntegral(scip,solval) && !SCIPisFeasIntegral(scip, lpcandsmin[i]) && !SCIPisFeasIntegral(scip, lpcandsmax[i]) )
411  	            newpoint = TRUE;
412  	
413  	         lpcandsmin[i] = MIN(lpcandsmin[i], solval);
414  	         lpcandsmax[i] = MAX(lpcandsmax[i], solval);
415  	      }
416  	
417  	      if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion )
418  	      {
419  	         /* update cloud intervals for candidates that have been integral in original LP, but have been fractional in previous cloud points */
420  	         for( i = 0; i < ndiscvars; ++i)
421  	         {
422  	            SCIP_Real solval;
423  	            solval = SCIPgetSolVal(scip, NULL, vars[i]);
424  	
425  	            assert(newlpcandsmin != NULL);
426  	            assert(newlpcandsmax != NULL);
427  	
428  	            newlpcandsmin[i] = MIN(newlpcandsmin[i], solval);
429  	            newlpcandsmax[i] = MAX(newlpcandsmax[i], solval);
430  	         }
431  	      }
432  	
433  	      if( newpoint )
434  	         counter++;
435  	
436  	      if( branchruledata->maxpoints != -1 && counter >= branchruledata->maxpoints )
437  	         break;
438  	   }
439  	
440  	   SCIPdebugMsg(scip, "considered %d additional points in the cloud\n",counter);
441  	
442  	   /* terminate the diving */
443  	   SCIP_CALL( SCIPendDive(scip) );
444  	
445  	   SCIP_CALL( SCIPstopClock(scip, branchruledata->cloudclock) );
446  	   ncomplete = nlpcands;
447  	
448  	   if( counter > 0 )
449  	   {
450  	      branchruledata->ncloudpoints += (counter+1);
451  	      branchruledata->nuseful++;
452  	
453  	      counter = 0;
454  	
455  	      /* sort all variables for which both bounds are fractional to the front */
456  	      for( i = 0; i < nlpcands; ++i)
457  	      {
458  	         if( !SCIPisFeasIntegral(scip, lpcandsmin[i]) && !SCIPisFeasIntegral(scip, lpcandsmax[i]) )
459  	         {
460  	            assert(counter <= i);
461  	            lpcandscopy[counter] = lpcandscopy[i];
462  	            lpcandssolcopy[counter] = lpcandssolcopy[i];
463  	            lpcandsfraccopy[counter] = lpcandsfraccopy[i];
464  	            counter++;
465  	         }
466  	      }
467  	
468  	      /* should only be in that if condition when at least one bound could be made integral */
469  	      assert(nlpcands - counter > 0);
470  	
471  	      ncomplete = counter;
472  	
473  	      /* filter all variables for which exactly one interval bound is fractional */
474  	      for( i = 0; i < nlpcands && !branchruledata->onlyF2; ++i)
475  	      {
476  	         if( SCIPisFeasIntegral(scip, lpcandsmin[i]) != SCIPisFeasIntegral(scip, lpcandsmax[i]) )
477  	         {
478  	            assert(counter < nlpcands);
479  	            lpcandscopy[counter] = lpcandscopy[i];
480  	            lpcandssolcopy[counter] = lpcandssolcopy[i];
481  	            lpcandsfraccopy[counter] = lpcandsfraccopy[i];
482  	
483  	            if( SCIPisFeasIntegral(scip, lpcandsmin[i]) )
484  	               branchruledata->skipdown[counter] = TRUE;
485  	            if( SCIPisFeasIntegral(scip, lpcandsmax[i]) )
486  	               branchruledata->skipup[counter] = TRUE;
487  	            assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]);
488  	
489  	            counter++;
490  	         }
491  	      }
492  	
493  	      SCIPdebugMsg(scip, "can fully skip %d/%d strong branching candidates\n", nlpcands - counter, nlpcands);
494  	      SCIPdebugMsg(scip, "can half  skip %d/%d strong branching candidates\n", counter - ncomplete, nlpcands);
495  	   }
496  	   else
497  	      counter = nlpcands;
498  	
499  	   /* if cloud sampling was not successful enough, disable it */
500  	   if( branchruledata->usecloud &&
501  	      branchruledata->ntried > 100 &&
502  	      (SCIP_Real)branchruledata->nuseful / branchruledata->ntried < branchruledata->minsuccessrate )
503  	   {
504  	      SCIPdebugMsg(scip, "Disabling cloud branching (not effective)\n");
505  	      branchruledata->usecloud = FALSE;
506  	   }
507  	
508  	   if( branchruledata->onlyF2 )
509  	      counter = MAX(counter,1);
510  	
511  	   /* the second counter should maybe be replaced at some point */
512  	   SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcandscopy, lpcandssolcopy, lpcandsfraccopy, branchruledata->skipdown,
513  	         branchruledata->skipup, counter, counter, ncomplete, &branchruledata->lastcand, 0, FALSE, FALSE,
514  	         &bestcand, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
515  	
516  	   if( branchruledata->lastcand <= ncomplete )
517  	   {
518  	      SCIPdebugMsg(scip, "saved %d of %d LPs\n", 2*(nlpcands - ncomplete), 2*nlpcands);
519  	      branchruledata->nsavedlps += 2*(nlpcands - ncomplete);
520  	   }
521  	   else
522  	   {
523  	      SCIPdebugMsg(scip, "saved %d of %d LPs\n", 2*(nlpcands - counter)+counter - ncomplete, 2*nlpcands);
524  	      branchruledata->nsavedlps += 2*(nlpcands - counter)+counter - ncomplete;
525  	   }
526  	
527  	   /* perform the branching */
528  	   if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED && counter > 0 )
529  	   {
530  	      SCIP_NODE* downchild;
531  	      SCIP_NODE* upchild;
532  	      SCIP_VAR* var;
533  	      SCIP_Bool allcolsinlp;
534  	      SCIP_Bool exactsolve;
535  	      SCIP_Bool newselected;
536  	
537  	      assert(*result == SCIP_DIDNOTRUN);
538  	      assert(0 <= bestcand && bestcand < nlpcands);
539  	      assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
540  	
541  	      var = lpcandscopy[bestcand];
542  	      newselected = FALSE;
543  	
544  	      /* if there are new candidates variables, also try them */
545  	      if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion && branchruledata->lastcand > ncomplete )
546  	      {
547  	         SCIP_VAR** newlpcands;
548  	
549  	         counter = 0;
550  	         /* reset skipping arrays to zero */
551  	         BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
552  	         BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
553  	
554  	         SCIP_CALL( SCIPallocBufferArray(scip, &newlpcands, ndiscvars) );
555  	
556  	         /* get new LP candidates with one fractional bound */
557  	         for( i = 0; i < ndiscvars; ++i)
558  	         {
559  	            if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, vars[i])) )
560  	               continue;
561  	
562  	            assert(newlpcandsmin != NULL);
563  	            assert(newlpcandsmax != NULL);
564  	
565  	            if( SCIPisFeasIntegral(scip, newlpcandsmin[i]) != SCIPisFeasIntegral(scip, newlpcandsmax[i]) )
566  	            {
567  	               newlpcands[counter] = vars[i];
568  	
569  	               if( SCIPisFeasIntegral(scip, newlpcandsmin[i]) )
570  	                  branchruledata->skipdown[counter] = TRUE;
571  	               if( SCIPisFeasIntegral(scip, newlpcandsmax[i]) )
572  	                  branchruledata->skipup[counter] = TRUE;
573  	               assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]);
574  	
575  	               counter++;
576  	            }
577  	         }
578  	
579  	         /* when there are new candidates, also try these */
580  	         if( counter > 0 )
581  	         {
582  	            SCIP_Real newdown;
583  	            SCIP_Real newup;
584  	            SCIP_Real newscore;
585  	            int newcand;
586  	            SCIP_Bool newdownvalid;
587  	            SCIP_Bool newupvalid;
588  	            SCIP_Real newbound;
589  	
590  	            branchruledata->ntriedunions++;
591  	            newscore = -SCIPinfinity(scip);
592  	            SCIP_CALL( SCIPselectVarPseudoStrongBranching(scip, newlpcands, branchruledata->skipdown, branchruledata->skipup, counter, counter,
593  	                  &newcand, &newdown, &newup, &newscore, &newdownvalid, &newupvalid, &newbound, result) );
594  	
595  	            if( *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM || *result == SCIP_CONSADDED  )
596  	            {
597  	               SCIPfreeBufferArray(scip, &newlpcands);
598  	               goto TERMINATE;
599  	            }
600  	
601  	            if( newscore > bestscore )
602  	            {
603  	               bestcand = newcand;
604  	               var = newlpcands[newcand];
605  	               bestdown = newdown;
606  	               bestup = newup;
607  	               bestdownvalid = newdownvalid;
608  	               bestupvalid = newupvalid;
609  	               bestscore = newscore;
610  	               newselected = TRUE;
611  	               branchruledata->nusefulunions++;
612  	            }
613  	         }
614  	         /* free temporary array for new union candidates */
615  	         SCIPfreeBufferArray(scip, &newlpcands);
616  	      }
617  	
618  	      /* perform the branching */
619  	      if( !newselected )
620  	      {
621  	         SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
622  	            counter, bestcand, SCIPvarGetName(var), lpcandssolcopy[bestcand], bestdown, bestup, bestscore);
623  	      }
624  	      else
625  	      {
626  	         SCIPdebugMsg(scip, " -> selected from %d new candidates,  candidate %d: variable <%s> (down=%g, up=%g, score=%g)\n",
627  	            counter, bestcand, SCIPvarGetName(var), bestdown, bestup, bestscore);
628  	      }
629  	
630  	      assert(!SCIPisFeasIntegral(scip, SCIPvarGetSol(lpcands[bestcand], TRUE)));
631  	
632  	      SCIP_CALL( SCIPbranchVar(scip, var, &downchild, NULL, &upchild) );
633  	      assert(downchild != NULL);
634  	      assert(upchild != NULL);
635  	
636  	      /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
637  	       * for cutting off sub problems and improving lower bounds of children
638  	       */
639  	      exactsolve = SCIPisExactSolve(scip);
640  	
641  	      /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
642  	      allcolsinlp = SCIPallColsInLP(scip);
643  	
644  	      /* update the lower bounds in the children */
645  	      if( allcolsinlp && !exactsolve )
646  	      {
647  	         SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
648  	         SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
649  	      }
650  	      SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
651  	      SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
652  	
653  	      *result = SCIP_BRANCHED;
654  	   }
655  	
656  	 TERMINATE:
657  	   if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion )
658  	   {
659  	      SCIPfreeBufferArray(scip, &newlpcandsmax);
660  	      SCIPfreeBufferArray(scip, &newlpcandsmin);
661  	   }
662  	   SCIPfreeBufferArray(scip, &lpcandscopy);
663  	   SCIPfreeBufferArray(scip, &lpcandssolcopy);
664  	   SCIPfreeBufferArray(scip, &lpcandsfraccopy);
665  	   SCIPfreeBufferArray(scip, &lpcandsmax);
666  	   SCIPfreeBufferArray(scip, &lpcandsmin);
667  	
668  	   /* if union usage was not successful enough, disable it */
669  	   if( branchruledata->useunion &&
670  	      branchruledata->ntriedunions > 10 &&
671  	      (SCIP_Real)branchruledata->nusefulunions / branchruledata->ntriedunions < branchruledata->minsuccessunion )
672  	   {
673  	      SCIPdebugMsg(scip, "Disabling union usage (not effective)\n");
674  	      branchruledata->useunion = FALSE;
675  	   }
676  	
677  	   return SCIP_OKAY;  /*lint !e438*/
678  	}
679  	
680  	/*
681  	 * branching rule specific interface methods
682  	 */
683  	
684  	/** creates the cloud branching rule and includes it in SCIP */
685  	SCIP_RETCODE SCIPincludeBranchruleCloud(
686  	   SCIP*                 scip                /**< SCIP data structure */
687  	   )
688  	{
689  	   SCIP_BRANCHRULEDATA* branchruledata;
690  	   SCIP_BRANCHRULE* branchrule;
691  	
692  	   /* create cloud branching rule data */
693  	   SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
694  	   branchruledata->lastcand = 0;
695  	   branchruledata->skipsize = 0;
696  	   branchruledata->skipup = NULL;
697  	   branchruledata->skipdown = NULL;
698  	   SCIP_CALL( SCIPcreateClock(scip, &(branchruledata->cloudclock)) );
699  	
700  	   /* include branching rule */
701  	   branchrule = NULL;
702  	   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
703  	         BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
704  	   assert(branchrule != NULL);
705  	
706  	   /* set non-fundamental callbacks via setter functions */
707  	   SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeCloud) );
708  	   SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitCloud) );
709  	   SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpCloud) );
710  	
711  	   /* add cloud branching rule parameters */
712  	   SCIP_CALL( SCIPaddBoolParam(scip,
713  	         "branching/" BRANCHRULE_NAME "/usecloud",
714  	         "should a cloud of points be used?",
715  	         &branchruledata->usecloud, FALSE, DEFAULT_USECLOUD, NULL, NULL) );
716  	   SCIP_CALL( SCIPaddBoolParam(scip,
717  	         "branching/" BRANCHRULE_NAME "/onlyF2",
718  	         "should only F2 be used?",
719  	         &branchruledata->onlyF2, FALSE, DEFAULT_ONLYF2, NULL, NULL) );
720  	   SCIP_CALL( SCIPaddBoolParam(scip,
721  	         "branching/" BRANCHRULE_NAME "/useunion",
722  	         "should the union of candidates be used?",
723  	         &branchruledata->useunion, FALSE, DEFAULT_USEUNION, NULL, NULL) );
724  	   SCIP_CALL( SCIPaddIntParam(scip,
725  	         "branching/" BRANCHRULE_NAME "/maxpoints",
726  	         "maximum number of points for the cloud (-1 means no limit)",
727  	         &branchruledata->maxpoints, FALSE, DEFAULT_MAXPOINTS, -1, INT_MAX, NULL, NULL) );
728  	   SCIP_CALL( SCIPaddRealParam(scip,
729  	         "branching/" BRANCHRULE_NAME "/minsuccessrate",
730  	         "minimum success rate for the cloud",
731  	         &branchruledata->minsuccessrate, FALSE, DEFAULT_MINSUCCESSRATE, 0.0, 1.0, NULL, NULL) );
732  	   SCIP_CALL( SCIPaddRealParam(scip,
733  	         "branching/" BRANCHRULE_NAME "/minsuccessunion",
734  	         "minimum success rate for the union",
735  	         &branchruledata->minsuccessunion, FALSE, DEFAULT_MINSUCCESSUNION, 0.0, 1.0, NULL, NULL) );
736  	   SCIP_CALL( SCIPaddIntParam(scip,
737  	         "branching/" BRANCHRULE_NAME "/maxdepthunion",
738  	         "maximum depth for the union",
739  	         &branchruledata->maxdepthunion, FALSE, DEFAULT_MAXDEPTHUNION, 0, 65000, NULL, NULL) );
740  	
741  	   return SCIP_OKAY;
742  	}
743