Intermediate integer programming representations using value disjunctions

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 formu-
lation 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 descrip-
tion decomposes into one “linking polyhedron” per block and the “aggre-
gated 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 coeffi-
cients, this theorem provides a complete description in an extended space
with a polynomial number of variables.
Based on this theory, we propose a new branching scheme that analyzes
the problem structure. It is designed to be applied in those subproblems
of hard integer programs where LP-based techniques do not provide good
branching decisions. Preliminary computational experiments show that it
is successful for some benchmark problems of multi-knapsack type.