Standard LP vs Mixed-Integer LP Optimal solution.

Question

I have a question about standard LP optimal solution vs Mixed Integer LP optimal solution.

Let $z*$ denote the optimal value for $c \cdot x$ and $z^{int}$ to be the optimal value $c \cdot x$ for the mixed interger LP. Why is it that $z* \ge z^{int}$? $$ \max c \cdot x \\ \mathrm{s.t.} \quad Ax \leq b\\ x \geq 0 \\$$

$$ \max c \cdot x \\ \mathrm{s.t.} \quad Ax \leq b\\ x \geq 0 \\ x_{i} \in Z, i \in I $$

Answer 1

$z*\ge z^{int}$ because $z*$ is the optimal solution of the relaxation of the associated MILP. In other words it has less constraints, so the feasible space is larger: there are more potential good solutions.

Note that for a minimization problem, you would obviously have $z*\le z^{int}$.