On the Reduced Raster Points for Cutting and Packing Problems

Favorite this paper
How to cite this paper?
Details
  • Presentation type: Trabalho completo (oral)
  • Track: 15. PM – Programação Matemática
  • Keywords: Cutting and packing problems; Grid of points; Reduced raster points;
  • 1 Universidade Estadual de Campinas
  • 2 Universidade Federal de Catalão

On the Reduced Raster Points for Cutting and Packing Problems

Thiago Alves de Queiroz

Universidade Federal de Catalão

Abstract

Cutting and packing problems involving rectangular-shaped items can be solved optimally with a set of points on which to pack items. Several authors have proposed sets, for example, the normal patterns, the reduced raster points, the regular normal patterns, and the meet-in-the-middle patterns. Many of these sets guarantee an optimal solution to the problem being solved. We investigate the set proposed in 1987, known as reduced raster points, for which we give a formal proof of optimality, demonstrate some properties, propose an efficient algorithm for computing it, and show experiments evidencing their effectiveness over other sets.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!