PO-derived Bounds for Knapsack Families
Study bounds on knapsack-type integer programs derived from Polyhedral Omega counting and compare to branch-and-bound.
- Suitable for
- Master's thesis
- Supervision
- Zafeirakis Zafeirakopoulos
We study how Polyhedral Omega (PO) counting over parametric families can be used to derive tight bounds for knapsack-type ILPs, and benchmark these bounds against classical branch-and-bound solvers.
Problem
The 0–1 knapsack problem asks: given items with weights \(w_i\) and values \(v_i\), find a subset with total weight \(\leq c\) and maximum total value. For a parametric family (e.g., capacity \(c\) varies), the generating function
\[F(z, x) = \sum_{c \geq 0} \left(\sum_{\substack{S \subseteq [n] \\ \sum_{i\in S}w_i \leq c}} \prod_{i\in S} v_i^{x_i}\right) z^c\]encodes the complete solution landscape. PO computes this as a rational function in \(z\) and \(x\).
Approach
-
Exact bound extraction. Once \(F\) is computed, the optimal value for a specific capacity \(c\) is the maximum-weight coefficient of \([z^c]F\). Extracting this avoids re-solving the ILP for each \(c\).
-
Sensitivity analysis. The chamber decomposition of the parameter space shows which values of \(c\) have the same combinatorial optimum structure, enabling rapid re-optimization when capacity changes slightly.
-
Upper bounds via LP relaxation comparison. Compare PO-derived tight bounds against the LP relaxation bound and branch-and-bound B&B at fixed capacities.
- Repo: po-bounds-knapsack
Milestones
| ID | Title |
|---|---|
| M1 | Replicate PO counting on toy knapsack |
| M2 | Bound extraction & correctness tests |
| M3 | Benchmark suite + analysis |
| M4 | Final report & release |
Tasks
| ID | Title | Status |
|---|---|---|
| T1 | Implement counting for parametric families | todo |
| T2 | Extract bounds from generating functions | todo |
| T3 | Benchmark vs. B&B across sizes | todo |
| T4 | Ablations + write-up | todo |
Deliverables
- PO-bound computation module
- Benchmark across parametric families
- Report with comparisons vs. branch-and-bound
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