NEW EVALUATION FOR COMPUTATIONAL AMOUNT OF THE SIMPLEX METHOD

DOI Web Site Web Site 12 References
  • Kitahara Tomonari
    Graduate School of Decision Science and Technology, Tokyo Institute of Technology
  • Mizuno Shinji
    Graduate School of Decision Science and Technology, Tokyo Institute of Technology

Bibliographic Information

Other Title
  • 単体法の計算量の新評価
  • タンタイホウ ノ ケイサンリョウ ノ シン ヒョウカ

Search this article

Abstract

The simplex method is the most fundamental method for solving linear programming problems(LPs) and it can efficiently solve large-scale actual LPs. However, it has been an open question whether the simplex method is a polynomial algorithm or not. In addition, for some pivoting rules, LP instances which need an exponential number of iterations are known, such like the Klee-Minty problem. Recently Kitahara and Mizuno obtained an upper bound for the number of different basic solutions generated by the primal simplex method with Dantzig's rule. The bound is represented by the number of constraints, the number of variables, and the minimum and the maximum values of all the positive elements of primal basic feasible solutions. By calculating the actual number of different basic solutions for an LP instance, they showed that the bound is almost tight. In this paper, we summarize these results and explain related results by using examples and figures.

Journal

References(12)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top