Graver basis
ফলিত গণিতে, গ্রেভার ঘাঁটিগুলি বহুপদী সময়ে রৈখিক এবং বিভিন্ন অরৈখিক পূর্ণসংখ্যা প্রোগ্রামিং সমস্যার পুনরাবৃত্তিমূলক সমাধান সক্ষম করে। এগুলি জ্যাক ই. গ্রেভার দ্বারা প্রবর্তিত হয়েছিল। গ্রবনার ঘাঁটির তত্ত্বের সাথে তাদের সংযোগ নিয়ে বার্নড স্টারমফেলস আলোচনা করেছিলেন। গ্রেভার ঘাঁটির অ্যালগরিদমিক তত্ত্ব এবং পূর্ণসংখ্যা প্রোগ্রামিং-এ এর প্রয়োগ শ্মুয়েল ওন দ্বারা বর্ণনা করা হয়েছে। আনুষ্ঠানিক সংজ্ঞা একটি m × n পূর্ণসংখ্যা ম্যাট্রিক্সের গ্রেভার ভিত্তি হল কখন এবং সমস্ত i দ্বারা সংজ্ঞায়িত একটি ভাল আংশিক ক্রমের অধীনে সেটের ন্যূনতম উপাদানগুলির সসীম সেট। উদাহরণস্বরূপ, গ্রেভার বেসিস ভেক্টর (2,-1,0), (0,-1,2), (1,0,-1), (1,-1,1) এবং তাদের নেতিবাচকতা নিয়ে গঠিত। গ্রেভার বেস ব্যবহার করে পূর্ণসংখ্যা প্রোগ্রামিং সমাধান করা পূর্ণসংখ্যা প্রোগ্রামিং হল রৈখিক বৈষম্যের একটি সিস্টেমকে সন্তুষ্ট করে পূর্ণসংখ্যা পয়েন্টের সেটের উপর একটি রৈখিক বা অরৈখিক উদ্দেশ্যমূলক ফাংশনকে অনুকূল করার সমস্যা। আনুষ্ঠানিকভাবে, এটি নিম্নরূপ মানক আকারে লেখা যেতে পারেঃ এটি সবচেয়ে মৌলিক বিচ্ছিন্ন অপ্টিমাইজেশান সমস্যাগুলির মধ্যে একটি এবং এর একটি খুব বিস্তৃত মডেলিং শক্তি এবং বিভিন্ন ক্ষেত্রে অসংখ্য প্রয়োগ রয়েছে, তবে সাধারণত নীচে উল্লিখিত হিসাবে গণনামূলকভাবে খুব কঠিন। যাইহোক, গ্রেভার ভিত্তির পরিপ্রেক্ষিতে, রৈখিক এবং বিভিন্ন অরৈখিক উদ্দেশ্যমূলক ফাংশনের সমস্যাটি বহুপদী সময়ে সমাধান করা যেতে পারে যেমনটি পরে ব্যাখ্যা করা হয়েছে। রৈখিক পূর্ণসংখ্যা প্রোগ্রামিং সবচেয়ে বেশি অধ্যয়নরত ক্ষেত্রে, যা পুঙ্খানুপুঙ্খভাবে বিবেচনা করা হয়, তা হল রৈখিক পূর্ণসংখ্যা প্রোগ্রামিং, এটি ধরে নেওয়া যেতে পারে যে সমস্ত চলকগুলি নীচে এবং উপরে থেকে সীমাবদ্ধঃ এই ধরনের সীমা হয় হাতে থাকা প্রয়োগে স্বাভাবিকভাবে উপস্থিত হয়, অথবা কোনও সর্বোত্তম সমাধান না হারিয়ে প্রয়োগ করা যেতে পারে। কিন্তু, এমনকি রৈখিক উদ্দেশ্যমূলক ফাংশনের ক্ষেত্রেও সমস্যাটি এনপি-হার্ড এবং তাই সম্ভবত বহুপদী সময়ে সমাধান করা যায় না। যাইহোক, এর গ্রেভার ভিত্তির নিম্নলিখিত বৈশিষ্ট্য রয়েছে। প্রতিটি সম্ভাব্য বিন্দুর জন্য x: হয় x সর্বোত্তম (অর্থাৎ, সীমাবদ্ধতাগুলি ন্যূনতম করে); অথবা একটি ভেক্টর g রয়েছে, যাতে x + g সম্ভব এবং (অর্থাৎ, x এর সাথে গ্রেভার ভিত্তির একটি উপাদান যোগ করে উন্নত করা যেতে পারে)। অতএব, গ্রেভার ভিত্তিতে, আইএলপি নিম্নলিখিত সহজ পুনরাবৃত্তিমূলক অ্যালগরিদম ব্যবহার করে বহুপদী সময়ে সমাধান করা যেতে পারে। প্রথমে ধরে নিন যে কিছু প্রাথমিক সম্ভাব্য বিন্দু x দেওয়া আছে। যদিও সম্ভব, নিম্নলিখিত পুনরাবৃত্তিটি পুনরাবৃত্তি করুনঃ ধনাত্মক পূর্ণসংখ্যা q এবং উপাদান g এমনভাবে খুঁজে বের করুন যাতে x + qg সীমা লঙ্ঘন না করে এবং সর্বোত্তম সম্ভাব্য উন্নতি দেয়; x: = x + qg আপডেট করুন এবং পরবর্তী পুনরাবৃত্তিতে এগিয়ে যান। শেষ বিন্দু x সর্বোত্তম এবং পুনরাবৃত্তির সংখ্যা বহুপদী। একটি প্রাথমিক সম্ভাব্য পয়েন্ট খুঁজে বের করার জন্য, একটি উপযুক্ত সহায়ক প্রোগ্রাম সেট আপ করা যেতে পারে এবং একইভাবে সমাধান করা যেতে পারে। নন-লিনিয়ার ইন্টিজার প্রোগ্রামিং সাধারণ উদ্দেশ্যমূলক ফাংশন f-এর ক্ষেত্রে, যদি ভেরিয়েবলগুলি সীমাহীন হয় তবে সমস্যাটি প্রকৃতপক্ষে অসম্পূর্ণ হতে পারেঃ এটি হিলবার্টের 10ম সমস্যার সমাধান থেকে অনুসরণ করে (দেখুন), যে কোনও অ্যালগরিদম বিদ্যমান নেই, যা 58টি ভেরিয়েবলে 8 ডিগ্রির একটি পূর্ণসংখ্যা বহুপদী f দেওয়া হয়েছে, সিদ্ধান্ত নেয় যে সমস্ত 58-মাত্রিক পূর্ণসংখ্যা ভেক্টরের উপর f-এর ন্যূনতম মান 0 কিনা। যাইহোক, যখন চলকগুলি সীমাবদ্ধ থাকে, তখন বেশ কয়েকটি অরৈখিক উদ্দেশ্যমূলক ফাংশনের জন্য বহুপদী সময়ে গ্রেভার ভিত্তি ব্যবহার করে সমস্যাটি সমাধান করা যেতে পারে যার মধ্যে রয়েছেঃ ফর্মের পৃথকীকৃত-উত্তল ফাংশন; বিশেষত প্রতিটি ধনাত্মক পূর্ণসংখ্যা p-এর জন্য p-আদর্শ; যৌগিক-গুহা ফাংশন f (x) = g (Wx), যেখানে W হল একটি d × n স্থির পূর্ণসংখ্যা ম্যাট্রিক্স, এবং যেখানে g একটি d-বৈকল্পিক অবতল ফাংশন; নির্দিষ্ট (in)-নির্দিষ্ট চতুর্ভুজ এবং উচ্চতর ডিগ্রি বহুপদী ফাংশন। কিছু অ্যাপ্লিকেশন বহুমাত্রিক সারণি নিম্নোক্ত অপ্টিমাইজেশান সমস্যাটি বিবেচনা করুন ত্রিমাত্রিক সারণিতে নির্ধারিত সারির যোগফল সহ, অ-ঋণাত্মক পূর্ণসংখ্যা সহ (যার সর্বাধিক মান পরোক্ষভাবে উপরের সমস্ত চলককে সীমাবদ্ধ করে)। এই পদ্ধতির সংজ্ঞায়িত ম্যাট্রিক্সকে (lm + ln + mn) × (lmn) দ্বারা চিহ্নিত করুন। মনে রাখবেন যে এই ম্যাট্রিক্সটি সাধারণত সম্পূর্ণরূপে একমুখী নয়। যাইহোক, এটি দেখানো হয়েছিল যে প্রতিটি স্থির l এবং m-এর জন্য, তার গ্রেভার ভিত্তি গণনা করা যেতে পারে সময় যা n-এ বহুপদী। উপরে উল্লিখিত ফলাফলগুলি স্থির l এবং m এবং পরিবর্তনশীল n-এর জন্য বহুপদী সময়ে এই সমস্যাটি সমাধান করার অনুমতি দেয়। লক্ষ্য করুন যে যদি টেবিলের শুধুমাত্র একটি দিক l স্থির থাকে (এমনকি l = 3 সহ) যখন m এবং n উভয়ই পরিবর্তনশীল হয়, তবে সমস্যাটি NP শক্ত, যেমন দেখানো হয়েছে। আরও সাধারণভাবে, উচ্চ-মাত্রিক টেবিলের সমস্যাগুলির জন্য অনুরূপ ইতিবাচক ফলাফল থাকে (প্রবর্তিত): প্রতিটি নির্দিষ্ট ডি এবং, (অ)-পরিবর্তনশীল এন এবং নির্ধারিত মার্জিন সহ টেবিলের উপর-রৈখিক অপ্টিমাইজেশন বহুপদী সময়ে করা যেতে পারে। পরিসংখ্যানগত ডাটাবেসে নিরাপত্তা সমস্যা এবং গোপনীয়তা প্রবেশের জন্য এর আরও প্রয়োগ রয়েছে। মাল্টি-কমোডিটি প্রবাহ সরবরাহ, খরচ এবং ক্ষমতার সীমাবদ্ধতা সাপেক্ষে m সরবরাহকারীদের থেকে n ভোক্তাদের কাছে k ধরনের পূর্ণসংখ্যা পণ্যের পূর্ণসংখ্যা মাল্টি-কমোডিটি প্রবাহের সমস্যা বিবেচনা করুন, যাতে বৃত্তের উপর রৈখিক বা যানজট-নির্ভর উত্তল ব্যয়ের সমষ্টি হ্রাস করা যায়। তারপর প্রতিটি স্থির k এবং m-এর জন্য, সংজ্ঞায়িত ব্যবস্থার গ্রেভার ভিত্তি গণনা করা যেতে পারে এবং ফলস্বরূপ বিভাজক-উত্তল উদ্দেশ্যমূলক ফাংশনটি সময়ের সাথে হ্রাস করা যেতে পারে যা ভোক্তাদের পরিবর্তনশীল সংখ্যা n-এ এবং বাকি ডেটাতে বহুপদী। অন্যান্য প্রয়োগ গ্রেভার ভিত্তির অ্যালগরিদমিক তত্ত্বের অনেক প্রয়োগের মধ্যে রয়েছেঃ স্টোকাস্টিক ইন্টিজার প্রোগ্রামিং, এন-ফোল্ড ইন্টিজার প্রোগ্রামিং, এন-ফোল্ড 4-ব্লক ডিকম্পোসেবল ইন্টিজার প্রোগ্রামিং, ক্লাস্টারিং, পরিসংখ্যানগত ডাটাবেসে প্রকাশ নিয়ন্ত্রণ এবং অবিভাজ্য বস্তুর ন্যায্য বরাদ্দ। এই প্রয়োগগুলির মধ্যে কিছুতে প্রাসঙ্গিক গ্রেভার ভিত্তি বহুপদী সময়ে গণনা করা যায় না, তবে একটি পরোক্ষ উপায়ে অ্যাক্সেস করা যেতে পারে যা এটি বহুপদী সময়ে ব্যবহার করার অনুমতি দেয়। সর্বজনীনতা এবং পরামিতি এটি দেখানো হয়েছিল যে প্রতিটি (সীমাবদ্ধ) পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা কিছু m এবং n এবং কিছু লাইনের যোগফলের জন্য উপরে আলোচিত 3 × m × n টেবিল সমস্যার সাথে সুনির্দিষ্টভাবে সমতুল্য। সুতরাং, এই ধরনের 3 × m × n টেবিলের সমস্যাগুলি পূর্ণসংখ্যা প্রোগ্রামিংয়ের জন্য সর্বজনীন। উপরন্তু, প্রতিটি নির্দিষ্ট m-এর জন্য, পূর্ণসংখ্যা প্রোগ্রামের ফলস্বরূপ শ্রেণীটি উপরে বর্ণিত পুনরাবৃত্তিমূলক গ্রেভার ভিত্তি পদ্ধতি দ্বারা বহুপদী সময়ে সমাধান করা যেতে পারে। সুতরাং টেবিলের প্রস্থ m সমস্ত পূর্ণসংখ্যা প্রোগ্রামিং সমস্যার একটি পরামিতি প্রদান করে। পূর্ণসংখ্যা প্রোগ্রামিংয়ের জন্য আনুমানিক শ্রেণিবিন্যাস উপরে আলোচিত সার্বজনীন 3 × m × n টেবিল সমস্যাকে সংজ্ঞায়িত করে ম্যাট্রিক্সের গ্রেভার ভিত্তি দ্বারা নির্দেশ করে। এর উপাদানগুলি হল 3 × মি × এন টেবিল যার সমস্ত লাইনের যোগফল 0 এর সমান। এই ধরনের টেবিলের ধরন হল এর অ-শূন্য 3 × মি স্তরগুলির সংখ্যা। দেখা যাচ্ছে যে একটি সীমাবদ্ধ গ্রেভার জটিলতা ফাংশন g (m) রয়েছে যাতে যে কোনও n-এর জন্য, গ্রেভার ভিত্তির যে কোনও উপাদানের প্রকার সর্বাধিক g (m) হয়। এটি অনুসরণ করে যে গ্রেভার ভিত্তি হল গ্রেভার ভিত্তির উপযুক্তভাবে এম্বেড করা অনুলিপিগুলির মিলন। কার্যত একটি নির্বিচারে পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা প্রায় সমাধান করার জন্য, নিম্নরূপ এগিয়ে যান। উপরে উল্লিখিত সর্বজনীনতা দ্বারা সক্ষম হিসাবে প্রথমে এটি একটি উপযুক্ত 3 × মি × এন টেবিল সমস্যায় এম্বেড করুন। এখন আনুমানিকতার নিম্নলিখিত শ্রেণিবিন্যাস প্রয়োগ করুন। এই শ্রেণিবিন্যাসের কে স্তরে, সর্বাধিক কে-তে কেবল সেই ধরনের উপাদানগুলির সমন্বয়ে গঠিত উপসেট হতে দিন; 3 × এম × এন টেবিলের সমস্যায় এম্বেড করা পূর্ণসংখ্যা প্রোগ্রামিং সমস্যার জন্য যতটা সম্ভব সম্ভাব্য বিন্দু পেতে যতক্ষণ সম্ভব পুনরাবৃত্তিমূলক অ্যালগরিদমে এই আনুমানিক ব্যবহার করুন; যদি এই বিন্দুর উদ্দেশ্যমূলক ফাংশন মান সন্তোষজনক হয় (ধরুন, রৈখিক প্রোগ্রামিং শিথিলকরণের মানের তুলনায়), তবে এই বিন্দুটি ব্যবহার করুন; অন্যথায় কে বৃদ্ধি করুন এবং শ্রেণিবিন্যাসের পরবর্তী স্তরে এগিয়ে যান। এটি দেখানো যেতে পারে যে যে কোনও নির্দিষ্ট স্তর k-এর জন্য, গ্রেভার ভিত্তির আনুমানিক বহুপদী কার্ডিনালিটি রয়েছে এবং সেই সময়ের মধ্যে গণনা করা যেতে পারে। স্থির প্যারামিটার ট্র্যাক্টেবিলিটিঃ বহুপদী থেকে ঘন সময় জটিলতা উপরে আলোচিত কিছু অ্যাপ্লিকেশন সমাধানের সময় জটিলতা, যেমন বহুমাত্রিক টেবিল সমস্যা, বহুমাত্রিক প্রবাহ সমস্যা এবং এন-ভাঁজ পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা, প্রাসঙ্গিক গ্রেভার ভিত্তির কার্ডিনালিটি দ্বারা প্রভাবিত হয়, যা সাধারণত বড় ডিগ্রি জি সহ একটি বহুপদী যা সিস্টেমের একটি উপযুক্ত গ্রেভার জটিলতা। আরও দ্রুততর অ্যালগরিদম উপস্থাপন করা হয়, যা প্রতিটি পুনরাবৃত্তিতে সিস্টেম নির্বিশেষে ঘন সময়ে স্পষ্টভাবে গ্রেভার ভিত্তি তৈরি না করে q ধনাত্মক পূর্ণসংখ্যা এবং g উপাদান সহ x + qg সেরা উন্নতি খুঁজে পায়। প্যারামিটারাইজড জটিলতার পরিভাষায়, এটি বোঝায় যে এই সমস্ত সমস্যা উপযুক্তভাবে প্যারামিটারাইজড এবং বিশেষত l × m × n টেবিলের সমস্যাগুলি l এবং m দ্বারা প্যারামিটারাইজড, স্থির প্যারামিটার ট্র্যাক্টেবল। আরও দেখুন গর্ডানের লেম্মা-পূর্ণসংখ্যা ম্যাট্রিক্সের শূন্য সেটের সাথে সম্পর্কিত আরেকটি সরঞ্জাম। তথ্যসূত্র রৈখিক প্রোগ্রামিং