Monday 5 September 2011

Moving on

This is my last post with this blog. Now that Preston White is established as editor-in-chief of IAOR, it seems best to stop blogging as "IAOReditor".

So I am launching ORinDevon.blogspot.com as my new blog site.

Friday 29 July 2011

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.

Wednesday 13 July 2011

The importance of experience

Three lessons were drummed into us as students of O.R., and I have tried to pass them on to my students.

(1) do not analyse numerical data by machine before you have looked at that data by hand; the analyst needs to have a "feel" for the numbers.
(2) do not assume that the decision-maker who is identified for you by the management is actually the decision-maker; somebody on the spot may actually take decisions which the management do not know about.
(3) observe as much of the system as possible, first hand. Walk the line!

On our trip last week to South Wales, the importance of number (3) became clear. But I doubt if the organisation actually has an O.R. team, but they needed O.R. advice.

We went out to an inn for our evening meal. Like most inns serving food, there was one queue for ordering food, and another for drinks. Food orders were passed to the kitchens and waiting staff, and drinks, of course, were served at once. However, on Wednesday evenings, it was Curry Night. If you ordered a curry at the food counter, then you could have a drink included in the price. This meant that the young lady at the food counter had to leave her place and collect the drink that you had ordered from her. Hence she had to do an increased workload on an evening when there was increased demand at the food queue. Customers for food had long queues, while there were no queues for drinks. Service time could be speeded up in various ways ... passing a token to the drinks bar ... having an extra person to serve at the food queue, all or some of the time. It could also be reduced by having a printed list of what "free drinks" were available, rather than for the staff to have to recite them. All of this could have been noticed if someone with authority had actually observed the queue process, rather than assume that the normal system could cope on the Curry Night.


Result: two very nice curries, reasonable drinks, but lost profits because we didn't go back to the long queue for a sweet.

Monday 11 July 2011

Mini supermarkets

A news item at the weekend told that one of the big four UK supermarkets has opened a small city centre store for the first time. Morrisons were joining others (Tesco & Sainsbury and Co-operative) who have both large out-of-town stores and basic outlets in city centres.

The story claimed that the decision had been taken because of the recession, affecting the number of people who shop out-of-town. But the other stores know that there are different clienteles for different types of shop, so there is almost certainly an underlying decision to try and reach the clientele who shop regularly in their city centres. Maybe the recession drew the management's attention to the need to do this?

I don't know how many O.R. scientists work at Morrisons. But I hope that any who are there have read about a study that one of the others commissioned, which led to a change in the way that it handled distribution to its city-centre shops. The study showed that the principles of distribution were significantly different to such stores, compared with the model that was used for out-of-town stores. The O.R. person involved spent three months travelling in the cabs to observe what actually happened, which was not what the staff in head office thought happened. And as numerous O.R. studies have shown, it is always important for the O.R. staff to get involved on the front line, or sharp end.

What's in that truck?

Last week Tina and I drove from Exeter to South Wales for a two day break (it rained a lot!). On the motorway (M5) we started to pass the time by looking at the articulated lorries coming on the other carriageway. The first "game" was to look out for those labelled with the major British supermarkets. We decided that the rules were to see how long it took before we had a hand of five: Asda, Morrison, Sainsbury and Tesco, plus one wild card from Waitrose, Co-operative, Somerfield etc. We weren't sure whether or not to count M&S, as their lorries might be carrying clothes ... but decided that the big supermarkets also deal in clothes and much else. (Yes, British readers will know that Somerfield doesn't exist as an entity these days, but the Co-operative which has taken it over has not completed the conversion of its fleet. We even spotted a truck whose trailer read Somerfield, pulled by a tractor labelled Co-operative.)

In the first hour, we completed three hands of five, an indication of how much traffic there is into the south-west of England. But we were also interested in the other labelled food trucks. Once, when I was consulting for a major confectionery company, I remarked that you never saw lorries with their name on the side. I was told that when the company started in the UK, they linked to a local haulage company in the same town, and that haulage company continued to carry all the confectionery; the two companies had grown together. So there are many household names which never appear on the sides of articulated lorries in the UK.

But there were two companies we commented on, one selling yoghurts and dairy products, the other selling pasties and pies. How many yoghurts fit into a 40-ton trailer? Allowing for packaging and pallets, we suggested about 30,000 (assuming about 1kg each). And about the same time for the pies, possibly a few more. How many of these products would be sold in one day in a major supermarket? We estimated at least 10 and at most 1000, for both "large" and packages of four. So by the rules of guesstimation, we plumped for 100 per day (geometric mean). With two products, that meant each lorry carried enough for about 150 supermarkets. And with thousands of supermarkets across the country, one could see why it was economical for these companies to haul such large quantities of their products from factory to distribution centre in large trucks.

Next time we use the motorway, we'll be looking out for other named products on the move, and wondering whether the owners have made the decision to run their own fleets for commercial reasons or because it has "just happened".

Saturday 2 July 2011

Networks and social networks

I was teaching a course on graphs and networks a few years ago, soon after Facebook became popular, and I mentioned that the graph of connections between the students in the room, defined by their Facebook "friends" would be an interesting one. Within 24 hours, several students had asked to be friends; I said that I felt it would compromise me to be linked to some but not all the class. However, we were able to discuss aspects of graph properties that related to Facebook.

I have a love of practical uses of graphs and networks, so was delighted to find a new one. It is the "Map of the World Drawn Entirely Using Facebook Connections" (found here among other places). Based on a large number of connections in Facebook, lines are drawn between them, and the colour of the line relates to the number of connections. Many people have links within their home city, still more are linked within their home country, and then there are international ones.

There are several fascinating aspects to the map. National coasts are very learly defined. Look at Florida, for instance. There are numerous links within the state, and these so outnumber the links to neighbouring states, that the coast of southern USA is clear. The same is true of the west of Britain. There are not many links between Wales and the west of England, so that the Bristol Channel is clearly marked. It is hard to see the boundaries between most countries, though Spain is clearly separated from France and Portugal, and (hardly surprisingly) the boundaries of Israel are well marked.

The author comments on the emptiness of China, Brazil and Russia. There are empty spaces in the world's deserts as well -- in Australia, the Sahara, and Central Asia.

The more I look at the map, the more I find of interest. A wonderful illustration of the power of mathematics and Operational Research.

Friday 24 June 2011

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.

Tuesday 7 June 2011

Critical mass for academic research

The current issue of the magazine "Mathematics Today" (vol 47, no 3, dated June 2011) includes an article Critical Masses of Research Groups in the Mathematical Sciences
in which the authors (Ralph Kenna and Bertrand Berche) have analysed the research ratings of academic groups in the United Kingdom, as recorded in the Research Assessment Exercise of 2008 (RAE2008). It is based on more extensive work that they have published (Critical mass and the dependency of research quality on group size).

In summary, the authors plotted the outcome of RAE2008 (measured as a quality between 0 and 100) against the size of the research group that reported to RAE2008. This yielded scatter diagrams, which can be interpreted as being piecewise linear, with no, one or two "knees" or breakpoints where the slope changes. Small groups get small scores, and the score increases rapidly as the group size increases. At a critical size, the slope is reduced, and the score increases more slowly. A second "knee" means that the slope is reduced still further, almost to flatness.

The interpretation of the "knees" is that they represent critical sizes for research groups. The lower one is the smallest viable size; less than this, and the quality of the research falls sharply. The upper one represents an upper limit, beyond which adding extra researchers will not add to the quality of the output.

Having said that, the authors report that in pure mathematics, the lower critical mass is at most 2, and the upper one is at most 4. For applied maths, the figures are 6 and 13.

But for statistics and O.R., the critical sizes are 9 and 18. In other words, to produce good academic output, O.R. scientists and statisticians need to be in a large group. Our work makes us gregarious; we work well with other people around us. Since I read the article, I have wondered why this should be, and concluded that it is in the nature of academics in these disciplines that they work together well, they have complementary skills, and those skills are heterogeneous, and they like to collaborate in teams. It chimed with my experience and observations. At various times I have been in groups of between 9 and 18, where we worked well together, and the interplay of ideas flowed. I have also been in a smaller group, and then there was much less academic stimulation. One might think that this would also be true of applied mathematicians, but I suspect that they are more homogeneous in academic expertise than those in stats/O.R.. And the pure mathematics area is much more dependent on individuals with their ideas and theories than those who work with mathematical models and statistical data. (Pure mathematicians -- I love you a lot! -- but you will probably admit to flying solo much of the time.)

Many years ago, I found a spoof paper which was written by M.V.Wilkes under the pseudonym H.W.O.Petard on the optimum size of an establishment. It argues that time gets wasted by people reporting to one another ....

Wednesday 11 May 2011

Lateral thinking

The term "lateral thinking" was coined by Edward de Bono in 1967, and it has become widely used since then. I found myself admiring how some people had been thinking laterally when I was following a country footpath the other day.

Stiles and footbridges on such footpaths work better if they provide some kind of grip for shoes and boots. In some places, this is done by wrapping the wooden planks in chicken wire to make for a ridged surface. However, I noticed that several stiles and bridges now use decking planks instead. These are grooved to provide grip. The popularity of decking means that such planks are readily available, whereas there would be insufficient demand for such planks if the only consumers were people making stiles and footbridges.

Similarly in O.R.; there are solutions which would not be affordable unless some other group of users were also going to use a similar solution and the expense could be shared ... or even completely paid by the others. The moral is to think laterally when a solution has to be implemented.

Wednesday 27 April 2011

Back to the blood donor session

I have written about the sequence of queues in a blood donor session earlier. Yesterday my appointment was later in the session and the system had reached a steady state; so I could observe where the bottlenecks were in the system. I had to wait a long time for the initial medical assessment, but I think that this was because the person in charge was operating a sort of feedback so that he didn't have too many people waiting at the next queue -- or too few either. What surprised me was that there was a long delay once I was on the couch; but I realised that it was a combination of rare events which meant that the nurses were busy elsewhere.

I wonder whether anyone in the blood donor service in the U.K. -- or elsewhere -- monitors where there are bottlenecks in sequences of queues. Not the long delays between doctors and hospitals, but the process within one system?

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.

Tuesday 12 April 2011

The Geograph Project

Six years ago, I signed up to take part in the Geograph project in the U.K. http://www.geograph.org.uk/

This is a mixture of eduaction and fun, and a challenge and a game. Photographs of places (not people) are linked to the Ordnance Survey (O.S.) grid-square in which the picture was taken. The O.S. maps are divided into squares with side 1km (i.e.metric) and any place in the U.K. can be located by a grid reference. I am sitting at SX 9309 9189 which locates me to within 10 metres. Some webpages will accept that and locate my home on a map or satellite.

The aim of those who signed up at first was to be the first to obtain a photograph for a grid square, and I recorded first "Hits" for about 100 of them. Most of mainland Britain has now been "Geographed" so participation for many people means extending the range of pictures. Within many grid squares there are numerous sites and sights to record, and those who are part of the project try to extend the range in various ways, and to add more squares to their personal tally. At the time of writing, I have photographs recorded in 1118 squares with a further 36 where my picture is only of a close-up detail.

So where does the link with O.R. apply? It first comes with the problem of planning an expedition to add further squares to that total. This could be seen as a variant of the orienteering problem, of finding ones way around check-points in the shortest time. Except that there are no check-points, all one wants are pictures from a square. So in an ideal world, one could stand at the corner of four grid-squares, and turn north-east, south-east, south-west and north-west and take pictures in each direction with negligible distance covered. To get a further two squares, you would have to walk one kilometre to the next intersection and take two more squares. Or you could walk 1.414.km diagonally and photograph three more squares. (I say walk, but obviously, you can travel in any way that you like.) So, travelling horizontally or vertically means that you obtain 4+2N pictures with a distance of N kilometres, i.e. an average of 2+4/N pictures per km. travelling diagonally gives 4+3N pictures for a walk of 1.414N kilometres, an average of
2.121 +2.828/N pictures per km. If you want 6 pictures, walk along a grid line.
If you want 7, go diagonally, If you want 8, go along a grid line, If you want 9 or 10, go diagonally. My reckoning is that for 21 pictures or more, the diagonal is best, but below that, you need to compare the strategies.

Letting H be along a grid line, D be diagonal
5H, 6H, 7D, 8H, 9D, 10D, 11H, 12H, 13D, 14H, 15D, 16D, 17H, 18H, 19D, 20H,

The problem is more serious than this because roads and paths do not allow one to wander at will. So the problem becomes more realistic when you start to impose such constraints, and to impose the obvious condition of returning to the start point. That is left for a future occasion.

Monday 4 April 2011

More on parking meter risk

Last November I speculated about different policies for scheduling the collection of cash from parking meters.
http://iaoreditor.blogspot.com/2010/11/parking-meter-risk.html

On Monday morning last week, the meters in our residential street were emptied. It struck me that whatever rules you have for collecting cash, this was not optimal. There are no parking restrictions at the weekend, so these meters had been full of their money for three nights and 66 hours. Fortunately, the local crime figures have not recorded any vandalism of parking meters in the past year.

Thursday 17 March 2011

Why OR in sports? Some reflections

Why is OR applicable to sports?

Many sports have a score, a number, to be maximised or optimised - hence there is a link to OR

Most sports have limited resources, to be used optimally - hence OR, The resources may be the team, or time, or money

Many sports operate sequentially, with decisions being made in order - just like in dynamic programming

Sports events require transport and supply chains - areas where OR has expertise

In a separate blog, I have mentioned the range of sports which have provided abstracts in IAOR. Most of those links are to strategy in the sport itself. My other blog on the subject considers the problems of scheduling transport.

Transport to sports events

When I studied OR as a postgraduate, we were presented with several scenarios to reflect on their logistical problems. One was related to sports transport.

An event is scheduled at time T1 and finishes at time T2. Spectators arrive by public transport in advance of time T1. Their arrivals are spread over a considerable period, as their plans vary. Some may want to be very early, others arrive in the last few minutes. But the general distribution of their arrivals is widely spread. So the transport provision has to reflect this ... with vehicles scheduled over a wide range of times before T1.

On the other hand, at time T2, all those who arrived by public transport are ready to depart at the same time. So the public transport has to be concentrated into a much smaller time window.

These are the same sorts of problem that one meets in other circumstances, but the size of the crowds at some sports events make the contrasting problems particularly difficult.

OR has been used by the organisers of the recent Olympics to cope with this scheduling problem. And already, the London Underground OR team is planning how to cope with the 2012 Games.

OR in Sport - the index

This month's suggestion from INFORMS is that bloggers should write about OR in Sport.
The problem that I have about this is knowing where to start. When I edited IAOR, there were numerous research papers that were included in IAOR, and I cross referenced them by sport. So my records show that there were abstracts relating to the following sports:
athletics
baseball
basketball
cricket
croquet
curling
darts
football
golf
hockey
horse racing
karate
netball
Olympics
orienteering
skating
skiing
tennis
volleyball
yachting
So, this is my first contribution - an index!

Tuesday 15 March 2011

Reducing wood waste



It is interesting to see how technology can be used to create something which is ethically and aesthetically pleasing. I have been pointed to the website of a company called Bolefloor who make wooden floorboards. But these are not rectangular boards, they follow the natural curves of the wood, so that there is less waste in shaping the boards.



So, here is their process:
1) take a tree
2) saw it and plane it into planks of uniform thickness (21mm)
3) scan the shape of the edges
4) now optimise -- how can the floor of a room be made of these planks, like a jigsaw, with plain or tongue-and-groove edges, to minimise the waste? Here is the O.R. content, though it looks as if it was people who come from the computer science academic regime who did it.
5) shape the edges and ship to the customer.

Result - a beautiful, unique floor.

Tuesday 1 March 2011

Puzzles and logic

My father had a selection of books of mathematical puzzles, and as a youngster I used to enjoy trying to solve them. Later, we subscribed to a Sunday newspaper, the Sunday Times, which had a weekly "Brainteaser". These were problems of logic and mathematics which we enjoyed solving together. Much to my mother's dismay, some Sunday lunchtime meals were disturbed as he and I debated how to solve the problem.

These were puzzles where the first stage was to sort out the logic needed to solve them. Recently, a number of puzzles have become popular, such as Sudoku. These need logic (and minimal mathematical skill) but the logic is more or less the same each time. I am interested in the reasoning behind the setting of such problems; how can you guarantee that the puzzle can be solved and has a a unique solution?

The Independent newspaper has carried Sudoku puzzles for several years; recently, it has carried a range of puzzles. We have been looking at the ones that are called "Maths Puzzle". These are based around the nine digits 1-9, arranged in a square, with two mathematical operators between the three digits in each row, and between the three digits in each column. Then, at the three row ends and three column feet, are the results of the "sum". The challenge is to work out where the nine digits are placed, given the six results and the twelve operators. See "Maths Puzzle" for an example.

So, I wonder how such problems are set. With nine digits, the checking could be done by brute force very quickly, and that is how I suspect it is verified. The newspaper's problems have an easy puzzle, with two digits entered, and a hard one with one digit entered. Tina and I tackle the problems ignoring those digits. Much more need for logic.

And the O.R. link? The solution is a problem of combinatorial optimisation.

Friday 11 February 2011

Games and the Acts of the Apostles

One of the standard textbooks in operational research a generation ago was "Fights, Games and Debates" by Anatol Rapoport. Rapoport distinguished between Fights, where you want to overpower your opponent, Games, where you want to outwit your opponent, and Debates, where you want to convince your opponent. Last week our home group Bible study was looking at chapter 25 and I commented that the story there illustrated those three situations.

The fight: in 25v7, When Paul came in, the men who had come down from Jerusalem stood around him. They brought many serious charges against him, but they could not prove them.

The game: in 25v3, They requested Festus, as a favour to them, to have Paul transferred to Jerusalem, for they were preparing an ambush to kill him along the way.

The debate: in 25v8, Then Paul made his defence: “I have done nothing wrong against the Jewish law or against the temple or against Caesar.”

As is clear from the whole chapter, the various parties present were not working to the same agenda, and hence they never communicated with one another.

Tuesday 8 February 2011

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.

Saturday 15 January 2011

Epidemics and advertising

I first learnt the power of stochastic models when I had lectures by the late Professor David Kendall (famed for the Kendall notation for queue models http://en.wikipedia.org/wiki/Kendall%27s_notation). He spoke about a simple model of an epidemic, and how that model gave rise to a statistical distribution for the number of people who would be infected. To add variety to his lectures, he spoke of the way that the model could be modified to describe the spread of a rumour (when someone spreads the message to someone who has already heard it, he realises it is a rumour and stops spreading it).

(Incidentally, I wonder whether David Kendall and I come from the same branch of the Kendall family, as my mother was a Kendall before she married.)

Since then, models of epidemics have become very much more sophisticated, but the essentials remain the same. As I write, the UK government is concerned with the spread of influenza in the population. The Labour opposition claims that the advertising about risk should have been started much earlier. In response, the government have spoken about the need to time the adverts for greatest effectiveness. I suspect that there are O.R. models in the background.

Advertising too long in advance is of limited value -- it will be forgotten. It needs to be at a time when it may affect the behaviour of people, who may be infected or susceptible. So the timing needs to be linked to models of the spread of the current 'flu virus. Hence two models need to be linked -- one about the effectiveness of advertising, the other an epidemiological one. But these models are bound to be in the background and, once again, O.R. is the "hidden science".

Marmalade, seasonality, production planning

It's the middle of January, and this is the time of year to buy Seville oranges. And to make real "English" marmalade, you must have Seville oranges. However, these oranges are only available for a few weeks, from early January to early February. Commercial producers can preserve the fruit and spread the production over the rest of the year, but amateurs have a short window for home production. It is seasonality, but seasonality of supply of raw material, not seasonality of demand.

So yesterday and today we have been making marmalade. Just over 20 pounds of it. (This is one product in the kitchen which we measure in pounds, not in the metric way, because the glass jars we use are "one pound jars" or "12 ounce jars" even though they are labelled 454 grammes, or 340 grammes.) This was two batches in our large jam pan, and my forecast is that it will last us until early 2012. Forecasting demand for twelve months is not generally advisable in industry or commerce, but in our case we know that the rate we use it is about 20 to 24 pounds per year, and we buy a little each year to add variety to the diet, to support charities who sell home-made marmalade, to try other flavours, and because my family know that a jar of "interesting marmalade" will be a welcome present for birthday or Christmas. Given all this, our actual demand for our own marmalade is less than 20 pounds per year, so next year will probably be a "one batch" January. So here is a matter of "make-to-stock" production planning!

The basic recipe can be varied in many ways; extra fruit can be added, in which case the quantity of sugar needs to be increased. This year, for the first time, we have added some fresh pomelo.

Who would have thought that something so mundane could illustrate facets of operational research.

Here's the recipe for a basic batch, which we keep written in one of the cookbooks on an old 80 column punched card!

3lb Seville oranges
2 lemons
5.25 pints water
6lb sugar, which may be mixed granualted and demarara
0.5oz margarine or butter

1: peel the fruit and cut the peel into slivers of the size you like (ours are about 2cm by 2mm [it is easier to give small sizes in metric units])
2: put the peel into 2.25 pints of water and simmer gently for 90 to 120 minutes
3: chop the peeled fruit roughly (we either quarter the fruit or cut it into 4 or 5 slices) and put it all as pith in a large jam pan with 3 pints of water and simmer alongside the peel
4: Drain the pith into a bowl or pan through a colander, and scrape the pith through the colander as well, to give "body" to the marmalade.
5: unless you have two jam pans, now you need to wash the jam pan
6: add the drained liquid from the bowl to the jam pan, add the peel and its liquid, add the sugar and boil steadily ("rolling boil") until a test shows that it has reached setting temperature. (We take a small amount, put it on a saucer, cool it in the freezer for 30 seconds and then see if it wrinkles. Other methods exist.)
7: remove from heat, add the margarine/butter and stir to remove the scum on the liquid. Leave to cool for 6-10 minutes
8: meanwhile, wash your jars, and place in a cool oven to dry and sterilize at about 100 deg C,
9: Carefully fill each jar, and finish off as usual for home-made preserves.

Tuesday 11 January 2011

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;

O.R. at the blood donor session


When I taught queue models in O.R. at the university I encouraged students to give blood at the regular donor sessions held on campus. It was a good example of queues in series -- arrive -- register -- health check -- give blood -- refreshments, and I urged the students to observe and consider how the system could be improved.

Yesterday when I gave blood, I arrived before the system had reached a steady state and there was little delay. Wonderful! As I lay on the couch, it was possible to watch the donor next to me and the machinery used to shake the blood. The plastic bags holding the donated blood rested on a tray which was programmed to rock. What was odd was that the rocking was intermittent. Up, down, up, down, pause. Repeat. Someone had designed it so that it rocked twice and then paused. Why? Was this an optimal way of rocking the blood? Someone had designed the mechanism, and that design had involved finding a numerical solution to "Rock N times, at rate R per minute, pause S seconds"

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"