Abstract | ||
---|---|---|
We consider convex programming problems with integrality constraints that are invariant under a linear symmetry group. To decompose such problems, we introduce the new concept of core points, i.e., integral points whose orbit polytopes are lattice-free. For symmetric integer linear programs, we describe two algorithms based on this decomposition. Using a characterization of core points for direct products of symmetric groups, we show that prototype implementations can compete with state-of-the-art commercial solvers, and solve an open MIPLIB problem. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.orl.2013.02.007 | Operations Research Letters |
Keywords | Field | DocType |
Symmetry,Integer linear programs,Integer convex optimization,Core point,Core set | Integer,Discrete mathematics,Combinatorics,Mathematical optimization,Symmetry group,Symmetric group,Convex combination,Integer points in convex polyhedra,Polytope,Invariant (mathematics),Convex optimization,Mathematics | Journal |
Volume | Issue | ISSN |
41 | 3 | 0167-6377 |
Citations | PageRank | References |
4 | 0.45 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Katrin Herr | 1 | 35 | 2.66 |
Thomas Rehn | 2 | 16 | 2.56 |
Achill Schürmann | 3 | 52 | 9.17 |