الانتقال إلى المحتوى
العودة إلى نتائج البحث

البرمجة الصحيحة المختلطة — التحسين الدقيق للقرارات المستمرة والصحيحة

قدّمه
Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
السنة
1958–1960
النوع
Mathematical optimization
العائلة
Simulation / optimization

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

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

الفكرة الحدسية وراء الطريقة

تتضمن العديد من مشاكل التحسين الواقعية قرارات لا يمكن تقسيمها — إما أن تفتح منشأة أو لا تفتحها، أو تعين عاملًا واحدًا بالضبط لنوبة عمل، أو تطلب وحدات كاملة. تتجاهل البرمجة الخطية المستمرة هذه الحقائق ويمكن أن تنتج إجابات جزئية غير قابلة للتنفيذ. تفرض البرمجة الصحيحة المختلطة التكامل مباشرة في النموذج. يستكشف الحل مساحة الحلول الصحيحة الممكنة بشكل منهجي عبر التفرع والحد (branch-and-bound): يحل المشاكل الفرعية المستمرة المسترخية (relaxed continuous subproblems) لتحديد حد أفضل حل ممكن في كل منطقة، ويتخلص من المناطق التي لا يمكن أن تحسن الحل الصحيح الأفضل الذي تم العثور عليه حتى الآن، ويضيف مستويات القطع (cutting planes) لشد البحث. النتيجة هي خطة مثلى مثبتة أو شبه مثلى.

التاريخ

تم وضع الأسس للبرمجة الصحيحة بواسطة رالف جوموري، الذي قدم طريقة مستويات القطع في عام 1958، و بواسطة لاند ودويج، اللذين وضعا إطار التفرع والحد في عام 1960. شهدت العقود اللاحقة تطوير نظرية الاسترخاء الخطي، والتركيبات متعددة السطوح (polyhedral combinatorics) (Edmonds, Padberg, Grötschel)، وبحلول التسعينيات أصبحت البرمجة الصحيحة المختلطة واسعة النطاق عملية بفضل الحلول التجارية. تم تناول المجال بشكل شامل في Nemhauser and Wolsey (1988) و Wolsey (1998).

متى تُستخدم

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

الحدود والاعتبارات

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

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • ينتج حلولًا مثلى مثبتة مع فجوة مثلى قابلة للقياس، مما يتيح تبريرًا صارمًا للقرارات.
  • يتعامل مع المتغيرات الثنائية والصحيحة العامة بشكل أصلي، مما يلتقط قيود عدم القابلية للتجزئة والقيود المنطقية في العالم الواقعي.
  • تستغل الحلول الحديثة (Gurobi, CPLEX, SCIP) تقنيات التفرع والحد المتقدمة، ومستويات القطع، والمعالجة المسبقة للتعامل مع الحالات الكبيرة بكفاءة.
  • صياغة النموذج الشفافة تجعل الافتراضات واضحة وقابلة للتدقيق من قبل خبراء المجال.
  • يدعم تحليل الحساسية والدراسات البارامترية لفهم كيفية تغير الحلول مع بيانات الإدخال.
  • مدعوم على نطاق واسع بلغات النمذجة (AMPL, GAMS, Pyomo, JuMP) مما يتيح النمذجة السريعة.

التطبيقات

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

كيف يعمل

كيف يعمل

1

تحديد نموذج التحسين: دالة هدف (مزيج خطي من متغيرات القرار لتقليلها أو تعظيمها)، وقيود عدم المساواة والمساواة الخطية، ومتطلبات التكامل. تتعامل المتغيرات المستمرة مع الكميات التي يمكن أن تكون جزئية؛ والمتغيرات الثنائية (0/1) أو الصحيحة العامة تتعامل مع القرارات المنفصلة.

الصيغة
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^p
2

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

الصيغة
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0
3

اختيار متغير صحيح جزئي من حل الاسترخاء الخطي. إنشاء مشكلتين فرعيتين عن طريق إضافة قيد أرضية (floor constraint) في إحداهما وقيد سقف (ceiling constraint) في الأخرى، وتقسيم المساحة الممكنة دون فقدان أي نقطة ممكنة صحيحة.

الصيغة
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceil
4

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

الصيغة
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}
5

اختياريًا، إضافة مستويات قطع (cutting planes) — متباينات صالحة تقطع حل الاسترخاء الخطي الجزئي دون إزالة أي نقطة ممكنة صحيحة. مستويات قطع Gomory هي النهج الكلاسيكي؛ يمكن لمستويات القطع الخاصة بالمشكلة (مثل مستويات القطع للفئة clique cuts، مستويات القطع للتدفق flow cuts) أن تقلل حجم الشجرة بشكل كبير.

الصيغة
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}
6

التوقف عندما يتم استكشاف شجرة التفرع والحد بالكامل أو عندما تقع الفجوة بين أفضل حل صحيح والحد الأدنى العام ضمن تفاوت محدد من قبل المستخدم (مثل 0.01%). إرجاع الحل المحتضن مع شهادة المثلى الخاصة به.

الصيغة
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilon

الأخطاء الشائعة

  • اختيار تفاوت فجوة مثلى ضيق جدًا يمكن أن يجعل الحل يعمل إلى أجل غير مسمى؛ قم دائمًا بتعيين فجوة عملية (مثل 1%) للحالات الكبيرة.
  • التناظر في النموذج (مثل المنشآت القابلة للتبديل) ينشئ فروعًا مكررة ويزيد حجم شجرة البحث — استخدم قيود كسر التناظر (symmetry-breaking constraints).
  • الاسترخاءات الخطية الضعيفة (فجوة تكامل كبيرة) تؤدي إلى أشجار تفرع وحد كبيرة جدًا؛ استثمر الوقت في إضافة متباينات صالحة أو تشديد الصياغة.
  • معاملة جميع المتغيرات كمتغيرات صحيحة عندما يحتاج البعض فقط إلى ذلك هو أمر مكلف بشكل غير ضروري؛ استخدم المتغيرات الثنائية فقط حيث تتطلب القيود المنطقية ذلك.
  • تجاهل البدء الدافئ (warm-starting) بحل ممكن أولي جيد يهدر وقت الحل في العثور على المحتضن الأول.

الأسئلة الشائعة

كيف تختلف البرمجة الصحيحة المختلطة عن البرمجة الخطية (LP)؟

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

متى يجب أن أستخدم استدلالًا (heuristic) بدلاً من البرمجة الصحيحة المختلطة؟

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

ما هي فجوة المثلى وكيف يجب أن تكون صغيرة؟

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

هل يمكن للبرمجة الصحيحة المختلطة التعامل مع أهداف أو قيود غير خطية؟

تفترض البرمجة الصحيحة المختلطة القياسية الخطية. يجب خطية العلاقات غير الخطية (مثل التقريب الخطي القطعي، التوسع الثنائي للمنتجات) أو التعامل معها بواسطة حلول البرمجة غير الخطية الصحيحة المختلطة (MINLP)، والتي يصعب حلها بشكل كبير.

ما هي الحلول الموصى بها للبرمجة الصحيحة المختلطة؟

تجارية: Gurobi و CPLEX هي المعايير الصناعية. مفتوحة المصدر: SCIP و CBC (عبر COIN-OR) و HiGHS تنافسية للمشاكل متوسطة الحجم. كلها تدعم واجهات النمذجة القياسية مثل AMPL و Pyomo و JuMP.

طرق ذات صلة

المصادر

  1. Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.

    ردمك: 9780471359432
    تم النسخ.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ردمك: 9780471283669
    تم النسخ.