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-2024 Zuse Institute Berlin (ZIB) */
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"
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 */
59struct 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 */
70static
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
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) */
139static
140SCIP_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] */
154static
155SCIP_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) */
173static
174SCIP_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 */
190static
191SCIP_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 */
206static
207SCIP_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 */
244static
245SCIP_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 */
311static
312SCIP_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 */
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}
#define BRANCHRULE_DESC
Definition: branch_random.c:51
static SCIP_DECL_BRANCHFREE(branchFreeRandom)
#define BRANCHRULE_PRIORITY
Definition: branch_random.c:52
static SCIP_DECL_BRANCHEXECEXT(branchExecextRandom)
static SCIP_DECL_BRANCHEXECLP(branchExeclpRandom)
#define BRANCHRULE_NAME
Definition: branch_random.c:50
static SCIP_DECL_BRANCHEXECPS(branchExecpsRandom)
static SCIP_DECL_BRANCHCOPY(branchCopyRandom)
#define DEFAULT_INITSEED
Definition: branch_random.c:56
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
static SCIP_DECL_BRANCHEXIT(branchExitRandom)
static SCIP_DECL_BRANCHINIT(branchInitRandom)
#define BRANCHRULE_MAXDEPTH
Definition: branch_random.c:53
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_random.c:54
random variable branching rule
#define NULL
Definition: def.h:267
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPincludeBranchruleRandom(SCIP *scip)
#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
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:265
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:201
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
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_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:185
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
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
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:897
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 SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1050
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12218
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17858
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:17846
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
public methods for branching rules
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
public methods for problem variables
public methods for branching rule plugins and branching
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for random numbers
public methods for the branch-and-bound tree
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:57
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_BRANCHED
Definition: type_result.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54