Autor(es)

Isabel Méndez-Díaz and Gustavo Vulcano and Paula Zabala

URL Pública

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 …