Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Criss-cross methods: a fresh view on pivot algorithms
 
research article

Criss-cross methods: a fresh view on pivot algorithms

Fukuda, Komei  
•
Terlaky, Tamás
1997
Mathematical Programming

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.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1007/BF02614325
Web of Science ID

WOS:A1997XR87300019

Author(s)
Fukuda, Komei  
Terlaky, Tamás
Date Issued

1997

Publisher

Springer-Verlag

Published in
Mathematical Programming
Volume

79

Issue

1-3

Start page

369

End page

395

Subjects

Linear programming

•

Quadratic programming

•

Linear complementarity problems

•

Oriented matroids

•

Pivot rules

•

Criss-cross method

•

Cycling

•

Recursion

Note

PRO 97.04

National Licences

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSO  
Available on Infoscience
February 13, 2006
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/222828
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés