Traveling Salesman Problem with a preprocessing method for classical and quantum optimization

إليك ملخص تقني مفصل لورقة البحث بعنوان: "مسألة البائع المتجول باستخدام طريقة معالجة مسبقة للتحسين الكلاسيكي والكمي."

1. تعريف المسألة

تتناول الورقة البحثية مسألة البائع المتجول (TSP)، وهي مسألة تحسين توافقية أساسية من فئة (NP-hard). الهدف هو إيجاد أقل دورة هاميلتونية تكلفة (مسار يزور كل مدينة مرة واحدة بالضبط ويعود إلى نقطة البداية) في رسم بياني كامل $G=(V, A)$.

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

2. المنهجية: تصفية الأقواس القائمة على التكلفة (CAF)

يقترح المؤلفون استراتيجية معالجة مسبقة مبتكرة تسمى تصفية الأقواس القائمة على التكلفة (Cost-Based Arc Filtering - CAF) لتقليل حجم النموذج مع ضمان جدوى الحل.

• المفهوم الجوهري: بدلاً من النظر في جميع الأقواس الممكنة في الرسم البياني الكامل ($|A| = n(n-1)$)، تقوم الطريقة بتقييد مجموعة المرشحين لتشمل $k$ من الجيران ذوي التكلفة الأدنى لكل رأس.
• الأساس النظري: تستند الطريقة إلى مبرهنة ديراك (Dirac's Theorem) من نظرية الرسوم البيانية، والتي تنص على أن الرسم البياني الذي يحتوي على $n$ من الرؤوس يكون "هاميلتونياً" إذا كان الحد الأدنى لدرجة الرأس $\delta(G) \geq n/2$.
• الخوارزمية:
  1. لكل رأس $i$، يتم ترتيب جميع الرؤوس الأخرى $j$ حسب تكلفة السفر المتزايدة $c_{ij}$.
  2. الاحتفاظ فقط بأول $k = \lceil n/2 \rceil$ من الجيران.
  3. إنشاء رسم بياني مختزل $\tilde{G}$ يحتوي فقط على هذه الأقواس المختارة.
• ضمان الجدوى: من خلال ضبط $k = \lceil n/2 \rceil$، أثبت المؤلفون (المبرهنة 1) أن الرسم البياني المختزل يحافظ على حد أدنى من الدرجة كافٍ لضمان وجود دورة هاميلتونية واحدة على الأقل. وبالتالي، تظل المسألة قابلة للحل.
• المنطق الأمثل: بينما لا تضمن الطريقة الحفاظ على الحل الأمثل الأصلي في المجموعة المختزلة، إلا أنها تستفيد من الخصائص الهندسية لنماذج TSP الإقليدية. في مثل هذه المسائل، تتكون الدورات المثلى عادة من اتصالات محلية قصيرة بدلاً من الأقواس طويلة المدى. تعمل تقنية CAF بفعالية على تصفية الاتصالات طويلة المدى وعالية التكلفة، مما يركز فضاء البحث على المناطق الأكثر واعدة.

3. الإعداد التجريبي

تقيم الدراسة منهجية CAF باستخدام أطر التحسين الكلاسيكية والكمية على حد سواء:

• مجموعات البيانات: نماذج معيارية من مكتبة TSPLIB (مشتقة تحديداً من berlin52.tsp)، تتراوح من 5 إلى 50 رأساً.
• المحلل الكلاسيكي: مُحسن Gurobi الإصدار 11.0.1 (صياغة ILP).
• المحلل الكمي: مُحلل Leap CQM Hybrid من D-Wave (النموذج التربيعي المقيد) الذي يعمل على وحدة المعالجة الكمية Advantage2_system1.4 (4596 كيوبت).
• المقاييس: عدد متغيرات القرار، وقت الحساب، فجوة الأمثلية، وجودة الحل.

4. النتائج الرئيسية

أ. التأثير على حجم النموذج

• تقليل المتغيرات: تقلل تقنية CAF عدد متغيرات القرار بنسبة تقارب 30% في المتوسط عبر جميع أحجام النماذج.
• القابلية للتوسع: يصبح هذا التقليل أكثر أهمية مع زيادة عدد الرؤوس ($V$). على سبيل المثال، عند $V=50$، ينخفض عدد المتغيرات من 2,450 (النموذج القياسي) إلى 1,652 (باستخدام CAF).

ب. أداء التحسين الكلاسيكي

• الحفاظ على الأمثلية: بالنسبة للنماذج التي تصل إلى $V=20$، حافظت CAF على القيمة الهدف المثلى (فجوة 0%) مقارنة بالصياغة الكاملة.
• الكفاءة الحسابية: قللت CAF أوقات الحل بشكل كبير.
  • عند $V=18$، انخفض الوقت من ~107 ثانية إلى ~57 ثانية.
  • عند $V=19$، انخفض الوقت من ~257 ثانية إلى ~139 ثانية.
  • عند $V=20$، تم تقليل الوقت بأكثر من النصف (من ~670 ثانية إلى ~316 ثانية).
• النماذج الكبيرة: عند $V=21$، وصل النموذج القياسي إلى حد الـ 300 ثانية دون العثور على حد أدنى صالح، بينما وجد نموذج CAF حلاً صالحاً بقيمة هدف أقل، مما أظهر قدرة فائقة على التتبع.

ج. أداء التحسين الكمي

• القابلية للحل: استطاع المحلل الهجين الكمي حل النماذج حتى $V=15$ بشكل موثوق فقط عند تطبيق CAF. أما النماذج الأكبر فكانت غير قابلة للحل بدون المعالجة المسبقة.
• جودة الحل: حسنت CAF جودة الحلول التي يجدها المحلل الكمي بشكل كبير:
  • فجوة الأمثلية: انخفض متوسط الفجوة بنسبة تقارب 29–31%. على سبيل المثال، عند $V=13$، انخفضت الفجوة من 43% (بدون CAF) إلى 11% (مع CAF).
  • معدل النجاح: عند $V=15$، نجح المحلل في حل 40% من الدورات باستخدام CAF، بينما عانى النموذج غير المصفى بشكل كبير.
• الكفاءة: انخفض متوسط وقت الحل بنسبة تتراوح بين 5–17% تقريباً اعتماداً على حجم النموذج، حيث سمح النموذج المختزل للمحلل بالتقارب بشكل أسرع.

5. المساهمات الرئيسية

1. الضمان النظري: توفر الورقة برهاناً دقيقاً على أن استراتيجية معينة لتصفية الأقواس ($k = \lceil n/2 \rceil$) تحافظ على جدوى مسألة TSP من خلال استيفاء شرط ديراك للرسوم البيانية الهاميلتونية.
2. الربط بين الكلاسيكي والكمي: توضح الورقة كيف يمكن لخطوة معالجة مسبقة بسيطة أن تجعل مسائل TSP قابلة للحل باستخدام الأجهزة الكمية الحالية، مما يتيح حل مسائل ($V=15$) التي تُعتبر عادةً كبيرة جداً على الصياغة الكمية المباشرة.
3. الاختبار على بيانات حقيقية: على عكس العديد من دراسات TSP الكمية التي تستخدم مسائل تجريبية مصطنعة، يستخدم هذا البحث نماذج TSPLIB المعتمدة، مما يوفر تقييماً واقعياً لإمكانات التحسين الكمي.
4. المنفعة المزدوجة: أظهرت الطريقة فائدة لكل من المحللات الكلاسيكية (تقليل الوقت وتحسين القابلية للتوسع) والمحللات الكمية (تمكين أحجام مسائل أكبر وتحسين جودة الحلول).

6. الأهمية

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