مُلَخَّص

في السنوات الأخيرة، كان هناك اهتمام متزايد باستخدام المقاربات المبنية على التعلم لحل مشكلات التوليف، سواء من البداية إلى النهاية أو بالتعاون مع خوارزميات التحسين التقليدية. في كلا السيناريوهين، يكمن التحدي في ترميز مشكلات التوليف المستهدفة بصيغة ملائمة لخوارزميات التعلم. لقد اقترحت العديد من الأعمال السابقة تمثيلات مخصّصة للمشكلة، غالبًا على شكل رسم بياني، للاستفادة من مزايا الشبكات العصبية البيانية. ومع ذلك، تفتقر هذه المقاربات إلى العمومية؛ إذ لا يمكن نقل التمثيل بسهولة من مشكلة توليفية إلى أخرى. على الرغم من بعض المحاولات لسد هذه الفجوة، فإنها تقدم عمومية جزئية فقط. استجابةً لهذا التحدي، يقدم هذا البحث خطوةً نحو تمثيل عام شامل لمشكلات التوليف للمقاربات المبنية على التعلم. يتضمن النهج المقترح إنشاء رسم بياني من خلال تحليل أي قيد في مشكلة التوليف إلى شجرة تحليل نحوي مجردة، والتعبير عن العلاقات (مثل متغير مشترك في قيد) بواسطة الحواف. علاوة على ذلك، نقدم بنية شبكة عصبية بيانية قادرة على التعلم بكفاءة من هذا التمثيل. الأداة المقدمة تعمل على مشكلات التوليف المعبر عنها بتنسيق XCSP3، وتعالج جميع القيود المتاحة في مسابقة المسار المصغر لعام 2023. تظهر النتائج التجريبية على أربع مشكلات توليفية أن بنيتنا تحقق أداءً مماثلاً للهياكل المعمارية المخصصة مع الحفاظ على العمومية. تتوفر شيفرتنا ونماذجنا المدربة للجمهور على https://github.com/corail-research/learning-generic-csp.

مُقَدِّمَة

لقد جذبت مسائل التحسين التوافقي انتباه باحثي علوم الحاسوب منذ نشأة هذا المجال. وكانت مشكلات التحسين التوافقي، مثل مشكلة البائع المتجول أو الإشباع البولياني، محور بحث مستمر لعقود في مجتمع علوم الحاسوب. يمكننا الآن حل مشكلات كبيرة من هذه الأنواع بكفاءة باستخدام الأساليب الدقيقة (Applegate2009) والإجراءات التقريبية (36b9628e7a874d208624584d8a470985). تجسّد هذه الاستراتيجيات خبرات الخبراء حول بنية المشكلات المطبّقة عليها. وعلى الرغم من نجاحها الواسع في حل المشكلات التوافقية سواء كحل مباشر أو ضمن إجراءات البحث، أثار ظهور التعلم العميق في العديد من المجالات المختلفة (Bahdanau_Cho_Bengio_2016, brown2020language, Krizhevsky_Sutskever_Hinton_2012, mnih2015human) اهتمام الباحثين (Prouvost_2020). من بين نماذج التعلم العميق، أثبتت الشبكات العصبية البيانية (GNNs) (Scarselli_Gori_Tsoi_Hagenbuchner_Monfardini_2009) أنها أداة قوية ومرنة لحل هذه المشكلات. ومع ذلك، كما أشار Cappart et al. (2023) (cappart2021combinatorial)، لا يزال من الصعب تبنّي GNN والتعلم الآلي ضمن إجراءات الحل المستخدمة عمليًا. أحد الأسباب هو وجوب تصميم وتدريب بنية مخصصة لكل مشكلة توافقية، بالإضافة إلى الحاجة لمجموعة تدريب كبيرة وموصوفة بدقة.

اعتمد معظم النهج ذات الصلة على إنشاء تمثيل بياني مخصص للمشكلة، مثل NeuroSAT (Selsam2018) الذي يستفيد من ترميز صيغ SAT، أو الأساليب المرتبطة ارتباطًا وثيقًا بـمشكلة البائع المتجول (Prates_Avelar_Lemos_Lamb_Vardi_2018, joshi2022learning). تعاني هذه الأساليب من محدودية العمومية، إذ لا يمكن نقل بنية التمثيل ببساطة من مشكلة توافقية إلى أخرى. على الرغم من بعض المحاولات لسد هذه الفجوة، فإنها توفر عمومية جزئية فقط. على سبيل المثال، اقترح Gasse et al. (2019) (Gasse_Chetelat_Ferroni_Charlin_Lodi_2019) رسمًا ثنائي الطبقات يربط بين المتغيرات والقيود عندما يشارك المتغير في قيد معين، لكنه يشفّر فقط البرمجة الصحيحة المختلطة الثنائية. وفيما بعد، قدم Chalumeau et al. (2021) (chalumeau2021seapearl) رسمًا ثلاثي الطبقات حيث المتغيرات والقيم والقيود هي أنواع مخصصة من الرؤوس. يفتقر هذا الإطار أيضًا إلى العمومية؛ إذ يتطلب إعادة تدريب النموذج عند تغيير عدد المتغيرات. حتى الآن، كان آخر الاقتراحات عمل Marty et al. (2023) (Marty_François_Tessier_Gauthier_Rousseau_Cappart_2023) الذي استخدم رسمًا ثلاثي الطبقات يسمح بإضافة ميزات مخصصة لكل نوع رأس. على الرغم من أن أي مشكلة توافقية يمكن نظريًا ترميزها بهذا الإطار، فإن بعض المعلومات تضيع في العملية. على سبيل المثال، يصعب التمييز بين القيد \(3x_1 \leq 4x_2\) والقيد \(2x_1 \leq 5x_2\). فمن جهة، يمكن اعتباره عدم مساواة، لكننا نفقد تفاصيل المعاملات؛ ومن جهة أخرى، قد نفكّره كعلاقتين مختلفتين، لكن نفقد الصفة الأساسية للاختلاف. بعبارة أخرى، لم تكن دالة التشفير لديهم حقْنِيّة؛ فقد تشترك حالات مختلفة في التمثيل نفسه من دون إمكانية التمييز بينها. علاوة على ذلك، استهدفت تلك التجارب مشكلات نسبية نقية (المجموعة المستقلة القصوى، القطع الأقصى، تلوين الرسم) فقط، كما تواجه القيود نفسها في نهج Tönshoff et al. (2022) (Tönshoff_Kisin_Lindner_Grohe_2022).

استنادًا إلى هذا السياق، يتقدم هذا البحث نحو تمثيل عام تمامًا للمشكلات التوافقية المعتمدة على التعلم. فكرتنا الأساسية هي تفكيك أي قيد في مثيل المشكلة إلى شجرة بناء نحوي مجردة، ثم ربط العناصر المتماثلة (مثل نفس المتغير أو القيمة) بواسطة حواف. بعد ذلك، نقدم بنية GNN قادرة على استغلال هذا الرسم. لإظهار عمومية هذا النهج، يعمل نموذجنا مباشرة على الحالات المعبر عنها بتنسيق XCSP3 (Boussemart_Lecoutre_Audemard_Piette_2022)، ويعالج جميع القيود المتاحة في مسابقة المسار المصغر لعام 2023. أجرينا التجارب على أربع مشكلات تشمل قيودًا قياسية وعالمية مثل allDifferent (regin1994filtering), table (demeulenaere2016compact), negativeTable (verhaeghe2017extending), element وsum، وهدفها التنبؤ بإمكانية الإشباع لنسخ قرارية من المشكلات التوافقية. تظهر النتائج أن بنيتنا العامة تقدم أداءً قريبًا من الهياكل المعمارية المخصصة وتتفوّق على الرسم الثلاثي الطبقات لمارتي وآخرين (2023) (Marty_François_Tessier_Gauthier_Rousseau_Cappart_2023).

ترميز مثيلات المشكلات التوافقية كرسم بياني

رسميًا، يُعرّف مثيل المشكلة التوافقية \(\mathcal{P}\) على أنه رباعي \(\langle X, D(X), C, O \rangle\)، حيث \(X\) هي مجموعة المتغيرات، \(D(X)\) مجموعة النطاقات، \(C\) مجموعة القيود، و\(O\) (\(X \to \mathbb{R}\)) دالة الهدف. الحل الصالح هو تعيين كل متغير إلى قيمة من نطاقه بحيث تتحقق كل القيود. والحل الأمثل هو الذي لا يمكن تحسين قيمة هدفه من خلال حل آخر. هدفنا هو بناء دالة \(\Phi: \langle X, D(X), C, O \rangle \mapsto \mathcal{G}(V,f,E)\)، حيث \(\mathcal{G}\) رسم بياني و\(V\), \(f\), \(E\) مجموعات الرؤوس وميزات الرؤوس والحواف على التوالي. نريد أن تكون هذه الدالة حقْنِيّة، أي أن كل ترميز يمثّل مثيل مشكلة توافقية واحدًا فقط. نقترح تحقيق ذلك عبر رسم بياني متجانس غير موجه مكوّن من خمسة أنواع من الرؤوس: المتغيرات (\(\textsc{var}\))، القيود (\(\textsc{cst}\))، القيم (\(\textsc{val}\))، العوامل (\(\textsc{ope}\))، والنموذج (\(\textsc{mod}\)). الفكرة هي تقسيم كل قيد إلى سلسلة من العمليات الأولية، وجمع الرؤوس الممثلة لنفس المتغير أو القيمة، وربطها معًا. تشبه هذه العملية بناء شجرة التحليل النحوي المجردة لبرنامج. رسميًا، ينتج عنها رسم بياني \(\mathcal{G}(V, f, E)\) حيث \(V = V_\textsc{var} \cup V_\textsc{cst} \cup V_\textsc{val} \cup V_\textsc{ope} \cup V_\textsc{mod}\)، و\(f = f_\textsc{var} \cup f_\textsc{cst} \cup f_\textsc{val} \cup f_\textsc{ope} \cup f_\textsc{mod}\)، و\(E\) هي الحواف التي تربط الرؤوس وتعكس العلاقات في القيد.

ترميز المشكلة

يمثّل الترميز مثيلًا لمشكلة توافقية باعتباره مثالًا تشغيليًا. هناك 3 رؤوس للقيم (باللون الأخضر) ورأسان للمتغيرات (باللون الأحمر). بما أن \(x_1\) يمكنه أن يأخذ القيم 1 و2 في نطاقه، فهو متصل بحافتين، وكذلك \(x_2\). هناك 2 رؤوس قيد (باللون الأزرق)، واحدة لعدم المساواة (\(\leq\)) وأخرى لقيد الجدول (\(\textsf{ext}\)). توضح المنطقة الرمادية القيد \(3x_1 \leq 4x_2\) مع العاملين (باللون البرتقالي) وعمليتي الضرب: الأولى (\(\times\) بميزة 3) لـ\(x_1\) على الجانب الأيمن (\(\textsf{rhs}\))، والثانية (\(\times\) بميزة 4) لـ\(x_2\) على الجانب الأيسر (\(\textsf{lhs}\)). يوضح المشغّلان \(\textsf{rhs}\) و\(\textsf{lhs}\) جانبي المعادلة، وهو أمر ضروري للتمييز بين \(3x_1 \leq 4x_2\) و\(3x_1 \geq 4x_2\)، ويرتبط بالقيد المناسب. يتم التعبير عن قيد الجدول \(\textsc{table}([x_1,x_2],[(1,2),(2,3)])\) بطريقة مماثلة عبر زوجين \(t_1\) و\(t_2\). أخيرًا، يتصل رأس النموذج (باللون الأصفر) بالقيدين وبالمتغير \(x_1\) كجزء من دالة الهدف.

ملاحظة ختامية: يمكن استخدام هذا الترميز لتمثيل أي مثيل لمشكلة توافقية بطريقة فريدة. يتطلب ذلك تطوير محلل لكل قيد يحدد كيفية تفكيكه إلى مشغلات ومتغيرات. ندعم حاليًا جميع القيود المدرجة في نص XCSP3-core (Boussemart_Lecoutre_Audemard_Piette_2022) والمستخدمة في مسارات الحل المصغر لمسابقة XCSP-2023: المساواة الثنائية، الجدول، الجدول السلبي، الجدول القصير، العنصر، والمجموع. يحتوي مستودعنا على الوثائق اللازمة لبناء الرسم البياني لأي مثيل بصيغة XCSP3-core ووصف جميع الميزات المدعومة.

التعلم من الترميز باستخدام شبكة عصبية بيانية

لتحقيق الخطوة التالية ولتعلم هذا التمثيل، صممنا بنية شبكة عصبية بيانية مخصصة للاستفادة من هذا الترميز. الشبكة العصبية البيانية هي بنية متخصصة لحساب التمثيل الكامن (التضمين) لكل عقدة في الرسم البياني المعطى (Scarselli_Gori_Tsoi_Hagenbuchner_Monfardini_2009) من خلال تجميع المعلومات من العقد المجاورة بشكل تكراري. تُسمى كل خطوة تجميع بطبقة وتتضمن أوزانًا قابلة للتعلم، وهناك عدة طرق للتجميع معروفة في الأدبيات (li2016gated, monti2017geometric, velivckovicgraph). النموذج قابل للتفاضل ويمكن تدريبه باستخدام الانحدار التدريجي.

...

التجارب

يقيم هذا القسم منهجيتنا على أربع مهمات توافقية: SAT، COL، Knap، وTSP (نموذجَي TSP-Ext وTSP-Elem). درّبنا النماذج على نسخ قرارية من المشكلات، مستوضحين ما إذا كان هناك حل بتكلفة أقل من الهدف \(k\)؛ وعند عدم وجود دالة هدف تصبح مسألة إشباع بسيطة (SAT). قارنا منهجيتنا مع الهياكل المعمارية المخصصة لكل مشكلة والرسم الثلاثي الطبقات لمارتي وآخرين (2023) (Marty_François_Tessier_Gauthier_Rousseau_Cappart_2023). اعتمدنا الدقة في التنبؤ بوجود الحل مقياسًا للتقييم، واتبعنا البروتوكولات والتفاصيل التنفيذية المنشورة.

مشكلة الإشباع البولياني

استُخدم المولد العشوائي لـSelsam et al. (2018) (Selsam2018) لتوليد أزواج من نماذج SAT ذات \(n\) متغيرات بإضافة شروط عشوائية حتى تصبح المسألة غير قابلة للإشباع، ثم يُقلّب إشارة إحدى المتغيرات لجعلها قابلة للإشباع. تضمّ شروط المولد في المتوسط نحو 8 أحكام، وضمّنا كلًا من التوزيعين القابل وغير القابل للإشباع في مجموعة البيانات. أنشأنا مجموعة تدريب مكوّنة من 3,980,000 نموذج ومجموعة تحقق من 20,000.

مشكلة البائع المتجول

استُخدم المولد العشوائي لـPrates et al. (2018) (Prates_Avelar_Lemos_Lamb_Vardi_2018). يتكوّن الجيل من: (1) توزيع \(n\) نقاط عشوائية في مربع \((\sqrt{2}/2 \times \sqrt{2}/2)\)، (2) حساب مصفوفة المسافات الإقليدية، و(3) حل المثيل بالمحلل Concorde (applegate2006concorde) للحصول على التكلفة الأمثل \(C^*\). ثم أنتجنا نموذجين: أحدهما قابل بالهدف 1.02×\(C^*\)، والآخر غير قابل بالهدف 0.98×\(C^*\). بنينا نموذجَي TSP: الأول بقيد التمديد (TSP-Ext)، والثاني بقيد العنصر (TSP-Elem) لدراسة أثر النموذج على الترميز البياني والأداء. أنشأنا 850,000 نموذجًا للتدريب و50,000 للتحقق.

تلوين الرسم البياني

اتبعنا مولّد lemos2019graph لإنشاء رسومات من 40 إلى 60 رأسًا. لكل رسم نضيف حافة واحدة لتغيير قابلية التلوين بـ\(k\)، فنجمع نموذجَين: قيمة مثلى = \(k\) وأخرى أعلى. يستفيد الترميز من قيد \(\neq\). استخدمنا 140,000 نموذجًا للتدريب و10,000 للتحقق.

مشكلة الحقيبة

أنشأنا نماذجًا تحتوي من 20 إلى 40 عنصرًا وحللناها لإيجاد القيمة المثلى \(V^*\). ثم أنتجنا نموذجين: أحدهما قابل بالهدف 1.02×\(V^*\)، والآخر غير قابل بالهدف 0.98×\(V^*\). يستفيد الترميز من قيد sum. استخدمنا 950,000 نموذجًا للتدريب و50,000 للتحقق.

تفاصيل التنفيذ

درّبنا جميع النماذج باستخدام PyTorch (paszke2019pytorch) وPyTorch-Geometric (fey2019fast) على بطاقة Nvidia V100 بسعة 32 GB لمدة تصل إلى 4 أيام أو حتى التقارب. اخترنا النموذج الأفضل على مجموعة التحقق. لضمان عدالة المقارنة بين الهياكل المعمارية الخاصة والعامة، استخدمنا بطاقة واحدة وضبّطنا عدد الوحدات الخفية في MLP وLSTM. وللنماذج المخصصة، احتفظنا بنفس المعايير الفائقة في منشوراتها الأصلية. درّبنا النماذج بمُحسّن Adam (KingmaB14) مع جدول معدل التعلم وتخميد وزن \(10^{-8}\). يمكن العثور على كافة المعايير الفائقة في الكود المرفق. جميع نماذجنا معبر عنها بصيغة XCSP3.

قمنا بتنفيذ محلل لبناء الرسم البياني حسب هذا الترميز. شيفرتنا ونماذجنا المدربة متاحة للجمهور.

النتائج: دقة المناهج

يوضح الجدول [table:main-results] الدقة في التنبؤ بالإجابة الصحيحة على مجموعة التحقق لكل مشكلة وخط أساس. من المثير للاهتمام أن منهجنا يحقق أداءً مماثلًا للهياكل المعمارية المخصصة لكل مشكلة، مما يدلّ على إمكانية استخدامه مباشرة دون الحاجة لتصميم هيكل جديد مخصص. على النقيض، تراجع أداء منهج Marty_François_Tessier_Gauthier_Rousseau_Cappart_2023 في جميع المشكلات باستثناء تلوين الرسم البياني، لأن هذا التمثيل لا يحافظ على البنية التركيبية للقيود المعقدة.

بينما يحقق TSP-Elem نتائج قريبة من النموذج المخصص لـTSP، يعاني TSP-Ext من أداء أقل بوضوح، مما يبيّن أهمية اختيار نموذج إدخال مناسب للترميز. على سبيل المثال، ينتج TSP-Elem ترميزًا بحجم \(1841\) رأسًا و\(13042\) حافة، بينما يولّد TSP-Ext رسمًا بيانيًا مكوّنًا من \(5661\) رأسًا و\(28322\) حافة لنفس المثيل، مما يصعّب التدريب بسبب الحجم الأكبر.

تحليل: التعميم على نماذج أكبر

يوضح الشكل fig:generalization قدرة التعميم لنموذجنا، دون إعادة تدريب، على نماذج جديدة من 60 و80 و100 متغير (5000 نموذج لكل حجم). نلاحظ أن تمثيلنا العام يوفر تعميمًا أفضل من الهياكل المعمارية المخصصة لمشكلتَي SAT وTSP. بشكل لافت، يقدم TSP-Elem تعميمًا أفضل بكثير من TSP-Ext، مما يؤكد أثر نموذج الإدخال وحجم الرسم البياني. كذلك تبدو قدرة التعميم القوية للنموذج المخصص لمشكلة الحقيبة نابعةً أوليًا من دالة تجميع في GNN تعتمد على مجموع موزون. دراسة الأسباب الجذرية لهذا التعلم المتعمم موضوع بحث مستقبلي.

المناقشة: القيود والتحديات

على الرغم من النتائج المشجعة، هنالك بعض التحديات. أولًا، زمن التدريب طويل حتى على حالات صغيرة نسبيًا، ويرجع ذلك جزئيًا إلى حجم الرسومات الناتجة. هذا يفتح الباب لطرق ضغط خاصة تقلّص حجم الترميز دون فقدان المعلومات، مثل قيود smartTable (mairy2015smart). كما يبرز أهمية نموذج إدخال ينتج تضمينًا أصغر (مثل TSP-Elem مقارنة بـTSP-Ext). ثانيًا، اقتصرت المهمة الحالية على حل النسخ القرارِية من المشكلات بشكل من البداية إلى النهاية. وسيكون الدمج مع إجراءات حل كاملة، كما اقترح Gasse_Chetelat_Ferroni_Charlin_Lodi_2019 للبرمجة المختلطة الثنائية وcappart2021combining للبرمجة بالقيود، خطوة مهمة. أخيرًا، يبقى اختبار تعميم النموذج المدرب على مشكلة معينة (مثل TSP) على نسخة مشابهة (مثل TSP مع نوافذ زمنية) محورًا مثيرًا للاستكشاف.

الخلاصة والآفاق

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

الشكر والتقدير

تم تمويل هذا البحث بشكل رئيسي بفضل منحة اكتشاف NSERC (كندا) التي يحملها كوينتن كابارت. كما تلقى تمويلًا من برنامج الاتحاد الأوروبي للبحث والابتكار Horizon 2020 بموجب اتفاقية منحة رقم 101070149، مشروع Tuples.