Indeed, I left out the direct routes (and everything in between) because the number of paths was large enough to make my point.

Sophistication buys you nothing. It costs. It increases software bug density. You need the sophistication to get a reasonable answer in a reasonable amount of time -- but it's a necessary evil, not a benefit that is good to have.

The dijkstra algorithm is an approximation. That's why it gets an answer that is good enough in an acceptable amount of time.

Just to throw in two more cents... ITA Software (based in Cambridge, Mass) is packed with MIT and Harvard computer engineers. (Check out some of their staff: http://www.itasoftware.com/careers/l...ur-people.html)

I point this out in support of what igopogo wrote above-- I'm sure they already know the way to shave computing cycles off searches. I think ITA's real challenges are all in product management (i.e. specific user experience and featureset), not computing cycles, search timeouts or other raw horsepower issues.

(And they're probably staying awfully busy with Google integration, too...)

Indeed - you need very skilled engineers for this problem.

This doesn't support igopogo's point, it supports mine. If one could simply apply an algorithm as common as dijkstra, you could hire high-schoolers for the job.

I disagree. Look at their job applications. They're computational and programmatic puzzles. They're looking for more good engineers.

Perhaps I misunderstood your original post.

I see their open positions, but that doesn't dissuade me from thinking they need to focus on product management at least as much as the engineering side of things. Currently ITA looks like a fantastic power-tool that is designed and built by engineers.... that's awesome, and we all love it, and use it all the time. But in taking that power tool and making it part of Google (unsurprisingly, another company [and set of products] designed and built by engineers), they will want to be thinking more "big picture" about the features more mainstream customers want and how to make them more user-friendly.

(Of course, for those of us here on Flyertalk... we probably want more powertool-y functionality... damn the interface, full speed ahead! ;) )

The bottom line is that finding the definitively cheapest airfare is an unsolved problem. There is simply not enough processing power available to tackle the problem, even with the most sophisticated algorithms that find exact answers. Hence why adding restrictions to your search can sometimes reveal a better price. All aggregators apply a "lossy" algorithm, which very quickly finds something that is likely to be close to the best airfare. It's generally good enough, but it's a trade-off.

They can only let you leech so much CPU. Some search tools out there offload some of the processing into the visitors machine (e.g. dohop), so the server gives you a small database, and you run javascript to find the best route from a small number of relevant records.

Certainly there are copious limitations of ITA software (even though it's the most powerful all-around search tool). Perhaps the biggest limitation is that it cannot handle multi-booking flights. This means it often does not find the cheapest route (it finds the cheapest convenient flights). I would hate to see resources wasted on management as opposed to improving a tool that clearly has plenty of room to evolve.

How interesting! I just tried dohop and here's the records they dump onto my computer, to let me do super-quick local filtering/sorting. Love this approach.

http://ds.dohop.com/search/?lang=en&...1211&d2=141211

And skilled Flyertalkers. I use ITA as an iterative search engine. e.g.

I first search MSP to ONT (and include neighboring airports and +/- 1 day) to get an overall idea of general fares

I then limit it to the cheapest airport/day combinations and add in DL+ and/or DL, DL, DL

I then try forcing it between certain city pairs (usually those that are served by competitors) For example for ONT, I might force it through LAX.

I often throw in different hub cities to see if I can bring the mileage up, etc.

I definitely find that often more search criteria = cheaper fares, but of course, not always.

It's sophisticated, not complicated. You're right, a high school student could do it.

Dijkstra will be very unhappy to hear that. Whoops, if he were alive. He was under the impression that it arrived at a solution. He's got a bunch of mathematicians convinced also.

My only point was, the search is not an unsolved problem in **math**, and the cheapest route can be solved quickly. But finding the absolute cheapest route is not necessarily what ITA wants to do. The cheapest route may not have seats available, or may not be one that the average Joe wants to take (i.e. may involve a couple 23 hour layovers and a trip to Alaska and back, or maybe a 5-minute connection at DFW). Sure, we'd like to find the lowest fare even it means spending some time 2000 miles off our path...might prefer it actually. But ITA is in the business of serving average joes (or helping airlines serve average joes) so I'm gonna guess that more "thought" goes into determining what constitutes a reasonable, available route, and finding those routes. Working in the squishy, social, computer-guessing-what-a-human-wants is exactly what google (whoops, ITA) engineers are supposed to be doing. This is almost an unsolved (or perhaps un-optimized) problem in social science.

They like us to bang on their system and see if it works, but they are really not designing the system for us. And certainly they are not going to give us access to an algorithm that takes one full minute of real server time, that would be way too expensive.

Don't forget that Google isn't the only user of ITA's product and they aren't just concerned about making it human-usable in the future...that stuff is already happening now. ITA powers several airlines' search results, including Alaska's. It's highly customized to favor results on AS metal and only search a limited subset of partner carriers and fares.

ITA's matrix is a publicly-accessible testbed with access to the raw data and technology they offer, but it is far from the core market and focus of ITA's resources.

I'd still like (and would pay for!) a power-user tool, though. ;)

I've noticed that if you look at the booking details of an itinerary using Matrix 2, the base fare is displayed in the currency of the sales city, whereas in Matrix 1 it's always displayed in the airline's currency of record. Is it possible to force Matrix 1 to change the currency in which it displays the base fare?

(I see that the fare construction at the bottom of the booking details page in Matrix 1 does display the equivalent in the sales city currency, but this is rounded off to the nearest unit, and so it is usually slightly different from the amount displayed by Matrix 2.)

Alternately can anyone suggest a way to look up the current NUC conversion rates?

xe.com is what I use for conversion rates.

Sure. But the current daily exchange rate is generally not the same as the monthly published IATA conversion rates, which is what is needed here.

Not directly, but you can retrieve Fares in NUC in the KVS Tool, if desired. For example:

[KVS Availability Tool 6.7.0/Diamond - Sabre: Fares/DotRes/US]
There you go:
http://www.IATA.org/ps/publications/pages/iroe.aspx
:)

I'm not sure if it's just my newbie incapabilities with the ITA software or this unsolved mathematical problem you speak of, but I hope someone can enlighten me on my current dilemma.

I've been looking for the cheapest possible one-way flight from basically anywhere in Europe to SYD between 1 - 10 Dec 2011. I found LIS-BRU-AUH-SYD for $521 on Dec 2, 3 & 5 after a very long search. But now I'm trying to replicate it on ITA by putting 4 other EU airports in the "Departing from" field (LHR, CDG, FRA, MAD, LIS) and SYD as the destination, however the lowest price shows up as $999. What am I missing? Is there a limit of 3 airports that you can search? The $521 (and a recent $515 addition) from LIS show up when it is one of 3 airports, but not when it's the last of 4 or any thereafter.

However, if I put a list of 30 airport codes in, I come out with $665 as the cheapest, but the search finds some flights with some airports that I listed at the end of the line (i.e. LHR, CDG, FRA, MAD, AMS, FCO, MUC, IST, LGW, BCN, ORY, ZRH, DME, AYT, CPH, PMI, VIE, SVO, OSL, DUS, MXP, STN, DUB, MAN, BRU, ARN, ATH, TXL, LIS, HAM, HEL).

Ultimately I'd like to be able to search a number or airports at the same time, instead of one by one and know that I've covered all bases. I've also tried different things in the adv routing codes box as well, like X+, and EY+ (for X+ the cheapest is still $665, and interestingly for EY+ the exact $521 flight comes up but for $579?)

Any wisdom would be greatly appreciated.

why dont you just try to add 5 key cities in Europe to cover the entire region and then expand your search by 300 miles radius?

MAD | DUB | FRA | ARN| FCO should allow you cover most European airports...