البرمجة الخطية المختلطة الصحيحة (MILP)

البرمجة الخطية المختلطة الصحيحة (MILP) هي صنف المسائل min c^T x + d^T y s.t. Ax + By ≤ b, x ≥ 0, y ∈ Z^p_+ في الصورة القياسية، حيث x ∈ R^n متغيرات متصلة و y ∈ Z^p متغيرات صحيحة. شرط الصحة غالباً ثنائي y ∈ {0,1}^p ويصوغ قرارات منطقية (الاستثمار/عدمه، تشغيل/إيقاف آلة، استخدام/عدم استخدام مسار، إسناد منتج-مورد-فترة). التكاليف الثابتة، الدفعات المنفصلة، الفصلية وصياغات big-M تستلزم متغيرات صحيحة. التعقيد: MILP صنف NP-صعب (Cook 1971 عبر الاختزال من SAT؛ كثير من مسائل Karp 1972 الـ 21 NP-كاملة يمكن صياغتها MILP)؛ يكون استرخاء LP (بإلغاء الصحة واستبدالها بـ y ≥ 0) متعدد الحدود ويعطي حداً أدنى في التصغير. الخوارزمية الكلاسيكية هي branch-and-bound لـ Land و Doig (1960) — حل استرخاء LP، التفريع على y_i كسري، تشذيب الأشجار الفرعية ذات الحد الأسوأ. أدخل Gomory (1958) القطوع الكسرية، ووسع Padberg و Rinaldi (1991) إطار branch-and-cut؛ تجمع الحلول الحديثة بين مستويات القطع (Gomory و lift-and-project و MIR و cover)، المعالجة المسبقة للعقدة، الإرشاديات الأولية (feasibility pump و RINS)، تحليل التعارض و branch-and-bound المتوازي. تشمل نماذج MILP اختيار المواقع (Fixed Charge Facility Location)، توجيه المركبات، جدولة الإنتاج، الإسناد، التغليف، تصميم الشبكات، اختيار المحفظة (قيود الكاردينالية) و unit commitment للطاقة.