Integer programming — পূর্ণসংখ্যা প্রোগ্রামিং

পূর্ণসংখ্যা প্রোগ্রামিং (পূসপ্র; ইং. integer programming, IP) — গাণিতিক অপ্টিমাইজেশনের একটি শাখা, যেখানে এমন সমস্যা নিয়ে গবেষণা করা হয় যেখানে কিছু বা সমস্ত চলক কেবলমাত্র পূর্ণসংখ্যার মান গ্রহণ করতে পারে।

সর্বাধিক গবেষণাকৃত বিশেষ ক্ষেত্রটি হলো পূর্ণসংখ্যা রৈখিক প্রোগ্রামিং (পূরৈপ্র; ইং. integer linear programming, ILP), যেখানে উদ্দেশ্য ফাংশন এবং সীমাবদ্ধতাগুলি রৈখিক। রৈখিক প্রোগ্রামিং থেকে ভিন্নভাবে, যেখানে চলকগুলি যেকোনো বাস্তব মান গ্রহণ করতে পারে, সেখানে পূর্ণসংখ্যার শর্ত পূসপ্র সমস্যাগুলিকে সমাধানের জন্য উল্লেখযোগ্যভাবে জটিল করে তোলে।

পূর্ণসংখ্যা প্রোগ্রামিং অর্থনীতি, লজিস্টিক্স, উৎপাদন পরিকল্পনা এবং অন্যান্য ক্ষেত্রে ব্যাপকভাবে প্রয়োগ পায়, যেখানে চলকগুলি স্বভাবতই বিচ্ছিন্ন (যেমন, উৎপাদিত পণ্যের সংখ্যা বা কর্মীর সংখ্যা)।

সংজ্ঞা ও পরিভাষা

পূর্ণসংখ্যা রৈখিক প্রোগ্রামিংয়ের সাধারণ সমস্যাটি নিম্নলিখিতভাবে লেখা যায়:

এমন একটি ভেক্টর $x$ খুঁজুন, যা:

সর্বাধিক করে (বা সর্বনিম্ন করে) $c^{T}x$

শর্তের অধীনে:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{Z}}^n$ (ভেক্টর $x$-এর সমস্ত উপাদান — পূর্ণসংখ্যা)

যেখানে $x$ — চলকের ভেক্টর, $c$ এবং $b$ — ভেক্টর, এবং $A$ — সহগের ম্যাট্রিক্স।

চলকের প্রয়োজনীয়তা অনুযায়ী নিম্নলিখিত ধরনের সমস্যা পৃথক করা হয়:

• সম্পূর্ণ পূর্ণসংখ্যা প্রোগ্রামিং: সমস্ত চলক পূর্ণসংখ্যা হতে হবে।
• মিশ্র-পূর্ণসংখ্যা প্রোগ্রামিং (ইং. mixed-integer programming, MIP): কেবলমাত্র কিছু চলক পূর্ণসংখ্যা হতে হবে।
• বুলিয়ান (0-1) প্রোগ্রামিং: চলকগুলি কেবলমাত্র 0 বা 1 মান গ্রহণ করে, যা «হ্যাঁ/না» ধরনের যৌক্তিক সিদ্ধান্ত মডেল করতে সক্ষম করে।

মূল বৈশিষ্ট্য ও জটিলতা

গণনামূলক জটিলতা

পূর্ণসংখ্যা রৈখিক প্রোগ্রামিংয়ের সমস্যাটি সাধারণ ক্ষেত্রে NP-কঠিন। এর অর্থ হলো, এমন কোনো পরিচিত অ্যালগরিদম নেই যা যেকোনো পূসপ্র সমস্যার জন্য বহুপদী সময়ে সঠিক সর্বোত্তম সমাধান খুঁজে পেতে পারে। জটিলতার কারণ হলো সমস্যার সংমিশ্রণমূলক প্রকৃতি, কারণ সম্ভাব্য পূর্ণসংখ্যা সমাধানের সংখ্যা চলকের সংখ্যা বৃদ্ধির সাথে সাথে জ্যামিতিকভাবে বাড়তে পারে।

রৈখিক প্রোগ্রামিংয়ের সাথে সম্পর্ক (রৈপ্র-শিথিলায়ন)

যেকোনো পূসপ্র সমস্যার জন্য তার রৈখিক শিথিলায়ন — একটি রৈখিক প্রোগ্রামিং (রৈপ্র) সমস্যা — তৈরি করা যায়, যেখানে চলকের পূর্ণসংখ্যার শর্ত বাদ দেওয়া হয়। রৈপ্র-শিথিলায়নের সমাধানের দুটি গুরুত্বপূর্ণ বৈশিষ্ট্য রয়েছে:

1. এটি উল্লেখযোগ্যভাবে দ্রুত (বহুপদী সময়ে) খুঁজে পাওয়া যায়।
2. রৈপ্র-শিথিলায়নের উদ্দেশ্য ফাংশনের সর্বোত্তম মান মূল পূর্ণসংখ্যা সমস্যার সর্বোত্তম মানের একটি প্রাক্কলন দেয় (সর্বাধিকীকরণ সমস্যার জন্য উপরের সীমা এবং সর্বনিম্নীকরণের জন্য নিচের সীমা)।

তবে রৈপ্র-শিথিলায়নের ভগ্নাংশ সমাধানকে নিকটতম পূর্ণসংখ্যায় সরল বৃত্তায়ন করলে সাধারণত পূর্ণসংখ্যা সমস্যার সর্বোত্তম বা এমনকি গ্রহণযোগ্য সমাধান পাওয়া যায় না।

সম্পূর্ণ ইউনিমডুলারিটির বৈশিষ্ট্য

পূরৈপ্র সমস্যার একটি গুরুত্বপূর্ণ শ্রেণি রয়েছে যেগুলি তাদের রৈপ্র-শিথিলায়নের মতোই সহজে সমাধানযোগ্য। এগুলি হলো সেসব সমস্যা যেখানে সীমাবদ্ধতার ম্যাট্রিক্স $A$ সম্পূর্ণ ইউনিমডুলার (অর্থাৎ এর যেকোনো বর্গ উপম্যাট্রিক্সের নির্ধারক 0, +1 বা −1)। যদি ম্যাট্রিক্স $A$ সম্পূর্ণ ইউনিমডুলার হয় এবং ভেক্টর $b$ পূর্ণসংখ্যা হয়, তাহলে রৈপ্র-শিথিলায়নের গ্রহণযোগ্য সমাধানের বহুভুজের সমস্ত শীর্ষবিন্দু স্বয়ংক্রিয়ভাবে পূর্ণসংখ্যা হবে। ফলস্বরূপ, সিমপ্লেক্স পদ্ধতিতে প্রাপ্ত সমাধান পূর্ণসংখ্যা হবে। এই ধরনের সমস্যার উদাহরণ হলো পরিবহন সমস্যা এবং নিয়োগ সমস্যা।

সমাধানের পদ্ধতি

সম্পূর্ণ ইউনিমডুলারিটির বৈশিষ্ট্যহীন সাধারণ পূসপ্র সমস্যার জন্য অন্তর্নিহিত গণনার ধারণার উপর ভিত্তি করে সঠিক পদ্ধতি তৈরি করা হয়েছে।

• শাখা ও সীমানা পদ্ধতি (ইং. Branch and Bound) — মূল সঠিক পদ্ধতি, যা গ্রহণযোগ্য সমাধানের সেটকে পদ্ধতিগতভাবে উপসেটে ভাগ করার (শাখায়ন) এবং যেসব উপসেট সর্বোত্তম সমাধান ধারণ করে না সেগুলি কেটে ফেলার উপর ভিত্তি করে। উপসেটের সম্ভাবনা মূল্যায়নের জন্য রৈপ্র-শিথিলায়ন ব্যবহার করা হয়।

• ছেদক তল পদ্ধতি (গমোরি পদ্ধতি; ইং. Cutting Plane Method) — একটি পুনরাবৃত্তিমূলক পদ্ধতি যা ক্রমাগত সমস্যায় নতুন রৈখিক সীমাবদ্ধতা («ছেদন») যোগ করে। এই ছেদনগুলি রৈপ্র-শিথিলায়নের ভগ্নাংশ সমাধান «কেটে ফেলে», কোনো গ্রহণযোগ্য পূর্ণসংখ্যা সমাধানকে প্রভাবিত না করে, ধীরে ধীরে রৈপ্র-শিথিলায়নের গ্রহণযোগ্য সমাধান অঞ্চলকে পূর্ণসংখ্যা সমাধানের উত্তল আবরণের কাছাকাছি নিয়ে আসে।

আধুনিক সমাধানকারীগুলি সাধারণত হাইব্রিড অ্যালগরিদম ব্যবহার করে, যেমন শাখা ও ছেদন পদ্ধতি (ইং. Branch and Cut), যা উভয় পদ্ধতির সুবিধা একত্রিত করে।

উদাহরণ ও প্রয়োগ ক্ষেত্র

পূর্ণসংখ্যা প্রোগ্রামিং সংমিশ্রণমূলক অপ্টিমাইজেশনের অনেক ক্লাসিক সমস্যা মডেল করতে সক্ষম।

• ন্যাপস্যাক সমস্যা: একটি ক্লাসিক 0-1 প্রোগ্রামিং সমস্যা, যেখানে সর্বোচ্চ মোট মূল্যমান সহ বস্তুর একটি সেট নির্বাচন করতে হয়, মোট ওজনের সীমাবদ্ধতা না ছাড়িয়ে।
• ভ্রমণকারী বিক্রয়কর্মী সমস্যা: একটি নির্দিষ্ট শহরের সেটের মধ্য দিয়ে সংক্ষিপ্ততম রুট খোঁজার সমস্যা। এটি পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা হিসেবে তৈরি করা যায়, যেখানে চলকগুলি চূড়ান্ত রুটে গ্রাফের প্রান্তগুলির অন্তর্ভুক্তির জন্য দায়ী।

এর নমনীয়তার কারণে, পূসপ্র অপারেশনস রিসার্চের অন্যতম চাহিদাসম্পন্ন হাতিয়ার এবং নিম্নলিখিত ক্ষেত্রে প্রয়োগ পায়:

• লজিস্টিক্স ও সরবরাহ শৃঙ্খল ব্যবস্থাপনা: পরিবহন রুট অপ্টিমাইজেশন, গুদাম স্থাপন, মজুদ ব্যবস্থাপনা।
• উৎপাদন পরিকল্পনা: উৎপাদন সময়সূচি তৈরি, সম্পদ বরাদ্দ, সরঞ্জাম লোডিং।
• অর্থায়ন ও অর্থনীতি: বিনিয়োগ পোর্টফোলিও গঠন, মূলধন বাজেটিং।
• টেলিযোগাযোগ ও শক্তি: যোগাযোগ নেটওয়ার্ক ডিজাইন, শক্তি ইউনিটের কাজ পরিকল্পনা।

আরও দেখুন

• রৈখিক প্রোগ্রামিং
• শাখা ও সীমানা পদ্ধতি

তথ্যসূত্র

</references>