Solving Linear Ordering Problems With A Combined Interior Point/simplex Cutting Plane Algorithm

: We describe a cutting plane algorithm for solving linear ordering problems. The algorithm uses a primal-dual interior point method to solve the first few relaxations and then switches to a simplex method to solve the last few relaxations. The simplex method uses CPLEX 4.0. We compare the algorithm with one that uses only an interior point method and with one that uses only a simplex method. We solve integer programming problems with as many as 31125 binary variables. Computational results show that the combined approach can dramatically outperform the other two methods. 1.1 INTRODUCTION The linear ordering problem has applications in economics, archaeology, scheduling, the social sciences, and aggregation of individual preferences. A cutting plane method provides a way to obtain a provably optimal solution to a linear ordering problem. Such a method requires the solution of a sequence of linear programming problems. It is now possible to solve linear ordering problems of a size wher..