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. 

Scraps from a parallel universe: Alan Turing Obituary

Manchester Grauniad, 27 August 2013

Lord Turing of Bletchley died yesterday, 26 August 2013, Aged 101. 

It is appropriate that the great computer pioneer, Alan Turing, died at an age which looks like it is written in binary.  But it is also fortunate for his family, friends, and the world, that he lived for 96 years longer than that, since 101 in binary is 5.

Lord Turing achieved scientific fame based on his 1936 paper which introduced the concept of a "Turing Machine", leading to the theoretical basis of computer science.  During the war and afterwards he worked on the hardware aspects of computers, so can also be seen as a founder of practical computer science.  Not content with this, he founded Artificial Intelligence with his seminal paper "Computing Machinery and Intelligence."  It was for these contributions that he became, in 1965, the first winner of the Von Neumann award, the highest recognition for a Computer Scientist.

Turing's originality did not finish having founded Computer Science and Artificial Intelligence. He continued with productive and original work, both theoretical and practical, throughout the late 1950s, the 1960s and through most of the 1970s.  Indeed as Emeritus Professor in the 1980s he was a familiar sight cycling to his office to share a new result with his colleagues.  His most important contributions from this phase of his career can be summarised thus:

...

[Unfortunately here a page is missing from the scrap that traversed the parallel universe.]

... 

It was only in his later career that it became widely known that his work on wartime cryptography had been of major importance in helping to win the war for the Allies, and it was this which propelled him from simply being recognised by scientists as first among equals, to being a national hero.

Lord Turing married relatively late in life, having met his future husband in June 1954 at the age of 41.  Their marriage in 1955 was one of the first same-sex marriages in the UK, reflecting the country's recognition of the contribution to the war effort that gay people made.  His husband predeceased him in 1996.

When asked in old age about the secret of his long life, Lord Turing often joked that it was eating an apple every night in bed that kept him alive.    

The Grauniad contacted some of Turing's friends and colleagues for reactions to his passing.

Steve Jobs, Apple: "Whenever I thought of 'there's an app for that' I thought of Turing and his incredible foresight - before computers were invented - that a single machine could act as any other machine."

Sir Douglas Adams, Author: "Everyone knew Turing through his work, but knowing Turing as a friend was something special.  In fact, it was Alan who suggested that 46 would be the funniest number to be the answer to life, the universe, and everything."

John McCarthy, Artificial Intelligence pioneer: "Alan always saw the big picture as well as
the details, and indeed suggested the names 'first' and 'rest' for key operations in my programming language, instead of some arbitrary names I had in mind based on the machine I was working on at the time."

An Astonishingly Wonderful Thing

"I have written to the Governor General asking her to commission Rudd as Prime Minister of Australia." 

From Julia Gillard's resignation speech

I don't know anything about this situation, but ... 

... peaceful replacement of one leader by another is an astonishingly wonderful thing, and one of the great inventions of democracy. Or if not an invention then at least highly polished by democracy. 

Just since 1945 in the UK: Churchill, Attlee, Home, Wilson, Heath, Callaghan, Thatcher, Major, Brown. Whatever you think of these people, they all lost an election (Thatcher's a party one like Gillard) and handed over power to somebody else because that's the way democracy works.

There is PLENTY to complain about in democracies and the way politicians work. But sometimes let's pause and celebrate this fact. Let's not forget that engineering a peaceful takeover by his political opponents won F W De Klerk the Nobel Peace Prize.

Sky TV Nuisance Calls

Sky TV, stop the nuisance calls to my home!

This happened because I had the cheek to try to get out of a relationship with you.   Now you are making nuisance calls,  inquiring into my relationship with my wife, and then accused me of impersonating myself.   Then you refused to note in the account that we did not wish to receive any more phone calls from you.

When I said I was 100% confident that the account holder (my wife) would not wish to discuss this further with you, you refused to take my word for it.

At about that point you asked about my relationship with the account holder.  To be precise you said "Who are you to Ms Underwood?"

Yes, as a private company with a business relationship, you started asking me personal questions about my relationship with my wife.    (Ok you don't know she's my wife, I've now let that slip.  But it's still none of your business.)

When I said that my wife had empowered me to deal with you on this account, which is all you needed to know, you told me that you didn't know that.  I said you did, because you called our home address, which I knew, and I also knew the account password which you had asked for.

At this point you said that you didn't know who it was you were speaking to.

So yep, you asked about my relationship with my wife, then accused me (after passing all your security checks) of not being me.

All this because I told you I did not want to tell you why I want to stop getting Sky TV.

I will write it simply.

STOP MAKING NUISANCE CALLS TO MY HOME.

For others not in an abusive relationship with Sky, let me go back a few steps in the process so you can understand how this happened.

The other day we cancelled Sky TV.  This was an incredibly painful process, marred for example by the fact that the Sky website said we could cancel by email ...

... then when I finally gave in and phoned to cancel, I was told that not only was it impossible to cancel by email, but that I had to pay for the three days I had spent waiting to hear back.

Incidentally, this is still what the web page says as I write this (25 June 2013).  If the agent is right that cancellation by email is impossible, they are (at the very best) misleading customers by stating this.   I say at the very best, because in fact this results in more money being paid by customers to Sky.  One waits a few days to find out it's impossible - having given clear notice in writing that one wishes to cancel - Sky then tells you the method they themselves provided is invalid and you have to pay for those extra days.  If this is legal, there's something wrong with the law.

Anyway in the end we managed to cancel over the phone.  Not being happy campers, we did not see fit to give our reasons.  Well to be honest, we did say that we were not watching Sky at the minute, which is completely true.  But we kept being probed further - on what should have been a simple phone call.  I.e. the call should go:

Us: We wish to cancel.

Sky: Ooh, sorry to hear that, can we interest you in maybe an offer to keep you?

Us: No, thanks very much.

Sky: Oh well, ok, let me just tap these buttons... well thanks very much for your custom. Oh and sorry for the email thing, we'll backdate the cancellation three days.

But no.  Not only was there abject refusal to backdate the cancellation (I was told her manager couldn't do it and her manager's manager would not come to the phone), but my simple wish to cancel the account and get on with my life was not respected with incessant questions about what other service I was going to use etc.  It's not so much that I mind being asked these questions - they are obviously useful market research for Sky.  But I minded very much indeed when my polite refusal to answer them was not respected.  In the end the phone rep did give me two days money back - not three days because she said they would have had to call back the next day.  That doesn't seem reasonable to me but at that point I gave in.

Oh I haven't mentioned the bit where several times the rep told me things that were not true. E.g.  that I had been informed that cancellation by email would require a phone call and I was told it might take 72 hours to hear back from my email.   Neither is true.

Today I was at home and received several calls asking for my wife.  The last time I asked who it was to be told it was Sky TV.  I said I could speak for the account holder so the guy said it was about our cancellation and some extra details they needed.  The extra details were ... the reasons for cancelling Sky TV.  I told him I wasn't going to tell him, so he said he would call back for the account holder...

So I said that she would not want to give reasons either, and he said he would call back, and I asked him not to.   Which obviously is an unreasonable request, as he refused even to enter into their system that we did not wish to be called on this.

STOP MAKING NUISANCE CALLS TO MY HOME.

Obviously, Sky, if you have a genuine reason you need to call us (maybe the bank refusing to stop the direct debit or something), that's fine.   The fact that your system requires a reason for cancellation when we don't wish to give you one is NOT a good enough reason to call us.  Oh, and by the way, remember that we did give you a reason anyway?  In our email to you, and on the phone the first time, when we said we just weren't watching much Sky TV?

I am posting this online because I complained the other day about not hearing anything from my email request.   I was told I would hear back within 24 hours about my complaint.  So far I have heard nothing.  That was five days ago (three working days.)  

Obviously Sky TV ignores complaints using their online system.  So I have written this blog post.

Mansplaining the Mansplainer

This is a fantastic story my wife Judith Underwood told me many years ago, posted here with her permission.

Before I go on, let's just clear up the definition of mansplaining:

"The tendency of some men to mistakenly believe that they automatically know more about any given topic than does a woman and who, consequently, proceed to explain to her- correctly or not- things that she already knows."  Urban Dictionary

I was pointed to the "Mansplained" tumblr today by Mikael.  It's fantastic, though wear fire retardant clothes if you are a woman or have ever liked a woman.

By wife once scored a wonderful triumph by mansplaining to a mansplainer.  Here's the story.

When she did her degree in maths and computer science at Oberlin College in the late 80s, they had a computer lab full of terminals.  (In those days terminals would be "dumb terminals", probably a green on black screen with no fancy graphics, but I just mention that for nostalgia.)

One of the terminals in this particular lab had the habit that once in a while it would freeze up.   It would freeze for maybe 15 minutes.  The only fix was to not touch any keys.  Every time you touched a key, it would be frozen for 15 minutes. You had to walk away and use another terminal, and 15 minutes later it would come back to life. All the CS students knew this, but other occasional visitors would get caught.

One day Judith was in the lab and a man came in and started using this terminal.  It froze up.

The guy started expressing exasperation.  Judith told him he had to leave it for fifteen minutes. The guy started banging keys.  Judith told him he had to leave it for fifteen minutes. The guy started mansplaining to Judith that there were various things he could try.  Judith told him he had to leave it for fifteen minutes. The guy started banging various other keys.

Judith just said to him: "Just leave it for fifteen minutes, and don't worry your pretty little head about it."

She walked away and he looked dumbfounded.  He'd been mansplained.

I love my wife.

As a coda, purely for fun, here is a picture of me and my wife, a few years after this story happened but so long ago that a digital camera was super cool, in black and white only, and in research labs like at Cornell where she did her PhD.  She still has the same great hair, and I don't.

Dr Who, The Master, the Captain of the Starship Enterprise, and Uncle Claudius

Is this the most ridiculous coincidence involving the most famous science fiction TV characters ever?

In 2009's BBC Hamlet, Dr Who played Hamlet, while the Captain of the Starship Enterprise played his Uncle Claudius.

In 2007's Utopia, the same Dr Who faced off against the Master.

In 1980's BBC Hamlet, the same Master played Hamlet, while the same Captain of the Starship Enterprise played his Uncle Claudius. 

In 1976's I Claudius, the same Master played Dr Who's Uncle Claudius.

At least the last one was a different Doctor.

Details:

Links go to IMDB pages for the actors and characters.

2009, David Tennant as Hamlet, Patrick Stewart as Claudius
2007, Derek Jacobi played the Master against David Tennant's The Doctor in "Utopia"
1980, Derek Jacobi as Hamlet, Patrick Stewart as Claudius
1976, Derek Jacobi as Claudius, uncle of Caligula played by John Hurt.
2013, John Hurt played The Doctor in "The Name Of The Doctor"

Cheers and Jeers

There's some good news about Christmas Lectures.  The Royal Institution has updated its policy on the Christmas Lectures trademark.   You can read about it here in full.   But here are some key points for which the Ri deserves praise:

• The Ri has recognised that the name Christmas Lectures for non-Ri events is very important to many science communicators.
• In their words, "The Royal Institution recognises the goodwill and hard work that goes into organising" Christmas Lectures around the country. 
• The Ri has proposed that Christmas Lectures this year form part of a "Christmas Festival of Science."  I think this is an excellent idea - as I mentioned in my original blog post.   Anything which can raise the visibility of Christmas Lectures around the country is good news in my opinion.   
• The Ri has set up a simple form which anyone can use and which is not in my opinion onerous.  
• The Ri has assured me that anyone using this form and who is a bona fide science communicator and not seeking to profit from the Lecture will receive approval from the Ri. 
• The Ri has realised that it approached the trademark issue in the wrong way, sending out heavy handed "nastygrams" (as one tweeter described it.)  
• My friend received an email apology for the upset caused to her, which I know she was very grateful for, and which it was good of them to take a moment to do in the melee of events.  

I am very happy to hear all of the above. I think it is good news and I am happy to recommend that anyone running a Christmas Lecture take part with the Ri's plans for a Christmas Festival.

But it's not all good news.  The Ri was quite right to move quickly to make these changes and I absolutely did not want to stand in their way.   But I still have major criticisms of their position.  

Here's the thing.

The Royal Institution still claims that they own the name "Christmas Lectures" as a trademark, and that it cannot be used without their permission.  And that this applies even to a not-for-profit Christmas Lecture given by any science communicator.  So they are still in the position that if you (for any reason) don't want to register your lecture, they claim you are infringing their trademark. The - absurd - endpoint of this is that they will have to sue you.

I absolutely am not a lawyer but I simply do not believe that the Ri trademark on a public and non-televised Christmas Lecture could possibly hold up if challenged.   The words are generic, have been used by many many lecturers for decades, and no conscientious consumer could think that a Christmas Lecture at their local University had anything to do with the Ri.   While the Ri persuaded the trademark office that they were entitled to the trademark, that is not an adversarial system with another side pointing out the ridiculous nature of their claims: if they sue anybody they will - I very much hope - be laughed out of court for some of these claims.

And even if I'm wrong about this - there's a very good chance I am - it is the only the Ri that cares.  Obviously even if they are right legally, the hurt and insult and "land grab" (another tweeter's phrase) on the name Christmas Lectures was a totally unnecessary own goal.

It's so easy Ri, use the get out of jail free card I gave you yesterday.  Withdraw the parts of the trademark claim relating to a public lecture.   Please please please do that.

You have nothing to lose by doing so and a lot of goodwill to lose if you don't.