Advanced search
Start date

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


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)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items

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

Please report errors in scientific publications list using this form.