The Linear Ordering Problem with cumulative costs
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 .
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 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)}: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 -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 costunder the constraints
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: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 . 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 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 -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 -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 -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 〉:
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 aswhere 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 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 -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:...
- 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) - et al.
A cutting plane algorithm for the linear ordering problem
Operations Research
(1984) - et al.
On the acyclic subgraph polytope
Mathematical Programming
(1985) - 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....
Cited by (27)
Comprehensive learning TLBO with recursive precedence-based solution construction and multilevel local search for the linear ordering problem
2024, Expert Systems with ApplicationsMetaheuristics for the linear ordering problem with cumulative costs
2012, European Journal of Operational ResearchCitation 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 ResearchCitation 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.
Exact and Heuristic Methods in Combinatorial Optimization: A Study on the Linear Ordering and the Maximum Diversity Problem: Second Edition
2022, Applied Mathematical Sciences (Switzerland)Evaluating topological ordering in directed acyclic graphs
2021, Electronic Journal of Graph Theory and Applications