# How to get an integer solution from rational solution in simplex algorithm?

How to get an integer solution from rational solution in simplex algorithm?

recategorized

This is explained on slides 77-79 (Simplex Algorithm on Integer Numbers). The idea is as follows: We first compute a rational solution. For every variable that has a non-integer solution, we enforce that the simplex algorithm will push it to either the next greater or next lower integer by changing the bound of that variable. We may have to repeat that for the other variables until an integer solution is found.
by (170k points)
selected
Thanks for the explanation.

Is it possible to have multiple solutions for a given set of equations, like if we pivot a violating variable with other variable as taken in solution, the answer comes different.
Yes, that is possible. The simplex algorithm traverses the corners of the polyhedron specified by the inequalities and you may choose different paths for that traversal by choosing the variables for pivoting. As there may be several solutions, you may find also different ones this way.

+1 vote