Integer programming methods for seriation and unidimensional scaling of proximity matrices: A review and some extensions

A number of linear-, goal-, and integer-programming models have been developed for problems related to the sequencing (or ranking) of a set of objects. This paper provides a review of integer linear programming models related to seriation and unidimensional scaling of proximity matrices. In addition to the review of existing literature, some new formulations are proposed for seriation of symmetric dissimilarity matrices based on anti-Robinson indices. Some new modeling ideas for unidimensional scaling in the L-1-norm are also presented. I conclude that the computational viability of integer programining methods for seriation and unidimensional scaling problems depends largely on the criterion of interest, with unidimensional scaling in the L-1-norm being especially challenging.