Том 27, номер 1, 2020 г., Стр. 127–140

УДК 519.85
Рипатти А. В., Картак В. М.
Нахождение примера задачи линейного раскроя с минимальными размерами, для которого нарушается оптимальность при округлении вверх

Аннотация:
Рассматривается известная одномерная задача раскроя с целью найти целочисленные примеры с минимальным размером материала $L$, для которых не выполняется свойство округления вверх. Разрывом целочисленности называется разница между точным решением примера задачи раскроя и решением её линейной релаксации, и пример задачи раскроя обладает свойством округления вверх, если его разрыв целочисленности меньше 1. Предлагается новый метод поиска всех примеров с максимальным разрывом целочисленности для фиксированных значений $L$, длин заготовок и оптимального целочисленного решения. Данный метод позволяет вычислительно доказать, что все примеры с $L \le 15$ обладают свойством округления вверх. Также приведены несколько примеров c $L = 16$, не обладающих таким свойством, что даёт улучшение ранее известного результата $L = 18$.
Табл. 2, библиогр. 14.

Ключевые слова: задача раскроя, свойство округления вверх, разрыв целочисленности

DOI: 10.33048/daio.2020.27.665

Рипатти Артём Валерьевич¹
Картак Вадим Михайлович¹
1. Уфимский государственный авиационный технический университет,
ул. Карла Маркса, 12, 450008 Уфа, Россия
е-mail: ripatti@inbox.ru, kvmail@mail.ru

Статья поступила 27 июня 2019 г.
После доработки — 18 сентября 2019 г.
Принята к публикации 27 ноября 2019 г

Литература

[1] Baum S., Trotter Jr L. Integer rounding for polymatroid and branching optimization problems // SIAM J. Algebraic Discrete Methods. 1981. Vol. 2, No. 4. P. 416–425.

[2] Fieldhouse M. The duality gap in trim problems // SICUP Bull. 1990. Vol. 5, No. 4. P. 4–5.

[3] Gau T. Counter-examples to the IRU property // SICUP Bull. 1994. Vol. 12, No. 3.

[4] Gilmore P. C., Gomory R. E. A linear programming approach to the cutting-stock problem // Oper. Res. 1961. Vol. 9, No. 6. P. 849–859.

[5] Kartak V. M. Sufficient conditions for the integer round-up property to be violated for the linear cutting stock problem // Autom. Remote Control. 2004. Vol. 65, No. 3. P. 407–412.

[6] Kartak V. M., Ripatti A. V., Scheithauer G., Kurz S. Minimal proper non-IRUP instances of the one-dimensional cutting stock problem // Discrete Appl. Math. 2015. Vol. 187. P. 120–129.

[7] Kartak V. M., Ripatti A. V. The minimum raster set problem and its application to the $d$-dimensional orthogonal packing problem // Eur. J. Oper. Res. 2018. Vol. 271, No. 1. P. 33–39.

[8] Kartak V. M., Ripatti A. V. Large proper gaps in bin packing and dual bin packing problems // J. Global Optim. 2019. Vol. 74, No. 3. P. 467–476.

[9] Marcotte O. An instance of the cutting stock problem for which the rounding property does not hold // Oper. Res. Lett. 1986. Vol. 4, No. 5. P. 239–243.

[10] Rietz J., Dempe S. Large gaps in one-dimensional cutting stock problems // Discrete Appl. Math. 2008. Vol. 156, No. 10. P. 1929–1935.

[11] Rietz J., Scheithauer G., Terno J. Families of non-IRUP instances of the one-dimensional cutting stock problem // Discrete Appl. Math. 2002. Vol. 121, No. 1. P. 229–245.

[12] Rietz J., Scheithauer G., Terno J. Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem // Optimization. 2002. Vol. 51, No. 6. P. 927–963.

[13] Ripatti A. V., Kartak V. M. 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). Cham: Springer, 2019. P. 79–85. (Commun. Comput. Inform. Sci.; Vol. 1090).

[14] Scheithauer G., Terno J. 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). Heidelberg: Springer, 1992. P. 439–444.