GilmoreGomory

GilmoreGomory refers to a family of cutting planes used to solve integer linear programming problems, commonly called Gilmore–Gomory cuts or Gomory–Gilmore cuts. The method was developed in the 1960s by Ralph E. Gomory and Ellis L. Gilmore and is regarded as one of the early practical approaches to tighten linear relaxations of integer programs. It helped establish cutting-plane techniques as a core component of modern integer programming, later integrated into branch-and-cut solvers.

The core idea is to generate valid linear inequalities (cuts) from the current linear programming relaxation that exclude the present non-integer solution while preserving all feasible integer solutions. Cuts are derived from a row of the simplex tableau corresponding to a basic variable with a fractional value. By taking the fractional parts of the coefficients in that row, an inequality is formed that the current non-integer solution violates but every integer-feasible point satisfies. Repeating this process for appropriate rows yields a sequence of increasingly tight relaxations.

In practice, Gilmore–Gomory cuts are used within broader solution frameworks such as branch-and-cut, where cuts are added to the LP relaxation to prune the search space and guide the solver toward integer feasibility. The approach laid groundwork for later cutting-plane families, including the Chvátal–Gomory cuts, and remains a foundational concept in the theory and practice of integer programming.

Notes: The technique is theoretical and can produce exponential worst-case behavior, but it remains influential in the development of modern MILP solvers. It is most often discussed in the context of linear and integer programming, polyhedral theory, and optimization algorithms.