Research ArticleOpen AccessGoogle Scholar indexed
Posterior Constraint Selection for Nonnegative Linear Programming
Center on Stochastic Modeling, Optimization, & Statistics (COSMOS), The University of Texas at Arlington, Arlington, TX, USA
Center on Stochastic Modeling, Optimization, & Statistics (COSMOS), The University of Texas at Arlington, Arlington, TX, USA
Center on Stochastic Modeling, Optimization, & Statistics (COSMOS), The University of Texas at Arlington, Arlington, TX, USA
- 1 Center on Stochastic Modeling, Optimization, & Statistics (COSMOS), The University of Texas at Arlington, Arlington, TX, USA
- 2 Center on Stochastic Modeling, Optimization, & Statistics (COSMOS), The University of Texas at Arlington, Arlington, TX, USA
- 3 Center on Stochastic Modeling, Optimization, & Statistics (COSMOS), The University of Texas at Arlington, Arlington, TX, USA
American Journal of Operations Research·Volume 07 (2016)·Pages 26–40·Published 27 December 2016·DOI10.4236/ajor.2017.71002
Copy link · social · email
Abstract
Posterior constraint optimal selection techniques (COSTs) are developed for nonnegative linear programming problems (NNLPs), and a geometric interpretation is provided. The posterior approach is used in both a dynamic and non-dynamic active-set framework. The computational performance of these methods is compared with the CPLEX standard linear programming algorithms, with two most-violated constraint approaches, and with previously developed COST algorithms for large-scale problems.
KeywordsLinear ProgrammingNonnegative Linear ProgrammingLarge-Scale ProblemsActive Set MethodsConstraint SelectionPosterior MethodCOSTs
- Todd, M.J. (2002) The Many Facets of Linear Programming. Mathematical Programming, 91, 417-436. https://doi.org/10.1007/s101070100261
- Dare, P. and Saleh, H. (2000) GPS Network Design: Logistics Solution Using Optimal and Near-Optimal Methods. Journal of Geodesy, 74, 467-478. https://doi.org/10.1007/s001900000104
- Rosenberger, J.M., Johnson, E.L. and Nemhauser, G.L. (2003) Rerouting Aircraft for Airline Recovery. Transportation Science, 37, 408-421. https://doi.org/10.1287/trsc.37.4.408.23271
- Li, H.-L. and Fu, C.-J. (2005) A Linear Programming Approach for Identifying a Consensus Sequence on DNA Sequences. Bioinformatics, 21, 1838-1845. https://doi.org/10.1093/bioinformatics/bti286
- Stone, J.J. (1958) The Cross-Section Method, an Algorithm for Linear Programming. DTIC Document, P-1490.
- 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. https://doi.org/10.1287/mnsc.12.7.588
- Adler, I., Karp, R. and Shamir, R. (1986) A Family of Simplex Variants Solving an Linear Program in Expected Number of Pivot Steps Depending on d Only. Mathematics of Operations Research, 11, 570-590. https://doi.org/10.1287/moor.11.4.570
- Zeleny, M. (1986) An External Reconstruction Approach (ERA) to Linear Programming. Computers & Operations Research, B, 95-100. https://doi.org/10.1016/0305-0548(86)90067-5
- Myers, D.C. and Shih, W. (1988) A Constraint Selection Technique for a Class of Linear Programs. Operations Research Letters, 7, 191-195. https://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. https://doi.org/10.1016/0167-6377(93)90045-I
- 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. https://doi.org/10.1287/opre.40.5.885
- Barnhart, C., Johnson, E., Nemhauser, G., Savelsbergh, M. and Vance, P. (1998) Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research, 46, 316-329. https://doi.org/10.1287/opre.46.3.316
- Mitchell, J.E. (2000) Computational Experience with an Interior Point Cutting Plane Algorithm. SIAM Journal on Optimization, 10, 1212-1227. https://doi.org/10.1137/S1052623497324242