Reformulation and decomposition of integer programs

François Vanderbeck and Laurence Wolsey ()
Additional contact information
Laurence Wolsey: Université catholique de Louvain (UCL). Center for Operations Research and Econometrics (CORE)

No 2009016, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: In this survey we examine ways to reformulate integer and mixed integer programs. Typically, but not exclusively, one reformulates so as to obtain stronger linear programming relaxations, and hence better bounds for use in a branch-and-bound based algorithm. First we cover in detail reformulations based on decomposition, such as Lagrangean relaxation, Dantzig-Wolfe column generation and the resulting branch-and-price algorithms. This is followed by an examination of Benders’ type algorithms based on projection. Finally we discuss in detail extended formulations involving additional variables that are based on problem structure. These can often be used to provide strengthened a priori formulations. Reformulations obtained by adding cutting planes in the original variables are not treated here.

Keywords: Integer program; Lagrangean relaxation; column generation; branch-and-price; extended formulation; Benders' algorithm (search for similar items in EconPapers)
Date: 2009-03-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2009.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2009016

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().