[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(
)
关于单纯形算法若干进展的新见解
)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.
- 首先回顾了采用最钝角行、列主元规则求解线性规画问题的原始、对偶可行解的主要过程, 阐述了其与众不同的特性.然后构造了2个特殊的辅助问题, 并证明了最钝角行、列主元规则的过程实际上分别等价于采用原始、对偶单纯形算法求解相应的辅助问题.此外, 还对嵌套的pricing规则进行了回顾, 并基于最优解的启发式特征刻画给出了该规则的一个几何解释.
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.