Use the BIP brach and cut algorithm to solve the following problem interactively.
$$\max \ z=2x_1-x_2+5x_3-3x_4+4x_5\\ s.t. 3x_1-2x_2+7x_3-5x_4+4x_5\le6\\ x_1-x_2+2x_3-4x_4+2x_5\le0 \\ x_j \\ binary$$
Attempt
First consider $x_1=0$, thus the new LP is $$\max \ z=-x_2+5x_3-3x_4+4x_5\\ s.t. -2x_2+7x_3-5x_4+4x_5\le6\\ -x_2+2x_3-4x_4+2x_5\le0 \\ x_j \\ binary$$
When solving this new LP using software yields no optimal solution which can be taken as a correct answer.
Then when I consider $x_1=1$ and after the substitution on the original LP, the software gives again the same answer no optimal solution.
From here I cannot construct the next brach, so the LP has no solution?
However I checked the solution given at the end of the book and it is $(0,0,1,1,1)$ with $z=6$.
Why is that?
I don't think the software it's wrong because I've tested with other LP's and returns the correct answer.
Could someone please help?
You have probably made a mistake as you entered the problem. I tried the problem with $x_1=0$ (since that eventually leads to a solution) and got x* = (0, 0, 1, 1, 1, 0, 0, 1, 0, 0). I have added my input of the LP relaxation below: