Id: arxiv/2607.09222 Url: https://arxiv.org/abs/2607.09222 Tags: math.OC Score: 0 Title: Polyhedral extended formulations that approximate the Gomory closure for packing problems Domain: math.OC Source: arxiv Authors: Friedrich Eisenbrand, Samuel Fiorini, Lars Rohwedder, Jiaye Wei Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-10 Page: https://delphi.science/r/arxiv/2607.09222 We consider $0/1$ packing problems $\max\{c^T x \colon Ax \leq 1, \, x \in \{0,1\}^n\}$, with $A \in \mathbb{R}_{\geq 0}^{m \times n}$. A way to solve such problems is via tightening the linear programming relaxation $P$ with Gomory \emph{cutting-planes}. The Gomory-closure $P'$ of $P$ is the intersection of $P$ with all its cutting planes. The optimization problem over $P'$ is NP-hard. Mastrolilli (2020) has shown that for fixed $ε>0$, the Lasserre hierarchy yields a polynomial-size convex but non-polyhedral extended formulation that approximates $P'$ up to a factor of $1+ε$. Our main…