.png){kind=icon}
.png){kind=icon}
Return
Solving real-world linear ordering problems using a primal-dual interior point cutting plane method
.png){kind=icon}
PRE
AI
DOI：10.1007/BF02206819.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
TRAVELING SALESMAN PROBLEMS
PROJECTIVE ALGORITHM
OPTIMIZATION
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W
Organization
No organization information available