Symmetric integer linear programming with a core point approach
| dc.contributor.advisor | Bremner, David | |
| dc.contributor.author | Banihashemi, Seyyedemahsa | |
| dc.date.accessioned | 2025-01-13T15:51:18Z | |
| dc.date.available | 2025-01-13T15:51:18Z | |
| dc.date.issued | 2024-11 | |
| dc.description.abstract | This thesis explains the implementation of two existing algorithms, to solve symmetric integer linear programs (ILPs), using PyScipOpt, a Python interface to the SCIP optimization software. The existing approach focuses on a special feature of circulant matrices to develop new constraints for solving these problems, based on core points, a subset of integral points in symmetric ILPs. We made some modifications to the algorithms. This was achieved by constructing and utilizing essential sets more effectively, calculating the value of big M, and modifying constraints when the matrix is singular. Additionally, we used the two algorithms to compare the outcomes for problems solved by Knitro with those same problems solved using SCIP. We test the algorithms with both feasible and infeasible instances, varying in the number of variables. Moreover, we tested infeasible ILP problems with different polytope shapes, using Algorithm 2, CPLEX, and SCIP to compare the performance of these three solvers. | |
| dc.description.copyright | © Seyyedemahsa Banihashemi, 2024 | |
| dc.format.extent | viii, 88 | |
| dc.format.medium | electronic | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/38227 | |
| dc.language.iso | en | |
| dc.publisher | University of New Brunswick | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | Symmetric integer linear programming with a core point approach | |
| dc.type | master thesis | |
| oaire.license.condition | other | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | University of New Brunswick | |
| thesis.degree.level | masters | |
| thesis.degree.name | M.C.S. |