Linear optimization, mathematics for better decision-making

Linear optimization, originally known as linear programming, is the branch of mathematics devoted to solving complex decision-making problems when resources are limited. Through simple yet powerful mathematical models, it enables the planning, distribution, and allocation of resources in an efficient way. This methodology has a broad impact on sectors such as logistics, finance, and strategic planning.

Linear programming should not be confused with computer programming. In this context, programming refers to planning a set of actions to solve a problem optimally, not to writing code. To avoid such confusion, in 2010 the Mathematical Programming Society decided to change its name to the Mathematical Optimization Society, better reflecting its focus on mathematical optimization and efficient decision-making.

Historical development of Linear Optimization

The history of linear optimization begins long before it was formalized as a discipline. As early as 1826, Joseph Fourier developed a mathematical method for eliminating variables in systems of linear inequalities, now known as the Fourier Elimination Method (Fourier, 1826). His approach was purely theoretical, aimed at studying problems in algebra and mathematical analysis. Almost a century later, in 1936, Théodore Motzkin extended and formalized this method for more complex systems of inequalities, establishing what is now called the Fourier–Motzkin Elimination Method (Motzkin, 1936). The fundamental difference between the two lies in their objectives: Fourier sought to solve general mathematical problems, while Motzkin laid the foundations for broader applications, moving closer to the field of optimization.

In 1939, Leonid Kantorovich published a book, in Russian, (Kantorovich, 1939) proposing linear optimization formulations and a simple, though inefficient, method for solving resource allocation problems. This book was translated into English in 1960 (Kantorovich, 1960). Shortly afterward, in 1941, Frank Hitchcock applied linear optimization to the transportation problem (Hitchcock, 1941), demonstrating how these techniques could be used in concrete logistical situations.

The major breakthrough came in 1947, when George Dantzig developed the Simplex Algorithm (Dantzig, 1951), an efficient procedure capable of solving linear optimization problems in practice. This algorithm is considered a cornerstone of operations research and one of the most important advances of the twentieth century (Cipra, 2000). In 1951, Tjalling Koopmans used linear optimization to formulate complex economic problems, highlighting its usefulness for large-scale resource planning (Koopmans, 1951). Decades later, in 1984, Narendra Karmarkar introduced the Interior Point Method (Karmarkar, 1984), showing that linear optimization problems could be solved in polynomial time and did not belong to the class $\mathcal{NP}$, as previously believed. The class $\mathcal{NP}$ includes problems whose solutions may be very difficult to find, whereas $\mathcal{P}$ groups problems that can be solved efficiently.

For their contributions to the theory of optimal resource allocation, Koopmans and Kantorovich received the Nobel Prize in Economics in 1975. However, Koopmans believed that Dantzig also deserved the prize, since the Simplex Algorithm was fundamental for the practical application of linear optimization and for bringing these ideas into the real world.

Having seen how the methods that shaped linear optimization were developed, it is now useful to understand the basic concepts that allow these problems to be formulated and solved.

Basic concepts

In linear optimization, the core idea is to make smart decisions in an environment with limited resources. To do so, three key elements are used: decision variables, which represent what we can control or adjust; the objective function, which indicates what we want to achieve, such as maximizing profits or minimizing costs; and the set of constraints, which represent the system’s limitations, such as budget, time, or available materials. Together, these elements define a set of feasible solutions, and the task of linear optimization is to find the best option within that set. Although the theory may sound abstract, these concepts are applied every day, from deciding how many products to manufacture to planning delivery routes or allocating resources in a hospital, among many other examples.

In linear optimization, although problems may appear in many different forms, they are usually transformed into a standard formulation or a canonical formulation:

• Standard formulation
  • All constraints are expressed as equalities.
  • All variables are non-negative.
  • This formulation allows algorithms to work uniformly with any problem.

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

• Canonical formulation
  • Focuses on maximization problems (or equivalently minimization).
  • Constraints are of the type ≤ (or equivalently ≥).
  • Variables are non-negative.
  • This is the most common way to present problems before applying optimization methods.

\[\begin{aligned} \min\;\;\; & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.t.:}\;\;\; & \mathbf{A}\mathbf{x} \geqslant \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0} \end{aligned} \qquad \begin{aligned} \max\;\;\; & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.t.:}\;\;\; & \mathbf{A}\mathbf{x} \leqslant \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0} \end{aligned}\]

Although these formulations may appear abstract, they are essential for turning real-world problems into mathematical models that can be solved by algorithms.

Illustrative example

Suppose a company produces two products, A and B, with the following data:

• Each unit of A generates a profit of 40€, and each unit of B generates 30€.
• There are 100 units of raw material available and 80 hours of production time.
• Producing one unit of A requires 2 units of raw material and 1 hour of time.
• Producing one unit of B requires 1 unit of raw material and 2 hours of time.

We define the decision variables:

• $x_A$ = number of units of A to produce.
• $x_B$ = number of units of B to produce.

The objective function, which we want to maximize, is the total profit:

\[\max\; z = 40x_A + 30x_B\]

The constraints of the system are:

• Available raw materials: \(2x_A + 1x_B \leqslant 100\)
• Available time: \(1x_A + 2x_B \leqslant 80\)
• Non-negative productions: \(x_A \geqslant 0, \quad x_B \geqslant 0\)

Once defined in this way, the problem can be solved using the Simplex method or interior point methods, yielding the optimal combination of products A and B.

Practical applications and usefulness

Linear optimization is not just a collection of formulas and algorithms; its true value lies in how it is applied to improve real-world decisions. Today, this tool is used in logistics to plan transportation routes and manage inventories; in industrial production to allocate resources efficiently and maximize profits; in finance to design investment portfolios or optimal budgets; and in strategic planning, from hospitals managing beds and staff to companies optimizing supply chains. As George Dantzig, one of the founding figures of linear optimization, pointed out, linear optimization makes it possible to formalize objectives and make optimal decisions even in complex systems:

“Linear programming is viewed as a revolutionary development giving man the ability to state general objectives and to find, by means of the simplex method, optimal policy decisions for a broad class of practical decision problems of great complexity. In the real world, planning tends to be ad hoc because of the many special-interest groups with their multiple objectives” (Dantzig, 1983).

From Fourier to modern methods, linear optimization shows how mathematical theory can lead to efficient and tangible decisions in the real world, across fields such as logistics, finance, and industrial production.