الباحثون يقتربون من حدود السرعة الجديدة لحل المشكلة الأساسية | مجلة كوانتا

تعتبر مسألة مندوب المبيعات المتجول واحدة من أقدم الأسئلة الحسابية المعروفة. ويسأل عن الطريق المثالي من خلال قائمة معينة من المدن، مما يقلل من المسافة المقطوعة. على الرغم من أن المشكلة تبدو بسيطة، إلا أنها صعبة للغاية. بينما يمكنك استخدام القوة الغاشمة للتحقق من جميع الطرق الممكنة حتى تجد أقصر طريق، فإن مثل هذه الإستراتيجية تصبح غير قابلة للاستمرار بعد عدد قليل من المدن. بدلاً من ذلك، يمكنك تطبيق نموذج رياضي صارم يسمى البرمجة الخطية، والذي يقارب المشكلة تقريبًا كمجموعة من المعادلات ويتحقق بشكل منهجي من المجموعات المحتملة للعثور على أفضل حل.

لكن في بعض الأحيان، تحتاج إلى تحسين المشكلات التي تتضمن مبالغ أعداد صحيحة. ما فائدة خطة تحسين المصنع التي تصنع 500.7 أريكة؟ ولهذا السبب، غالبًا ما يلجأ الباحثون إلى نوع مختلف من البرمجة الخطية يسمى البرمجة الخطية الصحيحة (آي إل بي). إنها شائعة في التطبيقات التي تتضمن قرارات منفصلة، ​​بما في ذلك تخطيط الإنتاج وجدولة طاقم الطيران وتوجيه المركبات. قال: "في الأساس، يعد ILP بمثابة خبز وزبدة أبحاث العمليات من الناحية النظرية والتطبيقية". سانتوش فيمبالا، عالم كمبيوتر في معهد جورجيا للتكنولوجيا.

منذ أن قاموا بصياغة ILP لأول مرة منذ أكثر من عامين، اكتشف الباحثون خوارزميات مختلفة تحل مشكلات ILP، لكنها كانت جميعها بطيئة نسبيًا من حيث عدد الخطوات المطلوبة. أفضل نسخة يمكن أن يتوصلوا إليها - نوع من حدود السرعة - تأتي من الحالة التافهة حيث يمكن لمتغيرات المشكلة (مثل ما إذا كان البائع يزور مدينة أم لا) أن تفترض فقط قيمًا ثنائية (صفر أو 1). في هذه الحالة، يتمتع ILP بوقت تشغيل يتوسع بشكل كبير مع عدد المتغيرات، والذي يسمى أيضًا البعد. (إذا كان هناك متغير واحد فقط، فإن الأمر يتطلب خطوتين فقط لاختبار كل مجموعة ممكنة وحل المشكلة؛ إذ يعني متغيران أربع خطوات، وثلاثة تعني ثماني خطوات، وهكذا.)

لسوء الحظ، بمجرد أن تأخذ المتغيرات قيمة تتجاوز الصفر والواحد فقط، يصبح وقت تشغيل الخوارزمية أطول بكثير. لقد تساءل الباحثون منذ فترة طويلة عما إذا كان بإمكانهم الاقتراب من المثالية التافهة. وكان التقدم بطيئا، مع سجل تم تعيينه في الثمانينيات وتدريجيًا فقط تحسينات صنع منذ ذلك الحين.

لكن في الآونة الأخيرة العمل by فيكتور ريس، حاليا في معهد الدراسات المتقدمة، و توماس روثفوس، في جامعة واشنطن، بأكبر قفزة في وقت التشغيل منذ عقود. من خلال الجمع بين الأدوات الهندسية للحد من الحلول الممكنة، أنشأوا خوارزمية جديدة وأسرع لحل مشكلة ILP في نفس الوقت تقريبًا مع الحالة الثنائية التافهة. وحصلت النتيجة على جائزة أفضل ورقة في عام 2023 أسس علوم الكمبيوتر مؤتمر.

قال: "هذه الخوارزمية الجديدة مثيرة للغاية". نوح ستيفنز-دافيدويتز، عالم رياضيات وعالم كمبيوتر في جامعة كورنيل. "إنه يمثل أول تحسن [كبير] في حلول ILP منذ ما يقرب من 40 عامًا."

يعمل ILP عن طريق تحويل مشكلة معينة إلى مجموعة من المعادلات الخطية التي يجب أن تلبي بعض المتباينات. تعتمد المعادلات المحددة على تفاصيل المشكلة الأصلية. ولكن على الرغم من أن هذه التفاصيل قد تختلف، إلا أن التركيبة الأساسية لمشاكل ILP تظل كما هي، مما يمنح الباحثين طريقة واحدة لمهاجمة العديد من المشكلات.

هذا لا يعني أنه عمل سهل. لم يكن حتى عام 1983 أن عالم الرياضيات هندريك لينسترا ثبت وأن المشكلة العامة كانت قابلة للحل، مما يوفر أول خوارزمية يمكنها حلها. فكرت لينسترا في ILP هندسيًا. أولاً، قام بتحويل المتباينات الموجودة في قلب ILP إلى شكل محدب، مثل أي مضلع منتظم. يمثل هذا الشكل قيود المشكلة الفردية التي تقوم بحلها، سواء كانت تتعلق بإنتاج الأريكة أو جدولة رحلات الطيران، وبالتالي فإن التصميم الداخلي للشكل يتوافق مع جميع القيم المحتملة التي يمكن أن تحل المتباينات، وبالتالي المشكلة. أطلق لينسترا على هذا الشكل اسم الجسم المحدب. يؤثر بُعد المشكلة على بُعد هذا الشكل: إذ يأخذ بمتغيرين شكل مضلع مسطح؛ في ثلاثة أبعاد هو أ الصلبة الأفلاطونية، وهلم جرا.

تخيل لينسترا بعد ذلك جميع الأعداد الصحيحة كمجموعة لا حصر لها من نقاط الشبكة، المعروفة في الرياضيات بالشبكة. تبدو النسخة ثنائية الأبعاد وكأنها بحر من النقاط، وفي الأبعاد الثلاثة تبدو مثل النقاط التي تتصل بها العوارض الفولاذية في المبنى. يعتمد بُعد الشبكة أيضًا على بُعد مشكلة معينة.

لحل مسألة معينة في ILP، أظهر Lenstra أنك تبحث فقط عن المكان الذي تلتقي فيه الحلول الممكنة بمجموعة الأعداد الصحيحة: عند تقاطع الجسم المحدب والشبكة. وقد توصل إلى خوارزمية يمكنها البحث في هذا الفضاء بشكل شامل، ولكن لكي تكون فعالة، كان عليها في بعض الأحيان تقسيم المشكلة إلى أجزاء ذات أبعاد أصغر، وإضافة العديد من الخطوات إلى وقت التشغيل.

وفي السنوات التالية، اكتشف العديد من الباحثين كيفية جعل هذه الخوارزمية تعمل بشكل أسرع. في عام 1988، قدم رافي كانان ولازلو لوفاسز مفهومًا يسمى نصف قطر التغطية، اقترضت من دراسة رموز تصحيح الأخطاء، لمساعدة الجسم المحدب والشبكة على التقاطع بشكل أكثر كفاءة. بشكل تقريبي، يتأكد نصف قطر التغطية من أن الجسم المحدب يحتوي دائمًا على نقطة عددية واحدة على الأقل، بغض النظر عن مكان وضعه على الشبكة. ونتيجة لذلك، يحدد حجم نصف قطر التغطية أيضًا مدى كفاءة حل مشكلة ILP.

لذلك تم تحديد حجم نصف قطر التغطية المثالي. لسوء الحظ، ثبت أن هذه مشكلة صعبة في حد ذاتها، وأفضل ما يمكن أن يفعله كانان ولوفاسز هو تضييق قيمة محتملة من خلال البحث عن الحدود العليا والسفلى. لقد أظهروا أن الحد الأعلى - الحد الأقصى لحجم نصف قطر التغطية - يتزايد خطيًا مع البعد. كان هذا سريعًا جدًا، ولكنه لم يكن كافيًا لتسريع وقت تشغيل ILP بشكل ملحوظ. وعلى مدار الثلاثين عامًا التالية، لم يتمكن الباحثون الآخرون من تحقيق نتائج أفضل إلا قليلاً.

ما ساعد ريس وروثفوس في نهاية المطاف على تحقيق هذا الهدف كان نتيجة رياضية غير ذات صلة ركزت بشكل كامل على الشبكات. في عام 2016، عوديد ريغيف وستيفينز دافيدويتز أظهرتفي الواقع، كم عدد نقاط الشبكة التي يمكن أن تتناسب مع شكل معين. قام ريس وروثفوس بتطبيق ذلك على أشكال أخرى، مما سمح لهما بتقدير عدد نقاط الشبكة الموجودة في نصف قطر تغطية ILP بشكل أفضل، مما أدى إلى خفض الحد العلوي. وقال ريجيف: "جاء الإنجاز الأخير مع إدراك أنه يمكنك بالفعل عمل أنواع أخرى من الأشكال".

كان هذا الحد الأعلى المشدد الجديد بمثابة تحسن كبير، مما سمح لريس وروثفوس بتحقيق تسريع كبير لخوارزمية ILP الشاملة. عملهم يجلب وقت التشغيل إلى (log n)^O(n)، حيث n هو عدد المتغيرات و O (ن)يعني أنه يقيس خطيًا مع n. (يعتبر هذا التعبير "تقريبًا" نفس وقت تشغيل المشكلة الثنائية.)

وقال "إنه انتصار عند تقاطع الرياضيات وعلوم الكمبيوتر والهندسة". دانيال دادوش من معهد الأبحاث الوطني CWI في هولندا، والذي ساعد في ريادة الخوارزمية التي استخدمها Reis وRothvoss لقياس وقت تشغيل ILP.

في الوقت الحالي، لم يتم استخدام الخوارزمية الجديدة فعليًا لحل أي مشاكل لوجستية، نظرًا لأن الأمر سيستغرق الكثير من العمل لتحديث برامج اليوم للاستفادة منها. ولكن بالنسبة لروثفوس، هذا خارج عن الموضوع. وقال: "إن الأمر يتعلق بالفهم النظري لمشكلة لها تطبيقات أساسية".

أما فيما يتعلق بإمكانية تحسين الكفاءة الحسابية لـ ILP بشكل أكبر، فلا يزال الباحثون يأملون في أن يستمروا في الاقتراب من وقت التشغيل المثالي - ولكن ليس في أي وقت قريب. وقال فيمبالا: "سيتطلب ذلك فكرة جديدة بشكل أساسي".