MPS (تنسيق)

MPS (نظام البرمجة الرياضية) هو تنسيق ملف لعرض وأرشفة مسائل البرمجة الخطية (LP) ومسائل البرمجة الخطية المختلطة .

سُمّي هذا التنسيق نسبةً إلى أحد منتجات البرمجة الخطية المبكرة من شركة IBM ^{[ 1 ]} ، وقد أصبح معيارًا فعليًا لوسيط ASCII بين معظم برامج حل البرمجة الخطية التجارية. تقبل جميع برامج حل البرمجة الخطية التجارية تقريبًا هذا التنسيق، كما يقبله نظام COIN-OR مفتوح المصدر . قد تتطلب برامج أخرى روتين قراءة مخصصًا لقراءة ملفات MPS. مع ذلك، ومع انتشار لغات النمذجة الجبرية، انخفض استخدام MPS. على سبيل المثال، وفقًا لإحصائيات خادم NEOS في يناير 2011، كانت أقل من 1% من الملفات المُرسلة بتنسيق MPS، مقارنةً بـ 59.4% من ملفات AMPL و29.7% من ملفات GAMS .

تعتمد صيغة MPS على نظام الأعمدة (بدلاً من إدخال النموذج كمعادلات)، وتُسمى جميع مكونات النموذج (المتغيرات، الصفوف، إلخ). ونظرًا لأنها صيغة قديمة، فهي مُصممة للعمل مع البطاقات المثقبة: تبدأ الحقول من الأعمدة 2، 5، 15، 25، 40، و50. تُحدد أقسام ملف MPS ببطاقات رأسية، والتي تبدأ من العمود 1. على الرغم من شيوع استخدام الأحرف الكبيرة في جميع أنحاء الملف لأسباب تاريخية، إلا أن العديد من برامج قراءة MPS تقبل الأحرف الكبيرة والصغيرة معًا في جميع أجزاء الملف باستثناء البطاقات الرأسية، وبعضها يسمح باستخدامها في أي مكان. لا تُعدّ الأسماء التي تختارها للكيانات الفردية (القيود أو المتغيرات) مهمةً للمُحلِّل؛ يُنصح باختيار أسماء ذات دلالة، أو أسماء يسهل على برنامج المعالجة اللاحقة قراءتها.

إليكم نموذجًا صغيرًا مكتوبًا بصيغة MPS (موضح بمزيد من التفصيل أدناه):

اسم مسبار الاختبار صفوف التكلفة N L LIM1 G LIM2 إي ماي إي كيو إن الأعمدة تكلفة إكس ون 1 ليم1 1 XONE LIM2 1 تكلفة YTWO 4 LIM1 1 YTWO MYEQN -1 تكلفة ZTHREE 9 LIM2 1 ZTHREE MYEQN 1 الجانب الأيمن RHS1 LIM1 5 LIM2 10 RHS1 MYEQN 7 حدود UP BND1 XONE 4 LO BND1 YTWO -1 UP BND1 YTWO 1 بيانات نهاية

للمقارنة، إليك نفس النموذج مكتوبًا بصيغة معادلة:

تحسين التكلفة: XONE + 4*YTWO + 9*ZTHREE رهناً بـ LIM1: XONE + YTWO <= 5 LIM2: XONE + ZTHREE >= 10 MYEQN: - YTWO + ZTHREE = 7 الحدود XONE <= 4 -1 <= YTWO <= 1 نهاية

كما ذُكر أدناه، فإن الحد الأدنى لـ XONE إما صفر أو سالب ما لا نهاية، وذلك حسب التطبيق، لأنه غير مُحدد. ومن الغريب أن تنسيق MPS لا يُحدد اتجاه التحسين، ولا يوجد اتجاه "افتراضي" قياسي؛ فبعض برامج حل البرمجة الخطية تُعظم القيمة إذا لم يُطلب منها خلاف ذلك، بينما تُصغرها برامج أخرى، ^{[ 2 ]} وبعضها الآخر يُعطي الأولوية للسلامة ولا يوجد اتجاه افتراضي، ويتطلب تحديدًا في برنامج تحكم أو عبر مُعامل استدعاء. إذا صُمم النموذج للتصغير، وكان برنامج الحل يتطلب التعظيم (أو العكس)، فمن السهل التحويل بين الحالتين عن طريق عكس جميع معاملات دالة الهدف. ستكون القيمة المُثلى لدالة الهدف حينها هي القيمة السالبة للقيمة المُثلى الأصلية، لكن قيم المتغيرات نفسها ستكون صحيحة. تدعم بعض البرامج تحديد التصغير/التعظيم داخل ملف MPS.

OBJSENSE الأعلى

يبدأ قسم الاسم بكلمة الاسم في الأعمدة من 1 إلى 4 وعنوان المشكلة في الأعمدة من 15 إلى 21. ^{[ 3 ]}

يُحدد قسم OBJSENSE الاختياري ما إذا كانت مسألة البرمجة الخطية مسألة تعظيم أو تصغير. يُعد هذا القسم مفيدًا بشكل خاص عندما لا يكون السلوك الافتراضي (التصغير) مرغوبًا فيه. ^{[ 4 ]}

يُحدد قسم الصفوف أسماء جميع القيود؛ حيث تُمثل القيم في العمودين 2 أو 3 الصفوف التي تُساوي (=)، والصفوف التي تُساوي (<=)، والصفوف التي تُساوي (>=)، والصفوف التي تُساوي (>=)، والصفوف التي لا تُقيد. ولا يُشترط ترتيب الصفوف المُسماة في هذا القسم، باستثناء الصفوف التي لا تُقيد والمُشار إليها بالحرف N، حيث يُفسر أول صف منها على أنه دالة الهدف.

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

يُتيح قسم الجانب الأيمن تعريف متجه واحد أو أكثر في الجانب الأيمن؛ ونادرًا ما يزيد عن متجه واحد. في المثال أعلاه، اسم متجه الجانب الأيمن هو RHS1، وله قيم غير صفرية في جميع صفوف القيود الثلاثة للمسألة. أما الصفوف التي لم يُذكر فيها متجه في الجانب الأيمن، فيُفترض أن يكون جانبها الأيمن صفرًا.

تحدد خاصية RANGES الاختيارية متباينات مزدوجة للحدود الدنيا والعليا للصفوف. ^{[ 3 ]}

يُحدد قسم BOUNDS الاختياري الحدود الدنيا والعليا للمتغيرات الفردية. تُحدد الأعمدة الأولى (2-3 أعمدة) نوع الحد. من بين الحدود الشائعة: UP، LO، FX، FR، MI، وPI. يُشير الحد من النوع UP إلى تطبيق حد أعلى على المتغير، بينما يُشير الحد من النوع LO إلى تطبيق حد أدنى. أما الحد من النوع FX ("ثابت") فيعني أن للمتغير حدين أعلى وأدنى يساويان قيمة واحدة. بينما يُشير الحد من النوع FR ("حر") إلى أن المتغير ليس له حدود دنيا أو عليا، وبالتالي يمكن أن يأخذ قيمًا سالبة. وهناك نوع آخر هو MI، وهو اختصار لـ "سالب حر"، حيث يُعطي حدًا أعلى يساوي صفرًا دون حد أدنى. أما الحد من النوع PL فهو مخصص للقيم الموجبة الحرة من الصفر إلى ما لا نهاية، ولكن نظرًا لكونه الإعداد الافتراضي، فنادرًا ما يُستخدم. بالإضافة إلى ذلك، توجد في بعض تعديلات تنسيق ملف mps أنواع حدود مُخصصة للاستخدام في نماذج MIP . مثل BV للثنائي، حيث تكون قيمته 0 أو 1. وUI للأعداد الصحيحة العليا وLI للأعداد الصحيحة الدنيا. يشير SC إلى شبه متصل، ويدل على أن المتغير قد يكون صفرًا، ولكن إن لم يكن كذلك، فيجب أن يساوي على الأقل القيمة المعطاة. تُعتبر المتغيرات غير المذكورة في مجموعة الحدود المعطاة غير سالبة (الحد الأدنى صفر، ولا يوجد حد أعلى). بعد ذلك، يكون عنوان الصف في الأعمدة من 5 إلى 12، متبوعًا بعنوان العمود في الأعمدة من 14 إلى 22. مع قيمة الحد في الأعمدة من 25 إلى 36. ^{[ 4 ]}

لا تُعالج بعض الحالات الخاصة من معيار MPS بشكلٍ متسق في التطبيقات. ففي قسم الحدود (BOUNDS)، إذا حُدد لمتغير حدٌ أعلى غير موجب دون حدٍ أدنى، فقد يكون حده الأدنى صفرًا أو سالب ما لا نهاية (كذلك، إذا حُدد الحد الأعلى بصفر، فقد يكون الحد الأدنى صفرًا أو سالب ما لا نهاية). ^{[ 5 ]} وإذا لم يُحدد حدٌ أعلى لمتغير صحيح، فقد يكون حده الأعلى واحدًا بدلًا من موجب ما لا نهاية.

بدلاً من ذلك، تسمح بعض برامج حل المعادلات متعددة النقاط (MPS) بإضافة فئات أخرى لتعزيز وظائفها، مثل علامات التكامل لتمييز المتغيرات الصحيحة باستخدام الكلمات المفتاحية 'MARKER' و'INTORG' و'Marker' و'INTEND' ^{[ 4 ]} أو قسم آخر مثل INTEGER. بالإضافة إلى العديد من الفئات المخصصة الأخرى لبرامج الحل المختلفة. ^{[ 4 ]}

يشير قسم ENDATA إلى نهاية مسألة البرمجة الخطية. يجب أن يكون هذا القسم موجودًا.

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

تتضمن العديد من منتجات البرمجة الخطية امتدادات لتنسيق MPS. يسمح تنسيق MPS المجاني بأسماء طويلة وبيانات أكثر دقة من خلال السماح للحقول بتجاوز عدد الأعمدة المحدد في المعيار الأصلي، واستخدام المسافات البيضاء كفواصل بدلاً من تحديد مواضع الأعمدة (مع ملاحظة أن هذا يجعل بعض ملفات MPS التي كانت تتضمن مسافات بيضاء كجزء من الأسماء غير صالحة). تتضمن بعض الامتدادات إضافة أنواع جديدة من البيانات إلى ملف MPS (مثل أقسام لتضمين المعنى الموضوعي، ومتطلبات التكامل، والبيانات التربيعية، أو بنى نمذجة MIP المتقدمة). يوجد أيضًا تنسيق ملف MPSC مضغوط. ^{[ 6 ]} يُعد SMPS ^{[ 7 ]} امتدادًا متخصصًا، مصممًا لتمثيل حالات مسائل البرمجة العشوائية ، ويُستخدم بشكل خاص في بيئات البحث.

على الرغم من أن بعض الامتدادات غير موحدة، إلا أن التنسيق لا يزال قيد الاستخدام العام.

• البرمجة الخطية
• تنسيق ملف MPS – وصف للتنسيق من قِبل مؤلفي برنامج lp_solve
• xMPS – تنسيق MPS موسع