Please wait a minute...
ZJUS-A
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  2001, Vol. 2 Issue (3): 241-246    DOI: 10.1631/jzus.2001.0241
Science & Engineering     
EXACT ALGORITHM FOR BIN COVERING
CHEN Feng, YAO En-yu
Department of Applied Mathematics, Zhejiang University, Hangzhou 310027, China
Download:     PDF (0 KB)     
Export: BibTeX | EndNote (RIS)      

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.

Key words： bin covering      column generation      branch-and-bound algorithm     
Received: 24 October 2000     
CLC:  O221.7  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
YAO En-yu
CHEN Feng
Cite this article:

CHEN Feng, YAO En-yu. EXACT ALGORITHM FOR BIN COVERING. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2001, 2(3): 241-246.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.2001.0241     OR     http://www.zjujournals.com/xueshu/zjus-a/Y2001/V2/I3/241

[1] Biao WU, En-yu YAO. Min-max partitioning problem with matroid constraint[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(10): 1446-1450.