Robert Gooding-Townsend, Science in Society editor
Late this February, gas prices in Vancouver surged to over $1.50 a litre, an increase of 20¢ in just two weeks. This was due to the shutdown of a key refinery in Burnaby. Around the same time, Taiwan was running out of toilet paper, which was partly caused by forest fires in Canada. When an essential product is suddenly in short supply, the consequences range from inconvenience to panic.
Canadian wildfires in 2017 led to sharply increased costs for toilet paper – in Taiwan. The algorithms used in supply chain management can’t mitigate unplanned risks. Images: (left) Ashcroft Reserve wildfire as seen across Loon Lake, BC. Photo by Shawn Cahill CC BY-SA 4.0; (right) by Santeri Viinamäki CC BY-SA 4.0
What do these stories have in common? For one thing, they expose how vulnerable our economy is to unexpected events. They also prompt us to look behind the curtain at our economy’s processing and supply chains.
Consider the complicated choices involved in refinery management. There are dozens of grades of refined fuels, each used in different industries with different demand levels, and with different costs and chemical properties. Switching between different production types is difficult and may require a temporary shutdown. A refinery owner may have several different refineries, with different capacities for production, storage, and shipping. So how much of what kind of fuel should be produced at each facility, and where should it be shipped? When should the company schedule maintenance shutdowns to have a minimal impact on the bottom line?
There are millions of dollars on the line, and these questions rapidly become too complicated for human decision makers. It’s no surprise that computers are used to make these calculations. What might be surprising is that the algorithms are in the public domain, and have been around since the 1940s.
It all starts with the simplex algorithm. This algorithm finds solutions to linear programs – problems with a whole bunch of options to achieve some goal, where all of the options are bound by some constraints. In the refinery management example, the goal is to maximize profit, the options are the different production levels of each fuel at each facility, and the key constraints are the capacities of each plant and the expected demand for each product.
Roughly speaking, the algorithm works by taking an initial guess – any solution that is feasible, even if it’s clearly far from optimal – and successively improving on it. It does this by systematically running up against the constraints, in a way that consistently achieves better performance in relation to the overall goal(s).
For example, in a refinery management problem, the initial guess may be to produce only one kind of fuel type. An early step in the algorithm might be to produce as much Grade A fuel as market demand allows; later steps might be to produce some (or more) Grades B and C, and shift production between different facilities. Each individual step is fairly straightforward, yet the final result will be the solution to a quite complicated problem.
If you would like to learn more, consider these links on linear programming (starts simple, long) and the simplex algorithm (shorter, more math).
One of the original problems that demonstrated the effectiveness of this algorithm was the problem of assigning 70 workers to 70 jobs. There are more than 10100 possible assignments, so it takes longer than the lifetime of the universe for any computer to go through them by elimination. But with the simplex method, this problem can be solved in minutes.
This flow diagram is a simplified representation of just one possible configuration for a refinery. With operations this complex, it’s no surprise that planning is heavily algorithmic. Image source: Wikimedia Commons. Mbeychok derivative work: Begoon – This file was derived from RefineryFlow.png:, CC BY-SA 3.0
Unlike other algorithms we hear about in the news, the simplex algorithm isn’t flashy or insidious. It was implemented on mainframes decades before Facebook was invented. The input data come from internal company information that just has to be organized. Even for people who object to a company’s business practices, it’s hard to take issue with the company finding the most efficient allocation of their resources.
Shortages occur when reality doesn’t match the inputs to the algorithm. Typically, management will use data from previous years as a guide to determine demand, raw material prices, and other factors. These may be adjusted to reflect known trends – inflation, population growth, changing consumption patterns, and so on. The algorithms can even be set to run different scenarios, so that a plan will be available for different situations. However, it cannot create a plan for unexpected shifts, such as a particularly severe forest fire season in another country. In fact, the ability to find optimal solutions with very tight constraints may backfire in these situations, since there will be less slack in the system. The algorithm can be rerun to figure out the best response to the new situation, but by then it may be too late.
This is a key trade-off that comes with this algorithm. It may introduce greater vulnerability to shocks, but it will be much more efficient when things go smoothly. It’s clearly a trade-off that many decision-makers are willing to accept. After all, we don’t notice the millions of shortages that don’t occur.
The simplex algorithm is one of the fundamentals of operations research, which underlies planning in a huge variety of fields: military planning, refinery operations, airline scheduling, portfolio optimization, inventory management, and more. Industry demands have led to the development of new areas of research – stochastic programming, which resembles the scenario-based approach described above, and robust optimization, which focuses on avoiding worst-case scenarios. Together, the algorithms in these fields are responsible for managing billions of dollars of operations each year. There is human oversight, of course, but huge portions of our economy are fundamentally under algorithmic control.
Historically, the widespread adoption of this algorithm occurred as part of the postwar technology boom. Like many other technologies at the time, it was developed for military purposes and later adapted to civilian use. Ironically, an algorithm that essentially implements centralized planning and distribution thrived in America, while in the Soviet Union, where this kind of algorithm was first formulated, it was neglected.
The simplex algorithm has certainly earned its place in history. So next time you go to buy something and find it available, spare a moment to think of the algorithm that ensured it was there.
~30~
Feature image: The Chevron refinery in Burnaby, whose shutdown caused Vancouver gas prices to spike. Image by Kyle Pearce CC BY-SA 2.0
