Solving linear ordering problems with a combined
interior point/simplex cutting plane algorithm
John Mitchell and Brian Borchers
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.
Mathematical Sciences, RPI, Troy NY 12180 USA, September 1997