Symbolic Polyhedral Omega
Geometry in symbolic dimension to solve families of integer programming problems parametrically.
- Suitable for
- Master's thesis
PhD thesis - Supervision
- Zafeirakis Zafeirakopoulos
Focus: Extend Polyhedral Omega to handle families of problems where some coefficients are symbolic (parametric), enabling family-wise solutions and sensitivity analysis.
Motivation
Standard Polyhedral Omega takes a linear Diophantine system \(A\mathbf{x} = \mathbf{b},\; \mathbf{x}\geq 0\) with integer \(A, \mathbf{b}\) and returns a rational generating function for all integer solutions. In the symbolic variant, some entries of \(\mathbf{b}\) (or \(A\)) are treated as formal parameters \(\mathbf{p}\). The output is a piecewise rational function: for each chamber in parameter space, a different rational expression counts the solutions.
This yields:
- Parametric feasibility regions — the set of \(\mathbf{p}\) for which solutions exist.
- Optimal value functions — the optimal objective as a closed-form function of \(\mathbf{p}\).
- Sensitivity analysis — how the optimum changes as \(\mathbf{p}\) varies continuously.
Core challenges
- Symbolic cone operations — the omega elimination step must track symbolic constraints, leading to parameterized polyhedral cones.
- Chamber decomposition — subdivide parameter space into chambers such that the generating function is a fixed rational function within each chamber.
- Computational complexity — the number of chambers may be exponential; efficient data structures and algorithms are needed.
Deliverables
- Julia prototype extending Polyhedral Omega to symbolic parameters on a restricted case
- Worked examples showing parametric feasibility regions and optimal value functions
- 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
-
M. Köppe and S. Verdoolaege. Computing Parametric Rational Generating Functions with a Primal Barvinok Algorithm. Electronic Journal of Combinatorics, 15(1), 2008. combinatorics.org