Zurück zu den Preprints des Jahres 2000


2000-12

Integral decomposition of polyhedra and some applications in mixed integer programming

by Henk, Martin, Köppe, Matthias, Weismantel, Robert.


Series: 2000-12, Preprints

MSC:
90C11 Mixed integer programming
52B11 $n$-dimensional polytopes

Abstract:
This paper addresses the question
of decomposing an infinite family of rational polyhedra
in an integer fashion. It is shown that there is
a finite subset of this family that generates the entire family.
Moreover, an integer analogue
of Caratheodory's theorem carries
over to this general setting.
The integer decomposition of a family of polyhedra
has different applications in integer
and mixed integer programming.

Keywords:
mixed integer programming, test sets, indecomposable polyhedra, Hilbert bases, rational polyhedral cones