LP-type problem
الگورتھم کے مطالعہ میں، ایل پی قسم کا مسئلہ (جسے عمومی لکیری پروگرام بھی کہا جاتا ہے) ایک اصلاح کا مسئلہ ہے جو کم جہتی لکیری پروگراموں کے ساتھ کچھ خصوصیات کا اشتراک کرتا ہے اور جسے اسی طرح کے الگورتھم کے ذریعے حل کیا جا سکتا ہے۔ ایل پی قسم کے مسائل میں بہت سے اہم اصلاح کے مسائل شامل ہیں جو خود لکیری پروگرام نہیں ہیں، جیسے کہ پلانر پوائنٹس کے دیئے گئے سیٹ پر مشتمل سب سے چھوٹے دائرے کو تلاش کرنے کا مسئلہ۔ انہیں بے ترتیب الگورتھم کے امتزاج کے ذریعے اس وقت میں حل کیا جا سکتا ہے جو مسئلہ کی وضاحت کرنے والے عناصر کی تعداد میں لکیری ہو، اور مسئلہ کے طول و عرض میں سب ایکسپونینشل ہو۔ تعریف ایل پی قسم کے مسائل کو ان مسائل کے طور پر بیان کیا گیا تھا جن میں کسی کو عناصر کے ایک محدود سیٹ کو ان پٹ کے طور پر دیا جاتا ہے، اور ایک فنکشن جو مکمل طور پر ترتیب شدہ سیٹ سے اقدار کے ذیلی سیٹوں کا نقشہ بناتا ہے۔ فنکشن دو کلیدی خصوصیات کو پورا کرنے کے لیے ضروری ہے: یکسانیت: ہر دو سیٹوں کے لیے، f (A) ≤ f (B) ≤ f (S)۔ لوکلٹی: ہر دو سیٹوں اور ہر عنصر کے لیے، اگر، تب۔ ایل پی قسم کے مسئلے کی بنیاد اس خاصیت کے ساتھ ایک سیٹ ہے جس کے ہر مناسب ذیلی سیٹ کی قدر خود سے کم ہوتی ہے، اور ایل پی قسم کے مسئلے کے طول و عرض (یا مشترکہ طول و عرض) کو بنیاد کی زیادہ سے زیادہ بنیادی حیثیت کے طور پر بیان کیا جاتا ہے۔ یہ فرض کیا جاتا ہے کہ آپٹیمائزیشن الگورتھم فنکشن کا اندازہ صرف ان سیٹوں پر کر سکتا ہے جو خود بیس ہیں یا جو ایک عنصر کو بیس میں شامل کر کے بنائے جاتے ہیں۔ متبادل طور پر، الگورتھم کو دو ابتدائی کارروائیوں تک محدود کیا جا سکتا ہے: ایک خلاف ورزی کا ٹیسٹ جو اس بات کا تعین کرتا ہے، ایک بنیاد اور ایک عنصر کے لیے کہ آیا، اور ایک بنیادی حساب جو (ایک ہی ان پٹ کے ساتھ) کی بنیاد تلاش کرتا ہے۔ الگورتھم کے لیے انجام دینے کا کام صرف ان محدود تشخیصوں یا ابتدائی کا استعمال کرکے اندازہ لگانا ہے۔ مثالیں اور ایپلی کیشنز ایک لکیری پروگرام کی تعریف غیر منفی حقیقی متغیرات کے نظام کے ذریعے کی جا سکتی ہے، جو لکیری عدم مساوات کی رکاوٹوں کے تابع ہے، ساتھ ہی ایک غیر منفی لکیری معروضی فنکشن کو کم سے کم کیا جا سکتا ہے۔ اسے ایل پی قسم کے مسائل کے فریم ورک میں رکاوٹوں کا مجموعہ بنا کر رکھا جا سکتا ہے، اور (رکاوٹوں کے ذیلی سیٹ کے لیے) کے ذریعے بیان کردہ چھوٹے لکیری پروگرام کی کم از کم معروضی فنکشن ویلیو کی وضاحت کی جا سکتی ہے۔ مناسب عمومی پوزیشن کے مفروضوں کے ساتھ (ایک ہی بہترین معروضی فنکشن ویلیو والے متعدد حل پوائنٹس کو روکنے کے لیے)، یہ ایل پی قسم کے مسئلے کی یکسانیت اور مقامی ضروریات کو پورا کرتا ہے، اور متغیرات کی تعداد کے برابر مشترکہ طول و عرض رکھتا ہے۔ اسی طرح، ایک انٹیجر پروگرام (جو لکیری رکاوٹوں کے مجموعے اور لکیری آبجیکٹ فنکشن پر مشتمل ہوتا ہے، جیسا کہ لکیری پروگرام میں ہوتا ہے، لیکن اس اضافی پابندی کے ساتھ کہ متغیرات کو صرف انٹیجر ویلیوز پر لینا چاہیے) ایل پی قسم کے مسئلے کی یکسانیت اور لوکیٹی پراپرٹیز دونوں کو مطمئن کرتا ہے، لکیری پروگراموں کی طرح ہی عمومی پوزیشن کے مفروضوں کے ساتھ۔ کے نظریات اور یہ ظاہر کرتے ہیں کہ، متغیرات کے ساتھ ایک انٹیجر پروگرام کے لیے، مشترکہ طول و عرض زیادہ سے زیادہ ہے۔ کمپیوٹیشنل جیومیٹری میں بہت سے قدرتی اصلاح کے مسائل ایل پی-ٹائپ ہیں: دائرے کا سب سے چھوٹا مسئلہ ایک دائرے کے کم از کم رداس کو تلاش کرنے کا مسئلہ ہے جس میں طیارہ میں پوائنٹس کا ایک سیٹ ہوتا ہے۔ یہ یکسانیت کو مطمئن کرتا ہے (مزید پوائنٹس کا اضافہ صرف دائرے کو بڑا بنا سکتا ہے) اور لوکیٹی (اگر سیٹ کے لیے سب سے چھوٹا دائرہ موجود ہو اور، تو وہی دائرہ بھی موجود ہو)۔ چونکہ سب سے چھوٹے دائرے کا تعین ہمیشہ کچھ تین نکات سے ہوتا ہے، اس لیے سب سے چھوٹے دائرے کے مسئلے کی مشترکہ جہت تین ہوتی ہے، حالانکہ اس کی تعریف دو جہتی یوکلڈین جیومیٹری کا استعمال کرتے ہوئے کی گئی ہے۔ زیادہ عام طور پر، طول و عرض میں پوائنٹس کی سب سے چھوٹی منسلک گیند مشترکہ طول و عرض کا ایل پی قسم کا مسئلہ بناتی ہے۔ سب سے چھوٹے دائرے کے مسئلے کو عام طور پر گیندوں کے ایک سیٹ کو گھیرے ہوئے سب سے چھوٹی گیند، سب سے چھوٹی گیند جو گیندوں کے ہر سیٹ کو چھوتی ہے یا گھیرے ہوئے ہے، وزن والے 1 سینٹر کے مسئلے، یا غیر یوکلڈین خالی جگہوں میں اسی طرح کے چھوٹے گھیرے ہوئے گیند کے مسائل جیسے کہ بریگ مین کے انحراف سے طے شدہ فاصلے والی جگہ تک عام کیا جا سکتا ہے۔ سب سے چھوٹے منسلک ایلیپسائڈ کو تلاش کرنے کا متعلقہ مسئلہ بھی ایک ایل پی قسم کا مسئلہ ہے، لیکن ایک بڑے مشترکہ طول و عرض کے ساتھ۔ آئیے-جہتی یوکلڈین اسپیس میں کنویکس سیٹوں کی ایک ترتیب بنیں، اور فرض کریں کہ ہم اس ترتیب کا سب سے طویل سابقہ تلاش کرنا چاہتے ہیں جس کا ایک مشترکہ انٹرسیکشن پوائنٹ ہے۔ اس کا اظہار ایل پی قسم کے مسئلے کے طور پر کیا جا سکتا ہے جس میں جہاں کی اے کا پہلا رکن ہے جس کا تعلق اے کے انٹرسیکٹنگ پریفیکس سے نہیں ہے، اور جہاں اگر ایسا کوئی ممبر نہیں ہے۔ اس نظام کی مشترکہ جہت ہے۔ فرض کریں کہ ہمیں تین جہتی جگہ میں محور سے منسلک آئتاکار خانوں کا مجموعہ دیا گیا ہے، اور ہم جگہ کے مثبت آکٹینٹ میں ایک ایسی لکیر تلاش کرنا چاہتے ہیں جو تمام خانوں کو کاٹ دے۔ اس کا اظہار مشترکہ جہت 4 کے ساتھ ایل پی قسم کے مسئلے کے طور پر کیا جا سکتا ہے۔ دو کنویکس پولی ٹاپس کے درمیان قریب ترین فاصلہ تلاش کرنے کا مسئلہ، جو ان کے عمودی سیٹوں سے متعین ہوتا ہے، کو ایل پی قسم کے مسئلے کے طور پر پیش کیا جا سکتا ہے۔ اس تشکیل میں، سیٹ دونوں پولی ٹاپس میں تمام عمودی حصوں کا مجموعہ ہے، اور فنکشن ویلیو دو پولی ٹاپس میں عمودی حصوں کے دو ذیلی سیٹوں کے کنویکس ہلز کے درمیان سب سے چھوٹے فاصلے کی نفی ہے۔ مسئلہ کی مشترکہ جہت یہ ہے کہ اگر دو پولی ٹاپس جداگانہ ہیں، یا اگر ان کا غیر خالی چوراہا ہے۔ فرض کریں کہ} کواسیکونویکس افعال کا ایک مجموعہ ہے۔ پھر نقطہ وار زیادہ سے زیادہ خود کواسیکونویکس ہے، اور اس کی کم سے کم قیمت تلاش کرنے کا مسئلہ ایل پی قسم کا مسئلہ ہے۔ اس میں زیادہ سے زیادہ مشترکہ طول و عرض ہوتا ہے، افعال کے ڈومین کا طول و عرض کہاں ہے، لیکن کافی ہموار افعال کے لیے مشترکہ طول و عرض زیادہ سے زیادہ چھوٹا ہوتا ہے۔ ایل پی قسم کے بہت سے دوسرے مسائل کو بھی اس طرح سے کواسیکونویکس افعال کا استعمال کرتے ہوئے ظاہر کیا جا سکتا ہے۔ مثال کے طور پر، سب سے چھوٹا گھیرے ہوئے دائرے کا مسئلہ کم کرنے کا مسئلہ ہے جہاں ہر فنکشن دیئے گئے نکات میں سے کسی ایک سے یوکلڈین فاصلے کی پیمائش کرتا ہے۔ ایل پی قسم کے مسائل کو الگورتھمک گیم تھیوری میں بعض کھیلوں کے زیادہ سے زیادہ نتائج کا تعین کرنے، محدود عنصر کے طریقہ کار کے میش میں ورٹیکس پلیسمنٹ کو بہتر بنانے، سہولت کے مقام کے مسائل کو حل کرنے، مخصوص ایکسپونینشل ٹائم سرچ الگورتھم کی وقت کی پیچیدگی کا تجزیہ کرنے، اور اشیاء کی تین جہتی پوزیشنوں کو ان کی دو جہتی تصاویر سے دوبارہ تشکیل دینے کے لیے بھی استعمال کیا گیا ہے۔ الگورتھم سیڈل نے کم جہتی لکیری پروگرامنگ کے لیے ایک الگورتھم دیا جسے ایل پی قسم کے مسئلہ کے فریم ورک کے مطابق ڈھالا جا سکتا ہے۔ سیڈل کا الگورتھم ان پٹ کے طور پر سیٹ اور عناصر کا ایک علیحدہ سیٹ (ابتدائی طور پر خالی) لیتا ہے جو زیادہ سے زیادہ بنیاد سے تعلق رکھتے ہیں۔ اس کے بعد یہ بقیہ عناصر پر ایک ایک کر کے بے ترتیب ترتیب میں غور کرتا ہے، ہر ایک کے لیے خلاف ورزی کے ٹیسٹ انجام دیتا ہے اور نتیجہ پر منحصر ہے، معروف بنیادی عناصر کے بڑے سیٹ کے ساتھ اسی الگورتھم پر ریکرسو کال انجام دیتا ہے۔ اس کا اظہار مندرجہ ذیل سڈوکوڈ کے ساتھ کیا جا سکتا ہے: فنکشن سیڈل (S, f, X) R ہے: = خالی سیٹ B: = X کے لیے x کے لیے S کے بے ترتیب تعدد میں: اگر f (B) § f (B ≤ {x}): B: = سیڈل (R, f, X ≤ {x}) R: = R ≤ {x} ریٹرن B۔ اس حساب کی بنیاد پر، یہ دکھایا جا سکتا ہے کہ مجموعی طور پر الگورتھم کے ذریعے انجام دیے جانے والے خلاف ورزی کے ٹیسٹوں کی متوقع تعداد لکیری ہے لیکن اس میں ایکسپونینشل سے بھی بدتر ہے۔ کلارکسن بے ترتیب نمونے لینے کی تکنیکوں پر مبنی لکیری پروگرامنگ کے لیے دو الگورتھم، ایک تکراری الگورتھم اور ایک تکراری الگورتھم کی وضاحت کرتا ہے، اور دونوں کا ایک مجموعہ تجویز کرتا ہے جو تکراری الگورتھم سے تکراری الگورتھم کو کال کرتا ہے۔ تکراری الگورتھم بار بار بے ترتیب نمونوں کا انتخاب کرتا ہے جن کا سائز ان پٹ سائز کا تقریبا مربع جڑ ہوتا ہے، نمونے لینے والے مسئلے کو تکراری طور پر حل کرتا ہے، اور پھر باقی عناصر کے ذیلی سیٹ کو تلاش کرنے کے لیے خلاف ورزی کے ٹیسٹ کا استعمال کرتا ہے جس میں کم از کم ایک بنیادی عنصر شامل ہونا چاہیے: فنکشن تکراری (S, f) X ہے: = خالی سیٹ ریپیٹ R: = S کا بے ترتیب ذیلی سیٹ جس کا سائز d σnB ہے: = R σ کے لیے بنیاد، تکراری طور پر شمار کیا جاتا ہے V: = {x | f (B) ≤ f (B ≤ x)} X: = X ≤ V جب تک کہ V خالی ریٹرن B نہ ہو ہر تکرار میں، اس کا متوقع سائز ہے، اور جب بھی خالی ہوتا ہے اس میں کم از کم ایک شامل ہوتا ہے۔ لہذا، الگورتھم زیادہ تر تکرار پر کارکردگی کا مظاہرہ کرتا ہے، جن میں سے ہر ایک خلاف ورزی کے ٹیسٹ انجام دیتا ہے اور سائز کے ذیلی مسئلے پر ایک بار بار کال کرتا ہے۔ کلارکسن کا تکراری الگورتھم ہر عنصر کو وزن تفویض کرتا ہے، ابتدائی طور پر وہ سب برابر ہیں۔ اس کے بعد یہ بے ترتیب سے عناصر کا ایک مجموعہ منتخب کرتا ہے، اور سیٹوں کا حساب لگاتا ہے اور جیسا کہ پچھلے الگورتھم میں ہے۔ اگر کا کل وزن زیادہ تر اوقات کا کل وزن ہے (جیسا کہ مستقل امکان کے ساتھ ہوتا ہے) تو الگورتھم کے ہر عنصر کے وزن کو دوگنا کر دیتا ہے، اور پہلے کی طرح اس عمل کو اس وقت تک دہراتا ہے جب تک کہ خالی نہ ہو جائے۔ ہر تکرار میں، زیادہ سے زیادہ بنیاد کا وزن کل وزن سے زیادہ شرح سے بڑھتا ہوا دکھایا جا سکتا ہے، جس سے یہ نتیجہ نکلتا ہے کہ الگورتھم کو تکرار کے اندر ہی ختم ہونا چاہیے۔ کسی دیئے گئے مسئلے کو حل کرنے کے لیے تکراری الگورتھم کا استعمال کرتے ہوئے، اس کی تکراری کالوں کے لیے تکراری الگورتھم میں تبدیل ہو کر، اور پھر تکراری الگورتھم کے ذریعے کی جانے والی کالوں کے لیے سیڈل کے الگورتھم میں دوبارہ تبدیل ہو کر، خلاف ورزی کے ٹیسٹ کا استعمال کرتے ہوئے دیئے گئے ایل پی قسم کے مسئلے کو حل کرنا ممکن ہے۔ جب کسی لکیری پروگرام پر لاگو کیا جاتا ہے، تو اس الگورتھم کو ڈوئل سمپلیکس طریقہ کے طور پر سمجھا جا سکتا ہے۔ خلاف ورزی ٹیسٹ اور بیس کمپیوٹیشن پرائمیٹوز سے بالاتر کچھ اضافی کمپیوٹیشنل پرائمیٹوز کے ساتھ، اس طریقہ کو تعیناتی بنایا جا سکتا ہے۔ میٹوسیک، شیر اور ویلزل ایک الگورتھم کی وضاحت کرتے ہیں جو لکیری پروگراموں کی ایک اضافی خاصیت کا استعمال کرتا ہے جو ہمیشہ دوسرے ایل پی قسم کے مسائل کے پاس نہیں ہوتا ہے، کہ تمام اڈوں میں ایک دوسرے کی ایک جیسی بنیادی حیثیت ہوتی ہے۔ اگر ایل پی قسم کے مسئلے میں یہ خاصیت نہیں ہے، تو اسے نئے ڈمی عناصر کو شامل کرکے اور فنکشن میں ترمیم کرکے اس کی پرانی قیمت اور نمبر کے ترتیب شدہ جوڑے کو لیکسیگرافک طور پر واپس کرنے کے لیے بنایا جا سکتا ہے۔ ایک وقت میں ایس ون کے عناصر کو شامل کرنے، یا عناصر کے نمونے تلاش کرنے کے بجائے، ایک الگورتھم کی وضاحت کریں جو ایک وقت میں عناصر کو ہٹا دیتا ہے۔ ہر مرحلے پر یہ ایک بنیاد کو برقرار رکھتا ہے جو ابتدائی طور پر ڈمی عناصر کا مجموعہ ہو سکتا ہے۔ اسے مندرجہ ذیل سڈوکوڈ کے ساتھ بیان کیا جا سکتا ہے: فنکشن ایم ایس ڈبلیو (ایس، ایف، سی) یہ ہے کہ اگر ایس = سی تو ریٹرن سی ایک بے ترتیب عنصر ایکس کا انتخاب کرتا ہے جس میں ایس\سی بی = ایم ایس ڈبلیو (ایس\ایکس، ایف، سی) اگر ایف (بی) ष्णف (بی ष्णف {ایکس}) تو بی: = بیس (بی ष्णف {ایکس}) بی: = ایم ایس ڈبلیو (ایس، ایف، بی) ریٹرن بی الگورتھم کی زیادہ تر ریکرسو کالز میں، خلاف ورزی کا ٹیسٹ کامیاب ہو جاتا ہے اور آئی ایف اسٹیٹمنٹ چھوڑ دیا جاتا ہے۔ تاہم، ایک چھوٹے سے امکان کے ساتھ خلاف ورزی کا ٹیسٹ ناکام ہوجاتا ہے اور الگورتھم ایک اضافی بیس کمپیوٹیشن اور پھر ایک اضافی ریکرسو کال کرتا ہے۔ جیسا کہ مصنفین دکھاتے ہیں، الگورتھم کے لیے متوقع وقت n میں لکیری اور کے مربع جڑ میں ایکسپونینشل ہوتا ہے۔ اس طریقہ کار کو کلارکسن کے تکراری اور تکراری طریقہ کار کے ساتھ جوڑ کر، وقت پر انحصار کی ان دو شکلوں کو ایک دوسرے سے الگ کیا جا سکتا ہے، جس کے نتیجے میں ایک الگورتھم ہوتا ہے جو بیرونی تکراری الگورتھم میں او (ڈی این) کی خلاف ورزی کے ٹیسٹ انجام دیتا ہے اور ایک ایسا نمبر جو الگورتھم کی نچلی سطحوں کے مربع جڑ میں ایکسپونینشل ہوتا ہے۔ آؤٹ لیئرز کے ساتھ تغیرات اصلاح ایل پی قسم کی اصلاح کے مسائل کی ایک تغیر پر غور کرتی ہے جس میں سیٹ اور آبجیکٹیو فنکشن کے ساتھ مل کر ایک نمبر دیا جاتا ہے۔ کام عناصر کو ہٹانا ہے تاکہ بقیہ سیٹ پر آبجیکٹیو فنکشن کو جتنا ممکن ہو اتنا چھوٹا بنایا جا سکے۔ مثال کے طور پر، جب سب سے چھوٹے دائرے کے مسئلے پر لاگو ہوتا ہے، تو یہ سب سے چھوٹا دائرہ دے گا جس میں پلانر پوائنٹس کے دیئے گئے سیٹ کے علاوہ باقی سب شامل ہوتے ہیں۔ وہ دکھاتا ہے کہ، تمام غیر انحطاطی ایل پی قسم کے مسائل کے لیے (یعنی وہ مسائل جن میں تمام اڈوں کی الگ الگ اقدار ہوتی ہیں) اس مسئلے کو وقت پر حل کیا جا سکتا ہے، ایل پی قسم کے مسائل کے ایک سیٹ کو حل کرکے جس کی وضاحت ذیلی سیٹوں کے ذریعے کی جاتی ہے۔ کچھ ہندسی اصلاح کے مسائل کو ایل پی قسم کے مسائل کے طور پر ظاہر کیا جا سکتا ہے جس میں ایل پی قسم کی تشکیل میں عناصر کی تعداد اصلاح کے مسئلے کے لیے ان پٹ ڈیٹا ویلیوز کی تعداد سے نمایاں طور پر زیادہ ہوتی ہے۔ مثال کے طور پر، طیارہ میں پوائنٹس کے مجموعے پر غور کریں، جن میں سے ہر ایک مستقل رفتار کے ساتھ حرکت کرتا ہے۔ کسی بھی وقت، اس نظام کا قطر اس کے دو نکات کے درمیان زیادہ سے زیادہ فاصلہ ہوتا ہے۔ ایسے وقت کو تلاش کرنے کا مسئلہ جس پر قطر کو کم سے کم کیا جاتا ہے، کواسکونویکس افعال کے نقطہ وار زیادہ سے زیادہ کو کم کرنے کے طور پر وضع کیا جا سکتا ہے، ہر جوڑے کے لیے ایک، جوڑے کے درمیان یوکلڈین فاصلے کو وقت کی تقریب کے طور پر ماپتا ہے۔ اس طرح، اسے عناصر کے ایک سیٹ پر مشترکہ طول و عرض دو کے ایل پی قسم کے مسئلے کے طور پر حل کیا جا سکتا ہے، لیکن یہ سیٹ ان پٹ پوائنٹس کی تعداد سے نمایاں طور پر بڑا ہے۔ ایل پی قسم کے مسائل کو حل کرنے کے لیے ایک الگورتھم کی وضاحت کرتا ہے جیسے کہ اس میں ہر ایل پی قسم کے عنصر کا تعین کچھ مستقل کے لیے ان پٹ اقدار کے-ٹپل کے ذریعے کیا جاتا ہے۔ اس کے نقطہ نظر کو لاگو کرنے کے لیے، ایک فیصلہ الگورتھم موجود ہونا چاہیے جو کسی دی گئی ایل پی قسم کی بنیاد اور ان پٹ اقدار کے سیٹ کے لیے اس بات کا تعین کر سکے کہ آیا ایل پی قسم کے مسئلے کی بنیاد اس کے ذریعے متعین کی گئی ہے۔ چن کا الگورتھم مندرجہ ذیل مراحل انجام دیتا ہے: اگر ان پٹ اقدار کی تعداد کسی حد سے کم ہے، تو ایل پی قسم کے عناصر کا مجموعہ تلاش کریں جو اس کا تعین کرتا ہے اور نتیجے میں واضح ایل پی قسم کے مسئلے کو حل کرتا ہے۔ بصورت دیگر، ان پٹ اقدار کو مساوی سائز کے ذیلی سیٹوں سے زیادہ مناسب تعداد میں تقسیم کریں۔ اگر مضمر طور پر بیان کردہ ایل پی قسم کے مسئلے کو حل کرنے کے لیے معروضی فنکشن ہے، تو ایک فنکشن کی وضاحت کریں جو ذیلی سیٹوں کے مجموعے کو مجموعہ کے اتحاد کی قیمت سے جوڑتا ہے۔ پھر ذیلی سیٹوں کا مجموعہ اور معروضی فنکشن خود ایک ایل پی قسم کے مسئلے کی وضاحت کرتا ہے، جس کی جہت اسی طرح کی ہوتی ہے جسے حل کیا جانا ہے۔ کلارکسن کے الگورتھم کا استعمال کرتے ہوئے بیان کردہ (واضح) ایل پی قسم کے مسئلے کو حل کریں، جو خلاف ورزی کے ٹیسٹ کی لکیری تعداد اور بنیادی تشخیص کی پولی لوگرتھمک تعداد انجام دیتا ہے۔ بنیادی تشخیص چن کے الگورتھم پر بار بار کال کے ذریعے کی جا سکتی ہے، اور خلاف ورزی کے ٹیسٹ فیصلہ الگورتھم پر کال کے ذریعے کیے جا سکتے ہیں۔ اس مفروضے کے ساتھ کہ فیصلہ الگورتھم میں کافی وقت لگتا ہے جو کم از کم ان پٹ سائز کے فنکشن کے طور پر کثیر الجہتی طور پر بڑھتا ہے، چن ظاہر کرتا ہے کہ ایک واضح ایل پی فارمولیشن میں تبدیل ہونے کی حد اور پارٹیشن میں ذیلی سیٹوں کی تعداد کو اس طرح منتخب کیا جا سکتا ہے کہ مضمر ایل پی قسم کی اصلاح الگورتھم بھی وقت پر چلتی ہے۔ مثال کے طور پر، حرکت پذیر پوائنٹس کے کم از کم قطر کے لیے، فیصلہ الگورتھم کو صرف ایک مقررہ وقت پر پوائنٹس کے سیٹ کے قطر کا حساب لگانے کی ضرورت ہوتی ہے، یہ ایک ایسا مسئلہ ہے جسے گھومنے والی کیلیپرز تکنیک کا استعمال کرتے ہوئے وقت پر حل کیا جا سکتا ہے۔ لہذا، جس وقت قطر کو کم سے کم کیا جاتا ہے اسے تلاش کرنے کے لیے چن کا الگورتھم بھی وقت لیتا ہے۔ چن اس طریقہ کار کا استعمال وقت کے ساتھ-جہتی یوکلڈین اسپیس میں پوائنٹس کے دیئے گئے مجموعہ کے درمیان زیادہ سے زیادہ ٹوکی گہرائی کا نقطہ تلاش کرنے کے لیے کرتا ہے۔ ایک متغیر کثیر الاضحی پر یکساں تقسیم کے لیے زیادہ سے زیادہ ٹوکی گہرائی کے نقطہ کو تلاش کرنے کے لیے اسی طرح کی تکنیک کا استعمال کیا گیا تھا۔ تاریخ اور متعلقہ مسائل لکیری پروگرامنگ کے لیے لکیری ٹائم الگورتھم کی دریافت اور یہ مشاہدہ کہ ایک ہی الگورتھم کو بہت سے معاملات میں ہندسی اصلاح کے مسائل کو حل کرنے کے لیے استعمال کیا جا سکتا ہے جو لکیری پروگرام نہیں تھے، کم از کم ان کے پاس جاتا ہے، جنہوں نے تین متغیر لکیری پروگراموں اور سب سے چھوٹے دائرے کے مسئلے دونوں کے لیے لکیری متوقع ٹائم الگورتھم دیا۔ تاہم، میگڈو نے لکیری پروگرامنگ کی عمومی شکل کو یکجا کرنے کے بجائے ہندسی طور پر وضع کیا، جو کہ سیٹوں کے نظام پر ایک تجریدی مسئلہ کے بجائے ایک کنویکس آپٹیمائزیشن مسئلہ کے طور پر ہے۔ اسی طرح، اور کلارکسن (1988 کے کانفرنس ورژن میں) نے مشاہدہ کیا کہ ان کے طریقوں کا اطلاق کنویکس پروگراموں کے ساتھ ساتھ لکیری پروگراموں پر بھی کیا جا سکتا ہے۔ اس سے پتہ چلتا ہے کہ کم سے کم منسلک ایلیپسائڈ مسئلہ کو غیر لکیری رکاوٹوں کی ایک چھوٹی سی تعداد کو شامل کرکے کنویکس آپٹیمائزیشن مسئلہ کے طور پر بھی وضع کیا جا سکتا ہے۔ کم جہتی لکیری پروگرامنگ اور متعلقہ مسائل کے لیے وقت کی حدود کو بہتر بنانے کے لیے بے ترتیب کاری کے استعمال کا آغاز کلارکسن نے کیا تھا۔ لوکیٹی اور مونوٹونیکیٹی کے محرکات کو مطمئن کرنے والے افعال کے لحاظ سے ایل پی قسم کے مسائل کی تعریف سے ہے، لیکن اسی ٹائم فریم میں دوسرے مصنفین نے لکیری پروگراموں کی متبادل مشترکہ عمومی تشکیل دی۔ مثال کے طور پر، کے ذریعہ تیار کردہ فریم ورک میں، فنکشن کو ذیلی سیٹوں پر کل ترتیب سے تبدیل کیا جاتا ہے۔ کل آرڈر بنانے کے لیے ایل پی قسم کے مسئلے میں تعلقات کو توڑنا ممکن ہے، لیکن صرف مشترکہ طول و عرض میں اضافے کی قیمت پر۔ مزید برآں، جیسا کہ ایل پی قسم کے مسائل میں، گارٹنر عناصر کے ذیلی سیٹوں پر کمپیوٹیشن انجام دینے کے لیے کچھ پرائمیٹوز کی وضاحت کرتا ہے ؛ تاہم، اس کی رسمی شکل میں مشترکہ جہت کا ینالاگ نہیں ہے۔ لکیری پروگراموں اور لکیری تکمیلی مسائل دونوں کی ایک اور تجریدی عمومی کاری، جسے کئی دیگر مصنفین نے وضع کیا اور بعد میں اس کا مطالعہ کیا گیا، ہائپر کیوب کے کناروں کی سمت کا اس خاصیت سے متعلق ہے کہ ہائپر کیوب کے ہر چہرے (بشمول چہرے کے طور پر پورے ہائپر کیوب) میں ایک منفرد سنک ہوتا ہے، ایک ورٹیکس جس میں کوئی باہر جانے والے کنارے نہیں ہوتے ہیں۔ اس قسم کی واقفیت ایل پی قسم کے مسئلے سے تشکیل پائی جا سکتی ہے جس میں ایس کے ذیلی سیٹوں کو ہائپر کیوب کے عمودی حصوں سے اس طرح مطابقت دی جائے کہ دو ذیلی سیٹوں میں ایک عنصر سے فرق ہو اگر اور صرف اس صورت میں جب متعلقہ عمودی حصے ملحقہ ہوں، اور پڑوسی سیٹوں کے درمیان کنارے کو اگر اور دوسری طرف سمت دے کر۔ نتیجے میں ہونے والی واقفیت میں اضافی خاصیت ہوتی ہے کہ یہ ایک ڈائریکٹڈ ایسائکلک گراف بناتا ہے، جس سے یہ دکھایا جا سکتا ہے کہ ایک بے ترتیب الگورتھم پورے ہائپر کیوب (ایل پی قسم کے مسئلے کی بہترین بنیاد) کے منفرد سنک کو کئی مراحل میں تلاش کر سکتا ہے۔ خلاف ورزی کرنے والی جگہوں کا حال ہی میں تیار کردہ فریم ورک ایل پی قسم کے مسائل کو عام کرتا ہے، اس معنی میں کہ ہر ایل پی قسم کے مسئلے کو خلاف ورزی کرنے والی جگہ کے ذریعے ماڈل کیا جا سکتا ہے لیکن ضروری نہیں کہ اس کے برعکس ہو۔ خلاف ورزی کرنے والی جگہوں کو ایل پی قسم کے مسائل کی طرح بیان کیا جاتا ہے، ایک فنکشن کے ذریعہ جو نقشہ آبجیکٹیو فنکشن ویلیوز پر سیٹ کرتا ہے، لیکن کی ویلیوز کو آرڈر نہیں کیا جاتا ہے۔ آرڈر کی کمی کے باوجود، ہر سیٹ میں اڈوں کا ایک اچھی طرح سے متعین سیٹ ہوتا ہے (پورے سیٹ کی طرح ہی قدر کے ساتھ کم سے کم سیٹ) جو ایل پی قسم کے مسائل کے لیے کلارکسن کے الگورتھم کے تغیرات سے پایا جا سکتا ہے۔ درحقیقت، خلاف ورزی کرنے والی جگہوں کو ان نظاموں کی بالکل خصوصیت کے لیے دکھایا گیا ہے جنہیں کلارکسن کے الگورتھم کے ذریعے حل کیا جا سکتا ہے۔ حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ کمپیوٹیشنل جیومیٹری لکیری پروگرامنگ