A Hereditary Property of Cutting Plane Procedures
Abstract
Let K' denote the closure of a convex set K under a given cutting-plane procedure. The procedure satisfies the \emph{hereditary property} if F' = K' ∩ F for every face F of K. The property underlies inductive proofs of finite-rank and the polyhedrality of closures, and it is an admissibility requirement in abstract frameworks for cutting-plane procedures. Yet, it has not been studied systematically across well-known cutting-plane procedures. We establish two sufficient conditions for the property. The first applies to procedures that can be expressed as closures under intersection cuts from a family of lattice-free convex sets, when a single family realizes the closure of K and of each of its faces. It yields the hereditary property for the split, lift-and-project, Lovász--Schrijver, Sherali--Adams, and Lasserre closures, applied over general convex sets and for faces that need not be exposed. The second applies to procedures whose cuts are valid inequalities for Gomory's corner polyhedron, and it yields the hereditary property for the closure of Dantzig cuts derived from all bases. We complement these results with four classical procedures for which the hereditary property fails, namely the closure of Gomory's fractional cuts (derived from either all bases or feasible bases only), the mixed-integer Chvátal closure, the +-cut closure, and the closure of Dantzig cuts derived from feasible bases.
Related
- An Intersection Cutting Plane Algorithm for Chance-Constrained Programs with Finite Support
- DC decompositions and cutting-plane approximation: geometry and complexity
- A variational quantum eigensolver-based cutting plane framework for semidefinite programming problems
- Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
- The Liouville property for geometric graphs in the plane
BibTeX
@misc{cornuejols2026hereditary,
title = {{A Hereditary Property of Cutting Plane Procedures}},
author = {Gérard Cornuéjols and Vrishabh Patil},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02038},
eprint = {2609.02038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02038},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Hereditary Property of Cutting Plane Procedures
AU - Gérard Cornuéjols
AU - Vrishabh Patil
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02038
UR - https://arxiv.org/abs/2609.02038
AB - Let K' denote the closure of a convex set K under a given cutting-plane procedure. The procedure satisfies the \emph{hereditary property} if F' = K' ∩ F for every face F of K. The property underlies inductive proofs of finite-rank and the polyhedrality of closures, and it is an admissibility requirement in abstract frameworks for cutting-plane procedures. Yet, it has not been studied systematically across well-known cutting-plane procedures. We establish two sufficient conditions for the property. The first applies to procedures that can be expressed as closures under intersection cuts from a family of lattice-free convex sets, when a single family realizes the closure of K and of each of its faces. It yields the hereditary property for the split, lift-and-project, Lovász--Schrijver, Sherali--Adams, and Lasserre closures, applied over general convex sets and for faces that need not be exposed. The second applies to procedures whose cuts are valid inequalities for Gomory's corner polyhedron, and it yields the hereditary property for the closure of Dantzig cuts derived from all bases. We complement these results with four classical procedures for which the hereditary property fails, namely the closure of Gomory's fractional cuts (derived from either all bases or feasible bases only), the mixed-integer Chvátal closure, the +-cut closure, and the closure of Dantzig cuts derived from feasible bases.
ER -