Efficient Pre-Solve Algorithms for the Schwerin and Falkenauer_U Bin Packing Benchmark Problems for Getting Optimal Solutions with High Probability
| Autor: | Ágnes Werner-Stark, György Dósa, Zsolt Tuza, Gyula Abraham, Tibor Dulai |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
High probability
Class (set theory) greedy methods 021103 operations research Research areas Computer science Heuristic (computer science) Bin packing problem General Mathematics 0211 other engineering and technologies 02 engineering and technology bin packing benchmark instances 0202 electrical engineering electronic engineering information engineering Computer Science (miscellaneous) Benchmark (computing) QA1-939 020201 artificial intelligence & image processing Greedy algorithm Engineering (miscellaneous) Algorithm Mathematics |
| Zdroj: | Mathematics, Vol 9, Iss 1540, p 1540 (2021) Mathematics Volume 9 Issue 13 |
| ISSN: | 2227-7390 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|