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

Abstract

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.

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, NOV 2017. (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, FEB 2021. (13/07375-0, 14/23900-0)

RODRIGUES, MARCOS OKAMURA; CHERRI, LUIZ HENRIQUE; MUNDIM, LEANDRO RESENDE; HOCHREITER, R. MIP models for the irregular strip packing problem: new symmetry breaking constraints. 12TH INTERNATIONAL CONFERENCE APPLIED MATHEMATICAL PROGRAMMING AND MODELLING-APMOD 2016, v. 14, p. 7-pg., 2017-01-01. (12/18653-8, 14/23900-0, 15/24987-4, 13/07375-0, 10/10133-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.