পূর্ণসংখ্যা প্রোগ্রামিং পরীক্ষাগার
নির্ভুল শাখা-সীমা দিয়ে ছোট পূর্ণসংখ্যা লিনিয়ার প্রোগ্রাম সমাধান করুন এবং অনুসন্ধানের প্রতিটি নোড দেখুন। পুরো বৃক্ষ অনুসন্ধান হলেই সেরা বিন্দুকে প্রমাণিত সর্বোত্তম বলা হয়।
প্রোগ্রাম 4,000 অক্ষর ও 40 লাইন, 8 চলক এবং দুই বা তার বেশি চলকবিশিষ্ট 8 সীমাবদ্ধতায় সীমিত; নোড-সীমা 1 থেকে 5,000, এবং 3,000,000 নির্ভুল গাণিতিক ধাপের পরও অনুসন্ধান থামে। আপনার ডিভাইসে ব্যাকগ্রাউন্ড কর্মীতে সর্বোচ্চ 15 সেকেন্ডে গণনা হয়। JSON প্রতিবেদন ও নোডের CSV ডাউনলোড করা যায়। প্রথম লাইনে maximize বা minimize এবং উদ্দেশ্য ফাংশন লিখুন। এরপর প্রতি লাইনে একটি সীমাবদ্ধতা দিন। সর্বোচ্চ 4,000 অক্ষর। চালানোর আগে সেটিংস দেখে নিন।
আপনার ফলাফল
পূর্ণসংখ্যা প্রোগ্রামিং পরীক্ষাগার
- প্রথম লাইনে maximize 5x + 4y-এর মতো উদ্দেশ্য ফাংশন লিখুন।
- প্রতি লাইনে একটি করে সীমাবদ্ধতা যোগ করুন, যেমন x, y >= 0-এর সীমা; চাইলে integer x বা binary z-এর মতো লাইনও দিন, এবং প্রোগ্রামে থাকা চলক ব্যবহার করুন।
- নোড-সীমা নির্ধারণ করে অনুসন্ধান চালান।
- অবস্থা, বর্তমান সেরা সমাধান, সেরা সীমা ও ব্যবধান পড়ুন, তারপর JSON প্রতিবেদন বা নোডের CSV ডাউনলোড করুন।
যা জানা দরকার
প্রোগ্রাম 4,000 অক্ষর ও 40 লাইন, 8 চলক এবং দুই বা তার বেশি চলকবিশিষ্ট 8 সীমাবদ্ধতায় সীমিত; নোড-সীমা 1 থেকে 5,000, এবং 3,000,000 নির্ভুল গাণিতিক ধাপের পরও অনুসন্ধান থামে। আপনার ডিভাইসে ব্যাকগ্রাউন্ড কর্মীতে সর্বোচ্চ 15 সেকেন্ডে গণনা হয়। JSON প্রতিবেদন ও নোডের CSV ডাউনলোড করা যায়।
শাখা ও সীমা
প্রতিটি নোড সিমপ্লেক্স পদ্ধতিতে লিনিয়ার রিল্যাক্সেশন নির্ভুলভাবে সমাধান করে। ভগ্নাংশ মানের পূর্ণসংখ্যা চলকটি x <= floor এবং x >= ceiling এই দুই শাখায় ভাগ হয়। রিল্যাক্সেশন অসম্ভব হলে বা পাওয়া সেরা পূর্ণসংখ্যা বিন্দুকে হারাতে না পারলে নোড ছাঁটাই হয়। পদ্ধতি: Wolsey, Integer Programming, 2nd edition, অধ্যায় 7 (2020)।
প্রমাণিত মানে কী
প্রতিটি নোড সমাধান বা নির্ভুল সীমা দিয়ে ছাঁটাই হলে incumbent-কে সর্বোত্তম প্রমাণ করা যায়, অথবা সমস্যাটি অসম্ভব প্রমাণিত হয়। নোড-সীমা বা ধাপ-বাজেট আগে অনুসন্ধান থামালে incumbent কেবল এ পর্যন্ত পাওয়া সেরা বিন্দু; প্রতিবেদন সেরা সীমা ও তাদের ব্যবধান জানায়।
ইনপুটের নিয়ম
চলকগুলো পূর্ণসংখ্যা, যদি না কিছু চলক integer x, y দিয়ে তালিকাভুক্ত করেন; সে ক্ষেত্রে বাকিগুলো অবিচ্ছিন্ন। এক-চলক সীমাবদ্ধতা সীমায় রূপ নেয়। রিল্যাক্সেশন সীমাহীন হলে অনুসন্ধান থামে, কারণ পূর্ণসংখ্যা প্রোগ্রামটিও সীমাহীন বা অসম্ভব হতে পারে।