Open AccessComputational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models
Author(s) -
Masar Al-Rabeeah,
Elias Munapo,
Ali Al-Hasani,
Santosh Kumar,
A Eberhard
Publication year - 2019
Publication title -
international journal of mathematical, engineering and management sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.228
H-Index - 10
ISSN - 2455-7749
DOI - 10.33889/ijmems.2019.4.5-090
Subject(s) - knapsack problem , branch and bound , integer programming , integer (computer science) , mathematics , upper and lower bounds , constraint (computer aided design) , mathematical optimization , branch and cut , linear programming , software , computer science , programming language , mathematical analysis , geometry
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.