"For a mixed-integer linear programming model M with feasible solutions, by taking the non-zero valued variables from the linear relaxation solution of model M to construct the solution space of model M, is the integer programming model M guaranteed to have feasible solutions?"
As it is said that we consider/ study/ solve "M with feasible solutions" then the answer is 'yes'. However, an initial solution of M constructed from linear relaxation might not be feasible.
btw, a (relativly old) paper has shown an algorithm for finding a feasible point in a integer programming model:
this paper might help
https://www.jstor.org/stable/3690518
A Simplicial Approach to the Determination of an Integer Point of a Simplex
by Chuangyin Dang and Hans Van Maaren, Mathematics of Operations Research, Vol. 23, No. 2 (May, 1998), pp. 403-415
No, model M is not guaranteed to have feasible solutions when taking the non-zero valued variables from the linear relaxation solution of model M to construct the solution space. The linear relaxation solution provides a feasible solution to the relaxed version of the problem where the integer constraints are relaxed, allowing variables to take on fractional values.
When constructing the solution space of the integer programming model M using the non-zero valued variables from the linear relaxation solution, the resulting solution may violate the original problem's integer constraints. This means the constructed solution may have fractional values for the variables that should have been integers.
Hope it helps
- Badges
- Science method