Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew‐symmetric quadratic assignment problem
Merrill M. Flood · Networks · 1990
Abstract This paper presents algorithms for finding exact and approximate solutions for the weighted feedback are set problem, determining a minimum‐cardinality set of ares that breaks all cycles in a directed graph. This is also the problem of finding a group rank ordering given the rank orders for each member of a group. The algorithms have many other applications. Mathematically, the problem is that of finding a permutation matrix P that maximizes the sum of the elements above the principal diagonal of P1 WP where W is a skew‐symmetric matrix of order n. This is a special case of the Koopmans‐Beckmann quadratic assignment problem. Computational experience is reported for a sample of randomly generated problems, including comparisons with results obtained using algorithms three other authors have developed for solving the more general quadratic assignment problem. For our sample, using randomly generated problems, the computational time required for calculating all exact solutions for each problem is approximately T(n) = c2.232n, where c = 9.8764E ‐ 6 and T(20) = 93 s for the Cray X‐MP/48 supercomputer. For our sample, the computational time required for calculating one approximate solution is approximately T(n) = an4,1, where a = 3.0361E ‐ 8 and T(250) = 206 s for the Cray.