This post and the next are inspired by episodes of the podcast Linear Digressions. In this post I will describe general stuff – what kind of problem is suited to optimisation, and an overview of what optimisation is. In the next post I will go into some details – two related approaches to optimisation, with a bit of code to illustrate them.
The type of problem we’re trying to solve
There are many types of problem where there is a single correct answer, and all other answers are wrong. They include simple maths things like “What’s 2+3?”. These aren’t problems to tackle with optimisation.
There are other problems where there are many answers, and instead of a binary separation into correct and incorrect, the answers lie along a line from worse to better according to some property. These are things like finding the route to get from your home to somewhere else, where you judge options by the distance travelled or the time taken. The goal is to find the optimal or best answer.
What makes life a little tricky is something that’s often only implied in the setup of optimisation problems: The answers don’t just sit there ready for you to choose between, so you can’t just sort the answers by their value, and then pick the best. Instead, you need to put resources into finding each answer – CPU time, memory, network bandwidth etc.
Another thing that can make life tricky is that I’m assuming you can’t use maths to guide you. If there were a nice equation that described how good or bad a result you’d get at a given point on the line of all solutions, then you could use the equation in some way to quickly move to the best solution. For instance, if the value followed the curve below, you could differentiate the curve’s equation to find the slope of the line, then pick the place where the slope is zero (the line is horizontal), which in this case will be the maximum.
I’m assuming there isn’t such an equation, and so you don’t have the shortcuts it provides.
A simple, but probably wrong, approach
One simple approach is to generate all answers, and then pick the best. The good news about this is that you are guaranteed to get the best answer. However, there is bad news too: it has the biggest cost of all (sensible) approaches. Depending on the kind of problem you’re trying to optimise there might be an eye-wateringly large number of answers, and so generating all of them will be very expensive.
One easy way of having many answers is for each one to be built up as a combination of options. For instance, if you were trying to solve the Travelling Salesman Problem there would be the choice of which city you go to first, combined with the choice of which city to go to next and so on. As the number of cities grows, the number of possible routes grows very quickly.
Notice that I’m saying that this is probably wrong, not definitely wrong. If you want to definitely have the best answer, regardless of the cost, then a brute force approach of going through all the answers is correct for you.
However, in my experience this is not the most common goal. Instead you want something good enough that’s also cheap enough, i.e. the perfect is the enemy of the good. Ideally you want to be able to define what good enough and cheap enough mean for you (while accepting that you must make a trade-off between the two). So, something like the best answer out of the 100 answers I’ve examined or the first answer I get to that’s at least a 95% perfect fit. In the first approach you have a fixed upper limit to the resources you’ll use, but no guarantee on the quality of the result you pick. In the second approach you have a fixed lower limit to the quality of the result you pick, but no upper limit to the resources you’ll use.
In the follow-up article to this one, I’ll describe one interesting method of picking a good enough result, and how it’s an improvement on a simpler method.
Summary
Sometimes the problem you’re trying to solve isn’t a simple calculation, but rather is finding the best option among many. While it’s sometimes worth computing all possible options and then picking the best, sometimes you want an answer that’s good enough after a small enough amount of effort.
Random Tech Thoughts 