This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ceselli, A. Articles by Righini, G. Search for Related Content

An Optimization Algorithm for the Ordered Open-End Bin-Packing Problem

Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, 26013 Crema, Italy
Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, 26013 Crema, Italy
ceselli{at}dti.unimi.it
righini{at}dti.unimi.it

The ordered open-end bin-packing problem is a variant of the bin-packing problem in which the items to be packed are sorted in a given order and the capacity of each bin can be exceeded by the last item packed into the bin. We present a branch-and-price algorithm for its exact optimization. The pricing subproblem is a special variant of the binary knapsack problem, in which the items are ordered and the last one does not consume capacity. We present a specialized optimization algorithm for this subproblem. The speed of the column generation algorithm is improved by subgradient optimization steps, allowing for multiple pricing and variable fixing. Computational results are presented on instances of different sizes and items with different correlations between their size and their position in the given order.

Subject classifications: combinatorial optimization.
History: Received December 2005; revision received October 2006; accepted January 2007.