1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file scip_branch.c
17 * @ingroup OTHER_CFILES
18 * @brief public methods for branching rule plugins and branching
19 * @author Tobias Achterberg
20 * @author Timo Berthold
21 * @author Gerald Gamrath
22 * @author Leona Gottwald
23 * @author Stefan Heinz
24 * @author Gregor Hendel
25 * @author Thorsten Koch
26 * @author Alexander Martin
27 * @author Marc Pfetsch
28 * @author Michael Winkler
29 * @author Kati Wolter
30 *
31 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
32 */
33
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36 #include "scip/branch.h"
37 #include "scip/debug.h"
38 #include "scip/lp.h"
39 #include "scip/pub_message.h"
40 #include "scip/pub_var.h"
41 #include "scip/var.h"
42 #include "scip/scip_branch.h"
43 #include "scip/scip_numerics.h"
44 #include "scip/set.h"
45 #include "scip/struct_mem.h"
46 #include "scip/struct_primal.h"
47 #include "scip/struct_scip.h"
48 #include "scip/struct_set.h"
49 #include "scip/struct_var.h"
50 #include "scip/tree.h"
51
52
53 /** creates a branching rule and includes it in SCIP
54 *
55 * @note method has all branching rule callbacks as arguments and is thus changed every time a new
56 * callback is added in future releases; consider using SCIPincludeBranchruleBasic() and setter functions
57 * if you seek for a method which is less likely to change in future releases
58 */
59 SCIP_RETCODE SCIPincludeBranchrule(
60 SCIP* scip, /**< SCIP data structure */
61 const char* name, /**< name of branching rule */
62 const char* desc, /**< description of branching rule */
63 int priority, /**< priority of the branching rule */
64 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
65 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
66 * compared to best node's dual bound for applying branching rule
67 * (0.0: only on current best node, 1.0: on all nodes) */
68 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
69 SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */
70 SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */
71 SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */
72 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
73 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
74 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
75 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external candidates */
76 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
77 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
78 )
79 {
80 SCIP_BRANCHRULE* branchrule;
81
82 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchrule", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
83
84 /* check whether branching rule is already present */
85 if( SCIPfindBranchrule(scip, name) != NULL )
86 {
87 SCIPerrorMessage("branching rule <%s> already included.\n", name);
88 return SCIP_INVALIDDATA;
89 }
90
91 SCIP_CALL( SCIPbranchruleCreate(&branchrule, scip->set, scip->messagehdlr, scip->mem->setmem,
92 name, desc, priority, maxdepth,
93 maxbounddist, branchcopy, branchfree, branchinit, branchexit, branchinitsol, branchexitsol,
94 branchexeclp, branchexecext, branchexecps, branchruledata) );
95 SCIP_CALL( SCIPsetIncludeBranchrule(scip->set, branchrule) );
96
97 return SCIP_OKAY;
98 }
99
100 /** creates a branching rule and includes it in SCIP. All non-fundamental (or optional) callbacks will be set to NULL.
101 * Optional callbacks can be set via specific setter functions, see SCIPsetBranchruleInit(), SCIPsetBranchruleExit(),
102 * SCIPsetBranchruleCopy(), SCIPsetBranchruleFree(), SCIPsetBranchruleInitsol(), SCIPsetBranchruleExitsol(),
103 * SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecExt(), and SCIPsetBranchruleExecPs().
104 *
105 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBranchrule() instead
106 */
107 SCIP_RETCODE SCIPincludeBranchruleBasic(
108 SCIP* scip, /**< SCIP data structure */
109 SCIP_BRANCHRULE** branchruleptr, /**< pointer to branching rule, or NULL */
110 const char* name, /**< name of branching rule */
111 const char* desc, /**< description of branching rule */
112 int priority, /**< priority of the branching rule */
113 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
114 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
115 * compared to best node's dual bound for applying branching rule
116 * (0.0: only on current best node, 1.0: on all nodes) */
117 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
118 )
119 {
120 SCIP_BRANCHRULE* branchrule;
121
122 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchruleBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
123
124 /* check whether branching rule is already present */
125 if( SCIPfindBranchrule(scip, name) != NULL )
126 {
127 SCIPerrorMessage("branching rule <%s> already included.\n", name);
128 return SCIP_INVALIDDATA;
129 }
130
131 SCIP_CALL( SCIPbranchruleCreate(&branchrule, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, maxdepth,
132 maxbounddist, NULL, NULL, NULL, NULL, NULL, NULL,
133 NULL, NULL, NULL, branchruledata) );
134
135 SCIP_CALL( SCIPsetIncludeBranchrule(scip->set, branchrule) );
136
137 if( branchruleptr != NULL )
138 *branchruleptr = branchrule;
139
140 return SCIP_OKAY;
141 }
142
143 /** sets copy method of branching rule */
144 SCIP_RETCODE SCIPsetBranchruleCopy(
145 SCIP* scip, /**< SCIP data structure */
146 SCIP_BRANCHRULE* branchrule, /**< branching rule */
147 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
148 )
149 {
150 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
151
152 assert(branchrule != NULL);
153
154 SCIPbranchruleSetCopy(branchrule, branchcopy);
155
156 return SCIP_OKAY;
157 }
158
159 /** sets destructor method of branching rule */
160 SCIP_RETCODE SCIPsetBranchruleFree(
161 SCIP* scip, /**< SCIP data structure */
162 SCIP_BRANCHRULE* branchrule, /**< branching rule */
163 SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */
164 )
165 {
166 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
167
168 assert(branchrule != NULL);
169
170 SCIPbranchruleSetFree(branchrule, branchfree);
171
172 return SCIP_OKAY;
173 }
174
175 /** sets initialization method of branching rule */
176 SCIP_RETCODE SCIPsetBranchruleInit(
177 SCIP* scip, /**< SCIP data structure */
178 SCIP_BRANCHRULE* branchrule, /**< branching rule */
179 SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */
180 )
181 {
182 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
183
184 assert(branchrule != NULL);
185
186 SCIPbranchruleSetInit(branchrule, branchinit);
187
188 return SCIP_OKAY;
189 }
190
191 /** sets deinitialization method of branching rule */
192 SCIP_RETCODE SCIPsetBranchruleExit(
193 SCIP* scip, /**< SCIP data structure */
194 SCIP_BRANCHRULE* branchrule, /**< branching rule */
195 SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */
196 )
197 {
198 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
199
200 assert(branchrule != NULL);
201
202 SCIPbranchruleSetExit(branchrule, branchexit);
203
204 return SCIP_OKAY;
205 }
206
207 /** sets solving process initialization method of branching rule */
208 SCIP_RETCODE SCIPsetBranchruleInitsol(
209 SCIP* scip, /**< SCIP data structure */
210 SCIP_BRANCHRULE* branchrule, /**< branching rule */
211 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
212 )
213 {
214 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
215
216 assert(branchrule != NULL);
217
218 SCIPbranchruleSetInitsol(branchrule, branchinitsol);
219
220 return SCIP_OKAY;
221 }
222
223 /** sets solving process deinitialization method of branching rule */
224 SCIP_RETCODE SCIPsetBranchruleExitsol(
225 SCIP* scip, /**< SCIP data structure */
226 SCIP_BRANCHRULE* branchrule, /**< branching rule */
227 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
228 )
229 {
230 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
231
232 assert(branchrule != NULL);
233
234 SCIPbranchruleSetExitsol(branchrule, branchexitsol);
235
236 return SCIP_OKAY;
237 }
238
239 /** sets branching execution method for fractional LP solutions */
240 SCIP_RETCODE SCIPsetBranchruleExecLp(
241 SCIP* scip, /**< SCIP data structure */
242 SCIP_BRANCHRULE* branchrule, /**< branching rule */
243 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
244 )
245 {
246 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecLp", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
247
248 assert(branchrule != NULL);
249
250 SCIPbranchruleSetExecLp(branchrule, branchexeclp);
251
252 return SCIP_OKAY;
253 }
254
255 /** sets branching execution method for external candidates */
256 SCIP_RETCODE SCIPsetBranchruleExecExt(
257 SCIP* scip, /**< SCIP data structure */
258 SCIP_BRANCHRULE* branchrule, /**< branching rule */
259 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
260 )
261 {
262 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecExt", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
263
264 assert(branchrule != NULL);
265
266 SCIPbranchruleSetExecExt(branchrule, branchexecext);
267
268 return SCIP_OKAY;
269 }
270
271 /** sets branching execution method for not completely fixed pseudo solutions */
272 SCIP_RETCODE SCIPsetBranchruleExecPs(
273 SCIP* scip, /**< SCIP data structure */
274 SCIP_BRANCHRULE* branchrule, /**< branching rule */
275 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
276 )
277 {
278 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecPs", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
279
280 assert(branchrule != NULL);
281
282 SCIPbranchruleSetExecPs(branchrule, branchexecps);
283
284 return SCIP_OKAY;
285 }
286
287 /** returns the branching rule of the given name, or NULL if not existing */
288 SCIP_BRANCHRULE* SCIPfindBranchrule(
289 SCIP* scip, /**< SCIP data structure */
290 const char* name /**< name of branching rule */
291 )
292 {
293 assert(scip != NULL);
294 assert(scip->set != NULL);
295 assert(name != NULL);
296
297 SCIPsetSortBranchrules(scip->set);
298
|
(1) Event null_return: |
Calling "SCIPsetFindBranchrule" which might return null. [details] |
|
(2) Event return_null_fn: |
Returning the return value of "SCIPsetFindBranchrule", which might be null. |
299 return SCIPsetFindBranchrule(scip->set, name);
300 }
301
302 /** returns the array of currently available branching rules */
303 SCIP_BRANCHRULE** SCIPgetBranchrules(
304 SCIP* scip /**< SCIP data structure */
305 )
306 {
307 assert(scip != NULL);
308 assert(scip->set != NULL);
309
310 return scip->set->branchrules;
311 }
312
313 /** returns the number of currently available branching rules */
314 int SCIPgetNBranchrules(
315 SCIP* scip /**< SCIP data structure */
316 )
317 {
318 assert(scip != NULL);
319 assert(scip->set != NULL);
320
321 return scip->set->nbranchrules;
322 }
323
324 /** sets the priority of a branching rule */
325 SCIP_RETCODE SCIPsetBranchrulePriority(
326 SCIP* scip, /**< SCIP data structure */
327 SCIP_BRANCHRULE* branchrule, /**< branching rule */
328 int priority /**< new priority of the branching rule */
329 )
330 {
331 assert(scip != NULL);
332 assert(scip->set != NULL);
333
334 SCIPbranchruleSetPriority(branchrule, scip->set, priority);
335
336 return SCIP_OKAY;
337 }
338
339 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
340 SCIP_RETCODE SCIPsetBranchruleMaxdepth(
341 SCIP* scip, /**< SCIP data structure */
342 SCIP_BRANCHRULE* branchrule, /**< branching rule */
343 int maxdepth /**< new maxdepth of the branching rule */
344 )
345 {
346 assert(scip != NULL);
347 assert(scip->set != NULL);
348
349 SCIPbranchruleSetMaxdepth(branchrule, maxdepth);
350
351 return SCIP_OKAY;
352 }
353
354 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
355 SCIP_RETCODE SCIPsetBranchruleMaxbounddist(
356 SCIP* scip, /**< SCIP data structure */
357 SCIP_BRANCHRULE* branchrule, /**< branching rule */
358 SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */
359 )
360 {
361 assert(scip != NULL);
362 assert(scip->set != NULL);
363
364 SCIPbranchruleSetMaxbounddist(branchrule, maxbounddist);
365
366 return SCIP_OKAY;
367 }
368
369 /** gets branching candidates for LP solution branching (fractional variables) along with solution values,
370 * fractionalities, and number of branching candidates; The number of branching candidates does NOT
371 * account for fractional implicit integer variables which should not be used for branching decisions.
372 *
373 * Fractional implicit integer variables are stored at the positions *nlpcands to *nlpcands + *nfracimplvars - 1
374 *
375 * branching rules should always select the branching candidate among the first npriolpcands of the candidate
376 * list
377 *
378 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
379 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
380 *
381 * @pre This method can be called if @p scip is in one of the following stages:
382 * - \ref SCIP_STAGE_SOLVING
383 *
384 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
385 */
386 SCIP_RETCODE SCIPgetLPBranchCands(
387 SCIP* scip, /**< SCIP data structure */
388 SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */
389 SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
390 SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
391 int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */
392 int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
393 int* nfracimplvars /**< pointer to store the number of fractional implicit integer variables, or NULL */
394 )
395 {
396 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
397
398 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
399 {
400 SCIPerrorMessage("LP not solved to optimality - solstat=%d\n", SCIPlpGetSolstat(scip->lp));
401 return SCIP_INVALIDDATA;
402 }
403
404 SCIP_CALL( SCIPbranchcandGetLPCands(scip->branchcand, scip->set, scip->stat, scip->lp,
405 lpcands, lpcandssol, lpcandsfrac, nlpcands, npriolpcands, nfracimplvars) );
406
407 return SCIP_OKAY;
408 }
409
410 /** gets number of branching candidates for LP solution branching (number of fractional variables)
411 *
412 * @return the number of branching candidates for LP solution branching (number of fractional variables).
413 *
414 * @pre This method can be called if @p scip is in one of the following stages:
415 * - \ref SCIP_STAGE_SOLVING
416 *
417 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
418 */
419 int SCIPgetNLPBranchCands(
420 SCIP* scip /**< SCIP data structure */
421 )
422 {
423 SCIP_RETCODE retcode;
424 int nlpcands;
425
426 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
427
428 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
429 {
430 SCIPerrorMessage("LP not solved to optimality\n");
431 SCIPABORT();
432 return 0; /*lint !e527*/
433 }
434
435 retcode = SCIPbranchcandGetLPCands(scip->branchcand, scip->set, scip->stat, scip->lp,
436 NULL, NULL, NULL, &nlpcands, NULL, NULL);
437
438 if( retcode != SCIP_OKAY )
439 {
440 SCIPerrorMessage("Error <%d> during computation of the number of LP branching candidates\n", retcode);
441 SCIPABORT();
442 return 0; /*lint !e527*/
443 }
444
445 return nlpcands;
446 }
447
448 /** gets number of branching candidates with maximal priority for LP solution branching
449 *
450 * @return the number of branching candidates with maximal priority for LP solution branching.
451 *
452 * @pre This method can be called if @p scip is in one of the following stages:
453 * - \ref SCIP_STAGE_SOLVING
454 *
455 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
456 */
457 int SCIPgetNPrioLPBranchCands(
458 SCIP* scip /**< SCIP data structure */
459 )
460 {
461 SCIP_RETCODE retcode;
462 int npriolpcands;
463
464 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
465
466 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
467 {
468 SCIPerrorMessage("LP not solved to optimality\n");
469 SCIPABORT();
470 return 0; /*lint !e527*/
471 }
472
473 retcode = SCIPbranchcandGetLPCands(scip->branchcand, scip->set, scip->stat, scip->lp,
474 NULL, NULL, NULL, NULL, &npriolpcands, NULL);
475
476 if( retcode != SCIP_OKAY )
477 {
478 SCIPerrorMessage("Error <%d> during computation of the number of LP branching candidates with maximal priority\n", retcode);
479 SCIPABORT();
480 return 0; /*lint !e527*/
481 }
482
483 return npriolpcands;
484 }
485
486 /** gets external branching candidates along with solution values, scores, and number of branching candidates;
487 * these branching candidates can be used by relaxations or nonlinear constraint handlers;
488 * branching rules should always select the branching candidate among the first nprioexterncands of the candidate
489 * list
490 *
491 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
492 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
493 *
494 * @pre This method can be called if @p scip is in one of the following stages:
495 * - \ref SCIP_STAGE_SOLVING
496 *
497 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
498 *
499 * @note Candidate variables with maximal priority are ordered: binaries first, then integers, implicit integers and
500 * continuous last.
501 */
502 SCIP_RETCODE SCIPgetExternBranchCands(
503 SCIP* scip, /**< SCIP data structure */
504 SCIP_VAR*** externcands, /**< pointer to store the array of extern branching candidates, or NULL */
505 SCIP_Real** externcandssol, /**< pointer to store the array of extern candidate solution values, or NULL */
506 SCIP_Real** externcandsscore, /**< pointer to store the array of extern candidate scores, or NULL */
507 int* nexterncands, /**< pointer to store the number of extern branching candidates, or NULL */
508 int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
509 int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
510 int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
511 int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
512 * or NULL */
513 )
514 {
515 assert(scip != NULL);
516
517 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
518
519 SCIP_CALL( SCIPbranchcandGetExternCands(scip->branchcand, externcands, externcandssol, externcandsscore, nexterncands,
520 nprioexterncands, nprioexternbins, nprioexternints, nprioexternimpls) );
521
522 return SCIP_OKAY;
523 }
524
525 /** gets number of external branching candidates
526 *
527 * @return the number of external branching candidates.
528 *
529 * @pre This method can be called if @p scip is in one of the following stages:
530 * - \ref SCIP_STAGE_SOLVING
531 *
532 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
533 */
534 int SCIPgetNExternBranchCands(
535 SCIP* scip /**< SCIP data structure */
536 )
537 {
538 assert(scip != NULL);
539
540 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
541
542 return SCIPbranchcandGetNExternCands(scip->branchcand);
543 }
544
545 /** gets number of external branching candidates with maximal branch priority
546 *
547 * @return the number of external branching candidates with maximal branch priority.
548 *
549 * @pre This method can be called if @p scip is in one of the following stages:
550 * - \ref SCIP_STAGE_SOLVING
551 *
552 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
553 */
554 int SCIPgetNPrioExternBranchCands(
555 SCIP* scip /**< SCIP data structure */
556 )
557 {
558 assert(scip != NULL);
559
560 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
561
562 return SCIPbranchcandGetNPrioExternCands(scip->branchcand);
563 }
564
565 /** gets number of binary external branching candidates with maximal branch priority
566 *
567 * @return the number of binary external branching candidates with maximal branch priority.
568 *
569 * @pre This method can be called if @p scip is in one of the following stages:
570 * - \ref SCIP_STAGE_SOLVING
571 *
572 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
573 */
574 int SCIPgetNPrioExternBranchBins(
575 SCIP* scip /**< SCIP data structure */
576 )
577 {
578 assert(scip != NULL);
579
580 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
581
582 return SCIPbranchcandGetNPrioExternBins(scip->branchcand);
583 }
584
585 /** gets number of integer external branching candidates with maximal branch priority
586 *
587 * @return the number of integer external branching candidates with maximal branch priority.
588 *
589 * @pre This method can be called if @p scip is in one of the following stages:
590 * - \ref SCIP_STAGE_SOLVING
591 *
592 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
593 */
594 int SCIPgetNPrioExternBranchInts(
595 SCIP* scip /**< SCIP data structure */
596 )
597 {
598 assert(scip != NULL);
599
600 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
601
602 return SCIPbranchcandGetNPrioExternInts(scip->branchcand);
603 }
604
605 /** gets number of implicit integer external branching candidates with maximal branch priority
606 *
607 * @return the number of implicit integer external branching candidates with maximal branch priority.
608 *
609 * @pre This method can be called if @p scip is in one of the following stages:
610 * - \ref SCIP_STAGE_SOLVING
611 *
612 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
613 */
614 int SCIPgetNPrioExternBranchImpls(
615 SCIP* scip /**< SCIP data structure */
616 )
617 {
618 assert(scip != NULL);
619
620 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
621
622 return SCIPbranchcandGetNPrioExternImpls(scip->branchcand);
623 }
624
625 /** gets number of continuous external branching candidates with maximal branch priority
626 *
627 * @return the number of continuous external branching candidates with maximal branch priority.
628 *
629 * @pre This method can be called if @p scip is in one of the following stages:
630 * - \ref SCIP_STAGE_SOLVING
631 *
632 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
633 */
634 int SCIPgetNPrioExternBranchConts(
635 SCIP* scip /**< SCIP data structure */
636 )
637 {
638 assert(scip != NULL);
639
640 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchConts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
641
642 return SCIPbranchcandGetNPrioExternConts(scip->branchcand);
643 }
644
645 /** insert variable, its score and its solution value into the external branching candidate storage
646 * the relative difference of the current lower and upper bounds of a continuous variable must be at least epsilon
647 *
648 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
649 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
650 *
651 * @pre This method can be called if @p scip is in one of the following stages:
652 * - \ref SCIP_STAGE_SOLVING
653 *
654 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
655 */
656 SCIP_RETCODE SCIPaddExternBranchCand(
657 SCIP* scip, /**< SCIP data structure */
658 SCIP_VAR* var, /**< variable to insert */
659 SCIP_Real score, /**< score of external candidate, e.g. infeasibility */
660 SCIP_Real solval /**< value of the variable in the current solution */
661 )
662 {
663 assert(scip != NULL);
664 assert(var->scip == scip);
665
666 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
667
668 SCIP_CALL( SCIPbranchcandAddExternCand(scip->branchcand, scip->set, var, score, solval) );
669
670 return SCIP_OKAY;
671 }
672
673 /** removes all external candidates from the storage for external branching
674 *
675 * @pre This method can be called if @p scip is in one of the following stages:
676 * - \ref SCIP_STAGE_SOLVING
677 *
678 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
679 */
680 void SCIPclearExternBranchCands(
681 SCIP* scip /**< SCIP data structure */
682 )
683 {
684 assert(scip != NULL);
685
686 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPclearExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
687
688 SCIPbranchcandClearExternCands(scip->branchcand);
689 }
690
691 /** checks whether the given variable is contained in the candidate storage for external branching
692 *
693 * @return whether the given variable is contained in the candidate storage for external branching.
694 *
695 * @pre This method can be called if @p scip is in one of the following stages:
696 * - \ref SCIP_STAGE_SOLVING
697 *
698 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
699 */
700 SCIP_Bool SCIPcontainsExternBranchCand(
701 SCIP* scip, /**< SCIP data structure */
702 SCIP_VAR* var /**< variable to look for */
703 )
704 {
705 assert(scip != NULL);
706 assert(var->scip == scip);
707
708 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcontainsExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
709
710 return SCIPbranchcandContainsExternCand(scip->branchcand, var);
711 }
712
713 /** gets branching candidates for pseudo solution branching (non-fixed variables) along with the number of candidates
714 *
715 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
716 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
717 *
718 * @pre This method can be called if @p scip is in one of the following stages:
719 * - \ref SCIP_STAGE_PRESOLVING
720 * - \ref SCIP_STAGE_SOLVING
721 *
722 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
723 */
724 SCIP_RETCODE SCIPgetPseudoBranchCands(
725 SCIP* scip, /**< SCIP data structure */
726 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
727 int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */
728 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
729 )
730 {
731 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
732
733 SCIP_CALL( SCIPbranchcandGetPseudoCands(scip->branchcand, scip->set, scip->transprob,
734 pseudocands, npseudocands, npriopseudocands) );
735
736 return SCIP_OKAY;
737 }
738
739 /** gets number of branching candidates for pseudo solution branching (non-fixed variables)
740 *
741 * @return the number branching candidates for pseudo solution branching (non-fixed variables).
742 *
743 * @pre This method can be called if @p scip is in one of the following stages:
744 * - \ref SCIP_STAGE_PRESOLVING
745 * - \ref SCIP_STAGE_SOLVING
746 *
747 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
748 */
749 int SCIPgetNPseudoBranchCands(
750 SCIP* scip /**< SCIP data structure */
751 )
752 {
753 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
754
755 return SCIPbranchcandGetNPseudoCands(scip->branchcand);
756 }
757
758 /** gets number of branching candidates with maximal branch priority for pseudo solution branching
759 *
760 * @return the number of branching candidates with maximal branch priority for pseudo solution branching.
761 *
762 * @pre This method can be called if @p scip is in one of the following stages:
763 * - \ref SCIP_STAGE_PRESOLVING
764 * - \ref SCIP_STAGE_SOLVING
765 *
766 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
767 */
768 int SCIPgetNPrioPseudoBranchCands(
769 SCIP* scip /**< SCIP data structure */
770 )
771 {
772 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
773
774 return SCIPbranchcandGetNPrioPseudoCands(scip->branchcand);
775 }
776
777 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching
778 *
779 * @return the number of binary branching candidates with maximal branch priority for pseudo solution branching.
780 *
781 * @pre This method can be called if @p scip is in one of the following stages:
782 * - \ref SCIP_STAGE_SOLVING
783 *
784 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
785 */
786 int SCIPgetNPrioPseudoBranchBins(
787 SCIP* scip /**< SCIP data structure */
788 )
789 {
790 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
791
792 return SCIPbranchcandGetNPrioPseudoBins(scip->branchcand);
793 }
794
795 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching
796 *
797 * @return the number of integer branching candidates with maximal branch priority for pseudo solution branching.
798 *
799 * @pre This method can be called if @p scip is in one of the following stages:
800 * - \ref SCIP_STAGE_SOLVING
801 *
802 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
803 */
804 int SCIPgetNPrioPseudoBranchInts(
805 SCIP* scip /**< SCIP data structure */
806 )
807 {
808 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
809
810 return SCIPbranchcandGetNPrioPseudoInts(scip->branchcand);
811 }
812
813 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching
814 *
815 * @return the number of implicit integer branching candidates with maximal branch priority for pseudo solution branching.
816 *
817 * @pre This method can be called if @p scip is in one of the following stages:
818 * - \ref SCIP_STAGE_SOLVING
819 *
820 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
821 */
822 int SCIPgetNPrioPseudoBranchImpls(
823 SCIP* scip /**< SCIP data structure */
824 )
825 {
826 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
827
828 return SCIPbranchcandGetNPrioPseudoImpls(scip->branchcand);
829 }
830
831 /** calculates the branching score out of the gain predictions for a binary branching
832 *
833 * @return the branching score out of the gain predictions for a binary branching.
834 *
835 * @pre This method can be called if @p scip is in one of the following stages:
836 * - \ref SCIP_STAGE_SOLVING
837 *
838 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
839 */
840 SCIP_Real SCIPgetBranchScore(
841 SCIP* scip, /**< SCIP data structure */
842 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
843 SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */
844 SCIP_Real upgain /**< prediction of objective gain for rounding upwards */
845 )
846 {
847 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScore", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
848
849 assert( var == NULL || var->scip == scip );
850
851 return SCIPbranchGetScore(scip->set, var, downgain, upgain);
852 }
853
854 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children
855 *
856 * @return the branching score out of the gain predictions for a branching with arbitrary many children.
857 *
858 * @pre This method can be called if @p scip is in one of the following stages:
859 * - \ref SCIP_STAGE_SOLVING
860 *
861 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
862 */
863 SCIP_Real SCIPgetBranchScoreMultiple(
864 SCIP* scip, /**< SCIP data structure */
865 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
866 int nchildren, /**< number of children that the branching will create */
867 SCIP_Real* gains /**< prediction of objective gain for each child */
868 )
869 {
870 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScoreMultiple", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
871
872 assert( var->scip == scip );
873
874 return SCIPbranchGetScoreMultiple(scip->set, var, nchildren, gains);
875 }
876
877 /** computes a branching point for a continuous or discrete variable
878 *
879 * @see SCIPbranchGetBranchingPoint
880 *
881 * @return the branching point for a continuous or discrete variable.
882 *
883 * @pre This method can be called if @p scip is in one of the following stages:
884 * - \ref SCIP_STAGE_SOLVING
885 *
886 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
887 */
888 SCIP_Real SCIPgetBranchingPoint(
889 SCIP* scip, /**< SCIP data structure */
890 SCIP_VAR* var, /**< variable, of which the branching point should be computed */
891 SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */
892 )
893 {
894 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchingPoint", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
895
896 assert( var->scip == scip );
897
898 return SCIPbranchGetBranchingPoint(scip->set, scip->tree, var, suggestion);
899 }
900
901 /** calculates the node selection priority for moving the given variable's LP value to the given target value;
902 * this node selection priority can be given to the SCIPcreateChild() call
903 *
904 * @return the node selection priority for moving the given variable's LP value to the given target value.
905 *
906 * @pre This method can be called if @p scip is in one of the following stages:
907 * - \ref SCIP_STAGE_SOLVING
908 *
909 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
910 */
911 SCIP_Real SCIPcalcNodeselPriority(
912 SCIP* scip, /**< SCIP data structure */
913 SCIP_VAR* var, /**< variable on which the branching is applied */
914 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed;
915 * fixed should only be used, when both bounds changed
916 */
917 SCIP_Real targetvalue /**< new value of the variable in the child node */
918 )
919 {
920 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcNodeselPriority", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
921
922 assert( var->scip == scip );
923
924 return SCIPtreeCalcNodeselPriority(scip->tree, scip->set, scip->stat, var, branchdir, targetvalue);
925 }
926
927 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
928 * branching; this estimate can be given to the SCIPcreateChild() call
929 *
930 * @return the estimate for the objective of the best feasible solution contained in the subtree after applying the given
931 * branching.
932 *
933 * @pre This method can be called if @p scip is in one of the following stages:
934 * - \ref SCIP_STAGE_SOLVING
935 *
936 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
937 */
938 SCIP_Real SCIPcalcChildEstimate(
939 SCIP* scip, /**< SCIP data structure */
940 SCIP_VAR* var, /**< variable on which the branching is applied */
941 SCIP_Real targetvalue /**< new value of the variable in the child node */
942 )
943 {
944 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcChildEstimate", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
945
946 assert( var->scip == scip );
947
948 return SCIPtreeCalcChildEstimate(scip->tree, scip->set, scip->stat, var, targetvalue);
949 }
950
951 /** calculates the increase of the estimate for the objective of the best feasible solution contained in the subtree
952 * after applying the given branching
953 *
954 * @return the increase of the estimate for the objective of the best feasible solution contained in the subtree after
955 * applying the given branching.
956 *
957 * @pre This method can be called if @p scip is in one of the following stages:
958 * - \ref SCIP_STAGE_SOLVING
959 *
960 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
961 */
962 SCIP_Real SCIPcalcChildEstimateIncrease(
963 SCIP* scip, /**< SCIP data structure */
964 SCIP_VAR* var, /**< variable on which the branching is applied */
965 SCIP_Real varsol, /**< solution value of variable */
966 SCIP_Real targetvalue /**< new value of the variable in the child node */
967 )
968 {
969 SCIP_Real estimateinc;
970
971 assert(scip != NULL);
972 assert(var != NULL);
973
974 /* compute increase above parent node's (i.e., focus node's) estimate value */
975 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
976 estimateinc = SCIPvarGetPseudocost(var, scip->stat, targetvalue - varsol);
977 else
978 {
979 SCIP_Real pscdown;
980 SCIP_Real pscup;
981
982 /* calculate estimate based on pseudo costs:
983 * estimate = lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j})
984 * = parentestimate - min{f_b * pscdown_b, (1-f_b) * pscup_b} + (targetvalue-oldvalue)*{pscdown_b or pscup_b}
985 */
986 pscdown = SCIPvarGetPseudocost(var, scip->stat, SCIPsetFeasFloor(scip->set, varsol) - varsol);
987 pscup = SCIPvarGetPseudocost(var, scip->stat, SCIPsetFeasCeil(scip->set, varsol) - varsol);
988 estimateinc = SCIPvarGetPseudocost(var, scip->stat, targetvalue - varsol) - MIN(pscdown, pscup);
989 }
990
991 /* due to rounding errors estimateinc might be slightly negative */
992 if( estimateinc > 0.0 )
993 estimateinc = 0.0;
994
995 return estimateinc;
996 }
997
998 /** creates a child node of the focus node
999 *
1000 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1001 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1002 *
1003 * @pre This method can be called if @p scip is in one of the following stages:
1004 * - \ref SCIP_STAGE_SOLVING
1005 *
1006 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1007 */
1008 SCIP_RETCODE SCIPcreateChild(
1009 SCIP* scip, /**< SCIP data structure */
1010 SCIP_NODE** node, /**< pointer to node data structure */
1011 SCIP_Real nodeselprio, /**< node selection priority of new node */
1012 SCIP_Real estimate /**< estimate for(transformed) objective value of best feasible solution in subtree */
1013 )
1014 {
1015 assert(node != NULL);
1016
1017 SCIP_CALL( SCIPcheckStage(scip, "SCIPcreateChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1018
1019 SCIP_CALL( SCIPnodeCreateChild(node, scip->mem->probmem, scip->set, scip->stat, scip->tree, nodeselprio, estimate) );
1020
1021 return SCIP_OKAY;
1022 }
1023
1024 /** branches on a non-continuous variable v using the current LP or pseudo solution;
1025 * if solution value x' is fractional, two child nodes will be created
1026 * (x <= floor(x'), x >= ceil(x')),
1027 * if solution value is integral, the x' is equal to lower or upper bound of the branching
1028 * variable and the bounds of v are finite, then two child nodes will be created
1029 * (x <= x'', x >= x''+1 with x'' = floor((lb + ub)/2)),
1030 * otherwise (up to) three child nodes will be created
1031 * (x <= x'-1, x == x', x >= x'+1)
1032 *
1033 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1034 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1035 *
1036 * @pre This method can be called if @p scip is in one of the following stages:
1037 * - \ref SCIP_STAGE_SOLVING
1038 *
1039 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1040 */
1041 SCIP_RETCODE SCIPbranchVar(
1042 SCIP* scip, /**< SCIP data structure */
1043 SCIP_VAR* var, /**< variable to branch on */
1044 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
1045 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
1046 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
1047 )
1048 {
1049 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVar", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1050
1051 assert( var->scip == scip );
1052
1053 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
1054 {
1055 SCIPerrorMessage("cannot branch on continuous variable <%s>\n", SCIPvarGetName(var));
1056 return SCIP_INVALIDDATA;
1057 }
1058
1059 if( SCIPsetIsEQ(scip->set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1060 {
1061 SCIPerrorMessage("cannot branch on variable <%s> with fixed domain [%.15g,%.15g]\n",
1062 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
1063 return SCIP_INVALIDDATA;
1064 }
1065
1066 SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1067 scip->lp, scip->branchcand, scip->eventqueue, var, SCIP_INVALID, downchild, eqchild, upchild) );
1068
1069 return SCIP_OKAY;
1070 }
1071
1072 /** branches a variable x using a given domain hole; two child nodes (x <= left, x >= right) are created
1073 *
1074 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1075 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1076 *
1077 * @pre This method can be called if @p scip is in one of the following stages:
1078 * - \ref SCIP_STAGE_SOLVING
1079 *
1080 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1081 */
1082 SCIP_RETCODE SCIPbranchVarHole(
1083 SCIP* scip, /**< SCIP data structure */
1084 SCIP_VAR* var, /**< variable to branch on */
1085 SCIP_Real left, /**< left side of the domain hole */
1086 SCIP_Real right, /**< right side of the domain hole */
1087 SCIP_NODE** downchild, /**< pointer to return the left child (x <= left), or NULL */
1088 SCIP_NODE** upchild /**< pointer to return the right child (x >= right), or NULL */
1089 )
1090 {
1091 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarHole", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1092
1093 assert( var->scip == scip );
1094
1095 SCIP_CALL( SCIPtreeBranchVarHole(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
1096 scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, left, right, downchild, upchild) );
1097
1098 return SCIP_OKAY;
1099 }
1100
1101 /** branches on a variable x using a given value x';
1102 * for continuous variables with relative domain width larger epsilon, x' must not be one of the bounds;
1103 * two child nodes (x <= x', x >= x') are created;
1104 * for integer variables, if solution value x' is fractional, two child nodes are created
1105 * (x <= floor(x'), x >= ceil(x')),
1106 * if x' is integral, three child nodes are created
1107 * (x <= x'-1, x == x', x >= x'+1)
1108 *
1109 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1110 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1111 *
1112 * @pre This method can be called if @p scip is in one of the following stages:
1113 * - \ref SCIP_STAGE_SOLVING
1114 *
1115 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1116 */
1117 SCIP_RETCODE SCIPbranchVarVal(
1118 SCIP* scip, /**< SCIP data structure */
1119 SCIP_VAR* var, /**< variable to branch on */
1120 SCIP_Real val, /**< value to branch on */
1121 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
1122 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
1123 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
1124 )
1125 {
1126 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarVal", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1127
1128 assert( var->scip == scip );
1129
1130 /* A continuous variable will be fixed if SCIPisRelEQ(lb,ub) is true. Otherwise, the given branching value should be
1131 * such that its value is not equal to one of the bounds. We assert this by requiring that it is at least eps/2 away
1132 * from each bound. The 2.1 is there, because ub-lb may be in (eps, 2*eps], in which case there is no way to choose a
1133 * branching value that is at least eps away from both bounds. However, if the variable bounds are below/above
1134 * -/+infinity * 2.1, then SCIPisLT will give an assert, so we omit the check in this case.
1135 */
1136 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ||
1137 SCIPisRelEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ||
1138 SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) ||
1139 (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) );
1140
1141 if( SCIPsetIsEQ(scip->set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1142 {
1143 SCIPerrorMessage("cannot branch on variable <%s> with fixed domain [%.15g,%.15g]\n",
1144 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
1145 return SCIP_INVALIDDATA;
1146 }
1147
1148 SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1149 scip->lp, scip->branchcand, scip->eventqueue, var, val, downchild, eqchild, upchild) );
1150
1151 return SCIP_OKAY;
1152 }
1153
1154 /** n-ary branching on a variable x using a given value
1155 *
1156 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
1157 * The branching value is selected as in SCIPbranchVarVal().
1158 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
1159 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
1160 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
1161 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance
1162 * from the first nodes.
1163 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
1164 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
1165 *
1166 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
1167 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
1168 * results in a ternary branching where the branching variable is mostly fixed in the middle child.
1169 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
1170 * (except for one child if the branching value is not in the middle).
1171 *
1172 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1173 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1174 *
1175 * @pre This method can be called if @p scip is in one of the following stages:
1176 * - \ref SCIP_STAGE_SOLVING
1177 *
1178 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1179 */
1180 SCIP_RETCODE SCIPbranchVarValNary(
1181 SCIP* scip, /**< SCIP data structure */
1182 SCIP_VAR* var, /**< variable to branch on */
1183 SCIP_Real val, /**< value to branch on */
1184 int n, /**< attempted number of children to be created, must be >= 2 */
1185 SCIP_Real minwidth, /**< minimal domain width in children */
1186 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
1187 int* nchildren /**< pointer to store number of created children, or NULL */
1188 )
1189 {
1190 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarValNary", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1191
1192 assert( var->scip == scip );
1193
1194 /* see comment in SCIPbranchVarVal */
1195 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ||
1196 SCIPisRelEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ||
1197 SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) ||
1198 (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) );
1199
1200 if( SCIPsetIsEQ(scip->set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1201 {
1202 SCIPerrorMessage("cannot branch on variable <%s> with fixed domain [%.15g,%.15g]\n",
1203 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
1204 return SCIP_INVALIDDATA;
1205 }
1206
1207 SCIP_CALL( SCIPtreeBranchVarNary(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
1208 scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, val, n, minwidth, widthfactor, nchildren) );
1209
1210 return SCIP_OKAY;
1211 }
1212
1213 /** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
1214 * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
1215 * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
1216 *
1217 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1218 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1219 *
1220 * @pre This method can be called if @p scip is in one of the following stages:
1221 * - \ref SCIP_STAGE_SOLVING
1222 *
1223 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1224 */
1225 SCIP_RETCODE SCIPbranchLP(
1226 SCIP* scip, /**< SCIP data structure */
1227 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
1228 )
1229 {
1230 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1231
1232 SCIP_CALL( SCIPbranchExecLP(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1233 scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound,
1234 TRUE, result) );
1235
1236 return SCIP_OKAY;
1237 }
1238
1239 /** calls branching rules to branch on a external candidates; if no such candidates exist, the result is SCIP_DIDNOTRUN
1240 *
1241 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1242 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1243 *
1244 * @pre This method can be called if @p scip is in one of the following stages:
1245 * - \ref SCIP_STAGE_SOLVING
1246 *
1247 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1248 */
1249 SCIP_RETCODE SCIPbranchExtern(
1250 SCIP* scip, /**< SCIP data structure */
1251 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
1252 )
1253 {
1254 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchExtern", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1255
1256 SCIP_CALL( SCIPbranchExecExtern(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1257 scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound,
1258 TRUE, result) );
1259
1260 return SCIP_OKAY;
1261 }
1262
1263 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN
1264 *
1265 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1266 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1267 *
1268 * @pre This method can be called if @p scip is in one of the following stages:
1269 * - \ref SCIP_STAGE_SOLVING
1270 *
1271 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1272 */
1273 SCIP_RETCODE SCIPbranchPseudo(
1274 SCIP* scip, /**< SCIP data structure */
1275 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
1276 )
1277 {
1278 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchPseudo", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1279
1280 SCIP_CALL( SCIPbranchExecPseudo(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1281 scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound, TRUE, result) );
1282
1283 return SCIP_OKAY;
1284 }
1285