How my Ancestors used Operational Research
A few years ago, I taught a course module called “Graphs, Networks and Algorithms”. It was generally known as GNA. As part of the module, I created four spoof interviews with people who might have used the mathematical techniques of GNA at four times in history or prehistory.
Therefore, as one contribution to the INFORMS Challenge on OR and the Family, I offer:
How my Ancestors used Operational Research
Stigina, the Druidess
We interviewed Stigina on a windy hillside in Wiltshire, which gave us a very good view of the largest civil engineering project in Britain, one that she has been supervising for several years.
Interviewer: Stigina, this project has taken twenty years to complete, and you have been in charge of it for the last ten years. I believe that you said recently that the project would have taken another ten years except for your use of mathematical models that you learnt at university. Would you like to tell us about them?
Stigina: As readers will know, this project has involved a large number of people, and it has been necessary to coordinate their labour on a day-to-day basis. We have also had to move some very heavy construction items and other equipment over considerable distances. And, like every major project, the accountants have demanded that we do all our work within a tight budget. So I was very pleased to use some ideas from a course at the university called GNA.
Interviewer: Can you explain as simply as possible what ideas these were?
Stigina: Well, the stone that we used had to be transported to the site. In the GNA course we used diagrams to show possible routes between places. My assistant and I drew some diagrams on the walls of the cave that we used as the site managers office. These showed routes between the quarry and the project site, and I used what the mathematicians called “vertices” to show places where the workmen could obtain food and water. The same idea was used many years ago in France, at a place called Lascaux; the food vertices were drawn in the shape of different kinds of animals on the walls of a big cave. Then we worked out how many stones could be moved each month between these places, knowing that our workmen needed to hunt and look after their crops as well as be on the site. Then we used something that I learnt in GNA called the maximum flow algorithm to plan the routes that the stones would follow to get them here as quickly as possible.
Interviewer: This all sounds very useful. Are there other items from that university course which might be useful to modern society?
Stigina: I think so. Another valuable idea was called “assignment”. It could be useful for some of our ceremonies. Those who preside at such ceremonies come from many parts of the country. There are ceremonies in many places, and I am sure that the planners could use the idea of assignment to make sure that each ceremony was presided over and that all the possible presiding officers were employed. Sometimes, these days, there are druids who travel for weeks simply to attend a ceremony, and others could take their place if the assignment was done properly.
Interviewer: Thank you; one last question. What is the project going to be called?
Stigina: While we were building, there were several suggestions about what the structure should be called. But we decided that it should be named in honour of the stones and the university course, so I can reveal that its name will be Stonegna, although I expect that over the next few years that name will change a little.
Interviewer: Thank you, and congratulations on completing this huge project on time and within budget.
Stigina: Don’t thank me, thank the GNA course.
The Brunswig branch of the family
“No photographs, please!”
Our interviewer was a little startled by this opening remark from our latest interviewee. So she asked for an explanation.
“Surely you know. I’m still persona non grata in one of the towns round here, and I suspect that the Brunswig police might want to ask me some questions. The whole matter was closed some months ago, but there are people with long memories and short tempers. As far as I am concerned, there was a misunderstanding, and the press created some sensational stories. There was one reporter called Browning who made up a particularly fanciful account. But I have had to change my appearance for my own safety.”
So we asked for his side of the story.
“You can call me PP. Anyway, after I graduated from the university with my vocational degree, I spent a couple of years working in an established business before starting one on my own. All went well until I was negotiating a contract with the councillors--the town had such a problem with rodents that they were prepared to pay weekend rates for the job.”
“Wait a moment. PP, Are you saying that your business--let’s be blunt, you are a rat catcher--is a graduate profession?”
“Of course it is. But of course we don’t call ourselves by that name. We remove all kinds of pests, not just rats and mice. I had to deal with a couple of snakes in the royal apartments last week--nobody would admit to having let them loose, but the king has already taken on extra bodyguards. Most people in the business have a postgraduate degree in rodent extermination. There have been courses at several universities for the last twenty years or so. The degree programme has a mixture of history, biology, management and psychology. I was very fortunate to get a place on the course.”
“And you took options in mathematics and engineering?”
“Yes. I had studied mathematics and physics to A-level, and I wanted to use that background. In the psychology module, the lecturer had spoken of the effect of particular sounds on rodents, and that encouraged me to look at ways of generating and amplifying music as a method for clearing premises. I took out a patent on one invention. Here’s an example--called a Portable Interactive Eradication Device (PIED for short). And in mathematics, I studied that module called GNA, which I have found extremely useful.”
“Could you explain? There doesn’t seem to be much of a connection between graphs and rat catching--sorry, rodent extermination.”
“Well, one of the important parts of my job is deciding where to place traps. So I often draw plans of the building and try to find optimal locations for deterrents. GNA helped on that. And I need to patrol them, and I use a method called the travelling salesman algorithm for that. And often, when I have a really big job, I need to go round all the streets and alleys of a town to look for the signs that vermin have been there. For that, I used to use an algorithm that was devised for helping postmen--unfortunately, the postal service will not disclose their routes to me, saying that they are commercial secrets, so I need to find the optimal tours for myself. But the PIED has changed some of my processes--and that led to my problems in you-know-where.”
“Can you explain?”
“Using PIED, I don’t need to go along every alley-way. The sound that it generates attracts vermin within a radius of about twenty metres. Thus, if I go past the end of a short alley, I don’t need to go into it; I blow into the device and it saves me time. But the problem of finding an optimal route around a town is changed--I had to devise a new mathematical model and algorithm to solve it, using general principles from GNA. The trouble is that I complete contracts much more quickly than before. The councillors didn’t believe that I had actually dealt with the problem when I reported that the job was done within the weekend and they refused to pay me. And then they accused me of bewitching their children with PIED. I had to leave--but thanks to the publicity in the media, I have been offered a role in a TV commercial. You’ll see me advertising a men’s spray on deodorant.”
“Thank you for this interview.”
Charles, who went to sea with Sir Francis Drake
We sent our interviewer to see the recently retired Lord Mayor of Plymouth at his newly purchased mansion, known as Buckland Abbey. As is well known to all, the former Lord Mayor has had a brilliant career as a sea-farer, military strategist and civic leader. Already, there are many legends associated with his exploits. History will be the judge of how many of these are true.
We wanted to talk about his association with mathematics and this is an edited account of what he told us.
Of course, our sailing expeditions always included skilled navigators. Otherwise we would have been much less successful, both financially and in matters of new discoveries. Some of our navigators were trained as seamen, but on the important expeditions we employed the best possible men, and on my round-the-world journey, fifteen years ago, our chief navigator was an exceptional person. His name was Charles, and he had studied at the university of Cambridge, and then had traveled in Europe, studying in Denmark with an astronomer called Brahe and in Italy with a university professor called Galileo. His calculations and observations were always scrupulously correct. I could rely on his skill, day and night, all the time. But he also made me think about the business of sea-faring in a new way. Besides his charts, he often would show me diagrams--he called them “graphs and networks”-to explain what had happened, and what was going to happen according to his calculations. On his “graph” he would draw a small circle, and say that it represented a Spanish man-of-war; another circle would represent my ship, the Golden Hinde. Then he would draw more circles, representing places that we could reach between our ship and where the Spaniards were going. Together we would plan our route, and he would talk about the difference between taking the shortest route and the quickest route, and how these might be quite different. He would talk about the difference between the route that one ship might take and the best route for a fleet--and that was really useful. His greatest moment came, of course, when we had the invasion scare in ‘88. As you know, we were playing bowls on the Hoe at Plymouth when the first reports of the fleet reached England. Immediately, I sent for Charles, and to help calm my nerves and those of my fellow captains, we continued the game until he came. We made up a story to explain why the game went on--I didn’t want anyone to know that the secret weapon was going to be a mathematician and his ideas of graphs and networks! Charles used the bowling green and the bowls we had been playing with, and created diagrams so that we could plan the whole endeavour. We followed his instructions, sent the ships along the best routes according to his calculations, used the quickest routes which the enemy didn’t know about, and we were successful.
I even found employment for Charles on land; when I was planning the new water supply for Plymouth--the one that they now call “Drake’s leat” from the moor, Charles used his paper and quill pen to plan with graphs and networks and decide on the routes for the water. It really should be called “Charles’ leat” because of all the work that he did.
And after that, Charles went back to his books. He said that on our great voyage he had been able to disprove the idea that the sun went round the earth, and he wrote to his friend Galileo about it. And he told me that he had some revolutionary ideas called the “Laws of Motion” and “Calculus”-I didn’t understand them at all. He wrote to his old college in Cambridge about them just before he died; I hope that someone can use his ideas--but perhaps Charles will not get the credit that is due to him. I wonder ....
Interviewer: Thank you, Sir Francis
The 1920’s “Flapper Girl” and businesswoman
We interviewed Marion in her fashionable South Kensington flat, just round the corner from Harrods Department store.
Interviewer: Marion, if you will pardon us saying so, you look like a typical “flapper girl” of the 1920’s. Very few of your generation went to university, and even fewer studied mathematics. Can you tell us about your experience?
Marion: Well, my mother was one of the campaigners for “Votes for Women” a few years ago, and it seemed natural to want to use my brain and go to the university. And I enjoyed mathematics at school, and wanted to continue to learn. So that is how it came about.
Interviewer: Did you enjoy university life?
Marion: Of course I did. There were a lot of rules to protect us girls, but somehow we managed to have a really good time; I learnt the latest dances, such as the Charleston, and I remember the first talking picture to come to the cinema.
Interviewer: And now you have started your own business; can you tell us a little about it?
Marion: While I was at the university, the first crossword puzzles came into the newspapers, and some friends and I wasted a lot of time trying to solve them. But they have become extremely popular and we have decided to set up a business which employs people to create crossword puzzles and we sell them to magazines and newspapers, and organise competitions as well.
Interviewer: And how is mathematics connected to word puzzles like that?
Marion: You know the author Lewis Carroll was a pseudonym for an Oxford mathematics don, who created word puzzles called acrostics. There have always been links between mathematics and games. But my friends and I saw that we could use our university studies, and particularly a course called GNA, to help us make better puzzles and do create them more quickly. Let me explain, as simply as possible.
First of all, crossword puzzles need to have a grid of words, and then we need to set clues for those words. Usually we have one or two words that we would like to include in the grid. The simplest puzzle we use has six words, each of five letters. Suppose that the first two words that we want are “VOTES” and “WOMEN”, just like the little puzzle that I have drawn here. (I haven't managed to post the example ... sorry. It was a 5 by 5 grid, with five letter words in rows 1,3 and 5 and also in columns 1, 3 and 5. Row 1 read VOTES, Row 3 read WOMEN.) Now in the GNA course, we studied the mathematical concept of trees, and we use that here. Just like your family tree, an incomplete grid can have descendants, and we make the descendants of one grid have the same words, and one more. In this example, we need a word which starts with a V and has a W in the third place. There are only two or three words like that, so it restricts the choice of further words. Because the GNA course taught us to think about trees and branches, our business can make puzzles much more rapidly than our rivals who don’t know about such useful ideas. In fact, it doesn’t take very long to complete that grid with the words VOWEL, LODGE, TIMID and SINGE.
Interviewer: And has that university course helped you in other ways in the business?
Marion: More and more newspapers want what we call “cryptic crossword puzzles”. Instead of giving a clue to the word by a definition, the clue is in two parts, a definition and cryptic hints about the letters in the word. We are using the same idea of trees to help us with the cryptic hints. Take the word “VOTES” as an example. One descendant of the word in the tree would say that it was an anagram of “STOVE”. So our clue writer might write: “Selects broken stove” as the clue. Another descendant might say that it was made up of the letter V followed by OT, followed by E and S, so the clue writer might write “Elects five with warm Cockney players” Because you see, E and S are players in the game of bridge and OT is the way a Cockney might say “hot”. For longer words than “VOTES” we sometime have several possible descendants and it helps the clue writer a lot to know them.
Interviewer: So you are really grateful for the GNA course at university. What next for your business?
Marion: We’ve just heard about a Japanese puzzle to fill in numbers in a square, but I don’t think it will ever catch on.
Interviewer: Thank you very much.
(For the record, the picture is of my grandmother, who really did go to university in Liverpool and graduated in 1912 in classics. All the rest is fiction.)