Feature Selection for Data-driven Explainable Optimization

Kevin-Martin Aigner 1 , Marc Goerigk 2 , Michael Hartisch 1,2 , Frauke Liers 1 , Arthur Miehlich 1 , Florian Rösel 1 · 2025

Read Feature Selection for Data-driven Explainable Optimization by Kevin-Martin Aigner 1 , Marc Goerigk 2 , Michael Hartisch 1,2 , Frauke Liers 1 , Arthur Miehlich 1 , Florian Rösel 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-12184.txt.

Introduction

Kevin-Martin Aigner and co-authors define in 2025 a feature selection problem for explainable optimization. Solvers can find optimal solutions, but black-box results are often hard for humans to grasp. A data-driven view calls a solution explainable if it resembles past solutions used in similar cases.

Similarity must be measured on a small set of features chosen from a large pool. The authors prove the selection problem is computationally hard in the formal sense. They build math models for it and test local heuristics. Experiments on realistic data show the problem can be solved efficiently enough for mid-size instances.

Catalog record

CREATORKevin-Martin Aigner 1 , Marc Goerigk 2 , Michael Hartisch 1,2 , Frauke Liers 1 , Arthur Miehlich 1 , Florian Rösel 1
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-12184

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Feature Selection for Data-driven Explainable Optimization Kevin-Martin Aigner 1 , Marc Goerigk 2 , Michael Hartisch 1,2 , Frauke Liers 1 , Arthur Miehlich 1 , Florian Rösel 1 Abstract . Mathematical optimization, although often leading to NP-hard models, is now capable of solving even large-scale instances within reasonable time. However, the primary focus is often placed solely on optimality. This implies that while obtained solutions are globally optimal, they are frequently not comprehensible to humans, in particular when obtained by black-box routines. In contrast, explainability is a standard requirement for results in Artificial Intelligence, but it is rarely considered in optimization yet. There are only a few studies that aim to find solutions that are both of high quality and explainable. In recent work, explainability for optimization was defined in a data-driven manner: a solution is considered explainable if it closely resembles solutions that have been used in the past under similar circumstances. To this end, it is crucial to identify a preferably small subset of features from a presumably large set that can be used to explain a solution. In mathematical optimization, feature selection has received little attention yet. In this work, we formally define the feature selection problem for explainable optimization and prove that its decision version is NP-complete. We introduce mathematical models for optimized feature selection. As their global solution requires significant computation time with modern mixed-integer linear solvers, we employ local heuristics. Our computational study using data that reflect real-world scenarios demonstrates that the problem can be solved practically efficiently for instances of reasonable size. 1. Introduction Mathematical optimization plays a crucial role in solving complex real-world problems by providing optimal solutions, even for large-scale instances. The research focus has traditionally been on achieving optimality, basically neglecting explainability of obtained solutions. In applications where human beings are affected, it is however essential not only to determine optimal outcomes but also to ensure that these solutions are explainable and understandable to decision-makers. Without explanation, decision-makers may not trust or understand the reasoning behind the outcomes. If the process of finding a solution is perceived as a black box, it risks being ignored, even if the solution itself is globally optimal. Explanations bridge the gap between mathematical rigor and practical usability, increasing the likelihood of their real-world adoption. There are only very few works on explainable mathematical optimization. In this paper, we utilize the data-driven approach presented in [ 2 ] , where a solution is considered explainable if it closely resembles solutions that have been used in the past under similar circumstances. The framework works as follows: A set of instances along with historical solutions is given. Each instance is described via a set of features, such as resource availability, cost information, or contextual factors, like weather conditions or seasonality. A metric to quantify pairwise distances between instances is provided. Similarly, each solution is characterized by a set of features, including key indicators, structural properties, or other relevant attributes, with a corresponding metric to measure the similarity between solutions. To express the explainability of a solution, the most similar historical instances are identified based on instance feature distances within a predefined threshold. The explainability score is then computed as the sum of the solution feature distances between the current solution and the solutions associated with these historical instances. As for this framework the instance features are assumed to be given as input, we now study the question of how to select a high-quality set of instance features where similarity can be measured. The corresponding instance feature selection problem can be solved as a preprocessing step, after which the existing explainable optimization framework can be utilized. While feature selection is a standard task in Artificial Intelligence, only few works have considered this problem in optimization-related tasks, often integrated within some optimization model. For explainable optimization, it is important to select a preferably small set of instance features because this simplifies explainability of a solution, making it easier to understand. Our contributions: • We give a formal definition of the feature selection problem in explainable mathematical optimization. We clarify its complexity by proving that it is NP-complete in general. • We present a mixed-integer linear mathematical optimization model for optimal feature selection. While it turns out that its global solution by available mixed-integer linear optimization gets too demanding already for small instances, the feature selection problem can be solved satisfactorily by local search heuristics. • Computational results for shortest path problems with realistic data show that optimized feature selection is beneficial in explainable optimization. In particular, typically only a very small set of features suffices to explain a solution. The set of features can be computed within reasonable computational time. Outline: To ensure being self-contained, we repeat the framework for data-driven explainability in Section 2 . We summarize the state-of-the-art in the relevant literature on feature selection in Section 3 . Section 4 defines the feature selection problem for explainable optimization and shows that it is NP-complete in general. Building on this, Section 5 introduces mathematical optimization models to solve the problem outlined in Section 4 . As their global solution is typically too time-consuming, we explain our local K -opt heuristics in Section 6 . An extension of our approach that enables affine combinations of features is discussed in Section 7 . Computational results are presented in Section 8 . We conclude with a short summary and future research questions in Section 9 . 2. Problem Setting We write vectors in bold, and use the notation [n]:=\{1,\ldots,n\} to denote index sets. We study mathematical optimization problems for which {\mathcal{I}} is the set of all instances and \mathcal{X}\subseteq\mathbb{R}^{n} is the general domain of feasible vectors. For each instance I\in{\mathcal{I}} , let {{\mathcal{X}}(I)}\subseteq\mathbb{R}^{n} be the corresponding solution space. We call f^{I}:{{\mathcal{X}}(I)}\rightarrow\mathbb{R} the objective function of I and f^{I}(x) the objective value of x\in{{\mathcal{X}}(I)} . The nominal optimization problem that minimizes the objective function over the feasible set of instance I is given by (Nom) \min_{{\boldsymbol{x}}\in{\mathcal{X}}(I)}f^{I}({\boldsymbol{x}}). The data-driven framework for explainability in mathematical optimization introduced in [ 2 ] relies on the existence of high quality data consisting of historic instance-solution pairs. Assume we have N>0 data points (I^{i},x^{i},\lambda^{i}) , where I^{i}\in{\mathcal{I}} is a full description of the i -th historic instance, x^{i}\in\mathcal{X}(I^{i}) is the employed solution, and \lambda^{i}\in[-1,1] is a confidence score with which a solution x^{i} is considered optimal in instance I^{i} . We consider feature functions \phi_{\mathcal{I}}:{\mathcal{I}}\rightarrow{\mathcal{F}}_{\mathcal{I}} and \phi_{\mathcal{X}}:{\mathcal{I}}\times{\mathcal{X}}\rightarrow{\mathcal{F}}_{\mathcal{X}} that aggregate information of instances as well as solutions within features spaces {\mathcal{F}}_{\mathcal{I}}\subseteq\mathbb{R}^{p} and {\mathcal{F}}_{\mathcal{X}}\subseteq\mathbb{R}^{q} , respectively. We define two metrics d_{{\mathcal{I}}}:{\mathcal{F}}_{\mathcal{I}}\times{\mathcal{F}}_{\mathcal{I}}\rightarrow\mathbb{R}_{\geq 0} and d_{\mathcal{X}}:{\mathcal{F}}_{\mathcal{X}}\times{\mathcal{F}}_{\mathcal{X}}\rightarrow\mathbb{R}_{\geq 0} as similarity measures for instances and solutions, respectively. All functions involved are assumed to be computable in polynomial time and space. We consider a new instance I\in{\mathcal{I}} for which we want to find an explainable solution. Let (Sim-Set) S_{\epsilon}(I)=\{i\in[N]\mid d_{\mathcal{I}}(\phi_{\mathcal{I}}(I),\phi_{\mathcal{I}}(I^{i}))\leq\epsilon\} be the set containing the most similar historic instances with threshold \epsilon\geq\min_{i\in[N]}d_{\mathcal{I}}(\phi_{\mathcal{I}}(I),\phi_{\mathcal{I}}(I^{i})) . For \beta\geq 0 , the following bicriteria optimization model is proposed: (Exp) \min_{x\in{{\mathcal{X}}(I)}}\ \left\{f^{I}(x),\sum_{i\in S_{\epsilon}(I)}\frac{\lambda_{i}d_{{\mathcal{X}}}\left(\phi_{\mathcal{X}}(I,{\boldsymbol{x}}),\phi_{\mathcal{X}}(I^{i},{\boldsymbol{x}}^{i})\right)}{1+\beta d_{\mathcal{I}}\left(\phi_{\mathcal{I}}(I),\phi_{\mathcal{I}}(I^{i})\right)}\right\}. The first objective is the objective function of the nominal problem. The second objective represents the explainability of solution x . To calculate this value, we consider all similar historic instances in S_{\epsilon}(I)

Read the complete text