• পূর্ণসংখ্যা অপ্টিমাইজেশান

রৈখিক অপ্টিমাইজেশান সমস্যা যেগুলির জন্য কিছু ভেরিয়েবলকে পূর্ণসংখ্যার প্রয়োজন হয় সেগুলিকে মিশ্র পূর্ণসংখ্যা প্রোগ্রাম (MIPs) বলা হয়।

এই ভেরিয়েবলগুলি কয়েকটি উপায়ে উঠতে পারে:

  • পূর্ণসংখ্যার ভেরিয়েবল যেগুলি আইটেমের সংখ্যার প্রতিনিধিত্ব করে, যেমন গাড়ি বা টেলিভিশন সেট, এবং সমস্যাটি হল লাভের সর্বাধিক করার জন্য প্রতিটি আইটেমের কতগুলি তৈরি করতে হবে তা নির্ধারণ করা।
    সাধারণত, এই ধরনের সমস্যাগুলি স্ট্যান্ডার্ড রৈখিক অপ্টিমাইজেশন সমস্যা হিসাবে সেট আপ করা যেতে পারে, অতিরিক্ত প্রয়োজনীয়তা সহ যে ভেরিয়েবলগুলি অবশ্যই পূর্ণসংখ্যা হতে হবে। পরবর্তী বিভাগে এই ধরনের সমস্যার একটি উদাহরণ দেখায়।

  • বুলিয়ান ভেরিয়েবল যা 0-1 মানের সাথে সিদ্ধান্তের প্রতিনিধিত্ব করে।
    একটি উদাহরণ হিসাবে, একটি সমস্যা বিবেচনা করুন যার মধ্যে কর্মীদের কাজ অর্পণ করা জড়িত (দেখুন অ্যাসাইনমেন্ট )। এই ধরনের সমস্যা সেট আপ করতে, আপনি বুলিয়ান ভেরিয়েবল x i,j সংজ্ঞায়িত করতে পারেন যা 1 এর সমান যদি কর্মী i টাস্ক j এর জন্য নিযুক্ত করা হয় এবং অন্যথায় 0।

পূর্ণসংখ্যা অপ্টিমাইজেশানে একটি ভাল প্রাইমারের জন্য, আমরা মোসেক মডেলিং কুকবুক সুপারিশ করি৷

টুলস

Google MIP সমস্যা সমাধানের কয়েকটি উপায় প্রদান করে:

  • MPSolver : বেশ কয়েকটি তৃতীয় পক্ষের MIP সমাধানকারীর জন্য একটি মোড়ক, যা স্ট্যান্ডার্ড শাখা-এবং-বাউন্ড কৌশল ব্যবহার করে।
  • CP-SAT সমাধানকারী : একটি সীমাবদ্ধতা প্রোগ্রামিং সমাধানকারী যা SAT (সন্তুষ্টিযোগ্যতা) পদ্ধতি ব্যবহার করে।
  • আসল সিপি সলভার : একটি সীমাবদ্ধতা প্রোগ্রামিং সমাধানকারী।

আমি কোন সমাধানকারী ব্যবহার করা উচিত?

এমআইপি সল্ভার বা সিপি-স্যাট সলভার ব্যবহার করবেন কিনা তা সিদ্ধান্ত নেওয়ার জন্য কোনও লৌহঘটিত নিয়ম নেই। একটি মোটামুটি গাইড হিসাবে:

  • এমআইপি সলভারগুলি এমন সমস্যার জন্য আরও উপযুক্ত যা একটি স্ট্যান্ডার্ড LP হিসাবে সেট আপ করা যেতে পারে, তবে উপরের প্রথম উদাহরণের মতো নির্বিচারে পূর্ণসংখ্যা ভেরিয়েবল সহ।
  • CP-SAT সমাধানকারী সমস্যাগুলির জন্য আরও উপযুক্ত যেখানে বেশিরভাগ ভেরিয়েবল বুলিয়ান, উপরের দ্বিতীয় উদাহরণের মতো।

পূর্ণসংখ্যা এবং বুলিয়ান ভেরিয়েবল উভয়ই আছে এমন সাধারণ MIP-গুলির জন্য, দুটি সমাধানকারীর মধ্যে গতির মধ্যে প্রায়শই কোনও স্পষ্ট পার্থক্য থাকে না, তাই আপনার পছন্দ ব্যক্তিগত পছন্দে নেমে আসতে পারে।

MIP এবং CP-SAT সমাধানকারী উভয়ই ব্যবহার করে এমন উদাহরণগুলির জন্য, একটি অ্যাসাইনমেন্ট সমস্যা সমাধান করা এবং অন্যান্য অ্যাসাইনমেন্ট বিভাগগুলি দেখুন।

পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা সমাধানের আরেকটি উপায় হল নেটওয়ার্ক ফ্লো সল্ভার ব্যবহার করা।
একটি উদাহরণের জন্য একটি ন্যূনতম খরচ প্রবাহ সমস্যা হিসাবে অ্যাসাইনমেন্ট দেখুন।
একটি নেটওয়ার্ক ফ্লো হিসাবে সেট আপ করা যেতে পারে এমন একটি সমস্যার জন্য, ন্যূনতম খরচ প্রবাহ সমাধানকারী MIP বা CP-SAT সমাধানকারীর চেয়ে দ্রুত হতে পারে। যাইহোক, সব MIP এভাবে সেট আপ করা যায় না।