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-2019 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 scip.zib.de. */
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 Robert Lion 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 /* In debug mode, we include the SCIP's structure in scip.c, such that no one can access
45  * this structure except the interface methods in scip.c.
46  * In optimized mode, the structure is included in scip.h, because some of the methods
47  * are implemented as defines for performance reasons (e.g. the numerical comparisons).
48  * Additionally, the internal "set.h" is included, such that the defines in set.h are
49  * available in optimized mode.
50  */
51 #ifdef NDEBUG
52 #include "scip/struct_scip.h"
53 #include "scip/struct_stat.h"
54 #include "scip/set.h"
55 #include "scip/tree.h"
56 #include "scip/misc.h"
57 #include "scip/var.h"
58 #include "scip/cons.h"
59 #include "scip/solve.h"
60 #include "scip/debug.h"
61 #endif
62 
63 #ifdef __cplusplus
64 extern "C" {
65 #endif
66 
67 /**@addtogroup PublicBranchRuleMethods
68  *
69  * @{
70  */
71 
72 /** creates a branching rule and includes it in SCIP
73  *
74  * @note method has all branching rule callbacks as arguments and is thus changed every time a new
75  * callback is added in future releases; consider using SCIPincludeBranchruleBasic() and setter functions
76  * if you seek for a method which is less likely to change in future releases
77  */
78 extern
80  SCIP* scip, /**< SCIP data structure */
81  const char* name, /**< name of branching rule */
82  const char* desc, /**< description of branching rule */
83  int priority, /**< priority of the branching rule */
84  int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
85  SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
86  * compared to best node's dual bound for applying branching rule
87  * (0.0: only on current best node, 1.0: on all nodes) */
88  SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
89  SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */
90  SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */
91  SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */
92  SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
93  SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
94  SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
95  SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external candidates */
96  SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
97  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
98  );
99 
100 /** creates a branching rule and includes it in SCIP. All non-fundamental (or optional) callbacks will be set to NULL.
101  * Optional callbacks can be set via specific setter functions, see SCIPsetBranchruleInit(), SCIPsetBranchruleExit(),
102  * SCIPsetBranchruleCopy(), SCIPsetBranchruleFree(), SCIPsetBranchruleInitsol(), SCIPsetBranchruleExitsol(),
103  * SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecExt(), and SCIPsetBranchruleExecPs().
104  *
105  * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBranchrule() instead
106  */
107 extern
109  SCIP* scip, /**< SCIP data structure */
110  SCIP_BRANCHRULE** branchruleptr, /**< pointer to branching rule, or NULL */
111  const char* name, /**< name of branching rule */
112  const char* desc, /**< description of branching rule */
113  int priority, /**< priority of the branching rule */
114  int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
115  SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
116  * compared to best node's dual bound for applying branching rule
117  * (0.0: only on current best node, 1.0: on all nodes) */
118  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
119  );
120 
121 /** sets copy method of branching rule */
122 extern
124  SCIP* scip, /**< SCIP data structure */
125  SCIP_BRANCHRULE* branchrule, /**< branching rule */
126  SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
127  );
128 
129 /** sets destructor method of branching rule */
130 extern
132  SCIP* scip, /**< SCIP data structure */
133  SCIP_BRANCHRULE* branchrule, /**< branching rule */
134  SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */
135  );
136 
137 /** sets initialization method of branching rule */
138 extern
140  SCIP* scip, /**< SCIP data structure */
141  SCIP_BRANCHRULE* branchrule, /**< branching rule */
142  SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */
143  );
144 
145 /** sets deinitialization method of branching rule */
146 extern
148  SCIP* scip, /**< SCIP data structure */
149  SCIP_BRANCHRULE* branchrule, /**< branching rule */
150  SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */
151  );
152 
153 /** sets solving process initialization method of branching rule */
154 extern
156  SCIP* scip, /**< SCIP data structure */
157  SCIP_BRANCHRULE* branchrule, /**< branching rule */
158  SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
159  );
160 
161 /** sets solving process deinitialization method of branching rule */
162 extern
164  SCIP* scip, /**< SCIP data structure */
165  SCIP_BRANCHRULE* branchrule, /**< branching rule */
166  SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
167  );
168 
169 /** sets branching execution method for fractional LP solutions */
170 extern
172  SCIP* scip, /**< SCIP data structure */
173  SCIP_BRANCHRULE* branchrule, /**< branching rule */
174  SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
175  );
176 
177 /** sets branching execution method for external candidates */
178 extern
180  SCIP* scip, /**< SCIP data structure */
181  SCIP_BRANCHRULE* branchrule, /**< branching rule */
182  SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
183  );
184 
185 /** sets branching execution method for not completely fixed pseudo solutions */
186 extern
188  SCIP* scip, /**< SCIP data structure */
189  SCIP_BRANCHRULE* branchrule, /**< branching rule */
190  SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
191  );
192 
193 /** returns the branching rule of the given name, or NULL if not existing */
194 extern
196  SCIP* scip, /**< SCIP data structure */
197  const char* name /**< name of branching rule */
198  );
199 
200 /** returns the array of currently available branching rules */
201 extern
203  SCIP* scip /**< SCIP data structure */
204  );
205 
206 /** returns the number of currently available branching rules */
207 extern
209  SCIP* scip /**< SCIP data structure */
210  );
211 
212 /** sets the priority of a branching rule */
213 extern
215  SCIP* scip, /**< SCIP data structure */
216  SCIP_BRANCHRULE* branchrule, /**< branching rule */
217  int priority /**< new priority of the branching rule */
218  );
219 
220 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
221 extern
223  SCIP* scip, /**< SCIP data structure */
224  SCIP_BRANCHRULE* branchrule, /**< branching rule */
225  int maxdepth /**< new maxdepth of the branching rule */
226  );
227 
228 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
229 extern
231  SCIP* scip, /**< SCIP data structure */
232  SCIP_BRANCHRULE* branchrule, /**< branching rule */
233  SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */
234  );
235 
236 /* @} */
237 
238 /**@addtogroup PublicBranchingMethods
239  *
240  * @{
241  */
242 
243 /** gets branching candidates for LP solution branching (fractional variables) along with solution values,
244  * fractionalities, and number of branching candidates; The number of branching candidates does NOT
245  * account for fractional implicit integer variables which should not be used for branching decisions.
246  *
247  * Fractional implicit integer variables are stored at the positions *nlpcands to *nlpcands + *nfracimplvars - 1
248  *
249  * branching rules should always select the branching candidate among the first npriolpcands of the candidate
250  * list
251  *
252  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
253  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
254  *
255  * @pre This method can be called if @p scip is in one of the following stages:
256  * - \ref SCIP_STAGE_SOLVING
257  *
258  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
259  */
260 extern
262  SCIP* scip, /**< SCIP data structure */
263  SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */
264  SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
265  SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
266  int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */
267  int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
268  int* nfracimplvars /**< pointer to store the number of fractional implicit integer variables, or NULL */
269  );
270 
271 /** gets number of branching candidates for LP solution branching (number of fractional variables)
272  *
273  * @return the number of branching candidates for LP solution branching (number of fractional variables).
274  *
275  * @pre This method can be called if @p scip is in one of the following stages:
276  * - \ref SCIP_STAGE_SOLVING
277  *
278  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
279  */
280 extern
282  SCIP* scip /**< SCIP data structure */
283  );
284 
285 /** gets number of branching candidates with maximal priority for LP solution branching
286  *
287  * @return the number of branching candidates with maximal priority for LP solution branching.
288  *
289  * @pre This method can be called if @p scip is in one of the following stages:
290  * - \ref SCIP_STAGE_SOLVING
291  *
292  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
293  */
294 extern
296  SCIP* scip /**< SCIP data structure */
297  );
298 
299 /** gets external branching candidates along with solution values, scores, and number of branching candidates;
300  * these branching candidates can be used by relaxations or nonlinear constraint handlers;
301  * branching rules should always select the branching candidate among the first nprioexterncands of the candidate
302  * list
303  *
304  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
305  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
306  *
307  * @pre This method can be called if @p scip is in one of the following stages:
308  * - \ref SCIP_STAGE_SOLVING
309  *
310  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
311  *
312  * @note Candidate variables with maximal priority are ordered: binaries first, then integers, implicit integers and
313  * continuous last.
314  */
315 extern
317  SCIP* scip, /**< SCIP data structure */
318  SCIP_VAR*** externcands, /**< pointer to store the array of extern branching candidates, or NULL */
319  SCIP_Real** externcandssol, /**< pointer to store the array of extern candidate solution values, or NULL */
320  SCIP_Real** externcandsscore, /**< pointer to store the array of extern candidate scores, or NULL */
321  int* nexterncands, /**< pointer to store the number of extern branching candidates, or NULL */
322  int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
323  int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
324  int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
325  int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
326  * or NULL */
327  );
328 
329 /** gets number of external branching candidates
330  *
331  * @return the number of external branching candidates.
332  *
333  * @pre This method can be called if @p scip is in one of the following stages:
334  * - \ref SCIP_STAGE_SOLVING
335  *
336  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
337  */
338 extern
340  SCIP* scip /**< SCIP data structure */
341  );
342 
343 /** gets number of external branching candidates with maximal branch priority
344  *
345  * @return the number of external branching candidates with maximal branch priority.
346  *
347  * @pre This method can be called if @p scip is in one of the following stages:
348  * - \ref SCIP_STAGE_SOLVING
349  *
350  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
351  */
352 extern
354  SCIP* scip /**< SCIP data structure */
355  );
356 
357 /** gets number of binary external branching candidates with maximal branch priority
358  *
359  * @return the number of binary external branching candidates with maximal branch priority.
360  *
361  * @pre This method can be called if @p scip is in one of the following stages:
362  * - \ref SCIP_STAGE_SOLVING
363  *
364  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
365  */
366 extern
368  SCIP* scip /**< SCIP data structure */
369  );
370 
371 /** gets number of integer external branching candidates with maximal branch priority
372  *
373  * @return the number of integer external branching candidates with maximal branch priority.
374  *
375  * @pre This method can be called if @p scip is in one of the following stages:
376  * - \ref SCIP_STAGE_SOLVING
377  *
378  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
379  */
380 extern
382  SCIP* scip /**< SCIP data structure */
383  );
384 
385 /** gets number of implicit integer external branching candidates with maximal branch priority
386  *
387  * @return the number of implicit integer external branching candidates with maximal branch priority.
388  *
389  * @pre This method can be called if @p scip is in one of the following stages:
390  * - \ref SCIP_STAGE_SOLVING
391  *
392  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
393  */
394 extern
396  SCIP* scip /**< SCIP data structure */
397  );
398 
399 /** gets number of continuous external branching candidates with maximal branch priority
400  *
401  * @return the number of continuous external branching candidates with maximal branch priority.
402  *
403  * @pre This method can be called if @p scip is in one of the following stages:
404  * - \ref SCIP_STAGE_SOLVING
405  *
406  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
407  */
408 extern
410  SCIP* scip /**< SCIP data structure */
411  );
412 
413 /** insert variable, its score and its solution value into the external branching candidate storage
414  * the relative difference of the current lower and upper bounds of a continuous variable must be at least epsilon
415  *
416  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
417  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
418  *
419  * @pre This method can be called if @p scip is in one of the following stages:
420  * - \ref SCIP_STAGE_SOLVING
421  *
422  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
423  */
424 extern
426  SCIP* scip, /**< SCIP data structure */
427  SCIP_VAR* var, /**< variable to insert */
428  SCIP_Real score, /**< score of external candidate, e.g. infeasibility */
429  SCIP_Real solval /**< value of the variable in the current solution */
430  );
431 
432 /** removes all external candidates from the storage for external branching
433  *
434  * @pre This method can be called if @p scip is in one of the following stages:
435  * - \ref SCIP_STAGE_SOLVING
436  *
437  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
438  */
439 extern
441  SCIP* scip /**< SCIP data structure */
442  );
443 
444 /** checks whether the given variable is contained in the candidate storage for external branching
445  *
446  * @return whether the given variable is contained in the candidate storage for external branching.
447  *
448  * @pre This method can be called if @p scip is in one of the following stages:
449  * - \ref SCIP_STAGE_SOLVING
450  *
451  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
452  */
453 extern
455  SCIP* scip, /**< SCIP data structure */
456  SCIP_VAR* var /**< variable to look for */
457  );
458 
459 /** gets branching candidates for pseudo solution branching (non-fixed variables) along with the number of candidates
460  *
461  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
462  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
463  *
464  * @pre This method can be called if @p scip is in one of the following stages:
465  * - \ref SCIP_STAGE_PRESOLVING
466  * - \ref SCIP_STAGE_SOLVING
467  *
468  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
469  */
470 extern
472  SCIP* scip, /**< SCIP data structure */
473  SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
474  int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */
475  int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
476  );
477 
478 /** gets number of branching candidates for pseudo solution branching (non-fixed variables)
479  *
480  * @return the number branching candidates for pseudo solution branching (non-fixed variables).
481  *
482  * @pre This method can be called if @p scip is in one of the following stages:
483  * - \ref SCIP_STAGE_PRESOLVING
484  * - \ref SCIP_STAGE_SOLVING
485  *
486  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
487  */
488 extern
490  SCIP* scip /**< SCIP data structure */
491  );
492 
493 /** gets number of branching candidates with maximal branch priority for pseudo solution branching
494  *
495  * @return the number of branching candidates with maximal branch priority for pseudo solution branching.
496  *
497  * @pre This method can be called if @p scip is in one of the following stages:
498  * - \ref SCIP_STAGE_PRESOLVING
499  * - \ref SCIP_STAGE_SOLVING
500  *
501  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
502  */
503 extern
505  SCIP* scip /**< SCIP data structure */
506  );
507 
508 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching
509  *
510  * @return the number of binary branching candidates with maximal branch priority for pseudo solution branching.
511  *
512  * @pre This method can be called if @p scip is in one of the following stages:
513  * - \ref SCIP_STAGE_SOLVING
514  *
515  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
516  */
517 extern
519  SCIP* scip /**< SCIP data structure */
520  );
521 
522 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching
523  *
524  * @return the number of integer branching candidates with maximal branch priority for pseudo solution branching.
525  *
526  * @pre This method can be called if @p scip is in one of the following stages:
527  * - \ref SCIP_STAGE_SOLVING
528  *
529  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
530  */
531 extern
533  SCIP* scip /**< SCIP data structure */
534  );
535 
536 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching
537  *
538  * @return the number of implicit integer branching candidates with maximal branch priority for pseudo solution branching.
539  *
540  * @pre This method can be called if @p scip is in one of the following stages:
541  * - \ref SCIP_STAGE_SOLVING
542  *
543  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
544  */
545 extern
547  SCIP* scip /**< SCIP data structure */
548  );
549 
550 /** calculates the branching score out of the gain predictions for a binary branching
551  *
552  * @return the branching score out of the gain predictions for a binary branching.
553  *
554  * @pre This method can be called if @p scip is in one of the following stages:
555  * - \ref SCIP_STAGE_SOLVING
556  *
557  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
558  */
559 extern
561  SCIP* scip, /**< SCIP data structure */
562  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
563  SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */
564  SCIP_Real upgain /**< prediction of objective gain for rounding upwards */
565  );
566 
567 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children
568  *
569  * @return the branching score out of the gain predictions for a branching with arbitrary many children.
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  */
576 extern
578  SCIP* scip, /**< SCIP data structure */
579  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
580  int nchildren, /**< number of children that the branching will create */
581  SCIP_Real* gains /**< prediction of objective gain for each child */
582  );
583 
584 /** computes a branching point for a continuous or discrete variable
585  *
586  * @see SCIPbranchGetBranchingPoint
587  *
588  * @return the branching point for a continuous or discrete variable.
589  *
590  * @pre This method can be called if @p scip is in one of the following stages:
591  * - \ref SCIP_STAGE_SOLVING
592  *
593  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
594  */
595 extern
597  SCIP* scip, /**< SCIP data structure */
598  SCIP_VAR* var, /**< variable, of which the branching point should be computed */
599  SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */
600  );
601 
602 /** calculates the node selection priority for moving the given variable's LP value to the given target value;
603  * this node selection priority can be given to the SCIPcreateChild() call
604  *
605  * @return the node selection priority for moving the given variable's LP value to the given target value.
606  *
607  * @pre This method can be called if @p scip is in one of the following stages:
608  * - \ref SCIP_STAGE_SOLVING
609  *
610  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
611  */
612 extern
614  SCIP* scip, /**< SCIP data structure */
615  SCIP_VAR* var, /**< variable on which the branching is applied */
616  SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed;
617  * fixed should only be used, when both bounds changed
618  */
619  SCIP_Real targetvalue /**< new value of the variable in the child node */
620  );
621 
622 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
623  * branching; this estimate can be given to the SCIPcreateChild() call
624  *
625  * @return the estimate for the objective of the best feasible solution contained in the subtree after applying the given
626  * branching.
627  *
628  * @pre This method can be called if @p scip is in one of the following stages:
629  * - \ref SCIP_STAGE_SOLVING
630  *
631  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
632  */
633 extern
635  SCIP* scip, /**< SCIP data structure */
636  SCIP_VAR* var, /**< variable on which the branching is applied */
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  */
650 extern
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  */
675 extern
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  */
694 extern
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  */
720 extern
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  */
756 extern
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  */
779 extern
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  */
795 extern
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  */
811 extern
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_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:384
int SCIPgetNPrioPseudoBranchBins(SCIP *scip)
Definition: scip_branch.c:784
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:57
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:270
internal methods for branch and bound tree
SCIP_RETCODE SCIPbranchVarHole(SCIP *scip, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1033
#define SCIP_DECL_BRANCHEXECPS(x)
Definition: type_branch.h:161
int SCIPgetNPrioPseudoBranchImpls(SCIP *scip)
Definition: scip_branch.c:820
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:747
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
SCIP_RETCODE SCIPsetBranchruleInitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: scip_branch.c:206
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:886
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:190
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:158
#define SCIP_DECL_BRANCHFREE(x)
Definition: type_branch.h:60
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:1131
void SCIPclearExternBranchCands(SCIP *scip)
Definition: scip_branch.c:678
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:142
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip_branch.c:861
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:286
int SCIPgetNPrioPseudoBranchInts(SCIP *scip)
Definition: scip_branch.c:802
#define SCIP_DECL_BRANCHEXECEXT(x)
Definition: type_branch.h:140
type definitions for return codes for SCIP methods
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:105
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:500
#define SCIP_DECL_BRANCHEXITSOL(x)
Definition: type_branch.h:98
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:417
int SCIPgetNPrioExternBranchImpls(SCIP *scip)
Definition: scip_branch.c:612
type definitions for branching rules
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:238
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:838
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
int SCIPgetNPrioLPBranchCands(SCIP *scip)
Definition: scip_branch.c:455
#define SCIP_DECL_BRANCHINIT(x)
Definition: type_branch.h:68
#define SCIP_DECL_BRANCHCOPY(x)
Definition: type_branch.h:52
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:992
type definitions for SCIP&#39;s main datastructure
#define SCIP_DECL_BRANCHINITSOL(x)
Definition: type_branch.h:87
#define SCIP_DECL_BRANCHEXECLP(x)
Definition: type_branch.h:119
SCIP_RETCODE SCIPsetBranchruleMaxbounddist(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: scip_branch.c:353
internal miscellaneous methods
int SCIPgetNPrioExternBranchCands(SCIP *scip)
Definition: scip_branch.c:552
SCIP_RETCODE SCIPsetBranchrulePriority(SCIP *scip, SCIP_BRANCHRULE *branchrule, int priority)
Definition: scip_branch.c:323
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:959
internal methods for global SCIP settings
SCIP main data structure.
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1068
type definitions for problem variables
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:722
int SCIPgetNPrioExternBranchBins(SCIP *scip)
Definition: scip_branch.c:572
int SCIPgetNPrioExternBranchInts(SCIP *scip)
Definition: scip_branch.c:592
internal methods for problem variables
int SCIPgetNPrioExternBranchConts(SCIP *scip)
Definition: scip_branch.c:632
#define SCIP_Bool
Definition: def.h:69
int SCIPgetNPrioPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:766
methods for debugging
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip_branch.c:222
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:254
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip_branch.c:909
SCIP_RETCODE SCIPsetBranchruleMaxdepth(SCIP *scip, SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: scip_branch.c:338
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip_branch.c:654
type definitions for branch and bound tree
datastructures for problem statistics
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:936
SCIP_RETCODE SCIPbranchPseudo(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1224
internal methods for main solving loop and node processing
int SCIPgetNBranchrules(SCIP *scip)
Definition: scip_branch.c:312
SCIP_BRANCHRULE ** SCIPgetBranchrules(SCIP *scip)
Definition: scip_branch.c:301
#define SCIP_Real
Definition: def.h:157
result codes for SCIP callback methods
type definitions for branching and inference history
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:174
internal methods for constraints and constraint handlers
SCIP_RETCODE SCIPbranchLP(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1176
SCIP_RETCODE SCIPbranchExtern(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1200
common defines and data types used in all packages of SCIP
int SCIPgetNExternBranchCands(SCIP *scip)
Definition: scip_branch.c:532
#define SCIP_DECL_BRANCHEXIT(x)
Definition: type_branch.h:76
SCIP_Bool SCIPcontainsExternBranchCand(SCIP *scip, SCIP_VAR *var)
Definition: scip_branch.c:698