期刊
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2019
卷 11480, 期 -, 页码 247-260出版社
SPRINGER INTERNATIONAL PUBLISHING AG
DOI: 10.1007/978-3-030-17953-3_19
关键词
Integer programs; Cutting planes; Group relaxations
资金
- National Science Foundation [DMS-0914873, DMS-1320051]
- DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization through NSF [CCF-1740425]
The non-extreme minimal valid functions for the Gomory-Johnson infinite group problem are those that admit effective perturbations. For a class of piecewise linear functions for the 1-row problem we give a precise description of the space of these perturbations as a direct sum of certain finite- and infinite-dimensional subspaces. The infinite-dimensional subspaces have partial symmetries; to describe them, we develop a theory of inverse semigroups of partial bijections, interacting with the functional equations satisfied by the perturbations. Our paper provides the foundation for grid-free algorithms for testing extremality and for computing liftings of non-extreme functions. The grid-freeness makes the algorithms suitable for piecewise linear functions whose breakpoints are rational numbers with huge denominators.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据