Computational Aspects of Relaxation Complexity

Gennadiy Averkov, Christopher Hojny, Matthias Schymura

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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 an important tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rcQ(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. We also present an explicit formula for rc(X) of a specific class of sets X and present numerical experiments on the distribution of rc(X) in dimension 2.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings
EditorsMohit Singh, David P. Williamson
Pages368-382
Number of pages15
DOIs
Publication statusPublished - 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12707 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Integer programming formulation
  • Relaxation complexity

Fingerprint

Dive into the research topics of 'Computational Aspects of Relaxation Complexity'. Together they form a unique fingerprint.

Cite this