Advanced search
Start date

Cutting and Packing Problems: Practical and Theoretical Approaches


In this research project our goal is to contribute to the advancement of the Combinatorial Optimization field focusing, in particular, in cutting and packing problems.These problems were introduced by Kantorovich in 1939 and Brooks et al. in 1940 with applications in the industry in mind and are very common in situations where it is necessary to cut materials (as metal, glass, paper, etc) in smaller items in order to supply a specific demand or when it is necessary to load vehicles and containers. Other applications for packing and cutting problems include the scheduling of computational tasks and the dissemination of advertisements in web pages. Even though common, even simple versions of cutting and packing problems are NP-hard, that is, there is no algorithm for those problems which finds optimal solutions in polynomial time unless P=NP. Thus, in light of the practical importance of those problems, it is necessary to solve cutting and packing problems within an acceptable time limit, since that, in practice, it is very common that we have an urgency in the computation of the solution. Due to the complexity of the problems considered in this project, it is imperative to propose new heuristics, exact and approximation algorithms and to adapt techniques already utilized with success in other problems in order to obtain new baselines in the resolution of such problems. (AU)

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

Scientific publications (10)
(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)
FERNANDES, CRISTINA G.; FERREIRA, CARLOS E.; MIYAZAWA, FLAVIO K.; WAKABAYASHI, YOSHIKO. Prices of Anarchy of Selfish 2D Bin Packing Games. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, v. 30, n. 3, p. 355-374, . (13/03447-6, 16/23552-7, 16/01860-1, 15/11937-9)
LINTZMAYER, CARLA N.; MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; XAVIER, EDUARDO C.. Randomized approximation scheme for Steiner Multi Cycle in the Euclidean plane. THEORETICAL COMPUTER SCIENCE, v. 835, p. 134-155, . (16/23552-7, 16/21250-3, 17/22611-2, 15/11937-9, 16/01860-1)
QUEIROZ, THIAGO A.; BRACHT, EVANDRO C.; MIYAZAWA, FLAVIO K.; BITTENCOURT, MARCO L.. An extension of Queiroz and Miyazawa's method for vertical stability in two-dimensional packing problems to deal with horizontal stability. ENGINEERING OPTIMIZATION, v. 51, n. 6, p. 1049-1070, . (16/23552-7, 16/01860-1, 15/11937-9)
POVOA, MARCELO G.; XAVIER, EDUARDO C.. Approximation algorithms and heuristics for task scheduling in data-intensive distributed systems. International Transactions in Operational Research, v. 25, n. 5, p. 1417-1441, . (16/23552-7, 14/02104-0, 15/11937-9)
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)
BORGES, YULLE G. F.; SCHOUERY, RAFAEL C. S.; MIYAZAWA, FLAVIO K.; GRANELLI, FABRIZIO; DA FONSECA, NELSON L. S.; MELO, LUCAS P.. Smart energy pricing for demand-side management in renewable energy smart grids. International Transactions in Operational Research, v. 27, n. 6, . (16/23552-7, 13/21744-8, 15/11937-9, 16/01860-1)
WAINER, JACQUES; XAVIER, EDUARDO C.. A Controlled Experiment on Python vs C for an Introductory Programming Course: Student's Outcomes. ACM TRANSACTIONS ON COMPUTING EDUCATION, v. 18, n. 3, . (16/23552-7, 15/11937-9)
LINTZMAYER, CARLA NEGRI; MIYAZAWA, FLAVIO KEIDI; XAVIER, EDUARDO CANDIDO. Online circle and sphere packing. THEORETICAL COMPUTER SCIENCE, v. 776, p. 75-94, . (16/23552-7, 16/14132-4, 15/11937-9, 16/01860-1)
BORGES, YULLE G. F.; MIYAZAWA, FLAVIO K.; SCHOUERY, RAFAEL C. S.; XAVIER, EDUARDO C.. Exact algorithms for class-constrained packing problems. COMPUTERS & INDUSTRIAL ENGINEERING, v. 144, . (16/23552-7, 16/01860-1, 15/11937-9, 14/25892-4)
YUCRA QUISPE, KENT E.; LINTZMAYER, CARLA N.; XAVIER, EDUARDO C.. An exact algorithm for the Blocks Relocation Problem with new lower bounds. Computers & Operations Research, v. 99, p. 206-217, . (16/23552-7, 16/14132-4, 15/11937-9)

Please report errors in scientific publications list by writing to: