Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts

DOI10.1016/j.cor.2010.07.009zbMath1251.90282OpenAlexW1976513369MaRDI QIDQ1761944

Ali Khanafer, El-Ghazali Talbi, François Clautiaux

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2010.07.009

zbMATH Keywords

heuristicstabu searchcutting and packingtree-decompositionbin packing with conflicts

Mathematics Subject Classification ID

Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

Algorithms for the two dimensional bin packing problem with partial conflicts ⋮ A hybrid algorithm for constrained order packing ⋮ Bin Packing Problem with Time Lags ⋮ The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers ⋮ The min-conflict packing problem ⋮ Bin packing problem with conflicts and item fragmentation ⋮ On the benchmark instances for the bin packing problem with conflicts ⋮ Bin packing with directed stackability conflicts

Uses Software

• ParaDisEO
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for time constrained scheduling
• An introduction to timetabling
• Two-dimensional packing with conflicts
• New lower bounds for bin packing problems with conflicts
• An analytical model for the container loading problem
• An efficient tabu search approach for the 0-1 multidimensional knapsack problem
• Heuristics and lower bounds for the bin packing problem with conflicts
• Two-dimensional packing problems: a survey
• An approximation scheme for bin packing with conflicts
• Incidence matrices and interval graphs
• A new constraint programming approach for the orthogonal packing problem
• An exact method for graph coloring
• Exact Solution of the Two-Dimensional Finite Bin Packing Problem
• Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
• Algorithms for the Bin Packing Problem with Conflicts
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Two-Dimensional Finite Bin-Packing Algorithms
• Graph minors. II. Algorithmic aspects of tree-width
• Computing the Minimum Fill-In is NP-Complete
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms