Full Text:   <2097>

CLC number: O221.7

On-line Access: 

Received: 2000-10-24

Revision Accepted: 2001-02-20

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3763

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2001 Vol.2 No.3 P.241-246

http://doi.org/10.1631/jzus.2001.0241


EXACT ALGORITHM FOR BIN COVERING


Author(s):  CHEN Feng, YAO En-yu

Affiliation(s):  Department of Applied Mathematics, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   chenfeng@math.zju.edu.cn

Key Words:  bin covering, column generation, branch-and-bound algorithm


Share this article to: More

CHEN Feng, YAO En-yu. EXACT ALGORITHM FOR BIN COVERING[J]. Journal of Zhejiang University Science A, 2001, 2(3): 241-246.

@article{title="EXACT ALGORITHM FOR BIN COVERING",
author="CHEN Feng, YAO En-yu",
journal="Journal of Zhejiang University Science A",
volume="2",
number="3",
pages="241-246",
year="2001",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2001.0241"
}

%0 Journal Article
%T EXACT ALGORITHM FOR BIN COVERING
%A CHEN Feng
%A YAO En-yu
%J Journal of Zhejiang University SCIENCE A
%V 2
%N 3
%P 241-246
%@ 1869-1951
%D 2001
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2001.0241

TY - JOUR
T1 - EXACT ALGORITHM FOR BIN COVERING
A1 - CHEN Feng
A1 - YAO En-yu
J0 - Journal of Zhejiang University Science A
VL - 2
IS - 3
SP - 241
EP - 246
%@ 1869-1951
Y1 - 2001
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2001.0241


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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2023 Journal of Zhejiang University-SCIENCE