I'm following a description of the Branch and Bound Method.
But I don't understand at all, that if you assume a MILP problem has an optimal solution it implies that the relaxation problem has also an optimal solution.
Let
$$\mbox{MILP}:\hspace{0,2cm} \mbox{min}\left\lbrace c^Tx + h^Ty \mid (x,y) \in S \right\rbrace $$
Where $S=\left\lbrace (x,y) \in \mathbb{Z}^n_+ \times \mathbb{R}^p_+ \mid Ax+Gy =b\right\rbrace $.
Assume that MILP admits a finite optimum.
Then if
$$\mbox{LP}_0:\hspace{0,2cm}\mbox{min}\left\lbrace c^Tx + h^Ty \mid (x,y) \in P_0 \right\rbrace $$ where $P_0=\left\lbrace (x,y) \in \mathbb{R}^n_+ \times \mathbb{R}^p_+ \mid Ax+Gy =b\right\rbrace$, there is an optimal solution for $LP_0$.
The intuition say me that it must be truth because if you don't have an optimal solution in $LP_0$ is becuase you are not in a bounded region so you get contradiction.
Best Answer
Consider minimizing $x_1$ subject to $x_1=\sqrt{2}x_2$, with $n=2$ and $p=0$. The only integer feasible solution is $(0,0)$, but the LP relaxation is unbounded.