Generating Rationales Based on Human Explanations for Constrained Optimization

Inga Ibs, Constantin A. RothkopfCommunications 2025 · DOI · OpenAlex

Abstract

Many constrained optimization problems, including those relevant to infrastructure planning, e.g., energy systems or logistics, can be effectively solved using white-box solvers based on linear programming. While these algorithms are well understood by the experts who developed them, explanations of the solutions they find are still necessary to communicate their implications to laypeople. However, it is unclear what such explanations should look like since the linear program solvers’ high-dimensional and abstract representations of the problem likely do not match human representations. Here, we propose an algorithm for finding rationales that align with human representations of constrained optimization problems. The proposed algorithm incorporates key insights from prior research on the structure, complexity, and representations of human explanations for constrained optimization. Specifically, we introduce a grammar of predicates derived directly from participants’ explanations and behavioral data from our previous studies on human optimization strategies. With a prior that regularizes rule complexity, this grammar forms the foundation of a rational rules model, which we use to generate rationales modeled after human explanations. Given that human explanations for constrained optimization problems reflect a sequential decision process, our approach searches the space of sequential solution representations within a Markov Decision Process to identify the most interpretable sequence and corresponding rationale. We evaluate our algorithm on human solutions and demonstrate that the generated rationales have a high dataset description score and complexity similar to human explanations, suggesting that the rationales capture human decision processes well and, therefore, align with the representations and structure of human explanations.

Introduction

Mathematical solvers for constrained optimization problems, such as linear programming, dictate critical real-world infrastructure decisions, from energy grid planning to healthcare resource allocation. While experts understand the "white-box" solvers (like the Simplex method) used to find these solutions, the explanations they produce are often highly abstract. Telling a policymaker that a decision represents an "optimal vertex on a polytope" is unhelpful. This paper introduces a novel algorithm that translates these abstract mathematical solutions into intuitive, human-like "rationales" by modeling the problem as a sequential decision-making process.

The Challenge of Abstract Solvers

Standard Explainable AI (XAI) methods, like sensitivity analysis, often fail to bridge the gap because they rely on the solver's global, mathematical representation. Humans, however, do not solve optimization problems by visualizing high-dimensional spaces. Instead, they use local, sequential heuristics. For example, in a resource allocation task, a human might explain their strategy as: "First, maximize immediate profit; then, balance the remaining materials."

Human explanation heuristics in the Furniture Factory task.

To address this, the authors utilize data from the "Furniture Factory" game, where participants manage production under constraints. The goal is to map the solver's global optimal output onto these intuitive, sequential human reasoning patterns.

Methodology: Bridging Math and Narrative

The proposed rationale-generation pipeline retroactively explains an optimal solution using human-like strategies through four main components:

  1. Formulating Solutions as MDPs: Instead of treating the solution as a static output, the authors model the optimization problem as a Markov Decision Process (MDP). This represents the solution as a sequence of state-action pairs (e.g., iteratively adding items to a build plan).
  2. Probabilistic Context-Free Grammar (PCFG): The authors define a domain-specific language based on human heuristics identified in prior cognitive science studies, such as immediate profit, balancing resources, and gap reduction.
  3. Probabilistic Program Induction: Using Logical Program Policies (LPP), the algorithm searches for rule combinations from the grammar that best match a given sequence of decisions, applying a complexity-regularized prior to favor simpler explanations.
  4. Heuristic Search: Because a final solution has no inherent order, the algorithm uses a search tree to simultaneously find the most logical sequence of actions and the rationale that best explains that sequence.
The rationale-generation pipeline using MDPs and Probabilistic Context-Free Grammars.

Experimental Evaluation

The approach was evaluated using two primary datasets: a Human Solutions Dataset (1,001 solutions from the Furniture Factory game) and a Synthetic Benchmark Dataset (100 randomly generated resource allocation problems).

Key results include:

  • High Alignment: On the human dataset, generated rationales successfully described 93% of the actions taken in participants' solutions.
  • Human-like Simplicity: The rationales matched human cognitive complexity; 43% consisted of a single heuristic program, and 95% fell within the same attribute complexity range as actual human explanations.
  • Generalization: On the synthetic benchmark, the algorithm achieved a high mean description score of 0.83, finding full rationales for over half the problems.

Discussion and Future Directions

While the algorithm provides a highly plausible, human-friendly narrative, it acts as a surrogate model. It provides a narrative for how a solution could be reached, but it does not faithfully represent the actual mathematical operations the solver used. While acceptable for laypeople, technical debugging still requires traditional mathematical XAI tools. Future work will focus on improving scalability for problems with high action counts and expanding the grammar to non-linear optimization tasks.

Summary updated

Abstract

Abstract Many constrained optimization problems, including those relevant to infrastructure planning, e.g., energy systems or logistics, can be effectively solved using white-box solvers based on linear programming. While these algorithms are well understood by the experts who developed them, explanations of the solutions they find are still necessary to communicate their implications to laypeople. However, it is unclear what such explanations should look like since the linear program solvers’ high-dimensional and abstract representations of the problem likely do not match human representations. Here, we propose an algorithm for finding rationales that align with human representations of constrained optimization problems. The proposed algorithm incorporates key insights from prior research on the structure, complexity, and representations of human explanations for constrained optimization. Specifically, we introduce a grammar of predicates derived directly from participants’ explanations and behavioral data from our previous studies on human optimization strategies. With a prior that regularizes rule complexity, this grammar forms the foundation of a rational rules model, which we use to generate rationales modeled after human explanations. Given that human explanations for constrained optimization problems reflect a sequential decision process, our approach searches the space of sequential solution representations within a Markov Decision Process to identify the most interpretable sequence and corresponding rationale. We evaluate our algorithm on human solutions and demonstrate that the generated rationales have a high dataset description score and complexity similar to human explanations, suggesting that the rationales capture human decision processes well and, therefore, align with the representations and structure of human explanations.
BibTeX
@inproceedings{ibs2025generating,
  author = {Inga Ibs and Constantin A. Rothkopf},
  title = {{Generating Rationales Based on Human Explanations for Constrained Optimization}},
  booktitle = {Communications},
  year = {2025},
  doi = {10.1007/978-3-032-08317-3\_8},
}
Figure