Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2007.10863 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908350730469376 |
|---|---|
| author | Shahverdi, Naghmeh Banihashemi, Seyyedmahsa Bremner, David |
| author_facet | Shahverdi, Naghmeh Banihashemi, Seyyedmahsa Bremner, David |
| contents | For several decades the dominant techniques for integer linear programming have been branching and cutting planes. Recently, several authors have developed core point methods for solving symmetric integer linear programs (ILPs). An integer point is called a core point if its orbit polytope is lattice-free. It has been shown that for symmetric ILPs, optimizing over the set of core points gives the same answer as considering the entire space. Existing core point techniques rely on the number of core points (or equivalence classes) being finite, which requires special symmetry groups. In this paper we develop some new methods for solving symmetric ILPs (based on outer approximations of core points) that do not depend on finiteness but are more efficient if the group has large disjoint cycles in its set of generators. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_10863 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Outer approximations of core points for integer programming Shahverdi, Naghmeh Banihashemi, Seyyedmahsa Bremner, David Optimization and Control Computational Geometry 90C10 (Primary), 90C26 (Secondary), 52B15 (Secondary) G.4; F.2.1 For several decades the dominant techniques for integer linear programming have been branching and cutting planes. Recently, several authors have developed core point methods for solving symmetric integer linear programs (ILPs). An integer point is called a core point if its orbit polytope is lattice-free. It has been shown that for symmetric ILPs, optimizing over the set of core points gives the same answer as considering the entire space. Existing core point techniques rely on the number of core points (or equivalence classes) being finite, which requires special symmetry groups. In this paper we develop some new methods for solving symmetric ILPs (based on outer approximations of core points) that do not depend on finiteness but are more efficient if the group has large disjoint cycles in its set of generators. |
| title | Outer approximations of core points for integer programming |
| topic | Optimization and Control Computational Geometry 90C10 (Primary), 90C26 (Secondary), 52B15 (Secondary) G.4; F.2.1 |
| url | https://arxiv.org/abs/2007.10863 |