A projective simplex method for linear programming

✍ Scribed by Ping-Qi Pan

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 189 KB
• Volume: 292
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(99)00010-5

✦ Synopsis

Linear programming problems with quite square coecient matrix form a wide range of problems that are not amenable to existing algorithms. The method proposed in this paper attacks such problems from the dual side, alternatively arranging computations of the simplex method using the QR factorization. In each iteration, its tableau version handles an n À m  n 1 tableau rather than the m 1  n 1 conventional tableau, where m and n are the numbers of rows and columns of the coecient matrix. In contrast to the simplex method, where two m  m systems are solved per iteration, the new approach solves a single s  s s T n À m system only. It allows nonbasis de®ciency'', and hence could reduce computational work dramatically. A favorable complexity analysis is given for one of its implementations against its conventional counterpart. In addition, a new crash heuristic, having a clear geometrical meaning towards an optimal basis, is developed to provide good'' input. We also report numerical results obtained from our trials to give an insight into the method's behavior.