Equivariant perturbation in Gomory and Johnson's infinite group problem-III: foundations for the k-dimensional case with applications to k=2

• 成果类型: Article
• 署名作者: Basu, Amitabh; Hildebrand, Robert; Koppe, Matthias
• 署名单位: Johns Hopkins University; International Business Machines (IBM); IBM USA; University of California System; University of California Davis
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1064-9
• 发表日期: 2017
• 页码: 301-358
• 关键词: INEQUALITIES; relaxation; THEOREM

摘要

We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, we present the general regular solution to Cauchy's additive functional equation on restricted lower-dimensional convex domains. This provides a k-dimensional generalization of the so-called Interval Lemma, allowing us to deduce affine properties of the function from certain additivity relations. Next, we study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. We then give a theory of non-extremality certificates in the form of perturbation functions. We apply these tools in the context of minimal valid functions for the two-dimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under a regularity condition called diagonal constrainedness. We show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite two-dimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function.