Extended Formulations and Total Dual Integrality in Combinatorial Optimization

Summary

This is the undergraduate thesis project page of the student Henri Michel França Oliveira. The project is develop under the supervision of Professor Marcel K. de Carli Silva.

The goal of this project is to investigate generalizations of the theory of total dual integrality to extended (linear programming) formulations of combinatorial optimization problems. The idea is to study a constellation of compact extended formulations, tools, and techniques to obtain those, as well as the theory of total dual integrality, and then strive to integrate these branches of combinatorial optimization, drawing on a notion of total dual integrality for extended formulations introduced by Kipp Martin.

This project was originally developed as an undergraduate research project, and it is funded by The São Paulo Research Foundation (FAPESP).

Proposal

The main goal of this research project is to explore and investigate how the fundamental theory of dual integrality generalizes in the context of compact extended formulations of combinatorial optimization problems. This research will contribute to the existing body of knowledge in the field of combinatorial optimization and has the potential to open up promising new research directions.

As it is emphasized in the introduction of the project, totally dual integral formulations play a central role in combinatorial optimization. These formulations establish min-max relations that underpin efficient algorithms for many fundamental problems. The project aims to explore the exciting tools and techniques that have recently emerged in the area of extended formulations and to integrate them with the concept of total dual integrality.

Throughout the course of this research project, several important topics were (or will be) be studied. These topics may include:

• the (facial) structure of polyhedra from combinatorial optimization;
• Balas' theorem for the union of polyhedra;
• compact extended formulations for the cut polytope, the perfect matching polytope, and the stable set polytope, for some families of graphs;
• the Edmonds-Giles theorem for totally dual integral systems;
• integral polyhedra and Hilbert bases;

By exploring these topics and conducting thorough research, this project aims to contribute to the existing knowledge base in fundamental branches of the field of combinatorial optimization, and to equip the applicant with valuable skills and expertise for his future academic and professional pursuits.