International Journal of Mathematical, Engineering and Management Sciences

ISSN: 2455-7749

A Hybrid Strategy for Reducing Feasible Convex Space and the Number of Variables for Solving a Conventional Large LP Model

Santosh Kumar
Department of Mathematics and Statistics, University of Melbourne, Parkville, Victoria, Australia.

Elias Munapo
School of Economics and Decision Sciences, North West University, Mafikeng Campus, Mafikeng, South Africa.

‘Maseka Lesaoana
Department of Statistics and Operations Research, School of Mathematical and Computer Sciences, University of Limpopo, Turf loop Campus Private Bag X1106, Sovenga 0727, South Africa.

Philimon Nyamugure
Department of Statistics and Operations Research, National University of Science and Technology, PO Box AC939, Ascot, Bulawayo, Zimbabwe.

Nidhi Agarwal
Government Girls Senior Secondary School, Kota, Rajasthan, India.

DOI https://dx.doi.org/10.33889/IJMEMS.2017.2.4-017

Received on November 27, 2016
  ;
Accepted on December 26, 2016

Abstract

This paper considers a conventional linear programming model of ‘n’ variables and ‘m’ constraints. In the proposed method, we deal with n_1 number of variables, where n_1≤n and use a strategic move to reduce the feasible convex search space before embarking on the simplex method. The feasible space reduction process can be repeated, if desired.

Keywords- Linear programming model, Simplex method, Feasible space reduction, Reduced number of variables.

Citation

Kumar, S., Munapo, E., Lesaoana, ., Nyamugure, P., & Agarwal, N. (2016). A Hybrid Strategy for Reducing Feasible Convex Space and the Number of Variables for Solving a Conventional Large LP Model. International Journal of Mathematical, Engineering and Management Sciences, 2(4), 213-230. https://dx.doi.org/10.33889/IJMEMS.2017.2.4-017.

Conflict of Interest

Acknowledgements

We are thankful to the referee for constructive suggestions.

References

Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton, NJ.

Forrest, J. J., & Goldfarb, D. (1992). Steepest-edge simplex algorithms for linear programming. Mathematical Programming, 57(1-3), 341-374.

Gay, D. M., Overton, M. L., & Wright, M. H. (1998). A primal-dual interior method for nonconvex nonlinear programming. In Advances in Nonlinear Programming, 31-56. Springer US.

Karmarkar, N. (1984, December). A new polynomial-time algorithm for linear programming. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, 302-311. ACM.

Khachiyan, L. G. (1980). A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20(1), 53-72.

Klee, V., & Minty, G. J. (1972). How good is the Simplex algorithm? Inequalities, III, Proc. of the third symposium. Academic Press, 159-175.

Kumar, S. (2005). Information recycling mathematical methods for protean systems: A path-way approach. South African Journal of Industrial Engineering, 16(2), 81-101.

Kumar, S. (2006). Information recycling mathematical method: A path-way approach to geometric programs. South African Journal of Industrial Engineering, 17(2), 127-143.

Kumar, S., & Munapo, E. (2012). Some lateral ideas and their applications for developing new solution procedures for a pure integer programming model, Keynote address, Proc. Of Herbal International Conference on Applications of Mathematics and Statistics for Intelligent solutions through Mathematics and Statistics, Edited by Marriappan, Srinivasan and Amritraj, Excell India Publisher, 13-21.

Munapo, E., & Kumar, S. (2013). Solving large-scale linear optimization problem with non-negative coefficients by transforming into a 2-variable LP problem. ASOR Bulletin, 32(1), 1-12.

Munapo, E., Kumar, S., Lesaoana, M., & Nyamugure, P. (2014). Solving a large scale LP model with non-negative coefficients: A hybrid search over the extreme points and the normal direction to the given objective function. ASOR Bulletin, 33(1), 11-23.

Nyamugure, P., Munapo, E., Lesaoana, ‘M., & Kumar, S. (2017). A heuristic for a mixed integer program using the characteristic equation approach. International Journal of Mathematical, Engineering and Management Sciences, 2(1), 1-16.

Roos, C., Terlaky, T., & Vial, J. P. (2006). Interior point methods for linear optimization. Springer Science & Business Media.

Small, S. (1983). On the average speed of the simplex method in linear programming. Mathematical Programming, 27, 241-262.

Vanderbei, R. J. (2001). Linear programming: foundations and extensions. International Series in Operations Research & Management Science.

Vanderbei, R. J. (2008). Linear programming: foundations and extensions. Third Edition, Springer, pp 48.

Wright, M. H. (1998). The interior-point revolution in constrained optimization. In High Performance Algorithms and Software in Nonlinear Optimization, 24, 359-381. Springer US.

Wright, S. (1997). Primal-dual Interior methods. SIAM, Philadelphia.

Ye, Y. (2011). Interior point algorithms: theory and analysis, 44. John Wiley & Sons.

Zadeh, N. (2009). What is the worst case behavior of the simplex algorithm? Polyhedral computation, 48, 131-143.

Zoutendijk, G. (1960). Methods of feasible directions: a study in linear and non-linear programming. Elsevier.

Privacy Policy| Terms & Conditions