Constraint Optimal Selection Techniques (COSTs) for Linear Programming

Goh Saito, H. W. Corley, Jay M. Rosenberger

IMSE Department, The University of Texas at Arlington, Arlington, USA.

DOI: 10.4236/ajor.2013.31004                

Abstract

We describe a new active-set, cutting-plane Constraint Optimal Selection Technique (COST) for solving general linear programming problems. We describe strategies to bound the initial problem and simultaneously add multiple constraints. We give an interpretation of the new COST’s selection rule, which considers both the depth of constraints as well as their angles from the objective function. We provide computational comparisons of the COST with existing linear programming algorithms, including other COSTs in the literature, for some large-scale problems. Finally, we discuss conclusions and future research.

Keywords

Linear Programming; Large-Scale Linear Programming; Cutting Planes; Active-Set Methods; Constraint Selection; COSTs

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	H. W. Corley and J. M. Rosenberger, “System, Method and Apparatus for Allocating Resources by Constraint Selection,” US Patent No. 8082549, 2011. http://patft1.uspto.gov/netacgi/nph-Parser?patentnumber=8082549
[2]	G. Saito, H. W. Corley, J. M. Rosenberger and T.-K. Sung, “Constraint Optimal Selection Techniques (COSTs) for Nonnegative Linear Programming Problems,” Technical Report, The University of Texas, Arlington, 2012. http://www.uta.edu/cosmos/TechReports/COSMOS-04-02.pdf
[3]	M. J. Todd, “The Many Facets of Linear Programming,” Mathematical Programming, Vol. 91, No. 3, 2002, pp. 417-436.
[4]	J. M. Rosenberger, E. L. Johnson and G. L. Nemhauser, “Rerouting Aircraft for Aircraft Recovery,” Transportation Science, Vol. 37, No. 4, 2003, pp. 408-421.
[5]	J. J. Stone, “The Cross-Section Method: An Algorithm for Linear Programming,” Rand Corporation Memorandum P-1490, 1958.
[6]	G. L. Thompson, F. M. Tonge and S. Zionts, “Techniques for Removing Nonbinding Constraints and Extraneous Variables from Linear Programming Problems,” Management Science, Vol. 12, No. 7, 1966, pp. 588-608.
[7]	I. Adler, R. Karp and R. Shamir, “A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivots Steps Depending on d Only,” Mathematics of Operations Research, Vol. 11, No. 4, 1986, pp. 570-590.
[8]	M. Zeleny, “An External Reconstruction Approach (ERA) to Linear Programming,” Computers & Operations Research, Vol. 13, No. 1, 1986, pp. 95-100.
[9]	D. C. Myers and W. Shih, “A Constraint Selection Technique for a Class of Linear Programs,” Operations Research Letters, Vol. 7, No. 4, 1988, pp. 191-195.
[10]	N. D. Curet, “A Primal-Dual Simplex Method for Linear Programs,” Operations Research Letters, Vol. 13, No. 4, 1993, pp. 223-237.
[11]	M. S. Bazaraa, J. J. Jarvis and H. D. Sherali, “Linear Programming and Network Flows,” 3rd Edition, John Wiley, New York, 2005.
[12]	A. W. Naylor and G. R. Sell, “Linear Operator Theory in Engineering and Science,” Springer-Verlag, New York, 1982. doi:10.1007/978-1-4612-5773-8
[13]	P.-Q. Pan, “Practical Finite Pivoting Rules for the Simplex Method,” Operations-Research-Spektrum, Vol. 12, No. 4, 1990, pp. 219-225.
[14]	P.-Q. Pan, “A Simplex-Like Method with Bisection for Linear Programming,” Optimization, Vol. 22, No. 5, 1991, pp. 717-743.
[15]	F. Trigos, J. Frausto-Solis and R. R. Rivera-Lopez, “A Simplex-Cosine Method for Solving Hard Linear Problems,” Advances in Simulation, System Theory and Systems Engineering, Vol. 70X, 2002, pp. 27-32. http://lsog.tol.itesm.mx/publications.html
[16]	H. Vieira Jr. and M. P. E. Lins, “An Improved Initial Basis for the Simplex Algorithm,” Computers & Operations Research, Vol. 32, No. 8, 2005, pp. 1983-1993.
[17]	H. W. Corley, J. M. Rosenberger, W.-C. Yeh and T.-K. Sung, “The Cosine Simplex Algorithm,” The International Journal of Advanced Manufacturing Technology, Vol. 27, No. 9, 2006, pp. 1047-1050.
[18]	IMSE Library, The University of Texas, Arlington. http://imselib.uta.edu