12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > An augment-and-branch-and-cut framework for mix...
View graph of relations

« Back

An augment-and-branch-and-cut framework for mixed 0-1 programming

Research output: Contribution in Book/Report/ProceedingsChapter (peer-reviewed)

Published

Publication date2003
Host publicationCombinatorial Optimization : Eureka! You Shrink
EditorsMichael Jünger, Gerhard Reinelt, Giovanni Rinaldi
Place of publicationBerlin
PublisherSpringer
Pages119-133
Number of pages15
ISBN (Print)3-540-00580-3
Original languageEnglish

Conference

Conference5th International Workshop
CountryFrance
CityAussois
Period5/03/019/03/01

Publication series

NameLecture Notes in Computer Science
Volume2570

Conference

Conference5th International Workshop
CountryFrance
CityAussois
Period5/03/019/03/01

Abstract

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.