Advanced search
Start date
Betweenand

Modeling Techniques for Solving Combinatorial Optimization Problems

Grant number: 12/17585-9
Support Opportunities:Scholarships in Brazil - Post-Doctoral
Effective date (Start): November 01, 2012
Effective date (End): May 31, 2014
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
Principal Investigator:Cid Carvalho de Souza
Grantee:Alexandre da Silva Freire
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In several areas arise practical problems which can be stated as combinatorial optimization problems, such as transportation, industrial production, logistic, biological data analisis, etc. There is a wide literature about different modeling approaches for solving combinatorial optimization problems, such as Integer Linear Programming (ILP) and Constraint Programming (CP). These approaches have been successfuly applied for solving several NP-hard problems and, recently, it has been proposed in the literature new methods that unify the concepts of these two approaches. In this project, we present some combinatorial optimization problems for which we intend to develop ILP and CP models. We intend to investigate these problems from a theoretical point of view, by finding theoretical explanation to justify our approaches, and from a practical point of view, by making computational experiments in order to enable the practical use of our methods. These problems can be divided in two topics, being one of them the covering and packing problems in bipartite graphs, and the other one the matrix columns cover by extreme rays. We present applications of these problems in industrial production and biological data analisis, related results found in the literature, our preliminary results and the expected results. It is foreseen in our project a period of research abroad.

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

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)
CAMPELO, MANOEL; FREIRE, ALEXANDRE S.; LIMA, KARLA R.; MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. The convex recoloring problem: polyhedra, facets and computational experiments. MATHEMATICAL PROGRAMMING, v. 156, n. 1-2, p. 303-330, . (13/03447-6, 13/19179-0, 12/17585-9)
FREIRE, ALEXANDRE S.; MORENO, EDUARDO; YUSHIMITO, WILFREDO F.. A branch-and-bound algorithm for the maximum capture problem with random utilities. European Journal of Operational Research, v. 252, n. 1, p. 204-212, . (13/03447-6, 12/17585-9)

Please report errors in scientific publications list by writing to: cdi@fapesp.br.