Optimization Online


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

Masar Al-Rabeeah(masar.alrabeeah***at***rmit.edu.au)
Elias Munapo(emunapo***at***gmail.com)
Ali Al-Hasani(ali.alhasani***at***rmit.edu.au)
Santosh Kumar(Santosh.kumarau***at***gmail.com)
Andrew Eberhard(andy.eberhard***at***rmit.edu.au)

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.

Category 1: Applications -- OR and Management Sciences

Category 2: Other Topics (Multi-Criteria Optimization )

Citation: International Journal of Mathematical, Engineering and Management Sciences Vol. 4, No. 5, 11401153, 2019 https://dx.doi.org/10.33889/IJMEMS.2019.4.5-090

Download: [PDF]

Entry Submitted: 08/13/2019
Entry Accepted: 08/13/2019
Entry Last Modified: 08/13/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society