**
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.

**Conflict of Interest**

**Acknowledgements**

**References**

Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.

Borsani, V., Matta, A., Beschi, G., & Sommaruga, F. (2006, October). A home care scheduling model for human resources. In 2006 International Conference on Service Systems and Service Management (Vol. 1, pp. 449-454). IEEE.

Bredstrom, D., & RÃ¶nnqvist, M. (2007). A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. NHH Dept. of Finance & Management Science Discussion Paper, (2007/7).

Burer, S., & Letchford, A. N. (2012). Non-convex mixed-integer nonlinear programming, a survey. Surveys in Operations Research and Management Science, 17(2), 97-106.

Dey, S. S., & Vielma, J. P. (2010, June). The ChvÃ¡tal-Gomory closure of an ellipsoid is a polyhedron. In International Conference on Integer Programming and Combinatorial Optimization (pp. 327-340). Springer Berlin Heidelberg.

Dohn, A., Kolind, E., & Clausen, J. (2009). The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach. Computers & Operations Research, 36(4), 1145-1157.

Fiorini, S., Massar, S., Pokutta, S., Tiwary, H. R., & de Wolf, R. (2012, May). Linear vs. semidefinite extended formulations, exponential separation and strong lower bounds. In Proceedings of the forty-fourth annual ACM symposium on Theory of Computing (pp. 95-106). ACM.

Geoffrion, A. M., & Marsten, R. E. (1972). Integer programming algorithms, A framework and state-of-the-art survey. Management Science, 18(9), 465-491.

Hillier, F.S. and Lieberman, G.J. (2001), Introduction to Operations Research, McGraw Hill, New York.

Jozefowiez, N., Laporte, G., & Semet, F. (2012). A generic branch-and-cut algorithm for multiobjective optimization problems: Application to the multilevel traveling salesman problem. INFORMS Journal on Computing, 24(4), 554-564.

Kaibel, V. (2011). Extended formulations in combinatorial optimization. arXiv preprint arXiv:1104.1023.

Kumar, S. and Munapo, E. (2012). Some Lateral Ideas and their applications for developing new solution procedures for a pure integer programming model, Keynote address, Proc. Of the Herbal International Conference on Applications of Mathematics and Statistics â€“ Intelligent solutions through Mathematics and Statistics, Edited by Mariappan, Srinivasan and Amritraj, Excel India Publisher, pp 13-21, January.

Kumar, S., Munapo, E. and Jones, B.C. (2007). An integer equation controlled descending path to a protean pure integer program. Indian Journal of Mathematics, 49(2), 211-237.

Laesanklang, W., Landa-Silva, D. and Castillo-Salazar, J.A. (2015). Mixed integer programming with decomposition to solve a workforce scheduling and routing problem. International Conference on Operations Research and Enterprise Systems.

MorÃ¡n, R., Diego, A., Santanu, S. Dey and Vielma, J. P. (2012). A strong dual for conic mixed-integer programs. SIAM Journal on Optimization, 22(3), 1136-1150.

Noraini, M.R. and Geraghty, J. (2011). Genetic Algorithm Performance with Different Selection Strategies in Solving TSP, Proceedings of the World Congress on Engineering, July 6-8, London, UK.

Rasmussen, M. S., Justesen, T., Dohn, A., & Larsen, J. (2012). The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies. European Journal of Operational Research, 219(3), 598-610.

Sen, S., & Sherali, H. D. (2006). Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Mathematical Programming, 106(2), 203-223.

Sherali, H. D. and Adams, W. P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one Programming problems. SIAM Journal on Discrete Mathematics, 3(3), 411-430.

Sourd, F. and Spanjaard, O. (2008). A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem. INFORMS Journal on Computing, 20(3),472-484.

Sridhar, S. (2014). Mixed-Integer programming approaches for some non-convex and combinatorial optimization problems (Doctoral dissertation, Stanford University).

Vielma, J. P. (2015). Mixed integer linear programming formulation techniques. Society for Industrial and Applied Mathematics, 57(1), 3â€“57.

YÄ±ldÄ±z, S., & Vielma, J. P. (2013). Incremental and encoding formulations for mixed integer programming. Operations Research Letters, 41(6), 654-658.