Experimental and combinatorial optimization methods for the tropical subset problem on graphs

• Grant number: 21/07080-6
• Support Opportunities: Regular Research Grants
• Duration: October 01, 2021 - September 30, 2023
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Karla Roberta Pereira Sampaio Lima
• Grantee: Karla Roberta Pereira Sampaio Lima
• Host Institution: Escola de Artes, Ciências e Humanidades (EACH). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

The development of tools based on robust mathematical models to deal with real and computationally intractable problems has been increasingly aligned with combinatorial optimization techniques and integer linear programming due to the enormous technological advances and the need in the real world to deal with large volumes of data. These intractable problems emerge from medicine, bioinformatics, industry, logistics, and naturally appeal to computer science as a means to solve highly complex problems. Most computational problems involved in the analysis of biological data, for example, are difficult to solve, known as NP-hard problems, which a priori make researchers feel unmotivated and limited in their search for satisfactory results. On the other hand, the use of Combinatorial Optimization techniques in the analysis of such data in order to recognize certain structural patterns has provided great achievements in bioinformatics. In this project, we will investigate the problem of searching for specific structural patterns in networks that may represent biological interactions, such as metabolic, neurological, protein-protein interaction (PPI) networks, among others. The goals are to develop well-defined mathematical models, to implement each proposed model with the association of algorithmic techniques of polyhedral combinatorics, and to evaluate the quality of each model both from the theoretical standpoint, with the development of approximation algorithms, exact algorithms, construction of proofs of model correctness, and from the practical standpoint, with the implementation of the proposed models and algorithms in order to obtain optimal solutions for large real instances. The ultimate goal of the project is to deliver a tool based on integer linear programming and incorporating techniques and algorithms from combinatorial optimization that can be interpreted and made feasible for use in real bioinformatics problems. The project will be developed with the support of national and international collaborators, and master students of the proponent. (AU)