Criss-cross methods: A fresh view on pivot algorithms |
| |
Authors: | Komei Fukuda Tamás Terlaky |
| |
Institution: | (1) Department of Mathematics, Swiss Federal Institute of Technology, Lausanne, Switzerland;(2) Institute for Operations Research, Swiss Federal Institute of Technology, Zürich, Switzerland;(3) Faculty of Technical Mathematics and Informatics, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands |
| |
Abstract: | Criss-cross methods are pivot algorithms that solve linear programming problems in one phase starting with any basic solution.
The first finite criss-cross method was invented by Chang, Terlaky and Wang independently. Unlike the simplex method that
follows a monotonic edge path on the feasible region, the trace of a criss-cross method is neither monotonic (with respect
to the objective function) nor feasibility preserving. The main purpose of this paper is to present mathematical ideas and
proof techniques behind finite criss-cross pivot methods. A recent result on the existence of a short admissible pivot path
to an optimal basis is given, indicating shortest pivot paths from any basis might be indeed short for criss-cross type algorithms.
The origins and the history of criss-cross methods are also touched upon. |
| |
Keywords: | Linear programming Quadratic programming Linear complementarity problems Oriented matroids Pivot rules Criss-cross method Cycling Recursion |
本文献已被 SpringerLink 等数据库收录! |
|