The Modified Integer Round-Up Conjecture for bin packing (Scheithauer-Terno)
In one-dimensional bin packing (cutting stock), the Gilmore-Gomory configuration linear program assigns nonnegative weights to feasible bin patterns and minimizes their total subject to covering the item demands; its value is a lower bound for the optimum number of bins . The integer round-up property fails (Marcotte 1985-86), but all known instances satisfied . Scheithauer and Terno (1995, 1997) investigated this modified bound, now known as the Modified Integer Round-Up Conjecture. Does every bin packing instance satisfy ?
- Result
- Disproved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Bin packing and cutting stock; configuration LP integrality gap
- Posed by
- Guntram Scheithauer and Johannes Terno
- Year posed
- 1995
- Years open
- 31y
- Solved
- 2026-09-24
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 32 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: for every integer there are a finite rational instance , every item larger than (so at most five items per bin), and an integer with and ; the same LP value holds for the stronger formulation whose patterns are subsets of individual item copies. So the additive integrality gap of the configuration LP is unbounded and the Modified Integer Round-Up Conjecture is false. Not shown: a gap growing like in the instance size, matching the Hoberg-Rothvoss upper bound; the paper says it obtains no such lower bound.
What the AI did
The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region whose write-up was human-edited). The manuscripts are authored 'OpenAI' and name no human author. The family is a single manuscript, 'Additive hardness and unbounded configuration gaps in bin packing' (September 24, 2026); the same reduction also answers the additive-approximation question, entered separately.
Verification
No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the conjecture: for every it gives a rational instance with all sizes above , integral and ; taking contradicts the conjecture with no ceiling ambiguity. Lean: formalization.yaml lists comparator ComparatorChallenges/BinPackingGap.json, declaration OAI.BinPackingGap.main_results in OAI/Computability/BinPacking/Main.lean. The statement was read here: its first conjunct says that for every there are an instance with items, sizes in , , and both the individual-copy and the size-type configuration LP values equal to , the LPs being infima of fractional covers. That states the headline. Not rebuilt here. The instances come from a vertex-cover reduction and grow very fast with .
Sources
- Lean proofLean proof: OAI/Computability/BinPacking/Main.leanLean statement: ComparatorChallenges/BinPackingGap.lean
- CodeOpenAI math release: Additive hardness and unbounded configuration gaps in bin packing
- Problem recordScheithauer and Terno, The modified integer round-up property of the one-dimensional cutting stock problem (1995)