Graver basis
اطلاقی ریاضی میں، گریور بیس کثیر الجہتی وقت میں لکیری اور مختلف غیر لکیری انٹیجر پروگرامنگ کے مسائل کے تکراری حل کو قابل بناتے ہیں۔ انہیں جیک ای گریور نے متعارف کرایا تھا۔ گربنر اڈوں کے نظریہ سے ان کے تعلق پر برنڈ سٹرم فیلس نے تبادلہ خیال کیا۔ گریور بیسز کا الگورتھمک تھیوری اور انٹیجر پروگرامنگ پر اس کے اطلاق کو سموئیل اون نے بیان کیا ہے۔ رسمی تعریف m × n انٹیجر میٹرکس کی گریور بیس سیٹ میں کم سے کم عناصر کا محدود مجموعہ ہے جس کی وضاحت کب اور تمام i کے لیے کی گئی ہے۔ مثال کے طور پر، کی گریور بیس ویکٹر (2، −1,0)، (0، −1,2)، (1,0، −1)، (1، −1,1) اور ان کے منفی پہلوؤں پر مشتمل ہے۔ گریور بیسز انٹیجر پروگرامنگ کا استعمال کرتے ہوئے انٹیجر پروگرامنگ کو حل کرنا انٹیجر پوائنٹس کے سیٹ پر لکیری یا غیر لکیری معروضی فنکشن کو بہتر بنانے کا مسئلہ ہے جو لکیری عدم مساوات کے نظام کو مطمئن کرتا ہے۔ رسمی طور پر، اسے معیاری شکل میں درج ذیل لکھا جا سکتا ہے: یہ سب سے بنیادی مجرد اصلاح کے مسائل میں سے ایک ہے اور اس میں بہت وسیع ماڈلنگ کی طاقت اور مختلف شعبوں میں متعدد ایپلی کیشنز ہیں، لیکن عام طور پر کمپیوٹیشنل طور پر بہت مشکل ہے جیسا کہ ذیل میں بتایا گیا ہے۔ تاہم، کی گریور بنیاد کو دیکھتے ہوئے، لکیری اور مختلف غیر لکیری معروضی افعال کے ساتھ مسئلہ کو کثیر الجہتی وقت میں حل کیا جا سکتا ہے جیسا کہ آگے بیان کیا گیا ہے۔ لکیری انٹیجر پروگرامنگ سب سے زیادہ مطالعہ شدہ کیس، جس میں اچھی طرح سے علاج کیا جاتا ہے، لکیری انٹیجر پروگرامنگ کا ہے، یہ فرض کیا جا سکتا ہے کہ تمام متغیرات نیچے اور اوپر سے پابند ہیں: اس طرح کی حدود یا تو قدرتی طور پر ہاتھ میں موجود ایپلی کیشن میں ظاہر ہوتی ہیں، یا کسی بھی بہترین حل کو کھونے کے بغیر نافذ کی جا سکتی ہیں۔ لیکن، یہاں تک کہ لکیری آبجیکٹیو فنکشنز کے ساتھ بھی مسئلہ NP-سخت ہے اور اس لیے ممکنہ طور پر کثیر الجہتی وقت میں حل نہیں کیا جا سکتا۔ تاہم، کی قبر کی بنیاد میں درج ذیل خصوصیات ہیں۔ ہر قابل عمل نقطہ 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 عدد میٹرکس ہے جس میں d فکسڈ ہے، اور جہاں 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-بلاک ڈکپوز ایبل انٹیجر پروگرامنگ، کلسٹرنگ، شماریاتی ڈیٹا بیس میں انکشاف کنٹرول، اور ناقابل تقسیم اشیاء کی منصفانہ تقسیم۔ ان میں سے کچھ ایپلی کیشنز میں متعلقہ گریور کی بنیاد کو کثیر الجہتی وقت میں شمار نہیں کیا جا سکتا، لیکن اس تک بالواسطہ طریقے سے رسائی حاصل کی جا سکتی ہے جو اسے کثیر الجہتی وقت میں استعمال کرنے کی اجازت دیتی ہے۔ عالمگیریت اور پیرامیٹریزیشن اس میں دکھایا گیا تھا کہ ہر (باؤنڈڈ) انٹیجر پروگرامنگ کا مسئلہ بالکل 3 × m × n ٹیبل کے مسئلے کے مساوی ہے جس پر کچھ m اور n اور کچھ لائن جملوں کے لیے اوپر بحث کی گئی ہے۔ اس طرح، انٹیجر پروگرامنگ کے لیے اس طرح کے 3 × m × n ٹیبل کے مسائل عالمگیر ہیں۔ مزید برآں، ہر فکسڈ m کے لیے، انٹیجر پروگراموں کی نتیجے میں آنے والی کلاس کو کثیر الجہتی وقت میں اوپر بیان کردہ تکراری گریور بیس طریقہ کار کے ذریعے حل کیا جا سکتا ہے۔ لہذا ٹیبل کی چوڑائی m تمام انٹیجر پروگرامنگ کے مسائل کا پیرامیٹریزیشن فراہم کرتا ہے۔ انٹیجر پروگرامنگ کے لیے تخمینوں کی درجہ بندی میٹرکس کی گریور بنیاد سے ظاہر ہوتی ہے جو اوپر زیر بحث یونیورسل 3 × m × n ٹیبل کے مسئلے کی وضاحت کرتی ہے۔ کے عناصر 3 × m × n ٹیبلز ہیں جن میں تمام لائن کے مجموعے 0 کے برابر ہیں۔ اس طرح کی میز کی قسم اس کی غیر صفر 3 × میٹر تہوں کی تعداد ہے۔ یہ پتہ چلتا ہے کہ ایک محدود گریور پیچیدگی فنکشن g (m) ایسی ہے کہ کسی بھی n کے لیے، گریور کی بنیاد کے کسی بھی عنصر کی قسم زیادہ سے زیادہ g (m) ہوتی ہے۔ اس کے بعد یہ ہے کہ قبر کی بنیاد قبر کی بنیاد کی مناسب طور پر سرایت شدہ نقلوں کا اتحاد ہے۔ عملی طور پر ایک صوابدیدی انٹیجر پروگرامنگ کے مسئلے کو تقریبا حل کرنے کے لیے، مندرجہ ذیل طریقے سے آگے بڑھیں۔ پہلے اسے ایک مناسب 3 × m × n ٹیبل کے مسئلے میں شامل کریں جیسا کہ اوپر بیان کردہ عالمگیریت کے ذریعہ فعال کیا گیا ہے۔ اب کے تخمینوں کے درج ذیل درجہ بندی کو لاگو کریں۔ اس درجہ بندی کی سطح k پر، زیادہ سے زیادہ k پر صرف ان عناصر پر مشتمل ہونے کا ذیلی سیٹ ہونے دیں۔ 3 × m × n ٹیبل کے مسئلے میں سرایت شدہ انٹیجر پروگرامنگ کے مسئلے کے لیے زیادہ سے زیادہ ممکن نقطہ حاصل کرنے کے لیے اس تخمینے کو تکراری الگورتھم میں استعمال کریں۔ اگر اس نقطہ کی معروضی فنکشن ویلیو تسلی بخش ہے (جیسے کہ لکیری پروگرامنگ میں نرمی کی قیمت کے مقابلے میں)، تو اس نقطہ کا استعمال کریں ؛ بصورت دیگر k میں اضافہ کریں اور درجہ بندی کی اگلی سطح پر آگے بڑھیں۔ یہ دکھایا جا سکتا ہے کہ کسی بھی مقررہ سطح k کے لیے، گریور بیس کے تخمینے میں کثیر الجہتی کارڈینیلیٹی ہوتی ہے اور اس وقت میں اس کا حساب لگایا جا سکتا ہے۔ فکسڈ پیرامیٹر ٹریکٹیبلٹی: کثیر الجہتی سے کیوبک ٹائم پیچیدگی اوپر زیر بحث کچھ ایپلی کیشنز کو حل کرنے کی وقت کی پیچیدگی، جیسے کہ کثیر جہتی ٹیبل کے مسائل، کثیر الجہتی بہاؤ کے مسائل، اور این-فولڈ انٹیجر پروگرامنگ کے مسائل، متعلقہ گریور بیس کی بنیادی حیثیت کا غلبہ ہے، جو عام طور پر بڑی ڈگری جی کے ساتھ ایک کثیر الجہتی ہے جو نظام کی ایک مناسب گریور پیچیدگی ہے۔ بہت تیز الگورتھم میں پیش کیا جاتا ہے، جو نظام سے قطع نظر کیوبک ٹائم میں، واضح طور پر گریور بیس کی تعمیر کے بغیر ہر تکرار پر q مثبت عدد اور g عنصر کے ساتھ x + qg میں بہترین بہتری تلاش کرتا ہے۔ پیرامیٹرائزڈ پیچیدگی کی اصطلاحات میں، اس کا مطلب یہ ہے کہ یہ تمام مسائل مناسب طور پر پیرامیٹرائزڈ ہیں، اور خاص طور پر l × m × n ٹیبل کے مسائل جو l اور m کے ذریعہ پیرامیٹرائزڈ ہیں، فکسڈ پیرامیٹر ٹریکٹیبل ہیں۔ گورڈن کا لیما بھی دیکھیں-ایک اور ٹول جو عدد میٹرکس کے صفر سیٹوں سے متعلق ہے۔ حوالہ جات لکیری پروگرامنگ