Let's now look at how to solve the corresponding separation problem using the so called Gomory cuts.
Assume we are solving the linear relaxation of the problem by means of the simplex method and let x* be an optimal basic solution corresponding to the basic matrix B.
If x* is not integer, then at least one of its basic components, say that of index q in the basis, has to be fractional.
Now, let's consider the Chvátal inequality induced by the q-th row of the inverse of the matrix B.
It is easy to verify that in this inequality all the coefficients of the basic variables are null except for the one of the variable of index B(q) which is 1. Let's evaluate this inequality in the solution x*. Since all the non basic components of x* are null, the left hand side of the inequality reduces to the value of the component of index B(q) of x*. This component is fraction by hypothesis and thus strictly greater than its floor. This means that inequality (1) is violated by x* and thus, when we add it to the current formulation, the solution x* is no longer feasible.
