When being greedy doesn’t pay
When making schedules or other complex decisions, one of the most tempting ways to solve the problem is to use a greedy algorithm. Load the most expensive item by weight into your ship or buy the giant butter block because it has the lowest unit price (and upgrade the fridge to fit your Cosco quantity containers). Greedy algorithms take the best option that is available according to a simple measure and ignore future consequences. But are they the best choice?
Traders in Assyria found themselves with a simple version of this problem moving tin and textiles. Tin is the smaller, and rarer part of bronze (the other being copper) which made it very valuable. Tin as a trade good is also very dense (heavy and small). Cloth, on the other hand, was valuable for the labour invested in it and was lighter and bulkier. Given the donkeys in the caravan had limited capacity in space and weight, the traders would take both goods at the same time [1]. A greedy approach might take all Tin, to maximise the use of weight, or all cloth to maximise the use of space. A far better option though is to take a mix, leave some tin behind to allow for the weight of some cloth. Exactly what mix you take depends on the price of both, and next week I’ll talk about Pareto curve which allows us to explore this trade-off.
Another example can be seen with sailing vessels. Sailing boats cannot travel directly up wind, but they can zig-zag back and forth at an angle to the wind and still make progress upwind. In this case, being greedy and pointing the vessel up wind will result in the vessel slowly moving backwards, with no progress at all. Turning away from the wind just enough to get forward motion is also sub-optimal. There is a trade-off between the speed of the vessel and the heading: pointing the vessel too close into the wind results in a slow speed while pointing the vessel 90 degrees to the wind gives the highest speed but in the wrong direction. In this case, for a given wind speed we can work out the best angles ahead of time. Racers will often have tables of the best angle for the given windspeed saving them from re-solving this problem whenever the wind changes.
Sometimes greedy algorithms are sub-optimal, but sufficient. The classic example is the packing problem. Say we are moving house and have many boxes of different sizes. The small truck that we’ve hired can carry plenty of weight, but has limited space. The perfect loading pattern that minimises the number of trips taken is quite difficult and computationally expensive. The very first box you place has flow on effects that change how you pack every subsequent box. Even though it’s not perfect, being greedy and placing the biggest boxes in first will deliver a good enough result. The difference between the perfect optimal result and the greedy result is very small.
So, how do we decide when a simple greedy algorithm is good enough? Ignore whether the problem is solved perfectly by a greedy algorithm and instead try a few solutions by hand. That is, get in the back of your removalist truck and shift some boxes around, move the tiller of your boat trying different angles or take out an ingot of tin and replace it with some textiles. If you see a material change in outcome, then that indicates that more complex optimisation might be needed. If instead there is little difference between your solutions, a greedy algorithm is likely all you need.
If you’d like upgrade your scheduling, contact us at Hello@NorthCardinal.com.au and let’s have a chat.
[1] Elizabeth Wayland Barber (1994). Women’s work: the first 20,000 years, p. 170
