Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy
تقدم هذه الورقة CPMpy، وهو إطار عمل مفتوح المصدر ومعياري يقوم بترجمة نماذج قيود الأعداد الصحيحة ذات النطاق المحدود عالية المستوى إلى مختلف أشكال الصياغة المنخفضة المستوى (CP وSMT وILP وPB وSAT) لتمكين المقارنة السهلة بين تقنيات الحل المختلفة دون الحاجة إلى إعادة صياغة يدوية.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
في المشهد الواسع للذكاء الاصطناعي، يوجد تحدٍ مستمر يُعرف بنهج "النمذجة والحل" (model-and-solve). تخيل شخصًا يحاول تنظيم حدث معقد، مثل مؤتمر يضم مئات المتحدثين، والقاعات، والفترات الزمنية. هو لا يكتب برنامجًا حاسوبيًا خطوة بخوة لحل المسألة، بل يكتب مجموعة من القواعد: "المتحدث (أ) لا يمكن أن يكون في القاعة (ب)"، "القاعة (ج) يجب أن تُستخدم قبل الساعة الثانية ظهرًا"، و"المتحدث (د) يجب أن يتحدث بعد المتحدث (هـ)". تُسمى هذه القائمة من القواعد "نموذج القيود" (constraint model). وهو وصف رفيع المستوى للمشكلة، مكتوب بلغة يمكن للبشر فهمها. وتتمثل مهمة الكمبيوتر إذن في أخذ هذه القواعد وإيجاد حل يستوفي جميع هذه الشروط.
تنشأ الصعوبة لأن عدم وجود برنامج حاسوبي واحد هو الأفضل في حل كل نوع من أنواع القواعد. فبعض البرامج ممتازة في التعامل مع عبارات "إذا-إذن" المنطقية، بينما يبرع البعض الآخر في الحسابات الرياضية أو إدارة القوائم الكبيرة من الاحتمالات. لقد بنى الباحثون أنواعًا عديدة ومختلفة من برامج الحل هذه، ولكل منها نقاط قوة ونقاط ضعف خاصة بها. ومع ذلك، يوجد عائق رئيسي: غالبًا ما لا يمكن لبرنامج مصمم لنوع معين من الحلول أن يفهم مشكلة مكتوبة لنوع آخر. لاستخدام برنامج حل مختلف، يتعين على الخبير البشري عادةً إعادة كتابة مجموعة القواعد بأكملها يدويًا بتنسيق جديد، وهي عملية مملة وعرضة للخطأ، مما يحد من القدرة على مقارنة أي الأدوات هي الأفضل لمهمة معينة.
قام فريق من الباحثين في جامعة "كي لوفن" (KU Leuven) ومؤسسات أخرى بتطوير حل لهذه مشكلة الترجمة. لقد أنشأوا مكتبة برمجية تسمى "سي بي إم بي واي" (CPMpy) تعمل كمترجم عالمي لنماذج القيود هذه. يركز عملهم على أخذ وصف رفيع المستوى للمشكلة، مكتوب بقواعد رياضية ومنطقية قياسية، وتحويله تلقائيًا إلى اللغة المحددة المطلوبة لخمس عائلات مختلفة من تقنيات الحل. تتراوح هذه التقنيات من برامج حل البرمجة بالقيود، المتخصصة في الألغاز المنطقية المعقدة، إلى برامج البرمجة الخطية الصحيحة، التي تتفوق في مسائل الأمثلة، وحتى إلى برامج "سات" (SAT)، المصممة للتحقق من صحة العبارات المنطقية. لم يكتف الباحثون ببناء مترجم فح، بل بنوا مسارًا معياريًا (modular pipeline) حيث تكون كل خطوة من عملية التحويل مكونًا متميزًا وقابلًا لإعادة الاستخدام. وهذا يسمح للنظام بتجريد الميزات المعقدة التي لا يستطيع برنامج حل معين التعامل معها، واستبدالها بقواعد أبسط ومعادلة يستطيع البرنامج فهمها.
جوهر طريقتهم هو "شلال" من التحويلات. عندما يدخل النموذج إلى النظام، يخضع أولاً لفحص سلامة للتأكد من أن أي عمليات رياضية، مثل القسمة، معرفة لجميع القيم الممكنة. إذا كانت القسمة على صفر ممكنة، يضيف النظام "حارسًا" (guard) لمنع حدوث ذلك. بعد ذلك، يقوم النظام بإزالة أي عوامل "نفي" (not) قد تكون مدفونة بعمق داخل تعبيرات معقدة، ودفعها للأسفل حتى لا تنطبق إلا على متغيرات بسيطة، مما يبسط الهيكل المنطقي. ثم يقوم النظام بتفكيك "القيود العالمية" (global constraints)، وهي قواعد قوية ورفيعة المستوى مثل "يجب أن يكون لكل من هؤلاء الأشخاص جداول زمنية مختلفة"، إلى لبنات بناء أساسية يمكن لبرامج الحل الأبسط معالجتها.
بينما يتحرك النموذج عبر المسار، يتم تسطيحه (flattened). تُستبدل التعبيرات المتداخلة والمعقدة بمتغيرات بسيطة، ويتتبع النظام هذه الاستبدالات لتجنب إنشاء متغيرات مكررة. هذه الخطوة حاسمة لأن العديد من برامج الحل لا يمكنها التعامل مع القواعد التي يكون فيها قاعدة داخل أخرى. وبالنسبة لبرامج الحل التي تفهم فقط المعادلات الخطية، يقوم النظام بعملية تسمى "الخطيّة" (linearization)؛ حيث يحول القواعد المنطقية وعدم المساواة إلى معادلات خطية مستقيمة. وأخيرًا، بالنسبة لبرامج الحل التي تعمل فقط مع المتغيرات المنطقية (صواب أو خطأ)، يقوم النظام بترميز كل عدد صحيح في سلسلة من المفاتيح المنطقية (Boolean switches). وطوال هذه العملية، يحرص النظام على الحفاظ على المعنى الدقيق للمشكلة الأصلية؛ فهو يضمن أنه إذا وجد حل للنموذج رفيع المستوى الأصلي، فسيكون هناك حل للنموذج منخفض المستوى المترجم، والعكس صحيح.
لاختبار نظامهم، أخذ الباحثون 250 مسألة أمثلة من العالم الحقيقي من مسابقة دولية كبرى. مرروا هذه المسائل عبر مسار الترجمة الخاص بهم وغذوا النتائج في ثلاثة أنواع مختلفة من برامج الحل: برنامج حل برمجة خطية صحيحة رائد، وبرنامج حل "pseudo-boolean"، وبرنامج حل "الاشباع الأقصى" (maximum satisfiability). وقاسوا الوقت الذي استغرقه كل برنامج حل للوصول إلى أفضل إجابة ممكنة. أظهرت النتائج أن عملية الترجمة غيرت هيكل النماذج بشكل كبير؛ إذ غالبًا ما زاد عدد القواعد والمتغيرات بشكل هائل مع تفكيك القواعد الرفيعة المعقدة إلى أبسط أشكالها. ومع ذلك، كان هذا التوسع ضروريًا لجعل المسائل مفهومة لبرامج الحل المختلفة.
كما كشفت الدراسة أن الطريقة التي يُترجم بها النموذج تؤثر كثيرًا على الأداء. فبالنسبة لبرنامج حل البرمجة الخطية الصحيحة، أدى استخدام طرق متخصصة لتفكيك القواعد المعقدة إلى تسريع أوقات الحل. أما بالنسبة لبرامج الحل الأخرى، فقد كان التأثير أكثر دقة؛ حيث وجد الباحثون أنه بالنسبة لبعض البرامج، كان الترجمة القياسية هي الأفضل، بينما بالنسبة لأخرى، كانت الترجمة الأكثر هجومية (aggressive) التي تعامل الأرقام كمفاتيح منطقية بسيطة هي الأفضل. واكتشفوا أن نهج "مقاس واحد يناسب الجميع" لا يعمل؛ إذ تعتمد أفضل استراتيجية ترجمة تمامًا على برنامج الحل المستهدف. وفي الواقع، بالنسبة لنوع واحد من برامج الحل، أدى استخدام الترجمة الأكثر كفاءة لنوع آخر إلى جعل عملية الحل أبطأ. وهذا يؤكد أهمية وجود نظام مرن يمكنه تكييف الترجمة مع الأداة المستهدفة.
خلص الباحثون إلى أن نهجهم المعياري ينجح في سد الفجوة بين نمذجة المشكلات رفيعة المستوى وتقنيات الحل منخفضة المستوى. ومن خلال أتمتة عملية الترجمة، فإنهم يتيحون للمستخدمين كتابة مشكلة واحدة ثم اختبارها مقابل محركات حل متعددة دون الحاجة لإعادة الكتابة يدويًا. وتتيح هذه القدرة إجراء مقارنة مباشرة حول أي تقنية هي الأنسب لتطبيق معين. وبينما تزيد عملية الترجمة حتمًا من حجم نموذج المشكلة، فإن القدرة على الاستفادة من نقاط قوة برامج الحل المختلفة تفوق هذه التكلفة. ويُظهر هذا العمل أنه مع توفر أدوات الترجمة المناسبة، يمكن جعل عالم حل القيود المتنوع متاحًا وقابلاً للمقارنة، مما يساعد الباحثين والممارسين في العثء على الحلول الأكثر فعالية للمسائل التوليفية المعقدة.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.