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 was developep under the supervision of Professors Marcel K. de Carli Silva and Mario Leston Rey

The goal of this work is to take the first steps towards possible generalizations of the classical theory of total dual integrality in the context of extended formulations, a notion that was originally introduced in 1991.

This work was originally developed as an undergraduate research project, and it was funded by The São Paulo Research Foundation (FAPESP), grant #2023/07025-0.

Proposal

The main goal of this work is to take the first steps towards possible generalizations of total dual integrality in the context of extended formulations. We call such a generalization extended total dual integrality. This work contributes to the existing body of knowledge in the field of combinatorial optimization and has the potential to open up promising new research directions.

The notion of totally dual integral formulations plays a central role in combinatorial optimization. These formulations establish min-max relations that underpin efficient algorithms for many fundamental problems. In this work, we explored the exciting tools and techniques that have recently emerged in the area of extended formulations, in an attempt to integrate them with the concept of total dual integrality.

Besides an in-depth study of many fundamental concepts and results on LP theory and combinatorial optimization, our primary focus was initiating the construction of a collection of compact extended formulations that are totally dual integral in the extended sense.

Throughout the course of this work, several important topics were covered. These topics include:

• the (facial) structure of polyhedra from combinatorial optimization;
• compact extended formulations for the cut polytope of planar graphs, the dominant of the r-arborescence polytope of digraphs, and the perfectly matchable subgraph polytope of bipartite graphs;
• the Edmonds-Giles theorem for totally dual integral systems;
• integral polyhedra and Hilbert bases;