×

Bin packing problems in one dimension: Heuristic solutions and confidence intervals. (English) Zbl 0636.90060

Summary: The one-dimensional bin packing problem has many applications to problems of data management, scheduling and resonance allocation. Very large examples of this problem are likely to exceed the limits of computational tractability, and in such circumstances the use of approximate (heuristic) methods is suggested. We adapt a variety of heuristic methods for generating feasible solutions, and the results are then used to generate confidence intervals for the (in practice unknown) value of the optimal solution. A large-scale computational study for randomly generated problems with prespecified optimal values suggests that these intervals are extremely narrow and are also highly likely to contain the optimal solution value. The interval estimation procedure seems to generate much better results for the bin packing problem than for other problems tested in the literature.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C09 Boolean programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Eilon, S.; Christofides, N., The loading problem, Mgmt Sci., 17, 259-268 (1971) · Zbl 0208.45701
[2] Brown, A. R., Optimum Packing and Depletion (1971), American Elsevier: American Elsevier New York · Zbl 0268.90034
[3] Coffman, E. G., Computer and Job-Shop Scheduling Theory (1976), Wiley: Wiley New York · Zbl 0359.90031
[4] Johnson, D. S., Fast algorithms for bin packing, J. Comput. Syst. Sci., 8, 272-314 (1974) · Zbl 0284.68023
[5] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-104 · Zbl 0366.68041
[6] Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco) · Zbl 0411.68039
[7] Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. Comput., 3, 299-325 (1974) · Zbl 0297.68028
[8] Johnson, D. S., Near-optimal bin packing algorithms, (Technical Report MAC TR-109, Project MAC (1973), Massachusetts Institute of Technology: Massachusetts Institute of Technology Cambridge, Mass)
[9] Ong, H. L.; Magazine, M. J.; Wee, T. S., Probabilistic analysis of bin packing heuristics, Opns Res., 32, 983-998 (1984) · Zbl 0551.90067
[10] Golden, B. L.; Alt, F. B., Interval estimation of a global optimum for large combinatorial problems, Naval Res. Log. Q., 26, 69-77 (1979) · Zbl 0397.90100
[11] Fisher, R.; Tippett, L., Limiting forms of the frequency distribution of the largest or smallest member of a sample, (Proc. Camb. Philosoph. Soc., 24 (1928)), 180-190 · JFM 54.0560.05
[12] Vasko, F. J.; Wilson, G. R., An efficient heuristic for large set covering problems, Naval Res. Log. Q., 31, 163-171 (1984) · Zbl 0534.90064
[13] Bruijs, P. A., On the quality of heuristic solutions to a 19 × 19 quadratic assignment problem, Eur. J. Opl Res., 17, 21-30 (1984) · Zbl 0538.90069
[14] Dannenbring, D. G., Procedures for estimating optimal solution values for large combinatorial problems, Mgmt Sci., 23, 1273-1283 (1977) · Zbl 0377.90051
[15] Garey, M. R.; Johnson, D. S., Approximation algorithms for bin packing problems: a survey, (Ausiello, G.; Lucertini, M., The Design and Analysis of Algorithms in Combinatorial Optimization (1981), Springer: Springer Berlin) · Zbl 0558.68062
[16] Harter, H. L.; Moore, A., Maximum likelihood estimation of the parameters of the gamma and Weibull populations from complete and from censored samples, Technometrics, 7, 639-643 (1965)
[17] Zanakis, S., Computational experience with some nonlinear optimization algorithms in deriving maximum likelihood estimates for the three-parameter Weibull distribution, TIMS Stud. Mgmt Sci., 7, 63-77 (1977)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.