Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm

Download the paper, postscript or pdf.


John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA

Brian Borchers
Mathematics Department
New Mexico Tech
Socorro, NM 87801 USA

September 25, 1997, revised December 18, 1998.


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.

Publication details:

Appeared as Chapter 14, pages 349-366, of High Performance Optimization, edited by H. Frenk et al., Kluwer Academic Publishers, 2000.

Download the paper, postscript or pdf.

Return to my list of papers.