Operational Research: Today (3/4)

Tom Walker
Tom Walker

What is the best way to solve climate change? Maybe the answer is to don some hi-vis and glue yourself to the M25. Although perhaps, like environmentalist James Lovelock, we should all just accept our impending doom and spend our remaining years before the apocalypse doing donuts in Ferraris. 

However, there is a more optimistic view, put forward by Steven Pinker and Matt Ridley amongst others: 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.

History can rhyme: OR was initially developed to counter the existential threat of world wars, and now promises to aid us in our coming "wizard war" reversing modern society’s toll on the natural world.

From the 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 - have begun to be solved at scale.

At PreWarp, we specialise in optimal inventory and pricing decisions within fashion, casting these problems as Mixed Integer Programs.

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 reverse some of the purpose of linear programming (which combats the tractability 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.

Today, operational research is proving incredibly powerful in maximising profits and efficiencies while minimising waste in countless settings.

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.

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…