A Theoretical Study on Designing a Criterion for Reducing the Number of Branches in the Branch and Bound (B&B) Method for (2×m) Linear Problems
DOI:
https://doi.org/10.37375/esj.v7i2.2951Keywords:
Branch and Bound ethod, Subproblems Non-intAbstract
The Branch and Bound Method is considered the most important approach for solving integer programming problems. It is particularly useful when the problem's solution is physically infeasible, meaning the problem's variables are indivisible. The method begins by finding the non-integer optimal solution (Non-int) and then branching the problem into two subproblems, effectively dividing the feasible solution space into two regions. The optimal solutions for these subproblems are found individually, and the process of branching and solving continues. The branching sequence stops when a subproblem has no feasible solution or when its solution yields integer values. The number of subproblems generated through branching increases significantly with the number of variables and constraints. Sheikh et al. (July 2022) identified criteria for selecting the subproblem most likely to contain the optimal integer solution and stopping the branching for others that do not. In this paper, we propose an additional criterion aimed at reducing the number of branches, where previous criteria have been insufficient. This new criterion can reduce the number of branches by approximately 25%, thereby saving time and effort in solving the problem (pruning the branch tree).
References
المراجع العربية
- الشـــــيخ, عبـــــد الله وآحــــرون. (يونيو 2022)."اختــــيار المتغيـــر ذو الكســر الأكبر أو الأصغر كأساس للتفريع في طريقة التفريع والتحديد"، The International Journal of Engineering and Information Technology. June (2022) Vol (9).
- الشــيخ, عبــد الله وآحــــرون. (يوليو 2022)." دراسة تحليلية للبحث في شجرة التفريعات في طريقة التفريع والتحديد (B&B)(دراسة نظرية للمشاكل الخطية من نوع 2m×)"، مجلة البحوث الأكاديمية (العلوم التطبيقية). (2022) Vol (22)، 20-34.
. المراجع الأجنبية
- Achterberg, T., Koch, T., & Martin, A. (2018). Branching on general disjunctions. Mathematical Programming, 188(1), 69-95.
- A. H. Land and A. G. Doig.(1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No3.
- Berthold, T. (2021). Learning-based branching in integer programming. Annals of Operations Research, 304(1), 17-47.
- Dinakar Gade, Simge K¨u¸c¨ukyavuz, & Suvrajeet Sen,(2012). Integrated Systems Engineering 210 Baker Systems, 1971 Neil Avenue The Ohio State University, Columbus.OH.43210 {gade.6,kucukyavuz.2,sen.22}@osu.edu August 15, 2012.
- Elias Munapo. (2020).Improvement of the Branch and Bound Algorithm for Solving the Knapsack Linear Integer Problem. Eastern-European Journal of Enterprise Technologies2(4 (104)), 59-69.
- F. Ortega, L.A. Wolsey. (2003). A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow Problem. Networks, 143–158.
- Fischetti, M., Salvagnin, D., & Zanette, A. (2017). Minimal branching rule for mixed-integer linear programming. European Journal of Operational Research, 263(3), 715-723.
- J.T. Linderoth, M.W.P. Savelsbergh .(1999). A computational study of search strategies for mixed integer programming. INFORMS J. Comput11, 173.
- Koch, T., Ralphs, T., Shinano, Y., &Vigerske, S. (2019). Solving hard mixed-integer programming problems with MIP solvers and supercomputers. OR Spectrum, 41(4), 865-898.
- Lodi, A., Zarpellon, G., & Jo, J. (2021). Learning to Branch in Mixed-Integer Programming. Journal of Machine Learning Research, 22(1), 33-47.
- M. Fischetti, M. Monaci, O. G¨unl¨uk, & G.J. Woeginger (Eds.). (2011). Integer Programming and Combinatoral Optimization, in: Lecture Notes in Computer Science, vol. 6655, Springer, Berlin, Heidelberg, 183-191.
- T. Achterberg, T. Koch, & A. Martin. (2005). Branching rules revisited. Oper. Res. Lett. 33, 42-54.
