Title | ||
---|---|---|
Nondecomposable solutions to group equations and an application to polyhedral combinatorics |
Abstract | ||
---|---|---|
This paper is based on the study of the set of nondecomposable integer solutions in a Gomory corner polyhedron, which was recently used in a reformu- lation method for integer linear programs. In this paper, we present an algorithm for e ciently computing this set. We precompute a database of nondecompos- able solutions for cyclic groups up to order 52. As a second application of this database, we introduce an algorithm for computing nontrivial simultaneous lifting coe cients. The lifting coe cients are exact for a discrete relaxation of the integer program that consists of a group relaxation plus bound constraints. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/s10288-005-0073-y | 4OR |
Keywords | Field | DocType |
gomory corner polyhedron,irreducible group solutions,simulta- neous lifting,polyhedral combinatorics,cyclic group | Integer,Discrete mathematics,Mathematical optimization,Combinatorics,Cyclic group,Polyhedron,Mathematics,Polyhedral combinatorics | Journal |
Volume | Issue | ISSN |
4 | 1 | 1614-2411 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Matthias Jach | 1 | 24 | 1.71 |
Matthias KöPpe | 2 | 191 | 20.95 |
Robert Weismantel | 3 | 964 | 90.05 |