تحسين القيد أو برمجة القيود (CP) هو الاسم الذي يتم منحه لتحديد الحلول الممكنة من مجموعة كبيرة جدًا من المرشحين، حيث يمكن وضع نمذجة للمشكلة من حيث القيود العشوائية. تظهر مشكلات CP في العديد من التخصصات العلمية والهندسية. (كلمة "برمجة" هي تسمية خاطئة إلى حد ما، كما لو كانت كلمة "كمبيوتر" تعني في السابق "شخص يقوم بإجراء عمليات حسابية". وتشير كلمة "البرمجة" هنا إلى ترتيب الخطة، وليس البرمجة بلغة الكمبيوتر).
يعتمد CP إلى الجدوى (إيجاد حل ممكن) بدلاً من التحسين (إيجاد حل مثالي) ويركز على القيود والمتغيرات بدلاً من الوظيفة الموضوعية. في الواقع، قد لا يكون لمشكلة CP سوى وظيفة موضوعية - قد يكون الهدف هو تضييق نطاق مجموعة كبيرة جدًا من الحلول الممكنة لمجموعة فرعية أكثر قابلية للإدارة عن طريق إضافة قيود إلى المشكلة.
ومن الأمثلة على المشاكل المناسبة لدليل CP هو جدولة الموظف.
تظهر المشكلة عندما تحتاج الشركات التي تعمل بشكل مستمر - مثل
المصانع - إلى إنشاء جداول أسبوعية لموظفيها. في ما يلي مثال مبسّط للغاية: تعمل شركة بثلاث نوبات عمل لمدة 8 ساعات في اليوم وتعين ثلاثة من موظفيها الأربعة نوبات عمل مختلفة يوميًا، مع منح رابع يوم إجازة. حتى في مثل هذه الحالة الصغيرة، يكون عدد الجداول الزمنية الممكنة كبيرًا: كل يوم، هناك 4! = 4 * 3 * 2 * 1 = 24 تعيينات محتملة للموظفين، وبالتالي فإن عدد الجداول الزمنية الأسبوعية المحتملة هو 247، أي ما يزيد عن 247.
عادة ما تكون هناك قيود أخرى تقلل من عدد الحلول
الممكنة - على سبيل المثال، أن كل موظف يعمل على الأقل
عدد من الأيام في الأسبوع على الأقل. تتبع طريقة CP الحلول التي تظل ممكنة عند إضافة قيود جديدة، مما يجعلها أداة قوية لحل مشكلات الجدولة الكبيرة في العالم الحقيقي.
تتمتع CP وقد تم تطبيق CP بنجاح في التخطيط والجدولة والعديد من المجالات الأخرى مع قيود غير متجانسة.
الأدوات
تقدّم Google بعض الطرق لحلّ مشاكل CP:
- أداة حلّ CP-SAT: هي أداة لبرمجة القيود تستخدم طرق SAT (الرضا).
- الأداة الأصلية للحلّ الخاصة بسياسة CP: هي أداة لحلّ برمجة القيود يتم استخدامها في مكتبة التوجيه.
إذا كان من الممكن نمذجة مشكلتك باستخدام هدف خطي والقيود الخطية، تكون هناك مشكلة في البرمجة الخطية وعليك التفكير في MPSolver. (ومع ذلك، يتم عادةً حلّ مشاكل التوجيه باستخدام مكتبة توجيه المركبات لدينا حتى لو كان من الممكن تمثيلها في نموذج خطي).
أمثلة
يوضّح القسم التالي أداة حلّ CP-SAT، وهي أداة حلّ "أدوات OR" الأساسية لبرمجة القيود. (يشير SAT إلى الرضا: تستخدم أداة الحلّ أساليب لحل مشاكل SAT إلى جانب طرق CP).
في ما يلي بعض الأمثلة على مشكلات الجدولة المناسبة لأداة حل CP-SAT:
هناك مشكلتان كلاسيكيتان بشأن CP وهما مشكلة N-queens وألغاز التشفير.