Advanced search
Start date

Algorithms and models for cutting and packing problems

Grant number: 18/19217-3
Support Opportunities:Scholarships abroad - Research Internship - Doctorate (Direct)
Effective date (Start): February 09, 2019
Effective date (End): August 08, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Flávio Keidi Miyazawa
Grantee:Vinícius Loti de Lima
Supervisor: Manuel Iori
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Research place: Università degli Studi di Modena e Reggio Emilia, Modena (UNIMORE), Italy  
Associated to the scholarship:17/11831-1 - Algorithms and models for cutting and packing problems, BP.DD


Cutting and Packing Problems are often considered as applications in the real world. Both classes of problems can be considered theoretically equivalent, as cutting an item from a recipient may be equivalent to placing an item into a bin. In this project, we consider orthogonal packing problems, mainly on their versions with two- and three-dimensions. These problems consider the placement of hyper-rectangles called items inside of larger hyper-rectangles called bins. Many of the packing problems presented in the literature can be solved by an algorithm that relies on a decision problem, that determines the existence of a feasible packing of items into a bin. This decision problem, referred to as orthogonal packing problem, is an NP-Complete problem, that has been extensively studied in the literature. To the best of our knowledge, the last survey on two-dimensional packing problems has been presented more than a decade ago. Since then, the literature has changed a lot, concerning two-dimensional packing problems. Therefore, one of the objectives of this project is to propose an extensive study on two-dimensional packing problems,aiming to write a survey addressing these problems. From this extensive study, we also aim to propose efficient algorithms and models for two- and three-dimensional packing problems, mainly for the Orthogonal Packing Problem, with the motivation that it can be used as a sub-routine to solve other problems. We intend to make an extensive computational study of the proposed methods, to analyze their efficiency, aiming to improve the results from the methods proposed in the literature. (AU)

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)
IORI, MANUEL; DE LIMA, VINICIUS L.; MARTELLO, SILVANO; MIYAZAWA, FLAVIO K.; MONACI, MICHELE. Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, v. 289, n. 2, p. 399-415, . (18/19217-3, 15/11937-9, 19/12728-5, 16/01860-1, 16/23552-7)

Please report errors in scientific publications list by writing to: