  Linear programming is a powerful method in combinatorial optimization with
many applications in theory and practice. For solving a linear program quickly
it is desirable to have a formulation of small size for the given problem. A
useful approach for this is the construction of an extended formulation, which
is a linear program in a higher dimensional space whose projection yields the
original linear program. For many problems it is known that a small extended
formulation cannot exist. However, most of these problems are either
$\mathsf{NP}$-hard (like TSP), or only quite complicated polynomial time
algorithms are known for them (like for the matching problem). In this work we
study the minimum makespan problem on identical machines in which we want to
assign a set of $n$ given jobs to $m$ machines in order to minimize the maximum
load over the machines. We prove that the canonical formulation for this
problem has extension complexity $2^{\Omega(n/\log n)}$, even if each job has
size 1 or 2 and the optimal makespan is 2. This is a case that a trivial greedy
algorithm can solve optimally! For the more powerful configuration integer
program, we even prove a lower bound of $2^{\Omega(n)}$. On the other hand, we
show that there is an abstraction of the configuration integer program
admitting an extended formulation of size $f(\text{opt})\cdot
\text{poly}(n,m)$. In addition, we give an $O(\log n)$-approximate integral
formulation of polynomial size, even for arbitrary processing times and for the
far more general setting of unrelated machines.
