Reference : Intermediate integer programming representations using value disjunctions
Scientific congresses and symposiums : Unpublished conference/Abstract
Engineering, computing & technology : Computer science
Intermediate integer programming representations using value disjunctions
Louveaux, Quentin mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
10th workshop on combinatorial optimization
January 2006
[en] Mixed-integer programming ; Extended formulations
[en] We introduce a general technique for creating 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.
On the basis of 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.

File(s) associated to this reference

Fulltext file(s):

Open access
aussois06QL.pdfAuthor preprint494.35 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.