Groupe d’études et de recherche en analyse des décisions

\(\{0,\frac{1}{2}\}\)-cuts and the Linear Ordering Problem: Surfaces that Define Facets

Samuel Fiorini Université libre de Bruxelles, Belgique

The maximum acyclic subgraph problem and its complementary problem, the minimum feedback arc set problem, are two central problems in combinatorial optimization. Both problems can be formulated as linear programs on the same polytope, namely, the linear ordering polytope. In this talk, we give new facet-defining inequalities for the linear ordering polytope generalizing the well-known Moebius ladder inequalities. Our starting point is to observe that the natural derivation of the Moebius ladder inequalities as \(\{0,\frac{1}{2}\}\)-Chvatal-Gomory cuts produces triangulations of the Moebius band and of the corresponding (closed) surface, the projective plane. In that sense, Moebius ladder inequalities have the same "shape" as the projective plane. Inspired by the classification of surfaces, a classic result in topology, we prove that a surface has facet-defining \(\{0,\frac{1}{2}\}\)-cuts of the same "shape" if and only if it is nonorientable.

Notes:

  • I will begin the talk by introducing another of my current research topics with applications to data compression.
  • Slides will be written in French.