1    	
2    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
3    	/*                                                                           */
4    	/*                  This file is part of the program and library             */
5    	/*         SCIP --- Solving Constraint Integer Programs                      */
6    	/*                                                                           */
7    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
8    	/*                                                                           */
9    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
10   	/*  you may not use this file except in compliance with the License.         */
11   	/*  You may obtain a copy of the License at                                  */
12   	/*                                                                           */
13   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
14   	/*                                                                           */
15   	/*  Unless required by applicable law or agreed to in writing, software      */
16   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
17   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
18   	/*  See the License for the specific language governing permissions and      */
19   	/*  limitations under the License.                                           */
20   	/*                                                                           */
21   	/*  You should have received a copy of the Apache-2.0 license                */
22   	/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
23   	/*                                                                           */
24   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
25   	
26   	/**@file   branch_random.c
27   	 * @ingroup DEFPLUGINS_BRANCH
28   	 * @brief  random variable branching rule
29   	 * @author Tobias Achterberg
30   	 * @author Stefan Vigerske
31   	 */
32   	
33   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34   	
35   	#include "scip/branch_random.h"
36   	#include "scip/pub_branch.h"
37   	#include "scip/pub_message.h"
38   	#include "scip/pub_misc.h"
39   	#include "scip/pub_var.h"
40   	#include "scip/scip_branch.h"
41   	#include "scip/scip_message.h"
42   	#include "scip/scip_mem.h"
43   	#include "scip/scip_numerics.h"
44   	#include "scip/scip_param.h"
45   	#include "scip/scip_randnumgen.h"
46   	#include "scip/scip_tree.h"
47   	#include <string.h>
48   	
49   	
50   	#define BRANCHRULE_NAME          "random"
51   	#define BRANCHRULE_DESC          "random variable branching"
52   	#define BRANCHRULE_PRIORITY      -100000
53   	#define BRANCHRULE_MAXDEPTH      -1
54   	#define BRANCHRULE_MAXBOUNDDIST  1.0
55   	
56   	#define DEFAULT_INITSEED                41   /**< initial random seed */
57   	
58   	/** branching rule data */
59   	struct SCIP_BranchruleData
60   	{
61   	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator */
62   	   int                   initseed;           /**< initial random seed value */
63   	};
64   	
65   	/*
66   	 * Local methods
67   	 */
68   	
69   	/** selects a random active variable from a given list of variables */
70   	static
71   	void getRandomVariable(
72   	   SCIP*                 scip,               /**< SCIP data structure */
73   	   SCIP_BRANCHRULEDATA*  branchruledata,     /**< branchrule data */
74   	   SCIP_VAR**            cands,              /**< array of branching candidates */
75   	   SCIP_Real*            candssol,           /**< relaxation solution values of branching candidates, or NULL */
76   	   int                   ncands,             /**< number of branching candidates */
77   	   SCIP_VAR**            bestcand,           /**< buffer to store pointer to best candidate */
78   	   SCIP_Real*            bestcandsol         /**< buffer to store solution value of best candidate */
79   	   )
80   	{
81   	   int idx;
82   	   int firstidx;
83   	
84   	   assert(scip != NULL);
85   	   assert(cands != NULL);
86   	   assert(ncands > 0);
87   	   assert(bestcand != NULL);
88   	   assert(bestcandsol != NULL);
89   	
90   	   idx = SCIPrandomGetInt(branchruledata->randnumgen, 0, ncands-1);
91   	   assert(idx >= 0);
92   	
93   	   /* handle case where cands[idx] is fixed by selecting next idx with unfixed var
94   	    * this may happen if we are inside a multi-aggregation */
95   	   firstidx = idx;
96   	   while( SCIPisEQ(scip, SCIPvarGetLbLocal(cands[idx]), SCIPvarGetUbLocal(cands[idx])) )
97   	   {
98   	      ++idx;
99   	      if( idx == ncands )
100  	         idx = 0;
101  	      if( idx == firstidx )
102  	      {
103  	         /* odd: all variables seem to be fixed */
104  	         SCIPdebugMsg(scip, "Warning: all branching candidates seem to be fixed\n");
105  	         return;
106  	      }
107  	   }
108  	
109  	   /* a branching variable candidate should either be an active problem variable or a multi-aggregated variable */
110  	   assert(SCIPvarIsActive(SCIPvarGetProbvar(cands[idx])) ||
111  	      SCIPvarGetStatus(SCIPvarGetProbvar(cands[idx])) == SCIP_VARSTATUS_MULTAGGR);
112  	
113  	   if( SCIPvarGetStatus(SCIPvarGetProbvar(cands[idx])) == SCIP_VARSTATUS_MULTAGGR )
114  	   {
115  	      /* for a multi-aggregated variable, we call the getRandomVariable function recursively with all variables in the multi-aggregation */
116  	      SCIP_VAR* cand;
117  	
118  	      cand = SCIPvarGetProbvar(cands[idx]);
119  	
120  	      getRandomVariable(scip, branchruledata, SCIPvarGetMultaggrVars(cand), NULL, SCIPvarGetMultaggrNVars(cand),
121  	            bestcand, bestcandsol);
122  	      return;
123  	   }
124  	
125  	   assert(idx >= 0 && idx < ncands);
126  	
127  	   *bestcand = cands[idx];
128  	   assert(*bestcand != NULL);
129  	
130  	   if( candssol != NULL )
131  	      *bestcandsol = candssol[idx];
132  	}
133  	
134  	/*
135  	 * Callback methods
136  	 */
137  	
138  	/** copy method for branchrule plugins (called when SCIP copies plugins) */
139  	static
140  	SCIP_DECL_BRANCHCOPY(branchCopyRandom)
141  	{  /*lint --e{715}*/
142  	   assert(scip != NULL);
143  	   assert(branchrule != NULL);
144  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
145  	
146  	   /* call inclusion method of branchrule */
147  	   SCIP_CALL( SCIPincludeBranchruleRandom(scip) );
148  	
149  	   return SCIP_OKAY;
150  	}
151  	
152  	/** destructor of branching rule to free user data (called when SCIP is exiting) */
153  	/**! [SnippetBranchFreeRandom] */
154  	static
155  	SCIP_DECL_BRANCHFREE(branchFreeRandom)
156  	{  /*lint --e{715}*/
157  	   SCIP_BRANCHRULEDATA* branchruledata;
158  	
159  	   /* get branching rule data */
160  	   branchruledata = SCIPbranchruleGetData(branchrule);
161  	   assert(branchruledata != NULL);
162  	
163  	   /* free branching rule data */
164  	   SCIPfreeBlockMemory(scip, &branchruledata);
165  	   SCIPbranchruleSetData(branchrule, NULL);
166  	
167  	   return SCIP_OKAY;
168  	}
169  	/**! [SnippetBranchFreeRandom] */
170  	
171  	
172  	/** initialization method of branching rule (called after problem was transformed) */
173  	static
174  	SCIP_DECL_BRANCHINIT(branchInitRandom)
175  	{  /*lint --e{715}*/
176  	   SCIP_BRANCHRULEDATA* branchruledata;
177  	
178  	   branchruledata = SCIPbranchruleGetData(branchrule);
179  	   assert(branchruledata != NULL);
180  	   assert(branchruledata->initseed >= 0);
181  	
182  	   /* create a random number generator */
183  	   SCIP_CALL( SCIPcreateRandom(scip, &branchruledata->randnumgen,
184  	         (unsigned int)branchruledata->initseed, TRUE) );
185  	
186  	   return SCIP_OKAY;
187  	}
188  	
189  	/** deinitialization method of branching rule */
190  	static
191  	SCIP_DECL_BRANCHEXIT(branchExitRandom)
192  	{  /*lint --e{715}*/
193  	   SCIP_BRANCHRULEDATA* branchruledata;
194  	
195  	   /* get branching rule data */
196  	   branchruledata = SCIPbranchruleGetData(branchrule);
197  	   assert(branchruledata != NULL);
198  	
199  	   /* free random number generator */
200  	   SCIPfreeRandom(scip, &branchruledata->randnumgen);
201  	
202  	   return SCIP_OKAY;
203  	}
204  	
205  	/** branching execution method for fractional LP solutions */
206  	static
207  	SCIP_DECL_BRANCHEXECLP(branchExeclpRandom)
208  	{  /*lint --e{715}*/
209  	   SCIP_BRANCHRULEDATA* branchruledata;
210  	   SCIP_VAR** lpcands;
211  	   int nlpcands;
212  	   int bestcand;
213  	
214  	   assert(branchrule != NULL);
215  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
216  	   assert(scip != NULL);
217  	   assert(result != NULL);
218  	
219  	   SCIPdebugMsg(scip, "Execlp method of random branching in depth %d\n", SCIPgetDepth(scip));
220  	
221  	   branchruledata = SCIPbranchruleGetData(branchrule);
222  	   assert(branchruledata != NULL);
223  	
224  	   /* get branching candidates */
225  	   SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, NULL, NULL, &nlpcands, NULL) );
226  	   assert(nlpcands > 0);
227  	
228  	   /* get random branching candidate */
229  	   bestcand = SCIPrandomGetInt(branchruledata->randnumgen, 0, nlpcands-1);
230  	   assert(bestcand >= 0);
231  	
232  	   SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s>\n",
233  	      nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand]));
234  	
235  	   /* perform the branching */
236  	   SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) );
237  	   *result = SCIP_BRANCHED;
238  	
239  	   return SCIP_OKAY;
240  	}
241  	
242  	
243  	/** branching execution method for external candidates */
244  	static
245  	SCIP_DECL_BRANCHEXECEXT(branchExecextRandom)
246  	{  /*lint --e{715}*/
247  	   SCIP_BRANCHRULEDATA* branchruledata;
248  	   SCIP_VAR** externcands;
249  	   SCIP_Real* externcandssol;
250  	   int nprioexterncands;
251  	   SCIP_VAR* bestcand;
252  	   SCIP_Real bestcandsol;
253  	   SCIP_Real brpoint;
254  	   SCIP_NODE* downchild;
255  	   SCIP_NODE* eqchild;
256  	   SCIP_NODE* upchild;
257  	
258  	   assert(branchrule != NULL);
259  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
260  	   assert(scip != NULL);
261  	   assert(result != NULL);
262  	
263  	   SCIPdebugMsg(scip, "Execrel method of random branching\n");
264  	
265  	   branchruledata = SCIPbranchruleGetData(branchrule);
266  	   assert(branchruledata != NULL);
267  	
268  	   bestcand = NULL;
269  	   bestcandsol = 0.0;
270  	
271  	   /* get branching candidates */
272  	   SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, NULL, NULL, &nprioexterncands, NULL, NULL, NULL) );
273  	   assert(nprioexterncands > 0);
274  	
275  	   /* get random branching candidate
276  	    *
277  	    * since variables can occur several times in the list of candidates, variables that have been added more often have
278  	    * a higher probability to be chosen for branching
279  	    */
280  	   getRandomVariable(scip, branchruledata, externcands, externcandssol, nprioexterncands, &bestcand, &bestcandsol);
281  	
282  	   if( bestcand == NULL )
283  	   {
284  	      SCIPerrorMessage("branchExecrelRandom failed to select a branching variable from %d candidates\n", nprioexterncands);
285  	      *result = SCIP_DIDNOTRUN;
286  	      return SCIP_OKAY;
287  	   }
288  	
289  	   brpoint = SCIPgetBranchingPoint(scip, bestcand, bestcandsol);
290  	
291  	   SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s> with solution value %g, branching point=%g\n",
292  	      nprioexterncands, SCIPvarGetName(bestcand), bestcandsol, brpoint);
293  	
294  	   SCIP_CALL( SCIPbranchVarVal(scip, bestcand, brpoint, &downchild, &eqchild, &upchild) );
295  	
296  	   if( downchild != NULL || eqchild != NULL || upchild != NULL )
297  	   {
298  	      *result = SCIP_BRANCHED;
299  	   }
300  	   else
301  	   {
302  	      /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
303  	      assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand)));
304  	      *result = SCIP_REDUCEDDOM;
305  	   }
306  	
307  	   return SCIP_OKAY;
308  	}
309  	
310  	/** branching execution method for not completely fixed pseudo solutions */
311  	static
312  	SCIP_DECL_BRANCHEXECPS(branchExecpsRandom)
313  	{  /*lint --e{715}*/
314  	   SCIP_BRANCHRULEDATA* branchruledata;
315  	   SCIP_VAR** pseudocands;
316  	   int npseudocands;
317  	   int bestcand;
318  	
319  	   assert(branchrule != NULL);
320  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
321  	   assert(scip != NULL);
322  	   assert(result != NULL);
323  	
324  	   SCIPdebugMsg(scip, "Execps method of random branching\n");
325  	
326  	   branchruledata = SCIPbranchruleGetData(branchrule);
327  	   assert(branchruledata != NULL);
328  	
329  	   /* get branching candidates */
330  	   SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, NULL, &npseudocands) );
331  	   assert(npseudocands > 0);
332  	
333  	   /* get random branching candidate */
334  	   bestcand = SCIPrandomGetInt(branchruledata->randnumgen, 0, npseudocands-1);
335  	   assert(bestcand >= 0);
336  	
337  	   SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s>\n",
338  	      npseudocands, bestcand, SCIPvarGetName(pseudocands[bestcand]));
339  	
340  	   /* perform the branching */
341  	   SCIP_CALL( SCIPbranchVar(scip, pseudocands[bestcand], NULL, NULL, NULL) );
342  	   *result = SCIP_BRANCHED;
343  	
344  	   return SCIP_OKAY;
345  	}
346  	
347  	
348  	/*
349  	 * branching specific interface methods
350  	 */
351  	
352  	/** creates the random branching rule and includes it in SCIP */
353  	SCIP_RETCODE SCIPincludeBranchruleRandom(
354  	   SCIP*                 scip                /**< SCIP data structure */
355  	   )
356  	{
357  	   SCIP_BRANCHRULEDATA* branchruledata;
358  	   SCIP_BRANCHRULE* branchrule;
359  	
360  	   /* create random branching rule data */
361  	   SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
362  	
363  	   /* include allfullstrong branching rule */
364  	   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
365  	         BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
366  	
367  	   assert(branchrule != NULL);
368  	
369  	   /* set non-fundamental callbacks via specific setter functions*/
370  	   SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyRandom) );
371  	   SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeRandom) );
372  	   SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitRandom) );
373  	   SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitRandom) );
374  	   SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpRandom) );
375  	   SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextRandom) );
376  	   SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsRandom) );
377  	
378  	   SCIP_CALL( SCIPaddIntParam(scip, "branching/" BRANCHRULE_NAME "/seed", "initial random seed value",
379  	         &branchruledata->initseed, FALSE, DEFAULT_INITSEED, 0, INT_MAX, NULL, NULL) );
380  	
381  	   return SCIP_OKAY;
382  	}
383