We introduce new techniques for matched block design in multi-arm experiments. In matched block design, units with similar covariate values are grouped into blocks, with one unit per treatment in each block. Existing methods for unit-level block design often fail to produce optimal matches for multi-arm experiments. We present a mixed integer programming (MIP) formulation that guarantees optimal solutions for the general multi-arm matched blocking problem using a clique-based equipartitioning approach. For cases where the MIP is computationally infeasible, we introduce heuristics that decompose large problems into tractable subproblems while providing explicit quality-runtime tradeoffs. We demonstrate that our methods significantly outperform existing techniques on a diverse test suite, achieving consistent improvements in block balance quality. Additionally, we show how these methods can be adapted to improve covariate balance across treatment groups. We demonstrate that matched block design presents an interesting application area for metaheuristic and exact optimization methods.