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

Alberto Ceselli () and Giovanni Righini ()
Additional contact information
Alberto Ceselli: Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, 26013 Crema, Italy
Giovanni Righini: Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, 26013 Crema, Italy

Operations Research, 2008, vol. 56, issue 2, 425-436

Abstract: 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.

Keywords: combinatorial; optimization (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0415 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:56:y:2008:i:2:p:425-436

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().