gorithm

Beware of Orbitz, and their sleazy opt-out offers

I booked some international flights on Orbitz tonight, and I was shocked to find an email about $137.37 in travel insurance I knew nothing about.  Apparently, they have an opt-out insurance offer from a company called AccessAmerica on all their international tickets.  I didn't see it among all the rental car and hotel offers I ignore trying to buy my tickets. 

I had to call and wait on hold with Orbitz in order to get my money back. I wonder how many people they trick, adding big fees for fairly worthless, narrow insurance. 

I guess now I have a reason to choose among Expedia, Travelocity, and Orbitz.  I had always used all three, but now I guess I'm down to two.

Gurobi by the hour

If you follow the field of Operations Research at all, you've probably heard of the new company Gurobi. Started by three big CPLEX guys who left to go out on their own, it is trying to be the new state-of-the-art solver for linear programming (LP) and mixed integer programming (MILP). Their stand alone solver should be released any day now.  (You can already get it embedded in other modeling systems.)

I'm looking forward to it for a couple of reasons.  The first is that they promise an object oriented Python interface. I like Python as a language, and there isn't a really slick interface to a good solver.

However, I have another, bigger hope.  I hope I can get Gurobi by the hour.  Their website says:

Focused not just on the technology, Gurobi will also be introducing several new, more flexible delivery models for optimization technology, models that we believe will better serve our customers and the market in general.

That could mean lots of things. What I really want is to be able to use their solver on an Amazon EC2 instance, and pay by the hour. 

Amazon EC2 lets you fire up a computer on demand, paying only for the resources you use.  Their "High-CPU Extra Large Instance" has ideal specs for solving math models.  It has 7GB of memory and 8 cores of CPU, all for only $0.80/hour. You can get Windows or Ubuntu Linux (among others), which are the initial two operating systems Gurobi is supporting.   The 8 core machine should be a great test bed for the shared memory parallelism that is built into Gurobi.

If Gurobi is smart, they'll create a custom Amazon Machine Image (AMI) with their software already installed.  Amazon already has a system called DevPay that (I think) lets you bill for your software by the hour. What if you just paid $3/hour for this instance, with $2.20 going to Gurobi, and the $0.80 paying Amazon for the hardware.

That would be a complete game changer in the delivery of optimization. Instead of having to buy a big multicore box, and get a $5,995 license, you just fire up an EC2 instance, and pay them by the hour.  It hugely lowers the bar to experimenting. 

It also allows your run parallel instances without breaking the bank. We used to use CPLEX on a single PC.  However, we switched in the end to running COIN-OR open source software on a cluster, because there were times we needed to run lots of independent jobs in parallel. I imagine that would be true of most customers.  CPLEX charges insane money for parallel licenses.  With an hourly license scheme, you could just fire off 50 EC2 instances, and get all that work done at once.

It would be the perfect way to sell a program like Gurobi.  Instead of having to deal with demo licenses that restrict problem size, just rent out the full version.  If you price is right, then heavy users will still want a perpetual license.  If you amortize the $6000 over 2 years, and 250 work days a year, you get $12/day in revenues.  At $2.20/hour, you would break even in 5.5 hours per day.  Heavy users will still buy perpetual licenses, but you'll get a bunch of "casual" optimization customers that would otherwise turn to COIN, who will pay $20 bucks to solve a particular problem.

The Economist Rap

I've been a devoted reader of The Economist for years.  I really love it. So I have to link to this great rap (MP3) about my favorite magazine from the group Psikotic.  The lyrics sound like they really read it - they talk about the Big Mac Index, the weird ads, their editorial bias, the whole works. 

Missing paper by Donoho and Tsaig

Apparently, one of the authors of this paper lost it due to a computer failure.  I've got it on my hard drive, so I've reposted it for them (or anyone else).

Fast Solution of l1-norm Minimization Problems When the Solution May be Sparse
David Donoho and Yaakov Tsaig

Download FastL1.pdf

Programming Fonts: I like Pragmata

There's a good visual comparison of programming fonts over on Coding Horror.

I have to cast my vote for Pragmata, in 11 pt as he shows. Yes, it is expensive for a font, but then I look at a screen full of it for 40+ hours a week. It paid for itself long ago.

Netflix Prize teams sprint to the finish

As I mentioned in my previous post, the Netflix Prize is nearing the one year point tomorrow, with a $50,000 payoff. It is turning into a good geek race.

The second and third place teams, Gravity and Dinosaur Planet have combined to form "When Gravity and Dinosaurs Unite". They now have a first place score of 8.38% improvement.  This edges out BellKor, who also improved their score to 8.38%. 

While the new combined team is listed first, they may not actually win the progress prize.  To prevent any information leakage, the Leaderboard only shows the improvement of a randomly selected half of the test set.  It the other half of the test set that actually counts.  So with scores identical to four decimals, either may be ahead. 

It will interesting to see who pulls it out tomorrow, and if there will be any better entries.

Netflix Prize to pay $50,000 on Tuesday

The Netflix Prize will have been running for one year as of Tuesday, October 2, 2007.  For those who haven't heard of it, it is a contest to make predictions on a large dataset that are 10% better than the current Netflix recommendation system.  If you get to 10% improvement, there is a $1,000,000 prize. Nobody is there yet, but they are also giving a prize for the best progress made on each anniversary.

That means that the leading team will win a $50,000 progress prize on Tuesday.  As I write this BellKor is at 8.26% improvement, but Dinosaur Planet is at 7.99%, and Gravity is at 7.96%.  BellKor is two guys, Robert M. Bell and Yehuda Koren, from AT&T Labs. Dinosaur Planet is three guys just graduated with undergraduate degrees from Princeton, and Gravity is a team of four academics from Budapest University of Technology and Economics, Hungary.  it will be interesting to see if anyone has been waiting in the wings and not submitting until the last minute.

There is a lot of discussion about whether 10% is achievable. The only way to prove it is for someone to win, or for no winner to emerge despite lots of people banging on it for several years.  I personally thing it will eventually be won.  One thing that will make it winnable is that the teams have been fairly open about their approaches.  They held a special track of the KDD Cup this summer, and both BellKor and Gravity were among those who published papers on their approaches. You can read their papers here.  I really applaud the top entrants for their intellectual openness.

new iphone optimized typepad

i'm writing this post on my iPhone, using the new i.typepad.com application.

I am on the commuter rail.

I'll just see if this works before I hunt and peck too much.

It is the first iphone webapp I've tried, and it seems really slick.

Mathematica 6 is finally out!

It appears that Mathematica 6 is finally out.  The information is on

http://www.wolfram.com/products/mathematica/index.html

although it isn't on the main www.wolfram.com page yet. Go read about it ...

Mathematica 6 out March 15, 2007?

In a couple of my previous posts, I've unsuccessfully tried to guess when Mathematica 6 would be released.  I got this email from Wolfram today:

Dear Mathematica User,

We're excited to tell you that you'll soon be able to upgrade to Mathematica 6--our most important release in almost 20 years. And while we know you've been enjoying the powerful capabilities of Mathematica 5.2, we want to make sure you have the opportunity to take full advantage of our forthcoming advances.

Subscribe to Premier Service, from now until March 15, and you'll receive Mathematica 6 at no charge, as well as any future upgrades during the term of your subscription.

You could infer from this that it will be released shortly after March 15.  I can't wait to see what they included.  If you have the current version, and have lapsed maintenance, this isn't a bad deal - the upgrade price will probably be about the same.

DeLorme Earthmate GPS PN-20 is finally out

Delorme is a Maine company that makes really nice maps.  They make the best paper maps for New England, and nice map software as well.  I've been waiting for their first handheld GPS, the Delorme Earthmate GPS PN-20. It is the first GPS that can display raster maps, like they use in map programs.  It works in conjunction with their nice Topo USA, which I already use. Kind of like Google Maps in your pocket.

A good review is at gpsreview.net.

Netflix Prize: best score almost halfway there

The Netflix Prize has generated a lot of buzz in the machine learning world.  They are giving away $1 million for a 10% improvement in prediction accuracy over the Cinematch algorithm they use.  The data set is just too cool.  It has ~100 million movie ratings on 17,770 movies by 480,189 customers.  How can a geek resist playing with that?  The money is nice, but the data set is the real draw. 

As of the last few days, people are making real progress.  On Monday we were all in awe of a submission that was 1.79% better.  As of today, there have been four better submissions. The best is 4.52% better - so we're already almost half way to the million dollar level. Follow along with the current leader here. The contest has a minimum of 3 months to run, so it won't be over soon, it wouldn't surprise me if we have a qualifying entry before then.

Of course, I can't resist working on something like this.  My computer is crunching away on my solution, which will take a few more days. I'm limited most by free evening time.  I can't wait to see how well my first submission will do. 

I'm the "Craig Schmidt" team, or craigschmidt on the message board. I find it kind of strange that most people are using "team names" rather than their own names.  A big part of why you'd do this if for egoboo, so why be anonymous?

Wolfram NDA's their user conference, and the internet misses the whole thing

Wolfram Research had their Wolfram Technology Conference 2006. I expected that they would introduce Mathematica 6 at the conference, but apparently they didn't. I say apparently, because the entire conference caused not a ripple on the Internet. 

Why?  It seems they made all the participants sign blanket Nondisclosure agreements (NDA's), saying they couldn't talk about anything at the conference. The only mention I can find about the conference is one blog post from a guy complaining about the NDA.

From the titles of sessions, they were talking about Mathematica 6. I'm a customer who uses Mathematica. I want to know what happened! This seems a completely silly way to do things. Wolfram must be incredibly out of touch to actively squelch all mention of the conference and products.  Wouldn't want any buzz or excitement about our products.  That could be dangerous.

WTF!

my very educated mother just served us noodles

I'm a little sad to see Pluto demoted as a planet.  The key question is how we update:

my very educated mother just served us nine pickles

The Economist, always on the forefront of important issues, suggests:

my very educated mother just served us noodles

Kottke had a contest for a planet mnemonics, with this excellent winner (using nine planets as a protest):

My! Very educated morons just screwed up numerous planetariums.

Amazon's EC2 is pretty cheap

Amazon announced a limited beta test of a new on line utility computing service.  For $0.10/CPU hour, you can setup and run any number of virtual servers.  That works out at $876 per CPU year.  That's a bit more than you'd pay for a dedicated server, but the cool thing is that you can (at least in theory) have 1000 servers one day when you need them, and none the next. I wonder how many real servers they have at their disposal.

Kevin Werbach has an article about it here.

Tim Bray likes Ruby

I'm intrigued by the programming language Ruby.  I'm on the cusp of breaking down to start using it.  Tim Bray (of Sun) has some interesting posts on his blog, as he starts to learn the language.

While on the subject of Ruby, the Ruby Weekly News website is a good summary of the relevant mail lists, for the interested lurker.

Google's MapReduce algorithm

The New York Times had a good article a while back about Google's hardware and software infrastructure.  It said that one of their big innovations was an algorithm called MapReduce:

One such program, called MapReduce, is based on ideas discussed in computer science literature for decades, according to Urs Hölzle, Google's senior vice president for operations. "What surprised us was how useful it turned out to be in our environment," he said.

MapReduce, he said, "allows Joe Schmo software engineer to process large amounts of data and take advantage of our infrastructure."

Mr. Arnold, the consultant, said these tools created a significant cost advantage. "If you talk to guys who work in massively parallel computing operations, as much as 30 percent of their coding time is spent trying to figure out how to get the thing to run," he said. Google "has figured out how they can reduce a lot of the hassle and work of creating parallel applications."

Mr. Gates acknowledged that MapReduce was a significant technology, but he asserted that Microsoft was building its own parallel processing software, opening another front in the technological war between the two companies.

"They did MapReduce; we have this thing called Dryad that's better," Mr. Gates said. "But they'll do one that's better."

Anything with such a snarky quote from Bill Gates has got to be interesting.  So here's the paper that describes it.  It is an interesting approach to parallel computing, well worth a read.

Polynomial time simplex algorithm for linear programming

Our office is just a block away from MIT. That's nice, because I can go to the library and seminars.  The most interesting seminar I went to at MIT this year was probably one on a polynomial time simplex algorithm for linear programming:

Algorithms and Complexity Spring 2006
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
Speaker: Jonathan A. Kelner

In this talk, I shall present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input. We begin by reducing the input linear program to a special form in which we merely need to certify boundedness. As boundedness does not depend upon the right-hand-side vector, we run the shadow-vertex simplex method with a random right-hand-side vector. Thus, we do not need to bound the diameter of the original polytope. Our analysis rests on a geometric statement of independent interest: given a polytope $A x leq b$ in isotropic position, if one makes a polynomially small perturbation to $b$ then the number of
edges of the projection of the perturbed polytope onto a random 2-dimensional subspace is expected to be polynomial.  This is joint work with Daniel Spielman.

If time permits, I will also discuss recent extensions of this result with Evdokia Nikolova.  Using tools from random matrix theory, we extend the technical tools from the above work to provide a smoothed analysis of an algorithm to solve a wide class of non-convex optimization problems.

There have been polynomial time interior point algorithms for solving LP's, but variants of the simplex algorithm have always had exponential time in the worst case.  (Those damn Klee-Minty Cubes...) It has been an open problem for decades.  Now he just needs to make it strongly polynomial.

It was one of those seminars that you don't really follow, but it sure seems important.  He defended this thesis this week, so contratulations to Jon.  I'm sure he'll get a nice academic post. 

His website, with papers and such is here.

Good language shootout article

As someone who writes in C++ because it is fast, and Mathematica because my brain likes it, I'm always on the lookout for good langauge comparision articles.  I really liked this one, by Steve Yegge of  Amazon.

It comments on C, C++, Lisp, Java, Perl, Ruby, and Python.  I love this quote on C++:

With that said, it is obviously possible to write nice C++ code, by which I mean, code that's mostly C, with some C++ features mixed in tastefully and minimally.  But it almost never happens.  C++ is a vast playground, and makes you feel smart when you know all of it, so you're always tempted to use all of it.  But that's really, really hard to do well, because it's such a crap language to begin with.  In the end, you just make a mess, even if you're good.

How a statistical formula won the war

Keeping with the topic of geekiness from my last post, here an excellent article for the statistics geeks out there.

The Guardian has a story about how statisticians used the serial numbers of captured tank in WWII to accurately estimate the number of tanks being produced by the Germans.