Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models
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 reformulation...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ram Arti Publishers
2019-10-01
|
| Series: | International Journal of Mathematical, Engineering and Management Sciences |
| Subjects: | |
| Online Access: | https://www.ijmems.in/assets//90-IJMEMS-19-234-Vol.%204,%20No.%205,%201140%E2%80%931153,%202019.pdf |
| _version_ | 1811272304485728256 |
|---|---|
| author | Masar Al-Rabeeah Elias Munapo Ali Al-Hasani Santosh Kumar Andrew Eberhard |
| author_facet | Masar Al-Rabeeah Elias Munapo Ali Al-Hasani Santosh Kumar Andrew Eberhard |
| author_sort | Masar Al-Rabeeah |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T22:36:51Z |
| format | Article |
| id | doaj.art-159232cc03434dc890f4ed8fb35a44e9 |
| institution | Directory Open Access Journal |
| issn | 2455-7749 2455-7749 |
| language | English |
| last_indexed | 2024-04-12T22:36:51Z |
| publishDate | 2019-10-01 |
| publisher | Ram Arti Publishers |
| record_format | Article |
| series | International Journal of Mathematical, Engineering and Management Sciences |
| spelling | doaj.art-159232cc03434dc890f4ed8fb35a44e92022-12-22T03:13:49ZengRam Arti PublishersInternational Journal of Mathematical, Engineering and Management Sciences2455-77492455-77492019-10-01451140115310.33889/IJMEMS.2019.4.5-090Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related ModelsMasar Al-Rabeeah0Elias Munapo1Ali Al-Hasani2Santosh Kumar3Andrew Eberhard4School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia, Department of Mathematics, College of Sciences, University of Basrah, Al- Basrah, IraqSchool of Economic and Decision Sciences, North West University, Mafikeng Campus, South AfricaSchool of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia., Department of Mathematics, College of Sciences, University of Basrah, Al- Basrah, IraqSchool of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia, Department of Mathematics and Statistics, University of Melbourne, Melbourne, AustraliaSchool of Mathematical and Geospatial Sciences, RMIT University, Melbourne, AustraliaIn 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.https://www.ijmems.in/assets//90-IJMEMS-19-234-Vol.%204,%20No.%205,%201140%E2%80%931153,%202019.pdfReformulationBranch and boundGeneral linear integer programsKnapsack problemBi-objective modelsNon-dominated point set |
| spellingShingle | Masar Al-Rabeeah Elias Munapo Ali Al-Hasani Santosh Kumar Andrew Eberhard 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 Reformulation Branch and bound General linear integer programs Knapsack problem Bi-objective models Non-dominated point set |
| title | Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models |
| title_full | Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models |
| title_fullStr | Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models |
| title_full_unstemmed | Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models |
| title_short | Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models |
| title_sort | computational enhancement in the application of the branch and bound method for linear integer programs and related models |
| topic | Reformulation Branch and bound General linear integer programs Knapsack problem Bi-objective models Non-dominated point set |
| url | https://www.ijmems.in/assets//90-IJMEMS-19-234-Vol.%204,%20No.%205,%201140%E2%80%931153,%202019.pdf |
| work_keys_str_mv | AT masaralrabeeah computationalenhancementintheapplicationofthebranchandboundmethodforlinearintegerprogramsandrelatedmodels AT eliasmunapo computationalenhancementintheapplicationofthebranchandboundmethodforlinearintegerprogramsandrelatedmodels AT alialhasani computationalenhancementintheapplicationofthebranchandboundmethodforlinearintegerprogramsandrelatedmodels AT santoshkumar computationalenhancementintheapplicationofthebranchandboundmethodforlinearintegerprogramsandrelatedmodels AT andreweberhard computationalenhancementintheapplicationofthebranchandboundmethodforlinearintegerprogramsandrelatedmodels |