Scippy

SCIP

Solving Constraint Integer Programs

scip_branch.h
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.h
26 * @ingroup PUBLICCOREAPI
27 * @brief public methods for branching rule plugins and branching
28 * @author Tobias Achterberg
29 * @author Timo Berthold
30 * @author Thorsten Koch
31 * @author Alexander Martin
32 * @author Marc Pfetsch
33 * @author Kati Wolter
34 * @author Gregor Hendel
35 * @author Leona Gottwald
36 */
37
38/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39
40#ifndef __SCIP_SCIP_BRANCH_H__
41#define __SCIP_SCIP_BRANCH_H__
42
43
44#include "scip/def.h"
45#include "scip/type_branch.h"
46#include "scip/type_history.h"
47#include "scip/type_result.h"
48#include "scip/type_retcode.h"
49#include "scip/type_scip.h"
50#include "scip/type_tree.h"
51#include "scip/type_var.h"
52
53#ifdef __cplusplus
54extern "C" {
55#endif
56
57/**@addtogroup PublicBranchRuleMethods
58 *
59 * @{
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 */
68SCIP_EXPORT
70 SCIP* scip, /**< SCIP data structure */
71 const char* name, /**< name of branching rule */
72 const char* desc, /**< description of branching rule */
73 int priority, /**< priority of the branching rule */
74 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
75 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
76 * compared to best node's dual bound for applying branching rule
77 * (0.0: only on current best node, 1.0: on all nodes) */
78 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
79 SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */
80 SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */
81 SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */
82 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
83 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
84 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
85 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external candidates */
86 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
87 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
88 );
89
90/** creates a branching rule and includes it in SCIP. All non-fundamental (or optional) callbacks will be set to NULL.
91 * Optional callbacks can be set via specific setter functions, see SCIPsetBranchruleInit(), SCIPsetBranchruleExit(),
92 * SCIPsetBranchruleCopy(), SCIPsetBranchruleFree(), SCIPsetBranchruleInitsol(), SCIPsetBranchruleExitsol(),
93 * SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecExt(), and SCIPsetBranchruleExecPs().
94 *
95 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBranchrule() instead
96 */
97SCIP_EXPORT
99 SCIP* scip, /**< SCIP data structure */
100 SCIP_BRANCHRULE** branchruleptr, /**< pointer to branching rule, or NULL */
101 const char* name, /**< name of branching rule */
102 const char* desc, /**< description of branching rule */
103 int priority, /**< priority of the branching rule */
104 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
105 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
106 * compared to best node's dual bound for applying branching rule
107 * (0.0: only on current best node, 1.0: on all nodes) */
108 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
109 );
110
111/** sets copy method of branching rule */
112SCIP_EXPORT
114 SCIP* scip, /**< SCIP data structure */
115 SCIP_BRANCHRULE* branchrule, /**< branching rule */
116 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
117 );
118
119/** sets destructor method of branching rule */
120SCIP_EXPORT
122 SCIP* scip, /**< SCIP data structure */
123 SCIP_BRANCHRULE* branchrule, /**< branching rule */
124 SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */
125 );
126
127/** sets initialization method of branching rule */
128SCIP_EXPORT
130 SCIP* scip, /**< SCIP data structure */
131 SCIP_BRANCHRULE* branchrule, /**< branching rule */
132 SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */
133 );
134
135/** sets deinitialization method of branching rule */
136SCIP_EXPORT
138 SCIP* scip, /**< SCIP data structure */
139 SCIP_BRANCHRULE* branchrule, /**< branching rule */
140 SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */
141 );
142
143/** sets solving process initialization method of branching rule */
144SCIP_EXPORT
146 SCIP* scip, /**< SCIP data structure */
147 SCIP_BRANCHRULE* branchrule, /**< branching rule */
148 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
149 );
150
151/** sets solving process deinitialization method of branching rule */
152SCIP_EXPORT
154 SCIP* scip, /**< SCIP data structure */
155 SCIP_BRANCHRULE* branchrule, /**< branching rule */
156 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
157 );
158
159/** sets branching execution method for fractional LP solutions */
160SCIP_EXPORT
162 SCIP* scip, /**< SCIP data structure */
163 SCIP_BRANCHRULE* branchrule, /**< branching rule */
164 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
165 );
166
167/** sets branching execution method for external candidates */
168SCIP_EXPORT
170 SCIP* scip, /**< SCIP data structure */
171 SCIP_BRANCHRULE* branchrule, /**< branching rule */
172 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
173 );
174
175/** sets branching execution method for not completely fixed pseudo solutions */
176SCIP_EXPORT
178 SCIP* scip, /**< SCIP data structure */
179 SCIP_BRANCHRULE* branchrule, /**< branching rule */
180 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
181 );
182
183/** returns the branching rule of the given name, or NULL if not existing */
184SCIP_EXPORT
186 SCIP* scip, /**< SCIP data structure */
187 const char* name /**< name of branching rule */
188 );
189
190/** returns the array of currently available branching rules */
191SCIP_EXPORT
193 SCIP* scip /**< SCIP data structure */
194 );
195
196/** returns the number of currently available branching rules */
197SCIP_EXPORT
199 SCIP* scip /**< SCIP data structure */
200 );
201
202/** sets the priority of a branching rule */
203SCIP_EXPORT
205 SCIP* scip, /**< SCIP data structure */
206 SCIP_BRANCHRULE* branchrule, /**< branching rule */
207 int priority /**< new priority of the branching rule */
208 );
209
210/** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
211SCIP_EXPORT
213 SCIP* scip, /**< SCIP data structure */
214 SCIP_BRANCHRULE* branchrule, /**< branching rule */
215 int maxdepth /**< new maxdepth of the branching rule */
216 );
217
218/** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
219SCIP_EXPORT
221 SCIP* scip, /**< SCIP data structure */
222 SCIP_BRANCHRULE* branchrule, /**< branching rule */
223 SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */
224 );
225
226/** @} */
227
228/**@addtogroup PublicBranchingMethods
229 *
230 * @{
231 */
232
233/** gets branching candidates for LP solution branching (fractional variables) along with solution values,
234 * fractionalities, and number of branching candidates; The number of branching candidates does NOT
235 * account for fractional implicit integer variables which should not be used for branching decisions.
236 *
237 * Fractional implicit integer variables are stored at the positions *nlpcands to *nlpcands + *nfracimplvars - 1
238 *
239 * branching rules should always select the branching candidate among the first npriolpcands of the candidate
240 * list
241 *
242 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
243 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
244 *
245 * @pre This method can be called if @p scip is in one of the following stages:
246 * - \ref SCIP_STAGE_SOLVING
247 *
248 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
249 */
250SCIP_EXPORT
252 SCIP* scip, /**< SCIP data structure */
253 SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */
254 SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
255 SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
256 int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */
257 int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
258 int* nfracimplvars /**< pointer to store the number of fractional implicit integer variables, or NULL */
259 );
260
261/** gets number of branching candidates for LP solution branching (number of fractional variables)
262 *
263 * @return the number of branching candidates for LP solution branching (number of fractional variables).
264 *
265 * @pre This method can be called if @p scip is in one of the following stages:
266 * - \ref SCIP_STAGE_SOLVING
267 *
268 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
269 */
270SCIP_EXPORT
272 SCIP* scip /**< SCIP data structure */
273 );
274
275/** gets number of branching candidates with maximal priority for LP solution branching
276 *
277 * @return the number of branching candidates with maximal priority for LP solution branching.
278 *
279 * @pre This method can be called if @p scip is in one of the following stages:
280 * - \ref SCIP_STAGE_SOLVING
281 *
282 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
283 */
284SCIP_EXPORT
286 SCIP* scip /**< SCIP data structure */
287 );
288
289/** gets external branching candidates along with solution values, scores, and number of branching candidates;
290 * these branching candidates can be used by relaxations or nonlinear constraint handlers;
291 * branching rules should always select the branching candidate among the first nprioexterncands of the candidate
292 * list
293 *
294 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
295 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
296 *
297 * @pre This method can be called if @p scip is in one of the following stages:
298 * - \ref SCIP_STAGE_SOLVING
299 *
300 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
301 *
302 * @note Candidate variables with maximal priority are ordered: binaries first, then integers, implicit integers and
303 * continuous last.
304 */
305SCIP_EXPORT
307 SCIP* scip, /**< SCIP data structure */
308 SCIP_VAR*** externcands, /**< pointer to store the array of extern branching candidates, or NULL */
309 SCIP_Real** externcandssol, /**< pointer to store the array of extern candidate solution values, or NULL */
310 SCIP_Real** externcandsscore, /**< pointer to store the array of extern candidate scores, or NULL */
311 int* nexterncands, /**< pointer to store the number of extern branching candidates, or NULL */
312 int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
313 int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
314 int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
315 int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
316 * or NULL */
317 );
318
319/** gets number of external branching candidates
320 *
321 * @return the number of external branching candidates.
322 *
323 * @pre This method can be called if @p scip is in one of the following stages:
324 * - \ref SCIP_STAGE_SOLVING
325 *
326 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
327 */
328SCIP_EXPORT
330 SCIP* scip /**< SCIP data structure */
331 );
332
333/** gets number of external branching candidates with maximal branch priority
334 *
335 * @return the number of external branching candidates with maximal branch priority.
336 *
337 * @pre This method can be called if @p scip is in one of the following stages:
338 * - \ref SCIP_STAGE_SOLVING
339 *
340 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
341 */
342SCIP_EXPORT
344 SCIP* scip /**< SCIP data structure */
345 );
346
347/** gets number of binary external branching candidates with maximal branch priority
348 *
349 * @return the number of binary external branching candidates with maximal branch priority.
350 *
351 * @pre This method can be called if @p scip is in one of the following stages:
352 * - \ref SCIP_STAGE_SOLVING
353 *
354 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
355 */
356SCIP_EXPORT
358 SCIP* scip /**< SCIP data structure */
359 );
360
361/** gets number of integer external branching candidates with maximal branch priority
362 *
363 * @return the number of integer external branching candidates with maximal branch priority.
364 *
365 * @pre This method can be called if @p scip is in one of the following stages:
366 * - \ref SCIP_STAGE_SOLVING
367 *
368 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
369 */
370SCIP_EXPORT
372 SCIP* scip /**< SCIP data structure */
373 );
374
375/** gets number of implicit integer external branching candidates with maximal branch priority
376 *
377 * @return the number of implicit integer external branching candidates with maximal branch priority.
378 *
379 * @pre This method can be called if @p scip is in one of the following stages:
380 * - \ref SCIP_STAGE_SOLVING
381 *
382 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
383 */
384SCIP_EXPORT
386 SCIP* scip /**< SCIP data structure */
387 );
388
389/** gets number of continuous external branching candidates with maximal branch priority
390 *
391 * @return the number of continuous external branching candidates with maximal branch priority.
392 *
393 * @pre This method can be called if @p scip is in one of the following stages:
394 * - \ref SCIP_STAGE_SOLVING
395 *
396 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
397 */
398SCIP_EXPORT
400 SCIP* scip /**< SCIP data structure */
401 );
402
403/** insert variable, its score and its solution value into the external branching candidate storage
404 * the relative difference of the current lower and upper bounds of a continuous variable must be at least epsilon
405 *
406 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
407 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
408 *
409 * @pre This method can be called if @p scip is in one of the following stages:
410 * - \ref SCIP_STAGE_SOLVING
411 *
412 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
413 */
414SCIP_EXPORT
416 SCIP* scip, /**< SCIP data structure */
417 SCIP_VAR* var, /**< variable to insert */
418 SCIP_Real score, /**< score of external candidate, e.g. infeasibility */
419 SCIP_Real solval /**< value of the variable in the current solution */
420 );
421
422/** removes all external candidates from the storage for external branching
423 *
424 * @pre This method can be called if @p scip is in one of the following stages:
425 * - \ref SCIP_STAGE_SOLVING
426 *
427 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
428 */
429SCIP_EXPORT
431 SCIP* scip /**< SCIP data structure */
432 );
433
434/** checks whether the given variable is contained in the candidate storage for external branching
435 *
436 * @return whether the given variable is contained in the candidate storage for external branching.
437 *
438 * @pre This method can be called if @p scip is in one of the following stages:
439 * - \ref SCIP_STAGE_SOLVING
440 *
441 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
442 */
443SCIP_EXPORT
445 SCIP* scip, /**< SCIP data structure */
446 SCIP_VAR* var /**< variable to look for */
447 );
448
449/** gets branching candidates for pseudo solution branching (non-fixed variables) along with the number of candidates
450 *
451 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
452 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
453 *
454 * @pre This method can be called if @p scip is in one of the following stages:
455 * - \ref SCIP_STAGE_PRESOLVING
456 * - \ref SCIP_STAGE_SOLVING
457 *
458 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
459 */
460SCIP_EXPORT
462 SCIP* scip, /**< SCIP data structure */
463 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
464 int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */
465 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
466 );
467
468/** gets number of branching candidates for pseudo solution branching (non-fixed variables)
469 *
470 * @return the number branching candidates for pseudo solution branching (non-fixed variables).
471 *
472 * @pre This method can be called if @p scip is in one of the following stages:
473 * - \ref SCIP_STAGE_PRESOLVING
474 * - \ref SCIP_STAGE_SOLVING
475 *
476 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
477 */
478SCIP_EXPORT
480 SCIP* scip /**< SCIP data structure */
481 );
482
483/** gets number of branching candidates with maximal branch priority for pseudo solution branching
484 *
485 * @return the number of branching candidates with maximal branch priority for pseudo solution branching.
486 *
487 * @pre This method can be called if @p scip is in one of the following stages:
488 * - \ref SCIP_STAGE_PRESOLVING
489 * - \ref SCIP_STAGE_SOLVING
490 *
491 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
492 */
493SCIP_EXPORT
495 SCIP* scip /**< SCIP data structure */
496 );
497
498/** gets number of binary branching candidates with maximal branch priority for pseudo solution branching
499 *
500 * @return the number of binary branching candidates with maximal branch priority for pseudo solution branching.
501 *
502 * @pre This method can be called if @p scip is in one of the following stages:
503 * - \ref SCIP_STAGE_SOLVING
504 *
505 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
506 */
507SCIP_EXPORT
509 SCIP* scip /**< SCIP data structure */
510 );
511
512/** gets number of integer branching candidates with maximal branch priority for pseudo solution branching
513 *
514 * @return the number of integer branching candidates with maximal branch priority for pseudo solution branching.
515 *
516 * @pre This method can be called if @p scip is in one of the following stages:
517 * - \ref SCIP_STAGE_SOLVING
518 *
519 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
520 */
521SCIP_EXPORT
523 SCIP* scip /**< SCIP data structure */
524 );
525
526/** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching
527 *
528 * @return the number of implicit integer branching candidates with maximal branch priority for pseudo solution branching.
529 *
530 * @pre This method can be called if @p scip is in one of the following stages:
531 * - \ref SCIP_STAGE_SOLVING
532 *
533 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
534 */
535SCIP_EXPORT
537 SCIP* scip /**< SCIP data structure */
538 );
539
540/** calculates the branching score out of the gain predictions for a binary branching
541 *
542 * @return the branching score out of the gain predictions for a binary branching.
543 *
544 * @pre This method can be called if @p scip is in one of the following stages:
545 * - \ref SCIP_STAGE_SOLVING
546 *
547 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
548 */
549SCIP_EXPORT
551 SCIP* scip, /**< SCIP data structure */
552 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
553 SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */
554 SCIP_Real upgain /**< prediction of objective gain for rounding upwards */
555 );
556
557/** calculates the branching score out of the gain predictions for a branching with arbitrary many children
558 *
559 * @return the branching score out of the gain predictions for a branching with arbitrary many children.
560 *
561 * @pre This method can be called if @p scip is in one of the following stages:
562 * - \ref SCIP_STAGE_SOLVING
563 *
564 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
565 */
566SCIP_EXPORT
568 SCIP* scip, /**< SCIP data structure */
569 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
570 int nchildren, /**< number of children that the branching will create */
571 SCIP_Real* gains /**< prediction of objective gain for each child */
572 );
573
574/** computes a branching point for a continuous or discrete variable
575 *
576 * @see SCIPbranchGetBranchingPoint
577 *
578 * @return the branching point for a continuous or discrete variable.
579 *
580 * @pre This method can be called if @p scip is in one of the following stages:
581 * - \ref SCIP_STAGE_SOLVING
582 *
583 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
584 */
585SCIP_EXPORT
587 SCIP* scip, /**< SCIP data structure */
588 SCIP_VAR* var, /**< variable, of which the branching point should be computed */
589 SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */
590 );
591
592/** calculates the node selection priority for moving the given variable's LP value to the given target value;
593 * this node selection priority can be given to the SCIPcreateChild() call
594 *
595 * @return the node selection priority for moving the given variable's LP value to the given target value.
596 *
597 * @pre This method can be called if @p scip is in one of the following stages:
598 * - \ref SCIP_STAGE_SOLVING
599 *
600 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
601 */
602SCIP_EXPORT
604 SCIP* scip, /**< SCIP data structure */
605 SCIP_VAR* var, /**< variable on which the branching is applied */
606 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed;
607 * fixed should only be used, when both bounds changed
608 */
609 SCIP_Real targetvalue /**< new value of the variable in the child node */
610 );
611
612/** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
613 * branching; this estimate can be given to the SCIPcreateChild() call
614 *
615 * @return the estimate for the objective of the best feasible solution contained in the subtree after applying the given
616 * branching.
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 */
623SCIP_EXPORT
625 SCIP* scip, /**< SCIP data structure */
626 SCIP_VAR* var, /**< variable on which the branching is applied */
627 SCIP_Real targetvalue /**< new value of the variable in the child node */
628 );
629
630/** calculates the increase of the estimate for the objective of the best feasible solution contained in the subtree
631 * after applying the given branching
632 *
633 * @return the increase of the estimate for the objective of the best feasible solution contained in the subtree after
634 * applying the given branching.
635 *
636 * @pre This method can be called if @p scip is in one of the following stages:
637 * - \ref SCIP_STAGE_SOLVING
638 *
639 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
640 */
641SCIP_EXPORT
643 SCIP* scip, /**< SCIP data structure */
644 SCIP_VAR* var, /**< variable on which the branching is applied */
645 SCIP_Real varsol, /**< solution value of variable */
646 SCIP_Real targetvalue /**< new value of the variable in the child node */
647 );
648
649/** creates a child node of the focus node
650 *
651 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
652 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
653 *
654 * @pre This method can be called if @p scip is in one of the following stages:
655 * - \ref SCIP_STAGE_SOLVING
656 *
657 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
658 */
659SCIP_EXPORT
661 SCIP* scip, /**< SCIP data structure */
662 SCIP_NODE** node, /**< pointer to node data structure */
663 SCIP_Real nodeselprio, /**< node selection priority of new node */
664 SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */
665 );
666
667/** branches on a non-continuous variable v using the current LP or pseudo solution;
668 * if solution value x' is fractional, two child nodes will be created
669 * (x <= floor(x'), x >= ceil(x')),
670 * if solution value is integral, the x' is equal to lower or upper bound of the branching
671 * variable and the bounds of v are finite, then two child nodes will be created
672 * (x <= x'', x >= x''+1 with x'' = floor((lb + ub)/2)),
673 * otherwise (up to) three child nodes will be created
674 * (x <= x'-1, x == x', x >= x'+1)
675 *
676 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
677 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
678 *
679 * @pre This method can be called if @p scip is in one of the following stages:
680 * - \ref SCIP_STAGE_SOLVING
681 *
682 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
683 */
684SCIP_EXPORT
686 SCIP* scip, /**< SCIP data structure */
687 SCIP_VAR* var, /**< variable to branch on */
688 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
689 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
690 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
691 );
692
693/** branches a variable x using a given domain hole; two child nodes (x <= left, x >= right) are created
694 *
695 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
696 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
697 *
698 * @pre This method can be called if @p scip is in one of the following stages:
699 * - \ref SCIP_STAGE_SOLVING
700 *
701 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
702 */
703SCIP_EXPORT
705 SCIP* scip, /**< SCIP data structure */
706 SCIP_VAR* var, /**< variable to branch on */
707 SCIP_Real left, /**< left side of the domain hole */
708 SCIP_Real right, /**< right side of the domain hole */
709 SCIP_NODE** downchild, /**< pointer to return the left child (x <= left), or NULL */
710 SCIP_NODE** upchild /**< pointer to return the right child (x >= right), or NULL */
711 );
712
713/** branches on a variable x using a given value x';
714 * for continuous variables with relative domain width larger epsilon, x' must not be one of the bounds;
715 * two child nodes (x <= x', x >= x') are created;
716 * for integer variables, if solution value x' is fractional, two child nodes are created
717 * (x <= floor(x'), x >= ceil(x')),
718 * if x' is integral, three child nodes are created
719 * (x <= x'-1, x == x', x >= x'+1)
720 *
721 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
722 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
723 *
724 * @pre This method can be called if @p scip is in one of the following stages:
725 * - \ref SCIP_STAGE_SOLVING
726 *
727 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
728 */
729SCIP_EXPORT
731 SCIP* scip, /**< SCIP data structure */
732 SCIP_VAR* var, /**< variable to branch on */
733 SCIP_Real val, /**< value to branch on */
734 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
735 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
736 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
737 );
738
739/** n-ary branching on a variable x using a given value
740 *
741 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
742 * The branching value is selected as in SCIPbranchVarVal().
743 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
744 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
745 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
746 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance
747 * from the first nodes.
748 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
749 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
750 *
751 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
752 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
753 * results in a ternary branching where the branching variable is mostly fixed in the middle child.
754 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
755 * (except for one child if the branching value is not in the middle).
756 *
757 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
758 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
759 *
760 * @pre This method can be called if @p scip is in one of the following stages:
761 * - \ref SCIP_STAGE_SOLVING
762 *
763 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
764 */
765SCIP_EXPORT
767 SCIP* scip, /**< SCIP data structure */
768 SCIP_VAR* var, /**< variable to branch on */
769 SCIP_Real val, /**< value to branch on */
770 int n, /**< attempted number of children to be created, must be >= 2 */
771 SCIP_Real minwidth, /**< minimal domain width in children */
772 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
773 int* nchildren /**< pointer to store number of created children, or NULL */
774 );
775
776/** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
777 * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
778 * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
779 *
780 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
781 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
782 *
783 * @pre This method can be called if @p scip is in one of the following stages:
784 * - \ref SCIP_STAGE_SOLVING
785 *
786 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
787 */
788SCIP_EXPORT
790 SCIP* scip, /**< SCIP data structure */
791 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
792 );
793
794/** calls branching rules to branch on a external candidates; if no such candidates exist, the result is SCIP_DIDNOTRUN
795 *
796 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
797 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
798 *
799 * @pre This method can be called if @p scip is in one of the following stages:
800 * - \ref SCIP_STAGE_SOLVING
801 *
802 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
803 */
804SCIP_EXPORT
806 SCIP* scip, /**< SCIP data structure */
807 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
808 );
809
810/** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN
811 *
812 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
813 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
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 */
820SCIP_EXPORT
822 SCIP* scip, /**< SCIP data structure */
823 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
824 );
825
826/**@} */
827
828#ifdef __cplusplus
829}
830#endif
831
832#endif
common defines and data types used in all packages of SCIP
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
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
type definitions for branching rules
#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
type definitions for branching and inference history
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
result codes for SCIP callback methods
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for SCIP's main datastructure
type definitions for branch and bound tree
type definitions for problem variables