Contents

Gomory CutEdit

Gomory cuts are a foundational tool in the family of cutting plane methods used to solve integer programming problems. Introduced by Ralph Gomory in the late 1950s, these cuts are designed to tighten the linear programming (LP) relaxation of an integer program without removing any feasible integer solutions. In practice, they are a key component of modern solvers that tackle combinatorial optimization challenges by iteratively refining LP relaxations and guiding search toward integer feasibility. Gomory cuts are derived from the simplex tableau of a linear programming relaxation and are most notably associated with pure integer programming and their generalization to mixed-integer problems within broader frameworks like branch-and-cut.

The development of Gomory cuts helped establish a systematic approach to generating valid, problem-reducing inequalities directly from the structure of an LP solution. This made it possible to combine algebraic tightening with combinatorial search, a approach that has become standard in many practice-oriented optimization environments. As such, Gomory cuts sit at the intersection of theory and practice, providing a practical path from LP relaxations to integer-feasible solutions in a way that scales to relatively large and complex problems. For readers seeking historical and technical context, they are frequently discussed alongside other cutting planes in cutting plane method literature and within the broader history of integer programming.

History and development

Gomory introduced his cutting planes as part of a broader program to understand how the LP relaxation of an integer program could be iteratively strengthened without discarding any feasible integer points. Over time, the basic Gomory cut was generalized and integrated into more elaborate schemes. The development of the mixed-integer variant, often referred to as the Gomory mixed-integer cut, extended the idea to problems where some variables are restricted to integers while others remain continuous. These ideas are now standard in the family of techniques used in modern solvers that implement branch-and-cut algorithms, where cutting planes and branching operate in tandem to arrive at optimal or near-optimal integer solutions.

Beyond the original pure integer case, the field has expanded to include a variety of related cuts derived from disjunctions, lattice-free sets, and polyhedral theory. In particular, Chvátal–Gomory cuts, split cuts, and lift-and-project techniques form a hierarchy of increasingly powerful polyhedral refinements that subsume the basic Gomory construction in many settings. For readers, these developments are often described in relation to the theoretical underpinnings of polyhedral combinatorics and the practical implementation details found in mixed-integer programming solvers.

How Gomory cuts work

The core idea behind a Gomory cut is to exploit a fractional basic variable in the current LP tableau. In a standard LP relaxation, the basic variables are expressed in terms of nonbasic variables, typically in a form like x_r = b_r - sum_j a_rj x_j, where x_r is a basic variable and x_j are nonbasic. If the value of x_r in the current LP solution is fractional, the fractional parts of the coefficients a_rj and the constant term b_r can be used to construct a new inequality that is valid for all integer-feasible points but violated by the current fractional solution. The resulting inequality—a Gomory cut—removes the current fractional point from the LP feasible region while preserving all feasible integer points.

In simple terms, a Gomory cut takes the fractional parts of the row’s coefficients and assembles a linear inequality that any integer solution must satisfy. When added to the LP, this cut tightens the relaxation and pushes the solution toward integrality. For mixed-integer problems, generalized variants like the Gomory mixed-integer cut arise by applying the same idea to rows that involve both integer and continuous variables, often resulting in stronger cuts.

Gomory cuts are especially attractive because they are relatively straightforward to derive from the current tableau, requiring no backtracking or the introduction of entirely new variables. They are thus an inexpensive but effective addition to the set of tools used in a cutting plane method and are commonly among the first cuts implemented in modern optimization software.

Strengths, limitations, and practical use

  • Strengths:

    • Simplicity and ease of derivation from the current LP tableau.
    • Ability to prune fractional solutions early in the solve process, contributing to faster convergence in many problem classes.
    • Compatibility with other methods, making them a natural fit within branch-and-cut frameworks that blend cuts with branching.

  • Limitations:

    • Individual Gomory cuts can be weak, especially far from the optimal integer solution, so many problems require a sequence of cuts or combinations with stronger multicut or lift-and-project techniques.
    • In some instances, cuts can cause degeneracy or slow down the solver if too many are generated without commensurate progress.
    • The overall effectiveness depends on problem structure; certain combinatorial problems benefit more from alternative cuts or from structural reformulations.

  • Practical use:

    • In practice, Gomory cuts are used as part of a broader strategy within integer programming solvers, where they are combined with other cuts (such as split cuts and lift-and-project cuts) and with a robust branching strategy. The result is a flexible, widely applicable approach to solving a broad array of optimization problems encountered in logistics, scheduling, network design, and other domains. See split cut and Chvatal–Gomory cuts for related concepts.

Extensions and related concepts

  • GMI cuts (Gomory mixed-integer cuts) generalize the original idea to mixed-integer programs, expanding the scope of problems where Gomory-type refinements can be applied.
  • Chvátal–Gomory cuts assemble an entire family of cuts from all disjunctions that split the feasible region into integer-feasible and non-integer-feasible portions; these are closely related to Gomory’s construction and are a staple of modern polyhedral approaches.
  • Lift-and-project techniques and intersection cuts provide stronger, more general families of cuts by systematically projecting higher-dimensional polyhedra into lower dimensions while preserving integer feasibility.
  • The broader framework of branch-and-cut integrates Gomory cuts with branching and other cuts to form a practical, scalable solution method for large-scale problems.

See also