IJMEMES logo

International Journal of Mathematical, Engineering and Management Sciences

ISSN: 2455-7749 . Open Access


Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models

Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models

Masar Al-Rabeeah
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia; Department of Mathematics, College of Sciences University of Basrah, Al- Basrah, Iraq.

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

Ali Al-Hasani
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia; Department of Mathematics, College of Sciences University of Basrah, Al- Basrah, Iraq.

Santosh Kumar
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia; Department of Mathematics and Statistics University of Melbourne, Melbourne, Australia.

Andrew Eberhard
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia.

DOI https://dx.doi.org/10.33889/IJMEMS.2019.4.5-090

Received on April 03, 2019
  ;
Accepted on June 10, 2019

Abstract

In this paper, a reformulation that was proposed for a knapsack problem has been extended to single and bi-objective linear integer programs. A further reformulation by adding an upper bound constraint for a knapsack problem is also proposed and extended to the bi-objective case. These reformulations significantly reduce the number of branch and bound iterations with respect to these models. Numerical illustrations have been presented and computational experiments have been carried out to compare the behaviour before and after the reformulation. For this purpose, Tora software was used.

Keywords- Reformulation, Branch and bound, General linear integer programs, Knapsack problem, Bi-objective models, Non-dominated point set.

Citation

Al-Rabeeah, M., Munapo, E., Al-Hasani, A., Kumar, S., & Eberhard, A. (2019). Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models. International Journal of Mathematical, Engineering and Management Sciences, 4(5), 1140-1153. https://dx.doi.org/10.33889/IJMEMS.2019.4.5-090.