This article is cited in 2 papers

Constructing an instance of the cutting stock problem of minimum size which does not possess the integer round-up property

A. V. Ripatti, V. M. Kartak

Ufa State Aviation Technical University, 12 Karl Marx Street, 450008 Ufa, Russia

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.

UDC: 519.85

Received: 27.06.2019
Revised: 18.09.2019
Accepted: 27.11.2019

DOI: 10.33048/daio.2020.27.665

 English version: Journal of Applied and Industrial Mathematics, 2020, 14:1, 196–204

Bibliographic databases:

•