Symmetric integer linear programming with a core point approach
Loading...
Date
2024-11
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
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.