Seriation of asymmetric matrices using integer linear programming

Abstract

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 < or = n < or = 36) from the psychological literature, as well as 80 synthetic matrices (20 < or = n < or = 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.