The Linear Ordering Problem with cumulative costs

Livio Bertacco, Lorenzo Brunetta and Matteo Fischetti

European Journal of Operational Research, 2008, vol. 189, issue 3, 1345-1357

Abstract: 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 [alpha]u associated with each item u, each defined as a linear combination of the values [alpha]v of all items v that follow u in the permutation. This setting implies a cumulative (nonlinear) propagation of the value of variables [alpha]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.

Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00606-6
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:189:y:2008:i:3:p:1345-1357

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().