Paper Status Tracking

Journals by Title

Journals by Subject

Contact us

	[email protected]
	3275638434

	Paper Publishing WeChat

Useful Links

Creative Commons Attribution-NonCommercial 4.0 International License

Article

Open Access

A New Method Combining Interior and Exterior Approaches for Linear Programming

Author(s)

Nguyen Ngoc Chu, Pham Canh Duong and Le Thanh Hue

Full-Text PDF Download XML 1061 Views

DOI:10.17265/2159-5291/2015.05.004

Affiliation(s)

1. Institute of Mathematics, 18 Hoang Quoc Viet, Hanoi, Vietnam. 2. Center for Information Infrastructure Development, Vietnamese Academy of Science and Technology, 18 Hoang Quoc Viet, Hanoi, Vietnam. 3. Faculty of Informatics Technology, University of Mining and Geology, Hanoi, Vietnam.

ABSTRACT

In this paper we present a new method combining interior and exterior approaches to solve linear programming problems. With the assumption that a feasible interior solution to the input system is known, this algorithm uses it and appropriate constraints of the system to construct a sequence of the so called station cones whose vertices tend very fast to the solution to be found. The computational experiments show that the number of iterations of the new algorithm is significantly smaller than that of the second phase of the simplex method. Additionally, when the number of variables and constraints of the problem increase, the number of iterations of the new algorithm increase in a slower manner than that of the simplex method.

KEYWORDS

Linear programming, simplex method, station cone.

Cite this paper

References

[1] M.L. Balinski, Mathematical programming: journal, society, recollections, in: J.-K. Lenstra, A. H. G. Rinnooy Kan et A. Schrijver, eds., History of Mathematical Programming: a Collection of Personal Reminiscences, CWI et North-Holland Publishing Company, Amsterdam, pp. 5-18.
[2] R.E. Bixby, Implementing the simplex method: The initial basis, ORSA Journal on Computing 4 (1992) 267-284.
[3] R.E.Bixby, Progress in linear programming, ORSA Journal on Computing 6(1) (1994) 15-22.
[4] S.N. Chernikov, Linear Inequalities, Nauka, Moscow, 1968 (in Russian).
[5] G.B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, In Koopmans, T.C., ed., Activity Analysis of Production and Allocation, Wiley, New York, 1951, pp. 339-347.
[6] G.B. Dantzig, Progress in linear programming, ORSA Journal on Computing 6(1) (1963) 15-22.
[7] J.J. Forrest, D. Goldfarb, Steepest-edge simplex algorithms for linear programming, Mathematical Programming 57 (1992) 341-374.
[8] N.K. Karmarkar, A new polynomial-time algorithm for linear program-ming, Combinatorica 4 (1984) 373-395.
[9] L.G. Khachiyan, A polynomial algorithm in linear programming (in Russian), Doklady Akademiia Nauk SSSR 224 (1979) 1093-1096. English translation: Soviet Mathematics Doklady, 20, 191-194.
[10] V. Klee, G. J. Minty, How good is the simplex algorithm?, In: Shisha, O., ed., Inequalities, III, Academic Press, 1972, pp. 159-175. iterations. J. Res. Nat. Bur. Stand 49 (1952) 33-53.
[11] K. G. Murty, A Gravitational Interior Point Method for LP, Opsearch 42(1) (2005) 28–36.
[12] K. G. Murty, A New Practically Efficient Interior Point Method for LP,Algorithmic Operations Research 1 (2006) 3–19.
[13] K. Paparrizos *, N. Samaras, G. Stephanides, An efficient simplex type algorithm for sparse and dense linear programs, European Journal of Operational Research 148 (2003) 323–334.
[14] S. Smale, On the average number of the simplex method of linear programming, Mathematical Programming 27 (1983) 241-262.
[15] M.J. Todd, The many facets of linear programming, Mathematical Programming 91 (2002) 417- 436.
[16] Y. Ye, Interior Point Algorithm, Theory and Analysis, Wiley-Interscience, 1997.