The role of rationality in integer-programming relaxations

Quantifier elimination, model completeness, and related topics (03C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: For a finite set

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

that can be represented as

X = Q c a p m a t h b b Z^{d}

for some polyhedron

Q

, we call

Q

a relaxation of

X

and define the relaxation complexity

r c (X)

of

X

as the least number of facets among all possible relaxations

Q

of

X

. The rational relaxation complexity

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

restricts the definition of

r c (X)

to rational polyhedra

Q

. In this article, we focus on

X = D e l t a_{d}

, the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in

m a t h b b R^{d}

. We show that

r c (D e l t a_{d}) l e q d

for every

d g e q 5

. That is, since

r c_{m a t h b b Q} (D e l t a_{d}) = d + 1

, irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Lower bounds on the size of integer programs without additional variables, Mathematical Programming, 154(1):407-425, 2015). Moreover, we prove the asymptotic statement

r c (D e l t a_{d}) i n O (f r a c d s q r t l o g (d))

, which shows that the ratio

r c (D e l t a_{d}) / r c_{m a t h b b Q} (D e l t a_{d})

goes to

0

, as

d o i n f t y

.

Recommendations

Cites work

Describes a project that uses

Uses Software

SageMath

This page was built for publication: The role of rationality in integer-programming relaxations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6126664)