Department of Social Systems and Management Discussion Paper Series No.1271 Lagrangian Relaxation and Pegging Test for Linear Ordering Problems by Noriyoshi SUKEGAWA, Yoshitsugu YAMAMOTO and Liyuan ZHANG May 2011 UNIVERSITY OF TSUKUBA Tsukuba, Ibaraki 305-8573 JAPAN
NORIYOSHI SUKEGAWA, YOSHITSUGU YAMAMOTO, AND LIYUAN ZHANG Abstract. We develop an algorithm for the linear ordering problem (LOP), which has a large number of applications such as triangulation of input-output matrices, minimizing total weighted completion time in one-machine scheduling, and aggregation of individual preferences. The algorithm is based on the Lagrangian relaxation of the binary integer linear programming formulation. Since the number of the constraints that should be relaxed is proportional to the cubed number of items and too large to handle, we propose a modified subgradient method that ignores a part of the constraints and gradually adds constraints whose Lagrangian multiplier vector is likely to be positive at the optimal solution. We also propose an improvement of the ordinary pegging test by using the problem structure. The information obtained from the improved pegging test is used in an attempt to get a good incumbent in an early stage of computation.
1. I NTRODUCTION
The problem we consider in this paper is to find a linear ordering of n items when their pairwise comparison data is given.  The data is given by an n×n matrix C := [ c ij ] such that its ( i, j )th element carries the amount of profit made when item i is ranked prior to item j . Choosing an appropriate matrix C lets the problem embrace ranking aggregation prob- lem, which is called Kemeny's problem, minimum violations ranking problem, and Slater's problem. See the survey paper by Charon and Hudry [8] and Reinelt [23]. The problem is formulated as a linear integer programming problem. The polytope being the convex hull of binary vectors each corresponding to a linear ordering was named linear ordering polytope and investigated by Grötschel et al. [16]. They introduced some facet-defining valid inequalities of the polytope, and proposed a linear-programming-relaxation-based al- gorithm for the problem in [15]. For subsequent research on the linear ordering polytope, see [4, 10, 18, 21]. Their approach was further extended by Mitchell and Borchers [19, 20], who proposed a cutting plane algorithm based on a primal-dual interior point method, and solved problems with as many as 250 items. Since the problem is an NP -hard problem, see e.g., Section 2 of [8], there have been proposed several heuristic methods, e.g., La- grangian heuristic method in [3], scatter search method in [5], linear ordering construction heuristics in [9], Goddard's method in [13], variable neighborhood local search method in [14]. Charon and Hudry [7] made an experiment of a branch-and-bound method with Lagrangian relaxation and some heuristics. The binary integer programming formulation of the linear ordering problem has an O(n 3 ) of inequality constraints. This feature makes the problem hard to solve. In this paper, we propose a Lagrangian relaxation algorithm that considers a small fraction of the inequality constraits and a pegging test that takes advantage of the problem structure. The algorithm is a combination of well-known and widely-used techniques of mathematical 1 optimization, however, it would be well worth reporting how they function together and how they make the algorithm efficient in an integrated manner. Throughout this paper we will use the following symbols:

2. Linear Ordering Problem
2.1. Ranking aggregation. Suppose we have several different rankings of n items, and want to aggregate them to a single ranking or a linear ordering.  If each ranking comes from the ratings of items, summing up the ratings that item i receives to its overall rating and sorting them for a final linear ordering is a possible and widely used method. Our starting point in this section is not the ratings of items but their rankings. One of the well-known method for aggregation of rankings is the Borda method which was first proposed in the 18th century. As Kemeny proposed in [17], a natural solution would be a linear ordering that is "close" to all given rankings. Let σ 1 , . . . , σκ, . . . , σκ be given rankings of items N . Let for α ∈ [0, 1]
where | · | denotes the cardinality of the corresponding set, and [ t ]+ = max{ t, 0}. The coefficient c (1) is a weighted difference of the number of rankings that put i above j and those that put i below j , and c (2) is the weighted sum of differences between the rankings of i and j . The parameter α should be determined according to which of "aye" and "nay" = (1/2) E is more important. When α = 1/2, c (2) 1 (σκ(j) - σκ(i)). Let π denote an aggregated linear ordering. The values c ( ν ) for ν = 1,2 shows how the linear ordering π and given rankings agree about the order of i and j when π(i) < π(j). Hence the overall degree of agreement would be given by
A linear ordering that maximizes this function should be accepted as the "closest" aggre- gated linear ordering, hence our problem is formulated as
which we will refer to as the Linear Ordering Problem. 2.2. Minimum violations ranking. Ali et al. [1] and Pedings et al. [22] proposed min- imum violations ranking. Suppose we are given a matrix D := [dij](i,j)∈ N 2 such that dij is the points by which team i beats team j in their matchup, where we take the convention that d ii = 0. They call this matrix a point differential matrix and introduce the following definition. Definition 2.1. A matrix D is in hillside form if (ascending order across rows) dki ≥ dki (descending order down columns) for all i, j, k ∈ N 3 such that i < j. They proposed to find such a hidden hillside form by a simultaneous reordering of rows and columns of the given point differential matrix D , and showed that the problem is formulated¹ as ( LOP ) in the previous section with the following objective function coefficient for α = 1/2 Another choice of the objective function coefficient would be
3. Formulation of Linear Ordering Problem 3.1. Quadratic Assignment Formulation. Let yki be the binary variable such that
Then these variables satisfy
and the total agreement is given by The quadratic assignment formulation is to maximize the total agreement under the as- signment constraints (3.1) and (3.2) together with the binary variable constraints. This is a well-known NP -hard problem and already a challenging problem when n = 25. See Çela [6].
3.2. Integer Linear Programming Formulation. The coefficient c ij provides the de- gree of agreement of a linear ordering π such that π( i ) < π( j ). For a given linear ordering π let binary variables x ij for ( i, j ) ∈ N 2 be defined as
then the linear ordering problem is formulated as
The point is that the problem has n ( n − 1) binary variables, n ( n − 1)/2 equality con- straints and n(n − 1)(n − 2)/3 inequality constraints, all of which grow very rapidly as n grows. 3.3. Variable reduction. Substituting 1 – x ij for x ji for all i,j ∈ N with i < j halves the decision variables and yields the following equivalent problem ( P ):
where
We will call the inequality constraint of the first half the tranisitivity constraint of type 1, and one of the latter half type 2 , and we will denote the optimal objective function value of (P) by ω(P).
4. RELAXATION
4.1. Relaxation of inequality constraints. A possible relaxation is to temporarily discard some of the inequality constraints. Namely let U and V be subsets of N 3 and solve
Clearly if the optimal solution of ( P ( U, V )) satisfies all the transitivity constraints, it is an optimal solution of problem ( P ). 4.2. Lagrangian Relaxation. Problem (P(U,V)) is still a difficult problem to solve unless no favorable structure can be assumed on U and V .  One of the common tricks to deal with the problem would be the Lagrangian relaxation.  Namely, introducing a nonnegative multiplier u ijk for each constraint of type 1 and also a nonnegative multiplier Vijk for each constraint of type 2, we consider the following integer linear programming with only a simple binary variable constraint:
Omitting U and V , we denote this problem simply by ( LR ( u, v )), where u and v denote multiplier vectors ( u ijk )(ijk )∈U and ( Vijk )(ijk )∈V , respectively. Let r( u,v)ij denote the coefficient of variable x ij in the objective function. It is written as
(LR(u, v)) can be obtained by
Furthermore, the optimal objective function value, which we will denote by ω( LR ( u, v )), provides an upper bound of the optimal objective function value ω( P ) of problem ( P ).
The following theorem is well known, see e.g., Geoffrion [12]. Theorem 5.1. Let ( ū, v ) := (( ū,jk)(i,j,k)∈N3, ( ū,jk)(i,j,k)∈N3 ) be a Lagrangian multiplier vector corresponding to all the transitivity constraints, and let x be an optimal solution of the Lagrangian relaxation problem of (P) with (ū,ī). If x is feasible to problem (P) and satisfies the complementarity condition
then it is an optimal solution of (P). Definition 5.2. We say that x satisfies the restricted complementarity condition with ( u, v ) when
We readily see the following corollary. Corollary 5.3. If an optimal solution x(u,v) of (LR(u,v)) is feasible to problem (P) and satisfies the restricted complementarity condition with ( u,v ), then it is an optimal solution of (P). Proof. We readily see that the Lagrangian relaxation problem ( LR ( u, v )) is an ordinary Lagrangian relaxation problem of problem ( P ) with multipliers ( ū, v ) such that
When x ( u, v ) meets the restricted complementarity condition with ( u, v ) in Definition 5.2, it also satisfies the complementarity condition for all constraints with ( ū, v ).  This together with the feasibility of x ( u, v ) yields the desired result. ■ A feasible solution of problem ( P ) that has the largest objective function value among the feasible solutions found thus far is called an incumbent solution , and its objective func- tion value is called an incumbent value. The difference of ω( LR( u, v)) and the incumbent value is called the duality gap.
6. P EGGING T EST
6.1. Ordinary pegging test. By the information obtained from the optimal solution x(u,v) of the Lagrangian relaxation problem ( LR(u,v)) we can see which variable takes one and which takes zero at the optimal solution of problem ( P ). Let us choose ( s, t ) ∈ N 2 and suppose that problem ( P ) has an optimal solution with x st = ξ for some ξ ∈ {0,1}. Then problem ( P ) with an additional constraint x st = ξ is equivalent to problem ( P ) in the sense that optimal values of the two problems coincide. Suppose further we have an incumbent value ωιον. Then clearly ω(P|xst = ξ) = ω(P) ≥ ωlow Since ( P ( U , V )) is a relaxation of problem ( P ), and it is further relaxed to ( LR( u, v )), we obtain ω(LR(u,v)|xst = ξ) ≥ ω(P(U,V)|xst = ξ) ≥ ω(P|xst = ξ), hence ω(LR(u,v)|xst = ξ) ≥ ωlow Lemma 6.1. Let ξ be either zero or one. If ω(LR(u,v)|x st = ξ) < ω low, then x st = 1 − ξ for any optimal solution of problem (P). Proof. Straightforward from the above discussion.
Suppose that we have an optimal solution æ( u, v ) of ( LR( u, v )) and that x( u, v ) st = 0. By a simple calculation we see that (6.1) ω(LR(u,v)|xst = 1) = ω(LR(u,v)) + r(u,v)st. Note that x ( u, v ) st = 0 implies r ( u, v ) st ≤ 0. In the same way we see that (6.2) ω(LR(u,v)|x st = 0) = ω(LR(u,v)) − r(u,v)st when x(u,v)st = 1. Note also that r(u,v)st > 0 in this case. Theorem 6.2. Let x ( u,v ) be an optimal solution of the Lagrangian relaxation problem (LR(u,v)). if ω(LR(u, v)) — ωlow < |r(u, v)st| holds, then x*t = x(u,v)st for any optimal solution x* of (P). Proof. Substituting equation (6.1) or (6.2) for the condition in Lemma 6.1 will yield the assertion. ■ We say that the variable x st is pegged at x ( u, v ) st when the case holds in the theorem. 6.2. Improved Pegging Test. As the computation goes, we will have several variables pegged. Let P 0 and P 1 denote the index sets of the variables that have been pegged at zero and one, respectively. Given a Lagrangian multiplier vector ( u, v ), the problem
is a relaxation problem of ( P ). Let A(P 0 , P 1 ) be the set of arcs ( i, j ) such that either x ij has been pegged at one or x ji has been pegged at zero, i.e., (6.3)
Definition 6.3. Given P 0 and P 1 and i,j ∈ N , we say that i is an ancestor of j and also that j is a descendant of i when there is a directed path from i to j on the arc set A(P 0 , P 1 ). Definition 6.4. Given (s,t) ∈ N 2 \ (P 0 ∪ P 1 ) let S1 := {s} ∪ { i ∈ N | is an ancestor of s }, T 1 := { t } ∪ { j ∈ N | j is a descendant of t } So := {s} ∪ { i ∈ N | i is a descendant of s }, T 0 := {t} ∪ { j ∈ N | j is an ancestor of t }. Take a variable x st that has not yet been pegged, i.e., (s,t) ∈ N 2 \ (P 0 U P 1 ), and fix x st temporarily to one. Then every ancestor of s should be an ancestor of every descendant of t by the transitivity. Namely, the variables must satisfy
to meet the transitivity constraint. When x st is fixed temporarily to zero, we have similarly
Now given nonnegative multiplier vectors u and v we define
sophisticate This is a relaxation problem of ( P ) with a temporary constraint x st = 1 added. Lemma 6.5.  If ((S1 × T1) ∩ N2 ∩ P0) ∪ ((T1 × S1) ∩ N2 ∩ P1) ≠ ∅, then x ≠ t = ∅ for any optimal solution x* of problem (P). Proof.  If there is an element, say ( i, j ), in the set (( S 1 × T 1 ) ∩ N ≥ ∩ ω (( T 1 × S 1 ) ∩ N ≥ ∩ l ), the variable x ij must be zero and one at the same time, which implies that there is no optimal solution of (P) with x st = 1. ■ When x st is temporarily fixed to zero, we have the following problem and lemma.
Lemma 6.6.  If ((To × So) ∩ N ≥ ∩ Po) ∪ ((So × To) ∩ N ≥ ∩ P 1 ) ≠ ∅, then x ≥ t = 1 for any optimal solution x* of problem (P). Since the problem ( LR( u, v, P 0 , P 1 ) | x st = ξ ) is a relaxation problem of ( P ) with a constraint x st = ξ added, we readily see the following lemma. Lemma 6.7. Let ξ be either zero or one, and let x st be a variable that has not been pegged, i.e., (s,t) ∈ N 2 \ (P 0 ∪ P 1 ).  If ω (LR(u,v,P 0 ,P 1 ) | x st = ξ) < ω low, then x st = 1 − ξ for any optimal solution of problem (P). We have seen in (6.1) and (6.2) that ω(LR(u,v)) − ω(LR(u,v)|xst = 1 − x(u,v)st) = |r(u,v)st| holds.  Namely, the objective function value deteriorates by | r ( u, v ) st | when the additional constraint x st = 1 − x ( u, v ) st is added to ( LR ( u, v )). In the similar manner we see that
where
The first subset of D corresponds to the variables that should be one but takes zero at x(u,v), and the second subset to those that should be zero but takes one at x(u,v). 6.3. Transitive Closure. As was seen in the previous section, it would be useful and save computation time to peg as many variables as possible. This can be done by computing the transitive closure of the directed graph consisting of node set N and arc set A(P 0 , P 1 ) The transitive closure of (N,A(P 0 , P 1 )) is a directed graph (N, A) such that of (6.3). ( i, j ) ∈ A if and only if there is a directed path from i to j in A( P 0 , P 1 ). Once we have made the transitive closure, the sets used in the improved pegging test are readily obtained by
We apply the well-known algorithm for computing the transitive closure proposed by Warshall in 1962, see e.g., Section 19.3 of Sedgewick [24]. 7. Subgradient Method for Lagrangian Dual Problem For the sake of simplicity we abbreviate ω( LR ( u, v, P 0 , P 1 )) to ω( u, v) in this section. Lagrangian dual problem, denoted by ( LD ), is a problem for finding the smallest upper bound of ω( P ). Namely, it searches for a nonnegative multiplier vector ( u, v ) that mini- mizes ω( υ, υ):
The function ω( u, v ) is piecewise linear convex and not differentiable on the intersection of pieces. One of the most widely used methods for this problem is the subgradient method. Definition 7.1. ( g " , g " ) is said to be a subgradient of ω at ( ū , v ) ≥ 0 when ω( ū, ʊ) + ⟨ g “, u – ū⟩ + ⟨ g๊, v – ʊ⟩ ≤ ω( u, v ) holds for any ( u, v ) ≥ 0, where 〈 , 〉 means the inner product. The following lemma is well known. Lemma 7.2.  Let x(u,v) denote an optimal solution of the Lagrangian relaxation problem (LR(u, v, P 0 , P 1 )).  Then (g u, g v) such that 9 ijk  = 1 − x(u,v)ij − x(u,v)jk + x(u,v)ik 9ijk := 0 + x(u, v)ij + x(u, v)jk − x(u, v)ik is a subgradient of ω at ( u, v ). We use the following rule to update the multiplier vector ( u,v ) to the next iterate ( u + , v +).
where μ is a step size control parameter initially set to 2 and ‖ · ‖ is the Euclidean norm. It is known that if ω 10w in the update formulas is replaced by the optimal value ω( P ), the sequence generated will converge to an optimal solution of the Lagrangian dual problem ( LD ), see e.g., [12].  However the value ω( u, v ) does not necessarily decrease when the multiplier vector is updated. We count the number of consecutive failures to decrease the value, and when it amounts to 5, we halve the step size control parameter μ . When μ falls below 0.005, we increment the constraint index sets U and V and reset μ to its initial value 2. See Section 9 for the details.
8. HEURISTICS FOR GOOD INCUMBENTS
For a given n × n binary matrix X := [ xij](ij)∈ N 2 let w i := ∑ j ∈ N xij − ∑ j ∈ N xji, row-column difference, for each i ∈ N . Ali et al. [1] showed the following lemma and used it in their linear ordering problem formulation. Lemma 8.1. Let X := [ xij](i.j)∈N2 be an n × n binary matrix with zero diagonal elements. Then { w 1 , w 2 , . . . , w n } ranges over { n − 1 , n − 3 , . . . , − ( n − 3), − ( n − 1)} if and only if X represents a linear ordering. When the matrix X satisfies the antisymmetry, i.e., x ji = 1 − x ij , the row-column difference w i could be replaced by the row sum r i := ∑ j ∈ N X ij , which is called the Copeland score. Corollary 8.2. Suppose that n × n binary matrix X := [ xij ](i,j) ∈ N 2 satisfies the antisym- metry and has zero diagonal elements.  Then the row sum ri := LjEN xij ranges over {n − 1,n − 2, . . . , 1,0} if and only if X represents a linear ordering. Proof. Since x ji = 1 − x ij , we see that w i = 2r i − n + 1 holds. Substituting this for w i in Lemma 8.1 completes the proof. ■ For a solution x(u,v) of (LR(u,v,P),P1)), let X := [ xij](i,j)€N2 be the matrix such that
It is reasonable to think that item with a larger value of r i should be ranked higher. However, r i may not accurately reflect the information about which variables are pegged, and it could happen that r i < r j even when x ij has been pegged at one or x ij at zero. The descending ordering of the values of r i may violate the order that we have known is met by every optimal solution. On the other hand, the transitive closure B of the arc set B := { (i,j) | (j,i) ∈ P 0 or (i,j) ∈ P 1 }. reflects P 0 and P 1 precisely. Namely, the row-column difference w i of its adjacency matrix satisfies ūẓ > wj if (j, i) ∈ P 0 or (i, j) ∈ P 1 . However, lots of row-column differences may fall into a tie before the pegged variables build up. For a pegged variable x ij , let δ ij be the difference of the positions of item i and j in the optimal linear ordering ñ, i.e., δί j := | ñ − 1 ( i ) − ñ − 1 ( j )|. Clearly for k = 1, 2, . . . , ñ − 1, there are ( n − k ) pairs such that δέj = k . We consider the variables pegged by the first application of the pegging test. Figure 1 is a scatter plot of |{ (i,j) E N 2 | δ ij = k, x ij is pegged by the first application of the pegging test } | n — k versus k for k = 1,2,...n — 1 for the data DsumC of n = 347 items. We observed that all pairs with δ ij ≥ 120 and 99% of pairs with δ ij ≥ 42 were pegged by only the first application of the pegging test. This confirms that ⇀ ω is credible as the sorting key. Then we propose to sort the items according to the two keys: ⇀ ω i as the primary key and r i as the secondary key, which will serve as a tie breaker. The sorting can be done by first sorting according to the secondary key, and then according to the primary key by a stable sorting algorithm, e.g., bubble sort. See for example [24]. As heuristics for a good incumbent we first arrange the items as above, and then apply a local search for a further improvement. We observed from some preliminary experiment that 2-opt or 3-opt heuristics is not worth their computational cost, which agrees with the observation reported in Belloni and Lucena [3].  Then we use the following simple heuristic method. Given a linear ordering π , we take an item, say i = π − 1 ( k ), at the kth position, and search for a position in the range of [max{1, k − β}, min{n, k + β}] such that moving item i to the position improves the objective function value, where β is a fixed positive number. Then we accept it as a temporary incumbent and take the next item π− 1 ( k + 1) for a possible further improvement.
9. FEASIBILITY CHECK AND INCREMENT OF U AND V
When μ becomes less than 0.005, we decide that there is no chance of improving the upper bound unless we expand U or V . We add the transitivity constraints violated by the latest optimal solution x ( u, v ) of ( LR( u, v, P 0 , P 1 )). To avoid checking an enormous number of transitivity constraints one by one, we first make the arc set
where ī ij is defined by (8.1). Then we compute row sum r i of (8.2), sort the items according to it, and then look for a pair of items such that rj < r i and (j,i) ∈ A(x(u,v)), which we call an upward arc . Tracing the arcs of A( x ( u, v )) starting from an upward arc, we look for another item, say k , such that the three arcs (j,i), (i,k) and (k,j) form a directed cycle. Clearly this triple violates the transitivity constraint. Furthermore, we see the following lemma. Lemma 9.1. The arc set A(x(u,v)) contains no upward arcs if and only if x(u,v) is a linear ordering. Proof.  Suppose that x ( u, v ) is not a linear ordering.  Then it violates one of the transitivity constraints.  When x ij + x jk − x ik ≤ 1 is violated, A( x ( u, v )) contains a directed cycle {(i,j),(j,k),(k,i)} of length three, and at least one of its arcs form an upward arc. We also see that there is a directed cycle {(i,k),(k,j),(j,i)} when -xij - xjk + xik ≤ 0 is violated. When x(u, v) is a linear ordering, its row sum r i of X ranges over { n − 1 , n − 2 , . . . , 1 , 0} as in Corollary 8.2. Rearrange the columns and rows simultaneously in the descending order of r i .  Note that the diagonal elements are zero.  Clearly the first row consists of a single zero followed by n − 1 ones, i.e., ( l , 1 , . . . , 1). As the induction hypothesis we assume that the hth row is h zeros followed by n − h ones for h = 1,2,...,k. The case of k = 3 is shown below, where diagonal elements are underlined.
The k + 1st row must have k + 1 zeros and n − k − 1 ones, and the first k elements are zero by the antisymmetry and the k + 1st element, which is a diagonal element, is also zero. Therefore it is k + 1 zeros followed by n − k − 1 ones, i.e., (0,0, . . . ,0,0,1,1, . . . ,1). We see k+1 n-k-1 that the matrix X is upper triangular, meaning that A(x(u,v)) has no upward arcs. ■
10. A LGORITHM
The algorithm is composed of the inner and outer cycles. The inner cycle consisting of Step 2 to 7 generates a sequence of Lagrangian multiplier vectors ( u, v ), and a sequence of incumbent solutions and values ω ow . Some variables are pegged there. The outer cycle expands the constraint index sets U and V . Step 1 (Initialization) (a) Arrange the items according to the row-column difference ∑ j ∈ N Cij − ∑ j ∈ N Cji of cost coefficients and let the linear ordering obtained be the first incumbent solution and let ω 10w be its objective function value. (b) For each consecutive triple ( i, j, k ) in the incumbent linear ordering, add the transitivity constraints of type 1 and 2 to U and V , respectively. (c) l ← 0, μ ← 2.0, (u, v) ← (0, 0). (d) P 0 , P 1 ← 0 . (e) wup ← +∞. Step 2  (Solving (LR(u, v, P0, P1))) (a) Compute r(u,v)ij by (4.1). (b) Set x(u,v)ij according to (4.2). (c) ωup ← min{ωup,ω(LR(u,υ,Ρο,Ρι))}. (d) If wup is not improved, l ← l + 1. Otherwise, l ← 0. Step 3 (Termination) (a) If x(u,v) satisfies the optimality condition in Corollary 5.3 with (u,v), then terminate. (b) If ω up − ω 10w < ε , then terminate, where ε is a predetermined tolerance to the duality gap. Step 4 (Heuristics) (a) Apply the heuristic method in Section 8 to x ( u, v ) for a better solution . (b) ω low ← max{ω low , objective function value of  ž}. Step 5  (Pegging Test) (a) When ω up − ω low < η , then apply the improved pegging test (or the pegging test when P 0 = P 1 = ∅). (b) Let P 0 and P 1 be the index sets of variables pegged at zero and one, respec- tively. Step 6  (Update of μ) (a) If μ ≤ 0.005, then μ ← 2.0 and go to Step 8. (b) If l reaches 5, μ ← μ/2. Step 7 (Update of (u,v)) (a) Update ( u, v ) according to (7.1) and (7.2). (b) Go to Step 2. Step 8  (Update of U, V) (a) Find the transitivity constraints violated by x ( u, v ) and add them to U and V. (b)  u ijk, Vijk ← 0 for newly added indices ( i, j, k ). (c) Go to Step 2.
11. COMPUTATIONAL RESULTS
We coded the algorithm in Java, and run it on a PC with an Intel i3, 3.33 GHz processor and 2 GB of memory. The problem DsumC that we solved is a minimum violations ranking problem provided by K. Pedings, College of Charleston. The cost matrix C is based on the point differential matrix of 347 teams in NCAA college basketball for the 2008–2009 season. The problem has 60,031 binary variables and 13,807,130 transitivity constraints. Note that since the cost matrix is an integer matrix, objective function takes an integer value. See Pedings et al. [22] for the details. Table 1 to 3 show the results in which ● iteration shows the number of updates of the Lagrangian multiplier vector ( u,v ), ● lower bound shows the incumbent value ωιοw, ● upper bound shows the upper bound wup, ● duality gap is the difference Wup — Wlow, ● | U | + | V | shows the number of transitivity constraints in U U V , ● %1 shows the percentage of | U | + | V | to the total number of transitivity constraints, ● | P 0 | + | P 1 | shows the number of pegged variables, ● %² shows the percentage of the pegged variables, ● time(sec) shows the computation time in second. These statistics are given for every 500th iteration. Table 1 gives the result of the algorithm without pegging tests. After 2212 iterations, the duality gap reduced to less than one, and the incumbent at hand turned out to be an optimal solution. Note that the transitivity constraints being considered account for 0.08%, just a fraction of a percent of the total. Since the pegging test places a burden on the computation, we did it every 500th iteration.  Table 2 gives the result of the algorithm with the ordinary pegging test.  It terminated after 2141 iterations in 11.40 seconds, slightly shorter than the computation time when no pegging test was done. Note that about 92% of the variables were eventually pegged. Table 3 shows the result of the algorithm with the improved pegging test. We applied the ordinary pegging test at the 500th iteration and then the improved pegging test from the 1000th iteration at intervals of 500 iterations.  The algorithm found an optimal solution at the 316th iteration, and proved its optimality at the 2193th iteration when the duality gap fell below one.  It took the longest computation time due to the burden of the improved pegging test, however, about 95% of the variables were eventually pegged. If we failed to prove the optimality of the incumbent solution by an abortion of computation, this would still provide much information about an optimal solution.  We observed that U and V were updated for the first time in the 51th itertion, which led to a sharp decline of the upper bound.
SUKEGAWA, YAMAMOTO, AND ZHANG
Table 4 shows the result for the problem DavgC provided by Pedings based on the same data as DsumC. The difference is that the cost matrix consists of fractional cost coefficients. We stopped the computation after 5772 iterations when the duality gap reduced to less than one. The final incumbent may not be optimal, however, more than 95% of variables were pegged.
Table 2. Result for DsumC : ordinary pegging test T ABLE 3. Result for DsumC : improved pegging test
The problems we solved are so limited that more well-organized experiments should be carried out before any conclusion is made.
[1] I. Ali, W.D. Cook and M. Kress, "On the minimum violation ranking of a tournament", Management Sciences 32 (1986) 660–672. K.J. Arrow, Social Choice and Individual Values , John Wiley and Sons, New York, 1951. 2 A. Belloni and A. Lucena, "Lagrangian heuristics for the linear ordering problem", in: Metaheuristics: Computer Decision-Making eds. M.G.C. Resende and J.P. de Sousa, Kluwer, Dordrecht, 2004, pp.37– 63. G. Bolotashvili, M. Kovalev and E. Girlich, "New facets of the linear ordering polytope", SIAM 4 Journal of Discrete Mathematics 12 (1999) 326–336. V. Campos, F. Glover, M. Laguna and R. Martí, "An experimental evaluation of a scatter search for the [5] linear ordering problem", Journal of Global Optimization 21 397–414; DOI: 10.1023/A:1012793906010. E. Çela, The Quadratic Assignment Problem: Theory and Algorithms , Kluwer, Dordrecht, 2010. 6 I. Charon and O. Hudry, "A branch-and-bound algorithm to solve the linear ordering problem for [7] weighted tournaments", Discrete Applied Mathematics 154 (2006) 2097–2116. I. Charon and O. Hudry, "A survey on the linear ordering problem for weighted or unweighted tourna- [8] ments", A Quarterly Journal of Operations Research 5 (2007) 5–60; DOI: 10.1007/s10288-007-0036-6. S. Chanas and P. Kobylański, "A new heuristic algorithm solving the linear ordering problem", Com- [9] putational Optimization and Applications 6 (1996) 191–205; DOI: 10.1007/BF00249646. [10] J.P. Doignon, S. Fiorinia and G. Joret, "Facets of the linear ordering polytope: A unification for the fence family through weighted graphs", Journal of Mathematical Psychology 50 (2006) 251–262. [11] C.G. Garcia, D. Pérez-Brito, V. Campos and R. Martí, "Variable neighborhood search for the linear ordering problem", Computers and Operations Research 33 (2006) 3549–3565. [12] A.M. Geoffrion, "Lagrangian relaxation for integer programming", Mathematical Programming Study 2 (1974) 82–114. [13] S.T. Goddard, "Tournament rankings", Management Science 29 (1983) 1385–1392. C.G. González and D. Pérez-Brito, "A variable neighborhood search for solving the linear ordering [14] problem", MIC'2001 - 4th Metaheuristics International Conference pp.181–185. M. Grötschel, J. Jünger and G. Reinelt, "A cutting plane algorithm for the linear ordering problem", [15] Operations Research 32 (1984) 6, 1195–1220. M. Grötschel, J. Jünger and G. Reinelt, "Facets of the linear ordering polytope" Mathematical Pro- [16] gramming 33 (1985) 43–60. [17] J.G. Kemeny and J.L. Snell, Mathematical Models in the Social Sciences , Blaisdell, New York, 1972. J. Leunga, and J. Lee, "More facets from fences for linear ordering and acyclic subgraph polytopes", [18] Discrete Applied Mathematics 50 (1994) 185–200. [19] J.E. Mitchell and B. Borchers, "Solving real-world linear ordering problem using a primal-dual interior point cutting plane method", Annals of Operations Research 62 (1996) 253–276; DOI: 10.1007/BF02206819. [20] J.E. Mitchell and B. Borchers, "Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm", in: High Performance Optimization , H. Frenk et al. eds., pp. 349–366, Kluwer Academic Publishers, 2000. [21] A. Newman and S. Vempala, "Fences are futile: on relaxations for the linear ordering problem", in: Integer Programming and Combinatorial Optimization , Lecture Notes in Computer Science, 2001, Vol. 2081/2001, 333-347, DOI: 10.1007/3 − 540 − 45535 − 326. [22] K. Pedings, A.N. Langville and Y. Yamamoto, "A minimum violations ranking method", to appear in Optimization and Engineering. [23] G. Reinelt, The Linear Ordering Problem: Algorithms and Applications , Helderman, Berlin, 1985. [24] R. Sedgewick, Algorithms in C , 3rd Edition, Addison-Wesley, Boston, 2002. Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan E-mail address: {sukega60, yamamoto}@sk.tsukuba.ac.jp, zhangliyuan120@gmail.com