The study of theoretical and practical combinatorial optimization problems applied on real scenarios

• Grant number: 19/12728-5
• Support Opportunities: Research Grants - Visiting Researcher Grant - International
• Duration: February 09, 2020 - February 22, 2020
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Flávio Keidi Miyazawa
• Grantee: Flávio Keidi Miyazawa
• Visiting researcher: Manuel Iori
• Visiting researcher institution: Università degli Studi di Modena e Reggio Emilia, Reggio Emilia (UNIMORE), Italy
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

In this research project, we aim to investigate combinatorial optimisation problems, both theoretical as well as practical problems, coming from real applications. The main research line is to investigate packing problems. In the bin packing problem, we have to pack a set of one-dimensional items, each one with a given weight, into bins of a given capacity. The items packed in a same bin cannot violate its capacity. The number of bins used to pack all items must be minimised. The bin packing problem is extensively studied in the literature, and has many practical applications, such as cutting and packing problems, scheduling of tasks, process allocation, among others. The bin packing problem admits an integer linear programming formulation based on set covering. A conjecture attests that the difference between the rounded value of the linear relaxation solution and the optimal solution of this formulation is at most one unit. Prof. Manuel Iori has important results on this conjecture and we hope to investigate and obtain new properties of the problem related to such conjecture. We will also investigate techniques for generating sets of discretisation points for cutting and packing problems. Sets of discretisation points are used in formulations based on the discretisation of the possible positioning of the items in the containers and a way to subdivide the problem into small subproblems. Such formulations are often considered for the bin packing problem, as well as for multidimensional cutting and packing problems. Prof. Iori has currently the best results on discretisation points and we hope to obtain new results with this collaboration. At last, Prof. Manuel Iori also investigate several problems that arise from industries and we hope to investigate at least one of them in this collaboration.Prof. Manuel Iori is an internationally renowned researcher and the resolution of several combinatorial optimisation problems. He is author of the state-of-the-art methods for discretisation points in packing problems as well state-of-the-art formulations for packing into bins and multiple knapsacks. His research scope is broad including research problems packing, routing, scheduling, computer theory, using exact, heuristic and algorithms based on artificial intelligence. (AU)

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)

DE LIMA, VINICIUS L.; ALVES, CLAUDIO; CLAUTIAUX, FRANCOIS; IORI, MANUEL; VALERIO DE CARVALHO, JOSE M.. Arc flow formulations based on dynamic programming: Theoretical foundations and applications. European Journal of Operational Research, v. 296, n. 1, p. 3-21, JAN 1 2022. (17/11831-1, 19/12728-5)

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)