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
  • शीर्षक: सापेक्ष व्याख्याएं संदर्भ समस्याओं के लिए अंतर्जात अनिश्चितता के साथ: प्रतिस्पर्धी सुविधा स्थान के लिए एक अनुप्रयोग
  • लेखक: जैस्पोन रामिरेज़-आयर्बे, एम्मा फ्रेजिंगर (CIRRELT और कंप्यूटर विज्ञान और संचालन अनुसंधान विभाग, मॉन्ट्रियल विश्वविद्यालय)
  • वर्गीकरण: math.OC (गणितीय अनुकूलन और नियंत्रण)
  • प्रकाशन समय: 14 अक्टूबर 2025 (arXiv प्रीप्रिंट संस्करण 3)
  • पेपर लिंक: 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): नियमितकरण पद, 2-Wasserstein दूरी का उपयोग करता है

Wasserstein दूरी परिभाषा: दो असतत संभाव्यता वितरण P⁰ और P के लिए, 2-Wasserstein दूरी का वर्ग निम्नानुसार परिभाषित है:

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 प्रोसेसर
  • समय सीमा: 1 घंटा
  • नियमितकरण पैरामीटर: λ ∈ {0, 0.1, 1}

प्रायोगिक परिणाम

मुख्य परिणाम

  1. कम्प्यूटेशनल दक्षता में महत्वपूर्ण सुधार:
    • λ=0.1 पर औसत समाधान समय λ=0 की तुलना में काफी कम
    • उदाहरण: N=100, D=10, r=4 पर, λ=0.1 का औसत समय 137.92s बनाम λ=0 का 266.49s
  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 नियमितकरण का परिचय एक मुख्य बिंदु है, जिसमें न केवल सैद्धांतिक आधार है बल्कि व्यावहारिक कम्प्यूटेशनल लाभ भी लाता है। हालांकि कुछ सीमाएं हैं, लेकिन यह संदर्भ अनुकूलन समस्याओं की व्याख्यायोग्यता अनुसंधान में महत्वपूर्ण योगदान देता है।