Extended Formulations and Total Dual Integrality in Combinatorial Optimization

• Grant number: 23/07025-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2023
• End date: December 31, 2024
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Marcel Kenji de Carli Silva
• Grantee: Henri Michel França Oliveira
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

This is the research project for the undergraduate student Henri Michel França Oliveira, to be carried out at IME-USP under the supervision of Prof. Marcel K. de Carli Silva, from 01/Aug/2023 to 31/Jul/2024. The goal of the project is to investigate generalizations of the theory of total dual integrality to extended (linear programming) formulations of combinatorial optimization problems. The applicant will study a constellation of compact extended formulations, tools and techniques to obtain those, as well as the theory of total dual integrality. He will then strive to integrate these branches of combinatorial optimization, drawing on a notion of total dual integrality for extended formulations introduced by Kipp Martin. The comprehensive study material will equip Henri with key knowledge and skills to pursue a future Master's degree in the field.