  Explainability of decisions made by AI systems is driven by both recent
regulation and user demand. These decisions are often explainable only
\emph{post hoc}, after the fact. In counterfactual explanations, one may ask
what constitutes the best counterfactual explanation. Clearly, multiple
criteria must be taken into account, although "distance from the sample" is a
key criterion. Recent methods that consider the plausibility of a
counterfactual seem to sacrifice this original objective. Here, we present a
system that provides high-likelihood explanations that are, at the same time,
close and sparse. We show that the search for the most likely explanations
satisfying many common desiderata for counterfactual explanations can be
modeled using mixed-integer optimization (MIO). In the process, we propose an
MIO formulation of a Sum-Product Network (SPN) and use the SPN to estimate the
likelihood of a counterfactual, which can be of independent interest.
