Efficient Pre-Solve Algorithms for the Schwerin and Falkenauer_U Bin Packing Benchmark Problems for Getting Optimal Solutions with High Probability

Gyula Ábrahám, György Dósa, Tibor Dulai, Zsolt Tuza and Ágnes Werner-Stark
Additional contact information
Gyula Ábrahám: Faculty of Information Technology, University of Pannonia, Egyetem Str. 10, 8200 Veszprém, Hungary
György Dósa: Faculty of Information Technology, University of Pannonia, Egyetem Str. 10, 8200 Veszprém, Hungary
Tibor Dulai: Faculty of Information Technology, University of Pannonia, Egyetem Str. 10, 8200 Veszprém, Hungary
Zsolt Tuza: Faculty of Information Technology, University of Pannonia, Egyetem Str. 10, 8200 Veszprém, Hungary
Ágnes Werner-Stark: Faculty of Information Technology, University of Pannonia, Egyetem Str. 10, 8200 Veszprém, Hungary

Mathematics, 2021, vol. 9, issue 13, 1-21

Abstract: Bin Packing is one of the research areas of Operations Research with many industrial applications, as well as rich theoretical impact. In this article, the authors deal with Bin Packing on the practical side: they consider two Bin Packing Benchmark classes. These benchmark problems are often used to check the “usefulness”, efficiency of algorithms. The problem is well-known to be NP-hard. Instead of introducing some exact, heuristic, or approximation method (as usual), the problem is attacked here with some kind of greedy algorithm. These algorithms are very fast; on the other hand, they are not always able to provide optimal solutions. Nevertheless, they can be considered as pre-processing algorithms for solving the problem. It is shown that almost all problems in the considered two benchmark classes are, in fact, easy to solve. In case of the Schwerin class, where there are 200 instances, it is obtained that all instances are solved by the greedy algorithm, optimally, in a very short time. The Falkenauer U class is a little bit harder, but, here, still more than 91% of the instances are solved optimally very fast, with the help of another greedy algorithm. Based on the above facts, the main contribution of the paper is to show that pre-processing is very useful for solving such kinds of problems.

Keywords: bin packing; benchmark instances; greedy methods (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/13/1540/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/13/1540/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:13:p:1540-:d:586582

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().