The Linear Ordering Problem with cumulative costs

https://doi.org/10.1016/j.ejor.2006.03.071Get rights and content

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 α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.

Introduction

Several optimization problems require finding a permutation of a given set of items that minimizes a certain cost function. These problems are naturally modeled in graph-theory terms by introducing a complete (loopless) digraph G = (V, A) whose vertices v  V  {1,  , n} correspond to the n items to be sorted. By construction, there is a 1–1 correspondence between the Hamiltonian paths P = {(k1, k2),  , (kn−1, kn)} in G (viewed as arc sets) and the item permutations K=k1,,kn.

Depending on the cost function to be used, different optimization problems can be defined on G. The most familiar one arises when the cost of a given permutation K only depends on the consecutive pairs (ki, ki+1), i = 1,  , n  1. In this case, one can typically associate a cost cuv with each arc (u, v)  A, and the problem reduces to finding a min-cost Hamiltonian Path (HP) in G, a relative of the famous Traveling Salesman Problem (TSP) [10], [6]. Note however that this model is only appropriate when the overall cost is simply the sum of the “direct costs” of putting an item right after another in the final permutation. A more complex situation arises when a given cost guv has to be paid whenever item u is ranked before item v in the final permutation. In this case, a feasible solution can be more conveniently associated with an acyclic tournament, defined as the transitive closure of an Hamiltonian path P = {(k1, k2),  , (kn−1, kn)}:[P]{(ki,kj)A:i=1,,n-1,j=i+1,,n},see Fig. 1 for an illustration. The resulting problem then calls for a min-cost acyclic tournament in G, and is known as the Linear Ordering Problem (LOP) [3], [4], [5], [13]. Both HP and LOP are known to be NP-hard problems.

In some applications, both the HP and the LOP frameworks are unappropriate to describe the cost function. In this paper we introduce and study, for the first time, a relevant case 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. To be more specific, we address the following problem:

Definition 1.1 LOP-CC

Given a complete digraph G = (V, A) with non-negative node weights pv and non-negative arc costs cuv, the Linear Ordering Problem with Cumulative Costs (LOP-CC) is to find an Hamiltonian path P = {(k1, k2),  , (kn−1, kn)} and the corresponding node values αv that minimize the total costπ(P)=v=1nαvunder the constraintsαki=pki+j=i+1nckikjαkj,fori=n,n-1,,1.

Constraints (1) imply a cumulative “backward propagation” of the value of variables αv for v = n, n  1,  , 1, hence the name of the problem. We will also address a constrained version of the same problem, namely:

Definition 1.2 BLOP-CC

The Bounded Linear Ordering Problem with Cumulative Costs (BLOP-CC) is defined as the problem LOP-CC above, plus the additional constraints:αiUiV,where U is a given non-negative bound.

Notice that BLOP-CC can be infeasible. As shown in the next section, BLOP-CC finds important practical applications, in particular, in the optimization of mobile telecommunication systems.

As G is assumed to be complete, in the sequel we will not distinguish between an Hamiltonian path P = {(k1, k2),  , (kn−1, kn)} and the associated node permutation K=k1,,kn. Moreover, given any Hamiltonian path P = {(k1, k2),  , (kn−1, kn)}, we call direct all arcs (ki, ki+1)  P (the thick ones in Fig. 1), whereas the arcs (ki, kj) for j  i + 1 are called transitive (these are precisely the arcs in [P]⧹P, depicted in thin line in Fig. 1). Finally, we use notation π(P) to denote the cumulative cost of an Hamiltonian path P, defined as the LOP-CC cost π=v=1nαv of the corresponding permutation.

In this paper we introduce and study both problems LOP-CC and BLOP-CC. In Section 2, we give the practical application that motivated the present study and led to the patented new methodology for cellular phone management described in [2]. In Section 3, we show that both LOP-CC and BLOP-CC are NP-hard. A Mixed-Integer linear Programming (MIP) model is presented in Section 4, whereas an ad hoc enumerative method is introduced in Section 5. Extensive computational results on a large set of instances are presented in Section 6, whereas a dynamic-programming heuristic is also described and evaluated in Section 7. Some conclusions are finally drawn in Section 8.

Section snippets

Motivation

In this section we outline the practical problem that motivated the present paper; the interested reader is referred to [1], [9], [12] for more details.

In wireless cellular communications, mobile terminals (MTs) communicate simultaneously with a common Base Station (BS). In order to distinguish among the signals of different MTs, the Universal Mobile Telecommunication Standard (UMTS) [15] adopts the so-called code division multiple access technique, where each terminal is identified by a

Complexity of the LOP-CC

We start proving that the LOP-CC problem is NP-hard. We first give a simple outline of the proof, and then address in a formal proof the details required.

Our proof is by reduction from the following Hamiltonian Path problem, HP, which is known to be NP-complete.

Definition 3.1 HP

Given a digraph GHP = (VHP, AHP), decide whether GHP contains any directed Hamiltonian path.

Our reduction takes any HP instance GHP = (VHP, AHP) and computes the following LOP-CC instance 〈G = (V, A), p, c 〉:VVHP={1,,n};AV×V,pi1iVcij=Mif(i,j)

A MIP model

In this section we introduce a MIP model for BLOP-CC, derived from the LOP model of Grötschel, Jünger and Reinelt [3].

As already mentioned, in a standard Linear Ordering Problem we have n items to be placed in a convenient order. If we place item i before item j, we pay a cost of gij. The objective is to choose the item order that minimizes the total cost. This problem can then be modeled asmin(i,j)Agijxijsubject toxis the incidence vector of an acyclic tournment,where xij = 1 if item i is

An exact enumerative algorithm

Our enumerative algorithm is based on a standard backtracking technique (akin to those used in Constraint Programming) to generate all permutations and to find one with the lowest total cost. To limit the number of permutations actually evaluated, we use a pruning mechanism based on lower bounds.

Permutations are built progressively, and are extended backwards from the last node. At the root of the search tree (depth 0), none of the permutation elements in K=k1,,kn is fixed. At depth 1, the

Computational analysis of the exact methods

We have compared the performance of our exact enumerative algorithm with that of a state-of-the-art commercial MIP solver (ILOG-Cplex 9.0.2 [7]) applied to the MIP model of Section 4. The outcome of this experiment is reported in Table 1, where 4 large sets of BLOP-CC instances have been considered.

The instances used in our study have been provided by the telecommunications group of the Engineering School of the University of Padova, and are related to detection-order optimization in UMTS

Heuristics

We propose next a heuristic dynamic-programming solution scheme, based on the observation that the classic min-cost Hamiltonian path problem on small graphs can be solved very effectively by using dynamic programming [14]. Indeed, for the min-cost HP problem, a suitable dynamic-programming state is defined as the pair (S, h), where S is a non-empty node set and h  S. The optimal cost T(S, h) of a path starting from node h and visiting exactly once all the nodes in S can then be computed through

Conclusions

We have introduced and studied, for the first time, a new optimization problem related to the well-known Linear Ordering Problem, in which the solution cost is nonlinear due to a cumulative backwards propagation mechanism. This model was motivated by a practical application in UMTS mobile-phone telecommunication system.

We have formalized the problem, in two versions, and proved that they are both NP-hard. We have proposed a Mixed-Integer Linear Programming model as well as an ad hoc enumerative

Acknowledgements

Work supported by the MIUR PRIN research project Optimization, simulation and complexity in the design and management of telecommunication networks; and by the EU project ADONET (contract n. MRTN-CT-2003-504438). Thanks are due to Nevio Benvenuto, Giambattista Carnevale, and Stefano Tomasin for helpful discussions on the JOPCO methodology. We also thank Giovanni Rinaldi who suggested the use of a dynamic-programming approach.

References (15)

  • N. Benvenuto, G. Carnevale, S. Tomasin, Optimum power control and ordering in SIC receivers of uplink CDMA systems, in:...
  • N. Benvenuto et al.

    On the comparison between OFDM and single carrier modulation with a DFE using a frequency-domain feedforward filter

    IEEE Transactions on Communications

    (2002)
  • M. Grötschel et al.

    A cutting plane algorithm for the linear ordering problem

    Operations Research

    (1984)
  • M. Grötschel et al.

    On the acyclic subgraph polytope

    Mathematical Programming

    (1985)
  • M. Grötschel et al.

    Facets of the linear ordering polytope

    Mathematical Programming

    (1985)
  • ILOG Cplex 9.0: User’s Manual and Reference Manual, ILOG, S.A., 2004....
There are more references available in the full text version of this article.

Cited by (27)

  • Metaheuristics for the linear ordering problem with cumulative costs

    2012, European Journal of Operational Research
    Citation Excerpt :

    All the metaheuristics described in the previous sections were implemented in Java and experiments were conducted on a MacBook Pro computer with a 2.4 GHz Intel I3 processor and 4 GB of RAM. We have tested the procedure on three sets of instances previously reported (Bertacco et al., 2005; Duarte et al., 2011): UMTS Instances from the telecommunications group of the Engineering School of the University of Padova, related to detection-order optimization in UMTS networks, and previously reported in Bertacco et al. (2005).

  • An effective memetic algorithm for the cumulative capacitated vehicle routing problem

    2010, Computers and Operations Research
    Citation Excerpt :

    It consists in finding a tour on a given set of nodes which minimizes the sum of the elapsed times to reach the nodes, starting from a depot node. Various practical applications have been described in the literature: distribution, machine scheduling and even power-control and receiver optimization in wireless telecommunication systems [3]. Some articles take into account the returning time to the depot, which can modify the optimal solution.

  • Evaluating topological ordering in directed acyclic graphs

    2021, Electronic Journal of Graph Theory and Applications
View all citing articles on Scopus
View full text