References of "Discrete Optimization"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailIntermediate integer programming representations using value disjunctions
Köppe, Matthias ULg; Louveaux, Quentin ULg; Weismantel, Robert

in Discrete Optimization (2008), 5(2), 293-313

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 54 (9 ULg)
Full Text
Peer Reviewed
See detailExtended formulations for Gomory Corner polyhedra
Köppe, Matthias ULg; Louveaux, Quentin ULg; Weismantel, Robert et al

in Discrete Optimization (2004), 1(2), 141-165

We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory’s group relaxations. We present algorithmic schemes based on an iterative ... [more ▼]

We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory’s group relaxations. We present algorithmic schemes based on an iterative reformulation technique using these extended formulations. We give computational results for benchmark problems, which illustrate the primal and dual effect of the reformulation. [less ▲]

Detailed reference viewed: 64 (4 ULg)