Paper Info
Title
An Optimization Algorithm for the Ordered Open-End Bin-Packing Problem
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.
Year
DOI
Venue
2008
10.1287/opre.1070.0415
Operations Research
Keywords
Field
DocType
different correlation,exact optimization,binary knapsack problem,bin-packing problem,optimization algorithm,branch-and-price algorithm,column generation algorithm,specialized optimization algorithm,open-end bin-packing problem,subgradient optimization step,ordered open-end bin-packing problem,different size,bin packing problem,combinatorial optimization
Column generation,Mathematical optimization,Subgradient method,Bin,Algorithm,Combinatorial optimization,Knapsack problem,Open system (systems theory),Mathematics,Bin packing problem,Binary number
Journal
Volume
Issue
ISSN
56
2
0030-364X
Citations 
PageRank 
References 
8
0.55
8
Authors
2
Name
Order
Citations
PageRank
Alberto Ceselli134130.53
Giovanni Righini252033.90