[1] Pan Pingqi, Li Wei,. A non-monotone Phase-1 method in linear programming [J]. Journal of Southeast University (English Edition), 2003, 19 (3): 293-296. [doi:10.3969/j.issn.1003-7985.2003.03.018]

Copy

A non-monotone Phase-1 method in linear programming()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

19

Issue:

2003 3

Page:

293-296

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2003-09-30

Info

Title:

A non-monotone Phase-1 method in linear programming

Author(s):

Pan Pingqi;  Li Wei

Department of Mathematics, Southeast University, Nanjing 210096, China

Keywords:

linear programming;  Phase-1;  ratio-test-free;  pivoting rule

PACS:

O221.1

DOI:

10.3969/j.issn.1003-7985.2003.03.018

Abstract:

To gain superior computational efficiency, it might be necessary to change the underlying philosophy of the simplex method. In this paper, we propose a Phase-1 method along this line. We relax not only the conventional condition that some function value increases monotonically, but also the condition that all feasible variables remain feasible after basis change in Phase-1. That is, taking a purely combinatorial approach to achieving feasibility. This enables us to get rid of ratio test in pivoting, reducing computational cost per iteration to a large extent. Numerical results on a group of problems are encouraging.

References:

[1] Wolfe P. The composite simplex algorithm [J]. SIAM Review, 1965, 7: 42-54.
[2] Maros Istvan. A general Phase-I method in linear programming [J]. European Journal of Operations Research, 1986, 34: 64-77.
[3] Belling-Seib K. An improved general Phase-I method in linear programming [J]. European Journal of Operations Research, 1988, 36: 101-106.
[4] Pan P Q. A projective simplex method for linear programming [J]. Linear Algebra and its Applications, 1999, 29(2):99-125.
[5] Pan P Q. A new perturbation simplex algorithm for linear programming [J]. Journal of Computational Mathematics, 1999, 17(3): 233-242.
[6] Pan P Q. A projective simplex algorithm using LU decomposition [J]. Computers and Mathematics with Applications, 2000, 39(1): 187-208.
[7] Pan P Q. Practical finite pivoting rules for the simplex method[J]. OR Spektrum, 1990, 12: 219-225.

Memo

Memo:

Biography: Pan Pingqi(1942—), male, professor; panpq@seu.edu.cn.

Common functions