Gomory Fractional Cuts

When the simplex method solves the LP relaxation of an integer program, a basic variable can land on a non-integer value. From such a row we can build a Gomory fractional cut -- a linear inequality that excludes the current LP optimum while keeping every integer feasible point. The whole construction rests on a single operation: extracting the fractional part of a real number.

For any $a\in\mathbb{R}$, the fractional part of $a$ is

$$\{a\} \;=\; a - \lfloor a \rfloor,$$

where $\lfloor a\rfloor$ is the greatest integer $\leq a$. By construction, $\{a\}\in[0,1)$.

A few quick computations:

$$\{3.7\} = 3.7 - 3 = 0.7,$$ $$\{5\} = 5 - 5 = 0,$$ $$\{-1.3\} = -1.3 - (-2) = 0.7,$$ $$\left\{\tfrac{7}{3}\right\} = \tfrac{7}{3} - 2 = \tfrac{1}{3}.$$

Notice that for negative numbers, $\lfloor a\rfloor$ rounds down (more negative), so $\{a\}$ is still in $[0,1)$. The fractional part of an integer is always $0$.