Motivation
A fractional optimum identifies where the linear relaxation is too generous, but rejecting that point is easy: infinitely many inequalities can do so. The hard condition is preserving every integer feasible point. A useful cut must come with an argument that depends on integrality, the row equations, and the signs of variables, rather than on a picture of the current answer.
Tableau cuts exploit a particularly simple arithmetic fact. An integer plus a weighted sum of fractional coefficient parts must have the same fractional remainder as the right-hand side. If the weighted sum is nonnegative, it cannot lie between zero and the required positive remainder. This creates an inequality that the current fractional basis violates.
A second issue arises after a cut is added. The next LP optimum may still be fractional. Repeating valid cuts can yield a decreasing sequence of upper bounds without ever attaining the integer optimum in finitely many steps. To justify an algorithm we must specify which cuts are generated, how LPs are solved, and when branching is mandatory. Validity and finite termination are separate mathematical contracts.
Definitions
Definition 7.1.1
(Fractional part and a pure-integer tableau row)
For a real number , write for its greatest integer lower bound and . Suppose a tableau row is
Every variable appearing here, including any ordinary slack, is required to be integer for the pure-integer derivation. The current basic solution has and , so it violates integrality.
For rational original data, multiply each inequality by a common positive denominator before introducing its slack if an integer slack representation is needed. An inequality with integer coefficients and integer right-hand side gives an integer slack whenever its decision variables are integer. Artificial or newly introduced continuous variables do not become integer merely because they appear in a tableau.
A cutting plane is an inequality valid for every integer feasible point and violated by a selected relaxation point. A branch-and-cut node consists of inherited constraints, valid added cuts, and variable-domain restrictions from its ancestry. Its LP bound is an upper bound for maximization only after the relaxed optimum or another valid dual bound has been established.
Theorem/proposition
Theorem 7.1.2
(Pure-integer Gomory fractional inequality)
Under the tableau-row assumptions, every integer feasible point satisfies
The current basic solution violates this inequality. Negative tableau coefficients must use mathematical floor, not truncation toward zero.
Proposition 7.1.3
(Aggregation and rounding give a valid cut)
Let with integer-designated , and choose such that is an integer row. Then every feasible integer point satisfies
This is an aggregated rounding, or Chvátal–Gomory, inequality. Nonnegative aggregation multipliers are required for upper inequalities.
Theorem 7.1.4
(A sufficient finite branch-and-cut policy)
Suppose every designated integer variable has finite integer lower and upper bounds, and every processed node LP is infeasible or has a finite attained maximum. At each node, use only valid cuts, generate finitely many cuts before either closing or branching, and solve its LP subproblems with a terminating exact method. Branch a fractional designated variable by its floor/ceiling disjunction. Then a search that processes every surviving node terminates and either proves integer infeasibility or returns a global optimum.
This theorem also applies to mixed-integer models when node LPs have well-defined finite optima or certified infeasibility and the continuous decisions are retained. It does not justify the pure-integer fractional cut for continuous tableau variables. An unbounded node needs a separately valid integer-unboundedness analysis or a stated bounded-relaxation hypothesis; it cannot simply be marked solved because its LP is unbounded.
Proof sketch or proof idea
Proof
(Congruence and nonnegativity give the fractional cut)
For the first theorem, split every coefficient and the right-hand side into integer and fractional parts. Rearranging the row gives
The fractional sum on the left before subtracting the right-hand remainder is nonnegative. It has the same fractional remainder as , which lies strictly between zero and one. Its smallest possible nonnegative value is therefore that remainder. This proves the cut. At the current nonbasic-zero point the left side of the proposed inequality is zero, less than the positive right side, so the cut separates it.
This proof explains why negative coefficients are harmless when floors are handled correctly. For example, , not minus one half. It also explains why a continuous variable breaks the proof: an integer coefficient multiplied by a continuous value need not be integer, so the claimed remainder relation is lost.
Proof X-ray
Where each hypothesis enters the fractional cut
Write . The proof has three inputs and one closing move. Integrality of every variable makes an integer; this is the step a continuous column destroys, as the counterexample below shows. The floor convention makes every lie in , and nonnegativity of the variables then makes . The closing move combines these with : the integer is greater than , hence at least .
The hypothesis is used only for separation. If the remainder were zero, the inequality would read , valid but useless. Separation itself needs nothing about integer points: the current basic solution has every nonbasic coordinate zero, so .
Proof
(Nonnegative aggregation and integer rounding)
For aggregation, multiply the original inequalities by nonnegative multipliers and add to get . Since and are integer, their dot product is integer and cannot exceed the floor of the right side. The proof needs neither an optimal tableau nor a particular objective. A cut can be valid even when it is not currently violated; such a cut does not separate that particular point.
Proof
(Coverage and incumbent invariants on a finite tree)
For finite search, maintain two invariants. Every original integer feasible point remains in at least one live node unless it has already been accounted for by a valid closing certificate. Every incumbent is an actual feasible integer point. Valid cuts preserve the first invariant; floor/ceiling branches cover the parent's integer domain; infeasibility, integer relaxed optima, and adequate upper bounds justify closure.
Along any branch, each disjunction strictly shrinks one integer coordinate interval, by at least one integer unit. The path depth is bounded by the sum of the original interval widths. The binary tree is therefore finite. Finitely many cuts and terminating LP solves give finite work at each node. When every node is closed, the invariants prove that no feasible integer point has a better value than the incumbent. If none was found, the same coverage argument proves infeasibility.
The theorem requires the search to eventually process every live node. A scheduling rule that endlessly revisits an unrelated calculation is not a terminating search merely because the abstract tree is finite. Likewise, an unlimited cut loop at one node violates the finite-work condition even when each individual cut is valid and each LP solve finishes.
Worked examples
Worked example 7.1.5
(A negative tableau coefficient contributes a positive fraction)
Consider the row
Both nonbasic fractional coefficient parts equal one half, because . The fractional cut is , or .
The relaxed basic point is excluded. Integer point satisfies both row and cut, as does . Treating the negative coefficient's fractional part as negative would produce a different expression unsupported by the proof. The sign convention is part of the arithmetic, not a solver preference.
Worked example 7.1.6
(Two valid cuts can have different strength)
Maximize subject to , , and nonnegative integer variables. The relaxation has optimum with value . Adding one third of each inequality gives . Since the left side is integer, the aggregated cut is . Integer points attain two, so this cut closes the objective gap completely.
Now introduce integer slacks . The row for basic is
Its canonical coefficients are and , both with fractional part . The fractional cut is , equivalently . Since , its direct LP form is . This is valid and cuts the old optimum, but is weaker than the aggregated bound two. One should not claim that every derived fractional cut closes the entire gap in one step.
Concept lensAlgebraic
The fractional cut is an aggregated rounding cut
The tableau cut is a Chvátal–Gomory cut in disguise. Since , the row gives ; the left side is integer, so it is at most . Subtracting this from the row equation gives exactly . In the example above, the row for yields , and substituting returns .
Worked example 7.1.7
(A general-integer tree closes with two certified cases)
Maximize subject to , , and nonnegative integers. The capacity implies . The LP optimum is , value sixteen: the objective-per-capacity ratio favors , so fill it to three and use the remaining unit of capacity for .
Branch on or . The first node gives integer point with value fifteen. In the second, rewrite the objective as
Point attains thirteen, so that is the exact node LP bound. It is below the incumbent fifteen, and the node closes. These two cases cover all integer values zero, one, and two of , not merely binary choices. Thus fifteen is globally optimal.
Counterexample mode
A pure-integer row cut is invalid for a continuous nonbasic variable
Let with nonnegative integer and continuous. The feasible point exists. Applying the pure-integer formula would use fractional coefficient part and demand , falsely deleting it. The repair is to keep the pure-integer hypothesis or derive an appropriate mixed-integer inequality; declaring a continuous tableau column integer is not a valid shortcut.
Valid strict cuts need not terminate
Start with integer and maximize . The integer optimum is one. Add, successively, the valid rational cuts for . After the first stage, each later cut strictly improves the relaxation and removes its previous optimum. Nevertheless every finite-stage LP optimum is still fractional and greater than one. The bounds converge to the answer but never certify equality in a finite number of these stages.
This example does not refute a specialized finite-convergence theorem for a precisely specified Gomory algorithm; it refutes the much broader claim that validity plus strict improvement implies finite termination. A classical cut-only convergence proof needs its own selection rules and lexicographic reoptimization argument. Here the stated finite policy instead limits cuts per node and falls back on exhaustive branching.
Common mistakes
Common mistake
(Rounding a right-hand side whose left side is not integer)
Rounding the right side of an arbitrary inequality is valid only when its left side is known integer. Rational coefficients multiplying integer variables need not produce an integer: from one may not conclude , which would delete the integer point . Aggregating with negative multipliers also need not preserve an upper inequality. Both errors can yield a cut that excludes the true optimum.
Common mistake
(Continuing the old primal ratio test after a cut)
After adding a cut, the old primal basis may be infeasible even though the integer problem is unchanged. Reoptimization must restore the appropriate primal or dual invariants; simply continuing an old primal ratio test without checking feasibility is unjustified. Exact LP termination can be supplied by Phase I and an anti-cycling rule from the preceding unit.
Common mistake
(Closing a node on a small gap without an objective lattice)
A small relaxation gap is not exact closure unless a proven objective lattice makes rounding legitimate. A continuous objective contribution can remove that lattice even when some variables are integer. Numerical cut tolerances and coefficient scaling require additional analysis beyond these exact-arithmetic proofs.
Summary
Fractional tableau cuts come from congruence and nonnegativity; aggregated cuts come from nonnegative combination followed by integer rounding. Both preserve every integer point under explicit hypotheses, but their strength varies. Finite branch-and-cut additionally needs bounded integer domains, finite cut work at each node, exact terminating LP processing, and exhaustive scheduling. Validity by itself is not a termination theorem.
Exercises
Quick check
(Derive the fractional cut from , with all variables nonnegative integers.)
Solution · Answer
The fractional parts are and , because ; the right remainder is . Thus , or . At the nonbasic-zero basic point it fails, as required.
Quick check
(For and , with integer , aggregate to obtain a valid bound on . Compare it with the fractional intersection.)
Solution · Answer
Multiply both inequalities by one quarter and add: . The left side is integer, so the cut is . The relaxation intersection has sum and is cut off. Feasible integer point attains two, proving the maximum sum is two under nonnegativity as well.
Quick check
(In the general-integer example, add the valid inequality explicitly. Does this alone remove the root fractional optimum? Explain.)
Solution · Answer
No. The fractional point already satisfies . The inequality is a valid domain bound used to prove finite search, but it does not separate this LP point. Validity, separation, and strength are different properties.
Quick check
(Give a finite-search policy for the one-dimensional nonterminating cut example, and explain which hypothesis the cut-only sequence lacked.)
Solution · Answer
Generate at most a fixed finite number of these cuts, then branch the fractional into and . The second is infeasible under the original upper bound; the first attains integer optimum one. The cut-only process lacked a finite-work rule before branching, despite its bounded integer domain and strictly improving valid bounds.