Fast Lifting Procedures for the Bin Packing Problem

Journal Article

Haouari, Mohamed . 2005

• Publication Online URL: Fast Lifting Procedures for the Bin Packing Problem
• Tags: Bin packing, Lower bounds, Dual feasible functions
• Magazine \ Newspaper: Discrete Optimization
• Issue Number: 3
• Volume Number: 2
• Pages: 201–218

Publication Abstract

In this paper, we investigate fast lower bounds for the deterministic one-dimensional bin packing problem. We present two variants of a general lifting procedure which aims at systematically tightening a given lower bound. We describe several enhancements which improve the efficiency of the proposed procedure. Extensive numerical experiments show that the proposed lifting procedures consistently improve lower bounds from the literature.