[1] Hu Jianfeng, Pan Pingqi,. Fresh views on some recent developmentsin the simplex algorithm [J]. Journal of Southeast University (English Edition), 2008, 24 (1): 124-126. [doi:10.3969/j.issn.1003-7985.2008.01.027]

Copy

Fresh views on some recent developmentsin the simplex algorithm()

Share：

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

Volumn:

24

Issue:

2008 1

Page:

124-126

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2008-03-30

Info

Title:

Fresh views on some recent developmentsin the simplex algorithm

Author(s):

Hu Jianfeng;  Pan Pingqi

Department of Mathematics, Southeast University, Nanjing 210096, China

Keywords:

linear programming;  simplex algorithm;  pivot;  most-obtuse-angle;  nested pricing;  large-scale problem

PACS:

O221.1

DOI:

10.3969/j.issn.1003-7985.2008.01.027

Abstract:

First, the main procedures and the distinctive features of the most-obtuse-angle(MOA)row or column pivot rules are introduced for achieving primal or dual feasibility in linear programming.Then, two special auxiliary problems are constructed to prove that each of the rules can be actually considered as a simplex approach for solving the corresponding auxiliary problem.In addition, the nested pricing rule is also reviewed and its geometric interpretation is offered based on the heuristic characterization of an optimal solution.

References:

[1] Dantzig G B.Programming in a linear structure[J].Econometrica, 1949, 17:73-74.
[2] Lemke C E.The dual method of solving the linear programming problems[J].Naval Research Logistics Quarterly, 1954, 1(1):36-47.
[3] Pan P Q.Achieving primal feasibility under the dual pivoting rule[J].Journal of Information and Optimization Sciences, 1994, 15(3):405-413.
[4] Pan P Q.The most-obtuse angle row pivot rule for achieving dual feasibility:a computational study[J].European Journal of Operational Research, 1997, 101(1):167-176.
[5] Pablo G G, Angel S P.Phase Ⅰ cycling under the most-obtuse-angle pivot rule[J].European Journal of Operational Research, 2005, 167(1):20-27.
[6] Koberstein A, Suhl U.Progress in the dual simplex method for large scale LP problems:practical dual phase 1 algorithms[J].Computational Optimization and Applications, 2007, 37(1):49-65.
[7] Dantzig G B.Maximization of a linear function of variables subject to linear inequalities[C]//Activity Analysis of Production and Allocation.New York:John Wiley & Sons, 1951:339-347.
[8] Forrest J J H, Goldfarb D.Steepest-edge simplex algorithms for linear programming[J].Mathematical Programming, 1992, 57(1):341-374.
[9] Harris P M J.Pivot selection methods of the Devex LP code[J].Mathematical Programming, 1973, 5(1):1-28.
[10] Bland R G.New finite pivoting rules for the simplex method[J].Mathematics of Operations Research, 1977, 2(2):103-107.
[11] Dantzig G B, Orden A, Wolfe P.The generalized simplex method for minimizing a linear form under linear inequality restraints[J].Pacific Journal of Mathematics, 1955, 5(2)183-195.
[12] Pan P Q.Practical finite pivoting rules for the simplex method[J].OR Spektrum, 1990, 12(4):219-225.
[13] Terlaky T, Zhang S.Pivot rules for linear programming:a survey on recent theoretical developments[J].Annals of Operations Research, 1993, 46(1):203-233.
[14] Orchard-Hays W.Advanced linear programming computing techniques[M].New York:McGraw-Hill Book Company, 1968.
[15] Maros I.Computational techniques of the simplex method[M].Norwell, MA:Kluwer Academic Publishers, 2003.
[16] Murtagh B A, Saunders M A.MINOS 5.5 User’s guide[R].Stanford:Department of Operations Research of Stanford University, 1998.
[17] Pan P Q.Efficient nested pricing in the simplex algorithm[EB/OL].(2007-12-16)[2008-01-16].http://dx.doi.org/10.1016/j.orl.2007.10.001.
[18] Pan P Q, Li W, Cao J.Partial pricing rule simplex method with deficient basis[J].Numerical Mathematics:A Journal of Chinese Universities, 2006, 15(1):23-30.

Memo

Memo:

Biographies: Hu Jianfeng(1979—), male, graduate;Pan Pingqi(corresponding author), male, professor, panpq@seu.edu.cn.
Foundation item: The National Natural Science Foundation of China(No.10371017).
Citation: Hu Jianfeng, Pan Pingqi.Fresh views on some recent developments in the simplex algorithm[J].Journal of Southeast University(English Edition), 2008, 24(1):124-126.

Common functions