Advanced search
Start date

Combinatorial optimization: theory, formulations and applications

Grant number: 19/11702-2
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): August 01, 2019
Effective date (End): July 31, 2020
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Carlos Eduardo Ferreira
Grantee:Gabriel Morete de Azevedo
Home Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil


In this project we propose the study of topics in combinatorial optimization including graph theory, integer programming and some applications. In particular, we are interested with linear programming formulations: Given a matrix A m by n, and vectors b, with m real components, and c, with n real components, we want to find an vector x, with n real non-negative components, which maximizes the product cx subject to Ax less or equal to b. This formulation is very versatile and the are various efficient tools available to solve this models like Gurobi and Cplex. Many combinatorial optimization problems have interesting applications. One example is the Traveling Salesman Problem, which may be applied in assembly lines, one famous case was Siemens printed board circuits, which had a reduction in production by 35%. Other interesting problems are the shortest path in a graph, the minimum cut spanning tree and the resource management problem.

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