Premium
Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew‐symmetric quadratic assignment problem
Author(s) -
Flood Merrill M.
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230200102
Subject(s) - computational problem , mathematics , combinatorics , assignment problem , cardinality (data modeling) , algorithm , permutation (music) , quadratic equation , matrix (chemical analysis) , quadratic assignment problem , computational complexity theory , permutation matrix , optimization problem , computer science , physics , geometry , materials science , circulant matrix , acoustics , composite material , data mining
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 P 1 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) = c 2.232 n , where c = 9.8764 E ‐ 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) = an 4,1 , where a = 3.0361 E ‐ 8 and T (250) = 206 s for the Cray.