9 problems

Consider the cutting stock instances in the classes discussed in the source, their relaxation polyhedron, and the convex hull of their integer solutions. The near-integral relaxati…

In the cutting stock problem, let an AI instance be an instance from the AI class, and let its relaxation have a polyhedron integrality ratio measuring the closeness of the relaxat…

MIRUP conjecture. The Modified Integer Round Up Property holds for all instances of the CSP and BPP.

Consider the classical pattern-based formulation for the cutting-stock problem, viewed as a path-flow model obtained by Dantzig–Wolfe decomposition. Let $z_{lb}$ denote its optimal…

Let $P_{CSP}$ be the set of integer cutting patterns for the cutting stock problem, let $a_{ip}$ denote the number of copies of item $i$ in pattern $p$, and let $d_i$ be the demand…

Modified integer round-up conjecture. For every such instance,

Scheithauer's conjecture. The integer optimum satisfies

Let $z_{\rm IP}$ be the optimum of the integer linear programming formulation of a one-dimensional cutting stock instance and let $z_{\rm LP}$ be the optimum of its linear programm…

Scheithauer's conjecture. The general one-dimensional cutting stock problem has the modified integer round-up property.