Integral decomposition of polyhedra and some applications in mixed integer programming

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


Preprint series: 00-12, Preprints

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

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.