Modified Integer Round-Up Property for the cutting stock problem
Let be the set of integer cutting patterns for the cutting stock problem, let denote the number of copies of item in pattern , and let be the demand for item . The cutting stock problem is the integer set-covering model
subject to
and its proper relaxation is obtained by relaxing the integrality constraints on the pattern variables. Modified Integer Round-Up Property (MIRUP). The difference between the optimal solution value of the cutting stock problem and the rounded-up optimal solution value of its proper linear relaxation is at most one. This property concerns the strength of the proper relaxation: it asserts that rounding its optimum up gives a value within one of the integer optimum, but the source does not state whether the property has been proved or disproved.
References
Primary source
Vinícius L. de Lima, Cláudio Alves, François Clautiaux, Manuel Iori and José M. Valério de Carvalho, “Arc Flow Formulations Based on Dynamic Programming: Theoretical Foundations and Applications”, arXiv:2010.00558 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.