9.4 Cutting planes
A cutting plane is an inequality satisfied by every integer feasible point but violated by the current LP optimum. Adding it tightens the relaxation. Gomory (1958) showed how to derive one from any row of the optimal tableau with a fractional right-hand side.
Theorem 9.4.1 (Gomory fractional cut). Suppose all variables are integers and non-negative, and a row of the optimal tableau reads \(x_i + \sum _{j \in N}\bar a_jx_j = \bar b\) with \(\bar b\) not an integer. Writing \(f(v) = v - \lfloor v\rfloor \) for the fractional part, every integer feasible point satisfies \[ \sum _{j \in N}f(\bar a_j)\,x_j \geq f(\bar b) , \] and the current LP solution, with all \(x_j = 0\) for \(j \in N\), violates it.
Proof. Write \(\bar a_j = \lfloor \bar a_j\rfloor + f(\bar a_j)\) and \(\bar b = \lfloor \bar b\rfloor + f(\bar b)\); the row becomes \(x_i + \sum \lfloor \bar a_j\rfloor x_j - \lfloor \bar b\rfloor = f(\bar b) - \sum f(\bar a_j)x_j\). At an integer point the left side is an integer. The right side is less than \(1\), since \(f(\bar b) < 1\) and \(\sum f(\bar a_j)x_j \geq 0\). An integer less than \(1\) is at most \(0\), which is the cut. At the LP solution the right side is \(f(\bar b) > 0\). □
In Example 9.3.2 (with slacks \(s_1\), \(s_2\), which are integers since the data are) the optimal row for \(x_2\) is \(x_2 - \frac 18s_1 + \frac 34s_2 = \frac 32\). The cut is \(\frac 78s_1 + \frac 34s_2 \geq \frac 12\), and substituting \(s_1 = 24 - 6x_1 - 4x_2\), \(s_2 = 6 - x_1 - 2x_2\) it becomes \(6x_1 + 5x_2 \leq 25\) (Software 9.6.2). It cuts off \((3, 1.5)\), keeps every integer point, and moves the LP optimum to \((3.33, 1)\). Gomory proved that repeated cuts of this kind solve any IP in finitely many steps, but on their own they converge slowly; modern solvers use them inside branch and bound (branch and cut), together with cuts specific to the structure, such as cover inequalities for knapsack rows.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.