New lower bounds for bin packing problems with conflicts

DOI10.1016/j.ejor.2010.01.037zbMath1188.90214OpenAlexW2049071849MaRDI QIDQ976310

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

Publication date: 11 June 2010

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2010.01.037

zbMATH Keywords

lower boundschordal graphsKnapsack problemtree-decompositiondual-feasible functionsbin packing with conflicts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (17)

Vehicle scheduling under the warehouse-on-wheels policy ⋮ Algorithms for the two dimensional bin packing problem with partial conflicts ⋮ Lower and upper bounds for the bin packing problem with fragile objects ⋮ Bin Packing Problem with Time Lags ⋮ Determining the Minimum Number of Warehouses and their Space-Size for Storing Compatible Items ⋮ A Multi-start Tabu Search Based Algorithm for Solving the Warehousing Problem with Conflict ⋮ A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts ⋮ Conservative scales in packing problems ⋮ The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers ⋮ Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem ⋮ Just-in-time logistics for far-distant suppliers: scheduling truck departures from an intermediate cross-docking terminal ⋮ The min-conflict packing problem ⋮ Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts ⋮ Bin packing problem with conflicts and item fragmentation ⋮ Queue-constrained packing: a vehicle ferry case study ⋮ The minimum raster set problem and its application to the \(d\)-dimensional orthogonal packing problem ⋮ On the benchmark instances for the bin packing problem with conflicts

Cites Work

• Unnamed Item
• Approximation algorithms for time constrained scheduling
• A general framework for bounds for higher-dimensional orthogonal packing problems.
• New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation
• Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation
• Exact algorithms for the two-dimensional strip packing problem with and without rotations
• Knapsack problems with setups
• Packing problems
• Approximation algorithms for combinatorial problems
• The two-dimensional finite bin packing problem. I: New lower bounds for the oriented case
• Heuristics and lower bounds for the bin packing problem with conflicts
• Heuristics for the container loading problem
• Two-dimensional packing problems: a survey
• An improved typology of cutting and packing problems
• A new exact method for the two-dimensional orthogonal packing problem
• Exact Solution of the Two-Dimensional Finite 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
• New classes of fast lower bounds for bin packing problems

This page was built for publication: New lower bounds for bin packing problems with conflicts