Systems and Means of Informatics

2023, Volume 33, Issue 3, pp 61-75

EFFICIENCY OF THE REDUCTION ALGORITHMS IN THE BIN PACKING PROBLEM

  • E. B. Barashov
  • A. V. Egorkin
  • D. V. Lemtyuzhnikova
  • M. A. Posypkin

Abstract

The bin packing problem is a well-known combinatorial problem consisting in finding the minimum number of fixed-size bins to hold a given set of items with known weight. Despite its simple formulation, the problem is NP-hard and exact methods for its solution are often inefficient in practice. Therefore, the research and development of approximate methods for solving the bin packing problem is of great importance. The paper investigates a class of approximate algorithms consisting of the sequential application of reduction and one of four "greedy" algorithms. The effect of reduction on the quality of the solutions obtained and the running time of the methods under consideration is evaluated. The algorithms are compared on four data sets according to several criteria responsible for the quality of the obtained solutions and the time required to find them. The experimental study shows that the efficiency of the reduction varies widely and depends strongly on the problem coefficients.

[+] References (21)

[+] About this article