مُلَخَّص

في السنوات الأخيرة، ازداد الاهتمام باستخدام المقاربات القائمة على التعلُّم لحلّ المشكلات التوافقيّة، سواء من البداية إلى النهاية أو بالتعاون مع خوارزميّات التحسين التقليدية. في كلا السيناريوهين، يكمن التحدّي في ترميز مثيلات المشكلات المستهدفة في صيغة ملائمة لخوارزميّات التعلُّم. لقد اقترحت أعمالٌ عديدة تمثيلاتٍ مخصّصة للمشكلة، غالبًا على شكل رسمٍ بياني، للاستفادة من مزايا الشبكات العصبية البيانيّة. ومع ذلك، تفتقر هذه المقاربات إلى العموميّة، إذ لا يمكن نقل التمثيل بسهولة من مشكلة توافقيّة إلى أخرى. وعلى الرغم من بعض المحاولات لسدّ هذه الفجوة، فإنها ما زالت تقدّم عموميّة جزئية فقط. استجابةً لهذا التحدّي، يدعو هذا البحث إلى التقدّم نحو تمثيلٍ عامٍّ كاملٍ لمشكلاتٍ توافقيّة في سياق المقاربات القائمة على التعلُّم. يتضمن النهج المقترح بناءَ رسمٍ بياني عبر تحليل أيّ قيد في مثيل المشكلة إلى شجرة بنيةٍ نحويّة مُجرَّدة والتعبير عن العلاقات (مثل مشاركة متغيّر في قيد) بواسطة الحواف. علاوةً على ذلك، نقدّم بنية شبكةٍ عصبيةٍ بيانيّة قادرة على التعلُّم بكفاءة من هذا التمثيل. تعمل أداتُنا مباشرةً على مثيلاتٍ مُعبَّر عنها بتنسيق 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) رسمًا ثنائيَّ الطبقات يربط بين المتغيّرات والقيود عندما يشارك المتغيّر في قيدٍ معين. غير أنّ هذا النهج يشفّر فقط البرمجة الخطّية الصحيحة المُختلطة (MILP). ولاحقًا، قدّم 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: المساواة الثنائية، جدول القيم، الجدول السلبي، الجدول القصير، element، وsum. يحتوي مستودعُنا على الوثائق اللازمة لبناء الرسم البياني لأيّ مثيلٍ بصيغة 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}\).

التجارب

يُقيِّم هذا القسم منهجيّتَنا على مهامّ توافقيّة، مع التركيز على أربع مسائل: الإشباعُ البولياني (SAT)، تلوينُ الرسم البياني (COL)، مشكلةُ الحقيبة (Knap)، ومشكلةُ البائع المتجوّل (TSP) مع صياغتَي TSP-Ext (قيد الامتداد/الجدول) وTSP-Elem (قيد element). درّبنا النماذج على الإصدارات القرارِيّة من المشكلات، مُستَعلمِين عمّا إذا كان هناك حلٌّ بتكلفةٍ أقلّ من الهدف \(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\) نقاط عشوائيًا في المربّع \([0,1]^2\)، (2) حساب مصفوفة المسافات الإقليدية، و(3) حلّ المثيل بالمحلّل Concorde (applegate2006concorde) للحصول على التكلفة المثلى \(C^*\). ثم أنشأنا مثيلَين قرارِيَّين: أحدُهما قابلٌ للإشباع بهدف 1.02×\(C^*\) والآخر غيرُ قابلٍ للإشباع بهدف 0.98×\(C^*\). بنينا صياغتَين لـTSP: الأولى باستخدام قيد الامتداد (TSP-Ext)، والثانية باستخدام قيد element (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.