Skip to main content
SpringerLink
Log in

A Simple Projection Algorithm for Linear Programming Problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Fujishige et al. propose the LP-Newton method, a new algorithm for linear programming problem (LP). They address LPs which have a lower and an upper bound for each variable, and reformulate the problem by introducing a related zonotope. The LP-Newton method repeats projections onto the zonotope by Wolfe’s algorithm. For the LP-Newton method, Fujishige et al. show that the algorithm terminates in a finite number of iterations. Furthermore, they show that if all the inputs are rational numbers, then the number of projections is bounded by a polynomial in L, where L is the input length of the problem. In this paper, we propose a modification to their algorithm using a binary search. In addition to its finiteness, if all the inputs are rational numbers and the optimal value is an integer, then the number of projections is bounded by \(L+1\), that is, a linear bound.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Chakrabarty, D., Jain, P., Kothari, P.: Provable submodular minimization using Wolfe’s algorithm. In: Advances in Neural Information Processing Systems, pp. 802–809 (2014)

  2. Fujishige, S.: Submodular functions and optimization, 2nd edn. Annals of Discrete Mathematics, vol. 58. Elsevier, Amsterdam (2005)

    Google Scholar 

  3. Fujishige, S.: Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested. Jpn. J. Ind. Appl. Math. 29, 357–384 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  4. Fujishige, S., Hayashi, T., Isotani, S.: The minimum-norm-point algorithm applied to submodular function minimization and linear programming. Kyoto University. Research Institute for Mathematical Sciences [RIMS] (2006)

  5. Fujishige, S., Hayashi, T., Yamashita, K., Zimmermann, U.: Zonotopes and the LP-Newton method. Optim. Eng. 10, 193–205 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Fujishige, S., Liu, X., Zhang, X.: An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set. J. Optim. Theory Appl. 105, 113–147 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  7. Fujishige, S., Sato, H., Zhan, P.: An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane. Jpn. J. Ind. Appl. Math. 11, 245–264 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fujishige, S., Zhan, P.: A dual algorithm for finding the minimum-norm point in a polytope. J. Oper. Res. Soc. Jpn. 33, 188–195 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  9. Fujishige, S., Zhan, P.: A dual algorithm for finding a nearest pair of points in two polytopes. J. Oper. Res. Soc. Jpn. 35, 353–365 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  10. Grunbaum, B.: Convex polytopes, volume 221 of Graduate Texts in Mathematics, 60 (2003)

  11. Kitahara, T., Mizuno, S., Shi, J.: The LP-Newton method for standard form linear programming problems. Oper. Res. Lett. 41, 426–429 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  12. McMullen, P.: On zonotopes. Trans. Am. Math. Soc. 159, 91–109 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  13. Sekitani, K., Yamamoto, Y.: A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes. Math. Program. 61, 233–249 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  14. Silvestri, F., Reinelt, G.: The LP-Newton Method and Conic Optimization (2016). arXiv preprint arXiv:1611.09260

  15. Wolfe, P.: Finding the nearest point in a polytope. Math. Program. 11, 128–149 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  16. Ziegler, G.M.: Lectures on Polytopes, vol. 152. Springer, New York (2012)

    MATH  Google Scholar 

Download references

Acknowledgements

The first author is supported in part by Grant-in-Aid for Young Scientists (B) 15K15941 from the Japan Society for the Promotion of Sciences. The second author is supported in part by Grant-in-Aid for Young Scientists (Start-up) 15H06617 from the Japan Society for the Promotion of Sciences.

Author information

Authors and Affiliations

  1. Department of Economic Engineering, Faculty of Economics, Kyushu University, 6-19-1, Hakozaki, Higashi-ku, Fukuoka-shi, Fukuoka, 812-8581, Japan

    Tomonari Kitahara

  2. Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University, 1-13-27 Kasuga, Bunkyo-ku, Tokyo, 112-8551, Japan

    Noriyoshi Sukegawa

Authors
  1. Tomonari Kitahara
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Noriyoshi Sukegawa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tomonari Kitahara.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kitahara, T., Sukegawa, N. A Simple Projection Algorithm for Linear Programming Problems. Algorithmica 81, 167–178 (2019). https://doi.org/10.1007/s00453-018-0436-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-018-0436-3

Keywords

Search

Navigation