Computational aspects of relaxation complexity: possibilities and limitations

• 成果类型: Article
• 署名作者: Averkov, Gennadiy; Hojny, Christopher; Schymura, Matthias
• 署名单位: Brandenburg University of Technology Cottbus; Eindhoven University of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01754-8
• 发表日期: 2023
• 页码: 1173-1200
• 关键词: formulations; Knapsack; bounds; sets

摘要

The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is a useful tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rc(Q)(X), a variant of rc(X) in which the polyhedra P are required to be rational, and we show that rc(X) can be computed in polynomial time if X is 2-dimensional. Further, we investigate computable lower bounds on rc(X) with the particular focus on the existence of a finite set Y subset of Z(d) such that separating X and Y \ X allows us to deduce rc(X) >= k. In particular, we show for some choices of X that no such finite set Y exists to certify the value of rc(X), providing a negative answer to a question by Weltge (2015). We also obtain an explicit formula for rc(X) for specific classes of sets X and present the first practically applicable approach to compute rc(X) for sets X that admit a finite certificate.