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

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

基本信息

论文ID: 2506.19155
标题: Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location
作者: Jasone Ramírez-Ayerbe, Emma Frejinger (CIRRELT and Department of Computer Science and Operations Research, Université de Montréal)
分类: math.OC (数学优化与控制)
发表时间: 2025年10月14日 (arXiv预印本第三版)
论文链接: https://arxiv.org/abs/2506.19155v3

摘要

本文研究内生不确定性下的情境随机优化问题，其中决策会影响底层分布。为了在实践中实施此类决策，确保其结果可解释和可信至关重要。为此，作者计算相对反事实解释，为实践者提供使解决方案满足特定约束所需的情境协变量的具体变化。虽然相对解释在先前文献中已有介绍，但据作者所知，这是第一项专注于二元决策变量和内生不确定性问题的工作。作者提出了一种使用Wasserstein距离作为正则化项的方法，与未正则化的对应方法相比，该方法减少了计算时间。

研究背景与动机

问题背景

随着机器学习和优化在决策问题中的应用日益增加，特别是在医疗保健、住房分配、社会服务等高风险决策环境中，确保解决方案的可解释性和可信性变得至关重要。欧盟、美国白宫科技政策办公室和加拿大政府等机构都认识到对可解释性日益增长的需求。

核心问题

内生不确定性：决策变量z会影响随机变量y的条件概率分布P(y|z,x)
可解释性需求：需要理解情境变化如何导致决策变化，以及需要哪些变化使解决方案符合特定约束
实际应用场景：如医疗基础设施规划中，地方政府可能询问数据的最小变化会导致在其区域开设中心

现有方法局限性

现有反事实解释主要针对监督分类问题
缺乏针对二元决策变量和内生不确定性的优化问题的研究
传统方法计算复杂度高，缺乏有效的正则化机制

核心贡献

扩展研究范围：首次将相对反事实解释应用于内生不确定性下的情境随机优化问题
泛化现有方法：允许期望可行集D而非单一目标解决方案，泛化了基于专家提供解决方案的现有方法
处理二元变量：解决涉及二元决策变量设置下的相对解释问题
Wasserstein正则化：使用最小化反事实和事实解决方案诱导分布间距离的正则化项
计算效率提升：提出的正则化方法显著减少了计算时间

方法详解

任务定义

给定情境随机优化问题：

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

技术创新点

分布距离正则化：使用Wasserstein距离确保反事实分布与事实分布相近
模型无关下界：提供计算下界的模型无关方法
稀疏性诱导：通过ℓ₁范数和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}

实验结果

主要结果

计算效率显著提升：
- λ=0.1时平均求解时间比λ=0大幅减少
- 例如：N=100, D=10, r=4时，λ=0.1的平均时间137.92s vs λ=0的266.49s
稀疏性改善：
- Wasserstein正则化提高解的稀疏性
- λ=0.1时稀疏性通常优于λ=0的情况
优化间隙：
- 达到时间限制的实例中，非正则化情况的优化间隙明显更大