New bin packing fast lower bounds. (English) Zbl 1127.90055

Crainic, Teodor Gabriel; Perboli, Guido; Pezzuto, Miriam; Tadei, Roberto

Comput. Oper. Res. 34, No. 11, 3439-3457 (2007).

Summary: We address the issue of computing fast lower bounds for the Bin Packing problem, i.e., bounds that have a computational complexity dominated by the complexity of ordering the items by non-increasing values of their volume. We introduce new classes of fast lower bounds with improved asymptotic worst-case performance compared to well-known results for similar computational effort. Experimental results on a large set of problem instances indicate that the proposed bounds reduce both the deviation from the optimum and the computational effort.

MSC:

90C27

Combinatorial optimization

Keywords:

bin packing; lower bounds

Software:

OR-Library; Bison

References:

[1]	Garey, M. R.; Johnson, D. S., Computers and intractability (1979), W. H. Freeman and Co.: W. H. Freeman and Co. New York, USA · Zbl 0411.68039
[2]	Chen, B.; Srivastava, B., An improved lower bound for the bin packing problem, Discrete Applied Mathematics, 66, 81-94 (1996) · Zbl 0853.90094
[4]	Martello, S.; Toth, P., Knapsack problems—algorithms and computer implementations (1990), Wiley: Wiley Chichester, UK · Zbl 0708.68002
[5]	Martello, S.; Toth, P., Lower bounds and reduction procedures for the bin packing problem, Discrete Applied Mathematics, 28, 1, 59-70 (1990) · Zbl 0704.90074
[6]	Fekete, S. P.; Schepers, J., New classes of lower bounds for bin packing problems, Mathematical Programming, 91, 1, 11-31 (2001) · Zbl 1051.90020
[7]	Haouaria, M.; Gharbia, A., Fast lifting procedures for the bin packing problem, Discrete Optimization, 2, 201-218 (2005)
[8]	Labbé, M.; Laporte, G.; Mercure, H., Capacitated vehicle routing on trees, Operations Research, 39, 616-622 (1991) · Zbl 0736.90029
[9]	Coffman, E. G.; Garey, M. R.; Johnson, D. S., Bin packing approximation algorithms: a survey, (Hochbaum, D. S., Approximation algorithms for NP-hard problems (1997), PWS Publishing Company: PWS Publishing Company Boston, MA), 46-93
[10]	Bourjolly, J. M.; Rebetez, V., An analysis of lower bound procedures, Computers and Operations Research, 32, 3, 395-405 (2005) · Zbl 1077.90035
[12]	Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501
[13]	Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem—part ii, Operations Research, 11, 863-888 (1963) · Zbl 0124.36307
[14]	Vanderbeck, F., Computational study of a column generation algorithm for bin packing and cutting stock problems, Mathematical Programming, 86, 3, 565-594 (1999) · Zbl 0949.90066
[15]	Scholl, A.; Klein, R.; Jürgens, C., Bison: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers and Operations Research, 24, 7, 627-645 (1997) · Zbl 0882.90113
[16]	Schwerin, P.; Wäscher, G., The bin-packing problem: a problem generator and some numerical experiments with ffd packing and mtp, International Transactions in Operational Research, 4, 5/6, 377-389 (1997) · Zbl 0906.90151
[17]	Wäscher, G.; Gau, T., Heuristics for the integer one-dimensional cutting stock problem: a computational study, OR Spektrum, 18, 131-144 (1996) · Zbl 0853.90099
[18]	Beasley, J. E., Or-library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 11, 1069-1072 (1990)
[19]	Falkenauer, E., A hybrid grouping genetic algorithm for bin packing, Journal of Heuristics, 2, 1, 5-30 (1996)
[20]	Alvim, A. C.F.; Ribeiro, C. C.; Glover, F.; Aloise, D. J., A hybrid improvement heuristic for the one-dimensional bin packing problem, Journal of Heuristics, 10, 2, 205-229 (2004)
[21]	Chao, H.; Harper, M. P.; Quong, R. W., A tight lower bound for optimal bin packing, Operations Research Letters, 18, 3, 133-138 (1995) · Zbl 0855.90102