  Plug-in electric vehicles (EVs) are widely recognized as being highly
flexible electric loads that can be pooled and controlled via aggregators to
provide low-cost energy and ancillary services to wholesale electricity
markets. To participate in these markets, an aggregator must encode the
aggregate flexibility of the population of EVs under their command as a single
polytope that is compliant with existing market rules. To this end, we
investigate the problem of characterizing the aggregate flexibility set of a
heterogeneous population of EVs whose individual flexibility sets are given as
convex polytopes in half-space representation. As the exact computation of the
aggregate flexibility set -- the Minkowski sum of the individual flexibility
sets -- is known to be intractable, we study the problem of computing
maximum-volume inner approximations to the aggregate flexibility set by
optimizing over affine transformations of a given convex polytope in half-space
representation. We show how to conservatively approximate these set containment
problems as linear programs that scale polynomially with the number and
dimension of the individual flexibility sets. The inner approximation methods
provided in this paper generalize and improve upon existing methods from the
literature. We illustrate the improvement in approximation accuracy and
performance achievable by our methods with numerical experiments.
