Modified Integer Round-Up Property for the cutting stock problem

About 6 years old · traced to

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

min⁡∑p∈PCSPλp\min \sum_{p\in P_{CSP}}\lambda_p

subject to

∑p∈PCSPaipλp≥difor all i∈I,λp∈Z+for all p∈PCSP,\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.

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

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.