Advances in Polyhedral Relaxations of the Quadratic Linear Ordering Problem

We report on results concerning the polyhedral structure of, and integer linear programming formulations for, the quadratic linear ordering problem. Specifically, we provide a deeper analysis of the characteristic equation system that takes part in the minimal description of the convex hull of its feasible solutions, and we determine an accessible description of a restricted and inextensible subset of the odd-cycle inequalities that induces facets of it. We also present an extended formulation in which the products of the linear ordering variables that share an index are linearized implicitly.

Article

Download

View PDF