期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2009
卷号：1
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：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-andbound
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 pro jection. 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.
