Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.disopt.2006.12.003 | Discrete Optimization |
Keywords | Field | DocType |
original formulation,compact complete description,aggregated polyhedron,branch-and-cut algorithms,polyhedral combinatorics,extended space,extended formulations,fixed number,complete description,mixed-integer programming,general technique,extended formulation,lp-based technique,facet description decomposes,value disjunction,intermediate integer programming representation,mixed integer programming,branch and cut,computer experiment,polynomial time | Integer,Discrete mathematics,Mathematical optimization,Polynomial,Polyhedron,Branch and cut,Branch and price,Integer programming,Knapsack problem,Mathematics,Polyhedral combinatorics | Journal |
Volume | Issue | ISSN |
5 | 2 | Discrete Optimization |
Citations | PageRank | References |
5 | 0.55 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthias KöPpe | 1 | 191 | 20.95 |
| Quentin Louveaux | 2 | 189 | 14.83 |
| Robert Weismantel | 3 | 964 | 90.05 |