The Linear Ordering Problem with cumulative costs

The optimization problem of finding a permutation of a given set of items that minimizes a certain cost function is naturally modeled by introducing a complete digraph G whose vertices correspond to the items to be sorted. Depending on the cost function to be used, different optimization problems can be defined on G. The most familiar one is the min-cost Hamiltonian path problem (or its closed-path version, the Traveling Salesman Problem), arising when the cost of a given permutation only depends on consecutive node pairs. A more complex situation arises when a given cost has to be paid whenever an item is ranked before another one in the final permutation. In this case, a feasible solution is associated with an acyclic tournament (the transitive closure of an Hamiltonian path), and the resulting problem is known as the Linear Ordering Problem (LOP).In this paper we introduce and study a relevant case of LOP arising when the overall permutation cost can be expressed as the sum of terms αu associated with each item u, each defined as a linear combination of the values αv of all items v that follow u in the permutation. This setting implies a cumulative (nonlinear) propagation of the value of variables αv along the node permutation, hence the name Linear Ordering Problem with Cumulative Costs.We illustrate the practical application in wireless telecommunication system that motivated the present study.We prove complexity results, and propose a Mixed-Integer Linear Programming model as well as an ad hoc enumerative algorithm for the exact solution of the problem. A dynamic-programming heuristic is also described. Extensive computational results on large sets of instances are presented, showing that the proposed techniques are capable of solving, in reasonable computing times, all the instances coming from our application.