Scippy

SCIP

Solving Constraint Integer Programs

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