সীমাবদ্ধতা অপ্টিমাইজেশান , বা সীমাবদ্ধতা প্রোগ্রামিং (CP), প্রার্থীদের একটি খুব বড় সেটের মধ্যে সম্ভাব্য সমাধানগুলি চিহ্নিত করার জন্য দেওয়া নাম, যেখানে সমস্যাটিকে নির্বিচারে সীমাবদ্ধতার পরিপ্রেক্ষিতে মডেল করা যেতে পারে। অনেক বৈজ্ঞানিক এবং প্রকৌশল শাখায় CP সমস্যা দেখা দেয়। ("প্রোগ্রামিং" শব্দটি কিছুটা ভুল নাম, যেমন "কম্পিউটার" এর অর্থ "একজন ব্যক্তি যিনি গণনা করেন।" এখানে, "প্রোগ্রামিং" একটি কম্পিউটার ভাষায় প্রোগ্রামিং না করে একটি পরিকল্পনার বিন্যাসকে বোঝায়।)
CP অপ্টিমাইজেশন (একটি সর্বোত্তম সমাধান খোঁজার) পরিবর্তে সম্ভাব্যতার উপর ভিত্তি করে (একটি সম্ভাব্য সমাধান খোঁজা) এবং উদ্দেশ্যমূলক ফাংশনের পরিবর্তে সীমাবদ্ধতা এবং ভেরিয়েবলের উপর ফোকাস করে। প্রকৃতপক্ষে, একটি CP সমস্যার একটি উদ্দেশ্যমূলক ফাংশনও নাও থাকতে পারে — লক্ষ্য হতে পারে সমস্যাটিতে সীমাবদ্ধতা যুক্ত করে একটি আরও পরিচালনাযোগ্য উপসেটের সম্ভাব্য সমাধানগুলির একটি খুব বড় সেটকে সংকুচিত করা।
CP-এর জন্য উপযুক্ত একটি সমস্যার উদাহরণ হল কর্মচারী শিডিউলিং । সমস্যা দেখা দেয় যখন কোম্পানিগুলি যেগুলি ক্রমাগত কাজ করে — যেমন কারখানাগুলি — তাদের কর্মীদের জন্য সাপ্তাহিক সময়সূচী তৈরি করতে হবে। এখানে একটি খুব সরলীকৃত উদাহরণ: একটি কোম্পানি প্রতিদিন তিনটি 8-ঘন্টা শিফট চালায় এবং তার চারটি কর্মচারীর মধ্যে তিনজনকে প্রতিদিন বিভিন্ন শিফটে নিয়োগ দেয়, যখন চতুর্থ দিন ছুটি দেয়। এমনকি এত ছোট ক্ষেত্রে, সম্ভাব্য সময়সূচীর সংখ্যা বিশাল: প্রতিদিন, সেখানে 4! = 4 * 3 * 2 * 1 = 24 সম্ভাব্য কর্মচারী নিয়োগ, তাই সম্ভাব্য সাপ্তাহিক সময়সূচীর সংখ্যা 24 7 , যা 4.5 বিলিয়নের বেশি। সাধারণত অন্যান্য সীমাবদ্ধতা থাকবে যা সম্ভাব্য সমাধানের সংখ্যা কমিয়ে দেয় - উদাহরণস্বরূপ, প্রতিটি কর্মচারী প্রতি সপ্তাহে কমপক্ষে একটি ন্যূনতম সংখ্যক দিন কাজ করে। আপনি যখন নতুন সীমাবদ্ধতা যুক্ত করেন তখন CP পদ্ধতিটি ট্র্যাক রাখে কোন সমাধানগুলি সম্ভাব্য থাকে, যা এটিকে বড়, বাস্তব-বিশ্বের সময়সূচী সমস্যা সমাধানের জন্য একটি শক্তিশালী হাতিয়ার করে তোলে।
সারা বিশ্বে CP-এর একটি বিস্তৃত এবং অত্যন্ত সক্রিয় সম্প্রদায় রয়েছে যেখানে ডেডিকেটেড বৈজ্ঞানিক জার্নাল, সম্মেলন এবং বিভিন্ন সমাধানের কৌশল রয়েছে। ভিন্নধর্মী সীমাবদ্ধতা সহ পরিকল্পনা, সময়সূচী এবং অন্যান্য অসংখ্য ডোমেনে সিপি সফলভাবে প্রয়োগ করা হয়েছে।
টুলস
গুগল সিপি সমস্যা সমাধানের কয়েকটি উপায় প্রদান করে:
- CP-SAT সমাধানকারী : একটি সীমাবদ্ধতা প্রোগ্রামিং সমাধানকারী যা SAT (সন্তুষ্টিযোগ্যতা) পদ্ধতি ব্যবহার করে।
- অরিজিনাল সিপি সলভার : রাউটিং লাইব্রেরিতে ব্যবহৃত একটি সীমাবদ্ধতা প্রোগ্রামিং সমাধানকারী।
যদি আপনার সমস্যাটি একটি রৈখিক উদ্দেশ্য এবং রৈখিক সীমাবদ্ধতার সাথে মডেল করা যায়, তবে আপনার একটি রৈখিক প্রোগ্রামিং সমস্যা রয়েছে এবং MPSolver বিবেচনা করা উচিত। (তবে, রাউটিং সমস্যাগুলি সাধারণত আমাদের গাড়ির রাউটিং লাইব্রেরির সাথে সবচেয়ে ভাল সমাধান করা হয় যদিও সেগুলি একটি লিনিয়ার মডেলের সাথে উপস্থাপন করা যেতে পারে।)
উদাহরণ
পরবর্তী বিভাগে CP-SAT সমাধানকারী, সীমাবদ্ধতা প্রোগ্রামিংয়ের জন্য প্রাথমিক OR-Tools সলভার বর্ণনা করা হয়েছে। (SAT মানে সন্তুষ্টির জন্য: সমাধানকারী CP পদ্ধতির সাথে SAT সমস্যা সমাধানের কৌশল ব্যবহার করে।)
CP-SAT সমাধানকারীর জন্য উপযুক্ত সময়সূচী সমস্যার কিছু উদাহরণ এখানে দেওয়া হল:
দুটি ক্লাসিক CP সমস্যা হল এন-কুইন্স সমস্যা এবং ক্রিপ্টারিদমেটিক পাজল ।