full
search.png

Search

close.png

Cancel

arrow
Volume 31, Issue 4
On an Efficient Implementation of the Face Algorithm for Linear Programming

Leihong Zhang, Weihong Yang & Lizhi Liao

DOI: 10.4208/jcm.1301-m4106

J. Comp. Math., 31 (2013), pp. 335-354.

Published online: 2013-08

Preview Full PDF 2913 29482

Cited by

google scholar semantic scholar
Export citation
  • 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.

  • AMS Subject Headings

62H20, 15A12, 65F10, 65K05.

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-31-335, author = {Zhang , LeihongYang , Weihong and Liao , Lizhi}, title = {On an Efficient Implementation of the Face Algorithm for Linear Programming}, journal = {Journal of Computational Mathematics}, year = {2013}, volume = {31}, number = {4}, pages = {335--354}, 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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1301-m4106}, url = {http://global-sci.org/intro/article_detail/jcm/9739.html} }
TY - JOUR T1 - On an Efficient Implementation of the Face Algorithm for Linear Programming AU - Zhang , Leihong AU - Yang , Weihong AU - Liao , Lizhi JO - Journal of Computational Mathematics VL - 4 SP - 335 EP - 354 PY - 2013 DA - 2013/08 SN - 31 DO - http://doi.org/10.4208/jcm.1301-m4106 UR - https://global-sci.org/intro/article_detail/jcm/9739.html KW - Linear programming, Level face, Optimal face, Rank-one correction. AB -

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.

Zhang , LeihongYang , Weihong and Liao , Lizhi. (2013). On an Efficient Implementation of the Face Algorithm for Linear Programming. Journal of Computational Mathematics. 31 (4). 335-354. doi:10.4208/jcm.1301-m4106
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard