Browsing by Author "McGregor-Macdonald, Simon"
Now showing 1 - 1 of 1
- Results Per Page
- Sort Options
Item Restricted Path-following methods for linear programming: a comparison with the simplex method(Te Herenga Waka—Victoria University of Wellington, 2000) McGregor-Macdonald, SimonThis thesis introduces path-following methods for linear programming and compares them to the simplex method. This comparison involves three aspects of each method: mathematical basis of the methodology, theoretical computational complexity and computational performance in practice. Path-following methods follow the central path through the interior of the feasible region, whereas the simplex method traces around the boundary. The computational complexity of path-following methods is shown to be polynomial, while the simplex method is exponential in the worst-case. The experience of practitioners gives overwhelming evidence of the performance of the simplex method, but implementations of path-following methods can be competitive with the simplex method.