IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v189y2008i3p1345-1357.html
   My bibliography  Save this article

The Linear Ordering Problem with cumulative costs

Author

Listed:
  • Bertacco, Livio
  • Brunetta, Lorenzo
  • Fischetti, Matteo

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.

Suggested Citation

  • Bertacco, Livio & Brunetta, Lorenzo & Fischetti, Matteo, 2008. "The Linear Ordering Problem with cumulative costs," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1345-1357, September.
  • Handle: RePEc:eee:ejores:v:189:y:2008:i:3:p:1345-1357
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00606-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Biao Wu & Enyu Yao & Longcheng Liu, 2010. "A polynomially solvable case of optimal linear extension problem of a poset," Journal of Combinatorial Optimization, Springer, vol. 20(4), pages 422-428, November.
    2. Irène Charon & Olivier Hudry, 2010. "An updated survey on the linear ordering problem for weighted or unweighted tournaments," Annals of Operations Research, Springer, vol. 175(1), pages 107-158, March.
    3. Abraham Duarte & Manuel Laguna & Rafael Martí, 2011. "Tabu search for the linear ordering problem with cumulative costs," Computational Optimization and Applications, Springer, vol. 48(3), pages 697-715, April.
    4. J. Terán-Villanueva & Héctor Fraire Huacuja & Juan Carpio Valadez & Rodolfo Pazos Rangel & Héctor Puga Soberanes & José Martínez Flores, 2015. "A heterogeneous cellular processing algorithm for minimizing the power consumption in wireless communications systems," Computational Optimization and Applications, Springer, vol. 62(3), pages 787-814, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:189:y:2008:i:3:p:1345-1357. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.