EXACT ALGORITHM FOR BIN COVERING

CHEN Feng(Department of Applied Mathematics, Zhejiang University, Hangzhou 310027, China)  
YAO En-yu(Department of Applied Mathematics, Zhejiang University, Hangzhou 310027, China)  

Abstract:This paper presents a new arc flow model for the one-dimensional bin covering problem and an algorithm to solve the problem exactly through a branch-and-bound procedure and the technique of column generation. The subproblems occuring in the procedure of branch-and-bound have the same structure and therefore can be solved by the same algorithm. In order to solve effectively the subproblems which are generally large scale, a column generation algorithm is employed. Many rules found in this paper can improve the performance of the methods.
Keywords:bin covering, column generation, branch-and-bound algorithm

CLC Number:A  Document Code:O221.7

Reference:

[1]Assmann, S.F., Johnson, D.S., Kleitman, D.J. et al., 1984. On a dual version of the one-dimensional Bin packing problem. J. of Algorithms, 5:502-525.
[2]Chan, L., Simchi-Levi, D., Bramel, J., 1998. Worst case analyses, linear programming and the bin-packing problem. Mathematical Programming, 83:213-227.
[3]Csirik, J., Frenk, J.B.G., Galambos, G. et al., 1988. Online algorithmsfor a dual version of bin packing. Disc. Appl. Math., 21:163-167.
[4]Desrochers, M., Desrosiers, J., Solomon, M., 1992. A new optimization algorithm for thevehicle routing problem with time windows. Operations Research, 40:342-354.
[5]Hooffman, K.L., Padberg, M., 1993. Solving airline crew scheduling problems by branch-and-cut. Management Science, 39:657-682.
[6]Kojima, M., Mizuno, S., Yoshise, A., 1989. A primal-dual interior point method for linear programming, In: N.Meggido(ed.), Progress in Mathematical Programming. Springer-Verlag, New York, p. 29-47.
[7]Labbé, M., Laporte, G., Martello, S., 1995. An exact algorithm for the dual bin packing problem. Operations Research Letters, 17:9-18.
[8]Simchi-Levi, D., 1994. New worst-case results for the bin-packing problem. Naval Research Logistics, 41:579-585.
[9]Su, C.J., Yao, E.Y., 1999. On-line bin-covering problem with kernels. OR Transactions, 3(4): 71-78 (in Chinese, with English abstract).
[10]Vanderbeck, F., Laurence Wolsey, A., 1996. An exact algorithm for IP column generation. Operations Research Letters, 19:151-159.
[11]Vllerio de Carvalho, J.M., 1999. Exact solution of bin-packing problems using column gener ation and branch-and-bound. Annals of Operations Research ,86:629-659.

Received:2000 Oct. 24

Accepted:2001 Feb. 20

Published:2001 July 1