Advanced search
Start date
Betweenand

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

Grant number: 19/12728-5
Support type:Research Grants - Visiting Researcher Grant - International
Duration: February 09, 2020 - February 22, 2020
Field of knowledge:Physical Sciences and Mathematics - Computer Science
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
Home 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)