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

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.


90C27 Combinatorial optimization


OR-Library; Bison
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.