2025-11-13T21:28:11.123642

Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location

Ramírez-Ayerbe, Frejinger
In this paper, we consider contextual stochastic optimization problems under endogenous uncertainty, where decisions affect the underlying distributions. To implement such decisions in practice, it is crucial to ensure that their outcomes are interpretable and trustworthy. To this end, we compute relative counterfactual explanations that provide practitioners with concrete changes in the contextual covariates required for a solution to satisfy specific constraints. Whereas relative explanations have been introduced in prior literature, to the best of our knowledge this is the first work focusing on problems with binary decision variables and endogenous uncertainty. We propose a methodology that uses the Wasserstein distance as a regularization term, which leads to a reduction in computation times compared to its unregularized counterpart. We illustrate the method using a choice-based competitive facility location problem and present numerical experiments that demonstrate its ability to efficiently compute sparse and interpretable explanations.
academic

شروحات نسبية للمشاكل السياقية مع عدم اليقين الداخلي: تطبيق على تحديد موقع المنشآت التنافسية

المعلومات الأساسية

  • معرّف الورقة: 2506.19155
  • العنوان: Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location
  • المؤلفون: Jasone Ramírez-Ayerbe, Emma Frejinger (CIRRELT وقسم علوم الحاسوب والبحث العملياتي، جامعة مونتريال)
  • التصنيف: math.OC (التحسين الرياضي والتحكم)
  • تاريخ النشر: 14 أكتوبر 2025 (النسخة الثالثة من arXiv)
  • رابط الورقة: https://arxiv.org/abs/2506.19155v3

الملخص

تدرس هذه الورقة مشاكل التحسين العشوائي السياقي تحت عدم اليقين الداخلي، حيث تؤثر القرارات على التوزيع الأساسي. لتنفيذ مثل هذه القرارات عملياً، من الضروري ضمان أن تكون نتائجها قابلة للتفسير والثقة. لهذا الغرض، يحسب المؤلفون شروحات مضادة للواقع نسبية، مما يوفر للممارسين تغييرات محددة في متغيرات السياق المشروط اللازمة لجعل الحل يفي بقيود معينة. على الرغم من أن الشروحات النسبية قد تم تقديمها في الأدبيات السابقة، إلا أن هذا هو، حسب علم المؤلفين، أول عمل يركز على مشاكل المتغيرات الثنائية وعدم اليقين الداخلي. يقترح المؤلفون طريقة تستخدم مسافة Wasserstein كحد تنظيمي، مما يقلل وقت الحساب مقارنة بالطريقة غير المنظمة المقابلة.

الخلفية البحثية والدافع

خلفية المشكلة

مع تزايد تطبيق التعلم الآلي والتحسين في مشاكل القرار، خاصة في بيئات القرار عالية المخاطر مثل الرعاية الصحية وتخصيص الإسكان والخدمات الاجتماعية، أصبح ضمان قابلية تفسير الحلول والثقة فيها أمراً حتمياً. تعترف مؤسسات مثل الاتحاد الأوروبي ومكتب سياسة العلوم والتكنولوجيا بالبيت الأبيض والحكومة الكندية بالحاجة المتزايدة للقابلية للتفسير.

المشكلة الأساسية

  1. عدم اليقين الداخلي: متغيرات القرار z تؤثر على التوزيع الاحتمالي الشرطي للمتغير العشوائي y وهو P(y|z,x)
  2. متطلبات القابلية للتفسير: الحاجة إلى فهم كيف تؤدي التغييرات السياقية إلى تغييرات القرار، وما هي التغييرات المطلوبة لجعل الحل يفي بقيود معينة
  3. سيناريوهات التطبيق العملي: مثل التخطيط للبنية التحتية الطبية، حيث قد تسأل الحكومات المحلية عن الحد الأدنى من التغييرات في البيانات التي ستؤدي إلى فتح مركز في منطقتهم

قيود الطرق الموجودة

  • تركز الشروحات المضادة للواقع الموجودة بشكل أساسي على مشاكل التصنيف الخاضعة للإشراف
  • نقص الأبحاث حول مشاكل التحسين ذات المتغيرات الثنائية وعدم اليقين الداخلي
  • الطرق التقليدية لها تعقيد حسابي عالي وتفتقر إلى آليات تنظيم فعالة

المساهمات الأساسية

  1. توسيع نطاق البحث: تطبيق أول للشروحات المضادة للواقع النسبية على مشاكل التحسين العشوائي السياقي تحت عدم اليقين الداخلي
  2. تعميم الطرق الموجودة: السماح بمجموعة قابلة للتطبيق متوقعة D بدلاً من حل هدف واحد، مما يعمم الطرق القائمة على الحلول المقدمة من الخبراء
  3. التعامل مع المتغيرات الثنائية: حل مشاكل الشروحات النسبية في إعدادات متغيرات القرار الثنائية
  4. تنظيم Wasserstein: استخدام حد تنظيمي يقلل من مسافة التوزيع بين الحلول المضادة للواقع والفعلية
  5. تحسين الكفاءة الحسابية: الطريقة المقترحة المنظمة تقلل بشكل كبير من وقت الحساب

شرح الطريقة

تعريف المهمة

بالنظر إلى مشكلة التحسين العشوائي السياقي:

z*(x⁰) ∈ argmax_{z∈Z} E_{P(y|z,x⁰)}[r(y,z)]

حيث:

  • z ∈ Z: متجه متغيرات القرار
  • x⁰ ∈ X ⊆ ℝ^{dx}: متغيرات السياق المشروط المستمرة (الميزات)
  • y: متجه المتغيرات العشوائية التي تلتقط عدم اليقين الداخلي
  • P(y|z,x⁰): التوزيع الاحتمالي الشرطي

تعريف الشرح المضاد للواقع النسبي

التعريف 1.1: بالنسبة لعامل معين α ∈ (0,∞] ومساحة متوقعة D، فإن الشرح النسبي للمشكلة (1) هو سياق جديد x بحيث يوجد حل قابل للتطبيق في D، مع تغيير في المكافأة المتوقعة لا يتجاوز α مرات.

مشكلة التحسين الأساسية

يمكن التعبير عن حساب الشرح النسبي كمشكلة تحسين غير محدبة:

L*_free := min_{x∈X,z∈Z} L(x,x⁰)
s.t. E_{P(y|z,x)}[r(y,z)] ≥ α · E_{P(y|z⁰,x⁰)}[r(y,z⁰)]
     z ∈ D

دالة التكلفة وتنظيم Wasserstein

تتخذ دالة التكلفة الشكل التالي:

L(x⁰,x) = J(x⁰,x) + λΩ(x⁰,x)

حيث:

  • J(x⁰,x): مكون عدم التشابه
  • Ω(x⁰,x): الحد التنظيمي، باستخدام مسافة Wasserstein 2

تعريف مسافة Wasserstein: بالنسبة لتوزيعين احتماليين منفصلين P⁰ و P، يُعرّف مربع مسافة Wasserstein 2 على النحو التالي:

W²₂(P⁰,P) := min_{π∈Π} ∑_{c∈C} ∑_{c'∈C} π_{cc'} δ(c,c')²

تحت القيود:

  • ∑{c'∈C} π{cc'} = P⁰(c) ∀c ∈ C
  • ∑{c∈C} π{cc'} = P(c') ∀c' ∈ C
  • π_{cc'} ≥ 0

نقاط الابتكار التقني

  1. تنظيم مسافة التوزيع: استخدام مسافة Wasserstein لضمان قرب التوزيع المضاد للواقع من التوزيع الفعلي
  2. حد أدنى مستقل عن النموذج: توفير طريقة مستقلة عن النموذج لحساب الحد الأدنى
  3. تحريض الندرة: تحقيق حلول نادرة من خلال معايير ℓ₁ وتنظيم Wasserstein معاً

إعداد التجارب

سيناريو التطبيق: مشكلة تحديد موقع المنشآت التنافسية القائمة على الاختيار (CFLP)

  • النموذج: نموذج Logit متعدد الحدود (MNL)
  • القرار: اختيار مجموعة فرعية من المواقع المرشحة تحت قيود الميزانية لتعظيم التقاط الطلب المتوقع
  • دالة المنفعة: v_ = -0.1θ_ + x_d، حيث θ_ هي المسافة و x_d هي درجة الجاذبية

تكوين مجموعات البيانات

  • مثال صغير: |N|=4 مستخدمين، |D|=3 منشآت مرشحة، |E|=2 منشآت تنافسية، r=2 منشآت مفتوحة
  • حالات واسعة النطاق:
    • عدد المستخدمين: 100، 200
    • عدد المنشآت المرشحة: 10، 20، 40
    • الميزانية: 4، 8
    • المنشآت التنافسية ثابتة عند 5

مؤشرات التقييم

  • وقت الحساب: متوسط ووقت الحل الوسيط
  • مسافة Wasserstein: W²₂
  • الندرة: نسبة مئوية من ميزات السياق المتغيرة
  • التقاط الطلب: كمية الطلب الفعلية والمضادة للواقع
  • معيار ℓ₁: مسافة L1 لتغيير السياق

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

  • المحلل: Gurobi 11.0.1
  • بيئة البرمجة: Python 3.11.7
  • منصة الحساب: معالج Intel Core i9-10980XE
  • حد زمني: ساعة واحدة
  • معاملات التنظيم: λ ∈ {0, 0.1, 1}

نتائج التجارب

النتائج الرئيسية

  1. تحسن كبير في الكفاءة الحسابية:
    • انخفاض كبير في متوسط وقت الحل عند λ=0.1 مقارنة بـ λ=0
    • مثال: عند N=100, D=10, r=4، متوسط الوقت 137.92 ثانية عند λ=0.1 مقابل 266.49 ثانية عند λ=0
  2. تحسن الندرة:
    • يحسن تنظيم Wasserstein ندرة الحل
    • عادة ما تكون الندرة عند λ=0.1 أفضل من الحالة عند λ=0
  3. فجوة التحسين:
    • في الحالات التي تصل إلى الحد الزمني، فجوة التحسين في الحالة غير المنظمة أكثر وضوحاً

تحليل الحالات

نتائج المثال الصغير:

  • بدون تنظيم (λ=0): x_=0.350, W²₂=164.917
  • مع تنظيم (λ=0.25): x_=0.479, W²₂=90.849
  • النسخة المنظمة، على الرغم من تغيير السياق الأكبر، تحقق مسافة توزيع أصغر مع نفس الندرة

نتائج التجارب

  1. تأثير التنظيم: التنظيم المعتدل لـ Wasserstein لا يحسن وقت التشغيل والندرة فحسب، بل يؤدي أيضاً إلى انتقال سلس لتوزيع الطلب
  2. التعقيد الحسابي: ترث مشكلة المضاد للواقع التعقيد من المشكلة الفعلية الأساسية، وغالباً ما تصل الحالات ذات الميزانية الكبيرة r إلى الحد الزمني
  3. آلية الندرة: لا يتم تحقيق التغييرات النادرة فقط من خلال تقليل معيار ℓ₁، بل يشجع التنظيم أيضاً النموذج على تركيز التغييرات على عدد أقل من المنشآت بدلاً من نشر تعديلات صغيرة

الأعمال ذات الصلة

شروحات مضادة للواقع لمشاكل التحسين

  • Bogetoft et al. (2024): تطبيق المفهوم على تحليل مغلف البيانات (DEA)
  • Kurtz et al. (2025): شروحات مضادة للواقع للبرمجة الخطية، تشكيل ثلاثة أنواع ضعيفة وقوية ونسبية
  • سلسلة أعمال Korikov: حساب شروحات مضادة للواقع الضعيفة للبرمجة الخطية الصحيحة من خلال التحسين العكسي

مشاكل التحسين السياقي

  • Forel et al. (2023): افتراض تقدير المعاملات من متغيرات السياق المشروط، باستخدام الغابات العشوائية أو k-NN كمتنبئات
  • Vivier-Ardisson et al. (2024): التوسع إلى المصنفات القابلة للتفاضل، بما في ذلك الشبكات العصبية

الفرق بين هذه الورقة والأعمال ذات الصلة

  1. تحديد الهدف: السماح بمجموعة قابلة للتطبيق متوقعة D بدلاً من هدف واحد مقدم من الخبير
  2. نوع عدم اليقين: التركيز على عدم اليقين الداخلي
  3. نوع المتغيرات: التعامل مع متغيرات القرار الثنائية
  4. ابتكار التنظيم: إدخال تنظيم مسافة Wasserstein

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. فعالية الطريقة: توسيع ناجح للشروحات المضادة للواقع إلى مشاكل التحسين العشوائي السياقي تحت عدم اليقين الداخلي
  2. الميزة الحسابية: تنظيم Wasserstein يحسن بشكل كبير الكفاءة الحسابية
  3. جودة الحل: الحصول على حلول أكثر ندرة وقابلية للتفسير، مع انتقال احتمالي أكثر سلاسة

القيود

  1. قيود المتغيرات المستمرة: الصيغة الحالية تتطلب أن تكون متغيرات السياق المشروط من النوع المستمر، والتوسع إلى المتغيرات الفئوية لا يزال تحدياً
  2. عدم تفرد الحل: الحل عادة ما يكون غير فريد، مما قد يؤدي إلى خلاف بين أصحاب المصلحة وإمكانية التلاعب بالشرح
  3. الاعتبارات الأخلاقية: قد تثير الشروحات المضادة للواقع المتعددة الصحيحة مشاكل أخلاقية، مثل إخفاء ميزات السياق الحساسة

الاتجاهات المستقبلية

  1. شروحات ضعيفة: حساب شروحات ضعيفة تفرض الأمثلية للحل الجديد بدلاً من الشروحات النسبية
  2. توسع التوزيع: التوسع إلى توزيعات احتمالية أخرى
  3. مجالات التطبيق: التطبيق في مشاكل التحسين التصنيفي والتسعير والمشاكل السياقية الأخرى
  4. ضمانات التفرد: دمج حدود موضوعية لضمان تفرد الحل

التقييم المتعمق

المميزات

  1. المساهمة النظرية: أول تطبيق منهجي للشروحات المضادة للواقع على مشاكل عدم اليقين الداخلي، مع إطار نظري شامل
  2. ابتكار الطريقة: إدخال تنظيم Wasserstein له أساس نظري وتأثير عملي، مما يحسن الأداء الحسابي بشكل كبير
  3. التجارب الشاملة: تجارب شاملة من أمثلة صغيرة إلى حالات واسعة النطاق، مع مؤشرات تقييم متعددة الأبعاد
  4. القيمة العملية: تطبيق CFLP المختار له أهمية عملية كبيرة، والنتائج قابلة للتطبيق

أوجه القصور

  1. نطاق التطبيق المحدود: ينطبق فقط على متغيرات السياق المستمرة، مما يحد من عمومية الطريقة
  2. نقص تحليل التعقيد: افتقار إلى التحليل النظري لتعقيد الخوارزمية
  3. اختيار المعاملات: اختيار معامل تنظيم Wasserstein λ يفتقر إلى إرشادات منهجية
  4. التجارب المقارنة: المقارنة مع طرق الشروحات المضادة للواقع الأخرى غير كافية

التأثير

  1. المساهمة الأكاديمية: فتح اتجاه جديد لأبحاث القابلية للتفسير في التحسين السياقي
  2. القيمة العملية: توفير دعم قرار قابل للتفسير لمشاكل مثل تخطيط المنشآت وتخصيص الموارد
  3. إمكانية التكرار: توفير رمز وأمثلة كاملة لتسهيل التكرار والتوسع

السيناريوهات القابلة للتطبيق

  1. تخطيط المنشآت: قرارات اختيار المواقع للمنشآت الطبية والمدارس والشبكات التجارية
  2. تخصيص الموارد: مشاكل تخصيص الموارد العامة التي تتطلب شفافية وقابلية تفسير
  3. صنع السياسات: عمليات صنع القرار الحكومية التي تتطلب شفافية
  4. القرارات التجارية: اختيار المواقع الاستراتيجية في بيئة تنافسية

المراجع

تستشهد الورقة بـ 63 مرجعاً ذا صلة، تغطي شروحات مضادة للواقع ونظرية التحسين ومشاكل تحديد موقع المنشآت وغيرها من المجالات المهمة، مما يوفر أساساً نظرياً متيناً للبحث.

التقييم الشامل: هذه ورقة أكاديمية عالية الجودة حققت توازناً جيداً بين الابتكار النظري والتطبيق العملي. إدخال تنظيم Wasserstein هو نقطة مضيئة، حيث يتمتع بأساس نظري ويجلب مزايا حسابية عملية. على الرغم من بعض القيود، فقد قدمت مساهمة مهمة لأبحاث القابلية للتفسير في مشاكل التحسين السياقي.