Geodesic
Constructing an instance of the cutting stock problem of~minimum size which does not possess the integer round-up property
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 127-140.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2020_27_1_a6,
     author = {A. V. Ripatti and V. M. Kartak},
     title = {Constructing an instance of the cutting stock problem of~minimum size which does not possess the integer round-up property},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {127--140},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_1_a6/}
}
TY  - JOUR
AU  - A. V. Ripatti
AU  - V. M. Kartak
TI  - Constructing an instance of the cutting stock problem of~minimum size which does not possess the integer round-up property
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 127
EP  - 140
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_1_a6/
LA  - ru
ID  - DA_2020_27_1_a6
ER  - 
%0 Journal Article
%A A. V. Ripatti
%A V. M. Kartak
%T Constructing an instance of the cutting stock problem of~minimum size which does not possess the integer round-up property
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 127-140
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_1_a6/
%G ru
%F DA_2020_27_1_a6
A. V. Ripatti; V. M. Kartak. Constructing an instance of the cutting stock problem of~minimum size which does not possess the integer round-up property. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 127-140. http://geodesic.mathdoc.fr/item/DA_2020_27_1_a6/

[1] S. Baum, Jr. L. Trotter, “Integer rounding for polymatroid and branching optimization problems”, SIAM J. Algebraic Discrete Methods, 2:4 (1981), 416–425 | DOI | MR | Zbl

[2] M. Fieldhouse, “The duality gap in trim problems”, SICUP Bulletin, 5:4 (1990), 4–5

[3] “Counter-examples to the IRU property”, SICUP Bulletin, 12:3 (1994)

[4] P. C. Gilmore, R. E. Gomory, “A linear programming approach to the cutting-stock problem”, Oper. Res., 9:6 (1961), 849–859 | DOI | MR | Zbl

[5] V. M. Kartak, “Sufficient conditions for the integer round-up property to be violated for the linear cutting stock problem”, Autom. Remote Control, 65:3 (2004), 407–412 | DOI | MR | Zbl

[6] V. M. Kartak, A. V. Ripatti, G. Scheithauer, S. Kurz, “Minimal proper non-IRUP instances of the one-dimensional cutting stock problem”, Discrete Appl. Math., 187 (2015), 120–129 | DOI | MR | Zbl

[7] V. M. Kartak, A. V. Ripatti, “The minimum raster set problem and its application to the d-dimensional orthogonal packing problem”, Eur. J. Oper. Res., 271:1 (2018), 33–39 | DOI | MR | Zbl

[8] V. M. Kartak, A. V. Ripatti, “Large proper gaps in bin packing and dual bin packing problems”, J. Global Optim., 74:3 (2019), 467–476 | DOI | MR | Zbl

[9] O. Marcotte, “An instance of the cutting stock problem for which the rounding property does not hold”, Oper. Res. Lett., 4:5 (1986), 239–243 | DOI | MR | Zbl

[10] J. Rietz, S. Dempe, “Large gaps in one-dimensional cutting stock problems”, Discrete Appl. Math., 156:10 (2008), 1929–1935 | DOI | MR | Zbl

[11] J. Rietz, G. Scheithauer, J. Terno, “Families of non-IRUP instances of the one-dimensional cutting stock problem”, Discrete Appl. Math., 121:1 (2002), 229–245 | DOI | MR | Zbl

[12] J. Rietz, G. Scheithauer, J. Terno, “Tighter bounds for the gap and nonIRUP constructions in the one-dimensional cutting stock problem”, Optimization, 51:6 (2002), 927–963 | DOI | MR | Zbl

[13] A. V. Ripatti, V. M. Kartak, “Bounds for non-IRUP instances of Cutting Stock Problem with minimal capacity”, Mathematical Optimization Theory and Operations Research, Rev. Sel. Pap. 18th Int. Conf. (Ekaterinburg, Russia, July 8–12, 2019), Commun. Comput. Inform. Sci., 1090, Springer, Cham, 2019, 79–85 | DOI

[14] G. Scheithauer, J. Terno, “About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem”, Operations Research Proceedings 1991, Pap. 20th Annual Meeting DGOR (Hohenheim, Germany, Sept. 4–6, 1991), Springer, Heidelberg, 1992, 439–444 | DOI