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