Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case

• 成果类型: Article
• 署名作者: Basu, Amitabh; Hildebrand, Robert; Koeppe, Matthias
• 署名单位: Johns Hopkins University; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Davis
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0660
• 发表日期: 2015
• 页码: 105-129
• 关键词: valid inequalities; group polyhedra; facets; relaxation; THEOREM; Finite

摘要

We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We also present an extreme function that is a piecewise linear function with some irrational breakpoints, whose extremality follows from a new principle.