An optimization algorithm for the ordered open-end bin-packing problem
成果类型：
Article
署名作者：
Ceselli, Alberto; Righini, Giovanni
署名单位：
University of Milan
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1070.0415
发表日期：
2008
页码：
425-436
关键词：
摘要：
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. xing. Computational results are presented on instances of different sizes and items with different correlations between their size and their position in the given order.