On the facet pivot simplex method for linear programming

ملخص تقني: حول طريقة الارتكاز على الأوجه (Facet Pivot) للبرمجة الخطية

بيان المشكلة
تتناول الورقة البحثية الكفاءة الحسابية والقيود النظرية لطريقة "السمبلكس" القياسية ذات الارتكاز عند الرؤوس (Vertex Pivot) لحل مسائل البرمجة الخطية (LP). وبينما تظل طريقة "دانتزيغ" للرؤوس فعالة للغاية في الممارسة العملية، إلا أنها تفتقر إلى حد زمني مثبت من الدرجة متعددة الحدود (Polynomial-time). نظرياً، تتضمن السيناريوهات الأسوأ لطرق الرؤوس عدداً أسياً من التكرارات (كما هو موضح في مكعبات "كلي-مينتي")، وظل البحث عن خوارزمية ارتكاز ذات زمن متعدد الحدود أمراً مستعصياً لعقود. علاوة على ذلك، غالباً ما تتطلب طرق الرؤوس التقليدية عملية "المرحلة الأولى" (Phase I) المكلفة حاسوبياً لإيجاد حل أساسي أولي قابل للتحقق، لا سيما لمسائل البرمجة الخطية العامة التي تتضمن قيود عدم التساوي والقيود المحددة.

المنهجية
يقترح المؤلفون طريقة ارتكاز على الأوجه (Facet Pivot Simplex Method) تُحدث تحولاً جوهرياً في عملية الارتكاز من الرؤوس إلى الأوجه (القيود).

• الصياغة العامة: تعمل الطريقة على صياغة عامة للبرمجة الخطية:
  $$\min c^T x$$
  $$\text{subject to } A_I x = b_I, \quad A_J x \ge b_J, \quad \ell \le x \le u$$
  وعلى عكس الصيغ القياسية التي تحول متباينات عدم التساوي إلى معادلات عبر متغيرات "الارتخاء" (Slack variables)، يتعامل هذا النهج مع قيود عدم التساوي مباشرة كأوجه (Facets) للمتعدد السطوح الممكن (Feasible Polytope).

• المنطق الخوارزمي:

  • تعريف الأساس (Basis): بدلاً من أساس للمتغيرات (الرؤوس)، تحافظ الخوارزمية على أساس من $d$ من الأوجه (القيود) المستقلة خطياً، حيث $d$ هو بُعد المسألة.
  • العملية التكرارية: تبدأ الخوارزمية بحل أساسي أولي (غالباً ما يتم اشتقاقه مباشرة من قيود الحدود) والذي ليس بالضرورة أن يكون حلاً ممكناً. في كل تكرار، تختار الخوارزمية وجهاً داخلاً (قيد غير أساسي) ووجهاً خارجاً (قيد أساسي) لتحديث الأساس.
  • الإمكانية والتحسين الأمثل (Feasibility and Optimality): تحافظ الخوارزمية على تمثيل لمتجه الهدف $c$ كتركيبة خطية غير سالبة من الأوجه الأساسية الحالية (استناداً إلى شرط مشتق من "لمة فاركاس" - Farkas' Lemma). وهي تعمل بشكل تكراري على تحسين الحل عبر استبدال الأوجه لتقليل انتهاكات القيود.
  • التقارب (Termination): تتوقف العملية عند إيجاد حل أساسي ممكن. ووفقاً لنظريات التحسين المعروضة، إذا كان يمكن التعبير عن متجه الهدف كتركيبة غير سالبة من الأوجه الأساسية النشطة عند نقطة ممكنة، فإن تلك النقطة تكون مثلى.
  • التقارب النهائي: تثبت الورقة أنه إذا طُبقت "قاعدة أدنى/أقل مؤشر" (Least/Lowest Index Rule) لاختيار الأوجه الداخلة والخارجة، فإن الخوارطية تتجنب الدوران (Cycling) وتصل إلى نهاية في عدد محدد من الخطوات.

• التمييز الجوهري عن السمبلكس المزدوج (Dual Simplex): بينما تشترك طريقة الارتكاز على الأوجه في بعض السمات الهندسية مع طريقة السمبلكس المزدوج (الانتقال بين أسس القيود)، إلا أنها تختلف لأنها تعمل حصرياً على المسألة الأصلية (Primal) دون بناء أو حل مسألة مزدوجة (Dual) بشكل صريح. كما أنها تتعامل مع الصيغة العامة مباشرة، متجنبة التحويل إلى الصيغة القياسية.

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

1. الاقتراح الخوارزمي: تقدم الورقة خوارزمية محددة للارتكاز على الأوجه (الخوارزمية 4.1) تحل مسائل البرمجة الخطية العامة دون الحاجة إلى خطوة تهيئة "المرحلة الأولى".
2. الضمانات النظرية: يقدم المؤلفون براهين رياضية (بناءً على لمة فاركاس) تثبت أن الخوارزمية تجد حلاً أمثلاً في تكرارات منتهية، وتحدد بدقة المسائل غير الممكنة أو غير المحدودة.
3. التنفيذ: تم توفير تنفيذ بلغة MATLAB للخوارزمية، إلى جانب تنفيذات لطريقة "دانتزيغ" وطريقة "السمبلكس المزدوج" وطرق "نقطة الداخل" (Interior-Point Methods) للمقارنة.
4. التعامل مع القيود: تتعامل الطريقة بشكل طبيعي مع الحدود الدنيا والعليا والمتغيرات الحرة دون إدخال متغيرات ارتخاء اصطناعية، مما يؤدي إلى حجم مسألة أصغر مقار بتحويلات الصيغة القياسية.

النتائج التجريبية
أجرى المؤلفون اختبارات عددية على عدة مجموعات مرجعية:

• اختبارات Netlib: في مسائل Netlib القياسية ذات الحدود الدنيا والعليا، تطلبت طريقة الارتكاز على الأوجه عموماً وقتاً أقل من حيث ثواني المعالج (CPU seconds) مقار بأكثر قواعد "دانتزيغ" للارتكاز السلبية مقارنة بـ "دانتزيغ". وقد نجحت في حل المسائل التي فشلت فيها طريقة السمبلكس المزدوج بسبب نقص الرتبة (Rank Deficiency) أو سوء التكييف (Ill-conditioning).
• المسائل واسعة النطاق: بالنسبة للمسائل الكبيرة جداً (مثل $n > 50,000$)، تفوقت طرق "نقطة الداخل" (IPM) على جميع طرق الارتكاز، كما هو متوقع. ومع ذلك، أظهرت طريقة الارتكاز على الأوجه متانة حيث فشلت طريقة السمبلكس المزدوج.
• مكعبات كلي-مينتي (Klee-Minty Cubes): أظهرت طريقة الارتكاز على الأوجه أداءً أفضل بكثير من طريقة الرؤوس لـ "دانتزيغ" في متغيرات "كلي-مينتي"، حيث تطلبت عدداً أقل بكثير من التكرارات (غالباً ما يكون خطياً أو قريباً من الخطية في البعد $d$) مقارنة بالتكرارات الأسية التي تتطلبها طريقة الرؤوس.
• المسائل العامة العشوائية: بالنسبة لمسائل البرمجة الخطية العامة التي تتطلب "المرحلة الأولى" في الطرق القياسية، كانت طريقة الارتك_العلى الأوجه أكثر كفاءة بشكل ملحوظ من طريقة "دانتزيغ" لأنها تجاوزت مرحلة تهيئة "المرحلة الأولى".
• المسائل العشوائية القياسية: بالنسبة لمسائل البرمجة الخطية القياسية التي لا تتطلب "المرحلة الأولى"، لوحظ أن طريقة "دانتزيغ" كانت أكثر كفاءة قليلاً من حيث وقت المعالج، رغم أن عدد التكرارات كان متقارباً.

الأهمية والادعاءات
تدعي الورقة أن طريقة الارتكاز على الأوجه تقدم بديلاً واعداً للطرق القائمة على الرؤوس، لا سيما لمسائل البرمة الخطية العامة ذات قيود عدم التساوي. وتكمن أهميتها الأساسية في:

• إلغاء المرحلة الأولى: من خلال البدء بحل أساسي مشتق من قيود الحدود، تتجنب الطريقة مرحلة التهيئة المكلفة المطلوبة لطرق السمبلكس التقليدية للمسائل العامة.
• المتانة: أظهرت استقراراً عددياً أكبر من طريقة السمبلكس المزدوج في مسائل Netlib ذات التكييف الضعيف.
• الأمل في التعقيد متعدد الحدود: بينما لا يدعي المؤلفون أنهم أثبتوا حداً زمنياً متعدد الحدود، إلا أنهم يشيرون إلى أن هذا النوع الجديد من خوارزميات الارتكاز (الذي يعمل على الأوجه بدلاً من الرؤوس) يوفر مساراً جديداً للبحث نحو إيجاد طريقة سمبلكس ذات زمن متعدد الحدود، مما يعالج المسألة التاسعة من مسائل "سميل" (Smale's 9th problem).
• الكفاءة العملية: ثبت أن الطريقة تنافسية للغاية وغالباً ما تكون متفوقة على طريقة "دانتزيغ" في المسائل التي تتضمن العديد من قيود عدم التساوي، دون عبء تحويلها إلى معادلات.

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