Outer approximations of core points for integer programming
| dc.contributor.advisor | Bremner, David | |
| dc.contributor.advisor | Monson, Barry | |
| dc.contributor.author | Shahverdizadeh Shargh, Naghmeh | |
| dc.date.accessioned | 2023-03-01T16:16:07Z | |
| dc.date.available | 2023-03-01T16:16:07Z | |
| dc.date.issued | 2021 | |
| dc.date.updated | 2023-03-01T15:01:03Z | |
| dc.description.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. | |
| dc.description.copyright | ©Naghmeh Shahverdizadeh Shargh, 2021 | |
| dc.description.note | Electronic Only. | |
| dc.format | text/xml | |
| dc.format.extent | x, 115 pages | |
| dc.format.medium | electronic | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/13165 | |
| dc.language.iso | en_CA | |
| dc.publisher | University of New Brunswick | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Mathematics and Statistics | |
| dc.title | Outer approximations of core points for integer programming | |
| dc.type | doctoral thesis | |
| thesis.degree.discipline | Mathematics and Statistics | |
| thesis.degree.fullname | Doctor of Philosophy | |
| thesis.degree.grantor | University of New Brunswick | |
| thesis.degree.level | doctoral | |
| thesis.degree.name | Ph.D. |
Files
Original bundle
1 - 1 of 1