Knapsack problem: Maximize $24 x_1 + 2 x_2 + 20 x_3 + 4 x_4$
subject to $8 x_1+ 1 x_2+ 5 x_3+ 4 x_4 ≤ 9$
$x$ is binary for $i = 1,2,3,4$
How can I find a gomory cut for this problem? I think that $x_1 + x_3 \le 2$ would be a gomory cut, but I am not sure. I have no idea how I can be sure.
Welcome to Math.SE! I'm going to assume that you are referring to what is sometimes called a Chvatal-Gomory or CG cut.
The knapsack system is given in matrix form by $$ \begin{pmatrix}8&1&5&4\\1&&&\\&1&&\\&&1&\\&&&1\end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\\x_4\end{pmatrix}\leqslant \begin{pmatrix}9\\1\\1\\1\\1\end{pmatrix} $$ along with the requirement that the vector $x\in\mathbb{Z}^4_+$. We may write this system as $Ax\leqslant{b}$. To derive a CG (Gomory) cut, we pick some vector $u\geqslant0$ in $\mathbb{R}^5$, and compute the vector $u^\text{T}A$ and the scalar $u^\text{T}b$. If we let $\big(u^\text{T}A\big)_i$ denote the $i^\text{th}$ component of the vector $u^\text{T}A$, then the CG (Gomory) cut is given by $$ \sum_{i=1}^4\lfloor(u^\text{T}A)_i\rfloor x_i\leqslant\lfloor u^\text{T}b\rfloor. $$ The trick to this is picking the vector $u$ correctly. For an example, let's use $u=(1/8,0,0,0,1/2)$. Then $$ u^\text{T}A=\bigg(1,\frac{1}{8},\frac{5}{8},1\bigg) \quad\text{and}\quad u^\text{T}b=\frac{13}{8}. $$
Taking the floor of all these values, we obtain $$ \lfloor u^\text{T}A\rfloor=\big(1,0,0,1\big) \quad\text{and}\quad \lfloor u^\text{T}b\rfloor=1. $$ (I am abusing notation here--the symbol $\lfloor u^\text{T}A\rfloor$ means to compute the vector $u^\text{T}A$, then take the floor of each entry of the vector one at a time). Hence, our CG cut is $$ x_1+x_4\leqslant 1.$$ If you look at it, this cut makes sense--it says that we cannot take both item 1 and item 4.
