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 an all-integer dictionary row with nonnegative variables, this cut follows because is an integer and . Consequently that integer is at most . Negative coefficients use the usual fractional part , so . Normalize a resulting inequality sensibly before introducing a new integer-valued slack variable.
Articles by others on the same topic
The cutting-plane method is a mathematical optimization technique used to solve problems in convex optimization, particularly in integer programming and other combinatorial optimization problems. The primary idea behind this method is to iteratively refine the feasible region of an optimization problem by adding linear constraints, or "cuts," that eliminate portions of the search space that do not contain optimal solutions.