The modified integer round-up conjecture for cutting stock
Fix a positive integer stock length $W$ and $n \ge 1$ item types; type $i$ has integer length $1 \le \ell_i \le W$ and positive integer demand $b_i$. A cutting pattern is a vector in $$\mathcal{P} = \Bigl\{a \in \mathbb{Z}_{\ge 0}^n : \sum_{i=1}^n \ell_i a_i \le W\Bigr\}.$$ Every capacity-feasible pattern is used: there is no restriction $a_i \le b_i$, so patterns may contain more copies of an item than its demand (nonproper patterns). Let $$z_{\mathrm{IP}} = \min\Bigl\{\sum_{a \in \mathcal{P}} x_a : \sum_{a \in \mathcal{P}} a_i x_a \ge b_i \ (1 \le i \le n),\ x \in \mathbb{Z}_{\ge 0}^{\mathcal{P}}\Bigr\}$$ be the minimum number of stock pieces needed to meet all demands, each use of a pattern counting as one piece, and let $z_{\mathrm{LP}}$ be the value of its linear relaxation, with $x \in \mathbb{R}_{\ge 0}^{\mathcal{P}}$ (the Gilmore–Gomory relaxation). There are instances with $z_{\mathrm{IP}} = \lceil z_{\mathrm{LP}} \rceil + 1$. Karmarkar and Karp's rounding bounds the additive gap $z_{\mathrm{IP}} - z_{\mathrm{LP}}$ by $O(\log^2 z_{\mathrm{IP}})$, and Hoberg and Rothvoss improved the bound to $O(\log z_{\mathrm{LP}})$.
Problem. Does every such instance, with arbitrary item types, lengths, stock length and demands, satisfy $$z_{\mathrm{IP}} \le \lceil z_{\mathrm{LP}} \rceil + 1?$$
Source: Scheithauer and Terno (1995, 1997), the modified integer round-up property (MIRUP). Stated by AIM — Open Applied Problems in the form of Franco da Silva, Loti de Lima, Schouery, Côté and Iori (2026), with nonproper patterns.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, bin packing, cutting stock problem, integrality gap
References
@article{scheithauer1995,
author = {Scheithauer, Guntram and Terno, Johannes},
title = {The modified integer round-up property of the one-dimensional cutting stock problem},
journal = {European J. Oper. Res.},
volume = {84},
number = {3},
year = {1995},
pages = {562--571},
doi = {10.1016/0377-2217(95)00022-I},
}
@article{scheithauer1997,
author = {Scheithauer, Guntram and Terno, Johannes},
title = {Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem},
journal = {Oper. Res. Lett.},
volume = {20},
number = {2},
year = {1997},
pages = {93--100},
doi = {10.1016/S0167-6377(96)00047-8},
}
@misc{francodasilva2026,
author = {Franco da Silva, Renan Fernando and Loti de Lima, Vin{\'i}cius and Schouery, Rafael C. S. and C{\^o}t{\'e}, Jean-Fran{\c{c}}ois and Iori, Manuel},
title = {Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances},
year = {2026},
eprint = {2604.05152},
archivePrefix = {arXiv},
}
@inproceedings{hoberg2017,
author = {Hoberg, Rebecca and Rothvoss, Thomas},
title = {A logarithmic additive integrality gap for bin packing},
booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)},
publisher = {SIAM},
year = {2017},
pages = {2616--2625},
doi = {10.1137/1.9781611974782.172},
eprint = {1503.08796},
archivePrefix = {arXiv},
}
@misc{aim-modified-integer-round-up,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The modified integer round-up conjecture for cutting stock}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/1b7c7fd251c1643bb41f0e3cef38704bcef410fd/problems/341-modified-integer-round-up.md},
note = {Entry 341 at commit 1b7c7fd, 2026-10-13},
}
Resolution claims
We disprove the Modified Integer Round-Up Conjecture for bin packing by constructing instances with arbitrarily large additive gaps between the configuration-LP value and the integral optimum. We also prove that, for every fixed nonnegative integer $c$, distinguishing instances that fit in $B$ bins from those requiring more than $B+c$ bins is NP-hard. Both results hold with rational item sizes greater …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: math @ 1581d4c, source/main.tex. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00697, "The modified integer round-up conjecture for cutting stock", clopen.solutions.