Introduction
In mathematical optimization, the term "optimal" typically refers to the solution that minimizes a specific cost function. However, in practice, these mathematically perfect solutions—such as complex flight schedules or logistics routes—are often perceived as "black boxes" by the human operators responsible for implementing them. If a human planner cannot intuitively understand why a specific route was chosen over a more familiar one, they may lose trust in the system and reject the solution entirely.
While Explainable AI (XAI) has become a cornerstone of machine learning, mathematical optimization has traditionally been viewed as inherently interpretable due to its basis in clear logic and constraints. This paper challenges that assumption, arguing that logical transparency does not equate to human explainability. The authors propose a novel framework that justifies solutions through precedent: "We chose this path because it is similar to successful actions taken in similar past scenarios."
The Bicriteria Framework
The researchers introduce a bicriteria optimization framework that balances the traditional "nominal" cost (optimality) with a second objective: Explainability.
Similarity-Based Logic
The core of the framework is the "Exp" model, which defines explainability through analogy. A solution is considered explainable if it does not deviate significantly from "accepted" historical data. To achieve this, the model identifies a set of historical instances most similar to the current problem and penalizes the optimization engine for choosing solutions that differ from those past precedents.
Feature Functions and Complexity
To measure similarity, the authors use feature functions to map complex data into a feature space where distances (e.g., Manhattan or Hamming distance) can be calculated. Interestingly, the authors prove that adding this layer of explainability increases the computational complexity of the problem. For instance, while the standard shortest path problem is solvable in polynomial time, the "explainable" version can become NP-hard in general graphs because the model must simultaneously solve for pattern matching and optimization.
Experimental Setup
The framework was evaluated using two distinct setups:
- Synthetic Testcase: A $6 \times 6$ grid graph representing two city districts connected by three "bridges," used to visualize how the model chooses between different intuitive routes.
- Real-World Road Network: A dataset of the Chicago road network featuring 538 nodes and 1,287 edges. This dataset included over 4,300 historical traffic scenarios based on actual bus driver velocity data.
Key Results and the "Small Prize" for Trust
The most significant finding of the study is the shape of the Pareto front—the curve representing the trade-off between optimality and explainability. The results suggest that decision-makers do not have to sacrifice much efficiency to gain a substantial amount of trust.
In the Chicago road network experiments, the authors found that a fully explainable solution could be achieved with an increase in travel time of less than 3%. Furthermore, even a marginal 1% increase in nominal cost allowed for a massive jump in the explainability score.
Interestingly, the study also noted a "baseline explainability" of approximately 0.7 (on a 0 to 1 scale) for standard optimal solutions. This indicates that mathematically optimal paths often naturally align with past human behavior to a significant degree, but the framework allows for closing the remaining gap to full explainability with minimal effort.
Discussion and Future Work
Despite the theoretical NP-hardness of the explainable shortest path problem, the authors' Mixed-Integer Programming (MIP) formulation for the Chicago network solved in just a few seconds, demonstrating the practical viability of the approach.
However, the authors highlight several areas for future research:
- The "Echo Chamber" Risk: Learning from historical data risks reinforcing past inefficiencies or biases. If historical solutions were flawed, the "explainable" model will replicate them.
- Fairness: Always choosing the most explainable (precedent-based) solution could lead to unfair outcomes, such as repeatedly assigning the same unpopular shifts to the same employees.
- Automated Feature Engineering: Currently, humans must define which features make a solution explainable. Future work aims to develop methods to automatically discover which features most effectively drive human trust and comprehension.
Summary updated