Criss-cross methods : A fresh view on pivot algorithms
Fukuda, Komei
Terlaky, Tamás

Data: 1997
Resum: 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. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Linear programming ; Quadratic programming ; Linear complementarity problems ; Oriented matroids ; Pivot rules ; Criss-cross method ; Cycling ; Recursion
Publicat a: Mathematical Programming, vol. 79 n. 1-3 (1997) p. 369-395, ISSN 0025-5610

27 p, 1.5 MB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir