  We propose a generalization of the standard matched pairs design in which
experimental units (often geographic regions or geos) may be combined into
larger units/regions called "supergeos" in order to improve the average
matching quality. Unlike optimal matched pairs design which can be found in
polynomial time (Lu et al. 2011), this generalized matching problem is NP-hard.
We formulate it as a mixed-integer program (MIP) and show that experimental
design obtained by solving this MIP can often provide a significant improvement
over the standard design regardless of whether the treatment effects are
homogeneous or heterogeneous. Furthermore, we present the conditions under
which trimming techniques that often improve performance in the case of
homogeneous effects (Chen and Au, 2022), may lead to biased estimates and show
that the proposed design does not introduce such bias. We use empirical studies
based on real-world advertising data to illustrate these findings.
