حل LP المتقدم

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

يوفّر هذا الدليل مفاهيم جديدة ويوفّر أمثلة لمساعدتك في الحصول على أفضل أداء وموثوقية من أدوات حلّ LP.

المفاهيم

يعرض هذا القسم المفاهيم الأساسية حول الاستخدام المتقدّم لأدوات حل LP. نفترض أنّ القرّاء على دراية بمفهوم الازدواجية في LP.

عائلات خوارزميات LP

يمكن الوصول إلى فئات خوارزميات LP التالية من خلال أدوات OR.

  1. كانت خوارزمية Simplex أول خوارزمية LP العملية ولا تزال الأكثر رواجًا. تمشي الخوارزمية على طول الرؤوس (نقاط الزوايا) للمنطقة الممكنة، وتحسِّن بالتكرار قيمة دالة الهدف حتى تصل إلى الحل الأمثل. هناك نوعان من الخوارزميات البسيطة:

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

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

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

يسرد الجدول أدناه أدوات حلّ LP المتوفّرة في "أدوات OR" ويشير إلى المجموعات الثلاث للخوارزميات التي تم تنفيذها في كل أداة حل.

أداة الحلّ الاتصال العادي حاجز أول طلب
كلاب X X
تكلفة النقرة (CPLEX) X X
Glop X
160,000 X X
GurobiL X X
منع فقدان البياناتG X
XpressL X X

يشير الرمز G إلى أنّ أداة الحلّ هي من طوّرت Google. تشير الحرف L إلى أنّ الحلّ يتطلّب ترخيصًا صادرًا عن المطوّر التابع لجهة خارجية.

اطّلِع على الاقتراحات للحصول على اقتراحات حول أدوات الحلّ والخوارزميات التي يجب استخدامها.

ماذا يعني الحل حقًا؟

للاستفادة إلى أقصى حدّ من أدوات حلّ مشاكل LP إلى أقصى حد، من المهم فهم ما تتضمنه هذه الأدوات عندما تدّعي أداة الحلّ أنّ هذه المشاكل قد توصّلت إلى حل. يتناول هذا القسم الأساسيات اللازمة للإجابة عن هذا السؤال، لا سيما نظرًا لعدم الدقة العددية وعدم تفرد الحلول.

قيم التسامح

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

وضع في الاعتبار مشكلة البرمجة الخطية

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

ومشكلتها المزدوجة المقابلة

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

يحتوي هذا الزوج من المسائل على حل أساسي مثالي فريد يبلغ $ x_1 = 1, x_2 = 0 $ والحلّ الثنائي $ y = -2 $. ما هي الحلول التي يمكن أن تقبلها على أنها مثالية من خلال أداة الحلّ؟ للإجابة عن هذا، نحدد الكميات التالية:

  • فجوة الازدواج هي الفرق بين قيمة الهدف الأساسي والقيمة ثنائية الهدف، وهي في هذه الحالة $ |(-2x_1 - x_2) - y| $.
  • تشمل العجز الأساسي انتهاكات القيود الأساسية، في هذه الحالة، $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
  • العجز الثنائي هي انتهاكات القيود المزدوجة، وهي في هذه الحالة $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

تشير أداة الحلّ إلى أنّ الحلّ هو الأمثل إذا كانت فجوة الازدواجية والعجز الأساسي والعجز الثنائية أصغر من مقدار التسامح المحدّد.1

وعلى وجه التحديد، يتفاوت تطبيق قيم التفاوت المسموح بها لأسباب طبيعية وأخرى غير متزامنة على مستوى أدوات الحلّ والخوارزميات. على سبيل المثال، لا ترتكز فجوة الازدواجية في الخوارزمية البسيطة إلا على عدم الدقة العددية، في حين توجد القصور الأولية والمزدوجة حتى في الحساب الدقيق. بعض الطرق تفرض بشكل مباشر القيود المفروضة $ x_1 \ge 0 وx_2 \ge 0 و$ و$ و$ \le 0 $، بينما تتعامل بعض الطرق الأخرى مع مخالفات القيود الخطية بشكل مختلف عن انتهاكات القيود الخطية، مثل $x_1 + x_2 \le 1$. بالنسبة إلى بعض القيم النسبية للحلّ، تكون قيمة القيم التالية للدالة absolutesolutionss هي قيمة مساوية لثغرة أبجدية أو $silon، حيث تكون قيمة $مَعلمة غير حاصلة على معادلة $silon وهي قيمة مساوية لقيمة المعادلة $silon.

كمثال على تأثير قيم التسامح، ضع في الاعتبار قيمة التسامح المطلق $ \epsilon = \frac{1}{2} $ المطبّقة على الزوج ثنائي النواة أعلاه. الحل $ x_1 = 1.5, x_2 = 0, y = -3 $ به فجوة ازدواجية صفرية وحالات عدم القدرة على الخطأ أقلّ من $ \epsilon $، وبالتالي قد يعلن الحلّ عن هذا الحل "الأمثل". ومع ذلك، تختلف قيمة الهدف (-3) بمقدار 1 عن قيمة الهدف الأمثل الحقيقي وهي -2. تتراوح القيم التلقائية النموذجية لـ $ \epsilon $ بين $10^{-6}$ و $10^{-8}$، ما يجعل هذه الأمثلة الشديدة نادرة ولكن غير مستحيلة.

أنواع الحلول

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

تعرض خوارزميات النظام البسيط دائمًا الرؤوس أو نقاط الزوايا في المنطقة الممكنة. يُفضَّل استخدام هذه الحلول في بعض المواقف لأنها تميل إلى أن تكون أقل ندرة.

لا يكون لطرق الحاجز أو من الدرجة الأولى قم بشكل عام بإرجاع القمم. (تقدّم النظرية أوصافًا إضافية خارج نطاق هذا الدليل).

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

اقتراحات

نقدّم الاقتراحات التالية للاستخدام المتقدّم لأدوات حل LP.

توسيع نطاق بيانات المشكلة

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

من الشائع ظهور الثوابت العددية الصغيرة أو الكبيرة في نماذج LP. في المثال السابق، إذا \(x_1\) و \(x_2\) كانوا يمثّلون نسبة العملاء المُسنَدة إلى "المزوّد 1" أو "المزوّد 2"، وإذا أردنا زيادة الاستفادة إلى أقصى حد من خدمة هؤلاء العملاء، قد نكتب دالة الهدف التالية:

$$ \min -c_1x_1 - c_2x_2 $$

المكان:

  • $ c_1 $ هي الفائدة من تخصيص العملاء للمقدِّم 1
  • $ c_2 $ هي الفائدة من تخصيص العملاء للمقدم 2

سيتم اعتبار القيم المزدوجة التي تستوفي القيود التالية ممكنة باستخدام التسامح المطلق $ \epsilon $:

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $.

إذا كانت وحدتا الفائدة لـ $ c_1 $ و $ c_2 $ عبارة عن قيم كسرية صغيرة تحدث لتكون على نفس مقياس $ \epsilon $، تصبح شروط الاحتمالية المزدوجة ضعيفة إلى حد ما، وبالتالي قد يتم الإعلان عن العنصر الأساسي الذي لا يمثل المستوى الأمثل.

من ناحية أخرى، إذا كانت وحدات الفائدة "مبالغ صغيرة" (1 000 000 ميكرو دولار = 1 دولار)، تتطلب القيم المطلقة الناتجة جدًا والكبيرة جدًا دقة عالية في الحل، وربما تكون عالية بشكل غير معقول وفقًا لحدود أرقام النقاط العائمة. قد يفشل الحلون في التقارب إذا تمت صياغة المشكلة بهذه الطريقة. كجزء من صياغة مشكلة جيدة، يجب على المصممين المتقدمين التفكير في ما إذا كان يتم قياس بيانات المشكلة بطريقة تتوافق مع حدود تقبُّل أداة الحلّ لديهم.

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

للاطّلاع على القيم المسموح بها لتطبيق Glop، يمكنك الاطّلاع على primal_feasibility_tolerance وdual_feasibility_tolerance وsolution_feasibility_tolerance في GlopParameters. يُرجى ملاحظة أنّه يتم استخدام primal_feasibility_tolerance وdual_feasibility_tolerance ضمن الخوارزمية، بينما يتم وضع علامة في المربّع solution_feasibility_tolerance بعد الحل للإبلاغ عن مشاكل رقمية. بالنسبة إلى ميزة PDLP، يُرجى الاطّلاع على eps_optimal_absolute وeps_optimal_relative.

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

اختيار أدوات الحلّ والخوارزميات

نبدأ بمثال يوضح حجم التأثير الناتج عن اختيار أدوات الحلّ والخوارزميات، ثم نقدّم لك دليلاً لاختيار أدوات الحلّ.

التنوع عمليًا

ونوضح التباين في الأداء على مستوى خوارزميات LP وأدوات الحلّ من خلال مقارنة أوقات الحل في مجموعة محدّدة من الحالات التي استخدمها "هان ميتلمان" في أدوات قياس الأداء لأدوات حلّ المشاكل. ويتمّ اختيار الأمثلة صراحةً لإظهار الحدود القصوى للأداء النسبي ولا تمثّل بالضرورة السلوك النموذجي.

تتم مقارنة طريقتي Glop الرئيسية والمزدوجة البسيطة مع طريقة حاجز Gurobi (مع وجود كروس أوفر الذي وصل إلى حل رأسي أو بدونه) وطريقة PDLP، وهي طريقة من الدرجة الأولى، بدقة عالية ومنخفضة. تُحل تقارير الجدول أدناه الوقت بالثواني، بحد أقصى 20 دقيقة (1200 ثانية).

مثال Glop
Primal Simplex		 Glop
Dual Simplex		 Gurobi Barrier
مع كروس أوفر		 Gurobi Barrier
بدون جهاز كروس أوفر		 دقة عالية باستخدام PDLP
 PDLP
بدقة منخفضة
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3rd >1200 252.8 144.6 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 22.6 46.4 32.4
wide15 >1200 20.8 >1200 >1200 916.4 56.3
طاقة البناء 178.4 267.5 12.8 12.3 >1200 157.2
s250r10 12.1 520.6 15.2 16.4 >1200 >1200
إصدار أداة الحلّ OR-أدوات 9.3 OR-أدوات 9.3 Gurobi 9.0 Gurobi 9.0 OR-أدوات 9.3 OR-أدوات 9.3
solver_specific_parameters (القيم التلقائية) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

ومن هذه النتائج، نستنتج ما يلي.

  • يمكن أن يختلف الأداء النسبي للخوارزميات وأدوات الحلّ حسب ترتيب المقدار في مثيل واحد.
  • لا تتوفّر خوارزمية واحدة أو أداة حلّ أفضل بشكل موحّد من غيرها.
  • تعمل ميزة Crossover (يتم تفعيلها تلقائيًا) على زيادة وقت حلّ المشكلة، وفي بعض الأحيان تكون كبيرة.
  • يمكن لتقنية منع فقدان البيانات (PDLP) أن تحل لدقة منخفضة أحيانًا 10 مرات أسرع من الدقة العالية.

دليل موجز لاختيار أدوات حلّ LP

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

  1. جرِّب Glop. السبب: Glop هو تطبيق داخلي من Google للطرق الأولية والمزدوجة. Glop هو برنامج مفتوح المصدر وموثوق به لأعباء الإنتاج في Google.
    • إذا لم تكن الإعدادات التلقائية (الأساسية البسيطة) تعمل بشكل جيد، حاوِل التبديل إلى الاتصال العادي المزدوج باستخدام use_dual_simplex: true.
  2. في حال توفُّر ترخيص، جرِّب أداة حلّ تجارية (CPLEX أو Gurobi أو Xpress). تجربة طرق بسيطة وحواجزية. السبب: أدوات حلّ المشاكل هذه هي المعيار المتّبع في المجال ومحسَّنة للغاية. أيضًا، تكمل طرق الحواجز الخوارزميات البسيطة التي تقدمها Glop.
    • في حال استخدام حاجز، أوقِف "تقاطع" إذا لم تكن بحاجة إلى حل رأسي.
  3. جرِّب ميزة "منع فقدان البيانات". اضبط مقدار تفاوت درجات الحرارة مع تطبيقك. السبب: إنّ ميزة منع فقدان البيانات (PDLP) مصمّمة لحلّ أكبر المشاكل التي تواجهها، حيث تزيد الطرق البسيطة والعوائق من حيث حدود الذاكرة أو تكون بطيئة للغاية. تحقق ميزة PDLP أداءً أفضل عند تفضيل حل تقريبي وسريع على حل دقيق وبطيء.
  4. إذا وصلت إلى هذا الحد، فأنت الآن مستخدم LP متقدم! يرجى الاطّلاع على خيارات الدعم لأداة OR-Tools للحصول على مزيد من المساعدة.

  1. غالبًا ما يكون الأمر أكثر تعقيدًا من ذلك. يتحقّق الحلّون عادةً من هذه الشروط في نسخة مُحوَّلة أو مُبسطة من المسألة، تُسمى المشكلة التي تم حلها. في بعض الحالات، قد يكون حل المشكلة التي تم حلها بعيدًا عن حل مشكلة الإدخال. وقد يؤدي هذا الموقف إلى حالات غير معتادة، مثل حالة CPLEX OptimalInfeas أو IMPRECISE في Glop.↩