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:
FERNANDES, CRISTINA G.;
FERREIRA, CARLOS E.;
MIYAZAWA, FLAVIO K.;
Prices of Anarchy of Selfish 2D Bin Packing Games.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE,
Web of Science Citations: 0.