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