Branch and bound — শাখা ও সীমা পদ্ধতি

From Systems analysis wiki
Jump to navigation Jump to search

শাখা ও সীমা পদ্ধতি (ইংরেজি: Branch and Bound, সংক্ষেপে B&B বা BnB) — এটি বিযুক্ত এবং সমন্বয়মূলক অপ্টিমাইজেশন সমস্যা, বিশেষত NP-কঠিন সমস্যা সমাধানের জন্য সুনির্দিষ্ট অ্যালগরিদম নির্মাণের একটি সাধারণ প্যারাডাইম[1]। পদ্ধতিটি একটি নির্দেশিত অনুসন্ধান কৌশল, যেখানে সকল গ্রহণযোগ্য সমাধানের সমগ্র সেটটি ক্রমান্বয়ে উপসেটে বিভক্ত করা হয় (শাখায়ন), এবং প্রতিটির জন্য লক্ষ্য ফাংশনের মান সম্পর্কে অনুমান (সীমা) গণনা করা হয়। এই অনুমানগুলি সেই উপসেটগুলিকে বাদ দিতে (ছেঁটে ফেলতে) সক্ষম করে যেগুলি নিশ্চিতভাবে সর্বোত্তম সমাধান ধারণ করে না, যা অনুসন্ধান পরিসরকে উল্লেখযোগ্যভাবে সংকুচিত করে[2]।

পদ্ধতিটি সর্বপ্রথম ১৯৬০ সালে A. Land এবং A. Doig কর্তৃক পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা সমাধানের জন্য প্রস্তাবিত হয়েছিল[3]। তখন থেকে এটি অপারেশন রিসার্চ এবং কম্পিউটার বিজ্ঞানের অন্যতম মৌলিক পদ্ধতি হয়ে উঠেছে। পদ্ধতির মূল বৈশিষ্ট্য হলো এর নমনীয়তা: এটি কোনো নির্দিষ্ট অ্যালগরিদম নয়, বরং একটি উচ্চ-স্তরের কৌশলগত কাঠামো (framework), যা সমাধান করা সমস্যার কাঠামোর সাথে অভিযোজিত।

পদ্ধতির মূল উপাদান

পদ্ধতির ভিত্তিতে রয়েছে তিনটি মৌলিক অপারেশন, যা অনুসন্ধান গাছে সংগঠিত সমাধান পরিসরের উপসেটগুলিতে প্রয়োগ করা হয়।

  • শাখায়ন (ইংরেজি: Branching) — এটি বর্তমান গ্রহণযোগ্য সমাধানের সেট Si-কে কয়েকটি ছোট, সাধারণত অ-ছেদকারী উপসেট Si1,Si2,…,Sik-এ পুনরাবৃত্তিমূলকভাবে বিভক্ত করার প্রক্রিয়া। প্রতিটি এরূপ উপসেট একটি নতুন উপসমস্যার সাথে সম্পর্কিত এবং অনুসন্ধান গাছে একটি শিশু নোড হিসেবে উপস্থাপিত হয়। উদাহরণস্বরূপ, পূর্ণসংখ্যা প্রোগ্রামিং সমস্যায় শাখায়ন প্রায়ই সেই চলকের উপর করা হয় যার LP-relaxation সমাধানে ভগ্নাংশ মান রয়েছে।
  • সীমা নির্ধারণ (ইংরেজি: Bounding) — অনুসন্ধান গাছের প্রতিটি নোডের জন্য (অর্থাৎ প্রতিটি উপসমস্যার জন্য) লক্ষ্য ফাংশনের মানের একটি অনুমান গণনা করা হয়। ন্যূনীকরণ সমস্যার জন্য এটি হলো নিম্ন সীমা (lower bound), যা প্রদত্ত উপসেটের যেকোনো সমাধানের জন্য নিচ থেকে একটি নিশ্চিত অনুমান। প্রায়শই এই অনুমান মূল উপসমস্যার relaxation সমাধান করে পাওয়া যায় — একটি সরলীকৃত সংস্করণ যেখানে কিছু জটিল সীমাবদ্ধতা (যেমন পূর্ণসংখ্যা) সাময়িকভাবে উপেক্ষা করা হয়। সবচেয়ে প্রচলিত হলো LP-relaxation।
  • ছাঁটাই (ইংরেজি: Pruning) — এটি সেই নোডগুলিকে (এবং তাদের সম্পূর্ণ উপগাছ) বিবেচনা থেকে বাদ দেওয়ার প্রক্রিয়া যেগুলি নিশ্চিতভাবে সর্বোত্তম সমাধান ধারণ করতে পারে না। নিচের যেকোনো একটি ক্ষেত্রে একটি নোড ছাঁটাই করা হয়:
  1. সীমা দ্বারা ছাঁটাই: প্রদত্ত নোডের নিম্ন সীমা বর্তমানে পাওয়া সেরা গ্রহণযোগ্য সমাধানের মানের চেয়ে ভালো নয় (অর্থাৎ ন্যূনীকরণ সমস্যায় তা বড় বা সমান), যাকে রেকর্ড (incumbent) বলা হয়।
  2. গ্রহণযোগ্যতা দ্বারা ছাঁটাই: নোডের relaxation সমাধান মূল সমস্যার জন্য গ্রহণযোগ্য (যেমন সকল চলক পূর্ণসংখ্যা)। এই সমাধানটি বর্তমান রেকর্ডের সাথে তুলনা করা হয় এবং যদি এটি ভালো হয় তবে রেকর্ড আপডেট করা হয়। এই নোড থেকে আর শাখায়নের প্রয়োজন নেই।
  3. অসম্ভব্যতা দ্বারা ছাঁটাই: নোডের সাথে সম্পর্কিত উপসমস্যার কোনো গ্রহণযোগ্য সমাধান নেই।

সাধারণ অ্যালগরিদম

ন্যূনীকরণ সমস্যার জন্য শাখা ও সীমা পদ্ধতির সাধারণীকৃত অ্যালগরিদম নিচের ধাপগুলিতে বর্ণনা করা যায়:

  1. প্রাথমিককরণ: একটি প্রাথমিক গ্রহণযোগ্য সমাধান খুঁজে বের করুন (যেমন, কোনো heuristic ব্যবহার করে) এবং এর মানকে প্রাথমিক উপরের সীমা (রেকর্ড) হিসেবে নির্ধারণ করুন U। সক্রিয় নোডের একটি সারি Q তৈরি করুন যাতে মূল নোড (মূল সমস্যা) থাকে।
  2. মূল চক্র: যতক্ষণ সারি Q খালি না হয়:
    • অনুসন্ধান কৌশল অনুযায়ী (যেমন গভীরতা-প্রথম বা সেরা-অনুমান অনুসন্ধান) Q থেকে একটি নোড নির্বাচন করুন।
    • এই নোডের জন্য relaxation সমাধান করুন, নিম্ন সীমা L পান।
    • যদি L≥U হয় তবে নোডটি ছাঁটাই করুন।
    • যদি relaxation সমাধান মূল সমস্যার জন্য গ্রহণযোগ্য হয়, রেকর্ড আপডেট করুন: U←L।
    • যদি নোডটি ছাঁটাই না হয় এবং সমাধান গ্রহণযোগ্য না হয়, তবে শাখায়ন করুন — এটিকে শিশু নোডে বিভক্ত করুন এবং সেগুলি সারি Q-এ যোগ করুন।
  3. সমাপ্তি: যখন সারি Q খালি হয়ে যায়, অ্যালগরিদম শেষ হয়। রেকর্ড U-এর সাথে সম্পর্কিত পাওয়া সমাধানটি বৈশ্বিকভাবে সর্বোত্তম।

মূল বৈশিষ্ট্য ও উপপাদ্য

  • সঠিকতা ও অভিসরণ: যদি গ্রহণযোগ্য সমাধানের সেট সসীম হয় এবং শাখায়ন পদ্ধতি অভিসারী হয় (অর্থাৎ পুনরাবৃত্তিমূলক বিভাজনে উপসেটগুলি বিন্দুতে "সংকুচিত" হয়), তবে অ্যালগরিদম সসীম সংখ্যক ধাপে বৈশ্বিকভাবে সর্বোত্তম সমাধান খুঁজে পাওয়ার নিশ্চয়তা দেয়[4]।
  • অনুসন্ধান কৌশল: অ্যালগরিদমের দক্ষতা মূলত পরবর্তী নোড নির্বাচনের কৌশলের উপর নির্ভর করে (যেমন গভীরতা-প্রথম, প্রস্থ-প্রথম, সেরা-অনুমান অনুসন্ধান) এবং শাখায়নের জন্য চলক নির্বাচনের উপর। আধুনিক solver-রা প্রায়ই হাইব্রিড কৌশল ব্যবহার করে[5]।

উদাহরণ

  • পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা: পদ্ধতির ক্লাসিক প্রয়োগ। Relaxation হিসেবে রৈখিক প্রোগ্রামিং ব্যবহার করা হয়। শাখায়ন ঘটে ভগ্নাংশ চলক xj-এর উপর, যা অতিরিক্ত সীমাবদ্ধতা xj≤⌊xj*⌋ এবং xj≥⌈xj*⌉ সহ দুটি উপসমস্যা তৈরি করে।
  • ভ্রমণকারী বিক্রেতার সমস্যা: সমাধান পরিসর হলো গ্রাফে সকল সম্ভাব্য Hamiltonian চক্র। শাখায়ন ধার দিয়ে করা যেতে পারে (মার্গে ধার অন্তর্ভুক্ত/বাদ দেওয়া)। নিম্ন সীমা হিসেবে সহজতর সমস্যার সমাধান ব্যবহার করা যেতে পারে, যেমন অ্যাসাইনমেন্ট সমস্যা বা ন্যূনতম বিস্তৃত গাছ নির্মাণ[6]।

সম্পর্কিত ধারণা ও প্রয়োগ

  • Branch-and-Cut পদ্ধতি: একটি হাইব্রিড পদ্ধতি যা B&B-কে কর্তন সমতল পদ্ধতির সাথে একত্রিত করে। অনুসন্ধান গাছের প্রতিটি নোডে, relaxation সমাধানের পাশাপাশি অতিরিক্ত অসমতা (কাট) তৈরি করা হয় যা নিম্ন সীমাকে শক্তিশালী করে, ফলে শাখাগুলির আরও কার্যকর ছাঁটাই হয়।
  • Backtracking অনুসন্ধান: শাখা ও সীমা পদ্ধতিকে অপ্টিমাইজেশন সমস্যার জন্য এই অ্যালগরিদমের সাধারণীকরণ হিসেবে বিবেচনা করা যায়।
  • আলফা-বেটা ছাঁটাই: গেম গাছে নিশ্চিতভাবে পরাজিত শাখাগুলি ছাঁটাই করতে ব্যবহৃত একটি ধারণাগত সাদৃশ্য।

আরও দেখুন

  • পূর্ণসংখ্যা প্রোগ্রামিং
  • সমন্বয়মূলক অপ্টিমাইজেশন
  • ভ্রমণকারী বিক্রেতার সমস্যা
  • NP-কঠিন সমস্যা
  • সিম্প্লেক্স পদ্ধতি

টীকা

[1] [2] [3] [4] [5] [6] </references>

  1. ↑ 1.0 1.1 Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
  2. ↑ 2.0 2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ 3.0 3.1 Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
  4. ↑ 4.0 4.1 Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
  5. ↑ 5.0 5.1 Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
  6. ↑ 6.0 6.1 Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf
Retrieved from "https://systems-analysis.ru/int/index.php?title=Branch_and_bound_—_শাখা_ও_সীমা_পদ্ধতি&oldid=17056"