Scippy

SCIP

Solving Constraint Integer Programs

treemodel.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-2022 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file treemodel.h
17  * @ingroup PUBLICCOREAPI
18  * @brief Branching rules based on the Single-Variable-Branching (SVB) model
19  * @author Daniel Anderson
20  * @author Pierre Le Bodic
21  *
22  * The Single-Variable-Branching (SVB) model is a simplified model of
23  * Branch & Bound trees, from which several nontrivial variable selection
24  * rules arise. The Treemodel branching rule complements SCIP's hybrid
25  * branching by suggesting improved branching variables given the current
26  * pseudocosts and the current dual gap.
27  *
28  * Given a variable with dual bound changes (l, r) (both positive)
29  * and an absolute gap G, the SVB model describes the tree that needs to be
30  * built by branching on that same variable at every node until the value G
31  * is reached at every leaf, starting from 0 at the root node.
32  * If we do so for every variable, we can select the variable that produces
33  * the smallest tree.
34  * In the case where the gap is not known, then we can compute the growth rate
35  * of the tree, which we call the ratio.
36  * The ratio of a variable (l, r) is the factor by which the size of the tree
37  * built using (l, r) that closes a gap G must be multiplied by to close a gap
38  * G+1. This ratio is not constant for all gaps, but when G tends to infinity,
39  * it converges to a fixed value we can compute numerically using a root finding
40  * algorithm (e.g. Laguerre).
41  * The ratio is used when the gap is too large (e.g. no primal bound known) or
42  * to help approximate the size of the SVB tree for that variable.
43  *
44  * See the following publication for more detail:
45  *
46  * @par
47  * Pierre Le Bodic and George Nemhauser@n
48  * An abstract model for branching and its application to mixed integer programming@n
49  * Mathematical Programming, 2017@n
50  */
51 
52 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
53 
54 #ifndef __SCIP_TREEMODEL_H__
55 #define __SCIP_TREEMODEL_H__
56 
57 
58 #include "scip/scip.h"
59 
60 #ifdef __cplusplus
61 extern "C" {
62 #endif
63 
64 /** initialises the Treemodel parameter data structure */
65 SCIP_EXPORT
67  SCIP* scip, /**< SCIP data structure */
68  SCIP_TREEMODEL** treemodel /**< Treemodel parameter data structure */
69 );
70 
71 /** frees the Treemodel parameter data structure */
72 SCIP_EXPORT
74  SCIP* scip, /**< SCIP data structure */
75  SCIP_TREEMODEL** treemodel /**< Treemodel parameter data structure */
76 );
77 
78 /** returns TRUE if the Treemodel branching rules are enabled */
79 SCIP_EXPORT
81  SCIP* scip, /**< SCIP data structure */
82  SCIP_TREEMODEL* treemodel /**< Treemodel parameter data structure */
83 );
84 
85 /** apply the Treemodel branching rules to attempt to select a better
86  * branching candidate than the one selected by pseudocost branching */
87 SCIP_EXPORT
89  SCIP* scip, /**< SCIP data structure */
90  SCIP_TREEMODEL* treemodel, /**< Treemodel parameter data structure */
91  SCIP_VAR** branchcands, /**< branching candidate storage */
92  SCIP_Real* mingains, /**< minimum gain of rounding downwards or upwards */
93  SCIP_Real* maxgains, /**< maximum gain of rounding downwards or upwards */
94  SCIP_Real* tiebreakerscore, /**< scores to use for tie breaking */
95  int nbranchcands, /**< the number of branching candidates */
96  int* bestcand /**< the best branching candidate found before the call,
97  and the best candidate after the call (possibly the same) */
98 );
99 
100 #ifdef __cplusplus
101 }
102 #endif
103 
104 #endif
SCIP_RETCODE SCIPtreemodelSelectCandidate(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Real *tiebreakerscore, int nbranchcands, int *bestcand)
Definition: treemodel.c:911
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Bool SCIPtreemodelIsEnabled(SCIP *scip, SCIP_TREEMODEL *treemodel)
Definition: treemodel.c:899
SCIP_RETCODE SCIPtreemodelFree(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:883
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPtreemodelInit(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:825
#define SCIP_Real
Definition: def.h:177
SCIP callable library.