I remember when networks used the mail

INFORMS asked us to blog about O.R. and Social Networks.

Once upon a time, O.R. people networked using the mail. In those days, academics would often have a network of people interested in the same branch of O.R., and would circulate drafts of papers by post for comment and criticism. And we networked at conferences, study groups and lectures.

When the OR Society (UK) held its conference in Exeter in 1991, they asked me to chair the event. I invited various speakers from outside the O.R. community to speak at the event. Two were academics. from geography and medicine. Independently they commented that the atmosphere of an O.R. conference was different from the experiences of their disciplines in conferences. They both said that it was much more friendly, and they sensed that O.R. people were less competitive. The networking was both social and sociable.

And then came USENET and the sci.op-research discussion group, which I followed and contributed to over the next ten years. It made for an international gathering, though there were the regular contributors who had a word to say about everything. There were those who thought that they could get help with student homework free of charge, and every so often we had contributions who thought that "op" meant "optical". On balance, I think that the overall cost-benefit of using the discussion group was limited. I could have done more usefully with my time than follow it. But there were days when it was valuable.

And now there are discussions of a kind on LinkedIn and Facebook relating to O.R.; very few people are contributing ... even to the group that hates linear programming.

As an example of a concept used in O.R., both of these recognise that their users form a graph, with each friendship represented by an edge between the nodes of people. So there are suggestions of people that you may know who are two edges away from you. I laugh at some of these. I am "friends" with my wife's sister and her children. But I don't know their circle of friends in the place where they live, even though Facebook tells me that we have many mutual friends. Facebook has an app which plots a friend graph, which in my case is reasonably small. It has several cliques. But I would know that without the app.

So, for O.R., following the new social networks are probably not cost-effective. All in all, I hope that O.R. people will continue to network at conferences, study groups and lectures, and that they will always be both social and sociable events.

The Science of Better Owl Deliveries

Dear Muggle Friend
As you know, J K Rowling was a student at the University of Exeter in Devon, in the south-west of England. Many people have commented on the way that the author has used links from Devon in her books. Perhaps the best known is "Ottery St Catchpole", which is a very poorly concealed reference to Ottery St Mary; there are also references to Topsham, Ilfracombe and Chudleigh (spelt Chudley by JKR). However, there are further links. The name "Catchpole" is a reference to the former professor of theology at the university; JKR studied in the same building as the department of theology. The name Muggle may be connected to a missionary couple from an Exeter church whose surname is Muggleton. The word "goyle", commonly assumed to refer to gargoyles, is also a Devon dialect term meaning a valley.

But this is all about Operational Research (or Operations Research as Americans call it). Whichever name you use, it is abbreviated "OR". In both the USA and UK, OR is referred to as the "Science of Better". When JKR was at the University of Exeter, there was a successful undergraduate course in "Mathematical Statistics and Operational Research" which was usually known as "MSOR". It may be argued that the author was aware of the abbreviation "OR" and it came to appear in numerous names in the books. DumbledORe is an obvious example, along with the DiggORy family, and on the opposing "side" are the DementORs and lORd VoldemORt. There is the "ORder of the Phoenix" as well. I hope that you are convinced that OR runs through the series of Harry Potter books(?)

One application of OR in the book series is clearly used at Hogwarts. This is the owl post. Postal and delivery services around the world use OR to ensure efficient delivery of letters and packages. The pattern of deliveries used by the Owl post office in Hogsmeade shows many similarities to that used in the muggle world. However, there are a few differences. First, in Hogwarts, the owls have been studied and colour coded to divide them into short and long deliveries. This corresponds to a separation which is seldom used in postal services these days, that of marking letters "local" so that they did not need to be sent to a sorting office. Most postal services have used OR to determine that it is better to sort all post in one place, and hence have adopted the use of zip codes or postal codes. Second, provision is made in the Owl post office for rest and recuperation for owls. In the books, the time for this depends on the length of the owl's flight. In modern postal services, cars/planes/vans/trains carry long distance mail and do not need to rest. The concept of one messenger carrying a package all the way from sender to recipient (as owls do) is seen to be inefficient and has been rejected by postal organisations (with the possible exception of those engaged in espionage).

However, in one regard, postal services can learn from the owl post office. In some episodes from the books and films, deliveries are synchronised for many students at Hogwarts. Although many delivery companies offer "timed deliveries", these are normally timed to within a particular time window ("before 9am", "between noon and 4pm" and so on). I have applied for research funding to explore how to learn from the owls and improve the punctuality and precision of mail services.

I hope that you have learnt a little from this letter, which is my contribution to the June 2011 INFORMS challenge. You may even believe some of it.

Learning from mistakes

One of the stories of the early days of operational research during the second world war relates to the study of where warplanes were damaged when they returned to the U.K.. Each plane which landed was examined, and the places where there were holes in the wings and fuselage were plotted on a schematic. Once sufficient data had been collected, it was clear that the holes were clustered in certain sections of the warplanes. The story goes that someone in the O.R. team pointed out that the important lessons were not about the location of the holes, but about which parts of the schematic had no holes. These were the places where no planes had survived to return, and therefore indicated the vulnerable parts of the planes. These were those which needed extra protection.

I was reminded of this when I read an article in the newspaper about the American surgeon Atul Gawande. He is obsessed with failure in the medical services, and especially surgery. Most operations in hospitals go successfully, but the interest should be concentrated on those operations which go wrong. He asks the question: "Why?". Atul is especially concerned about surgery in the developing world, with the aim of saving lives. So he has written about failure, how it happens, how we learn from it, how we can do better. And he is working with the World Health Organisation to develop tools to help surgeons.

The simplest tool he has popularised is a checklist, that should be followed before every operation "Is this the right patient? Is this the right limb?". It takes two minutes, but saves lives and complications. However one item in the list is expensive; an oxygen monitor. So, Atul has identified this as the obstacle to implementing the checklist, and has persuaded a company to make them cheaply and there is a charity Lifebox which helps provide them.

So how can we learn from this in O.R.? Gene Woolsey has written about lessons that he learnt from some mistakes, but generally we crow about our successes and say little about our failures. Maybe practitioners ought to examine their failures more closely? I remember a couple of my projects which came to nothing because ai took the textbook attitude that the initial description indicated there was very little relevant data, and I said so. The clients reached the conclusion that the project was doomed from the outset. Maybe academics can also learn from mistakes. I advised my research students to document their "Dead ends" in the research programme.

Optimal search

A contribution to the February 2011 INFORMS blog theme, "OR and Love"

Way back in 1997, there was a news story about a psychologist who had published work about optimal strategies for finding a marriage partner. Seeing the report, I wrote a tongue-in-cheek letter to the national newspaper (The Independent) which pointed out that the mathematics behind this was familiar. I also wrote that it had created opportunities for light-hearted examination questions. The newspaper published my letter ... and a few days later I received an email from a mathematician at the University of Cambridge who wanted me to expand on the letter. It is a small world; that mathematician had tutored me as an undergraduate, but hadn't made the association of the signatory of the letter with one of his ex-students. He wanted to use my piece as part of a series of interesting mathematics for schoolchildren.

So I wrote a piece, still light-hearted, and it appears as "Marriage, mathematics and finding somewhere to eat" concerned with optimal stopping (the secretary problem). Cambridge provided the illustrations and a simple interactive game of "Googol".

Since then, that piece has been widely read, and I have had feedback from all over the world. (How I wish that my more serious written work was so widely read!) One friend told me that the item had been posted on her staff-room notice board, and she had acquired considerable kudos when she revealed that the author was a friend of hers.

I followed the article up with correspondence with the psychologist, which never led to a publication, but we learnt a lot from each other. Over the next year, I collected a stack of publications about this problem of optimal search, including several concerned with the mating habits of birds and animals, and the search habits of birds looking for nest sites.

Falling in love is not something to be modelled by O.R. techniques, but finding a partner can be simply modelled as a secretary problem. "A succession of potential candidates present themselves, and you can accept them or reject them. If rejected, you cannot go back and change your mind. What is your strategy to find 'the best'?" There are various variations on the problem.

But there were two bizarre twists to the story, as I heard from adults who had read this article for schoolchildren.

First came an email from an American lady. She asked, I assume seriously, if I could advise her whether her current partner was the right one for her. She asked for a mathematical formula which she could apply to him, to see if he was the best.

Second, another lady wrote (I forget where she came from) asking for my advice about increasing the pool of potential partners. Again, I think it was serious, but again I had to reply that there was no mathematics or other O.R. techniques which could be used in such circumstances.

One thing that the secretary problem does not address is how to approach the problem when both partners are using the search strategy! But dating agencies which encourage sequential search start with an assignment problem ... another O.R. and love technique.

The school which was too small

The current INFORMS blogging challenge/theme is about "O.R. and politics". It reminded me of a student project a great many years ago. It was never suitable for a research paper write-up, but a blog is an appropriate place to recount what happened.

The city had expanded, and a large housing estate had been built. Part of the development was a new primary school. However, before the estate was complete, the school became overcrowded. It was too small. Not much could be done to provide more space. The local politicians were embarrassed and the local media were not slow to blame them. The student (B) and I were asked to help the council officers make better decisions in the future.

So we interviewed people, read literature, and did our best to become familiar with aspects of planning. We quickly realised that the whole mess was multi-criteria, and many criteria were non-numerical. One of the attributes of O.R. should be the ability to cut through messes. For simplicity, here, we reduced the problem to a two way table. One dimension was the forecast demand, reduced to “Low”, “Medium”, “High” and the size of school “None”, “Small”, “Medium”, “Large”. In each of the twelve cells we wrote down aspects of the consequence of the two dimensions, and then iterated through meetings in which stake-holders could contribute their ideas. So the table of twelve cells became a tool for thinking with for planners and decision-makers. It could be – and was – used in other new developments in the city and region. Nothing high-tech, but we had helped to make the mess less messy. B went on to a career in O.R. and other messy problems.

Among the gems that we learnt along the way were the following:
(1) It takes about five years from initial ideas to opening a school, so the children who will use the school are being born at about the time of those initial ideas;
(2) Families with pre-school children are much more mobile than others, so it is not possible to forecast demand by local surveys of families;
(3) The forecasts made in the past had gone awry because of world-wide economic upheaval;

Politics in a developing country

Location-allocation problems appear in many settings, and O.R. scientists have been involved in numerous cases. My research student (S) was concerned for the location of primary health-care facilities in his home country. He came equipped with the data about the villages and towns in one province. Populations, location of existing facilities, which villages had suitable infrastructure, distances between the population centres, and the government's policy for expanding health services in their five-year plan. So he set out to study where facilities should be located if one had a blank sheet to start with, given the five-year plan. Then he added constraints, because it would not be politically expedient to close facilities, so these had to remain even if they were not in the optimal solution. He was anxious to develop a system that could be replicated on a PC in his country, and this was part of S's work.

One constraint which had to be imposed was that each sector of the province should have the same number of facilities, and that the expansion plan should ensure that no sector had more than one more than any other. This was to keep local leaders and government staff happy. So the expansion gave each sector two facilities, then expanded these to three. Given the existing facilities, and the uneven distribution of population in the sectors of the province, these constraints meant that the location of facilities would not be as good as it could be.

So S completed his research, and presented it in his thesis and in seminars. At one of these, an astute member of the audience asked how S could be confident that the province would implement the solution. Developing country politics is not always what westerners are used to, and an O.R. solution might not be accepted by politiicians. "Well," said S, "my father works in the provincial governor's office. The governor will take his advice." He had never disclosed this in his research.

This is my first contribution to INFORMS Blog challenge/theme for January 2011 "O.R. and Politics"

OR and the holidays (2)

This blog post contributes to the INFORMS monthly blogging theme. Look for the INFORMS blog to summarize the blogs at the end of the month.

A Christmas tradition in the U.K. is the office Christmas party, when everyone in the company gets together for some kind of celebration. This year, the economic situation has meant that some companies have cut back on the expense of these events. However, my wife Tina's company held one on Friday evening, and the director invited spouses and partners to attend. More importantly, as an O.R. problem, he arranges taxis for everyone to and from the event. To save money, each one is shared by several people, collected on the way from the most distant employee.

So here is the O.R. problem. How many taxis should be ordered, and which routes should they take? It should be recognisable as a "Vehicle routing problem" for which there are numerous soilution approaches. The constraints and interesting features include:
1) some calls have one pick-up, others two; a route which is feasible for one size of taxi may not be feasible for a smaller one;
2) the supply of large taxis in Exeter is limited;
3) there is heavy demand from other users on a Friday evening, so a supplier may not have enough vehicles; should you order taxis from several taxi companies;

It was a good party, though I ate too much. And the Christmas ale ("Raisins to be Cheerful" from St Austell Brewery) was very good.

OR and the holidays

This blog post contributes to the INFORMS monthly blogging theme. Look for the INFORMS blog to summarize the blogs at the end of the month.

I have two younger brothers, and we all have families. Choosing where to meet, when to meet and what to do for a Christmas family get-together is a multi-criteria decision problem, and our conclusions demonstrate that solutions to a repeated problem change with time as circumstances alter.

One brother (Michael) lives near Leicester, one (Andrew) near Gatwick, and we live in Exeter. For simplicity, these may be regarded as the vertices of a triangle, sides 4 hours, 5 hours and 3 to 4 hours (depending on the traffic around London).

In the old days it was easy. We all met at my parents' home, which was reasonably central. All that was needed was to schedule who travelled when, and help mum with the catering, cleaning and beds. It wasn't too hard to plan what to do.

Even when mum died, we continued to gather at the same place, but we needed to plan a great deal more for the catering.

Then dad came and lived with us, and people came here; with a smaller house than the parents' home, we needed to arrange that Andrew and Michael would overlap for lunch on the day that one arrived and the other departed.

But when dad died, we all felt that there were better times of the year to visit one another. Tourist attractions are generally closed in December, and that limits the scope for days out. So the problem became more interesting. Meanwhile, the next generation was growing up, which brought other people's criteria into the decision process.

We reached a conclusion that we did not need to meet in December, and for several years got together for a Saturday in January, when it was cheaper to travel by public transport, and there were places we could visit together or things we could do together. So that gave a feasible solution, which ticked several boxes for all of us: ease of travel (we each made a train journey with at most one change of trains), a warm place to meet with space for presents to be exchanged, an activity which was pleasant. There was one surprising downside; the presents that we gave had to be compact and portable as we would be carrying them all day.

Then there was a birth and activities which involved theatre or shows in London became infeasible. One year we strolled in London with a toddler, and fortunately the weather wsa good. We all saw parts of the capital which were new, so it was a memorable meeting.

Another birth meant a baby and toddler to be entertained, along with two twenty-somethings who might or might not be around in January, but were more likely to be available in the week between Christmas Day and the New Year. So the weight attached to different criteria changed. We fed our locations into a website (rendeznew) which told us that the meeting point in the centre of the three homes was near Swindon. So we searched for a suitable place to meet and eat there, hopefully with space for the restless children.

And that is the solution at present. Soon after Christmas, three cars (loaded with people and presents) will congregate on a gastropub near Swindon. Each of us will have a two to three hour drive each way, and we have told the staff that it is a family gathering. We are trying out a third pub, for variety.

Could all this be automated? As I have explained, there have been changes in our needs and hence on the emphasis on different criteria. The web site wasn't really needed, as we could see from a map that Swindon was reasonably central, and we had the knowledge of the UK road system to guide us. Once we had found the right locale, we could have searched for places to eat, by specifying criteria (must have car park, serve vegetarian food, be child friendly) but these would be binary constraints (yes/no) and we might want to treat them as slightly soft constraints.

Sometime, I may return to the algorithm used in rendeznew, which has interetsing O.R. aspects.

An astute reader may spot that there is one constraint which we have implicitly included. Nobody wants to stay in a hotel for the family get together.