info:eu-repo/semantics/article
Analysis of a generalized Linear Ordering Problem via integer programming
Fecha
2019-12Registro en:
Méndez Díaz, Isabel; Vulcano, Gustavo; Zabala, Paula Lorena; Analysis of a generalized Linear Ordering Problem via integer programming; Elsevier Science; Discrete Applied Mathematics; 271; 12-2019; 93-107
0166-218X
CONICET Digital
CONICET
Autor
Méndez Díaz, Isabel
Vulcano, Gustavo
Zabala, Paula Lorena
Resumen
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.