Approximate packing circles in a rectangular container: valid inequalities and nesting
A problem of packing a limited number of unequal circles in a fixed size rectangular container is considered. The aim is to maximize the (weighted) number of circles placed into the container or minimize the waste. This problem has numerous applications in logistics, including production and packing...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad Nacional Autónoma de México
2014
|
| Online Access: | http://eprints.uanl.mx/29776/7/29782.pdf |
| _version_ | 1838551022762459136 |
|---|---|
| author | Litvinchev, I. Ozuna, E.L. |
| author_facet | Litvinchev, I. Ozuna, E.L. |
| author_sort | Litvinchev, I. |
| collection | Repositorio Institucional |
| description | A problem of packing a limited number of unequal circles in a fixed size rectangular container is considered. The aim is to maximize the (weighted) number of circles placed into the container or minimize the waste. This problem has numerous applications in logistics, including production and packing for the textile, apparel, naval, automobile, aerospace and food industries. Frequently the problem is formulated as a nonconvex continuous optimization problem which is solved by heuristic techniques combined with the local search procedures. A new formulation is proposed based on using a regular grid approximated the container and considering the nodes of the grid as potential positions for assigning centers of the circles. The packing problem is then stated as a large scale linear 0-1 optimization problem. The binary variables represent the assignment of centers to the nodes of the grid. The resulting binary problem is then solved by the commercial software. Two families of valid inequalities are proposed to strengthening the formulation. Nesting circles inside one another is also considered. Numerical results are presented to demonstrate the efficiency of the proposed approach. |
| format | Article |
| id | eprints-29776 |
| institution | UANL |
| language | English |
| publishDate | 2014 |
| publisher | Universidad Nacional Autónoma de México |
| record_format | eprints |
| spelling | eprints-297762025-07-10T17:33:15Z http://eprints.uanl.mx/29776/ Approximate packing circles in a rectangular container: valid inequalities and nesting Litvinchev, I. Ozuna, E.L. A problem of packing a limited number of unequal circles in a fixed size rectangular container is considered. The aim is to maximize the (weighted) number of circles placed into the container or minimize the waste. This problem has numerous applications in logistics, including production and packing for the textile, apparel, naval, automobile, aerospace and food industries. Frequently the problem is formulated as a nonconvex continuous optimization problem which is solved by heuristic techniques combined with the local search procedures. A new formulation is proposed based on using a regular grid approximated the container and considering the nodes of the grid as potential positions for assigning centers of the circles. The packing problem is then stated as a large scale linear 0-1 optimization problem. The binary variables represent the assignment of centers to the nodes of the grid. The resulting binary problem is then solved by the commercial software. Two families of valid inequalities are proposed to strengthening the formulation. Nesting circles inside one another is also considered. Numerical results are presented to demonstrate the efficiency of the proposed approach. Universidad Nacional Autónoma de México 2014-08-01 Article PeerReviewed text en cc_by_nc_nd http://eprints.uanl.mx/29776/7/29782.pdf http://eprints.uanl.mx/29776/7.haspreviewThumbnailVersion/29782.pdf Litvinchev, I. y Ozuna, E.L. (2014) Approximate packing circles in a rectangular container: valid inequalities and nesting. Journal of Applied Research and Technology, 12 (4). pp. 716-723. ISSN 1665-6423 doi:10.1016/S1665-6423(14)70088-4 |
| spellingShingle | Litvinchev, I. Ozuna, E.L. Approximate packing circles in a rectangular container: valid inequalities and nesting |
| thumbnail | https://rediab.uanl.mx/themes/sandal5/images/online.png |
| title | Approximate packing circles in a rectangular container: valid inequalities and nesting |
| title_full | Approximate packing circles in a rectangular container: valid inequalities and nesting |
| title_fullStr | Approximate packing circles in a rectangular container: valid inequalities and nesting |
| title_full_unstemmed | Approximate packing circles in a rectangular container: valid inequalities and nesting |
| title_short | Approximate packing circles in a rectangular container: valid inequalities and nesting |
| title_sort | approximate packing circles in a rectangular container valid inequalities and nesting |
| url | http://eprints.uanl.mx/29776/7/29782.pdf |
| work_keys_str_mv | AT litvinchevi approximatepackingcirclesinarectangularcontainervalidinequalitiesandnesting AT ozunael approximatepackingcirclesinarectangularcontainervalidinequalitiesandnesting |