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