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

Question

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.

Answer 1

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.