# Why is the convex hull of a integer linear program a polyhedron with same optimum?

Given a MILP with feasible region $$P := \left\{ x \in \mathbb{R}^n \times \mathbb{Z}^p \mid Ax = b \right\}$$ with $$A \in \mathbb{R}^{m \times (p+n)}$$, $$b \in \mathbb{R}^{m \times 1}$$ and objective coefficients $$c \in \mathbb{R}^{n + p}$$, i.e. the MILP is $$\min_{x \in P} cx$$.

Why is $$\min_{x \in P} cx = \min_{x \in \text{conv}({P})} cx$$, i.e. why can we reduce integer programming to linear programming given the convex hull of $$P$$?

I think this is a well-known result of integer programming, but I wonder under which name / in which book I can find this result and a proof of it.

You can apply the convex hull's definition to an optimal solution $$x^*$$. It can be written as: $$x^* = \sum_{1 \leq k \leq m} \lambda_k x_k$$ such that $$\lambda_k \geq 0$$, $$\sum_{1 \leq k \leq m} \lambda_k = 1$$, $$x_k \in P$$ for all $$k$$, and $$m < \infty$$.
It's easy to see that by optimality, each $$x_k$$ should also be optimal (otherwise, we could improve the solution further). Hence: $$\min_{x \in \operatorname{conv}(P)} cx = c x_k.$$
On the other hand, by the inclusion $$\{x_k\} \subset P \subset \operatorname{conv}(P)$$, we have: $$c x_k \geq \min_{x \in P} cx \geq \min_{x \in \operatorname{conv}(P)} cx = c x_k,$$ which justifies the result.