How to solve an Integer Programming problem using Gomory's Cutting Plane method, without using the Dual? This is a concept question.
Im not opposed to using the dual in practice. Im just curious why every lesson on the subject inevitably leads to using the dual. Since the principle is to derive a new inequality condition, which can be added to the original problem, it should be solvable using standard methods without relying on the dual. And yet, every attempt I make at doing just that, fails. Its not obvious to me why, or if Im doing something wrong.
I can solve the relaxed problem just fine and end up with non-integer solutions. Im just not sure how to make use of the new inequality constraint, as I seem to be having problems in practice.
Question. Is it essential that I use the dual? Is there some fundamental concept Im missing here wherein the dual is absolutely required? Or can I just derive the new inequality constraint and add it into the system as I originally had it when I solved the relaxed problem? And if so, how do I go about doing that in a way that is reliable and yields me progress? If the dual is not required, why does every video and text lesson end up with the dual problem? Because this consistent push to use the dual along with my seemingly inability to solve it in any other way implies to me that it is required, but I see no mathematical reason why it should be, and its never explicitly stated.
When you solve the linear programming with primal simplex method and get an optimal solution, you have feasible solution in primal and dual problem. After adding a gomory cut (constraint), your primal problem will be infeasible but dual problem is still feasible! Now you can choose 2 methods to solve this problem:
Hence dual simplex method is faster for us to solve the problem with gomory cutting plane method.
Now give an example.
\begin{align} \max \quad& z= x_1 + x_2 + x_3 \\ \text{s.t.} \quad& 2x_1 + 4x_2 + 5x_3 \le 20 \\ & 3x_1 + 2x_2 + 2x_3 \le 15 \\ & x_1, x_2, x_3 \ge 0 \space \text{(int)} \end{align}
Optimal solution is $x^* = (\frac{5}{2}, \frac{15}{4}, 0)$ with tableau
\begin{array}{r|rrrrr|c} & x_1 & x_2 & x_3 & s_1 & s_2 & \text{RHS} \\ \hline z & 0 & 0 & \frac{1}{8} & \frac{1}{8} & \frac{1}{4} & \frac{25}{4} \\ \hline x_2 & 0 & 1 & \frac{11}{8} & \frac{3}{8} & -\frac{1}{4} & \frac{15}{4}\\ x_1 & 1 & 0 & -\frac{1}{4} & -\frac{1}{4} & \frac{1}{2} & \frac{5}{2} \end{array}
Now we add gomory cut on variable $x_2$. so we have
$$\frac{3}{8}x_3 + \frac{3}{8}s_1 + \frac{3}{4}s_2 \ge \frac{3}{4}$$
Now you can solve the main problem with new constraint from the beginning and you should add artificial variable and solve the problem using two-phase simplex or big M method but if you want to solve this problem with dual simplex method, we have
\begin{array}{r|rrrrrr|c} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & \text{RHS} \\ \hline z & 0 & 0 & \frac{1}{8} & \frac{1}{8} & \frac{1}{4} & 0 & \frac{25}{4} \\ \hline x_2 & 0 & 1 & \frac{11}{8} & \frac{3}{8} & -\frac{1}{4} & 0 & \frac{15}{4} \\ x_1 & 1 & 0 & -\frac{1}{4} & -\frac{1}{4} & \frac{1}{2} & 0 & \frac{5}{2} \\ s_3 & 0 & 0 & -\frac{3}{8} & -\frac{3}{8} & \frac{3}{4} & 1 & -\frac{3}{4} \\ \end{array}
Now $s_3$ is leaving variable and $x_3$ is entering variable. Updated tableau is
\begin{array}{r|rrrrrr|c} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & \text{RHS} \\ \hline z & 0 & 0 & 0 & 0 & 0 & \frac{1}{3} & 6 \\ \hline x_2 & 0 & 1 & 0 & -1 & -3 & \frac{11}{3} & 1 \\ x_1 & 1 & 0 & 0 & 0 & 1 & -\frac{2}{3} & 3 \\ x_3 & 0 & 0 & 1 & 1 & 2 & -\frac{8}{3} & 2 \\ \end{array}
The optimal solution was easily obtained with this method!
Good luck.