Advanced search
Start date
Betweenand

Cutting and Packing Problems: Practical and Theoretical Approaches

Grant number: 16/23552-7
Support type:Regular Research Grants
Duration: June 01, 2017 - November 30, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Rafael Crivellari Saliba Schouery
Grantee:Rafael Crivellari Saliba Schouery
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Assoc. researchers:Eduardo Candido Xavier ; Flávio Keidi Miyazawa ; Lehilton Lelis Chaves Pedrosa

Abstract

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)

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)
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, MAR 1 2021. Web of Science Citations: 0.
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, OCT 2 2020. Web of Science Citations: 0.
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, JUN 2020. Web of Science Citations: 0.
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 NOV 2019. Web of Science Citations: 0.
LINTZMAYER, CARLA NEGRI; MIYAZAWA, FLAVIO KEIDI; XAVIER, EDUARDO CANDIDO. Online circle and sphere packing. THEORETICAL COMPUTER SCIENCE, v. 776, p. 75-94, JUL 12 2019. Web of Science Citations: 0.
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, JUN 3 2019. Web of Science Citations: 1.
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, APR 2019. Web of Science Citations: 0.
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, NOV 2018. Web of Science Citations: 4.
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, SEP 2018. Web of Science Citations: 0.
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 SEP 2018. Web of Science Citations: 0.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.