The study of theoretical and practical combinatorial optimization problems applied...
One and two-dimensional bin packing with conflicts and unloading restrictions
A Combinatorial Branch-and-Bound Algorithm for the Bin Packing Problem
| Full text | |
| Author(s): |
Borges, Yulle G. F.
;
de Lima, Vinicius L.
;
Miyazawa, Flavio K.
;
Pedrosa, Lehilton L. C.
;
de Queiroz, Thiago A.
;
Schouery, Rafael C. S.
Total Authors: 6
|
| Document type: | Journal article |
| Source: | JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 48, n. 4, p. 28-pg., 2024-11-01. |
| Abstract | |
This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence of uncertain scenarios, of which only one is realized. For this problem, we propose approximation algorithms whose ratios are bounded by the square root of the number of scenarios times the approximation ratio for an algorithm for the vector bin packing problem. We also show how an asymptotic polynomial-time approximation scheme is derived when the number of scenarios is constant, that is, not a part of the input. As a practical study of the problem, we present a branch-and-price algorithm to solve an exponential set-cover model and a variable neighborhood search heuristic. Experiments show the competence of the branch-and-price in obtaining optimal solutions for about 59% of the instances considered, while the combined heuristic and branch-and-price optimally solved 62% of the instances considered. (AU) | |
| FAPESP's process: | 22/05803-3 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings |
| Grantee: | Reinaldo Morabito Neto |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 17/11831-1 - Algorithms and models for cutting and packing problems |
| Grantee: | Vinícius Loti de Lima |
| Support Opportunities: | Scholarships in Brazil - Doctorate (Direct) |