The modified integer round-up property of the one-dimensional cutting stock problem

The modified integer round-up property of the one-dimensional cutting stock problem

0.00 Avg rating0 Votes
Article ID: iaor19981709
Country: Netherlands
Volume: 84
Issue: 3
Start Page Number: 562
End Page Number: 571
Publication Date: Aug 1995
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer
Abstract:

A linear integer minimization problem (IP) has the modified integer round-up property (MIRUP) if the optimal value of any instance of IP is not greater than the optimal value of the corresponding LP relaxation problem rounded up plus one. The aim of this paper is to investigate numerically whether the MIRUP holds for the one-dimensional cutting stock problem. The computational experiments carried out with a lot of randomly generated instances of the one-dimensional cutting stock problem show that for all instances an integer solution fulfills the MIRUP. Moreover, in most cases the optimal value equals the round-up optimal value of the corresponding LP relaxation. Similarly, the approach proposed to verify the MIRUP is usable as a new heuristic procedure for solving one-dimensional cutting stock problems. This heuristic always leads to very good solutions, being optimal in most cases.

Reviews

Required fields are marked *. Your email address will not be published.