Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:1, 196-204
Volume 27, No 1, 2020, P. 127-140
UDC 519.85
A. V. Ripatti and V. M. Kartak
Constructing an instance of the cutting stock problem of minimum size which does not possess the integer round-up property
Abstract:
We consider the well-known one-dimensional cutting stock problem in order to find some integer instances with the minimal length L of a stock material for which the round-up property is not satisfied. The difference between the exact solution of an instance of a cutting stock problem and the solution of its linear relaxation is called the integrality gap. Some instance of a cutting problem has the integer round-up property (IRUP) if its integrality gap is less than 1. We present a new method for exhaustive search over the instances with maximal integrality gap when the values of $L$, the lengths of demanded pieces, and the optimal integer solution are fixed. This method allows us to prove by computing that all instances with $L \le 15$ have the round-up property. Also some instances are given with $L=16$ not-possessing this property, which gives an improvement of the best known result $L=18$.
Tab. 2, bibliogr. 14.
Keywords: cutting stock problem, integer round-up property, integrality gap.
DOI: 10.33048/daio.2020.27.665
Artem V. Ripatti 1
Vadim M. Kartak 1
1. Ufa State Aviation Technical University,
12 Karl Marx Street, 450008 Ufa, Russia
e-mail: ripatti@inbox.ru, kvmail@mail.ru
Received June 27, 2019
Revised September 18, 2019
Accepted November 27, 2019
References
[1] S. Baum and L. Trotter, Jr., Integer rounding for polymatroid and branching optimization problems, SIAM J. Algebraic Discrete Methods 2 (4), 416–425 (1981).[2] M. Fieldhouse, The duality gap in trim problems, SICUP Bulletin 5 (4), 4–5 (1990).
[3] T. Gau, Counterexamples to the IRU property, SICUP Bulletin 12 (3) (1994).
[4] P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting-stock problem, Oper. Res. 9 (6), 849–859 (1961).
[5] V. M. Kartak, Sufficient conditions for the integer round-up property to be violated for the linear cutting stock problem, Automat. Remote Control 65 (3), 407–412 (2004).
[6.] V. M. Kartak, A. V. Ripatti, G. Scheithauer, and S. Kurz, Minimal proper non-IRUP instances of the one-dimensional cutting stock problem, Discrete Appl. Math. 187, 120–129 (2015).
[7] V. M. Kartak and A. V. Ripatti, The minimum raster set problem and its application to the $D$-dimensional orthogonal packing problem, Eur. J. Oper. Res. 271 (1), 33–39 (2018).
[8] V. M. Kartak and A. V. Ripatti, Large proper gaps in bin packing and dual bin packing problems, J. Global Optim. 74 (3), 467–476 (2019).
[9] O. Marcotte, An instance of the cutting stock problem for which the rounding property does not hold, Oper. Res. Lett. 4 (5), 239–243 (1986).
[10] J. Rietz and S. Dempe, Large gaps in one-dimensional cutting stock problems, Discrete Appl. Math. 156 (10), 1929–1935 (2008).
[11] J. Rietz, G. Scheithauer, and J. Terno, Families of non-IRUP Instances of the one-dimensional cutting stock problem, Discrete Appl. Math. 121 (1), 229–245 (2002).
[12] J. Rietz, G. Scheithauer, and J. Terno, Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem, Optimization 51 (6), 927–963 (2002).
[13] A. V. Ripatti and V. M. Kartak, Bounds for non-IRUP instances of cutting stock problem with minimal capacity, in Communications in Computer and Information Science, Vol. 1090: Rev. Sel. Pap. 18th Int. Conf., Ekaterinburg, Russia, July 8–12, 2019 (Springer, Cham, 2019), pp. 79–85.
[14] G. Scheithauer and J. Terno, About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem, in Operations Research (Proc. 20th Annual Meeting DGOR, Hohenheim, Germany, Sept. 4–6, 1991) (Springer, Heidelberg, 1992), pp. 439–444.
