Philimon Nyamugure
Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe.
Elias Munapo
School of Economics and Decision Sciences, North West University, Mafikeng Campus Mafikeng, South Africa.
‘Maseka Lesaoana
Department of Statistics and Operations Research, University of Limpopo, Private Bag X1106, Sovenga 0727, South Africa.
Santosh Kumar
Department of Mathematics and Statistics, University of Melbourne, Melbourne, Australia.
DOI https://dx.doi.org/10.33889/IJMEMS.2017.2.1-001
Abstract
While most linear programming (LP) problems can be solved in polynomial time, pure and mixed integer problems are NP-hard and there are no known polynomial time algorithms to solve these problems. A characteristic equation (CE) was developed to solve a pure integer program (PIP). This paper presents a heuristic that generates a feasible solution along with the bounds for the NP-hard mixed integer program (MIP) model by solving the LP relaxation and the PIP, using the CE.
Keywords- Mixed integer program, Pure integer program, Characteristic equation, LP relaxation.
Citation
Nyamugure, P., Munapo, E., Lesaoana, â., & 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. https://dx.doi.org/10.33889/IJMEMS.2017.2.1-001.