SMALL DEGENERATE SIMPLICES CAN BE BAD FOR SIMPLEX METHODS

Access this Article

Search this Article

Author(s)

Abstract

<p>We show that the simplex method with Dantzig's pivoting rule may require an exponential number of iterations over two highly degenerate instances. The feasible region of the first instance is a full dimensional simplex, and a single point for the second one. In addition, the entries of the constraint matrix, the right-hand-side vector, and the cost vector are {0,1,2}-valued. Those instances, with few vertices and small input data length, illustrate the impact of degeneracy on simplex methods.</p>

Journal

  • Journal of the Operations Research Society of Japan

    Journal of the Operations Research Society of Japan 60(4), 419-428, 2017

    The Operations Research Society of Japan

Codes

  • NII Article ID (NAID)
    130006182211
  • NII NACSIS-CAT ID (NCID)
    AA00703935
  • Text Lang
    ENG
  • ISSN
    0453-4514
  • NDL Article ID
    028595220
  • NDL Call No.
    Z53-M226
  • Data Source
    NDL  J-STAGE 
Page Top