دراسة نظرية لتصميم معيار يسهم في تقليص عدد تفريعات طريقة التفريع والتحديد (B&B) للمشاكل الخطية من نوع (2×m)
DOI:
https://doi.org/10.37375/esj.v7i2.2951الكلمات المفتاحية:
التفريع والتحديد، المشاكل الفرعية، Non-intالملخص
تعتبر طـريقة التفـريع والتحـديد (Branch and Bound Method) أهم الطرق المستخدمة في حل مشاكل برمجة العدد الصحيح ، وتستخدم عندما يكون حل المشكلة غير منطقي من الناحية الفيزيائية، بمعنى عندما تكون متغيرات المشكلة غير قابلة للتجزئة ، وتبـدأ آلية عمل هذه الطريقة انطلاقاً من الحــل الأمثـــل (Non-int)، وذلك بتفريع المشكلة إلى مشكلتين فرعيتين ، وهذا يعني تجزئة منطقة الحلول الممكنة لمنطقتين، ومن تم إيجاد الحل الأمثل لهاتين المشكلتين كلاً على حدة، ويتم الاستمرار في تفريع المشاكل الفرعية وإيجاد حلولها. ويتم التوقف عن سلسلة التفريعات في حالة عـدم وجـود حــل للمشكلة الفرعيـــة أو عندما تكون قيم حلها قيم صحيحة (Integer). إن عدد المشاكل الفرعية الناتجة من عملية التفريع تزداد بشكل كبير بزيادة عدد متغيراتها وعدد قيودها، وقد توصل الشيخ وأخرون (يوليو 2022) لتحديد المعايير (Criterions) التي يتم استخدامها في بعض الحالات في تحديد المشكلة الفرعية الواجب تفريعها (المشكلة المرشحة لاحتواء الحل الأمثل Int)) ، والتوقف عن تفريع الأخرى (التي لا تحتوي على هذا الحل) ، وفي هذه الورقة تم تصميم معيار أخر لتقليص عدد التفريعات التي عجزت عليها المعايير المستخدمة في الورقة المذكورة ، بهدف توفير الوقت والجهد اللازم لحل المشكلة (تقليص شجرة التفريعات)، حيث يمكن عن طريق استخدام هذا المعيار تقليص ما يقارب على 25% من عدد التفريعات.
المراجع
المراجع العربية
- الشـــــيخ, عبـــــد الله وآحــــرون. (يونيو 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.
