Optimization via Polyhedral Omega

Use PO-based exact counting/enumeration to design exact and hybrid optimization methods for integer programs.

difficult master phd optimization combinatorics 7

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.

Plan

gantt
  title Optimization via PO — Semester Plan
  dateFormat  YYYY-MM-DD
  axisFormat  %b %d
  section Foundations
  PO refresher + LDS review    :done,   s1, 2025-11-01, 2025-11-07
  Small PO demos on toy ILPs   :active, s2, 2025-11-08, 2025-11-22
  section Methods
  Bounds from counting         :        s3, 2025-11-23, 2025-12-20
  PO → cutting planes          :        s4, 2025-12-21, 2026-01-25
  section Evaluation
  Benchmarks & ablations       :        s5, 2026-01-26, 2026-03-05
  Write-up & release           :        s6, 2026-03-06, 2026-03-31

References

  1. 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

  2. F. Breuer and Z. Zafeirakopoulos. Polyhedral Omega: a New Algorithm for Solving Linear Diophantine Systems. Annals of Combinatorics, 21(2):211–280, 2017.

  3. 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

  4. T. Ayyildiz, D. N. Demirel, I. Tapan, and Z. Zafeirakopoulos. A Julia Package for Polyhedral Omega and Applications. MACIS 2024.