Grids for cutting and packing problems: a study in the 2D knapsack problem
| Autor: | Vinícius Loti de Lima, Thiago Alves de Queiroz, Jéssica Gabriela de Almeida Cunha |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Integer linear programming model
Mathematical optimization 021103 operations research Computer science 0211 other engineering and technologies 02 engineering and technology computer.file_format Management Science and Operations Research Theoretical Computer Science Management Information Systems Reduction (complexity) Packing problems Computational Theory and Mathematics Knapsack problem 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Raster graphics computer |
| Zdroj: | 4OR. 18:293-339 |
| ISSN: | 1614-2411 1619-4500 |
| Popis: | Different grids of points to solve cutting and packing problems with rectangular shaped items are discussed in this work. The grids are the canonical dissections (also known as normal patterns), useful numbers, reduced raster points, regular normal patterns, and meet-in-the-middle patterns. Theoretical results involving the size and subset relations among the grids are proposed, besides practical procedures to reduce the size. Computational experiments are performed in which the two-dimensional (2D) knapsack problem is solved with an integer linear programming model. The results show the impact on the grids before and after applying the reduction procedures, concluding that the reduced raster points and meet-in-the-middle patterns are generally the grids with the smallest number of points. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink