CRIS Current Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishTwo dimensional cutting problems are about obtaining a set of rectangular items from a set of rectangular stock pieces and are of great relevance in industry, whenever a sheet of wood, metal or other material has to be cut. In this paper, we consider the 2-stage two-dimensional knapsack (2TDK) problem which requires finding the maximum profit subset of rectangular items obtainable through 2-stage guillotine cuts in a rectangular panel. We propose a formulation having a pseudopolynomial number of variables and constraints which can still be enumerated for the instances present in the literature. We compare the proposed formulation with the previous best known polynomial size one. Extensive computational experiments show that the new model is characterized by a stronger linear programming relaxation and can be effectively solved with a general-purpose MIP solver.
| Titolo: | A pseudo-polynomial size formulation for 2-stage 2-dimensional knapsack problems | |
| Autore/i: | Furini F.; Malaguti E. | |
| Autore/i Unibo: | ||
| Anno: | 2015 | |
| Titolo del libro: | Proceedings - CIE 45: 2015 International Conference on Computers and Industrial Engineering | |
| Pagina iniziale: | 833 | |
| Pagina finale: | 840 | |
| Abstract: | Two dimensional cutting problems are about obtaining a set of rectangular items from a set of rectangular stock pieces and are of great relevance in industry, whenever a sheet of wood, metal or other material has to be cut. In this paper, we consider the 2-stage two-dimensional knapsack (2TDK) problem which requires finding the maximum profit subset of rectangular items obtainable through 2-stage guillotine cuts in a rectangular panel. We propose a formulation having a pseudopolynomial number of variables and constraints which can still be enumerated for the instances present in the literature. We compare the proposed formulation with the previous best known polynomial size one. Extensive computational experiments show that the new model is characterized by a stronger linear programming relaxation and can be effectively solved with a general-purpose MIP solver. | |
| Data stato definitivo: | 1-mar-2022 | |
| Appare nelle tipologie: | 4.01 Contributo in Atti di convegno |
File in questo prodotto:
Copyright © 2022