Fast Lifting Procedures for the Bin Packing Problem

Journal Article

Haouari, Mohamed . 2005

• رابط المنشور على الويب: Fast Lifting Procedures for the Bin Packing Problem
• الوسوم: Bin packing, Lower bounds, Dual feasible functions
• المجلة \ الصحيفة: Discrete Optimization
• رقم العدد: 3
• رقم الإصدار السنوي: 2
• الصفحات: 201–218

مستخلص المنشور

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.