Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review
}
TY - CHAP
T1 - An augment-and-branch-and-cut framework for mixed 0-1 programming
AU - Letchford, A N
AU - Lodi, A
PY - 2003
Y1 - 2003
N2 - In recent years the branch-and-cut method, a synthesis of the classical branch-and-bound and cutting plane methods, has proven to be a highly successful approach to solving large-scale integer programs to optimality. This is especially true for mixed 0-1 and pure 0-1 problems. However, other approaches to integer programming are possible. One alternative is provided by so-called augmentation algorithms, in which a feasible integer solution is iteratively improved (augmented) until no further improvement is possible. Recently, Weismantel suggested that these two approaches could be combined in some way, to yield an augment-and-branch-and-cut (ABC) algorithm for integer programming. In this paper we describe a possible implementation of such a finite ABC algorithm for mixed 0-1 and pure 0-1 programs. The algorithm differs from standard branch-and-cut in several important ways. In particular, the terms separation, branching, and fathoming take on new meanings in the primal context.
AB - In recent years the branch-and-cut method, a synthesis of the classical branch-and-bound and cutting plane methods, has proven to be a highly successful approach to solving large-scale integer programs to optimality. This is especially true for mixed 0-1 and pure 0-1 problems. However, other approaches to integer programming are possible. One alternative is provided by so-called augmentation algorithms, in which a feasible integer solution is iteratively improved (augmented) until no further improvement is possible. Recently, Weismantel suggested that these two approaches could be combined in some way, to yield an augment-and-branch-and-cut (ABC) algorithm for integer programming. In this paper we describe a possible implementation of such a finite ABC algorithm for mixed 0-1 and pure 0-1 programs. The algorithm differs from standard branch-and-cut in several important ways. In particular, the terms separation, branching, and fathoming take on new meanings in the primal context.
KW - integer programming
KW - branch-and-cut
U2 - 10.1007/3-540-36478-1_12
DO - 10.1007/3-540-36478-1_12
M3 - Chapter (peer-reviewed)
SN - 3-540-00580-3
T3 - Lecture Notes in Computer Science
SP - 119
EP - 133
BT - Combinatorial Optimization
A2 - Jünger, Michael
A2 - Reinelt, Gerhard
A2 - Rinaldi, Giovanni
PB - Springer
CY - Berlin
T2 - 5th International Workshop
Y2 - 5 March 2001 through 9 March 2001
ER -