06-50
Intermediate integer programming representations using value disjunctions
by Köppe, Matthias; Louveaux, Quentin; Weismantel, Robert
Preprint series: 06-50, Preprints
- MSC:
- 90C10 Integer programming
Abstract: We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formulation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet description decomposes into one ``linking polyhedron\'\' per block and the ``aggregated polyhedron\'\'. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coefficients, this theorem provides a complete description in an extended space with a polynomial number of variables.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.