Outer approximations of core points for integer programming
Loading...
Files
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
Abstract
The main objective of this thesis is to develop some new algorithms for solving some hard symmetric integer linear programs (ILP). The idea comes from the concept of core points that are defined by the symmetry group of the polyhedron. The set of core points of a polyhedron is a subset of its integral points. It has been proved that if a symmetric integer linear program is integer feasible, either there is an optimal solution that is a core point or there is a core point in the core set of the polyhedron with the same objective value. Furthermore, for finding an optimal solution of a symmetric ILP, we can search among core points rather than integral points. The set of core points under a symmetry group can be finite or infinite. Recently, some techniques have been developed for solving symmetric ILPs with a finite number of core points. We discuss some of them in Chapter 3. But when the core set is infinite, these techniques are not practical anymore. In this thesis we develop some algorithms for the case where the set of core points has infinitely many elements. Then we use these algorithm to solve some hard symmetric ILPs.