TY - GEN

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

AU - Erzin, Adil

AU - Melidi, Georgii

AU - Nazarenko, Stepan

AU - Plotnikov, Roman

N1 - Funding Information: The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. 0314–2019–0014). Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Bar charts

KW - Simulation

KW - Strip packing

UR - http://www.scopus.com/inward/record.url?scp=85121856920&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/11790349-451a-32d6-9e83-a312ebbd50f6/

U2 - 10.1007/978-3-030-92711-0_14

DO - 10.1007/978-3-030-92711-0_14

M3 - Conference contribution

AN - SCOPUS:85121856920

SN - 978-3-030-92710-3

T3 - Communications in Computer and Information Science

SP - 201

EP - 216

BT - Advances in Optimization and Applications - 12th International Conference, OPTIMA 2021, Revised Selected Papers

A2 - Olenev, Nicholas N.

A2 - Evtushenko, Yuri G.

A2 - Malkova, Vlasta

A2 - Jacimovic, Milojica

A2 - Khachay, Michael

PB - Springer Science and Business Media Deutschland GmbH

T2 - 12th International Conference on Optimization and Applications, OPTIMA 2021

Y2 - 27 September 2021 through 1 October 2021

ER -