Close Search Advanced
Journals
Resources
About Us
Open Access

On an Efficient Implementation of the Face Algorithm for Linear Programming

On an Efficient Implementation of the Face Algorithm for Linear Programming
Preview
Add to basket

Year:    2013

Author:    Leihong Zhang, Weihong Yang, Lizhi Liao

Journal of Computational Mathematics, Vol. 31 (2013), Iss. 4 : pp. 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.

Submit Article

You do not have full access to this article.

Already a Subscriber? Sign in as an individual or via your institution

Journal Article Details

Publisher Name:    Global Science Press

Language:    English

DOI:    https://doi.org/10.4208/jcm.1301-m4106

Journal of Computational Mathematics, Vol. 31 (2013), Iss. 4 : pp. 335–354

Published online:    2013-01

AMS Subject Headings:   

Copyright:    COPYRIGHT: © Global Science Press

Pages:    20

Keywords:    Linear programming Level face Optimal face Rank-one correction.

Author Details

Leihong Zhang

Weihong Yang

Lizhi Liao

  1. Linear Programming Computation

    Dual Pivot Rule

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_12 [Citations: 0]
  2. Linear Programming Computation

    Interior-Point Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_9 [Citations: 0]
  3. Linear Programming Computation

    Pivotal Interior-Point Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_24 [Citations: 0]
  4. Linear Programming Computation

    Simplex Phase-I Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_13 [Citations: 0]

  5. MULKASE: a novel approach for key-aggregate searchable encryption for multi-owner data

    Padhya, Mukti | Jinwala, Devesh C.

    Frontiers of Information Technology & Electronic Engineering, Vol. 20 (2019), Iss. 12 P.1717

    https://doi.org/10.1631/FITEE.1800192 [Citations: 12]
  6. Linear Programming Computation

    Face Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_22 [Citations: 0]

  7. Assignment Algorithms for Modeling Resource Contention in Multirobot Task Allocation

    Nam, Changjoo | Shell, Dylan A.

    IEEE Transactions on Automation Science and Engineering, Vol. 12 (2015), Iss. 3 P.889

    https://doi.org/10.1109/TASE.2015.2415514 [Citations: 35]
  8. Linear Programming Computation

    Implementation of the Simplex Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_5 [Citations: 0]
  9. Linear Programming Computation

    D-Reduced Simplex Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_17 [Citations: 0]
  10. Linear Programming Computation

    Pivot Rule

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_11 [Citations: 0]
  11. Linear Programming Computation

    Sensitivity Analysis and Parametric LP

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_6 [Citations: 0]
  12. Linear Programming Computation

    Dual Simplex Phase-l Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_14 [Citations: 0]

  13. Assignment algorithms for modeling resource contention and interference in multi-robot task-allocation

    Nam, Changjoo | Shell, Dylan A.

    2014 IEEE International Conference on Robotics and Automation (ICRA), (2014), P.2158

    https://doi.org/10.1109/ICRA.2014.6907156 [Citations: 16]
  14. Linear Programming Computation

    Decomposition Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_8 [Citations: 0]
  15. Linear Programming Computation

    Dual Deficient-Basis Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_21 [Citations: 0]
  16. Linear Programming Computation

    Variants of the Simplex Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_7 [Citations: 0]
  17. Linear Programming Computation

    Dual Face Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_23 [Citations: 1]
  18. Linear Programming Computation

    Criss-Cross Simplex Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_18 [Citations: 0]
  19. Linear Programming Computation

    Face Method with Cholesky Factorization

    PAN, Ping-Qi

    2023

    https://doi.org/10.1007/978-981-19-0147-8_21 [Citations: 0]
  20. Linear Programming Computation

    Deficient-Basis Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_20 [Citations: 0]
  21. Linear Programming Computation

    Simplex Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_3 [Citations: 1]
  22. Linear Programming Computation

    Duality Principle and Dual Simplex Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_4 [Citations: 0]
  23. Linear Programming Computation

    Integer Linear Programming (ILP)

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_10 [Citations: 2]
  24. Linear Programming Computation

    Special Topics

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_25 [Citations: 0]
  25. Linear Programming Computation

    Improved Reduced Simplex Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_16 [Citations: 0]
  26. Linear Programming Computation

    Geometry of the Feasible Region

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_2 [Citations: 0]
  27. Linear Programming Computation

    Generalizing Reduced Simplex Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_19 [Citations: 0]
  28. Linear Programming Computation

    Reduced Simplex Method

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_15 [Citations: 0]
  29. Linear Programming Computation

    Introduction

    PAN, Ping-Qi

    2014

    https://doi.org/10.1007/978-3-642-40754-3_1 [Citations: 0]

  30. A review of “linear programming computation” by Ping-Qi Pan

    Shi, Yangyang | Zhang, Lei-Hong | Zhu, Wenxing

    European Journal of Operational Research, Vol. 267 (2018), Iss. 3 P.1182

    https://doi.org/10.1016/j.ejor.2017.10.051 [Citations: 1]