If a solution exists for an optimization problem in LP and if there is a feasible integer solution then there exists a solution to the corresponding integer programming problem.
This is the basic concept behind the linear relaxation problems. It is easy to understand that if an optimal solution exists and an integer solution lies in the feasible region, then there exists a solution to the integer programming problem, also.
I think integer programming problems can be looked at as linear programming problems with some additional constraint lines (that can't necessarily be visualized) to make sure only integer solutions are in the feasible region. However, if I had to write a proof for this what would be the way to go?
Best Answer
I assume that when you say a "solution" exists for the LP version you mean an optimal solution. There are three possibilities for any optimization problem with a topologically closed feasible region: it might be infeasible; it might be unbounded; or it might have an optimal solution. Since we are talking about a linear program, the feasible region is automatically closed. (LPs are assumed to have equality or weak inequality constraints, never strict inequalities.) Your assumption rules out infeasibility of the integer version, so you just need to rule out unboundedness. Knowing that the LP is bounded is your key to that.