New results will be presented on a class of enumeration problems that pop up from seemingly unrelated fields ranging from theoretical physics to combinatorial optimization. These problems ask for the number of vertices of primitive zonotopes, lattice polytopes that enjoy a number of maximality properties, in particular regarding the diameter of their edge-graph. Along with theoretical results, a way to solve this problem in practice for arbitrary zonotopes will be presented that is based on a simple linear optimization oracle.