محققین سیمینل مسئلہ کے لیے نئی رفتار کی حد تک پہنچتے ہیں۔ کوانٹا میگزین

سفر کرنے والے سیلز پرسن کا مسئلہ سب سے پرانے شمار شدہ کمپیوٹیشنل سوالات میں سے ایک ہے۔ یہ مائلیج کو کم سے کم کرتے ہوئے شہروں کی ایک مخصوص فہرست کے ذریعے مثالی راستہ مانگتا ہے۔ بظاہر سادہ نظر آنے کے باوجود، مسئلہ بدنام زمانہ مشکل ہے۔ اگرچہ آپ تمام ممکنہ راستوں کو چیک کرنے کے لیے طاقت کا استعمال کر سکتے ہیں جب تک کہ آپ کو مختصر ترین راستہ نہ مل جائے، ایسی حکمت عملی صرف چند شہروں کے بعد ناقابل برداشت ہو جاتی ہے۔ اس کے بجائے، آپ ایک سخت ریاضیاتی ماڈل کا اطلاق کر سکتے ہیں جسے لکیری پروگرامنگ کہا جاتا ہے، جو تقریباً مساوات کے ایک سیٹ کے طور پر مسئلہ کا تخمینہ لگاتا ہے اور بہترین حل تلاش کرنے کے لیے ممکنہ امتزاج کو طریقہ سے جانچتا ہے۔

لیکن بعض اوقات، آپ کو پوری تعداد کی مقدار میں شامل مسائل کے لیے بہتر بنانے کی ضرورت ہوتی ہے۔ ایک فیکٹری آپٹیمائزیشن پلان کیا فائدہ ہے جو 500.7 صوفے تیار کرتا ہے؟ اس کے لیے، محققین اکثر لکیری پروگرامنگ کی ایک قسم کی طرف رجوع کرتے ہیں جسے کہتے ہیں۔ انٹیجر لکیری پروگرامنگ (ILP)۔ یہ ان ایپلی کیشنز میں مقبول ہے جن میں پروڈکشن پلاننگ، ایئر لائن کے عملے کی شیڈولنگ اور گاڑیوں کی روٹنگ سمیت مجرد فیصلے شامل ہوتے ہیں۔ "بنیادی طور پر، ILP تھیوری اور پریکٹس دونوں لحاظ سے آپریشنز ریسرچ کی روٹی اور مکھن ہے،" کہا سنتوش ویمپالاجارجیا انسٹی ٹیوٹ آف ٹیکنالوجی میں کمپیوٹر سائنسدان۔

چونکہ انہوں نے سب سے پہلے ILP تیار کیا۔ 60 سال پہلے، محققین نے مختلف الگورتھم دریافت کیے ہیں جو ILP کے مسائل کو حل کرتے ہیں، لیکن وہ تمام مطلوبہ اقدامات کی تعداد کے لحاظ سے نسبتاً سست رہے ہیں۔ وہ بہترین ورژن جس کے ساتھ وہ سامنے آسکتے ہیں — ایک قسم کی رفتار کی حد — ایک چھوٹی سی صورت سے آتی ہے جہاں مسئلہ کے متغیرات (جیسے کہ سیلز مین کسی شہر کا دورہ کرتا ہے یا نہیں) صرف بائنری اقدار (صفر یا 1) کو فرض کر سکتا ہے۔ اس صورت میں، ILP کا ایک رن ٹائم ہے جو متغیرات کی تعداد کے ساتھ تیزی سے پیمانہ کرتا ہے، جسے طول و عرض بھی کہا جاتا ہے۔ (اگر صرف ایک متغیر ہے تو، یہ ہر ممکنہ امتزاج کو جانچنے اور مسئلہ کو حل کرنے کے لیے صرف دو قدم لیتا ہے؛ دو متغیر کا مطلب چار مراحل، تین کا مطلب آٹھ قدم، وغیرہ۔)

بدقسمتی سے، ایک بار جب متغیرات صفر اور 1 سے آگے کی قدر لے لیتے ہیں، تو الگورتھم کا رن ٹائم بہت زیادہ بڑھ جاتا ہے۔ محققین نے طویل عرصے سے سوچا ہے کہ کیا وہ معمولی مثالی کے قریب پہنچ سکتے ہیں۔ کے ساتھ پیش رفت سست رہی ہے۔ ریکارڈ 1980 کی دہائی میں مقرر کیا گیا اور صرف اضافہ بہتری کے بعد سے بنایا.

لیکن حالیہ کام by وکٹر ریس، فی الحال انسٹی ٹیوٹ فار ایڈوانسڈ اسٹڈی میں، اور تھامس روتھواسواشنگٹن یونیورسٹی میں، دہائیوں میں رن ٹائم کی سب سے بڑی چھلانگ لگائی ہے۔ ممکنہ حل کو محدود کرنے کے لیے جیومیٹرک ٹولز کو جوڑ کر، انھوں نے ILP کو حل کرنے کے لیے ایک نیا، تیز تر الگورتھم بنایا جس میں معمولی بائنری کیس تقریباً ایک ہی وقت میں ہوتا ہے۔ نتیجہ کو 2023 میں بہترین پیپر کا ایوارڈ ملا کمپیوٹر سائنس کی بنیادیں کانفرنس

"یہ نیا الگورتھم انتہائی دلچسپ ہے،" نے کہا نوح سٹیفنز-ڈیوڈووٹز، کارنیل یونیورسٹی میں ایک ریاضی دان اور کمپیوٹر سائنس دان۔ "یہ تقریباً 40 سالوں میں ILP حل کرنے والوں میں پہلی [بڑی] بہتری کی نمائندگی کرتا ہے۔"

ILP کسی دیے گئے مسئلے کو لکیری مساوات کے ایک سیٹ میں تبدیل کرکے کام کرتا ہے جو کچھ عدم مساوات کو پورا کرتی ہے۔ مخصوص مساوات اصل مسئلہ کی تفصیلات پر مبنی ہیں۔ لیکن اگرچہ یہ تفصیلات مختلف ہو سکتی ہیں، لیکن ILP مسائل کا بنیادی میک اپ ایک ہی رہتا ہے، جس سے محققین کو بہت سے مسائل پر حملہ کرنے کا واحد راستہ ملتا ہے۔

اس کا مطلب یہ نہیں ہے کہ یہ آسان کام ہے۔ یہ 1983 تک نہیں تھا کہ ریاضی دان ہینڈرک لینسٹرا۔ ثابت ہوا کہ عام مسئلہ بھی قابل حل تھا، پہلا الگورتھم فراہم کرتا ہے جو اسے کر سکتا تھا۔ لینسٹرا نے ILP کے بارے میں ہندسی طور پر سوچا۔ سب سے پہلے، اس نے ILP کے مرکز میں موجود عدم مساوات کو محدب شکل میں تبدیل کر دیا، جیسے کہ کوئی باقاعدہ کثیرالاضلاع۔ یہ شکل انفرادی مسئلے کی رکاوٹوں کی نمائندگی کرتی ہے جسے آپ حل کر رہے ہیں، چاہے وہ صوفے کی پیداوار ہو یا ایئر لائن کا شیڈولنگ، لہذا شکل کا اندرونی حصہ ان تمام ممکنہ اقدار سے مطابقت رکھتا ہے جو عدم مساوات کو حل کر سکتے ہیں، اور اس طرح مسئلہ۔ لینسٹرا نے اس شکل کو محدب جسم کہا۔ مسئلہ کا طول و عرض اس شکل کے طول و عرض کو متاثر کرتا ہے: دو متغیرات کے ساتھ یہ ایک فلیٹ کثیرالاضلاع کی شکل اختیار کرتا ہے۔ تین جہتوں میں یہ ایک ہے۔ پلوٹو ٹھوس، اور اسی طرح.

اس کے بعد لینسٹرا نے تمام انٹیجرز کو گرڈ پوائنٹس کے لامحدود سیٹ کے طور پر تصور کیا، جسے ریاضی میں جالی کے طور پر جانا جاتا ہے۔ ایک دو جہتی ورژن نقطوں کے سمندر کی طرح لگتا ہے، اور تین جہتوں میں یہ ان پوائنٹس کی طرح لگتا ہے جہاں ایک عمارت میں سٹیل کے شہتیر جڑتے ہیں۔ جالی کا طول و عرض بھی کسی مسئلے کے طول و عرض پر منحصر ہے۔

دیے گئے ILP مسئلے کو حل کرنے کے لیے، لینسٹرا نے دکھایا کہ آپ صرف یہ دیکھتے ہیں کہ ممکنہ حل انٹیجرز کے سیٹ سے کہاں ملتے ہیں: محدب جسم اور جالی کے چوراہے پر۔ اور وہ ایک الگورتھم لے کر آیا جو اس جگہ کو مکمل طور پر تلاش کر سکتا تھا — لیکن مؤثر ہونے کے لیے، اسے بعض اوقات مسئلے کو چھوٹے جہتوں کے ٹکڑوں میں توڑنا پڑتا ہے، جس سے رن ٹائم میں کئی مراحل شامل ہوتے ہیں۔

اگلے سالوں میں، کئی محققین نے اس الگورتھم کو تیزی سے چلانے کا طریقہ دریافت کیا۔ 1988 میں، روی کنن اور لاسزلو لواسز نے ایک تصور متعارف کرایا جسے کورنگ ریڈیس کہا جاتا ہے، قرض لیا کے مطالعہ سے غلطی کو درست کرنے والے کوڈز، محدب جسم اور جالیوں کو زیادہ مؤثر طریقے سے آپس میں ملانے میں مدد کرنے کے لئے۔ موٹے طور پر، ڈھکنے کا رداس اس بات کو یقینی بناتا ہے کہ محدب جسم میں ہمیشہ کم از کم ایک عدد عدد ہوتا ہے، چاہے آپ اسے جالی پر کہیں بھی رکھیں۔ نتیجے کے طور پر، احاطہ کرنے والے رداس کا سائز بھی اس بات کا تعین کرتا ہے کہ آپ ILP کے مسئلے کو کتنی مؤثر طریقے سے حل کر سکتے ہیں۔

لہذا یہ سب مثالی کورنگ رداس کے سائز کا تعین کرنے کے لئے نیچے آیا۔ بدقسمتی سے، یہ اپنے طور پر ایک مشکل مسئلہ ثابت ہوا، اور کنن اور لواسز جو سب سے بہتر کام کر سکتے تھے وہ اوپری اور نچلی حدود کو تلاش کرکے ممکنہ قدر کو کم کرنا تھا۔ انہوں نے ظاہر کیا کہ اوپری باؤنڈ - ڈھکنے والے رداس کا زیادہ سے زیادہ سائز - طول و عرض کے ساتھ لکیری طور پر چھوٹا ہوا. یہ کافی تیز تھا، لیکن ILP رن ٹائم کو نمایاں طور پر تیز کرنے کے لیے کافی نہیں تھا۔ اگلے 30 سالوں میں، دوسرے محققین صرف تھوڑا بہتر کر سکتے ہیں.

جس چیز نے بالآخر ریئس اور روتھووس کو توڑنے میں مدد کی وہ ایک غیر متعلقہ ریاضیاتی نتیجہ تھا جو خالصتاً جالیوں پر مرکوز تھا۔ 2016 میں، Oded regev اور Stephens-Davidowitz سے ظاہر ہوا، درحقیقت، ایک مخصوص شکل میں کتنے جالی پوائنٹس فٹ ہو سکتے ہیں۔ Reis اور Rothvoss نے اسے دوسری شکلوں پر لاگو کیا، جس کی وجہ سے وہ ILP کے احاطہ کرنے والے رداس میں موجود جالی پوائنٹس کی تعداد کا بہتر اندازہ لگا سکتے ہیں، اوپری باؤنڈ کو کم کرتے ہیں۔ ریجیو نے کہا، "تازہ ترین پیش رفت اس احساس کے ساتھ ہوئی کہ آپ درحقیقت دوسری قسم کی شکلیں بنا سکتے ہیں۔"

یہ نئی سخت اوپری حد ایک وسیع بہتری تھی، جس سے Reis اور Rothvoss کو مجموعی ILP الگورتھم کی ڈرامائی رفتار حاصل کرنے کا موقع ملا۔ ان کا کام رن ٹائم کو (log n)^O(n)، کہاں n متغیرات کی تعداد ہے اور اے (ن)اس کا مطلب ہے کہ اس کے ساتھ لکیری طور پر ترازو ہوتا ہے۔ n. (اس اظہار کو "تقریباً" بائنری مسئلہ کے رن ٹائم جیسا ہی سمجھا جاتا ہے۔)

"یہ ریاضی، کمپیوٹر سائنس اور جیومیٹری کے سنگم پر ایک فتح ہے،" کہا دانیال دادوش نیدرلینڈز میں قومی تحقیقی ادارے CWI کا، جس نے ILP رن ٹائم کی پیمائش کرنے کے لیے استعمال کیے جانے والے الگورتھم Reis اور Rothvoss کو پیش کرنے میں مدد کی۔

ابھی کے لیے، نیا الگورتھم درحقیقت کسی بھی لاجسٹک مسائل کو حل کرنے کے لیے استعمال نہیں کیا گیا ہے، کیونکہ اسے استعمال کرنے کے لیے آج کے پروگراموں کو اپ ڈیٹ کرنے میں بہت زیادہ کام کرنا پڑے گا۔ لیکن Rothvoss کے لئے، یہ نقطہ کے ساتھ ہے. "یہ ایک ایسے مسئلے کی نظریاتی تفہیم کے بارے میں ہے جس کے بنیادی اطلاقات ہیں،" انہوں نے کہا۔

اس بارے میں کہ آیا ILP کی کمپیوٹیشنل کارکردگی کو مزید بہتر بنایا جا سکتا ہے، محققین اب بھی پر امید ہیں کہ وہ مثالی رن ٹائم تک پہنچتے رہیں گے - لیکن جلد ہی نہیں۔ ویمپالا نے کہا، "اس کے لیے بنیادی طور پر ایک نئے آئیڈیا کی ضرورت ہوگی۔