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.

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, MAR 2016. (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, JUL 1 2016. (13/03447-6, 12/17585-9)