How I became one of the three "best optimizers in the world"

Eternal Glory

One of the three best optimizers in the world?  

A direct quote. And I'm one of three because our winning team - Mano - comprised me, Allen van Gelder and Ian Miguel won the First International Lightning Model and Solve competition. The competition web page said (boldface theirs).

The main aim of the competition is to have fun, and earn the eternal glory of the title of "best optimizers in the world".

It is, of course, not true. The key quote is the part not in bold: it was having fun.  It was a great piece of fun and winning really made my conference (it was at CP2013).  And it was really fun that the three of us, just using paper and pen beat nine other teams who had the best optimizing software in the world at their fingertips.  

Let me tell you how it happened and what we can learn from the experience.

Before I do that let me thank very much the organisers, Peter Stuckey, Farshid Hassani Bijarbooneh, and Håkan Kjellerstrand.  

Two Days Earlier

Allen van Gelder wandered up to me and asked me whether I'd like to join his team for the modelling competition.  The conversation was simple.  I said no, I was going to skip it.  He said "We're going to solve the problems by hand" and I said "Yes" and he said "I thought you would." So I became the second member of team Mano: Spanish for hand.  

Solving hard combinatorial problems by hand is something I enjoy a lot and something I have a bit of a reputation for.  In two cases I've solved open benchmark problems which had not been solved by any mechanical technique.   I might use a computer to do bits of bookkeeping, but not the hard yards of the search problem.  

Word Gets Around

One of the really fun aspects of the conference was that people kept coming up to me and saying "I hear you're going to enter the modelling competition by hand."  Those who really know me well asked me if I was going to take any whisky in: they know that I enjoy doing this kind of thing with a glass of whisky by my side.

The teams were of size three.  So I suggested that Ian Miguel join us.  He was harder to persuade than I had been, because he owed somebody a paper review, but eventually he joined in to complete the team Mano. 

Just before the competition, Bilal Hussain asked me what he thought our chances of winning were.  I said "Zero percent".  This was honest but maybe a little exaggerated, since I knew it wasn't zero.  But I thought it was very low.  Remember the bit where everybody else could use the best modelling and solving tools in the world? 

The Competition

I'm delighted that the organisers have put the contest materials online so you can follow along.

Ten teams gathered for the competition briefing.  We were given a copy of the rules.  The key point was the scoring system, which meant that getting valid answers in early was good.  This was useful for those of us playing by hand because we could scribble down something quickly while other teams would be coding.   Unfortunately we had to enter our answers by file on a usb stick, which would slow us down from our pencil and paper.  

A key point of the competition is that only one laptop was allowed per team of three.  This made the critical bottleneck the keyboard.  A modern laptop can do serious solving and also editing files at the same time, but two people can't type on the same keyboard at the same time (despite this ludicrous scene from NCIS.) 

The other key point was the scoring system: you got a point for each team you beat if you submitted a valid solution, even if a terrible one.  You beat a team if you got a better solution or you got the same quality of solution in earlier.

At start time we were allowed to turn over and read the problem descriptions.   We had already been given the USB stick with the instance data on it.  There were 6 classes with five instances in each class.  

The first problem was dealing with the 10 pages of detailed description.  We did rip up the sheets but the page breaks were not at the start of a problem, making it harder.  There was a lot to take in.  In fact I think at no point did any of the three of us seriously read the powerup or smelt problem classes, and we only scanned quickly the doubleclock family.   

The first problem we started working on quasi seriously was the queens problem, and this became Ian Miguel's problem - though this was not immediate.  We first realised we had an answer to instance 0 as we could copy it out from the question sheet.  However we then had the disappointment that there was no points for the instances 0, they were there as test data if we wanted them.  Then I told Ian the next instance was for board size 6, which he quickly solved.  The next disappointment was the realisation that this was wrong, the next instance was 7.   Without taking too long he solved that and then we typed it in the required format and took it to the front. 

This was nice because when we had our first correct solution confirmed we got a chocolate each!  Nice in itself but since nobody else had got one yet we knew we were the first to get a solution in, and so at that point technically in the lead.

A really good aspect of the competition was that you could get your solutions checked instantly. This meant that you either knew you were ok or you could work on fixing it. Spectacularly good was that you got an explanation of the mistake in automated fashion, so double kudos to Peter Stuckey for doing that.  This really helped us in one case.

Ian then continued working on queens problems, and eventually we submitted solutions for three instances (sizes 7, 11, and 16).  By 16 the fact that we did not have any graph paper was a real disadvantage!  But we got there: though non optimally as it turns out in each case. 

Allen decided to work on the seatplan problems, which he did using pen, paper, and the scissors he had brought.  With this he cut up bits of paper which he used for the individuals in the problem.  He did get a solution to the first instance, but unfortunately we'd made a transcription error in copying it from screen to paper - a problem of the hand approach though one might make a reading bug in a program.   He resolved this one with the right data and got a solution in time, but that was the only seatplan problem we solved.

After a while buzzing around I settled in to read the zamkeller description which was not very clear.  Since I have done work on permutations before and this involved permutations, this seemed natural.  Eventually I got it in my head (despite the mistakes in the original description, now corrected online).  When I did it became relatively simple, so I was able to cobble together something for the smallest two instances fairly fast, and (thanks to the instant checking) be sure they were correct (though not necessarily optimal.)  Since the instances got bigger I did write a little lisp program (shock horror, yes there was some computer assistance!) to write out the numbers in the sequences I wanted.   As I worked on this a general solution dawned on me which I was sure is optimal.  So I programmed this in, did a bit of editing of the output and got the third submitted, and when that was correct I quickly did the others and got the last instances submitted.   While I did use a computer here a bit, it was never used for any solving, and if I had been allowed I could have submitted entries on paper for the big instances (up to 3000 numbers) with a formula written out.

By the time each of us had done our last problem we were very nearly out of time.   

What Happened Next

We had been told we would get the results immediately the competition closed, but they changed their minds and said they would announce the results at the conference banquet.    

This was when I got my first inkling we might be doing well, because Peter mentioned that four of the ten groups had not submitted any correct instances.  This was a big surprise and since by then we knew we had submitted nine correct instances, we thought we could be doing well.  

After the banquet Peter stood up to announce the scores in reverse order, and since he went through every team that had scored, our excitement grew (I was sitting next to Ian Miguel but not Allen).   When the second place was announced we of course knew we had won, and a few moments later went up to collect an inscribed medal and a nice certificate.  So again many thanks for those mementos.

I certainly wore that medal all night, but much to my friends surprise I have not worn it since :)

Here's the blog post (thanks Håkan!) reporting that we won.

Why did we win?

A few people have - I hope jokingly - commented that this is a sad reflection on constraint programming, with its 20th annual conference next year, that a bunch of guys with pen and paper can beat the state of the art.  But (if they were not joking) I don't agree.  People can solve hard problems and the lightning nature of the competition meant it was like a race between a bike and a car: the bike can accelerate quicker but after a while the car will overtake.  Also, once the problems are modelled an unending sequence of instances can be solved.  

So having defended Constraint Programming as an art, let me tell you why Mano won. 

We understood very early on that quick and dirty answers were advantageous.  So we got our 7x7 queens solution in as soon as we could.  Indeed, since we were at the back, we ended up running up and down the stairs a lot.   It was worth the short break from work to get the feedback and our entry logged in case another team got the same quality solution to an instance later.

Another point was that we didn't spend too long looking for true optimal solutions, so for example none of our queens solutions were optimal (we found out in retrospect) but an optimal solution for 11x11 would have got us fewer points than Ian's non-optimal solution for 16x16.

One really powerful advantage we had over other teams was that we could parallel search three ways.  For much of the time we had people working on three problems independently.  This was a big thing as it meant we got entries into three different problem classes.   I don't know how other teams worked but this would have been more difficult, and especially with resulting contention for the key bottleneck - the keyboard.   For us there were only brief periods of typing and Allen had brought plenty of paper. 

On their own I think these advantages would have got us into the top three competitors.  We got the gold medal because I worked out the general solution to the zamkeller instances and therefore could submit solutions even to the huge instances.

There are things we could have done better.  Mainly I think none of us really read all the problem descriptions.  So for example I only glanced at the powerup instances, and only later realised they were quite amenable to hand solution.   If Allen had brought a pack of cards I think we could have done very well on the doubleclock instances!   Analogue tools can be useful.  But since we ran out of time, it's not obvious if we could have exploited these advantages. 

We were very beatable: the way to have done this would have been twofold.  First set somebody on something like the queens problems where hand solutions can be obtained, reducing contention. And second, look for cases where easy programs could be written to generate feasible if bad solutions for all the instances in a class. As Peter Stuckey pointed out at the banquet, the identity permutation has pessimal score zero in zamkeller, but would have got many points since other teams didn't attempt it.   This way constraint modelling is reserved for the cases it will really pay off, since time is so limited.  

What have we learnt for next year? 

I enjoyed this and I hope it happens again.  I've given away some tips if you are entering next year.  What about the organisers?  Peter told me he thought the problems were too hard. Actually I disagree, but probably it is true that they took to long to read and understand.  Ten pages of fairly dense material was a lot, and as I've said even the winning group's examination technique was bad, as we did not read all the problems in detail.  

What Have We Learnt For Constraint Programming?

One word. Modelling.

To expand, Modelling is hard.

To expand, we need better tools to make it easier to model constraint problems quickly.   

Every group should have been able to use a simple constraints tool to model the easier problems (like queens) and then get on with the other ones. 

This is what I take away, and it's nice that this is research that we in St Andrews are already doing, so I hope we can push this harder after this experience.