  Counterfactual explanations (CFE) are being widely used to explain
algorithmic decisions, especially in consequential decision-making contexts
(e.g., loan approval or pretrial bail). In this context, CFEs aim to provide
individuals affected by an algorithmic decision with the most similar
individual (i.e., nearest individual) with a different outcome. However, while
an increasing number of works propose algorithms to compute CFEs, such
approaches either lack in optimality of distance (i.e., they do not return the
nearest individual) and perfect coverage (i.e., they do not provide a CFE for
all individuals); or they cannot handle complex models, such as neural
networks. In this work, we provide a framework based on Mixed-Integer
Programming (MIP) to compute nearest counterfactual explanations with provable
guarantees and with runtimes comparable to gradient-based approaches. Our
experiments on the Adult, COMPAS, and Credit datasets show that, in contrast
with previous methods, our approach allows for efficiently computing diverse
CFEs with both distance guarantees and perfect coverage.
