HEATHROW Airport on a wet Wednesday afternoon and 300 passengers are sitting in a departure lounge waiting to board their plane to Los Angeles. A voice comes over the public address system apologising for the delay and explaining that the airline is waiting for a replacement aircraft to arrive. The plane scheduled for that route has been taken out of service for essential maintenance.
Just another day in the life of an airline, and another few hours on the ground for passengers and crew. But such delays cost money: up to tens of millions of pounds a year, according to some airlines. With so many variables, from the availability of a crew to putting the right aircraft on long-haul flights, scheduling aircraft is recognised as one of the most intractable problems imaginable. Solving the problems could take years, but airlines need the answers in seconds.
Now, after more than twenty years of trial and error, scientists are discovering how to crack such tough, computational nuts. They are getting to the root of what constitutes a 鈥渉ard problem鈥� and are taking lessons from nature, mimicking, for example, how the fittest set of genes is selected in living organisms. And they are relying on computers to find the Achilles heel of these mathematical monsters.
Advertisement
The results have been spectacular. Take the scheduling of aircraft maintenance. Earlier this year, a team at IC Parc, an industrial arm of Imperial College, London, discovered a way to allocate more than a hundred aircraft to several hundred flights. The calculation included more than a dozen everyday constraints, such as the need to meet maintenance schedules, and yet it took less than 5 seconds to solve on an ordinary desktop computer.
This is only one example of how such calculations can help organisations make their day-to-day activities more efficient. Other commercial concerns, ranging from telecommunications operators to retail companies, recognise the need for swift mathematical solutions to their increasingly complex organisational problems. The commercial stakes are so high that some of them are keeping their solutions close to their chests.
Cracking these problems has become one of the hottest areas of computer science since its humble beginnings in the 1970s when researchers were first asked the apparently simple question: just what is a 鈥渉ard鈥� problem?
The obvious answer is that a hard problem is one whose sheer size rules out any chance of solving it by a lucky guess. Take the example of finding the shortest route between a number of different cities, the so-called travelling sales man problem. Starting at any one city, our mythical sales rep could try to find the shortest route simply by trying out one route at a time until the quickest is found. This may sound simple enough, but as the number of cities grows, the number of routes the rep must check out grows extraordinarily quickly. In mathematical terms, the number of routes grows as n!, or factorial n, where n is the number of cities. With four cities, for example, the number of routes will be 1 脳 2 脳 3 脳 4, a total of 24. For just 25 cities, however, finding the best route is equivalent to finding one particular raindrop in all the world鈥檚 oceans.
The sheer number of alternatives wouldn鈥檛 matter if, instead of trying out each in turn, there was some clever mathematical recipe for sniffing out the right one. Thus any definition of a 鈥渉ard鈥� problem will depend on the cleverness of the recipe needed to solve it. In 1971, the mathematician Stephen Cook, now at the University of Toronto, nailed the issue of the definition of 鈥渉ard鈥� by inventing the concept of 鈥淧鈥� and 鈥淣P鈥� problems.
Roughly speaking, P problems are the easy ones. They take their name from the fact that the time a computer needs to solve them grows as some 鈥減olynomial鈥� function of the characteristic size of the problem. To be precise, the running time grows no faster than a fixed power of this characteristic size. One example is sorting a set of n business addresses into alphabetical order. Even when the addresses are badly jumbled up, the best sorting algorithms can arrange them alphabetically in a time that grows as n2. Thus, if it took 5 seconds to sort out 1000 addresses, it will take around 20 seconds to sort out 2000 addresses.
Time travel
This doesn鈥檛 seem too bad, which is why P-class problems are generally regarded as easy. So-called 鈥淣P鈥� 鈥� roughly speaking non-polynomial problems are a different kettle of fish. The time required to solve one of these can increase exponentially with the size of the problem, for instance, as 2n, or worse still as n!. The travelling salesman problem is a case in point: if a computer takes 5 seconds to solve a 10-city example, it will take around 100 000 years to solve one involving 20 cities.
Since Cook鈥檚 ground-breaking work, computer scientists have classified many hundreds of practical problems as being either P or NP. The bad news is that most of them have turned out to be NF, including scheduling flights, touring cities and drawing up timetables. Even apparently simple problems such as jigsaw puzzles and crossword designs turn out to be 鈥淣P-hard鈥�.
The good news is that these theoretical results strictly apply only to worst-case scenarios, for example, when no simple patterns 鈥� such as airports that offer flights to just a few destinations 鈥� exist linking any of the cities in the salesman problem. In real-life problems 鈥� the ones that commercial companies are interested in solving 鈥� patterns often do exist, and this gives computer scientists the chance to box clever, exploiting the patterns to speed the solution of NP problems. 鈥淭he concept of NP-hardness is important in that it unifies a lot of research on different problems,鈥� says algorithm expert Colin Reeves of Coventry University. 鈥淗owever, if you do have an NP-hard problem to solve, there鈥檚 no reason to throw in the towel 鈥� your problem may not be a worst-case instance at all.鈥�
Deep valleys
For practising problem-solvers like Reeves the challenge is to find algorithms that give reasonably good solutions reasonably quickly.
In recent years, an arsenal of general-purpose algorithms that produce reasonable solutions to a wide variety of NP-hard tasks has been built up. Behind them all is the basic idea of a 鈥渓andscape鈥� of solutions covered with 鈥渧alleys鈥� regions where, say, the length of a sales rep鈥檚 tour or the cost of some airline schedule dips. The deeper these valleys, the better the solution to the problem. What the algorithms must do is seek out these valleys, explore them and try to land in the deepest one they can find in a reasonable amount of time.
Computer scientists have been eclectic in their search for clever ways of homing in on these valleys. So-called simulated annealing, for example, draws inspiration from solid-stat physics and the way the atoms in molten metals cool down to form crystals in a state of lowest energy. Programmed into a computer, the algorithm metaphoricall roams around the solution landscape, moving downhill when it can, but occasionally moving uphill to avoid getting stuck in the shallow 鈥渧alleys鈥� of mediocre solutions.
The probability of these uphill moves occurring is dictated by an analogue of a 鈥渢emperature鈥� set by the parameters of the task, for example the number of jobs and how long they take on various machines. This temperature starts out high, allowing lots of uphill moves, and plenty of searching, but ends low, allowing the algorithm to focus on the better solutions it has found during its search.
Genetic algorithms, in contrast, take a leaf out of Darwin鈥檚 book, using 鈥渟urvival of the fittest鈥� to turn a set of mediocre initial guesses into near-optimal solutions (鈥淕rowing money from algorithms鈥�, New 杏吧原创, 3 December 1994). Each set of guesses is rated for its ability to solve the problem 鈥� its 鈥渇itness鈥� 鈥� and the better ones are selected to undergo random mutation and 鈥渕ating鈥� with other solutions. The offspring are then rated, and the process continues until acceptable solutions emerge.
Some algorithms are far less conceptually sophisticated, yet still appear to work. 鈥淭aboo search鈥�, for example, is an algorithm that tries out various moves around the solution space in search of valleys, and then picks the most promising move. The reverse of that move is then forbidden and added to a short 鈥渢aboo鈥� list whose oldest item is then dropped. The result is the creation of a 鈥渟hort-term memory鈥� of moves to avoid. This prevents regions of potential solutions being re-explored too soon, while reducing the chances of becoming permanently stuck in a suboptimal solution 鈥渧alley鈥�.
The performance of such algorithms can be very impressive. Using a variety of techniques, including some Darwinian-inspired algorithms, David Applegate of Bell Laboratories and his colleagues last year broke the record for solving the travelling salesman problem when they found the most efficient route in a tour involving 7397 cities. Admittedly it took the equivalent of 3.5 years on a single workstation to achieve, but then a brute-force attempt would have had to check out around 1025407 different tours, and would have taken far longer than the age of the Universe to do so.
The real value of such monster calculations is not their speed, however, it is that their solutions have been shown to be the best possible. As such, they can act as a gold standard against which the performance of commercial algorithms can be compared. Usually these don鈥檛 have to guarantee finding the absolute best solution to a huge problem: ones that are within 95 per cent of the best are perfectly acceptable. Commercial algorithms, however, do have to be fast.
The effect of dropping the 鈥渁bsolute best鈥� demand can be dramatic. For example, an algorithm developed last year by Shara Amin and colleagues at BT Laboratories in Martlesham, Suffolk, can get within a few per cent of the best tour on a 100-city travelling salesman problem in a few seconds, and for a 3000-city problem in 25 minutes, they expect to find a reasonable solution to the 7397-city record in just 2.5 hours.
But while some special algorithms do seem able to perform miracles with some NP-hard problems, working out which general type of algorithm to apply to which problem is still a black art. 鈥淭here are rules of thumb, though some are commercially sensitive,鈥� says Nick Radcliffe, who is professor of mathematics at Edinburgh University and runs his own problem-solving company, Quadstone. He says that most of the rules are pretty basic, such as using algorithms that have worked well on other problems with a similar structure. However, some techniques, particularly genetic algorithms, seem to offer a wider scope of application than others, making them worth including in an attack on problems ranging from flight scheduling to travelling salesmen. 鈥淲e usually hybridise genetic algorithms with anything else appropriate, and this tends to yield the best answers,鈥� says Radcliffe.
Reeves adopts a similarly pragmatic approach: 鈥淭ry several methods starting with the easiest to use, or program, until you are fairly satisfied with what you are getting.鈥� What those tackling real-life situations would dearly like, of course, is a set of rules that would take the guessing out of the choice of algorithm.
Theorists are now looking at this question, and the first papers describing such rules are beginning to emerge. One in particular, which has been circulating on the Internet since the summer, has caused quite a stir. In it, David Wolpert and Bill Macready of the Santa Fe Institute in New Mexico claim to have knocked the idea of an algorithmic 鈥減anacea鈥� for all hard problems on the head.
Whenever a new general algorithm like taboo search or genetic algorithms is invented there is usually a flurry of papers showing how wonderful it is at tackling various notorious NP-hard problems like the travelling salesman. But eventually someone comes up with a problem which the shiny new algorithm is not particularly effective at solving, and the dream of a cure-all for NP-hard ills is dashed once again 鈥� at least, until the next time.
Hope of an algorithmic panacea may spring eternal, but according to Wolpert and Macready, it鈥檚 a mirage. In what has been dubbed the No Free Lunch theorem, they claim to have shown that even if, say, genetic algorithms do better than simulated annealing at a certain type of NP problem, there will be just as many of a different type of problem where genetic algorithms will perform less well.
The No Free Lunch theorem remains very controversial among algorithm experts, and certainly not everyone is convinced. 鈥淚 believe that their statement is deeply misleading,鈥� says Radcliffe. 鈥淭echnically, their result is correct: it is their interpretation of it that I disagree with. Their proof is valid only for non-repeating searches, that is, those that never visit the same point twice. Neither genetic algorithms nor simulated annealing fall into this category, so I would say that the basic claims are false.鈥�
What everyone agrees on, however, is that there is no substitute for thinking hard when trying to crack a specific tough problem. Barry Richards and his colleagues at IC Parc are using artificial intelligence to spot the features in a problem that can make it much easier to solve. 鈥淲hen people try to solve real-world problems they typically have a first stab at it, and it doesn鈥檛 work very well,鈥� explains Richards. 鈥淏ut then they start to see the structure in a problem and spot short cuts. We鈥檙e looking to rationalise the methodology for doing that.鈥�
Using constraint logic programming, a method of reasoning with many variables that allows them to stay within many constraints simultaneously, the IC Parc team has developed parcPLAN, a software package that it claims can cut through the complexity. It does so by spotting the idiosyncrasies of the specific task, such as its symmetries, for example, arrangements of aircraft types and journeys that lead to the same maintenance costs, and bottlenecks, such as major maintenance jobs, which are better dealt with early before too much flexibility is lost.
鈥淲hat we鈥檝e succeeded in doing is finding an algorithm that suits this particular problem very well,鈥� says Richards, who worked with computer company ICL, BT and British Airways on the development of parcPLAN. Using real-life data on plane types, routes, maintenance schedules and a host of other constraints, parcPLAN has proved capable of juggling dozens of planes over hundreds of routes to produce the optimum schedule in just a few seconds 鈥� the type of speed needed by a real airline. 鈥淭he challenge now is to find generic ways of repeating this success on any problem,鈥� says Richards.
IC Parc is not alone in taking up this challenge: teams in the US, such as the Massachusetts Institute of Technology and AT&T in New Jersey, are working on it, too. They are all motivated by the belief that computer science is on the brink of conquering huge, commercially important problems such as scheduling and routeing. According to Richards, the growing consensus is that this will be achieved by combining the cunning of algorithms that seek out short cuts, such as parcPLAN, with the muscle of standard search methods like genetic algorithms. 鈥淲hat we鈥檙e doing now is pushing forward this new research agenda,鈥� he says 鈥淎nd we鈥檙e helping make companies a profit on the way.鈥�