International Journal of Mathematical, Engineering and Management Sciences

ISSN: 2455-7749

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


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.


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



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.