A Cutting Plane Algorithm for the Linear Ordering Problem

TLDR

The linear ordering problem is NP‑hard and arises in diverse applications such as matrix triangulation, scheduling, and preference aggregation, and its 0/1‑polytope facet structure has been previously studied. We present a new algorithm that leverages these facet‑structure insights. The algorithm employs a cutting‑plane method based on facet‑defining inequalities, augmented with heuristics and branch‑and‑bound techniques. Computational experiments show the algorithm outperforms existing solvers and can triangulate all input‑output matrices up to 60×60 within acceptable time.

Abstract

The linear ordering problem is an NP-hard combinatorial optimization problem with a large number of applications (including triangulation of input-output matrices, archaeological senation, minimizing total weighted completion time in one-machine scheduling, and aggregation of individual preferences). In a former paper, we have investigated the facet structure of the 0/1-polytope associated with the linear ordering problem. Here we report on a new algorithm that is based on these theoretical results. The main part of the algorithm is a cutting plane procedure using facet defining inequalities. This procedure is combined with various heuristics and branch and bound techniques. Our computational results compare favorably with the results of existing codes. In particular, we could triangulate all input-output matrices, of size up to 60 × 60, available to us within acceptable time bounds.