  We propose an algorithm for generating explicit solutions of multiparametric
mixed-integer convex programs to within a given suboptimality tolerance. The
algorithm is applicable to a very general class of optimization problems, but
is most useful for hybrid model predictive control, where on-line
implementation is hampered by the worst-case exponential complexity of
mixed-integer solvers. The output is a simplicial partition which defines a
static map from the current state to a suboptimal solution. The primary
theoretical contribution of this paper is to introduce a non-zero optimal cost
overlap metric which is necessary and sufficient for convergence. The overlap
size is also linked to partition complexity. The algorithm is massively
parallelizable and our implementation, which is publicly available, is run on a
cluster of several hundred processors. Not only does our solution have a
deterministic runtime, simulations show that our approach is faster than
on-line optimization by up to three orders of magnitude.
