Advanced search
Start date

Irregular and quasi-polyomino cutting and packing problems

Grant number: 14/23900-0
Support Opportunities:Scholarships in Brazil - Doctorate
Effective date (Start): March 01, 2015
Effective date (End): August 20, 2018
Field of knowledge:Engineering - Production Engineering - Operational Research
Principal Investigator:Franklina Maria Bragion de Toledo
Grantee:Marcos Okamura Rodrigues
Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
Associated research grant:13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry, AP.CEPID


A polyomino is a set of unit squares connected by joining one of their edges. A quasi-polyomino is a polyomino generalization, since it is a subset of not necessarily connected squares obtained from an equidistant raster grid. Quasi-polyominoes cutting and packing problems have many real applications, for instance, leather cutting, sheet metal stamping, printed circuit boards design and magazine and newspaper page layout. In this project, we will study quasi-polyominoes tiling, knapsack, strip packing and bin packing problems. We will propose mathematical models, exact and heuristic methods that will be compared with literature ones.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
RODRIGUES, MARCOS OKAMURA; TOLEDO, FRANKLINA M. B.. A clique covering MIP model for the irregular strip packing problem. Computers & Operations Research, v. 87, p. 221-234, . (13/07375-0, 10/10133-0, 14/23900-0, 13/14147-3)
RODRIGUES, MARCOS OKAMURA. Fast constructive and improvement heuristics for edge clique covering. DISCRETE OPTIMIZATION, v. 39, . (13/07375-0, 14/23900-0)
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
RODRIGUES, Marcos Okamura. Irregular and quasi-polyomino strip packing problems. 2020. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.

Please report errors in scientific publications list by writing to: