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