Optimization via Polyhedral Omega
Use PO-based exact counting/enumeration to design exact and hybrid optimization methods for integer programs.
- Suitable for
- Master's thesis
PhD thesis - Supervision
- Zafeirakis Zafeirakopoulos
Goal: Bridge PO-based exact counting with optimization — solve or accelerate integer linear programs (ILPs) using information extracted by Polyhedral Omega.
Classical ILP solvers (branch-and-bound, cutting planes) treat the feasibility question as a search problem. Polyhedral Omega instead computes an exact generating function that encodes the full solution set. This generating function carries global information — number of solutions, optimal value, sensitivity — that classical solvers can only obtain heuristically.
Threads
1. PO → objective bounds for knapsack-like families
For a parametric family of ILPs (e.g., the knapsack problem with capacity \(c\)), PO produces a rational generating function valid across all \(c\). Extracting the coefficient for a specific \(c\) gives the exact count; the maximum achieving coefficient gives the optimum.
2. PO-informed cutting planes
The generating function can certify infeasibility or reveal the structure of the integer hull. This structure can be translated into cutting planes that tighten the LP relaxation faster than generic cuts.
3. Hybrid methods
Combine PO (exact, expensive) with classical solvers (approximate, fast): run PO for small subproblems to produce strong bounds, then use branch-and-bound globally.
Background
Barvinok’s algorithm (1994) counts integer points in a polytope in polynomial time when the dimension is fixed. Polyhedral Omega (Breuer & Zafeirakopoulos, 2017) extends this to parametric settings, computing a piecewise rational generating function over the parameter space.
Deliverables
- Julia implementation of at least one PO-based optimization method (bounds, cutting planes, or hybrid)
- Benchmark comparison against classical branch-and-bound / cutting-plane solvers
- Short report (6–8 pages)
References
-
A. I. Barvinok. A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed. Mathematics of Operations Research, 19(4):769–779, 1994. DOI 10.1287/moor.19.4.769
-
F. Breuer and Z. Zafeirakopoulos. Polyhedral Omega: a New Algorithm for Solving Linear Diophantine Systems. Annals of Combinatorics, 21(2):211–280, 2017. DOI 10.1007/s00026-017-0349-x
-
S. Verdoolaege, R. Seghir, K. Beyls, V. Loechner, and M. Bruynooghe. Counting Integer Points in Parametric Polytopes Using Barvinok’s Rational Functions. Algorithmica, 48(1):37–66, 2007. DOI 10.1007/s00453-006-1231-0
-
T. Ayyildiz, D. N. Demirel, I. Tapan, and Z. Zafeirakopoulos. A Julia Package for Polyhedral Omega and Applications. ACM Communications in Computer Algebra, 58(2):39–42, 2024. DOI 10.1145/3712023.3712029