IJMEMES logo

International Journal of Mathematical, Engineering and Management Sciences

ISSN: 2455-7749 . Open Access


A Heuristic for a Mixed Integer Program using the Characteristic Equation Approach

A Heuristic for a Mixed Integer Program using the Characteristic Equation Approach

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

Received on October 21, 2016
  ;
Accepted on November 09, 2016

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.