  We consider the {\em Shaped Partition Problem} of partitioning $n$ given
vectors in real $k$-space into $p$ parts so as to maximize an arbitrary
objective function which is convex on the sum of vectors in each part, subject
to arbitrary constraints on the number of elements in each part. In addressing
this problem, we study the {\em Shaped Partition Polytope} defined as the
convex hull of solutions. The Shaped Partition Problem captures ${\cal N}{\cal
P}$-hard problems such as the Max-Cut problem and the Traveling Salesperson
problem, and the Shaped Partition Polytope may have exponentially many vertices
and facets, even when $k$ or $p$ are fixed. In contrast, we show that when both
$k$ and $p$ are fixed, the number of vertices is polynomial in $n$, and all
vertices can be enumerated and the optimization problem solved in strongly
polynomial time. Explicitly, we show that any Shaped Partition Polytope has
$O(n^{k{p\choose 2}})$ vertices which can be enumerated in $O(n^{k^2p^3})$
arithmetic operations, and that any Shaped Partition Problem is solvable in
$O(n^{kp^2})$ arithmetic operations.
