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.
References
[1]
Todd, M.J. (2002) The Many Facets of Linear Programming. Mathematical Programming, 91, 417-436. https://doi.org/10.1007/s101070100261
[2]
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
[3]
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
[4]
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
[5]
Stone, J.J. (1958) The Cross-Section Method, an Algorithm for Linear Programming. DTIC Document, P-1490.
[6]
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
[7]
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
[8]
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
[9]
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
[10]
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
[11]
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
[12]
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
[13]
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
[14]
Corley, H.W., Rosenberger, J., Yeh, W.-C. and Sung, T.K. (2006) The Cosine Simplex Algorithm. The International Journal of Advanced Manufacturing Technology, 27, 1047-1050. https://doi.org/10.1007/s00170-004-2278-1
[15]
Pan, P.-Q. (1990) Practical Finite Pivoting Rules for the Simplex Method. Operations-Research-Spektrum, 12, 219-225. https://doi.org/10.1007/BF01721801
[16]
Junior, H.V. and Lins, M.P.E. (2005) An Improved Initial Basis for the Simplex Algorithm. Computers and Operations Research, 32, 1983-1993.
https://doi.org/10.1016/j.cor.2004.01.002
[17]
Corley, H.W. and Rosenberger, J.M. (2011) System, Method and Apparatus for Allocating Resources by Constraint Selection. US Patent No. 8082549.
[18]
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.
https://doi.org/10.1016/j.amc.2014.11.080
[19]
Saito, G., Corley, H.W. and Rosenberger, J. (2012) Constraint Optimal Selection Techniques (COSTs) for Linear Programming. American Journal of Operations Research, 3, 53-64. https://doi.org/10.4236/ajor.2013.31004
[20]
Noroziroshan, N., Corley, H.W. and Rosenberger, J. (2015) A Dynamic Active-Set Method for Linear Programming. American Journal of Operations Research, 5, 526-535. https://doi.org/10.4236/ajor.2015.56041
