We present a mixed integer linear programming approach to orthogonally block two-level, multilevel, and mixed-level orthogonal designs. The approach involves an exact optimization technique which guarantees an optimal solution. It can be applied to many problems where combinatorial methods for blocking orthogonal designs cannot be used. By means of 54-run and 64-run examples, we demonstrate that our approach outperforms two benchmark techniques in terms of the number of estimable two-factor interaction contrasts and in terms of the D-efficiency for models with main effects and some two-factor interaction contrasts. We demonstrate the generic nature of our approach by applying it to the most challenging instances in a catalog of all orthogonal designs of strength 3 with up to 81 runs as well as a small catalog of strength-4 designs. The approach can also be applied to strength-2 designs, but, for these cases, alternative methods described in the literature may perform equally well. Supplementary materials for this article are available online. © 2015 American Statistical Association and the American Society for Quality.