From Continuous to Integer Optimization: The Power of Integer Variables

Image by Fernando Santander from Unsplash

Continuous linear optimization is one of the greatest success stories of mathematical optimization. Since its development in the mid-20th century, it has enabled us to tackle resource allocation, production planning, transportation, and logistics problems featuring millions of variables and constraints. However, there is a fundamental limitation: the real world is not always continuous.

We cannot build 3.7 hospitals, hire 2.4 workers, or open 5.6 factories. In many real-world scenarios, decisions are inherently discrete. Furthermore, there is a special class of choices that are strictly binary: a project is either launched or not, a machine is purchased or not, a vehicle drives a route or not.

Integer optimization (or integer programming) arises precisely to capture these types of decisions. At first glance, it seems like a minimal tweak to continuous linear optimization: simply requiring certain variables to take integer, or specifically binary, values. Yet, that tiny condition completely reshapes the mathematical structure of the problem, explaining why integer optimization remains one of the greatest challenges in the field.

The Origins of Integer Linear Programming

The earliest developments in linear optimization emerged in the 1930s through the work of Leonid Kantorovich, though it was after World War II that George Dantzig revolutionized the field with the invention of the Simplex Method.

However, it soon became clear that many practical problems could not be adequately represented using continuous variables alone. Decisions involving selection, assignment, or facility location naturally tend to be discrete: an installation is built or not, a vehicle is deployed or not, a machine is purchased or not.

Throughout the 1950s, researchers began designing algorithms specifically tailored to handle discrete decisions. Landmark milestones include the pioneering work of Ralph Gomory (1958, 1960) (Gomory, 1958; Gomory, 1960), who developed cutting-plane algorithms to derive integer solutions directly from the continuous problem, and Ailsa H. Land and Alison G. Doig (1960) (Land & Doig, 1960), who published a solution procedure for discrete programming problems that became the cornerstone of modern Branch and Bound methods.

These approaches introduced two ideas that remain essential in modern commercial solvers: using the continuous relaxation to extract vital insights about the integer problem, and systematically narrowing the search space through bounds and additional constraints.

A standard continuous linear problem can be written as:

\[\begin{aligned} \min \quad & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.t.:} \quad & \mathbf{Ax} \leqslant \mathbf{b}, \\ & \mathbf{x} \geqslant \mathbf{0}. \end{aligned}\]

One of its most crucial geometric properties is that the feasible region forms a convex polyhedron. This convexity endows continuous problems with remarkably well-behaved properties:

• The global optimum can always be found at a vertex (extreme point).
• Highly efficient algorithms exist to solve massive instances.
• Duality theory provides bounds and mathematical optimality guarantees.
• Small modifications to the inputs can be easily analyzed via sensitivity analysis.

It seemed as though optimization was essentially solved… until integer variables entered the picture. Imagine deciding how many trucks a fleet should buy. Continuous linear optimization might yield a solution like $x = 7.42$. Mathematically, it is perfectly valid; practically, it is useless. The intuitive reaction seems obvious:

“Let us just solve the continuous problem and round the solution to the nearest integer.”

However, this quick fix almost never works.

Why Simple Rounding Fails

The first instinct when faced with a fractional solution from a continuous solver is to simply round it. However, rounding fails to guarantee even a feasible solution, and even if feasibility is preserved, optimality is rarely maintained.

• Rounding can yield infeasible solutions.

  Consider the following integer program:

  \[\begin{aligned} \min \quad & z = -x_1-x_2 \\ \text{s.t.:} \quad & -2x_1+2x_2 \leqslant 1, \\ & 16x_1-14x_2 \leqslant 7, \\ & x_1,x_2 \geqslant 0, \; \text{ integer}. \end{aligned}\]

  If we temporarily drop the integrality constraint and solve the continuous relaxation, we obtain the fractional point:

  \[(x_1,x_2)=(7,7.5)\]

  This solution is valid for the continuous problem, but invalid for the integer problem since $x_2$ is not an integer.

  We might try rounding $x_2$ up or down, yielding either \((7,7)\) or \((7,8)\).

  However, neither point is feasible. For $(7,7)$, the second constraint evaluates to \(14 \nleqslant 7\), violating it. For $(7,8)$, the first constraint evaluates to \(2 \nleqslant 1\), violating it as well.

  The true optimal integer solution is actually \((x_1,x_2)=(3,3)\).

  The figure below illustrates this example geometrically. It shows the feasible region of the continuous relaxation, the fractional point $(7,7.5)$, the infeasible integer points resulting from rounding, and the valid integer solutions.

Thus, rounding does not just pull us away from the optimal point: it can produce a solution that is completely invalid.

• Rounding can yield a feasible yet suboptimal solution.

  We might then think that if we just round in a way that preserves feasibility, we will be fine. But that does not solve the issue either: a rounded solution can be feasible and still be far from the true integer optimum.

  Consider the following binary model:

  \[\begin{aligned} \max \quad & z=8x_1+7x_2 \\ \text{s.t.:} \quad & 5x_1+4x_2\leqslant 6, \\ & 0\leqslant x_1,x_2\leqslant1, \\ & x_1,x_2\in\mathbb{Z}. \end{aligned}\]

  Which can be written explicitly with binary domain constraints as:

  \[\begin{aligned} \max \quad & z=8x_1+7x_2 \\ \text{s.t.:} \quad & 5x_1+4x_2\leqslant 6, \\ & x_1,x_2 \in \{0,1\} \end{aligned}\]

  Since the variables are binary, the candidate integer solutions are:

  \[(0,0) \quad (1,0) \quad (0,1) \quad (1,1)\]

  The point $(1,1)$ is infeasible as it violates the main constraint (\(9 \nleqslant 6\)). Evaluating the remaining candidates gives:

  \[\begin{array}{c|c}(x_1,x_2) & z \\ \hline (0,0) & 0\\ (1,0) & 8\\ (0,1) & 7 \end{array}\]

  Therefore, the true optimal integer solution is \((x_1,x_2)=(1,0)\) with \(z_I=8\).

  Now let us see what happens if we drop the integrality requirement and solve the continuous relaxation:

  \[\begin{aligned} \max \quad & z=8x_1+7x_2 \\ \text{s.t.:} \quad & 5x_1+4x_2\leqslant 6, \\ & 0\leqslant x_1,x_2\leqslant 1 \end{aligned}\]

  Here, the continuous optimal solution is \((x_1,x_2)=(0.4,1)\) with \(z_C=10.2\).

  Applying standard rounding to \((0.4,1)\) leads us to \((0,1)\). This rounded solution is indeed feasible for the integer problem and yields \(z=7\).

  However, as we just saw, the feasible integer point \((1,0)\) achieves \(z=8\). Rounding produced a feasible solution, but missed the global optimum.

This example highlights a fundamental contrast between continuous and integer optimization. The continuous relaxation offers a fractional baseline that provides invaluable bounds and insights, but there is no magic rounding formula to transform that continuous point into the integer optimum.

In short, integer programming is not just about “getting rid of decimals.” It is about finding the best combination within a discrete search space, and proving that no better combination exists.

The Continuous Relaxation

To understand how integer problems are actually solved, we need to define a core concept mentioned earlier: the continuous relaxation.

Given an integer program:

\[\begin{aligned} \min \quad & z_I=\mathbf{c}^\intercal \mathbf{x} \\ \text{s.t.:} \quad & \mathbf{Ax} \leqslant \mathbf{b},\\ & \mathbf{x} \in \mathbb{Z}^n \end{aligned}\]

Its continuous relaxation simply drops the integrality constraint:

\[\begin{aligned} \min \quad & z_C = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.t.:} \quad & \mathbf{Ax} \leqslant \mathbf{b} \end{aligned}\]

Geometrically, this means we stop restricting ourselves strictly to integer lattice points inside the polyhedron and allow any point within the feasible region.

The continuous relaxation is far easier to solve and yields critical information:

• It provides an absolute bounding baseline for the integer problem.
• It quickly detects infeasible subregions.
• It measures how far the continuous solution strays from the integer solution.
• It serves as the primary building block for modern integer optimization algorithms.

For instance, in a maximization problem, if the continuous relaxation yields a value of

\[z_C=120\]

while our best known integer solution gives

\[z_I=100\]

there is a 20-unit gap between them. We express this relative difference as the optimality gap:

\[\text{gap}=\frac{|z_C-z_I|}{|z_I|} \cdot 100\]

In this case:

\[\text{gap}=\frac{|120-100|}{|100|}\cdot 100=20\%\]

The tighter the continuous relaxation, the closer its bound is to the true integer solution, providing stronger guidance for the search. Conversely, a large optimality gap indicates that the relaxation leaves a wide region to explore, making the resolution process computationally demanding.

Paradoxically, continuous linear optimization remains the single most important tool used to solve integer optimization.

One Small Constraint That Changes Everything

At first glance, the only difference between the two models seems to be a single extra line:

\[\mathbf{x} \in \mathbb{Z}^n\]

Yet, that single constraint completely transforms the structure of the problem. In continuous linear programming, we work over a convex set:

\[\mathcal{S}=\{\mathbf{x} : \mathbf{Ax} \leqslant \mathbf{b} \}\]

In integer programming, we are strictly interested in the subset of integer points:

\[\mathcal{S} \cap \mathbb{Z}^n\]

While the surrounding polyhedron remains convex, restricting ourselves to integer lattice points destroys convexity in the feasible set. The problem shifts from continuous analysis to combinatorial optimization.

Why Is Integer Optimization So Much Harder?

The fundamental challenge is not merely the presence of integer variables, it is that the search space changes entirely.

• In continuous linear programming, we efficiently navigate the extreme points (vertices) of a convex set.
• In integer programming, we must navigate a discrete grid to figure out which of potentially millions (or trillions) of integer points is optimal.

For this reason, most integer optimization problems are computationally hard and belong to the class of $\mathcal{NP}$-hard problems. No algorithms are currently known that guarantee solving all instances in polynomial time for these problems.

While continuous linear problems with millions of variables can be solved in seconds, much smaller integer models can prove dauntingly difficult. Even a model with just a few hundred binary variables can, under unfavorable formulations, require hours or days of compute time.

How Are These Problems Actually Solved?

The answer is: by solving many continuous problems.

Modern commercial solvers rely on algorithms like Branch and Bound, Cutting Planes, and Branch and Cut. They continuously leverage continuous relaxations to compute bounds, prune regions of the search tree, and systematically narrow down the search toward the global optimum.

In a sense, continuous linear optimization does not disappear when integer variables are introduced, it becomes the indispensable engine driving the entire solution process.

---

Integer optimization is often presented as a straightforward extension of continuous linear programming. From a formulation standpoint, this is true: you simply add an integrality condition. Mathematically and computationally, however, the shift is profound. Although the underlying constraint polyhedron remains convex, restricting solutions to integer points destroys convexity in the feasible set, giving rise to severe combinatorial complexity.

That is precisely why integer optimization has sparked some of the most significant breakthroughs in modern mathematical optimization. It remains an indispensable framework for modeling real-world problems across logistics, energy systems, telecommunications, finance, and scheduling.

After all, not everything in life can be continuous: many of our most critical decisions come down to discrete, all-or-nothing choices.

---

Would you like to keep exploring the world of Operations Research? Discover more posts on the topic here.