Abstract:
The quadratic linear ordering problem models a large number of applications in a variety of different domains. To solve it exactly, polyhedral methods have been proposed but their development is still in its beginning. Specifically, while it is evident that only a fraction of the triangle inequalities, which are most commonly known from the boolean quadric polytope, take part in a minimal linear description of the polytope associated with a canonical formulation of the quadratic linear ordering problem, it is broadly unclear to which of these inequalities this applies and how to distinguish them from the others. At the same time, these inequalities are essential to build strong polyhedral and semidefinite programming relaxations. Addressing these open questions and potentials, we reveal the desired combinatorial pattern that enables to identify the triangle inequalities which are facet-inducing and deduce a corresponding exact polynomial-time separation algorithm.
