Modified Integer Round-Up Property for the cutting stock problem

Let PCSPP_{CSP} be the set of integer cutting patterns for the cutting stock problem, let aipa_{ip} denote the number of copies of item ii in pattern pp, and let did_i be the demand for item ii. The cutting stock problem is the integer set-covering model

minpPCSPλp\min \sum_{p\in P_{CSP}}\lambda_p

subject to

pPCSPaipλpdifor all iI,λpZ+for all pPCSP,\sum_{p\in P_{CSP}}a_{ip}\lambda_p\geq d_i \quad\text{for all }i\in I,\qquad \lambda_p\in\mathbb{Z}_+ \quad\text{for all }p\in P_{CSP},

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

Never refreshed

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.