  It is well known that selecting a good Mixed Integer Programming (MIP)
formulation is crucial for an effective solution with state-of-the art solvers.
While best practices and guidelines for constructing good formulations abound,
there is rarely a systematic construction leading to the best possible
formulation. We introduce embedding formulations and complexity as a new MIP
formulation paradigm for systematically constructing formulations for
disjunctive constraints that are optimal with respect to size. More
specifically, they yield the smallest possible ideal formulation (i.e. one
whose LP relaxation has integral extreme points) among all formulations that
only use 0-1 auxiliary variables. We use the paradigm to characterize optimal
formulations for SOS2 constraints and certain piecewise linear functions of two
variables. We also show that the resulting formulations can provide a
significant computational advantage over all known formulations for piecewise
linear functions.
