Research ArticleOpen AccessGoogle Scholar indexed
A Dynamic Active-Set Method for Linear Programming
IMSE Department, The University of Texas at Arlington, Arlington, USA
IMSE Department, The University of Texas at Arlington, Arlington, USA
IMSE Department, The University of Texas at Arlington, Arlington, USA
- 1 IMSE Department, The University of Texas at Arlington, Arlington, USA
- 2 IMSE Department, The University of Texas at Arlington, Arlington, USA
- 3 IMSE Department, The University of Texas at Arlington, Arlington, USA
American Journal of Operations Research·Volume 05 (2015)·Pages 526–535·Published 8 November 2015·DOI10.4236/ajor.2015.56041
Copy link · social · email
Abstract
An efficient active-set approach is presented for both nonnegative and general linear programming by adding varying numbers of constraints at each iteration. Computational experiments demonstrate that the proposed approach is significantly faster than previous active-set and standard linear programming algorithms.
KeywordsConstraint Optimal Selection TechniquesDynamic Active-Set MethodsLarge-Scale Linear ProgrammingLinear Programming
- Bixby, R.E., Gregory, J.W., Lustig, I.J., Marsten, R.E. and Shanno, D.F. (1992) Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods. Operations Research, 40, 885-897. http://dx.doi.org/10.1287/opre.40.5.885
- Rosenberger, J.M., Johnson, E.L. and Nemhauser, G.L. (2003) Rerouting Aircraft for Airline Recovery. Transportation Science, 37, 408-421. http://dx.doi.org/10.1287/trsc.37.4.408.23271
- Todd, M.J. (2002) The Many Facets of Linear Programming. Mathematical Programming, 91, 417-436. http://dx.doi.org/10.1007/s101070100261
- Elwes, R. (2012) The Algorithm That Runs the World. New Scientist, 215, 32-37. http://dx.doi.org/10.1016/S0262-4079(12)62078-8
- Dare, P. and Saleh, H. (2000) GPS Network Design: Logistics Solution Using Optimal and Near-Optimal Methods. Journal of Geodesy, 74, 467-478. http://dx.doi.org/10.1007/s001900000104
- Saito, G., Corley, H.W., Rosenberger, J.M., Sung, T.-K. and Noroziroshan, A. (2015) Constraint Optimal Selection Techniques (COSTs) for Nonnegative Linear Programming Problems. Applied Mathematics and Computation, 251, 586-598. http://dx.doi.org/10.1016/j.amc.2014.11.080
- Stone, J.J. (1958) The Cross-Section Method, an Algorithm for Linear Programming. DTIC Document, P-1490, 24.
- Thompson, G.L., Tonge, F.M. and Zionts, S. (1996) Techniques for Removing Nonbinding Constraints and Extraneous Variables from Linear Programming Problems. Management Science, 12, 588-608. http://dx.doi.org/10.1287/mnsc.12.7.588
- Myers, D.C. and Shih, W. (1988) A Constraint Selection Technique for a Class of Linear Programs. Operations Research Letters, 7, 191-195. http://dx.doi.org/10.1016/0167-6377(88)90027-2
- Curet, N.D. (1993) A Primal-Dual Simplex Method for Linear Programs. Operations Research Letters, 13, 233-237. http://dx.doi.org/10.1016/0167-6377(93)90045-I
- Adler, I., Karp, R. and Shamir, R. (1986) A Family of Simplex Variants Solving an m× d Linear Program in Expected Number of Pivot Steps Depending on d Only. Mathematics of Operations Research, 11, 570-590. http://dx.doi.org/10.1287/moor.11.4.570
- Zeleny, M. (1986) An External Reconstruction Approach (ERA) to Linear Programming. Computers & Operations Research, 13, 95-100. http://dx.doi.org/10.1016/0305-0548(86)90067-5
- Mitchell, J.E. (2000) Computational Experience with an Interior Point Cutting Plane Algorithm. SIAM Journal on Optimization, 10, 1212-1227. http://dx.doi.org/10.1137/S1052623497324242