Applying mod-k-cuts for solving linear ordering problems

摘要

The linear ordering problem consists of finding an ordering of the nodes of the weighted complete digraph on n nodes such that the sum of the weights of the arcs compatible with the ordering is maximized. In this paper, we report about the usefulness of mod-k cuts in a branch-and-cut algorithm for solving linear ordering problems to optimality.