SCIP Doxygen Documentation
Loading...
Searching...
No Matches
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-2024 Zuse Institute Berlin (ZIB) */
7
/* */
8
/* Licensed under the Apache License, Version 2.0 (the "License"); */
9
/* you may not use this file except in compliance with the License. */
10
/* You may obtain a copy of the License at */
11
/* */
12
/* http://www.apache.org/licenses/LICENSE-2.0 */
13
/* */
14
/* Unless required by applicable law or agreed to in writing, software */
15
/* distributed under the License is distributed on an "AS IS" BASIS, */
16
/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17
/* See the License for the specific language governing permissions and */
18
/* limitations under the License. */
19
/* */
20
/* You should have received a copy of the Apache-2.0 license */
21
/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22
/* */
23
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25
/**@file treemodel.h
26
* @ingroup PUBLICCOREAPI
27
* @brief Branching rules based on the Single-Variable-Branching (SVB) model
28
* @author Daniel Anderson
29
* @author Pierre Le Bodic
30
*
31
* The Single-Variable-Branching (SVB) model is a simplified model of
32
* Branch & Bound trees, from which several nontrivial variable selection
33
* rules arise. The Treemodel branching rule complements SCIP's hybrid
34
* branching by suggesting improved branching variables given the current
35
* pseudocosts and the current dual gap.
36
*
37
* Given a variable with dual bound changes (l, r) (both positive)
38
* and an absolute gap G, the SVB model describes the tree that needs to be
39
* built by branching on that same variable at every node until the value G
40
* is reached at every leaf, starting from 0 at the root node.
41
* If we do so for every variable, we can select the variable that produces
42
* the smallest tree.
43
* In the case where the gap is not known, then we can compute the growth rate
44
* of the tree, which we call the ratio.
45
* The ratio of a variable (l, r) is the factor by which the size of the tree
46
* built using (l, r) that closes a gap G must be multiplied by to close a gap
47
* G+1. This ratio is not constant for all gaps, but when G tends to infinity,
48
* it converges to a fixed value we can compute numerically using a root finding
49
* algorithm (e.g. Laguerre).
50
* The ratio is used when the gap is too large (e.g. no primal bound known) or
51
* to help approximate the size of the SVB tree for that variable.
52
*
53
* See the following publication for more detail:
54
*
55
* @par
56
* Pierre Le Bodic and George Nemhauser@n
57
* An abstract model for branching and its application to mixed integer programming@n
58
* Mathematical Programming, 2017@n
59
*/
60
61
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62
63
#ifndef __SCIP_TREEMODEL_H__
64
#define __SCIP_TREEMODEL_H__
65
66
67
#include "
scip/scip.h
"
68
69
#ifdef __cplusplus
70
extern
"C"
{
71
#endif
72
73
/** initialises the Treemodel parameter data structure */
74
SCIP_EXPORT
75
SCIP_RETCODE
SCIPtreemodelInit
(
76
SCIP
*
scip
,
/**< SCIP data structure */
77
SCIP_TREEMODEL
** treemodel
/**< Treemodel parameter data structure */
78
);
79
80
/** frees the Treemodel parameter data structure */
81
SCIP_EXPORT
82
SCIP_RETCODE
SCIPtreemodelFree
(
83
SCIP
*
scip
,
/**< SCIP data structure */
84
SCIP_TREEMODEL
** treemodel
/**< Treemodel parameter data structure */
85
);
86
87
/** returns TRUE if the Treemodel branching rules are enabled */
88
SCIP_EXPORT
89
SCIP_Bool
SCIPtreemodelIsEnabled
(
90
SCIP
*
scip
,
/**< SCIP data structure */
91
SCIP_TREEMODEL
* treemodel
/**< Treemodel parameter data structure */
92
);
93
94
/** apply the Treemodel branching rules to attempt to select a better
95
* branching candidate than the one selected by pseudocost branching */
96
SCIP_EXPORT
97
SCIP_RETCODE
SCIPtreemodelSelectCandidate
(
98
SCIP
*
scip
,
/**< SCIP data structure */
99
SCIP_TREEMODEL
* treemodel,
/**< Treemodel parameter data structure */
100
SCIP_VAR
**
branchcands
,
/**< branching candidate storage */
101
SCIP_Real*
mingains
,
/**< minimum gain of rounding downwards or upwards */
102
SCIP_Real*
maxgains
,
/**< maximum gain of rounding downwards or upwards */
103
SCIP_Real*
tiebreakerscore
,
/**< scores to use for tie breaking */
104
int
nbranchcands
,
/**< the number of branching candidates */
105
int
*
bestcand
/**< the best branching candidate found before the call,
106
and the best candidate after the call (possibly the same) */
107
);
108
109
#ifdef __cplusplus
110
}
111
#endif
112
113
#endif
bestcand
int bestcand
Definition
heur_objpscostdiving.c:295
i
int i
Definition
heur_rootsoldiving.c:212
scip
Definition
objbenders.h:44
scip.h
SCIP callable library.
SCIP_Treemodel
Definition
treemodel.c:94
SCIP_Var
Definition
struct_var.h:208
Scip
Definition
struct_scip.h:70
SCIPtreemodelSelectCandidate
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:912
SCIPtreemodelInit
SCIP_RETCODE SCIPtreemodelInit(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition
treemodel.c:826
SCIPtreemodelFree
SCIP_RETCODE SCIPtreemodelFree(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition
treemodel.c:884
SCIPtreemodelIsEnabled
SCIP_Bool SCIPtreemodelIsEnabled(SCIP *scip, SCIP_TREEMODEL *treemodel)
Definition
treemodel.c:900
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition
type_retcode.h:63
treemodel.h
© 2002-2024 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.10.0