Research map / Learning theory and algorithms / Combinatorial and search optimization
A Framework for Data-Driven Explainability in Mathematical Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a data-driven framework that adds solution explainability (similarity to historical solutions in similar instances) as a second objective in mathematical optimization, with complexity results and computational experiments on explainable shortest paths.
Problem
Optimal solutions from mathematical programs may be rejected by humans because they are opaque; there is no explicit criterion for whether a solution is explainable relative to past decisions.
Approach
Treat explainability as a bicriteria objective: a solution is explainable if its solution features resemble those of solutions used in similar historical instances (weighted by instance similarity and confidence), yielding Pareto trade-offs with optimality; complexity results show hardness in general and polynomial cases such as DAGs and spanning trees.
Key results
- On the synthetic grid, the nominal solution already gets relative explainability about 0.7, and above 0.9 explainability is reached at about 20% increase in objective value.
- On the Chicago network, a fully explainable solution is obtained with less than 3% increase in objective value.
- Explainable shortest path is NP-hard for general directed graphs with cycles-allowed or 2-vertex-disjoint path reductions, but polynomial for DAGs and minimum spanning tree problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase explainability weight while allowing only a small increase in nominal objective value | Explainable shortest path · Synthetic shortest path | relative explainability score: around 0.7 -> more than 0.9; around 20% increase in objective value | Helped |
| Increase explainability weight to obtain a fully explainable solution | Explainable shortest path · Real street network shortest path | objective value increase: less than 3% | Mixed |
| Measure solution similarity only across the three bridge edges instead of all edges (ablation) | Explainable shortest path · Synthetic shortest path | optimality reduction for fully explainable solutions: 10% | Hurt |
Surprising findings
- Enforcing full explainability when only bridge edges define solution features costs only about 10% optimality on average in the synthetic case.
- Restricting path revisits (edge progressions) with constant feature set size yields polynomial solvability, while simple paths are NP-hard.
Limitations
- Explainability is defined via user-chosen features whose comprehensibility is not quantified.
- Explainable shortest path with cycles is NP-hard, so the MIP formulation is needed in general.
- Using only historic favorable solutions may yield unfair solutions applied repeatedly.
Experimental setup
Datasets: synthetic grid graphs with 50 perturbed historical instances Chicago road network velocity data (4363 historical scenarios, 538 nodes, 1287 edges)
Benchmarks: synthetic two-grid graph with three bridges Chicago road network
Metrics: relative optimality score relative explainability score pareto front
Baselines: nominal shortest path (alpha=1)
Builds on: shortest path problem weighted sum scalarization
Closest papers by meaning
- Paths, Proofs, and Perfection: Developing a Human-Interpretable Proof System for Constrained Shortest Paths (AAAI 2024 · similarity 0.87)
- Decision Information Meets Large Language Models: The Future of Explainable Operations Research (ICLR 2025 · similarity 0.85)
- Finding Simple Proofs for First-Order Optimization (NeurIPS 2026 · similarity 0.84)
- What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization (NeurIPS 2025 · similarity 0.83)
- Autoformulation of Mathematical Optimization Models Using LLMs (ICML 2025 · similarity 0.83)
- Even-if Explanations: Formal Foundations, Priorities and Complexity (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.