EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
54. Bin Packing Problem with Conflicts and Item Fragmentation
Invited abstract in session WC-52: Heuristic Algorithms for Combinatorial Optimization Problems I (Contributed), stream Combinatorial Optimization.
Wednesday, 12:30-14:00Room: 8003 (building: 202)
Authors (first author is the speaker)
| 1. | Ali Ekici
|
| Industrial Engineering, Ozyegin University |
Abstract
In this study, we analyze a variant of the well-known Bin Packing Problem where items can be fragmented and some pairs of items cannot be packed into the same bin due to conflicts. The goal is to pack a given set of items into a minimum number of fixed-capacity bins while not packing fragments of conflicting items into the same bin. This problem is called the Bin Packing Problem with Conflicts and Item Fragmentation. We develop a lower bounding scheme based on identifying a maximal clique of the conflict graph for the problem and propose a heuristic algorithm called the Sequential Maximum Degree Packing Heuristic which sequentially packs the items starting from the highest degree item using a mixed-integer model. We test the proposed solution approach on the instances with random conflict graphs and compare its performance against that of the benchmark algorithms in the literature. We observe that our approach outperforms the benchmark algorithms especially when the conflict graph is dense. It provides solutions with up to 13% less optimality gap compared to the algorithms in the literature. Finally, the proposed lower bounding scheme improves the trivial continuous lower bound only if a large maximal clique of the conflict graph can be identified.
Keywords
- Cutting and Packing
- Combinatorial Optimization
- Algorithms
Status: accepted
Back to the list of papers