Advanced search
Start date

Two-Dimensional Cutting Problems: Mathematical Formulations and Solution Methods

Grant number: 16/08039-1
Support type:Scholarships in Brazil - Doctorate
Effective date (Start): June 01, 2016
Effective date (End): September 30, 2018
Field of knowledge:Engineering - Production Engineering - Operational Research
Principal researcher:Reinaldo Morabito Neto
Grantee:Mateus Pereira Martin
Home Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
Associated research grant:13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry, AP.CEPID


This project addresses the Constrained Two-Dimensional Guillotine Cutting Problems (C2DCP). These problems are about to produce smaller rectangles (items or pieces), from larger rectangles (objects), by using cutting operations that split materials in two rectangles and respect the amount of times that the pieces may appear in the cutting patterns, without restriction on the number of stages. Although the C2DCP is present in some industrial environments, there are no records in the literature of mathematical formulations for this problem. This project proposes the development of mathematical programming models and solution methods for C2DCP. The C2DCP will be analyzed in the context of the following problems: Placement Problem, Cutting Stock Problem and Bin Packing Problem. Three solution strategies are proposed. The first strategy involves the development of a compact formulation for these problems to deal with small item and object sets. The second and third strategies involve larger sets of items and objects from the development of extensive formulations for these problems, in a Column Generation context. The second strategy deals with the development of a mathematical programming model to generate cutting patterns for C2DCP and the third strategy proposes the use of dynamic programming methods to generate these patterns. The development of mathematical models contributes to the research of solution methods to the problem, from the analysis of particular structures that allow the reformulation of the problem through decomposition or relaxation techniques. The robustness of the methods will be evaluated by computational experiments using instances of the literature, which also will be compared to other approaches.

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

Scientific publications (6)
(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)
MARTIN, MATEUS; MORABITO, REINALDO; MUNARI, PEDRO. A top-down cutting approach for modeling the constrained two- and three-dimensional guillotine cutting problems. Journal of the Operational Research Society, v. 72, n. 12, p. 2755-2769, DEC 2 2021. Web of Science Citations: 0.
MARTIN, MATEUS; OLIVEIRA, JOSE FERNANDO; SILVA, ELSA; MORABITO, REINALDO; MUNARI, PEDRO. Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm. EXPERT SYSTEMS WITH APPLICATIONS, v. 168, APR 15 2021. Web of Science Citations: 0.
MARTIN, MATEUS; MORABITO, REINALDO; MUNARI, PEDRO. Two-stage and one-group two-dimensional guillotine cutting problems with defects: a CP-based algorithm and ILP formulations. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, FEB 2021. Web of Science Citations: 0.
MARTIN, MATEUS; MORABITO, REINALDO; MUNARI, PEDRO. A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem. Computers & Operations Research, v. 115, MAR 2020. Web of Science Citations: 0.
MARTIN, MATEUS; BIRGIN, ERNESTO G.; LOBATO, RAFAEL D.; MORABITO, REINALDO; MUNARI, PEDRO. Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern. International Transactions in Operational Research, v. 27, n. 2 JULY 2019. Web of Science Citations: 2.
MARTIN, MATEUS; HOKAMA, PEDRO H. D. B.; MORABITO, REINALDO; MUNARI, PEDRO. The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, JUN 2019. Web of Science Citations: 1.

Please report errors in scientific publications list by writing to: