Scippy

SCIP

Solving Constraint Integer Programs

branch_random.c
Go to the documentation of this file.
1 
2 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
3 /* */
4 /* This file is part of the program and library */
5 /* SCIP --- Solving Constraint Integer Programs */
6 /* */
7 /* Copyright (C) 2002-2020 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
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])) ||
103 
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
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 */
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
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
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
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
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
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
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 */
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 */
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 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
static SCIP_DECL_BRANCHFREE(branchFreeRandom)
#define BRANCHRULE_MAXDEPTH
Definition: branch_random.c:44
public methods for SCIP parameter handling
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
public methods for memory management
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:888
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
static SCIP_DECL_BRANCHEXECEXT(branchExecextRandom)
random variable branching rule
static SCIP_DECL_BRANCHEXECLP(branchExeclpRandom)
static SCIP_DECL_BRANCHINIT(branchInitRandom)
#define FALSE
Definition: def.h:73
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_DECL_BRANCHEXECPS(branchExecpsRandom)
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17335
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1117
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_random.c:45
public methods for branching rules
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17131
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:107
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPdebugMsg
Definition: scip_message.h:69
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:724
public methods for the branch-and-bound tree
static SCIP_DECL_BRANCHEXIT(branchExitRandom)
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
#define SCIPerrorMessage
Definition: pub_message.h:55
#define BRANCHRULE_PRIORITY
Definition: branch_random.c:43
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: scip_branch.c:502
SCIP_RETCODE SCIPincludeBranchruleRandom(SCIP *scip)
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1041
public data structures and miscellaneous methods
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:9945
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
SCIP_EXPORT SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11984
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:176
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:256
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17718
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17728
public methods for branching rule plugins and branching
static void getRandomVariable(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR **cands, SCIP_Real *candssol, int ncands, SCIP_VAR **bestcand, SCIP_Real *bestcandsol)
Definition: branch_random.c:62
public methods for random numbers
#define BRANCHRULE_NAME
Definition: branch_random.c:41
SCIP_EXPORT int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:17430
public methods for message output
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
#define BRANCHRULE_DESC
Definition: branch_random.c:42
#define SCIP_Real
Definition: def.h:163
public methods for message handling
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
#define DEFAULT_INITSEED
Definition: branch_random.c:47
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:192
static SCIP_DECL_BRANCHCOPY(branchCopyRandom)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
SCIP_EXPORT SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17442