Explications Relatives pour les Problèmes Contextuels avec Incertitude Endogène : Une Application à la Localisation Compétitive d'Installations

Informations Fondamentales

• ID de l'article : 2506.19155
• Titre : Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location
• Auteurs : Jasone Ramírez-Ayerbe, Emma Frejinger (CIRRELT et Département d'Informatique et de Recherche Opérationnelle, Université de Montréal)
• Classification : math.OC (Optimisation et Contrôle Mathématiques)
• Date de publication : 14 octobre 2025 (version 3 de la prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2506.19155v3

Résumé

Cet article étudie les problèmes d'optimisation stochastique contextuelle sous incertitude endogène, où les décisions influencent la distribution sous-jacente. Pour mettre en œuvre de telles décisions dans la pratique, il est crucial d'assurer que leurs résultats sont interprétables et fiables. À cette fin, les auteurs calculent des explications contrefactuelles relatives, fournissant aux praticiens les modifications concrètes des covariables contextuelles nécessaires pour que la solution satisfasse des contraintes spécifiques. Bien que les explications relatives aient été introduites dans la littérature antérieure, ceci est, selon les auteurs, le premier travail se concentrant sur les variables de décision binaires et les problèmes d'incertitude endogène. Les auteurs proposent une méthode utilisant la distance de Wasserstein comme terme de régularisation, qui réduit le temps de calcul par rapport à la méthode non régularisée correspondante.

Contexte et Motivation de la Recherche

Contexte du Problème

Avec l'augmentation croissante de l'application de l'apprentissage automatique et de l'optimisation aux problèmes décisionnels, en particulier dans les environnements décisionnels à haut risque tels que la santé, l'allocation de logements et les services sociaux, assurer l'interprétabilité et la fiabilité des solutions est devenu crucial. Des institutions telles que l'Union européenne, le Bureau de la Politique Scientifique et Technologique de la Maison-Blanche et le gouvernement canadien reconnaissent le besoin croissant d'interprétabilité.

Problème Central

1. Incertitude endogène : La variable de décision z affecte la distribution de probabilité conditionnelle P(y|z,x) de la variable aléatoire y
2. Besoin d'interprétabilité : Comprendre comment les changements contextuels conduisent à des changements décisionnels et quels changements sont nécessaires pour que la solution satisfasse des contraintes spécifiques
3. Scénarios d'application pratique : Par exemple, dans la planification des infrastructures médicales, les gouvernements locaux pourraient demander quels changements minimaux dans les données conduiraient à l'ouverture d'un centre dans leur région

Limitations des Méthodes Existantes

• Les explications contrefactuelles existantes se concentrent principalement sur les problèmes de classification supervisée
• Absence de recherche sur les problèmes d'optimisation avec variables de décision binaires et incertitude endogène
• Les méthodes traditionnelles présentent une complexité computationnelle élevée et manquent de mécanismes de régularisation efficaces

Contributions Principales

1. Extension du Domaine de Recherche : Première application des explications contrefactuelles relatives aux problèmes d'optimisation stochastique contextuelle sous incertitude endogène
2. Généralisation des Méthodes Existantes : Permet un ensemble réalisable attendu D plutôt qu'une solution cible unique, généralisant les méthodes existantes basées sur des solutions fournies par des experts
3. Traitement des Variables Binaires : Résout le problème des explications relatives impliquant des variables de décision binaires
4. Régularisation de Wasserstein : Utilise un terme de régularisation minimisant la distance entre les distributions induites par les solutions contrefactuelles et factuelles
5. Amélioration de l'Efficacité Computationnelle : La méthode de régularisation proposée réduit significativement le temps de calcul

Détails de la Méthode

Définition de la Tâche

Étant donné un problème d'optimisation stochastique contextuelle :

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

où :

• z ∈ Z : vecteur de variables de décision
• x⁰ ∈ X ⊆ ℝ^{dx} : covariables contextuelles continues (caractéristiques)
• y : vecteur de variables aléatoires capturant l'incertitude endogène
• P(y|z,x⁰) : distribution de probabilité conditionnelle

Définition de l'Explication Contrefactuelle Relative

Définition 1.1 : Pour un facteur donné α ∈ (0,∞] et un espace souhaité D, une explication relative du problème (1) est un nouveau contexte x tel qu'il existe une solution réalisable dans D dont la modification de la récompense attendue est au maximum α fois celle-ci.

Problème d'Optimisation Principal

Le calcul de l'explication relative peut être formulé comme le problème d'optimisation non-convexe suivant :

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

Fonction de Coût et Régularisation de Wasserstein

La fonction de coût prend la forme suivante :

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

où :

• J(x⁰,x) : composante de dissimilarité
• Ω(x⁰,x) : terme de régularisation utilisant la distance 2-Wasserstein

Définition de la Distance de Wasserstein : Pour deux distributions de probabilité discrètes P⁰ et P, le carré de la distance 2-Wasserstein est défini comme :

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

soumis aux contraintes :

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

Points d'Innovation Technique

1. Régularisation par Distance de Distribution : Utilise la distance de Wasserstein pour assurer la proximité entre la distribution contrefactuelle et la distribution factuelle
2. Borne Inférieure Indépendante du Modèle : Fournit une méthode indépendante du modèle pour calculer les bornes inférieures
3. Induction de Parcimonie : Réalise des solutions parcimonieuses par la combinaison de la norme ℓ₁ et de la régularisation de Wasserstein

Configuration Expérimentale

Scénario d'Application : Problème de Localisation d'Installations Compétitives Basé sur le Choix (CFLP)

• Modèle : Modèle Logit Multinomial (MNL)
• Décision : Sélectionner un sous-ensemble de sites candidats sous contrainte budgétaire pour maximiser la capture de demande attendue
• Fonction d'Utilité : v_ = -0.1θ_ + x_d, où θ_ est la distance et x_d est le score d'attractivité

Configuration des Ensembles de Données

• Petit exemple : |N|=4 utilisateurs, |D|=3 installations candidates, |E|=2 installations concurrentes, r=2 installations à ouvrir
• Instances à grande échelle :
  • Nombre d'utilisateurs : 100, 200
  • Nombre d'installations candidates : 10, 20, 40
  • Budget : 4, 8
  • Installations concurrentes fixes : 5

Indicateurs d'Évaluation

• Temps de calcul : Temps de résolution moyen et médian
• Distance de Wasserstein : W²₂
• Parcimonie : Pourcentage de caractéristiques contextuelles modifiées
• Capture de Demande : Quantités de demande factuelles et contrefactuelles
• Norme ℓ₁ : Distance L1 des changements contextuels

Détails d'Implémentation

• Solveur : Gurobi 11.0.1
• Environnement de Programmation : Python 3.11.7
• Plateforme de Calcul : Processeur Intel Core i9-10980XE
• Limite de Temps : 1 heure
• Paramètres de Régularisation : λ ∈ {0, 0.1, 1}

Résultats Expérimentaux

Résultats Principaux

1. Amélioration Significative de l'Efficacité Computationnelle :
   • Le temps de résolution moyen pour λ=0.1 est considérablement réduit par rapport à λ=0
   • Exemple : N=100, D=10, r=4, temps moyen λ=0.1 : 137.92s vs λ=0 : 266.49s
2. Amélioration de la Parcimonie :
   • La régularisation de Wasserstein améliore la parcimonie des solutions
   • La parcimonie pour λ=0.1 est généralement supérieure à celle de λ=0
3. Écart d'Optimisation :
   • Dans les instances atteignant la limite de temps, l'écart d'optimisation du cas non régularisé est nettement plus important

Analyse de Cas

Résultats du Petit Exemple :

• Sans régularisation (λ=0) : x_=0.350, W²₂=164.917
• Avec régularisation (λ=0.25) : x_=0.479, W²₂=90.849
• Bien que la version régularisée présente un changement contextuel plus important, la distance de distribution est plus petite et la parcimonie est identique

Découvertes Expérimentales

1. Effet de la Régularisation : Une régularisation de Wasserstein modérée améliore non seulement le temps d'exécution et la parcimonie, mais conduit également à une transition plus fluide de la distribution de demande
2. Complexité Computationnelle : Le problème contrefactuel hérite de la complexité du problème factuel sous-jacent, les instances avec un budget r important atteignant fréquemment la limite de temps
3. Mécanisme de Parcimonie : Les changements parcimonieux ne sont pas seulement réalisés par la minimisation de la norme ℓ₁, la régularisation encourage également le modèle à concentrer les changements sur moins d'installations plutôt que de les disperser en petites modifications

Travaux Connexes

Explications Contrefactuelles pour les Problèmes d'Optimisation

• Bogetoft et al. (2024) : Application du concept à l'analyse par enveloppe de données (DEA)
• Kurtz et al. (2025) : Explications contrefactuelles pour la programmation linéaire, formalisant trois types : faible, fort et relatif
• Série de travaux de Korikov : Calcul d'explications contrefactuelles faibles pour la programmation linéaire en nombres entiers par optimisation inverse

Problèmes d'Optimisation Contextuelle

• Forel et al. (2023) : Suppose que les paramètres sont estimés à partir de covariables contextuelles, utilisant des forêts aléatoires ou k-NN comme prédicteurs
• Vivier-Ardisson et al. (2024) : Extension aux classificateurs différentiables, incluant les réseaux de neurones

Distinction avec les Travaux Connexes

1. Définition de l'Objectif : Permet un ensemble réalisable attendu D plutôt qu'une cible unique fournie par un expert
2. Type d'Incertitude : Se concentre sur l'incertitude endogène
3. Type de Variables : Traite les variables de décision binaires
4. Innovation de Régularisation : Introduit la régularisation par distance de Wasserstein

Conclusions et Discussion

Conclusions Principales

1. Efficacité de la Méthode : Extension réussie des explications contrefactuelles aux problèmes stochastiques contextuels avec incertitude endogène
2. Avantages Computationnels : La régularisation de Wasserstein améliore significativement l'efficacité computationnelle
3. Qualité des Solutions : Obtention d'explications plus parcimonieuses et plus interprétables, avec des changements de probabilité de choix plus fluides

Limitations

1. Restriction aux Variables Continues : La formulation actuelle exige que les covariables contextuelles soient continues, l'extension aux covariables catégoriques reste un défi
2. Non-Unicité des Solutions : Les solutions ne sont généralement pas uniques, ce qui peut conduire à des désaccords entre les parties prenantes et à la possibilité de manipuler les explications
3. Considérations Éthiques : Plusieurs explications contrefactuelles valides peuvent soulever des problèmes éthiques, tels que dissimuler les caractéristiques contextuelles sensibles

Directions Futures

1. Explications Contrefactuelles Faibles : Calculer des explications contrefactuelles faibles forçant l'optimalité de la nouvelle solution plutôt que des explications relatives
2. Extension de Distribution : Extension à d'autres distributions de probabilité
3. Domaines d'Application : Applications dans les problèmes contextuels tels que l'optimisation de classification et la tarification
4. Garanties d'Unicité : Incorporation de termes objectifs assurant l'unicité des solutions

Évaluation Approfondie

Points Forts

1. Contribution Théorique : Première application systématique des explications contrefactuelles aux problèmes d'incertitude endogène, cadre théorique complet
2. Innovation Méthodologique : L'introduction de la régularisation de Wasserstein est à la fois théoriquement fondée et pratiquement efficace, améliorant significativement les performances computationnelles
3. Expérimentation Complète : Expériences complètes allant des petits exemples aux instances à grande échelle, avec des indicateurs d'évaluation multidimensionnels
4. Valeur Pratique : L'application CFLP choisie a une importance pratique significative, les résultats étant opérationnels

Insuffisances

1. Portée d'Application Limitée : Applicable uniquement aux variables contextuelles continues, limitant l'universalité de la méthode
2. Analyse de Complexité Insuffisante : Manque d'analyse théorique de la complexité algorithmique
3. Sélection des Paramètres : Absence de guidance systématique pour le choix du paramètre de régularisation λ de Wasserstein
4. Expériences Comparatives : Comparaisons insuffisantes avec d'autres méthodes d'explication contrefactuelle

Impact

1. Contribution Académique : Ouvre une nouvelle direction pour la recherche sur l'interprétabilité de l'optimisation contextuelle
2. Valeur Pratique : Fournit un support décisionnel interprétable pour les problèmes pratiques tels que la localisation d'installations et l'allocation de ressources
3. Reproductibilité : Fournit un code complet et des instances, facilitant la reproduction et l'extension

Scénarios d'Application

1. Planification d'Installations : Décisions de localisation pour les installations médicales, écoles et points de vente commerciaux
2. Allocation de Ressources : Problèmes d'allocation de ressources publiques nécessitant transparence et interprétabilité
3. Formulation de Politiques : Processus décisionnels gouvernementaux nécessitant transparence et interprétabilité
4. Décisions Commerciales : Sélection de positions stratégiques en environnement compétitif

Références

L'article cite 63 références pertinentes, couvrant plusieurs domaines incluant les explications contrefactuelles, la théorie de l'optimisation et les problèmes de localisation d'installations, fournissant une base théorique solide pour la recherche.

Évaluation Globale : Ceci est un article académique de haute qualité qui a atteint un bon équilibre entre l'innovation théorique et l'application pratique. L'introduction de la régularisation de Wasserstein est un point fort, offrant à la fois une justification théorique et des avantages computationnels pratiques. Malgré certaines limitations, il apporte des contributions importantes à la recherche sur l'interprétabilité des problèmes d'optimisation contextuelle.