Computational Aspects of Relaxation Complexity: Possibilities and Limitations

Abstract: The relaxation complexity

m a t h r m r c (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

m a t h r m {r c}_{m a t h b b Q} (X)

, a variant of

m a t h r m r c (X)

in which the polyhedra

P

are required to be rational, and we show that

m a t h r m r c (X)

can be computed in polynomial time if

X

is 2-dimensional. Further, we investigate computable lower bounds on

m a t h r m r c (X)

with the particular focus on the existence of a finite set

Y s u b s e t e q m a t h b b Z^{d}

such that separating

X

and

Y s e t m i n u s X

allows us to deduce

m a t h r m r c (X) g e q k

. In particular, we show for some choices of

X

that no such finite set

Y

exists to certify the value of

m a t h r m r c (X)

, providing a negative answer to a question by Weltge (2015). We also obtain an explicit formula for

m a t h r m r c (X)

for specific classes of sets

X

and present the first practically applicable approach to compute

m a t h r m r c (X)

for sets

X

that admit a finite certificate.

This page was built for publication: Computational Aspects of Relaxation Complexity: Possibilities and Limitations