Automating Idealness Proofs for Binary Programs with Application to Rectangle Packing J. Fravel and R. Hildebrand were partially supported by AFOSR grant FA9550-21-1-0107. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessa

Jamie Fravel, Robert Hildebrand · 2026

Read Automating Idealness Proofs for Binary Programs with Application to Rectangle Packing J. Fravel and R. Hildebrand were partially supported by AFOSR grant FA9550-21-1-0107. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessa by Jamie Fravel, Robert Hildebrand (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-15252.txt.

Introduction

Jamie Fravel and Robert Hildebrand automate a tedious kind of proof in discrete optimization. Their 2026 arXiv paper deals with integer programs called ideal. A program is ideal when its continuous relaxation matches its convex hull, so it can be solved as a continuous problem.

That match brings large computational gains. But proving it by hand can take many pages of fine case analysis, even for small formulations. The authors build automated verification methods for such proofs. They apply the new methods to rectangle packing, a classic layout problem in operations research.

Catalog record

CREATORJamie Fravel, Robert Hildebrand
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE124 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-15252

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Automating Idealness Proofs for Binary Programs with Application to Rectangle Packing J. Fravel and R. Hildebrand were partially supported by AFOSR grant FA9550-21-1-0107. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the Air Force Office of Scientific Research. J. Fravel is also partially supported by Charles Univ. project PRIMUS 24/SCI/012 and by the project 25-17221S of GAČR. There are no relevant financial or non-financial competing interests to report. Jamie Fravel, Robert Hildebrand Abstract An integer program is called ideal if its continuous relaxation coincides with its convex hull allowing the problem to be solved as a continuous program and offering substantial computational advantages. Proving idealness analytically can be extraordinarily tedious—even for small formulations—such proofs often span many pages of intricate case analysis which motivates the development of automated verification methods. We develop a general-purpose framework for certifying idealness in Mixed Binary Linear Programs (MBLPs), formulating the verification problem as a linear program when the data is fixed and as a nonconvex quadratic program when the data is parametric. We apply this framework to study several formulations of the rectangle packing problem that are conjectured to be pairwise-ideal, obtaining computational proofs where analytic proofs were previously unknown or impractical. As our second contribution, we introduce and model a novel generalization of the rectangle packing problem that enforces edge clearances between selected rectangles. We present both existing and novel MBLP formulations which arise from different encodings of the underlying disjunctive constraints. We perform some computational experiments on these formulations under a strip-packing objective to determine the importance of pairwise-idealness in practice. Keywords: Integer Programming, Rectangle Packing, Layout, Disjunction, Computer-Aided Proof, Ideal Formulation. 1 Introduction In integer programming, the quality of formulation can have a profound impact on computational tractability. A formulation whose continuous relaxation is tight—meaning it closely approximates the convex hull of integer-feasible solutions—will yield a smaller branch-and-bound tree and a shorter run time. The strongest possible property a formulation can possess is idealness : when the continuous relaxation exactly equals the convex hull, the integer program can be solved as a continuous linear program and completely bypasses branch-and-bound, dramatically improving both solution speed, memory requirements and numerical stability. We formally define this property: Definition 1 (Ideal) . Consider a mixed-binary linear feasibility set P_{I}:=\left\{(\mathbf{x},\mathbf{y})\in\mathbb{R}^{n_{c}}\times\{0,1\}^{n_{b}}\colon A\big[\negthinspace\begin{smallmatrix}\mathbf{x}\\ \mathbf{y}\end{smallmatrix}\negthinspace\big]\geq\mathbf{b}\right\} and its continuous relaxation P:=\left\{(\mathbf{x},\mathbf{y})\in\mathbb{R}^{n_{c}}\times[0,1]^{n_{b}}\colon A\big[\negthinspace\begin{smallmatrix}\mathbf{x}\\ \mathbf{y}\end{smallmatrix}\negthinspace\big]\geq\mathbf{b}\right\}. We say the formulation P_{I} is ideal if \conv(P_{I})=P. Terminology We use the term ideal following the terminology of [ 48 ] while [ 8 ] use the equivalent term perfect . The related concept of locally ideal , introduced by [ 30 ] , refers to idealness of a formulation for a specific portion—usually near the optimum—of a larger optimization problem rather than the complete model. [ 45 ] provides an extensive discussion of this terminology and notes that “ideal comes from the fact that this is the strongest property we can expect from an MIP formulation.” A weaker but related notion is that of a sharp formulation, introduced by [ 18 ] , which requires only that the LP relaxation projects onto the convex hull of feasible solutions. Every locally ideal formulation is sharp, but the converse does not hold. Proving that a given integer program is ideal can be a difficult and tedious task, even for very small instances. As an example, the analytic proof of Theorem 1 (that a simple rectangle packing formulation is pairwise-ideal) is included in Appendix A . This proof is seven pages long. Additionally, no analytic proof of idealness is known for the more complicated formulations given in this paper (Theorems 2 and 4 ). The complexity of such proofs motivates our development methods to automate the process of identifying and proving idealness. Application: Rectangle Packing We demonstrate our idealness-proving framework on the rectangle packing problem , which asks how to arrange a collection of axis-aligned rectangles within a container region such that no two rectangles overlap. This fundamental geometric optimization problem arises across diverse application domains: in logistics and warehousing for pallet loading and container packing; in manufacturing for cutting stock optimization where raw materials must be cut into smaller pieces with minimal waste; in facilities planning for floor layout design; and in electronics for VLSI circuit design where components must be placed on a chip [ 11 , 25 ] . Mixed-integer linear programming provides a natural framework for modeling rectangle packing, but naive formulations typically rely on big- M constraints to encode the disjunctive non-overlapping requirements. Such programs are notorious for producing weak continuous relaxations which motivates the study of ideal formulations for this problem class. We apply our techniques to various mixed-binary models for the Rectangle Packing Problem 3 , obtaining computational proofs of idealness for formulations where analytic proofs were previously unknown or would require prohibitively complex case analysis. 1.1 Contributions We develop an optimization framework, which we call Ideal O’Matic ( 2 ), for identifying idealness in any Mixed Binary Linear Program (MBLP). 2 is linear when given specific, known input data for the underlying MBLP and is nonconvex quadratic (bilinear) over parametric input data. We say that a mixed-integer programming formulation for the rectangle packing is pairwise-ideal if it is ideal when applied to problem instances with only two rectangles. Ideal O’Matic is instrumental in obtaining the following: • A computational proof that the commonly used “Standard Unary” formulation is pairwise-ideal. There already exists an analytic proof of this result for the Floor Layout Problem up to a strict inequality [ 13 ] ; an adaptation of this proof to 3 is given in Appendix A . • A computational proof of pairwise-idealness for the “Refined Unary” formulation given by [ 13 ] , confirming their conjecture [ 13 , Conjecture 1] . • A novel counterexample of pairwise-idealness for the binary formulation originally described by Meller, Chen and Sherali [ 27 ] . • A novel modification of the binary formulation and a computational proof that the modified version is pairwise-ideal. Additionally, we perform several numerical experiments on these formulations to determine the importance of implementing a pairwise-ideal formulation in settings with large numbers of objects. We also vary the models by adding known symmetry-breaking inequalities, experimenting with the impact of Gurobi’s Cuts and Heuristics parameters and incorporating branching priorities. 1.2 Literature ILP for Proofs We find a few examples of integer programming being used to answer questions in theoretical mathematics. [ 23 ] use ILP to search for non-Hamiltonian, 4-regular, 1-tough graphs with sixteen and seventeen nodes; finding none, they confirm an existing conjecture. Our proof scheme follows similar logic. [ 9 ] use ILP to produce a proof that “Chvátal’s conjecture holds for all downsets whose union of sets contains seven elements or less.” Integer programming has also been used to find bounds on graph pebbling number [ 22 ] , and to support Frankl’s Conjecture [ 33 ] . Each of these papers use SCIP’s rational integer linear programming capabilities [ 10 ] to avoid floating-point/rounding errors. Unfortunately, SCIP is not yet capable of producing exact solutions to quadratically constrained integer programs—a feature which is vital to our own computational proofs. Ideal

Read the complete text