• تحسين عدد صحيح

تُعرف مسائل التحسين الخطي التي تتطلب أن تكون بعض المتغيّرات كأعداد صحيحة باسم برامج العدد الصحيح المختلطة (MIP).

يمكن أن تنشأ هذه المتغيرات بطريقتين:

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

  • المتغيّرات المنطقية التي تمثّل القرارات ذات القيم 0-1
    كمثال، يمكنك التفكير في مشكلة تتعلّق بإسناد المهام إلى العاملين ( راجِع المهام الدراسية). لإعداد هذا النوع من المسائل، يمكنك تحديد متغيّرات منطقية xi,j تساوي 1 في حال تعيين العامل i للمهمة j، و0 في الحالات الأخرى.

وللحصول على معلومات تمهيدية جيدة حول تحسين الأعداد الصحيحة، ننصحك بالاطّلاع على دليل إعداد نماذج Mosek.

الأدوات

توفّر Google بضع طرق لحل مشاكل MIP:

  • MPSolver: برنامج تضمين للعديد من حلول MIP التابعة لجهات خارجية التي تستخدم أساليب معيارية تعتمد على تفريع الفرع (MIP) وترابطه.
  • أداة حلّ CP-SAT: هي أداة لبرمجة القيود تستخدم طُرق تقييم SAT (مدى الرضا).
  • أداة حلّ مشكلة CP الأصلية: هي أداة لبرمجة القيود.

أيّ أداة حلّ عليّ استخدامها؟

ما مِن قاعدة ثابتة لتحديد ما إذا كان يجب استخدام أداة حلّ MIP أو أداة حلّ CP-SAT. كدليل تقريبي:

  • تعتبر أدوات حلّ MIP أكثر ملاءمةً للمسائل التي يمكن إعدادها كتنسيق LP عادي، ولكن مع متغيّرات عشوائية للأعداد الصحيحة، كما في المثال الأول أعلاه.
  • تعد أداة حل CP-SAT أكثر ملاءمة للمشكلات التي تكون فيها معظم المتغيرات منطقية، مثل المثال الثاني أعلاه.

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

للحصول على أمثلة تستخدم كلاً من أدوات حلّ MIP وCP-SAT، يمكنك مراجعة حل مسألة مهمة وأقسام المهام الأخرى.

هناك طريقة أخرى لحل مشاكل برمجة الأعداد الصحيحة وهي استخدام أداة حلّ تدفق الشبكة.
راجع التعيين كمشكلة الحد الأدنى للتكلفة للحصول على مثال.
بالنسبة إلى أي مشكلة يمكن إعدادها كتدفق شبكة، يمكن أن تكون أداة حلّ الحد الأدنى للتكلفة أسرع من أدوات حلّ MIP أو CP-SAT. ومع ذلك، لا يمكن إعداد جميع MIP بهذه الطريقة.