EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1930. On the box-total dual integrality of the perfect matching polytope

Invited abstract in session WB-25: Topics in Integer Programming II, stream Combinatorial Optimization.

Wednesday, 10:30-12:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Francesco Pisanu
LIPN, Université Sorbonne Paris Nord
2. Roland Grappe
Université Paris Dauphine
3. Mathieu Lacroix
LIPN, Université Sorbonne Paris Nord

Abstract

A rational linear system is totally dual integral (TDI) if for every integer linear function, the associated dual problem has an integer optimal solution whenever the optimum is finite. Following the definition, TDI systems with integer right-hand sides characterize integer polyhedra. A TDI system is box-TDI if adding any rational bounds on the variables (i.e., boxes) preserves its TDIness. Classical examples of box-TDI systems are those involved in the Max Flow-Min Cut Theorem of Ford and Fulkerson. In general, box-TDI systems are systems that yield strong min-max relations.

In the early 80s, W.J. Cook proved that any TDI system describing a polyhedron allowing a box-TDI description is also box-TDI. Thus, box-TDIness is a geometrical property, and any polyhedron that can be described by a box-TDI system is called a box-TDI polyhedron.

Recently, a graph characterization of the box-TDIness of the matching polytope has been released. However, this characterization is too restrictive for the perfect matching polytope (PMP). In this talk, we highlight the differences between the two cases and provide insights for tackling the problem of characterizing the box-TDIness of the PMP. We also show that deciding whether the PMP of a graph is box-TDI is equivalent to testing the box-TDIness of its affine hull, which implies that "Recognizing whether the perfect matching polytope of a given graph is box-TDI can be done in polynomial time."

Keywords

Status: accepted

Back to the list of papers