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 2002-2022 Zuse Institute Berlin */
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
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])) ||
112 
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 */
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 */
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 */
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 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
static SCIP_DECL_BRANCHFREE(branchFreeRandom)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
#define BRANCHRULE_MAXDEPTH
Definition: branch_random.c:53
public methods for SCIP parameter handling
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
public methods for memory management
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17699
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17975
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:57
static SCIP_DECL_BRANCHEXECEXT(branchExecextRandom)
random variable branching rule
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:897
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:201
static SCIP_DECL_BRANCHEXECLP(branchExeclpRandom)
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
static SCIP_DECL_BRANCHINIT(branchInitRandom)
#define FALSE
Definition: def.h:96
#define TRUE
Definition: def.h:95
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
static SCIP_DECL_BRANCHEXECPS(branchExecpsRandom)
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_random.c:54
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10012
public methods for branching rules
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:116
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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:511
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPdebugMsg
Definition: scip_message.h:78
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:83
public methods for numerical tolerances
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
public methods for the branch-and-bound tree
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12226
static SCIP_DECL_BRANCHEXIT(branchExitRandom)
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1050
#define SCIPerrorMessage
Definition: pub_message.h:64
#define BRANCHRULE_PRIORITY
Definition: branch_random.c:52
SCIP_RETCODE SCIPincludeBranchruleRandom(SCIP *scip)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17260
#define NULL
Definition: lpi_spx1.cpp:164
#define SCIP_CALL(x)
Definition: def.h:393
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1126
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
public data structures and miscellaneous methods
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:265
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:17687
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:71
public methods for random numbers
#define BRANCHRULE_NAME
Definition: branch_random.c:50
public methods for message output
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17379
#define BRANCHRULE_DESC
Definition: branch_random.c:51
#define SCIP_Real
Definition: def.h:186
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:185
public methods for message handling
#define DEFAULT_INITSEED
Definition: branch_random.c:56
static SCIP_DECL_BRANCHCOPY(branchCopyRandom)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17985
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17589