Characterizing the optimality gap and the optimal packings for the bin packing problem

DOI10.1007/s11590-014-0789-8zbMath1317.90254MaRDI QIDQ2017826

Samir Elhedhli, Fatma Gzara

Publication date: 23 March 2015

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-014-0789-8

zbMATH Keywords

heuristics; Lagrangian relaxation; column generation; set covering; bin packing; set partitioning

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

Bin packing and cutting stock problems: mathematical models and exact algorithms

Uses Software

• Bison

Cites Work

• Exact solution of bin-packing problems using column generation and branch-and-bound
• BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem
• LP models for bin packing and cutting stock problems
• Ranking lower bounds for the bin-packing problem
• Heuristics for the integer one-dimensional cutting stock problem: A computational study
• Computational study of a column generation algorithm for bin packing and cutting stock problems
• A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting
• Using Extra Dual Cuts to Accelerate Column Generation
• A Linear Programming Approach to the Cutting-Stock Problem
• Dual-Optimal Inequalities for Stabilized Column Generation
• The Bin‐Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP
• A Linear Programming Approach to the Cutting Stock Problem—Part II