Reformulation and Decomposition of Integer Programs

François Vanderbeck () and Laurence A. Wolsey ()
Additional contact information
François Vanderbeck: Institut de Mathématiques de Bordeaux (IMB) and INRIA, Université de Bordeaux
Laurence A. Wolsey: Université Catholique de Louvain, Center for Operations Research and Econometrics

Chapter Chapter 13 in 50 Years of Integer Programming 1958-2008, 2010, pp 431-502 from Springer

Abstract: Abstract 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 reformulations based on decomposition, such as Lagrangean relaxation, the Dantzig-Wolfe reformulation and the resulting column generation and branch-and-price algorithms. This is followed by an examination of Benders’ type algorithms based on projection. Finally we discuss 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: Knapsack Problem; Extended Formulation; Column Generation; Lagrangean Relaxation; Valid Inequality (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (5)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-3-540-68279-0_13

Ordering information: This item can be ordered from
http://www.springer.com/9783540682790

DOI: 10.1007/978-3-540-68279-0_13

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().