A Framework for Inherently Interpretable Optimization Models

Due to the existence of explicitly stated models and well defined solution processes, researchers in operations research and optimization can have high confidence in the correctness and usefulness of found solutions. If discrepancies between the real-world application and the found solution occur, the underlying model is usually adapted within a feedback cycle. Overall, this design process gives confidence in the validity of the solution. After obtaining a satisfactory model that reflects all conditions, solutions are expected to be employed in various settings, i.e. parameters are adapted, yielding new solutions for every special case.

However, explaining why a solution (e.g. a production plan) of type A is implemented today, while type B was used yesterday is not an easy task. While it is possible to explain the model that is being used, the function that maps a model to a solution is complex and not necessarily explainable. Furthermore, solvers are able to provide necessary and sufficient optimality conditions, and sensitivity analysis can yield a better understanding of the specifics of an optimal solution. But most of such checking and validation tools—often communicated in a very formal, mathematical language—are only accessible to experts, that already have a high confidence in the process. Indeed, even understanding a (linear) programming model can quickly become a challenging task, especially for people not familiar with modeling techniques. Users with less mathematical and computer background, e.g. the planner using the optimization software and the workers in charge of implementing the result, may consider the solver a black box. This raises the question whether a solution is acceptable for the end user, or the object of the optimization process (the worker). Workers directly affected by the optimized decision may wish to understand them and obtain knowledge about future outcomes in order to asses when one has to work overtime or on weekend shifts. Not being able to answer such questions may lead to discontent and loss of trust and result in weak adoptions of optimized decisions.

We argue that non-theoretical and easily comprehensible explanations have to be available in order motivate actions obtained from optimization programs. In particular, justifications of why a system recommends certain actions are more relevant for non-experts than explanations of how the solution is obtained [MB00, YJ95]. Providing the underlying optimization model might not be useful here, as, “disclosure alone does not guarantee that anyone is paying attention or is able to accurately interpret the information; more complex information is more likely to be unexamined or misunderstood” [Pra05]. In [SPVR01] the authors argue that employees’ identification with their company is stronger, the more adequate information they receive about their company and their personal role within the company. Furthermore, effective and transparent communication and explanations play a vital role in fostering trust and positive employee-organization relationships [Raw08, MS14, YMF19, WXW18]. Decision models that are complex and difficult to understand can result in skepticism and reluctance to adopt or use the system that was actually designed to support decision making, even if the models have been shown to improve decision-making performance [ACC${}^{+}$06, KDBL${}^{+}$09]. In [KDBL${}^{+}$09] the authors argue that a decision-support system “must be designed to induce an alignment of a decision maker’s mental model with the decision model”.

Therefore, providing insights into decisions obtained from optimization processes is an important task for managers. Incorporating workers into the feedback cycle of the modeling process can be one important part and providing explanations during this process improves the feedback loop [CSGK19]. After a model is created workers still are in need of more easily comprehensible explanations of when and why different solutions are considered. Furthermore, end users often have the need of being able to explain decisions obtained from an AI, e.g. for loan [SYX${}^{+}$20, SMF21] or medical consultants [SCDS77, Swa85, LSG${}^{+}$19]. Even the European “right to explanation” tries to ensure that users can ask for an explanation of an algorithmic decision that was made about them [GF17].

We first introduce a mixed-integer programming formulation for the problem of minimizing $F_p\left(a\right)$ when we restrict the explanatory rule to the form of a univariate, binary decision tree of fixed depth. The application of such a tree can be seen as a series of yes/no queries, to reach a leaf that corresponds to a solution. Let $Q\in N$ be the number of queries, called splits, and thus $K=2^Q$ is the number of leaves of the decision tree. The $k$-th leaf is associated with solution $x^k\in X$. To ensure comprehensible rules, we let the split at each level $q$ of the decision tree be the same in each subtree and furthermore only a single entry of the cost scenario vector $c_j\in R^n$ of the materialized scenario $j\in \left[N\right]$ is queried and compared to a threshold value $b^q\in R$. Binary variables $d_i^q$ indicate whether entry $i$ of the cost vector is queried in split $q$ of the decision tree. Let $a_j^k$ be the indicator whether in scenario $j\in \left[N\right]$ the traversal of the decision tree reaches leaf $k\in \left[K\right]$.

Each leaf can be described via a binary representation of the split outcomes. To this end let $S_q\subseteq \left[K\right]$ contain the leaves $k$ where in binary representation of $k-1$, the $q$th digit is 1, e.g. for $Q=2$ splits and $K=4$ leaves, we have $S_1=\{2,3\}$ and $S_2=\{1,3\}$ using the binary representation as shown in Table 3.

Using this notation, we propose the following mixed-integer formulation.

While Constraints (1b) demand that each scenario is mapped to exactly one solution, Constraints (1c) ensure comprehensibility by restricting each split in the decision tree to query only a single parameter. Constraints (1d) and (1e) describe each split of the decision tree and mirror the traversal of a scenario through the different levels: Assume $b^q$ and $d^q$ are already fixed. Then for each scenario $j\in \left[N\right]$ and split $q\in \left[Q\right]$ either ${\sum }_{i\in \left[n\right]}{c}_{ji}{d}_i^q\le b^q$ or ${\sum }_{i\in \left[n\right]}{c}_{ji}{d}_i^q>b^q$ holds. Depending on the outcome the decision tree is traversed to the right or to the left, and hence either one of the leaves to the right or to the left of the current node has to be reached which is indicated via ${\sum }_{k\in S_q}{a}_j^k$ for sufficiently large $M$ and sufficiently small $ϵ$.

We can add bounds to the threshold values $b^q$ using ${min}_{i,j}{c}_{ji}\le b^q\le {max}_{i,j}{c}_{ji}$ for each $q$ to improve numerical stability. The optimization criterion (1a) as well as the optimization domain (1f) remain general and the type (linear, quadratic, etc.) and thus the tractability of this model vary from case to case.

As a special case, we consider the Laplace criterion, i.e., we are interested in explanatory rules yielding solutions that perform well on average. This optimization criterion can be realized within the scope of Model (1) by using the quadratic objective function $L\left(a\right)={\sum }_{k\in \left[K\right]}{\sum }_{j\in \left[N\right]}{a}_j^k{\sum }_{i\in \left[n\right]}{c}_{ji}{x}_i^k$ that adds up the costs of the solutions chosen in every scenario. If a linear model is of interest, linearization options are possible, e.g. by introducing auxiliary variables $z_j\in R_{\ge 0}$, using objective function $F_p\left(a\right)={\sum }_{j\in \left[N\right]}{z}_j$, and adding constraints

which force $z_j$ to take the cost of the unique solution $k\in \left[K\right]$ associated with scenario $j\in \left[N\right]$ according to the decision tree.

In the proposed model, Restrictions (1c) ensure that each split within the decision tree only considers a single dimension of the cost vector $c$. While this feature is used for the sake of comprehensibility, it also gives a computational benefit. Given a constant tree depth $Q$, there are $O\left(n^Q\right)$ possibilities to set variables $d_i^q$. Once we fix which dimension $i$ to query in split $q$, we can enumerate all possible values for $b^q$. Let us assume that $d_i^q=1$ for some fixed $q$ and $i$. Consider the set $\{c_{ji}:j\in [N\left]\right\}$ of values in dimension $i$. Let us sort the values of this set, and consider all midpoints between two subsequent sorted values. Then, this set of midpoints contains an optimal choice for $b^q$, as we can enumerate all possible separations of values in this dimension. Hence, there are $O\left(N\right)$ possibilities to set $b^q$.

If all $d_i^q$ and $b^q$ variables are fixed, variables $a_j^k$ become fixed as well. Hence, the remaining optimization problem is to minimize the criterion ${\mu }_p({\sum }_{k\in \left[K\right]}{a}_1^k{c}_1^{\top }{x}^k,\dots ,{\sum }_{k\in \left[K\right]}{a}_N^k{c}_N^{\top }{x}^k)$ with a fixed assignment of solutions to scenarios. We refer to these problems as subproblems. If subproblems can be solved in $O\left(T\right)$, this means that the interpretable optimization problem can be solved in $O\left(n^Q{N}^{Q}T\right)$.

In the special case of the Laplace decision criterion, we have that

This means that we need to solve $K$ separate nominal problems, where the costs in each such problem are given by the sum of costs of scenarios that have been assigned to this $k\in \left[K\right]$. Hence, the interpretable optimization problem can be decomposed to $O\left(n^Q{N}^{Q}K\right)$ nominal problems. In general, if $\mu$ is decomposable (see [JBA14]), it is possible to consider $K$ separate problems to solve the subproblem.

The connection to decision trees as they are used in classification problems suggests the use of a greedy heuristic to solve the interpretable optimization problem. The main idea is that instead of considering all $n^Q{N}^Q$ possible combinations to determine splits in the decision tree, we determine the splits one level after the other.

We first enumerate all possible splits on the first level. That is, we solve a problem with $Q=1$ by enumerating all possible values for variables $d_i^1$ and for the threshold $b^1$. We hence solve $O\left(nN\right)$ subproblems in this first step.

We then fix the best of these candidate splits and consider the next level. That is, we solve a problem with $Q=2$, where we only need to enumerate the possible values for variable $d_i^2$ and $b^2$. Again, there are $O\left(nN\right)$ subproblems to be solved.

By repeating this procedure until a desired depth $Q$ is reached, a feasible solution has been found in $O\left(QnNT\right)$. Note that this means the depth $Q$ has been moved from being an exponent in the full enumeration approach, to being a factor in the heuristic. Further note that by construction, the greedy heuristic is optimal for $Q=1$.

In case of the Laplace criterion, the first subproblem consists of solving two nominal problems, the second subproblem consists of solving four nominal subproblems, and so on. In total, we need to solve $O\left(nN{\sum }_{q=1}^Q{2}^q\right)=O\left(nNK\right)$ nominal problems to construct a greedy decision tree.

In order to obtain explanatory rules that are applicable in practice, the input needed to evaluate the rule and retrieve the suggested solution has to be available. So far, the cost value in each dimension of the realized scenario functions as the input for the rule. The ability to retrieve this information at any point in time can be questionable and highly depends on the use case itself. But even if the cost parameters cannot be observed, scenarios—in particular in the case of real world data—often contain more information than seemingly useful for the problem at hand. For example traffic data might not only contain travel times, but also information regarding time and date and even could be augmented to contain weather data or other information that potentially has an impact on the decision: In a shortest path setting it is intuitively clear that an optimal path from the eastern to the western part of a town can depend on the daytime, the day of the week or the weather conditions. Hence, when trying to find easily comprehensible, high quality rules for future scenarios this kind of information should not be dismissed.

In order to utilize meta data, the general model proposed in Section 3 can be used by expanding the problem domain $X$ by $m$ dummy variables, where $m\in N$ is the dimension of the available meta data. Each dummy variable $x_{n+i}$ for $i\in \left[m\right]$ should be forced to zero by demanding $x_{n+i}=0$ in $X$ in order to stop these non-cost information to affect the objective function. The entry $c_{j,n+i}$ for meta information $i$ in scenario $j$ does not contain the “cost”, but the realized value in this observed scenario, e.g. if for each scenario the day of the week is known, then $c_{j,n+i}$ is a value between 1 and 7.

While implementing this augmentation can be done in a straight-forward manner, expert knowledge of the underlying problem is useful in order to obtain concise explanatory rules. Picking up on the shortest path setting, one useful split in the decision tree could try to separate rush hour times. Let us assume that rush hour is from 6am to 9am and the time stamp of each scenario is stored in a minute-by-minute precision starting at midnight represented by the value 0 until one minute before midnight represented by the value 1439. In order to determine whether a scenario occurs within the rush hour, two decision tree levels are needed, where the first one checks whether it is after 6am, i.e. $c_{j,n+i}\ge 360$ and a second one checks $c_{j,n+i}\le 540$. However, if the relevance and characteristics of the rush hour are known, the separation of such scenarios could be achieved by a single split at the cost of having to pre-process the data. In the described case, one option could be to shift the time-stamp interpretation such that time stamp 0 represents scenarios at 6am, making the split $c_{j,n+i}\le 180$ sufficient in order to identify a rush hour scenario. In fact, it might even be replaced by a 0/1 attribute to indicate if this scenario takes place within the rush hour or not. Another way could be to partition the time stamp information into eight clusters with each three hour duration. This way, instead of having a single data point “time stamp”, eight indicator values can be used to represent the clusters. Thus, 6am to 9am scenarios could be determined by splitting on the third entry, only.

So far the changing parameters only affected the quality and not the feasibility of a solution, i.e. the feasible set of solutions $X$ remained the same in all scenarios. If a scenario also affects the feasible region, each scenario $j$ induces a different feasibility set $X^j$, where the $k$-th solution $x^k$ only has to satisfy the feasibility sets of the scenarios $j$ it is assigned to via $a_j^k$. We denote

and demand that $x^k\in X^{k,j}\left(a\right)$. Assuming that $X^j$ can be stated via a linear constraint system $A^{j}x\le b^j$, $x^k\in X^{k,j}\left(a\right)$ can be enforced via

with $M$ being a vector with sufficiently large entries, such that in case of $a_j^k=0$ these constraints are trivially fulfilled. If with probability $ϵ\in [0,1]$ a solution is allowed to not obey the respective feasibility set, additional auxiliary variables $g_j\in \{0,1\}$ can be used with ${\sum }_{j\in \left[N\right]}{p}_j{g}_j\le ϵ$ and the feasible region is given by

With the goal of obtaining easily comprehensible explanatory rules we restricted ourselves to univariate decision trees (cf. Constraints (1c) and (1h)). Depending on the use case, multivariate decision trees might also be appropriate. A model that can be used to obtain a binary decision tree that allows more general linear splits can be formulated using the following constraints to replace (1c-1e).

In order to ensure comprehensibility of the resulting decision tree we uphold in (3a) and (3b) that at most $P\in N$ non-zero entries are allowed in each ${\ell }^q$, i.e., we still aim for sparse rules. Furthermore, we use a normalization constraint ${\sum }_{i\in \left[n\right]}|{\ell }_i^q|=1$ to mitigate numerical issue arising from the use of $ϵ$ and $M$ in the same constraints. Only allowing integer coefficients can further reduce numerical issues, to the expense of the model’s computability.

When using the enumeration approach or the greedy heuristic for multivariate decision trees, more combinations need to be taken into account. If $P$ is a constant, we can still enumerate all possibilities for binary variables $d_i^q$, of which at most $P$ can be active. Values for ${\ell }_i^q$ and $b^q$ can then be enumerated by considering all $P$-dimensional hyperplanes defined through the costs $c_{ji}$. However, such approaches become computationally too expensive with higher values of $P$.

So far the splits used in the decision tree were the same at every level of the tree. This was done in order to maintain the highest possible level of comprehensibility as in this setting the same $Q$ split criteria have to be checked regardless of the scenario. However, having different splits depending on the current region reached while traversing the decision tree can also be of interest, as solutions with higher quality are obtainable with only a slight decrease of comprehensibility. Having the number $K$ of considered solutions and thus the number of leaves of the decision tree fixed, we now have to decide on the splitting criterion in each of the $K-1$ internal nodes. In order for one leaf to be reached, the splits of the $Q$ nodes traversed to reach this leaf have to be set accordingly.

Following the notation as in [BD17] we denote as $A_L\left(k\right)$ the set of ancestors of the leaf representing solution $k$ whose left branch has to be chosen in order to reach this leaf, and $A_R\left(k\right)$ are the remaining nodes on the path from the root to this leaf. By keeping the notation that $a_j^k$ indicates whether solution $k$ is chosen in scenario $j$, but changing $q$ to the index of an internal node rather than the level of the splitting node, Constraints (1d) and (1e) (or for the multivariate case Constraints (3d) and (3e)) have to be replaced by the following two constraints

With Constraint (1b) each scenario is associated with exactly one leaf and with the above constraints the splitting criteria along the path leading from the root to this leaf have to be met.

Using such decision trees in the enumeration method or the greedy heuristic is directly possible, but means that more variable combinations have to be enumerated. In case of the enumeration method, $O\left(Q^Q{n}^Q{N}^Q\right)$ subproblems need to be solved, while the greedy heuristic needs to consider $O\left(KnN\right)$ subproblems.

In the proposed model it is assumed that the costs of implementing solution $k$ in scenario $j$ are represented via $c_j^{\top }{x}^k$. However, providing the option of being able to implement solution $x^k$ might also be associated with costs that are independent of the scenario realization. The existence of first-stage costs is a common feature in multi-stage robust and stochastic optimization. For example, in disaster management preparatory actions are necessary in order to be able to eventually deploy a specific emergency response plan. In order to reflect this option in the model we enlarge the domain to contain a variable vector $y\in R^{\pi }$ that is associated to preparatory actions that have to be adequate for all potential future solutions $x^k$. In particular for all solutions $k$ the pair $(y,x^k)$ has to part of the new domain $\overline{X}\subseteq R^{\pi }\times X$, ensuring that the performed preparations enable the realization of solution $x^k$. By adding the cost term ${\hat{c}}^{\top }y$ to the objective function and modeling the connection between preparation and implementation in $\overline{X}$ the original model can easily be adapted to deal with such a factor.

To compare the performance of the optimal interpretable solution found by solving the mixed-integer programming formulation proposed in Section 3.1 with the performance of the greedy heuristic from Section 3.3, we generate shortest path problems on grid graphs. We create small quadratic grids of $5\times 5$ nodes. Each node is connected to its up to four horizontal and vertical neighbors, i.e., there are 40 edges. Edges are oriented upwards and to the right. The origin is placed on the bottom left corner, while the destination is placed on the top right corner. To create scenarios, we generate fives types $t$, each given by its own midpoint ${\mu }_e^t$ for each edge $e$ and a deviation range ${\delta }_e^t$. Midpoints are sampled uniformly i.i.d. from $[10,30]$ and deviations from $[0,0.25]$. To generate a scenario, we first choose a type $t$ and then sample each edge costs uniformly i.i.d. from $\left[\right(1-{\delta }_e^t){\mu }_e^t,(1+{\delta }_e^t\left){\mu }_e^t\right]$. This means that each problem instance contains five types of scenarios, which enables us to test the degree to which optimization models are able to make use of this structure. We consider instances with $\{5,6,\dots ,20\}$ scenarios for training and 1000 scenarios for testing. For each number of scenarios, 100 instances are created (a total of $16\times 100=1600$ instances).

For each instance, we solve the optimization model (1) (denoted as IP2 and IP4 when using $K=2$ and $K=4$ solutions, respectively) and we run the greedy heuristic (denoted as G2 and G4). We compare the solution time of each approach, as well as the performance on training and test instances of the resulting explanatory rules. We measure performance in the following way. Let $f\left(\xi \right)$ denote the objective value of the solution found by some method in scenario $\xi$. Let $f^{nom}\left(\xi \right)$ denote the objective value of the nominal solution, i.e., the solution that minimizes the sum (or average) of objective values over all training scenarios. Finally, let $f^{opt}\left(\xi \right)$ denote the optimal objective value for scenario $\xi$. The performance of $f$ in scenario $\xi$ is then calculated as

which means that a value of 100% gives an optimal solution in scenario $\xi$, whereas a value of 0% means that there is no improvement over the nominal solution. We consider the average of these performance values over all scenarios.

Figure 2 shows the average performance for training scenarios and test scenarios, for different numbers of training scenarios. Note that it can be expected that the performance on training scenarios has a tendency to decrease with more training scenarios, as more scenarios need to be considered simultaneously. At the same time, more training scenarios should lead to a better performance on test scenarios. Our results confirm this behavior.

In Figure 2(a), G2 and IP2 have identical performance, and thus both lines are on top of each other. This is to be expected, as the greedy heuristic places a single decision in an optimal way. Comparing G4 and IP4, there is a performance difference of about 5 percentage points on the training data.

On test instances (see Figure 2(b)), it is possible that G2 and IP2 have different performance values, as optimal solutions are not necessarily unique. There is no clear preference of one method over the other. We note that IP4 again outperforms G4, but the difference between both methods has become smaller. In some cases, G4 even shows a slightly better average performance than IP4. Overall, the greedy heuristic gives a reasonable approximation of the optimal solution on these instances.

Compare this relatively small loss in performance with the improvements in median computation times, as shown in Figure 3. Note the logarithmic vertical axis.

While the greedy method scales well with an increased number of scenarios, this is not the case for the integer program. For 20 scenarios (the largest problems considered in this experiment), IP4 is around two orders of magnitude slower than G4. Also note that plotting median times benefits the IP methods, as they are more prone to outliers than the greedy methods. In summary, the greedy method gives a good trade-off between small computation times and larger performance values, and will thus be the method we consider in our subsequent experiments.

In this second experiment, we consider the possible disadvantage resulting from using explanatory rules over formulations that do not consider this restriction. To this end, we use the greedy heuristic to find explanatory rules, and compare with the performance of the min-sum-min model with two (MSM2) and with four solutions (MSM4). Performance is measured in the same way as in Experiment 1. We again use grid graphs, but consider larger instances with 10 times 10 nodes (180 edges) and a number of training scenarios in the range $\{10,15,\dots ,50\}$. We generate 100 instances for each number of training scenarios (a total of $9\times 100=900$ instances). For each instance, we first run the greedy heuristics G2 and G4 and then assign the computation times as time limits for MSM2 and MSM4, respectively. While this may create a bias towards the greedy methods (which have exactly as much computation time as they need), this approach avoids setting an arbitrary time limit for the MSM methods.

In Figure 4, we present the average performance on training and on test instances. G4 achieves nearly the same performance of MSM4 on training instances (see Figure 4(a)), with a performance difference of about one to two percentage points. Interestingly, G2 even outperforms MSM2, which is only possible due to the time limit applied to the latter method.

On test instances (see Figure 4(b)), we note that the usage of our explanatory rules show a drop in performance for small sizes of training sets. This indicates that the rules learned on these sets do not yet generalize well to other scenarios. As the number of scenarios in the training set increases, the performance of greedy again comes close to that of MSM. While G2 reaches the same performance as MSM2, the difference between G4 and MSM4 remains at around three percentage points.

We show median computation times of the greedy methods in Figure 5. As predicted in our analysis, there is a clear linear relationship between the number of scenarios in the training set and computation time. Also note that running G4 takes about three times as long as running G2 (note that G4 needs to first run G2, and then run an additional iteration where four nominal problems need to be solved for every split candidate instead of two problems, which results in three times the effort of G2).

Summarizing these results, we find that explanatory rules only lead to a small decrease in performance compared to general decision rules on the instances we considered, in particular, if sufficient training scenarios are available. At the same time, the linear solution time of the greedy method means that our approach scales well in problem size.

In this third experiment, we consider real-world data collected in [CDG19]. The graph models the road network of Chicago with 538 nodes and 1308 edges. Travel speeds were taken from a live traffic interface over a 46-day time horizon. The dataset we use contains all measurements that were made (a total of 4363 scenarios). These are split by using one half for training, and one half for testing. We generate 100 random source-sink pairs. To avoid path problems where both nodes are too close to each other, we generate a nominal path for each source-sink candidate, and repeat the sample while the number of edges in the nominal path is less or equal to 50.

To reduce computation times, we randomly skip checking each split candidate on the existing 1308 edges with 95% probability, which means that the greedy heuristic is sped up by factor 20. Additionally, we extend the instance by two artificial edges to capture meta data on scenarios. These edges loop into an additional, separate node, so that they are never part of a path. On the first edge, we use the day of the week of a scenarios as its lengths, encoded as integer numbers from one (Monday) to seven (Sunday). On the second edge, we use the time within the day, encoded as seconds since midnight, i.e., an integer from 0 to 86399.

We use the greedy heuristic to find explanatory rules using all 1310 edges, and also using only the two edges carrying meta data. The median computation time for the first setting is 1209.5 seconds (two solutions) and 3450.5 seconds (four solutions), while the second setting results in median computation times of 126.4 seconds (two solutions) and 363.1 seconds, respectively.

In Table 4, we show the average performance for both settings. While it is possible to slightly improve upon the nominal solution using only meta data, this improvement is small. Significantly larger improvements are possible when using the full data of the graph. Indeed, if we consider the first splitting decisions of this approach (i.e., the rule that G2 finds), only 1 in 100 runs use the day of the week (split between Monday to Saturday and Sunday), and 8 in 100 runs use the time of the day. In Figure 6, we highlight which edges were split on in the remaining 91 cases. We note that in particular the edges along the shore of Lake Michigan in the north-east are used for this purpose. A possible explanation is that these edges see continuous high-density traffic, which makes them reliable predictors to identify the traffic scenario.

If we only consider the meta data, there are five cases where G2 splits on the day (once between Friday and Saturday, four times between Saturday and Sunday). The remaining splits are made on the time of the day. In Figure 7, we present a histogram of these decisions, where each bin represents an hour of the day. The majority of splits cut off few scenarios on the boundary of the day, in particular in the first and in the last hour. This underlines the small improvements that these rules give, see Table 4. Traffic speed is highly volatile, and the data represents snapshots at particular points in time, rather than averages over larger time horizons. Hence, explanatory rules such as ”before 7am” and ”after 7am” do not perform as well as one might intuitively expect.

Our computational experiments have been designed to answer three questions. The first is concerned with a comparison of the greedy heuristic and the mixed-integer programming formulation to find explanatory rules in form of a decision tree. Recent research on decision trees for classification models (see [BD17]) reports promising results when constructing optimal decision trees. In our setting, computation times quickly increase to become prohibitive for larger problems. The greedy heuristic scales well (linearly in the number of scenarios) and is a viable choice also for larger optimization problems. At the same time, the quality of solutions found by the heuristic is close to that of exact solutions, which makes the heuristic the preferred solution method for the remaining experiments.

The second question considers the loss that occurs when we use an explanatory rule instead of an arbitrary rule to make decisions. Our experiments show that on training data, there is little difference between both approaches. This is different on test data, where an insufficient training size leads to interpretable solutions that do not perform well. With more training data available, we can again observe that explanatory rules show a performance that is very close to more general rules. Hence, these results seem to encourage the use of explanatory rules.

Finally, we consider the performance of our approach on real-world data. While the previous experiments constructed scenarios is a way that there exists inherent structure that can be exploited, this is not necessarily the case for the considered data set. Indeed, improvements over nominal solutions towards the lower bound are significantly smaller, but still useful with up to around 20%. It seems that particularly high-density edges give reliable predictions which of the candidate solutions to use.

The results presented here are, naturally, only valid within the scope of the setup we used. At the same time, none of our methods were specifically designed for the shortest path problem, which underlies all experiments. Hence, we can expect to find a similar performance of our approach for different optimization problems.