Fractional Cut

In the world of mathematical optimization, we often seek the absolute best plan to allocate resources, a plan that maximizes profit or minimizes cost. However, the elegant world of continuous mathematics frequently provides answers that are nonsensical in reality, such as needing to build 1.67 trucks or schedule 3.5 teams of workers. This conflict between the mathematically optimal fractional solution and the real world's demand for whole-number answers is the central dilemma of integer programming. The gap isn't just an inconvenience; it represents a fundamental barrier to creating practical, actionable plans. How, then, can we systematically find the true integer optimum without resorting to guesswork?

This article demystifies a powerful technique designed to solve this very problem: the fractional cut. By reading, you will understand how this method bridges the gap between the continuous and the discrete. The article is structured to guide you from core theory to practical impact. First, the "Principles and Mechanisms" chapter will dissect the logic behind generating a cut, showing how the "dross" of a fractional solution is alchemically transformed into a new, valid rule. We will explore the derivation step-by-step and visualize its geometric effect. Following that, the "Applications and Interdisciplinary Connections" chapter will bring the theory to life, demonstrating how fractional cuts enforce the laws of indivisibility in diverse fields, from logistics and manufacturing to power grid management and even abstract puzzles in graph theory.

Imagine you're trying to ship goods using a fleet of trucks. You've used a brilliant mathematical method to find the absolute best way to load them, a plan that guarantees maximum profit. The computer spits out the answer: "Build 1.67 trucks of Type A, and 2.75 trucks of Type B." This is, of course, nonsense. You can't build a fraction of a truck. You've solved a problem in the beautiful, fluid world of continuous numbers, but reality demands answers in whole numbers—integers.

This is the central dilemma of integer programming. The continuous optimum, while mathematically elegant, is often practically useless. How do we bridge this gap? How do we find the true best integer solution without resorting to blind guesswork? The answer lies in a wonderfully clever procedure that, step by step, carves away the impossible to reveal the possible. This procedure uses something called a ​​Gomory fractional cut​​.

Let's think about our nonsensical fractional solution. It's the best answer if we're allowed to use fractions. Since we're not, that specific answer is forbidden. The core idea of a cut is simple: we want to add a new rule, a new constraint, to our problem. This rule must be carefully crafted to do two things simultaneously:

1. It must make our current fractional solution illegal.
2. It must not rule out any of the valid, real-world integer solutions.

In essence, we are "cutting off" a piece of the continuous solution space that contains our fractional answer, but we're being careful not to throw the baby out with the bathwater.

Consider a simple case where our fractional optimum for variables $(x_1, x_2)$ is $(\frac{18}{11}, \frac{23}{11})$. Suppose we magically come up with a new rule: $3x_1 + 2x_2 \le 9$. Is this a good cut? Let's check. We plug in our fractional values:

Our proposed rule demands that this value be less than or equal to $9$, which is $\frac{99}{11}$. But $\frac{100}{11}$ is not less than or equal to $\frac{99}{11}$. Our fractional solution violates the new rule! So, this cut successfully makes the current fractional optimum infeasible. If we could be sure that this rule doesn't eliminate any good integer solutions, we would have made progress. But where do such magic rules come from?

It turns out these cuts aren't magic at all. They are derived with an impeccable logic that feels like a beautiful bit of alchemy, turning the "dross" of a fractional answer into the "gold" of a new, valid constraint. The secret lies hidden within the final ​​simplex tableau​​—the detailed map that the optimization algorithm produces to describe its solution.

On this map, we look for a specific landmark: a row corresponding to a variable that is supposed to be an integer but currently has a fractional value. For instance, our map might tell us:

Here, $x_B$ is supposed to be an integer, but the current solution (where the non-basic variables $x_1, x_2, x_3$ are all zero) gives $x_B = 3.5$. This is our source of power. This single equation contains a hidden truth. To find it, we'll play a game of separation. Let's rewrite the equation with all variables on one side:

Now for the key insight. Any number can be split into its whole part and its fractional "leftover." For example, $1.3$ is $1 + 0.3$, and $3.5$ is $3 + 0.5$. Let's decompose every number in our equation this way:

Now, let's rearrange this equation, putting everything we know for sure is an integer on the left side, and all the fractional parts on the right. Since $x_B, x_1, x_2, x_3$ must all be integers in any valid final solution, the terms $x_B$, $1x_2$, and the integer part of the constant, $3$, are parts of our "integer pile."

Look at this beautiful result! The left side of the equation is a combination of integers, so it must evaluate to an integer. This is a fundamental law. If the left side is an integer, then the right side must also be an integer.

But now look closely at the right side. In standard optimization problems, our variables ($x_1, x_2, x_3$) must be non-negative. This means the term $(0.2x_1 + 0.3x_2 + 0.6x_3)$ is always greater than or equal to zero. So, the entire right-hand side is $0.5$ minus some non-negative value. It can never be greater than $0.5$.

We have discovered two things about the right-hand side that must be true for any valid integer solution:

1. It must be an integer.
2. It must be less than or equal to $0.5$.

What integers are less than or equal to $0.5$? Only $0, -1, -2, \ldots$ and so on. In other words, the right-hand side must be less than or equal to zero. And with that, we have unearthed our hidden rule:

Rearranging this gives us the ​​Gomory fractional cut​​:

This is the magic. We started with one equation and, using only the property of integrality, we derived a brand new inequality. This new rule is guaranteed to be true for every possible integer solution, yet it is violated by our current fractional solution (where $x_1=x_2=x_3=0$, giving $0 \ge 0.5$, which is false). We have successfully performed the cut. This same logic can be expressed more elegantly using the language of modular arithmetic, where we are essentially stating that the fractional parts of the equation must balance out.

What does this algebraic trickery look like? The set of all possible solutions to the continuous problem forms a multi-dimensional shape called a ​​polytope​​. The optimal fractional solution is a corner of this shape. The valid integer solutions are like a grid of isolated points, and the shape that just barely encloses all of them is called the ​​integer hull​​. Our goal is to surgically trim the oversized polytope down to the slender integer hull.

Each Gomory cut is a straight line (or plane, or hyperplane) that slices off a piece of the polytope. A well-constructed cut is a ​​supporting hyperplane​​ to the integer hull—it rests snugly against the hull, often touching it at one or more valid integer points, while slicing away a region of the continuous space that contains no integer points at all.

Imagine our cut is the line $x_1 + x_2 \ge 1$. This slices the solution space in two. All the valid integer points lie on one side of the line, satisfying the new rule. Our old fractional answer is left on the other side, now excluded from the feasible region. By repeatedly applying these cuts, we are essentially "shrink-wrapping" the feasible region around the true integer solutions.

This powerful technique has its own rules. What if we try to generate a cut from a row where the integer variable already has a whole number value, say $x_1 = 3$? Following the same logic, the fractional part of the constant is $0$, leading to a trivial cut like $0.4y + 0.25s_2 \ge 0$. Since all variables and coefficients are non-negative, this is always true and adds no new information. The method is smart enough to only act when there's a fraction to fix.

Furthermore, our derivation relied on a crucial assumption: that the non-basic variables ($x_1, x_2, x_3$ in our example) are non-negative. If we allow them to be negative, our logic that the right-hand side is less than or equal to $0.5$ falls apart. Indeed, one can find integer solutions with negative variables that violate a cut derived this way, proving this assumption is not just a convenience but a cornerstone of the method's validity.

One cut is rarely enough to find the integer optimum. The Gomory method is an iterative journey.

1. Solve the continuous (LP) problem.
2. If the solution is all integers, stop. You've won.
3. If not, pick a row with a fractional integer variable and generate a Gomory cut.
4. Add this new cut to your list of rules and go back to step 1.

Each time we add a cut, we tighten the ​​bound​​ on our solution. For a maximization problem, the continuous solution provides an overly optimistic upper bound on what's truly possible. Each cut shaves down this bound, bringing our estimate closer to the real-world integer optimum.

This journey, while guaranteed to reach the destination, is not always swift. If a cut happens to be nearly parallel to the direction of our objective function, slicing it off will only move the optimal point a tiny amount. The objective value improves very slowly, a phenomenon known as "tailing off". Even so, the logic is relentless. Bit by bit, slice by slice, the impossible is carved away, until the only thing left is the elegant, practical, and true integer solution.

We have seen the clever mechanics behind Ralph Gomory's fractional cuts. On paper, it is a neat algebraic trick. But to stop there would be like learning the rules of chess without ever seeing the beauty of a grandmaster's game. The true magic of this idea comes alive when we see it at work, bridging the profound gap between the smooth, flowing world of our mathematical models and the lumpy, granular reality we inhabit. Our continuous equations love fractions, but the world is often made of whole things—trucks, people, atoms, choices. A Gomory cut is the mathematical tool that teaches our equations to respect this fundamental graininess.

Let us begin with things we can picture. Consider a small company trying to ship its goods. It can use two types of trucks on two different routes, and its goal is to meet the demand at the minimum cost. Our initial, "relaxed" mathematical model—which assumes everything is perfectly divisible—might offer a wonderfully economical solution: use zero trucks on the first route and, say, $3.5$ trucks on the second. This is, of course, nonsense. You cannot dispatch half a truck.

What happens when we confront the mathematics with this physical absurdity? The machinery of the Gomory cut performs a remarkable piece of logical judo. From the very equation that gave us the impossible '$3.5$', it derives a new, perfectly logical constraint. In a typical case, it might be an inequality that says, "any valid integer plan must use at least one truck on the first route." Think about that! The nonsensical fractional answer contained the seed of a deeper truth about the real, discrete solution. The cut forces the model to be honest about the indivisible nature of trucks.

This same principle appears in manufacturing. Imagine a paper mill that cuts large stock rolls into smaller, sellable lengths using a few predefined cutting patterns. An initial linear programming model might suggest the most efficient way to meet demand is to use two rolls for one pattern, and half a roll for another. Again, this is physically impossible. The Gomory cut generated from this "half-pattern" absurdity reveals a hidden, structural dependency. It might tell us that to make all the pattern counts whole numbers, we are forced to use at least one roll of a completely different pattern that the fractional solution ignored. The cut uncovers non-obvious combinatorial truths that are necessary for a realistic plan.

The world of people, with its schedules and assignments, is just as "lumpy" as the world of trucks. Imagine a hospital administrator scheduling nurse teams to cover morning, evening, and night shifts. The optimal plan from a simple model might call for "$3.5$" teams on the morning shift. We face the same impossibility—you cannot staff a ward with half a team. The Gomory cut provides the necessary correction. It might reveal that to make the morning shift numbers whole, the hospital is forced to add at least one full team to either the evening or night shift. The cut translates the abstract requirement of "integrality" into a concrete operational trade-off. It’s the mathematics telling the planner, "You can't have your cake and eat it too; to fix this fractional assignment, you must commit a real, whole resource elsewhere."

This logic applies to countless human-scale problems. In university timetabling, a course cannot be "partially" assigned to a time slot; it is either in the slot or it is not. In project management, a worker cannot be assigned to $0.7$ of a task. In all these cases, a fractional solution from a relaxed model represents a physical or logical impossibility. The Gomory cut is the mechanism that enforces the fundamental, combinatorial rule of indivisibility.

Now, let us scale up from a single factory or hospital to vast infrastructure networks. Consider an electric power grid. An operator must decide which power plants to turn on to meet electricity demand—a classic "unit commitment" problem. A power plant is either on or it is off; there is no in-between. It is a binary, $y \in \{0, 1\}$, decision. Yet a relaxed model, seeking the lowest cost, might conclude that the optimal strategy is to "75% start up" a particular generator, yielding a fractional value like $y=0.75$.

This is not just inconvenient; it is physically meaningless. Here, the Gomory cut acts as a restorer of physical law. By taking the equation that yields the fractional startup value, the method generates a new constraint. When translated back into the physical variables of the system, this new constraint might simply state "$y \ge 1$". It forces the generator to be fully on. The mathematics, when forced to confront its own non-physical conclusion, deduces the physical reality as a logical necessity. The cut isn't just an arbitrary constraint; it's a theorem about the system that was invisible in the fractional world.

The power of this idea is not confined to the physical world of trucks and generators. It extends beautifully into the purely abstract realm of logic and combinatorics. Take the classic map-coloring problem, a famous puzzle in graph theory. Can you color a map with, say, three colors such that no two adjacent countries share a color? This can be framed as an integer program. A relaxed version might produce a "solution" where a node is colored with "half red" and "half blue."

While this notion of "fractional coloring" is itself an interesting mathematical topic, it doesn't help us color a real map. Once again, Gomory cuts can be generated from these fractional color assignments. Each cut slices away an impossible, mixed-color solution, systematically pushing the answer towards a valid, discrete coloring where each node is $100\%$ one color. Here, the cuts are enforcing not a physical law, but a purely logical one. This demonstrates the profound generality of the method.

So, are Gomory cuts a magic bullet that solves any integer problem in one shot? Not quite. In the real world of computational optimization, they are one instrument in a grand symphony of algorithmic techniques. Modern solvers for Integer Linear Programs (ILPs) use a powerful framework called ​​Branch-and-Cut​​. The strategy is a beautiful dance:

1. ​​Relax​​: First, the solver ignores the integer constraints and solves the easy LP relaxation. This gives a fractional answer and, for a maximization problem, an upper bound on the true optimal integer value.

2. ​​Cut​​: If the solution is fractional, the solver generates valid inequalities—like Gomory cuts—to slice off this fractional point from the feasible region, tightening the model without removing any true integer solutions. These cuts can be globally valid and applied throughout the entire search, or locally valid for just one part of it. This process can be repeated, aiming to close the "integrality gap"—the difference between the fractional dream and the integer reality.

3. ​​Branch​​: If cutting is not enough to find an integer solution, the algorithm "branches." It splits the problem into two smaller, more constrained subproblems (e.g., for a binary variable $x_k$, one subproblem with the constraint $x_k=0$ and another with $x_k=1$) and repeats the relax-and-cut process on each new branch.

This combination is incredibly effective. The cuts reduce the amount of branching needed by providing tighter bounds, which allows the algorithm to prune vast sections of the search tree early, especially when a good integer solution is found quickly. Of course, there are special cases where this machinery is wonderfully unnecessary. For problems whose constraint matrix is "totally unimodular," the solution to the LP relaxation is guaranteed to be integer from the start. But for the vast landscape of hard, "lumpy" problems that define our world—from airline scheduling to financial modeling and beyond—Gomory's method provides the sharp edge needed to carve out the truth, one cut at a time.