Cutting and Packing Problems: Practical and Theoretical Approaches

• Grant number: 16/23552-7
• Support Opportunities: Regular Research Grants
• Start date: June 01, 2017
• End date: 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
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated 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

(16)

(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)

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. (16/23552-7, 16/21250-3, 17/22611-2, 15/11937-9, 16/01860-1)

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. (18/19217-3, 15/11937-9, 19/12728-5, 16/01860-1, 16/23552-7)

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. (16/23552-7, 16/01860-1, 15/11937-9)

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. (13/03447-6, 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, SEP 2018. (16/23552-7, 14/02104-0, 15/11937-9)

KOHAYAKAWA, YOSHIHARU; MIYAZAWA, FLAVIO KEIDI; WAKABAYASHI, YOSHIKO; BENDER, MA; FARACHCOLTON, M; MOSTEIRO, MA. A Tight Lower Bound for an Online Hypercube Packing Problem and Bounds for Prices of Anarchy of a Related Game. LATIN 2018: THEORETICAL INFORMATICS, v. 10807, p. 15-pg., 2018-01-01. (13/03447-6, 15/11937-9, 13/07699-0, 16/23552-7, 16/01860-1)

LINTZMAYER, CARLA NEGRI; MIYAZAWA, FLAVIO KEIDI; XAVIER, EDUARDO CANDIDO; BENDER, MA; FARACHCOLTON, M; MOSTEIRO, MA. Two-Dimensional Knapsack for Circles. LATIN 2018: THEORETICAL INFORMATICS, v. 10807, p. 14-pg., 2018-01-01. (15/11937-9, 16/14132-4, 16/23552-7, 16/01860-1)

RODRIGUES, FELIX CARVALHO; XAVIER, EDUARDO C.; SCHAFER, GUIDO. On Fair Cost Facility Location Games with Non-singleton Players. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 342, p. 18-pg., 2019-04-28. (15/11937-9, 16/23552-7)

DA SILVA, MAURO R. C.; SCHOUERY, RAFAEL C. S.; PEDROSA, LEHILTON L. C.. A Polynomial-time Approximation Scheme for the MAXSPACE Advertisement Problem. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 12-pg., 2019-08-30. (17/21297-2, 15/11937-9, 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, NOV 2019. (16/23552-7, 13/21744-8, 15/11937-9, 16/01860-1)

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. (16/23552-7, 16/14132-4, 15/11937-9, 16/01860-1)

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. (16/23552-7, 16/14132-4, 15/11937-9)

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. (16/23552-7, 16/01860-1, 15/11937-9, 14/25892-4)

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. (16/23552-7, 15/11937-9)

CREPALDI, THIAGO; DA FONSECA, NELSON L. S.; XAVIER, EDUARDO C.; IEEE. Selection of Servers for Video on Demand Service over Hybrid Cloud. 2018 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS (ICC), v. N/A, p. 7-pg., 2018-01-01. (15/11937-9, 16/23552-7)

LINTZMAYER, CARLA N.; MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; XAVIER, EDUARDO C.. Quasilinear Approximation Scheme for Steiner Multi Cycle in the Euclidean plane. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 13-pg., 2019-08-30. (15/11937-9, 17/22611-2, 16/23552-7, 16/01860-1, 16/21250-3)