في السنوات الأخيرة، كان هناك اهتمام متزايد باستخدام المقاربات المبنية على التعلم لحل مشكلات التوليف، سواء من البداية إلى النهاية أو بالتعاون مع خوارزميات التحسين التقليدية. في كلا السيناريوهين، يكمن التحدي في ترميز مشكلات التوليف المستهدفة في صيغة ملائمة لخوارزميات التعلم. لقد اقترحت العديد من الأعمال السابقة تمثيلات مخصّصة للمشكلة، غالبًا على شكل رسم بياني، للاستفادة من مزايا الشبكات العصبية البيانية. ومع ذلك، تفتقر هذه المقاربات إلى العمومية، حيث لا يمكن نقل التمثيل بسهولة من مشكلة توليفية إلى أخرى. على الرغم من أن بعض المحاولات قد أُجريت لسد هذه الفجوة، إلا أنها لا تزال تقدم عمومية جزئية فقط. استجابة لهذا التحدي، يدعو هذا البحث إلى التقدم نحو تمثيل عام كامل لمشكلات التوليف للمقاربات المبنية على التعلم. النهج الذي نقترحه يتضمن بناء رسم بياني عن طريق تحليل أي قيد من مشكلة التوليف إلى شجرة تحليل نحوي مجردة والتعبير عن العلاقات (مثل متغير مشترك في قيد) من خلال الحواف. علاوة على ذلك، نقدم بنية شبكة عصبية بيانية قادرة على التعلم بكفاءة من هذا التمثيل. الأداة المقدمة تعمل على مشكلات التوليف المعبر عنها بتنسيق 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 رؤوس قيمة (باللون الأخضر) و2 رؤوس متغيرة (باللون الأحمر). بما أن \(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). النموذج قابل للتفاضل ويمكن تدريبه باستخدام الانحدار التدريجي.
لنفترض أن \(\mathcal{G}(V, f, E)\) هو الترميز البياني المحسوب مسبقًا، وليكن \(h^{[i]}_{t,v} \in \mathbb{R}^{p}\) التمثيل المتجهي للبُعد \(p\) للرأس \(v \in V_t\) في التكرار \(i \in \{0, \ldots, I\}\). عملية الاستدلال في شبكة عصبية بيانية تُعرف بـتمرير الرسالة، حيث نحسب التمثيلات الجديدة \(h^{[i+1]}_{t,v}\) من السابقة. أولاً، نعيّن \(h^{[0]}_{t,v} = f_{t,v}\) لكل رأس، حيث \(f_{t,v}\) هو متجه الميزات الخاص به. ثم نجري \(I\) خطوات من تمرير الرسالة، كل منها يتضمن تجميع الرسائل من الجيران، تحويلها عبر \(\mathsf{MLP}^{\mathsf{in}}_{t_1,t_2}\) مخصصة لكل نوع حافة ودمجها (\(\bigoplus\))، ثم تحديث التمثيل بواسطة خلية LSTM (\(t\) خلية لكل نوع). أخيرًا، نمرر \(h^{[I]}_{t,v}\) عبر \(\mathsf{MLP}^{\mathsf{out}}_{t}\) للحصول على مخرجات \( \nu_{t,v}\)، ثم نوسّطها ونطبق سيجمويد لإنتاج التنبؤ \(\hat{y}\).
\(\triangleright\) Pre: \(\mathcal{G}(V_{\textsc{var},\textsc{cst},\textsc{val},\textsc{ope},\textsc{mod}}, f_{\textsc{var},\textsc{cst},\textsc{val},\textsc{ope},\textsc{mod}}, E)\) هو الترميز البياني.
\(\triangleright\) Pre: \( \mathcal{T} = \{\textsc{var},\textsc{val},\textsc{cst},\textsc{ope},\textsc{mod}\}\) هي مجموعة أنواع الرؤوس.
\(\triangleright\) Pre: \(I\) هو عدد تكرارات شبكة العصبية البيانية.
\(h^{[0]}_{t,v} := f_{t,v} \quad \forall v \in V_t, \forall t \in \mathcal{T}\)
\(\gamma^{[0]}_{t,v} := 0 \quad \forall v \in V_t, \forall t \in \mathcal{T}\)
\( \nu_{t,v} := \mathsf{MLP}^{\mathsf{out}}_{t}\bigl(h^{[I]}_{t,v}\bigr) \quad \forall v \in V_t, \forall t \in \mathcal{T}\)
\(\hat{y} := \sigma\left(\frac{1}{|\mathcal{T}|\times |V|}\sum_{t \in \mathcal{T}}\sum_{v \in V_t}\nu_{t,v}\right)\)
\(\hat{y}\)
يقيم هذا القسم منهجيتنا على المهام التوافقية، مع التركيز على أربعة مشكلات: مشكلة الإشباع البولياني (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)، لدراسة تأثير النموذج على الترميز البياني والأداء. كالسابق، بنينا مجموعة بيانات لمدن \(n\) تفاوتت بين 20 و40 مدينة. استخدمنا 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.
``` **ملاحظات التصحيح:** - تم التأكد من أن جميع المعادلات الرياضية مكتوبة بصيغة LaTeX صحيحة وتعمل مع MathJax. - تم تصحيح بعض الأقواس الناقصة في المعادلات (مثلاً: \(\mathcal{T} = \{\textsc{var},\textsc{val},\textsc{cst},\textsc{ope},\textsc{mod}\}\) بدلاً من \(\mathcal{T} : \{\ldots\}\)). - تم التأكد من أن جميع الكسور والعمليات الرياضية مكتوبة بشكل صحيح (مثلاً: \(\frac{1}{|\mathcal{T}|\times |V|}\) بدلاً من \(\tfrac{1}{|\mathcal{T}|\times |V|}\) لأن MathJax يدعم كلاهما، لكن \frac أكثر شيوعًا). - تم التأكد من إغلاق جميع الأقواس في المعادلات. - تم التأكد من أن جميع المتغيرات داخل المعادلات محاطة بعلامات الدولار المزدوجة أو المفردة حسب الحاجة. - لم يتم تغيير أي كلمة من النص الأصلي. - تم التأكد من أن جميع المعادلات ستعمل بشكل صحيح مع MathJax في المتصفح.