Standard

A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem. / Erzin, Adil; Melidi, Georgii; Nazarenko, Stepan et al.

Advances in Optimization and Applications - 12th International Conference, OPTIMA 2021, Revised Selected Papers. ed. / Nicholas N. Olenev; Yuri G. Evtushenko; Vlasta Malkova; Milojica Jacimovic; Michael Khachay. Springer Science and Business Media Deutschland GmbH, 2021. p. 201-216 (Communications in Computer and Information Science; Vol. 1514 CCIS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Erzin, A, Melidi, G, Nazarenko, S & Plotnikov, R 2021, A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem. in NN Olenev, YG Evtushenko, V Malkova, M Jacimovic & M Khachay (eds), Advances in Optimization and Applications - 12th International Conference, OPTIMA 2021, Revised Selected Papers. Communications in Computer and Information Science, vol. 1514 CCIS, Springer Science and Business Media Deutschland GmbH, pp. 201-216, 12th International Conference on Optimization and Applications, OPTIMA 2021, Virtual, Online, 27.09.2021. https://doi.org/10.1007/978-3-030-92711-0_14

APA

Erzin, A., Melidi, G., Nazarenko, S., & Plotnikov, R. (2021). A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem. In N. N. Olenev, Y. G. Evtushenko, V. Malkova, M. Jacimovic, & M. Khachay (Eds.), Advances in Optimization and Applications - 12th International Conference, OPTIMA 2021, Revised Selected Papers (pp. 201-216). (Communications in Computer and Information Science; Vol. 1514 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-92711-0_14

Vancouver

Erzin A, Melidi G, Nazarenko S, Plotnikov R. A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem. In Olenev NN, Evtushenko YG, Malkova V, Jacimovic M, Khachay M, editors, Advances in Optimization and Applications - 12th International Conference, OPTIMA 2021, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2021. p. 201-216. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-92711-0_14

Author

Erzin, Adil ; Melidi, Georgii ; Nazarenko, Stepan et al. / A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem. Advances in Optimization and Applications - 12th International Conference, OPTIMA 2021, Revised Selected Papers. editor / Nicholas N. Olenev ; Yuri G. Evtushenko ; Vlasta Malkova ; Milojica Jacimovic ; Michael Khachay. Springer Science and Business Media Deutschland GmbH, 2021. pp. 201-216 (Communications in Computer and Information Science).

BibTeX

@inproceedings{d80c8997d6fb499caa729c898564e5bd,
title = "A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem",
abstract = "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{\textquoteright}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.",
keywords = "Approximation algorithms, Bar charts, Simulation, Strip packing",
author = "Adil Erzin and Georgii Melidi and Stepan Nazarenko and Roman Plotnikov",
note = "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: {\textcopyright} 2021, Springer Nature Switzerland AG.; 12th International Conference on Optimization and Applications, OPTIMA 2021 ; Conference date: 27-09-2021 Through 01-10-2021",
year = "2021",
doi = "10.1007/978-3-030-92711-0_14",
language = "English",
isbn = "978-3-030-92710-3",
series = "Communications in Computer and Information Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "201--216",
editor = "Olenev, {Nicholas N.} and Evtushenko, {Yuri G.} and Vlasta Malkova and Milojica Jacimovic and Michael Khachay",
booktitle = "Advances in Optimization and Applications - 12th International Conference, OPTIMA 2021, Revised Selected Papers",
address = "Germany",

}

RIS

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 -

ID: 35244206