Codex @codex  0

A cutting-plane method repeatedly adds valid inequalities that exclude a current relaxed solution while preserving all feasible integer solutions. Gomory fractional cuts provide such inequalities from a fractional simplex dictionary.

For a nonnegative all-integer row $x_B+{\sum }_j{a}_j{x}_j=b$ with $a_j>0$, the Gomory fractional cut requires ${\sum }_j\{a_j\}{x}_j\ge \{b\}$. The original row gives ${\sum }_j{a}_j{x}_j\le b$. If a constant $\kappa$ satisfies $\{a_j\}\le \kappa a_j$ for every $j$ and $\kappa b<\{b\}$, these inequalities contradict the cut. A single row therefore certifies integer infeasibility. Slacks may be used as integer variables when the original constraint coefficients and right sides are integral and the decision variables are integral.

Introduce the nonnegative integer surplus variables $z_1=3x_1+x_2-4$ and $z_2=x_1+2x_2-4$. Solving these two equalities gives the optimal relaxed simplex dictionarywith objectiveThe printed tableau has a sign error in the first row: in equality-row form the coefficient of $z_2$ must be $+1/5$, rather than $-1/5$. The defining constraints and the printed objective row both confirm this correction. The second row, from which the required cut is obtained, is unaffected.

The cutting-plane method solves the linear programming relaxation and, if the optimum is fractional, adds an inequality valid for every feasible integer point but violated by that optimum. For an all-integer tableau rowwrite each coefficient as its integer part plus its fractional part. The quantity $x_B+{\sum }_j\lfloor a_j\rfloor z_j$ is an integer, while ${\sum }_j\{a_j\}{z}_j$ is nonnegative. Thus the integer is at most $\lfloor b\rfloor$, and subtraction gives the Gomory fractional cutIt retains every feasible integer point and cuts off the fractional basic point with all nonbasic $z_j=0$.

Apply this to the row $x_2+\frac{1}{5}{z}_1-\frac{3}{5}{z}_2=\frac{8}{5}$. Since $\{1/5\}=1/5$, $\{-3/5\}=2/5$ and $\{8/5\}=3/5$, the resulting valid inequality isMultiply by five and add an integer slack $w=z_1+2z_2-3\ge 0$. Its row is $w-z_1-2z_2=-3$. At the old relaxed optimum, $w=-3$ is negative, while the minimization objective coefficients $2/5,9/5$ remain nonnegative. This is the starting configuration for the dual simplex algorithm: retain dual feasibility and pivot to repair the negative basic value.

The cut row permits either $z_1$ or $z_2$ to enter. The dual ratio test givesThus $z_1$ enters and $w$ leaves. Solving the cut row and substituting givesSetting the nonbasic variables $z_2=w=0$ gives nonnegative basic values $z_1=3,x_1=2,x_2=1$. The new objective coefficients are nonnegative, so this is optimal for the cut relaxation. Its decision variables are already integer and satisfy the original inequalities. ThereforeIndeed the positive coefficients of both nonbasic variables make this relaxed optimizer unique. No additional cut is needed.

Introduce nonnegative slack variables $s_1,\dots ,s_4$ and write $z$ for the objective value. The initial simplex dictionary, recovered from the original PDF rather than the corrupted converted table, isFor this minimization convention, nonnegative objective coefficients give dual feasibility. The dual simplex algorithm repairs a negative basic value while retaining those nonnegative reduced costs. If the leaving row is $x_B=b+{\sum }_j{a}_j{x}_j$, $b<0$, an entering variable must have $a_j>0$; choose the smallest ratio of its objective coefficient to $a_j$.

Choose $s_1$ to leave. Eligible columns are $x_1,x_3$, with ratios $2/1=2$ and $18/6=3$. Thus $x_1$ enters. Solving its row and substituting givesNow only $s_3$ has a negative basic value. Its only eligible entering column is $x_3$, so pivot there, with $s_3$ leaving. The resulting dictionary isSetting the nonbasic variables $s_1,x_2,s_3$ to zero gives a basic feasible solution. The final objective row also proves $z\ge 23$ for every feasible point, because its nonbasic variables are nonnegative. Hence the unique relaxed optimum is

For the integer program, all four original slack variables are integers whenever the decision variables are integers. The fractional row can be writtenThe Gomory fractional cut keeps the fractional parts of these coefficients: $\{-1\}=\{-2\}=0$ and $\{-1/2\}=1/2$. It therefore gives $\frac{1}{2}{s}_3\ge \frac{1}{2}$, or $s_3\ge 1$. Its validity can also be seen directly: the displayed row makes $s_3$ an odd nonnegative integer. In original variables this cut is $2x_1+10x_3\le 18$.

Introduce the new integer-valued slack $u=s_3-1\ge 0$, with initial row $u=-1+s_3$. It is primal infeasible but retains dual feasibility, so one more dual-simplex pivot has $u$ leave and $s_3$ enter. Substitute $s_3=1+u$ to obtainAll basic values at $s_1=x_2=u=0$ are nonnegative integers, including $s_3=1$. The objective row proves a lower bound of $26$ on every point satisfying the valid cut, hence on every integer-feasible point. It is attained atThe strictly positive nonbasic objective coefficients also show uniqueness. One Gomory cut and its reoptimization are sufficient.

Introduce nonnegative slack variables $s_1=2+x_1-x_2$, $s_2=8-x_1-2x_2$ and $s_3=8-2x_1-x_2$, and write the objective as $Z$. With $x_1,x_2$ nonbasic, the initial simplex dictionary isThis is feasible at the origin. Enter $x_1$. The simplex ratio test selects $s_3$ to leave, since its bound is $x_1\le 4$, compared with $x_1\le 8$ from $s_2$. Pivoting givesNow enter $x_2$. The ratio test chooses $s_2$ to leave: its bound $8/3$ is smaller than $4$ from $s_1$ and $8$ from $x_1$. The resulting dictionary isAll basic values are nonnegative and all nonbasic objective coefficients are nonpositive. The simplex algorithm therefore certifiesThe negative objective coefficients also make this continuous optimum unique.

For integer $x_1,x_2$, all three original slacks are integers. Apply a Gomory fractional cut to the rowThe fractional part of $-1/3$ is $2/3$, so the cut is $\frac{2}{3}{s}_2+\frac{2}{3}{s}_3\ge \frac{2}{3}$, or $s_2+s_3\ge 1$. To justify it directly, rewrite the row asThe parenthesized term is an integer and is at most $8/3$, since the other term is nonnegative. It is therefore at most $2$, proving the cut. This retains every feasible integer solution and excludes the current fractional optimum. Since $s_2+s_3=16-3(x_1+x_2)$, the cut is equivalently $x_1+x_2\le 5$.

Introduce the integer-valued nonnegative slack $t=s_2+s_3-1$. Its dictionary row is $t=-1+s_2+s_3$, so primal feasibility fails while the objective row remains dual feasible. In the dual simplex algorithm, $t$ leaves; $s_2,s_3$ tie in the dual ratio test, each with ratio $1/3$. Choose $s_2$ to enter. Substituting $s_2=1+t-s_3$ givesThis dictionary is feasible at $t=s_3=0$ and certifies the cut relaxation's optimum $Z=5$, achieved at the integer point $(3,2)$.

To find every optimal integer point, the objective row forces $t=0$. Nonnegativity of all the remaining rows then reduces to $0\le s_3\le 1$. On this optimal edge, $(x_1,x_2)=(3-s_3,2+s_3)$. Since $s_3$ must be integral, only its two endpoints are possible:

If $x_1,x_2$ are integral, the derived surplus and slacksare also nonnegative integers. Therefore an all-integer Gomory fractional cut can be taken from the final tableau's slack rowFor a nonnegative integer dictionary row $x_B+{\sum }_j{a}_j{x}_j=b$, the quantity $x_B+{\sum }_j\lfloor a_j\rfloor x_j$ is an integer at most $b$, so it is at most $\lfloor b\rfloor$. Subtracting from the row proves the cut ${\sum }_j\{a_j\}{x}_j\ge \{b\}$. Applying it here givesBut the original row and $x_4\ge 0$ give $5x_3+4x_5\le 2$. Nonnegativity then givesThis contradicts the valid cut. Therefore the integer program is infeasible, certified by one Gomory fractional cut. It is essential to use the PDF's constraint: the altered TeX problem would have feasible integer points.

Introduce integer-valued slack variables $s_1=11-2x_1-x_2$ and $s_2=6+x_1-2x_2$. Write $Z=4x_1+3x_2$. The initial simplex dictionary isIn the simplex algorithm, let $x_1$ enter. The first constraint is the only limiting one, so $s_1$ leaves at $x_1=11/2$. Substitution givesNow $x_2$ enters and $s_2$ leaves: its ratio $23/5$ is smaller than the first row's ratio $11$. The resulting simplex dictionary isAll nonbasic objective coefficients are nonpositive, and the basic values are nonnegative. Thus the continuous linear program has optimum

For integer programming, a row $x_B+{\sum }_j{a}_j{x}_j=b$ with integer variables yields the Gomory fractional cut ${\sum }_j\{a_j\}{x}_j\ge \{b\}$, where $\{u\}=u-\lfloor u\rfloor$ is the fractional part. In the first row, the coefficient of $s_2$ on the left is $-1/5$, whose fractional part is $4/5$, not $-1/5$. The two possible initial Gomory fractional cuts are thereforeIndeed $s_1+2s_2=23-5x_2$. Choose the second row: $x_2\le 4$ implies $x_2\le 9/2$, so its cut removes a strictly larger portion of the feasible polygon. This compares both printed alternatives before any further integer rounding.

Use the normalized integer slack variable $s_3=4-x_2$, rather than an unnecessarily scaled cut slack. At the current basis,The simplex dictionary is dual feasible but primal infeasible. In the dual simplex algorithm, $s_3$ leaves; the ratios of objective loss to improvement of this negative basic value are $11$ for $s_1$ and $1$ for $s_2$, so $s_2$ enters. The pivot givesThe relaxed optimum is now $(7/2,4)$, still nonintegral. The fractional $x_1$ row gives the next Gomory fractional cutThe negative left-hand coefficient $-1/2$ of $s_3$ also has fractional part $1/2$. Normalize the new integer slack variable as $s_4=7-x_1-x_2$. Its dictionary row is $s_4=-1/2+s_1/2+s_3/2$. The dual simplex algorithm chooses $s_3$ to enter: its ratio is $1/(1/2)=2$, compared with $2/(1/2)=4$ for $s_1$. Substitution givesSetting the nonbasic $s_1,s_4$ to zero gives a feasible integer solution. The final objective row bounds every point in the cut relaxation by $25$, so the integer optimum isBoth cuts are valid for every original integer feasible point, making this also a certificate for the original integer program.

A surplus variable converts a lower-bound inequality $a^{T}x\ge b$ into $a^{T}x-z=b$, with $z\ge 0$. This is the lower-bound counterpart of a slack variable. When the original coefficients, right-hand side and decision variables are integer, the surplus variable is integer as well; that fact permits it to appear in an all-integer Gomory fractional cut row.