A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem

Adil Erzin, Georgii Melidi, Stepan Nazarenko, Roman Plotnikov

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование


The Two-Bar Charts Packing Problem (2-BCPP) is to pack the bar charts (BCs) of two bars into the horizontal unit-height strip of minimal length. The bars may move vertically within the strip, but it is forbidden to change the order and separate the chart’s bars. Recently, for this novel issue, which is a generalization of the Bin Packing Problem (BPP), Strip Packing Problem (SPP), and 2-Dimensional Vector Packing Problem (2-DVPP), several approximation algorithms with guaranteed estimates have been proposed. However, after a preliminary analysis of the solutions constructed by approximation algorithms, we discerned that the guaranteed estimates are inaccurate. This fact inspired us to conduct a numerical experiment in which the approximate solutions are compared to each other and with the optimal ones. We use the Boolean Linear Programming (BLP) formulation of 2-BCPP proposed earlier and apply the CPLEX package to find the optimal solutions or lower bounds for optimum. We also use a database of instances for BPP with known optimal solutions to construct the instances for the 2-BCPP with known minimal packing length. The results of computational experiments comprise the main content of this paper.

Язык оригиналаанглийский
Название основной публикацииAdvances in Optimization and Applications - 12th International Conference, OPTIMA 2021, Revised Selected Papers
РедакторыNicholas N. Olenev, Yuri G. Evtushenko, Vlasta Malkova, Milojica Jacimovic, Michael Khachay
ИздательSpringer Science and Business Media Deutschland GmbH
Число страниц16
ISBN (печатное издание)978-3-030-92710-3
СостояниеОпубликовано - 2021
Событие12th International Conference on Optimization and Applications, OPTIMA 2021 - Virtual, Online
Продолжительность: 27 сент. 20211 окт. 2021

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том1514 CCIS
ISSN (печатное издание)1865-0929
ISSN (электронное издание)1865-0937


Конференция12th International Conference on Optimization and Applications, OPTIMA 2021
ГородVirtual, Online

Предметные области OECD FOS+WOS



Подробные сведения о темах исследования «A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).