Full Text:
<2373>
CLC number: O221.7
On-line Access:
Received: 2000-10-24
Revision Accepted: 2001-02-20
Crosschecked: 0000-00-00
Cited: 0
Clicked: 4271
EXACT ALGORITHM FOR BIN COVERING
| |||||||||||||
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.
[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>