期刊
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH
卷 8, 期 1, 页码 1-48出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10288-010-0122-z
关键词
Polyhedral combinatorics; Extended formulations; Projections; Matchings
资金
- Fondazione Cassa di Risparmio di Padova e Rovigo
- NSF [CMMI0653419]
- ONR [N00014-09-1-0133]
- ANR [BLAN06-1-138894]
This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By perfect formulation, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called compact extended formulations. We survey various tools for deriving and studying extended formulations, such as Fourier's procedure for projection, Minkowski-Weyl's theorem, Balas' theorem for the union of polyhedra, Yannakakis' theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set. We also present Bienstock's approximate compact extended formulation for the knapsack problem, Goemans' result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据