Solving real-world linear ordering problems using a primal-dual interior point cutting plane method

Solving real-world linear ordering problems using a primal-dual interior point cutting plane method

0.00 Avg rating0 Votes
Article ID: iaor19971537
Country: Netherlands
Volume: 62
Issue: 1
Start Page Number: 253
End Page Number: 376
Publication Date: Mar 1996
Journal: Annals of Operations Research
Authors: ,
Keywords: programming: linear
Abstract:

Cutting plane methods require the solution of a sequence of linear programs, where the solution to one provides a warm start to the next. A cutting plane algorithm for solving the linear ordering problem is described. This algorithm uses the primal-dual interior point method to solve the linear programming relaxations. A point which is a good warm start for a simplex-based cutting plane algorithm is generally not a good starting point for an interior point method. Techniques used to improve the warm start include attempting to identify cutting planes early and storing an old feasible point, which is used to help recenter when cutting planes are added. Computational results are described for some real-world problems; the algorithm appears to be competitive with a simplex-based cutting plane algorithm.

Reviews

Required fields are marked *. Your email address will not be published.