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/