This research project addresses variants of two-dimensional cutting and packing problems involving tetris-like items. In these problems, the items have shapes of tetrominoes and must be arranged without overlapping and completely inside a rectangular plate. The objective may be either to maximize the occupied area of the plate or to minimize one of the dimensions of the plate. Some real applications of these problems may include the cutting of fabric and leather, the stamping of metal sheets, the cutting of ceramic coating, the design of printed circuit boards and the layout of magazines, newspapers and internet pages. They consist in hard combinatorial optimization problems, and, to our knowledge, there are no studies in the literature that addressed these problems and that proposed mixed integer linear programming models to describe them. In this research project, we aim to develop mathematical programming models based on mixed integer linear programming to describe these problems, to implement them using modeling languages and optimization solvers, and to perform computational experiments with instances randomly generated and obtained from the available literature.
News published in Agência FAPESP Newsletter about the scholarship: