Analysis of a generalized Linear Ordering Problem via integer programming

Abstract

We study a generalized version of the linear ordering problem: Given a collection of partial orders represented by directed trees with unique root and height one, where each tree is associated with a nonnegative reward, the goal is to build a linear order of maximum reward, where the total reward is defined as the sum of the rewards of the trees compatible with the linear order. Each tree has a single root, and includes a distinguished element either as the root or as a leaf. There is a constraint about the position that the distinguished element has to occupy in the final order. The problem is NP-Hard, and has applications in diverse areas such as machine learning, discrete choice theory, and scheduling. Our contribution is two-fold. On the theoretical side, we formulate an integer programming model, establish the dimension of the convex hull of all integer feasible solutions, and infer several families of valid inequalities, including facet defining ones. On the computational side, we develop a branch-and-cut (B&C) algorithm that is competitive with state-of-the-art, generic B&C methods with respect to running time and quality of the solutions obtained. Through an extensive set of numerical studies, we characterize conditions of the model that result in a significant dominance of our B&C proposal.