We report on results concerning the polyhedral structure of the quadratic linear ordering problem and its associated integer linear programming formulations. Specifically, we provide a deeper analysis of the characteristic equation system that partly describes the corresponding polytope, i.e., the convex hull of the feasible solutions to the quadratic linear ordering problem, and determine an accessible description of a restricted and inextensible subset of the odd-cycle inequalities that induces facets of it. Further, we present an extended formulation that provides a replacement for the commonly used linearization applied to products of linear ordering variables that share an index.
Article
View Advances in Polyhedral Relaxations of the Quadratic Linear Ordering Problem