Paper Info
Title
DC programming and DCA for large-scale two-dimensional packing problems
Abstract
In this paper, we propose a global optimization method based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) involving cutting plane techniques for solving two-dimensional Bin packing and Strip packing problems. Given a set of rectangular items, we consider problems of allocating each item to larger rectangular standardized units. In two-dimensional bin packing problem, these units are finite rectangles, and the objective is to pack all the items into the minimum number of units. In two-dimensional strip packing problem, there is a single standardized unit of given width, and the objective is to pack all the items within the minimum height. These problems are characterized as BLP (Binary Linear Programming) problems. Thanks to exact penalty technique in DC Programming, the BLP can be reformulated as polyhedral DC program which can be efficiently solved via the proposed DC programming approach. Computational experiments on large-scale dataset involving up to 200 items show the good performance of our algorithm.
Year
DOI
Venue
2012
10.1007/978-3-642-28490-8_34
ACIIDS
Keywords
Field
DocType
binary linear programming,strip packing problem,two-dimensional strip packing problem,large-scale two-dimensional packing problem,larger rectangular standardized unit,polyhedral dc program,dc programming,two-dimensional bin packing problem,dc algorithm,two-dimensional bin packing,proposed dc programming approach
Cutting-plane method,Mathematical optimization,Packing problems,Global optimization,Computer science,Convex function,Set packing,Dc programming,Bin packing problem,Strip packing
Conference
Volume
ISSN
Citations 
7197
0302-9743
1
PageRank 
References 
Authors
0.34
8
4
Name
Order
Citations
PageRank
Babacar Mbaye Ndiaye142.07
Le Thi Hoai An2103880.20
Pham Dinh Tao31340104.84
Yi Shuai Niu4212.11