4.2.2 Optimisation problems
In general terms an optimisation problem is just one in which the task is to find the best possible solution from among a number of alternatives. Seen in these abstract terms, a huge proportion of the problems we look to computers to solve for us are optimisation problems. You'll recall from our earlier discussion that Turing and the Symbolic AI trail-blazers of the Dartmouth conference saw certain kinds of intelligent thought as a process of search, in which the best solution is selected from all the alternatives. If they were right, artificial intelligence is a set of optimisation problems too.
In mathematics, an optimisation problem is one in which the task is to find the point, or points, at which a function reaches its maximum (or minimum) value, generally subject to some constraints. To take an extremely simple example, suppose we want to find the maximum area of a rectangle with a perimeter of no more that 16 cm. We can formulate this as an optimisation problem, as follows:
Assuming the rectangle has sides xand y, the function f(x,y) we are optimising is x * y (since the area of a rectangle is obtained by multiplying the lengths of its sides). The problem is to find values of x and y that give the maximum value for f(x,y). The constraint is that 2x + 2y ≤ 16.
This example may seem quite trivial, but such problems can prove hideously tough computationally.
In computing, however, optimisation problems are generally ones in which the search is for the best solutions from among a number of possibilities. The most frequently occurring of these are combinatorial optimisation problems (COPs), where, as the name suggests, the task is to find the best combination of discrete values from some given set. The classic COP – familiar to every computer scientist – is the Travelling Salesman Problem (TSP), probably the most commonly used example in computing courses anywhere. The TSP is not a realistic problem, but it is popular among teachers of Computer Science because it is so simple to state and to visualise. Here is a brief description of it – if you know about it already, by all means skip the next couple of paragraphs.
A salesperson is required to visit N cities, each city being a certain distance from the others, for example as in the following grid, showing a five-city TSP.
| Exeter | Bristol | Manchester | Leeds | London | |
|---|---|---|---|---|---|
| Exeter | X | 74 | 236 | 278 | 173 |
| Bristol | 74 | X | 165 | 207 | 119 |
| Manchester | 236 | 165 | X | 43 | 198 |
| Leeds | 278 | 207 | 43 | X | 195 |
| London | 173 | 119 | 198 | 195 | X |
Notice that in this example the grid is symmetrical, but it need not be: a different route could be used to get from Manchester to London, say, from the route from London to Manchester.
The task is simple: find the order in which to visit all five cities that gives the shortest round trip, or tour. This looks easy enough to achieve, on the face of it – just try every combination until you find the best one. But this approach, known as brute force, very rapidly becomes impractical: our example has five cities, and there are 120 possible combinations of this basic set. However, if the salesperson has to visit ten cities, there are 3,628,800 tours; for fifteen cities, 1,307,674,368,000; for twenty cities the number of tours is roughly 2.43 x 1018. As the number of cities increases, it rapidly becomes impossible for any actual or imaginable computer to handle the number of combinations involved, using the brute-force approach – it would just take too long. The brute-force strategy entails what is termed a combinatorial explosion. The TSP is a problem that is known in computational complexity theory as NP-hard. Since this is not a course concentrating on the theory of computation, all we need say about this is that NP-hard problems are ones in which there is no known algorithm for solving them in any realistic period of time (although such algorithms may exist).
SAQ 13
I mentioned above that optimisation problems are sometimes constrained. Think of one or more possible constraints on the TSP.
Answer
One obvious constraint is that the salesperson should never visit the same city twice. We might find that there were other constraints, such as it being impossible to move from one city (say Manchester) to another (say Leeds) for practical reasons, such as absence of suitable transport, company rules, etc.
As we said above, the TSP is not a problem of any practical importance in itself. But it has all the features of a vast set of problems that are of major importance in computing, engineering and science. Here are two examples:
- Circuit board drilling – In the manufacture of printed circuit boards, computer-controlled machines drill holes and insert parts into the boards. The problem is to plot a route for the tool to travel across the board that will minimise machine time and tooling costs.
- Protein folding – Proteins are made up of chains of amino acids, which are transcribed from ribonucleic acid (RNA) as a linear sequence. After transcription, the sequence rapidly folds up into a three-dimensional structure which is generally the most energy-conservative one possible. The problem is to predict, for any given protein, what that 3-D structure will be, from among all the possible formations its sequence can fold into.
SAQ 14
Note down one or two other examples of optimisation problems you've heard of.
Answer
All sorts of answers are possible. Most planning and scheduling problems, for example, are optimisation problems. Scheduling of aircraft flights, working out the order in which to remove the supports on a completed structure such as a bridge, and planning the layout of a factory floor are all good examples. Even planning the best way to get to work in the morning, a classic example of an artificial intelligence problem, is a matter of optimisation.
Because they are so important, many computational strategies have been developed to tackle COPs. You've probably come across some of them yourself, but there's no need to look at any of them here. Instead, I just want to make two important general points about optimisation problems:
- For every TSP, there may be one, and only one, best solution. But unless we can use brute force, which for larger problems we just can't do, then it may simply not be possible to find that one, best solution. We may have to be satisfied with merely very good solutions.
- Given that in practice it is very difficult to find the best, or even good, solutions by brute force, search strategies have to be supplemented in some way. Clever shortcuts in the search process have to be found. These are the heuristics I mentioned. For Symbolic AI thinkers, heuristics are where the intelligence in artificial intelligence comes in.