Why does the cutting plane method for integer programming run in exponential time? I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. 
The algorithm consists in adding constraints to the initial problem in order to approximate the convex hull of the polyhedron. I understand the exponential complexity comes from the fact that the number of such valid inequalities is exponential. But why? 
 A: Consider $\min \{ c^Tx : x \in P \cap\mathbb{N}\}$ for some polyhedron $P$. When you replace $P$ with $P'$ where all extreme points of $P'$ are integral and there is no integer vector in $P$ that is not in $P'$, then by solving $\min \{ c^Tx : x \in P'\}$ with a method that returns a cornerpoint (e.g., the simplex method), you obtain an integer solution to the original problem.
A cutting plane method constructs $P'$ from $P$ by iteratively 'slicing off' parts of $P$ that do not contain integer solutions.
The question assumes that all cutting plane methods run in exponential time. That is not true. It is possible to add a small number of cutting planes (equal to the number of decision variables) and obtain the optimal solution to an integer optimization problem. To do that, you need to add the cutting planes that are the facet defining inequalities for $P'$ at the optimal solution. In practice, you do not know what those cutting planes are, so you end up adding many more cutting planes than necessary. That number of cutting planes can be exponential, as the following example shows.
Consider the problem $\max_{x \in \mathbb{N}^2} \{ x_2 : 2kx_1 + x_2 \leq 2k$, $-2kx_1 + x_2 \leq 0 \}$ for $k\in\mathbb{N}$. (For example, take $k=4$ and draw along.) The feasible region is a triangle between $(0,0)$, $(1,0)$ and $(0.5, k)$ intersected with $\mathbb{N}^2$. The optimal solution to the relaxed problem is the top of the triangle. If you multiply the first inequality with $2k-1$, the second inequality with $2k+1$, add, and round, you get the cutting plane $-x_1 + x_2 \leq k-1$, which invalidates the first solution. Visually, you can deduce the following series of cuts (i.e., linear inequalities with integer coefficients and an integer right-hand side):
$$x_1 + x_2 \leq k-1$$
$$-x_1 + x_2 \leq k$$
$$x_1 + x_2 \leq k-2$$
$$-x_1 + x_2 \leq k-1$$
etc, until you have added the last three cuts $-x_1+x_2 \leq 0$, $x_1+x_2 \leq 1$, and $x_1 + x_2 \leq 0$. Thus, the number of cuts needed is $2k+1$, which is exponential in the input size, which is $\mathcal{O}(\log k)$.
