In recent years, GPU computing has become an increasingly important tool to develop efficient applications in several areas, including optimization. One of the optimization approaches that seems to take most advantage from GPU computing is dynamic programming. In this paper, we investigate the application of GPU computing to the two-dimensional guillotine cutting problem, solved by dynamic programming. We show a possible implementation and we discuss a number of technical issues. Computational results on test instances available in the literature and on new larger instances show the effectiveness of the dynamic programming approach based on GPU computing for this problem. Data, as supplemental material, are available at http://dx.doi.org/10.1287/ijoc.2016.0693.
Marco, A.B., Vittorio, M., Francesco, S. (2016). Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem. INFORMS JOURNAL ON COMPUTING, 28(3), 540-552 [10.1287/ijoc.2016.0693].
Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem
BOSCHETTI, MARCO ANTONIO;MANIEZZO, VITTORIO;STRAPPAVECCIA, FRANCESCO
2016
Abstract
In recent years, GPU computing has become an increasingly important tool to develop efficient applications in several areas, including optimization. One of the optimization approaches that seems to take most advantage from GPU computing is dynamic programming. In this paper, we investigate the application of GPU computing to the two-dimensional guillotine cutting problem, solved by dynamic programming. We show a possible implementation and we discuss a number of technical issues. Computational results on test instances available in the literature and on new larger instances show the effectiveness of the dynamic programming approach based on GPU computing for this problem. Data, as supplemental material, are available at http://dx.doi.org/10.1287/ijoc.2016.0693.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
