"Explanations" are an important field of research and a prerequisite for a successful real-world deployment of any data science and analytics application. Unfortunately, the "explanations" that are currently provided rarely explain anything. Nor do they actually help provide the one benefit that solution context should: risk mitigation.
Types of Optimization "Explanations"
Roughly, the field currently focuses on the following types of "explanations."
- Proof of Correctness. This is rarely even mentioned, but naturally everything an algorithm does, even one that provides explanations, is always subject to the correctness of the computer program and its execution. An optimization solver may provide traces and logs that highlight potential problems, for example, when the problem is ill-conditioned and machine precision becomes a factor during the solution process. (Since formal algorithm verification is hard, the "explanation" for using a particular solver should consist in thoroughly conducted test results.)
- Proof of Optimality. This is, in the word sense, the only real explanation that is being considered in the field. (In the word sense, an explanation is an account of the why. Therefore, an explanation for an optimal solution would have to include a reason why the solution provided is not worse than any other.) In a linear program, short optimality proofs do exist, and we may be able to provide a dual solution that shows that one cannot do better than what was provided. For NP-hard problems, however, we do not know how to provide short proofs in general (and they may not even exist if NP != co-NP).
- Proof of Infeasibility. Just as there are most likely no short optimality proofs for NP-hard problems, we have no algorithms that provide a short proof that no solution exists. We therefore often revert to providing a smaller subset of constraints that jointly exclude all possible solutions.
- Proof of Feasibility. One should think that this was a given in modern solvers. Unfortunately, even some modern MIP solvers do not check constraint feasibility (within the limits of machine precision) for their integer solutions. Instead, they often relax the notion of integrality itself and only enforce that each integer variable has a value that is "close" to an integer. Consequently, a feasibility check is typically added as a post-optimization step by thorough users.
- Sensitivity Analysis. In its easiest form, the solver may return the set of constraints that limit the solution quality the most. This can sometimes even take the form of a quantitative analysis of the type "If we had one more unit of this resource, we could maximally improve our objective by $x" (so-called "shadow prices"). Sensitivity analysis can also mean to what extent inputs can change their value without affecting the solution's feasibility and optimality.
- Plausibility Tests and Solution Pools. Some optimization environments allow investigating trade-offs and generating alternatives by answering questions of the type "What is the best solution if I set this variable to that value?" Instead of answering specific questions, they may also provide entire sets of solutions that are, in some metric, diverse. This can allow users to incorporate external information in their decision-making process, which was not incorporated in the model. For example, a decision-maker may identify features in the optimal solution that cause execution brittleness and settle for a sub-optimal solution that appears to be more robust.
User Stories
Before we check what information is crucially missing, let us first consider when and by whom explanations are actually being used and for what purpose.
- Before Model Deployment. In this case, explanations are not used to check the concrete action recommendations provided but to scrutinize the model implementation and solver performance themselves, usually based on historical inputs with known outcomes or the ability to conduct counterfactual analysis. In this setting, "explanations" serve the purpose of test-driving the new technology. The main questions: Was our business process modeled correctly, and do the recommendations "make sense?" Both model developers and stakeholders may use "explanations" at this point, primarily to see if the model formulation leads to solutions that are of practical value, whether solution time expectations or limits are in order, trade-off between different KPIs are handled correctly, etc.
- After Model Deployment. In this setting, the user or an automated checker may try to assure that the solution that is about to be executed is "sane." If the beneficiary of the explanation is an actual person, it is rarely either the modeler or the original business stakeholder, but someone whose task it is to monitor the ongoing business process. The purpose of the "explanation" in this scenario is primarily to prevent nonsensical, risky, or potentially very harmful plans from ever reaching the execution level.
- For strategic 'one-off' decisions, model development and deployment may happen at the same time. In essence, we massage the model and iterate over different trade-offs, objectives, safety levels, scenarios, etc., while churning the one and only problem instance at hand repeatedly, thereby producing a pool of different solutions, each optimized for a different formulation for the exact same situation. In this case, the modeler and/or stakeholder may consult "explanations" to guide the exploration of different courses of action that are available and may be considered for potential execution.
Solution Context
From here on out, rather than calling everything an "explanation," let us use more precise terminology. As noted earlier, most of the additional information provided does not constitute an actual explanation. The only true explanation, a proof of optimality or infeasibility, cannot (unless NP=co-NP) be provided in a compact form that would allow a practical review. And in the case of an LP, where a compact proof of optimality does exist, the correctness of the solution is implied by the correctness of the solver itself.
So let us talk about solution context instead. It is more than an academic exercise to use precise terminology. In the context of optimization, the term 'explanation' always evokes the idea of rationalizing why a specific solution is the right one, the best one, and the only one to be selected. It not only bears the connotation of persuasion. It sounds condescending that the user needed to be educated. The reason why stakeholders reject optimization is also this attitude of optimization experts who enter the room with "provably optimal" solutions.
In none of the user stories above is persuasion the purpose of providing more than merely a variable assignment and a corresponding objective function value. By providing solution context, we either seek to assert and stress-test our model (and potentially change it; user stories 1 and 3) or we aim to assess and limit the risk of executing potentially poor solutions (user story 2). But assertion, stress testing, and risk mitigation are all part of a different branch of analytics research: assurance.
Assurance
Solution context serves but one purpose: to assure that our solutions reliably enable superior business results. And that means, just as in data science, that optimization must put the following guardrails around their analytics:
- Data Assurance. If the data in the model are wrong, all bets are off. The derived recommendations, the assessment of feasibility and performance, and even the "explanations" provided: everything hinges on the validity of the data that enters the model. This means we must assess noise and bias, strive to detect errors and attacks, and quantify uncertainty in the forecasts that enter the optimization model. Solution context must therefore include an assessment of the data that enters our model, highlighting any potential issues.
- Model Assurance. The model is always an imperfect approximation of the world. Before a model is deployed (user stories 1 and 3), we must ensure that the model is accurate where necessary. If we use linear approximations to nonlinear functions, we must ensure that the error introduced cannot significantly affect the quality of the solutions. If we linearly aggregate multiple objectives into one, we must ensure that the trade-off between the objectives is indeed a constant. If we use averages of uncertain forecasts in our model, we must ensure that our assessment of solution quality is still accurate.
Handling Uncertainty
And this is where OR "explanations" fall short. Textbook OR problems all work with deterministic data and a model that is, per definition, accurate. But:
- Almost no one has a pure knapsack problem. Both resource consumption and profits are usually estimates that come with inherent uncertainty.
- Almost no one has a travelling salesperson problem. Travel times and service times are estimates that come with inherent uncertainty.
- Almost no one has a job shop problem. Machines break down, demand fluctuates, people get sick, and materials arrive late. Everything that hits the shop floor comes with inherent uncertainty.
And this means, with absolute certainty, that performance cannot be represented by one value. Because as inputs change, so do outputs. Your costs and profits and service levels, they all fluctuate with the inputs. But, of course, we have to make our decisions before we know the actual inputs. Otherwise, we would simply defer our optimization until the time when we have deterministic knowledge.
Therefore, the most important solution context that an optimization application must provide is an assessment of how solution quality and feasibility change as uncertain inputs change.
In InsideOpt Seeker models, every stochastic term can be queried for its distribution. For this puzzle, e.g., we derived this context of our optimized investment strategy:
So rather than receiving a solution and a statement that it achieves an average return of $18,399, the user can see that the real results may vary between $4,000 and $55,000, depending on the inherent uncertainty in the inputs.
A curve like this builds more trust than any irreducible set of infeasible constraints ever will. Because it openly acknowledges what stakeholders have know all along: that outcomes cannot be predicted with certainty.
That the objective of optimization is not a proof of optimality, but to provide a rational, risk-mitigating course of action.