11
$\begingroup$

In the machine learning community there is the big topic of explainability, where you want to make the solution of ML models explainable or derive explainable models.

This is also interesting for optimization, because the stakeholders sometimes want to know why the solution is optimal and this is not easy to explain.

What are approaches to this? Are there papers on this in the context of optimization?

$\endgroup$
1
  • 1
    $\begingroup$ For instance for linear programming it is common to teach duality theory. Now the dual solution provides dual variables also called reduced cost or shadow prices. They can be used to explain why the optimal solution is as it is. $\endgroup$ Jan 25 at 6:07
8
$\begingroup$

Solving: why is this solution optimal?

As Richard explained, the objective in OR is not "fuzzy" like in ML: we assume an objective that can be evaluated by the computer. Once the problem is specified, there is not much to explain: you can prove optimality or infeasibility directly.

Many solution methods attempt to prove optimality, and it is possible to get an optimality (or infeasibility) certificate from the solution process. This is trivial for LPs, and well known for SAT and MILP problem (see this paper for more information). When using heuristics you are out of luck, but can still compare the results to bounds obtained with other methods.

Modeling: what is a good solution?

But you asked how to explain the solutions to stakeholders.

Before you solve the problem, you have to model it in a way that matches the stakeholders' expectation of a good solution. The difficulty here is to specify what a good solution is. The stakeholders have domain knowledge that you don't, and many conflicting objectives. The goal is to specify the model with them so that they can understand the solutions: this is a matter of engineering and communication.

I suggest the answer to this question about OR industry projects for a better view of the issues at hand.

An example

The stakeholders may ask the OR team:

We want to minimize costs and downtime at our factory

This is not explainable: how do you compare a solution with 1 hour downtime and 100k cost, and one with 10 hours downtime and 20k cost? So the OR team will lead them to more explainable specifications.

For example, by ordering the objectives:

We want less than one hour of downtime if possible, and otherwise want to minimize the cost

Or by providing a conversion factor:

We can allow some downtime, if it saves at least 20k per hour

In both cases, it is easy to see which solution is better.

In practice

In practice, the stakeholders will have an idea of what a good solution looks like, but it will not always be easy to explain: they know it when they see it!

The task of the OR practitioners is to turn this domain knowledge into a model. A good way is to look at solutions with them, and understanding how they rank them. From there, it is generally possible to come up with an ordering of the objectives, or conversion factors, that they can agree with.

Just like in ML, it builds trust in the model when you can explain it, and is crucial for tool adoption. Compared to ML, the explanation stems from the specification, and is generally easy to understand for everyone involved.

$\endgroup$
4
  • $\begingroup$ (+1) Good Answer. "[H]ow do you compare a solution with 1 hour downtime and 100k cost, and one with 10 hours downtime and 20k cost?" I would also add sometimes you show them an array of solutions with the associated tradeoffs and let them decide what optimal is... $\endgroup$ Jan 25 at 16:01
  • $\begingroup$ We have models with 50K inputs and god knows how many variables and I can assure you: It is NOT easy for anyone to understand the solutions. And getting just one solution does not tell to which degree solutions imagined by the stakeholders are away from the objective value of the optimal solution. $\endgroup$
    – rwitzel
    Apr 22 at 11:26
  • $\begingroup$ @rwitzel I can sympathetize :D I didn't mean to imply that our job was easy, or that understanding the solutions is easy in general. My point is that there is no "explainability" for OR models in the same sense as in ML, and that OR is closer to typical software engineering in that respect. If you have a better formulation I'll take it :) $\endgroup$ Apr 22 at 19:54
  • $\begingroup$ @SecretAgentMan Good point. And yes, my simple example does not show how complex it is to specify and debug a model in practice $\endgroup$ Apr 22 at 20:02
7
$\begingroup$

In my view, mathematical optimization is inherently explainable for various reasons:

  • The model is "white-box", i.e. it is developed by a person defining all the variables and constraints. This means that if a certain constraint is active or inactive, there is a logical conclusion that can be drawn from this.

  • The result is, as you say, provably optimal. One can explain how to get there; I like to use the example of Google Maps, where the lower bound is the speed "as the crow flies", and then the actual solution is taking the highway, which is a little bit slower. By getting these things close to each other you can prove that something cannot be done better. In my book, this means I can explain it.

  • Using the values of the dual variables at the optimal solution you can explain how the objective function would change if one was to move in one direction or another away from the optimal solution; the dual variables are sometimes interpreted as the derivatives of the objective function along that particular constraint. In fact, even for a mixed-integer program, you could fix the discrete components and visualize this effect for the continuous variables. This "post-optimal" analysis, as it is sometimes called, is readily available and comes naturally out of the theory of mathematical optimization.

$\endgroup$
0
2
$\begingroup$

I assume one way to gain good level of interpretation of solver's result in optimization (especially in a high dimensional setting) is by doing something called Scenario Discovery. You can read more about this from linked papers here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.