Intermediate integer programming representations using value disjunctions

Details Intermediate integer programming representations using value disjunctions Intermediate integer programming representations using value disjunctions

2006-03-13

arxiv.org/abs/math/0603311v1

Mathematics

Optimization and Control

26 pages, 5 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Intermediate integer programming representations using value disjunctions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Intermediate integer programming representations using value disjunctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intermediate integer programming representations using value disjunctions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-704754