Calchas

From my discussions with ITA Hacker, and my own guesses about what is going on:

On a multicity itinerary, the sheer number of possible routes, carriers and fares can be enormously high. Also, if you ever read fare rules, you will know the allowable combination of different fares on different carriers can be quite complicated. So it is not sufficient to have a list of fares in price order, you also need to inspect each rule and confirm the proposed routing is allowed under it. And then you need to do that for every fare, every possible series of connections between the cities you want to go to, for each carrier. And if you have multiple fare components, you need to check that the combinations are mutually allowed. Plus each route has different taxes and fees to be checked, and the fuel surcharge as well.

It gets to a point where it is no longer computationally feasible to crunch through all the possible combinations and compute the price on each one. ITA have recently raised the search time to 90 seconds, which has been helpful, but at some point a number of options have to be discarded before they are even reviewed. Hopefully it throws away the most expensive options.

ITA designs a number of very intelligent algorithms to try to figure out the fare combinations in advance that are likely to work together and are likely to be cheap. This is actually the product they sell to travel agents and airlines.

Once you have pinned down the first few sectors on your itinerary, the computational difficulty of the problem has fallen by several orders of magnitude, and the ITA Software can now recalculate the remaining possibilities, whereupon it suddenly discovers there is a much cheaper way of pricing the proposed itinerary available.