If you search for the most important or impactful algorithms ever invented, you will come across many different lists published by various academics, magazines, blogs etc. with various opinions on what algorithms have been most important to humankind.
One algorithm that tends to consistently make the "top 10" is the Simplex Method for Linear Programming, created by George Dantzig. But many of us in the planning and optimization space are not aware of the broader history of optimization beyond this discovery.
The excerpt below is taken from an excellent optimization introduction course written by @SP for training of our new operations research scientists explaining more of the history of optimization.
The history of optimization
About 5,000 years ago, people in Western Asia and Northern Africa started to use mathematics. This was an important step in the history of optimization, as these people realized that they could use mathematics as a tool to optimize their world. They invented algebra, arithmetic and geometry, and in order to explain the behavior in the real world, they made an abstraction of the real world in a simplified model, using a mathematical description. The great thing was that they could make calculations in this mathematical model and that they could translate the results back to the real world and make decisions.
For 5,000 years, the optimization approach of people has basically not changed. The approach is to make a model that represents the real world as closely as possible and using this model an optimal solution was calculated using the mathematic rules of the model. In 500 BC, the Greek philosopher and mathematician Pythagoras stated: “At its deepest level, reality is mathematical in nature”. A perfect description of the core idea of fields such as “Mathematical Optimization”, “Operations Research” or “Business Analytics”, all different names for approaches to make optimal decisions and to optimize the world.
For thousands of years, no big revolutions happened in this field. The mathematical approaches have of course been improved and better decisions could be taken, but only with the availability of computers in the middle of the 20th century, everything changed. The first important revolution was the invention of the Simplex Method in 1947. A next big revolution happened at the end of the century when Digital Twins started to be used for supply chain planning and optimization.
1940s: The invention of the Simplex Method
During World War II, the field of mathematical optimization got a lot of interest. There was a clear business case: how can we minimize cost and maximize the impact of our military activities? Especially in England and the US, thousands of mathematicians were employed in this field.
One of them was George Dantzig, who stopped working on his PhD in Berkeley and joined the US Air Force. In 1947, he published the Simplex method for solving linear programming models efficiently. This was a revolution in the area of mathematical optimization and combined with the availability of computers it had a huge impact on this field.
The Simplex method is still used today in solvers like CPLEX. We can say that Dantzig created a mathematical model that was a much better representation of the real world than anything used before, including an efficient algorithm to find optimal solutions of this model.
Since 1947, computers have become extremely powerful, more efficient solution algorithms have been invented, and the models have been extended with more capabilities.
1990s: The use of a Digital Twin
During the 1990s, people who applied optimization technology to solve real world problems realized that although mathematical solvers were helpful tools, they were limited. Research at universities and development at companies such as IBM (who acquired ILOG in 2009, who acquired CPLEX in 1997) helped make the mathematical solvers work faster. But, despite the addition of capabilities such as quadratic constraints, it became clear that the mathematical solvers are too limited to solve real world optimization puzzles. Real world puzzles are excessively large to be solved by a mathematical solver and the mismatch between the real world and the mathematical model is too large. The big revolution happening in the 1990s was the addition of a Digital Twin.
A Digital Twin is a model of the real world that is as close to the real world as possible and not necessarily close to the model needed by a mathematical optimizer. Also, people have realized that in the supply chain planning & optimization arena, reality is not only mathematical in nature, as Pythagoras claimed. Soft knowledge and human interaction are important next to mathematics. So, a Digital Twin allows humans to interact with the planning, shows the consequences of planning decisions with regard to Key Performance Indicators (KPIs) and to constraint violations, being modeled as close to reality as possible. Digital Twins have simply much more flexibility than the models used by mathematical solvers. For example, constraints in a Digital Twin are not limited by rules such as everything is linear, like in Dantzig’s model. The model is also not limited by a rule that it has to be represented as a graph like in Dijkstra’s model.
2020s: The state of supply chain optimization nowadays
If we look at the largest and most successful companies in the world solving supply chain planning & optimization puzzles, all of them (including us) are using an approach where a Digital Twin model is used. This Digital Twin model is as close to the real world as possible but not necessarily close to a Mathematical Model. The Digital Twin is not only a successful concept in supply chain planning & optimization; it is a key concept within all Dassault Systemes solutions.
As Seppo explains above, the approach we take today relies on the combination of digital twins together with algorithmic support to solve complex supply chain problems. In many cases, this is a ready-to-go digital twin model that only requires the customer's data and can leverage pre-built automation for decision making. In other cases, we use the flexibility of our modeling language to adjust the digital twin and the appropriate algorithms to solve more unique problems. But the digital twin is always central to our approach to ensure we do not lose sight of the challenges and needs of the real-world.
