Scippy

SCIP

Solving Constraint Integer Programs

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