محلل التحسين عالي المستوى

برنامج HiGHS هو برنامج مفتوح المصدر لحل نماذج البرمجة الخطية (LP) والبرمجة الخطية المختلطة (MIP) والبرمجة التربيعية المحدبة (QP). [ 1 ] [ 2 ]

تُقدّم مكتبة HiGHS، المكتوبة بلغة C++ والمنشورة بموجب ترخيص MIT ، واجهات برمجة للغات C و Python و Julia و Rust و R و JavaScript و Fortran و C# . وهي لا تعتمد على أي مكتبات خارجية.  يتوفر غلاف برمجي بسيط وسهل الاستخدام للغة Python عبر حزمة highspy على PyPI . كما يمكن استدعاء HiGHS عبر NuGet . [ 3 ]

على الرغم من أن برنامج HiGHS يعمل عادةً بخيط معالجة واحد، إلا أن بعض مكوناته قادرة على الاستفادة من معالجات متعددة النوى، ومنذ الإصدار 1.10.0 ، أصبح بإمكانه تشغيل حلّ المعادلات الخطية من الدرجة الأولى على وحدات معالجة الرسومات من NVIDIA. صُمم HiGHS لحلّ النماذج واسعة النطاق، ويستغلّ خاصية تباعد البيانات في المسألة . ويتمّ تقييم أدائه بشكل دوري مقارنةً بالبرامج التجارية وغيرها من البرامج مفتوحة المصدر باستخدام معايير قياس الأداء المعتمدة في هذا المجال . [ 4 ]

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

تاريخ

يعتمد برنامج HiGHS على حلول برمجية طوّرها طلاب دكتوراه من مجموعة التحسين وبحوث العمليات [ 5 ] في كلية الرياضيات بجامعة إدنبرة . وتعود جذوره إلى أواخر عام 2016، عندما جمعت إيفيت غالابوفا بين حلها المسبق للبرمجة الخطية وإجراء جوليان هول لانهيار سيمبلكس وحل هوانغفو تشي الثنائي للسيمبلكس لحل فئة من مسائل البرمجة الخطية الصناعية بسرعة تفوق أفضل الحلول مفتوحة المصدر في ذلك الوقت. [ 6 ] ومنذ ذلك الحين، تم تطوير واجهة برمجة تطبيقات C++ وواجهات لغات أخرى، كما أُضيفت أدوات نمذجة وفئات أخرى من الحلول. 

في أوائل عام 2022، أيدت مشاريع نمذجة أنظمة الطاقة المفتوحة GenX و PyPSA طلب تمويل لحل HiGHS في محاولة لتقليل اعتماد مجتمعها على المكتبات الاحتكارية. [ 7 ]

حلول

سيمبلكس

يحتوي برنامج HiGHS على تطبيقات لطريقة سيمبلكس الأولية والثنائية المعدلة لحل مسائل البرمجة الخطية، استنادًا إلى التقنيات التي وصفها هول وماكينون (2005) [ 8 ] وهوانغفو وهول (2015، 2018) [ 9 ] [ 1 ] . تشمل هذه التقنيات استغلال خاصية التباعد الفائق عند حل الأنظمة الخطية في تطبيقات سيمبلكس، واستغلال خاصية تعدد الخيوط في حل سيمبلكس الثنائي. ويتم الإبلاغ بانتظام عن أداء حل سيمبلكس مقارنةً بالبرامج التجارية وغيرها من البرامج مفتوحة المصدر باستخدام معايير قياسية معتمدة في هذا المجال [ 10 ] .

نقطة داخلية

يحتوي برنامج HiGHS على تطبيق لطريقة النقطة الداخلية لحل مسائل البرمجة الخطية، استنادًا إلى التقنيات التي وصفها شورك وجوندزيو (2020). [ 11 ] ويتميز البرنامج بحل نظام نيوتن تكراريًا باستخدام طريقة التدرج المترافق المُهيأ ، بدلًا من الحل المباشر عبر تحليل LDL* . ويتم بانتظام الإبلاغ عن أداء مُحلِّل النقطة الداخلية مقارنةً بالبرامج التجارية وغيرها من البرامج مفتوحة المصدر باستخدام معايير قياس الأداء المعتمدة في هذا المجال. [ 12 ]

شهد الإصدار 1.12 تقديم تطبيق لطريقة النقطة الداخلية لحل مسائل البرمجة الخطية، استنادًا إلى التقنيات التي وصفها زانيتي وجوندزيو (2025). [ 13 ] تُسمى هذه الميزة الاختيارية HiPO وتعتمد على مكتبة BLAS . [ 14 ]

البرمجة المختلطة للأعداد الصحيحة

يحتوي برنامج HiGHS على خوارزمية حل التفرع والقطع لمسائل البرمجة الخطية المختلطة. ويتم الإبلاغ بانتظام عن أدائه مقارنةً بالبرامج التجارية وغيرها من البرامج مفتوحة المصدر باستخدام معايير قياسية في هذا المجال. [ 15 ]

البرمجة التربيعية

يحتوي برنامج HiGHS على أداة حل مجموعة نشطة لمسائل البرمجة التربيعية المحدبة (QP).

التطبيقات التي تستخدم HiGHS

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

دعم الحوسبة العددية

باعتبارها برمجيات مفتوحة المصدر قوية قيد التطوير المستمر، يتزايد اعتماد برنامج HiGHS في مشاريع البرمجيات التطبيقية التي تدعم التحليل العددي . فعلى سبيل المثال، تستخدم مكتبة SciPy العلمية برنامج HiGHS كحلّ للمسائل الخطية [ 16 ] بدءًا من الإصدار 1.6.0 [ 17 ] ، وحلّ مسائل البرمجة الخطية المختلطة (MIP) في HiGHS للتحسين المتقطع بدءًا من الإصدار 1.9.0 [ 18]. بالإضافة إلى توفير واجهة لبرنامج HiGHS، تصف لغة JuMP للنمذجة الخاصة بلغة Julia [ 19 ] الاستخدام المحدد لبرنامج HiGHS في وثائق المستخدم الخاصة بها [ 20 ] . ويعتمد حلّ مسائل البرمجة الخطية المختلطة (MIP) في مكتبة NAG على برنامج HiGHS [ 21 ] ، كما يُعدّ HiGHS حلّ مسائل البرمجة الخطية (LP) ومسائل البرمجة الخطية المختلطة (MIP) الافتراضي في مجموعة أدوات التحسين من MathWorks [ 22 ] .   

نماذج أنظمة الطاقة المفتوحة

يُستخدم برنامج HiGHS الآن أيضًا في بعض التطبيقات المتخصصة، بما في ذلك بيئة نمذجة أنظمة الطاقة المفتوحة . ويُفعّل الإصدار الإلكتروني من نموذج PyPSA الأوروبي متعدد القطاعات برنامج HiGHS افتراضيًا منذ فبراير 2022. [ 23 ] [ 24 ] كما أضاف مشروع GridCal، الذي يُطوّر برمجيات أنظمة الطاقة البحثية ، دعمًا اختياريًا لبرنامج HiGHS في فبراير  2022. [ 25 ] وفي أوائل عام 2026، أجرت مبادرة التحول في مجال الطاقة المفتوحة بعض الدراسات المعيارية المتخصصة. [ 26 ]

انظر أيضاً

مراجع

  1. 1 2 هوانغفو، كيو؛ هول، جيه إيه جيه (1 مارس 2018). "موازاة طريقة سيمبلكس الثنائية المنقحة" (ملف PDF) . حساب البرمجة الرياضية . 10 (1): 119-142 . doi : 10.1007/s12532-017-0130-5 . ISSN 1867-2957 . S2CID 4641325. تاريخ الاسترجاع: 27 فبراير 2022 .  أيقونة الوصول المفتوح
  2. هول، جوليان (21 سبتمبر 2020). HiGHS: برنامج مفتوح المصدر عالي الأداء للتحسين الخطي (ملف PDF) . إدنبرة، المملكة المتحدة: جامعة إدنبرة . تاريخ الاسترجاع: 27 فبراير 2022 . عرض تقديمي.
  3. "Highs.Native" . تم الاطلاع عليه بتاريخ 13 مايو 2025 .
  4. "معايير أداء برامج التحسين" . شجرة القرار لبرامج التحسين . مارس 2022. تم الاطلاع عليه بتاريخ 31 مارس 2022 .
  5. "التحسين وبحوث العمليات: كلية الرياضيات" . مارس 2022. تم الاطلاع عليه بتاريخ 31 مارس 2022 .
  6. غالابوفا، إيفيت (2022). Presolve، وCrash، وهندسة البرمجيات لـ HiGHS (ملف PDF) (أطروحة دكتوراه). إدنبرة، المملكة المتحدة: جامعة إدنبرة . تاريخ الاسترجاع: 13 مايو 2025 .
  7. بارزن، ماكسيميليان؛ هول، جوليان؛ جينكينز، جيسي؛ براون، توم (31 مارس 2022). حلول التحسين: الحلقة المفقودة لنظام بيئي مفتوح المصدر بالكامل لنمذجة أنظمة الطاقة (ملف PDF) . doi : 10.5281/zenodo.6409432 . تاريخ الاسترجاع: 3 أبريل 2022 . مقترح تمويل من ثماني صفحات يقدم أيضاً خارطة طريق مفصلة نسبياً. أيقونة الوصول المفتوح
  8. هول، جيه إيه جيه؛ ماكينون، كيه آي إم (1 ديسمبر 2005). "التباعد الفائق في طريقة سيمبلكس المُعدّلة وكيفية استغلاله" (ملف PDF) . التحسين الحسابي والتطبيقات . 32 (3): 259-283 . doi : 10.1007/s10589-005-4802-0 . ISSN 1573-2894 . S2CID 15967632. تاريخ الاسترجاع: 1 أبريل 2022 .   ملف PDF المرفق هو نسخة أولية مطبوعة.
  9. هوانغفو، كيو؛ هول، جيه إيه جيه (أبريل 2015). "تقنيات تحديث جديدة لطريقة سيمبلكس المعدلة" (ملف PDF) . التحسين الحسابي والتطبيقات . 60 (3): 587-608 . doi : 10.1007/s10589-014-9689-1 . ISSN 0926-6003 . S2CID 254416722. تاريخ الاسترجاع: 31 مارس 2022 .  
  10. "معيار أداء خوارزميات حل البرمجة الخطية البسيطة" . شجرة القرار لبرامج التحسين . مارس 2022. مؤرشف من الأصل في 11 نوفمبر 2021. تم الاطلاع عليه في 31 مارس 2022 .
  11. شورك، لوكاس؛ غوندزيو، جاك (ديسمبر 2020). "تطبيق طريقة النقطة الداخلية مع تهيئة الأساس" (ملف PDF) . الحوسبة والبرمجة الرياضية . 12 (4): 603-635 . doi : 10.1007/s12532-020-00181-8 . hdl : 20.500.11820/00a692a1-3372-41f6-8baf-f45396efcc0e . ISSN 1867-2949 . S2CID 53444331. تاريخ الاسترجاع: 31 مارس 2022 .  
  12. "معيار أداء خوارزميات حل مسائل البرمجة الخطية ذات الحواجز" . شجرة القرار لبرامج التحسين . مارس 2022. تاريخ الاسترجاع: 31 مارس 2022 .
  13. زانيتي، فيليبو؛ غوندزيو، جاك (2025). "طريقة النقطة الداخلية المنتظمة القائمة على التحليل باستخدام النظام المعزز". arXiv : 2508.04370 [ math.OC ].
  14. مجهول. "وثائق HiGHS" . تم الاطلاع عليه بتاريخ 21 مارس 2026 .
  15. "حالات معيار MIPLIB2017" . شجرة القرار لبرمجيات التحسين . مارس 2022. تم الاطلاع عليه بتاريخ 31 مارس 2022 .
  16. "SciPy — scipy.optimize.linprog" . تحسين SciPy . مارس 2022. تم الاطلاع عليه في 1 أبريل 2022 .
  17. "أبرز ميزات الإصدار 1.6.0 من SciPy" . تحسين SciPy . مارس 2022. تم الاطلاع عليه في 2 أبريل 2022 .
  18. "أبرز ميزات الإصدار 1.9.0 من SciPy" . تحسين SciPy . مايو 2022. تم الاطلاع عليه بتاريخ 5 مايو 2022 .
  19. "JuMP" . JuMP . مارس 2022. تم الاطلاع عليه في 1 أبريل 2022 .
  20. "JuMP — نماذج" . JuMP . مارس 2022. تم الاطلاع عليه في 1 أبريل 2022 .
  21. "دليل مكتبة NAG، الإصدار 29.3" . مجموعة أدوات نمذجة التحسين NAG . يناير 2024. تم الاطلاع عليه بتاريخ 25 مارس 2024 .
  22. "ملاحظات إصدار مجموعة أدوات التحسين" . مجموعة أدوات التحسين من ماث ووركس . مارس 2024. تم الاطلاع عليه بتاريخ 22 مارس 2024 .
  23. براون، توم. "خادم تحسين PyPSA-Eur-Sec" . تم الاسترجاع في 22 يوليو 2022 . واجهة ويب لنموذج PyPsa Eur Sec.
  24. "تحديث GitHub: تبديل المُحلِّل من Gurobi إلى HiGHS" . مشروع خادم PyPSA . 3 فبراير 2022. تم الاطلاع عليه في 22 يوليو 2022 .
  25. "تحديث GitHub: إضافة إعدادات عالية لنظام Linux" . مشروع GridCal . 3 فبراير 2022. تم الاطلاع عليه بتاريخ 24 يوليو 2022 .
  26. مجهول (12 مارس 2026). "معيار الطاقة المفتوحة" . تحول الطاقة المفتوحة . برلين، ألمانيا . تم الاطلاع عليه في 20 مارس 2026 .