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-2023 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
54 extern "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  */
68 SCIP_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  */
97 SCIP_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 */
112 SCIP_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 */
120 SCIP_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 */
128 SCIP_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 */
136 SCIP_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 */
144 SCIP_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 */
152 SCIP_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 */
160 SCIP_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 */
168 SCIP_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 */
176 SCIP_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 */
184 SCIP_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 */
191 SCIP_EXPORT
193  SCIP* scip /**< SCIP data structure */
194  );
195 
196 /** returns the number of currently available branching rules */
197 SCIP_EXPORT
199  SCIP* scip /**< SCIP data structure */
200  );
201 
202 /** sets the priority of a branching rule */
203 SCIP_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) */
211 SCIP_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 */
219 SCIP_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  */
250 SCIP_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  */
270 SCIP_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  */
284 SCIP_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  */
305 SCIP_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  */
328 SCIP_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  */
342 SCIP_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  */
356 SCIP_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  */
370 SCIP_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  */
384 SCIP_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  */
398 SCIP_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  */
414 SCIP_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  */
429 SCIP_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  */
443 SCIP_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  */
460 SCIP_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  */
478 SCIP_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  */
493 SCIP_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  */
507 SCIP_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  */
521 SCIP_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  */
535 SCIP_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  */
549 SCIP_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  */
566 SCIP_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  */
585 SCIP_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  */
602 SCIP_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  */
623 SCIP_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  */
641 SCIP_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  */
659 SCIP_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  */
684 SCIP_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  */
703 SCIP_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  */
729 SCIP_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  */
765 SCIP_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  */
788 SCIP_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  */
804 SCIP_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  */
820 SCIP_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
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
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 SCIPgetNPrioPseudoBranchBins(SCIP *scip)
Definition: scip_branch.c:795
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 SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
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
#define SCIP_DECL_BRANCHEXECPS(x)
Definition: type_branch.h:176
int SCIPgetNPrioPseudoBranchImpls(SCIP *scip)
Definition: scip_branch.c:831
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:758
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:57
SCIP_RETCODE SCIPsetBranchruleInitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: scip_branch.c:217
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:897
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:201
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
#define SCIP_DECL_BRANCHFREE(x)
Definition: type_branch.h:75
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
void SCIPclearExternBranchCands(SCIP *scip)
Definition: scip_branch.c:689
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip_branch.c:872
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
int SCIPgetNPrioPseudoBranchInts(SCIP *scip)
Definition: scip_branch.c:813
#define SCIP_DECL_BRANCHEXECEXT(x)
Definition: type_branch.h:155
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:116
SCIP_Real SCIPcalcChildEstimateIncrease(SCIP *scip, SCIP_VAR *var, SCIP_Real varsol, SCIP_Real targetvalue)
Definition: scip_branch.c:971
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
#define SCIP_DECL_BRANCHEXITSOL(x)
Definition: type_branch.h:113
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
int SCIPgetNPrioExternBranchImpls(SCIP *scip)
Definition: scip_branch.c:623
type definitions for branching rules
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:849
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
int SCIPgetNPrioLPBranchCands(SCIP *scip)
Definition: scip_branch.c:466
#define SCIP_DECL_BRANCHINIT(x)
Definition: type_branch.h:83
#define SCIP_DECL_BRANCHCOPY(x)
Definition: type_branch.h:67
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1050
type definitions for SCIP&#39;s main datastructure
#define SCIP_DECL_BRANCHINITSOL(x)
Definition: type_branch.h:102
#define SCIP_DECL_BRANCHEXECLP(x)
Definition: type_branch.h:134
SCIP_RETCODE SCIPsetBranchruleMaxbounddist(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: scip_branch.c:364
int SCIPgetNPrioExternBranchCands(SCIP *scip)
Definition: scip_branch.c:563
SCIP_RETCODE SCIPsetBranchrulePriority(SCIP *scip, SCIP_BRANCHRULE *branchrule, int priority)
Definition: scip_branch.c:334
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1017
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
type definitions for problem variables
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
int SCIPgetNPrioExternBranchBins(SCIP *scip)
Definition: scip_branch.c:583
int SCIPgetNPrioExternBranchInts(SCIP *scip)
Definition: scip_branch.c:603
int SCIPgetNPrioExternBranchConts(SCIP *scip)
Definition: scip_branch.c:643
#define SCIP_Bool
Definition: def.h:93
int SCIPgetNPrioPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:777
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip_branch.c:233
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:265
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip_branch.c:920
SCIP_RETCODE SCIPsetBranchruleMaxdepth(SCIP *scip, SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: scip_branch.c:349
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip_branch.c:665
type definitions for branch and bound tree
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:947
SCIP_RETCODE SCIPbranchPseudo(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1282
int SCIPgetNBranchrules(SCIP *scip)
Definition: scip_branch.c:323
SCIP_BRANCHRULE ** SCIPgetBranchrules(SCIP *scip)
Definition: scip_branch.c:312
#define SCIP_Real
Definition: def.h:186
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:185
SCIP_RETCODE SCIPbranchLP(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1234
SCIP_RETCODE SCIPbranchExtern(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1258
common defines and data types used in all packages of SCIP
int SCIPgetNExternBranchCands(SCIP *scip)
Definition: scip_branch.c:543
#define SCIP_DECL_BRANCHEXIT(x)
Definition: type_branch.h:91
SCIP_Bool SCIPcontainsExternBranchCand(SCIP *scip, SCIP_VAR *var)
Definition: scip_branch.c:709