Modified Integer Round-Up Property for the cutting stock problem
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.