Seriation of asymmetric matrices using integer linear programming

Integer linear programming approaches for seriation of asymmetric n x n proximity matrices have generally been perceived as intractable for problems of practical size. However, to date, no computational evidence has been provided regarding the effectiveness (or ineffectiveness) of such approaches. This paper presents an evaluation of an integer linear programming method for asymmetric seriation using five moderately sized matrices (15 less than or equal to n less than or equal to 36) from the psychological literature, as well as 80 synthetic matrices (20 less than or equal to n less than or equal to 30). The solution to the linear programming relaxation of the integer-programming model was integer-optimal for each of the five empirical matrices and many of the synthetic matrices. In such instances, branch-and-bound integer programming was not required and optimal orderings were obtained within a few seconds. In all cases where the solution to the linear programming relaxation was not integer-optimal, branch-and-bound integer programming was able to find an optimal seriation in 18 minutes or less. A pragmatic solution strategy for larger matrices (n > 30) is also presented. This approach exploits the fact that, in many instances, only a modest percentage of all possible transitivity constraints are required to obtain an optimal solution.