সবচেয়ে সুপরিচিত কম্বিনেটরিয়াল অপ্টিমাইজেশান সমস্যাগুলির মধ্যে একটি হল অ্যাসাইনমেন্ট সমস্যা । এখানে একটি উদাহরণ দেওয়া হল: ধরুন একদল কর্মীদের একটি সেট কাজ সম্পাদন করতে হবে, এবং প্রতিটি কর্মী এবং কাজের জন্য, কর্মীকে কাজের জন্য অর্পণ করার জন্য একটি খরচ আছে। সমস্যা হল প্রতিটি কর্মীকে সর্বাধিক একটি কাজের জন্য বরাদ্দ করা, যেখানে কোনও দুইজন কর্মী একই কাজ সম্পাদন করে না, মোট খরচ কমিয়ে দেয়।
আপনি নীচের গ্রাফ দ্বারা এই সমস্যাটি কল্পনা করতে পারেন, যেখানে চারজন কর্মী এবং চারটি কাজ রয়েছে। প্রান্তগুলি কাজগুলিতে কর্মীদের বরাদ্দ করার সমস্ত সম্ভাব্য উপায় উপস্থাপন করে। প্রান্তের লেবেলগুলি হল শ্রমিকদের কাজের জন্য বরাদ্দ করার খরচ।
একটি অ্যাসাইনমেন্ট প্রান্তগুলির একটি উপসেটের সাথে মিলে যায়, যেখানে প্রতিটি শ্রমিকের সর্বাধিক একটি প্রান্ত থাকে এবং একই কাজ করার জন্য কোন দুই শ্রমিকের প্রান্ত থাকে না। একটি সম্ভাব্য অ্যাসাইনমেন্ট নীচে দেখানো হয়েছে.
অ্যাসাইনমেন্টের মোট খরচ হল 70 + 55 + 95 + 45 = 265
পরবর্তী বিভাগটি দেখায় কিভাবে এমআইপি সল্ভার এবং সিপি-স্যাট সলভার ব্যবহার করে একটি অ্যাসাইনমেন্ট সমস্যা সমাধান করা যায়।
অ্যাসাইনমেন্ট সমস্যা সমাধানের জন্য অন্যান্য সরঞ্জাম
OR-Tools অ্যাসাইনমেন্ট সমস্যা সমাধানের জন্য আরও কয়েকটি সরঞ্জাম সরবরাহ করে, যা MIP বা CP সমাধানকারীদের চেয়ে দ্রুত হতে পারে:
যাইহোক, এই সরঞ্জামগুলি কেবলমাত্র সাধারণ ধরণের অ্যাসাইনমেন্ট সমস্যার সমাধান করতে পারে। তাই সাধারণ সমাধানকারীদের জন্য যারা বিভিন্ন ধরণের সমস্যা পরিচালনা করতে পারে (এবং বেশিরভাগ অ্যাপ্লিকেশনের জন্য যথেষ্ট দ্রুত), আমরা MIP এবং CP-SAT সমাধানকারীদের সুপারিশ করি।