  Inspired by branch-and-bound and cutting plane proofs in mixed-integer
optimization and proof complexity, we develop a general approach via Hoffman's
Helly systems. This helps to distill the main ideas behind optimality and
infeasibility certificates in optimization. The first part of the paper
formalizes the notion of a certificate and its size in this general setting.
The second part of the paper establishes lower and upper bounds on the sizes of
these certificates in various different settings. We show that some important
techniques existing in the literature are purely combinatorial in nature and do
not depend on any underlying geometric notions.
