A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint

被引：0

作者：

Andrea Bettinelli

Alberto Ceselli

Giovanni Righini

机构：

[1] Università degli Studi di Milano,Dipartimento di Tecnologie dell’Informazione

来源：

Annals of Operations Research | 2010年 / 179卷

关键词：

Bin packing; Column generation; Branch-and-price;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

In this paper we consider a variation of the bin packing problem in which bins of different types have different costs and capacities. Furthermore, each bin has to be filled at least to a certain level, which depends on its type. We present a set partitioning formulation and an exact optimization algorithm which exploits column generation and specialized heuristics. We compare our algorithm with the general purpose solver ILOG CPLEX, running on two compact ILP formulations and we report on experimental results on instances we have generated from data-sets for the variable size bin packing problem.

引用

页码：221 / 241

页数：20

共 27 条

[1]

Alves C.(2007)Accelerating column generation for variable sized bin-packing problems European Journal of Operational Research 183 1333-1352

[2]

Valerio de Carvalho J. M.(2008)A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem Computers and Operations Research 35 1315-1328

[3]

Alves C.(2002)A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths European Journal of Operational Research 141 274-294

[4]

Valerio de Carvalho J. M.(2007)Ship scheduling with flexible Cargo sizes Journal of the Operational Research Society 58 1167-1177

[5]

Belov G.(2005)A local search based heuristic for the demand constrained multidimensional knapsack problem INFORMS Journal on Computing 17 82-98

[6]

Scheithauer G.(2001)Variable-sized bin packing: Tight absolute worst-case performance ratios for four approximation algorithms SIAM Journal on Computing 30 2069-2083

[7]

Brønmo G.(2008)Solving the variable size bin packing problem with discretized formulations Computers and Operations Research 35 2103-2113

[8]

Christiansen M.(1986)Variable sized bin packing SIAM Journal on Computing 15 222-230

[9]

Nygreen B.(1995)A 2 Operations Research 43 130-141

[10]

Cappanera P.(2003) constraint formulation for the capacitated minimal spanning tree problem European Journal of Operational Research 147 365-372

← 1 2 3 →