Blog

Operational Research: Today (3/4)

Tom Walker
By 
Tom Walker
CTO

What is the best way to solve climate change? Some would have you believe that the answer is to dress up in red gowns and glue yourself to the M25. Or perhaps, like environmentalist James Lovelock, we should just accept our impending doom and spend the remaining years before the apocalypse doing donuts in Ferraris. 

However, there is a more optimistic view promulgated by people like Steven Pinker and Matt Ridley: that scientific progress will continue to outpace the increasing requirements of a growing human population, as it has consistently done in the past. 

Aside from the sexier technological solutions – Tesla electric pickups impervious to all except a direct blow from a sledgehammer, clean jet fuel from compressed algae, urban vertical avocado farms like something out of the Matrix – the operational research (OR) approach of making the most of existing infrastructure with clever maths may be unshowy, but often proves very powerful. There is a symmetry to this – while OR was developed to combat the existential threat of the world wars, it promises to aid us in our coming wizard war reversing modern society’s toll on the natural world.

From these seeds of linear and dynamic programming planted in the 1940s and 50s, forests of increasingly efficient algorithms have flourished into the modern day, and swathes of optimisation problems studied but intractable for decades before have begun to be solved at large scale in today’s operational research.

At PreWarp, the decision problems we specialise in are inventory and pricing decisions within fashion. These types of problems are usually formulated as Mixed Integer Programs (MIPs). 

MIPs are related to the linear programs developed by Dantzig, but with the extra constraint that some of the problem variables are integers (the counting numbers e.g. 1, 2, 3) as opposed to real numbers (which can take any value, e.g. 2.718). 

While this seems to undo some of the purpose of linear programming (it combats the computational complexity issue of many optimisation problems by simplifying the problem), this additional integer constraint often proves necessary to properly describe real world problems. A simple example from our own work: our customers often want to pick a markdown decision from a finite set of possibilities, say 30%, 40% or 50% off. In the linear programming setup, our models would be free to pick any number from a continuum between 30% and 50%, say 31.42%.

This added constraint makes efficient solutions harder to find, but from the kernel of Dantzig’s linear programming work, sophisticated modern algorithms have been found that excel at it.

MIP models see wide application in modern operations research. They are applied to famous optimisation problems such as the travelling salesman problem and vehicle routing problem where they enable the minimisation of transportation costs for fleets of delivery vehicles for companies. In the energy sector they are helping combat climate change by enabling governments to optimise the various components of their energy grids and deal with the peaky supply of renewable energy generators. MIP models also drive modern dynamic pricing strategies from Uber to Easyjet (but don’t let that put you off the beauty of MIP!). 

Elsewhere, descendants of Bellman’s work on dynamic programming such as Dijkstra’s shortest path algorithm help Google Maps calculate the most efficient route.

Today, operational research is proving incredibly powerful in maximising profits and efficiencies while minimising waste in countless settings, and promises to come to the aid of humanity in combatting the strain modern society is placing on the natural world. 

The specialised task of formulating these optimisation models remains a barrier to its broader uptake – however, in recent years, a glimpse of a generalised decision-making framework has emerged; one which can be applied to multiple diverse problems, and can learn over time to make strikingly superhuman decisions…


Still curious? Read on