首页 | 本学科首页   官方微博 | 高级检索  
     检索      

ON AN EFFICIENT IMPLEMENTATION OF THE FACE ALGORITHM FOR LINEAR PROGRAMMING*
摘    要:In this paper, we consider the solution of the standard linear programming Lt'). A remarkable result in LP claims that all optimal solutions form an optimal face of the underlying polyhedron. In practice, many real-world problems have infinitely many optimal solutions and pursuing the optimal face, not just an optimal vertex, is quite desirable. The face algorithm proposed by Pan 19] targets at the optimal face by iterating from face to face, along an orthogonal projection of the negative objective gradient onto a relevant null space. The algorithm exhibits a favorable numerical performance by comparing the simplex method. In this paper, we further investigate the face algorithm by proposing an improved implementation. In exact arithmetic computation, the new algorithm generates the same sequence as Pan's face algorithm, but uses less computational costs per iteration, and enjoys favorable properties for sparse problems.

关 键 词:线性规划算法  FACE  标准线性规划  现实世界  正交投影  单纯形法  算术运算  计算成本

On an Efficient Implementation of the Face Algorithm for Linear Programming
Authors:Lei-Hong Zhang  Wei Hong Yang  Li-Zhi Liao
Institution:[1]Department of Applied Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China [2]School of Mathematical Sciences, Fudan University, Shanghai 200433, China [3]Department of Mathematics and Institute of Computational and Theoretical Studies, Hong Kong Baptist University, Hong Kong, China
Abstract:In this paper, we consider the solution of the standard linear programming (LP). A remarkable result in LP claims that all optimal solutions form an optimal face of the underlying polyhedron. In practice, many real-world problems have infinitely many optimal solutions and pursuing the optimal face, not just an optimal vertex, is quite desirable. The face algorithm proposed by Pan 19] targets at the optimal face by iterating from face to face, along an orthogonal projection of the negative objective gradient onto a relevant null space. The algorithm exhibits a favorable numerical performance by comparing the simplex method. In this paper, we further investigate the face algorithm by proposing an improved implementation. In exact arithmetic computation, the new algorithm generates the same sequence as Pan's face algorithm, but uses less computational costs per iteration, and enjoys favorable properties for sparse problems.
Keywords:Linear programming  Level face  Optimal face  Rank-one correction  
本文献已被 维普 等数据库收录!
点击此处可从《计算数学(英文版)》浏览原始摘要信息
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号