Rubik's cube is not mainstream O.R., but news about it has made the news today, with the proof that every scrambled position can be solved in 20 moves or less. The announcement is here. It is good when mathematics is covered in the press.
There is a slight link with O.R., but I won't exaggerate it. In theory, you could create a dynamic programming formulation of the problem of solving a scrambled cube. The state would be the description of the cube; the decision would be which of the possible moves to make next; the single stage cost would be one; and the objective would be the minimum number of moves needed to solve the cube from its present state. Stages would be identified with the objective value. But before anyone tries this, note that the researchers looked at 55,882,296 cases (states).
And for the last two years, I have shared an office with Peter Vamos, one of Erno Rubik's cousins.
Thursday, 12 August 2010
Wednesday, 11 August 2010
Farewell to all that
Today I removed my last possessions from the university campus. Since I retired, I have had the privilege of a little working space on campus, in an office shared with several other active retired staff. I have used it for writing and editorial work, and valued the chance to see and talk with former colleagues.
Alas, that has now come to an end. The office is no longer to be free for the honorary staff, and so I decided to move my last few things home. As I did so, I thought back over the 35 years since I came to Exeter. It is unusual to have spent so much of one's entire working life in one place.
I have had six different offices, in three different buildings.
When I came, the data and programs for my research came with me in two card cabinets, each holding 10000 punched cards. When I left, I needed a USB stick to carry far more data and material. I regret that one of the datasets that was on punched cards has been lost; it can never be replaced, and there was scope for some more statistical analysis to be done on it. Some of the research publications that I had used for my PhD research were on microfiche; that is a medium which has practically disappeared. When I came, I already had a small collection of books and journals that filled about 12ft of shelf space. Even with pruning, I have three times that space for professional material.
When I started, the language of choice for programming was Fortran. That was my fifth language (after Algol 60, Titan Autocode, Basic, CSL). We progressed through Simula, Pascal, C and C++. The first desktop computer we used was a PET, but we never did any research on it. A research grant provided a more substantial machine in 1981 or 82, which used 8inch floppy discs, and compiled a Pascal program in about 20 minutes! Olivetti PCs arrived in 1986, and thereafter most of my computing was based on PCs.
What changes will there be in the next 35 years?
Alas, that has now come to an end. The office is no longer to be free for the honorary staff, and so I decided to move my last few things home. As I did so, I thought back over the 35 years since I came to Exeter. It is unusual to have spent so much of one's entire working life in one place.
I have had six different offices, in three different buildings.
When I came, the data and programs for my research came with me in two card cabinets, each holding 10000 punched cards. When I left, I needed a USB stick to carry far more data and material. I regret that one of the datasets that was on punched cards has been lost; it can never be replaced, and there was scope for some more statistical analysis to be done on it. Some of the research publications that I had used for my PhD research were on microfiche; that is a medium which has practically disappeared. When I came, I already had a small collection of books and journals that filled about 12ft of shelf space. Even with pruning, I have three times that space for professional material.
When I started, the language of choice for programming was Fortran. That was my fifth language (after Algol 60, Titan Autocode, Basic, CSL). We progressed through Simula, Pascal, C and C++. The first desktop computer we used was a PET, but we never did any research on it. A research grant provided a more substantial machine in 1981 or 82, which used 8inch floppy discs, and compiled a Pascal program in about 20 minutes! Olivetti PCs arrived in 1986, and thereafter most of my computing was based on PCs.
What changes will there be in the next 35 years?
Friday, 30 July 2010
Algorithms for better public transport
It is always pleasant when an operational research project is commented on in the media. I spotted this in Boing Boing, an online blog which I find fascinating and also frustrating. The story is about a research project into better algorithms for timetabling public transport, and has the acronym ARRIVAL, meaning
Algorithms for Robust and online Railway optimization: Improving the Validity and reliAbility of Large scale systems.
ARRIVAL is hosted in Greece (here), but has been an international research project, sadly without UK involvement. It has produced several published research papers, as well as practical solutions to transport problems.
Algorithms for Robust and online Railway optimization: Improving the Validity and reliAbility of Large scale systems.
ARRIVAL is hosted in Greece (here), but has been an international research project, sadly without UK involvement. It has produced several published research papers, as well as practical solutions to transport problems.
Wednesday, 21 July 2010
EURO XXIV (EURO24) in Lisbon, part 2
I realise that my first blog about the conference was a little negative. Let's look at the good things about conferences.
I met a great number of people, renewing old friendships, and in a few cases, starting new ones. Conferences are great for this, especially if most of the time, you are beavering away in one place, not meeting like-minded people. I have several friends who I have only met at conferences. It is even a good place to see friends from other parts of the U.K.. Of course, one shouldn't really admit that one goes to conferences to meet people; as far as our paymasters are concerned, we go to present our research work and to listen to other people present their research work.
That's the theory. In practice, many of the presenters are there to "Tick the box" of conference presentation. There is not enough time to discuss the material in depth in the sessions. And people work in tight little niches. So the chances are that you won't get many questions that stir new ideas.
But it was good to be part of this conference. Jim Cochran gave an excellent plenary session about teaching O.R. and making it interesting. The best attended session that I went to was on financial optimization and had some good papers. The worst for attendance was on sustainable development ("we are working on sustainable development for developing countries. To calibrate our model, we are using Luxembourg.") A good number turned up to a session on graphs and networks, but fewer were interested in water systems. And in all these, there were interesting models being discussed.
The conference organisers had excellent catering, apart from the reception. Endless coffee, chilled bottled water, fruit juice or squash, and biscuits to eat. Lunch was one of the easiest conference lunches I have known -- huge buffet tables, so very little queueing.
Springer had a demonstration of their touch-screen library, with 200 books available. All could be read and re-read on screen, though I wonder how long before their text books are on an electronic book?
The sun shone; Lisbon is beautiful, though the university campus could do with more effort clearing rubbish and repairing pavements. I wondered why there were so many police on the campus.
I met a great number of people, renewing old friendships, and in a few cases, starting new ones. Conferences are great for this, especially if most of the time, you are beavering away in one place, not meeting like-minded people. I have several friends who I have only met at conferences. It is even a good place to see friends from other parts of the U.K.. Of course, one shouldn't really admit that one goes to conferences to meet people; as far as our paymasters are concerned, we go to present our research work and to listen to other people present their research work.
That's the theory. In practice, many of the presenters are there to "Tick the box" of conference presentation. There is not enough time to discuss the material in depth in the sessions. And people work in tight little niches. So the chances are that you won't get many questions that stir new ideas.
But it was good to be part of this conference. Jim Cochran gave an excellent plenary session about teaching O.R. and making it interesting. The best attended session that I went to was on financial optimization and had some good papers. The worst for attendance was on sustainable development ("we are working on sustainable development for developing countries. To calibrate our model, we are using Luxembourg.") A good number turned up to a session on graphs and networks, but fewer were interested in water systems. And in all these, there were interesting models being discussed.
The conference organisers had excellent catering, apart from the reception. Endless coffee, chilled bottled water, fruit juice or squash, and biscuits to eat. Lunch was one of the easiest conference lunches I have known -- huge buffet tables, so very little queueing.
Springer had a demonstration of their touch-screen library, with 200 books available. All could be read and re-read on screen, though I wonder how long before their text books are on an electronic book?
The sun shone; Lisbon is beautiful, though the university campus could do with more effort clearing rubbish and repairing pavements. I wondered why there were so many police on the campus.
Friday, 16 July 2010
Locating emergency ambulances
The ambulance station in Exeter is on the east side of the city. The city is divided by the river Exe, and the bridges across the river form a bottleneck for traffic. Quite often there is gridlock on the roads approaching the bridges.
So the ambulances are deployed away from the station at times of peak traffic. Yesterday, Tina and I were walking by the river and we spotted such a redeployed ambulance parked by the footpath. It made me wonder ... about the policy for deploying ambulances. This one was placed so that it could cross the river, or leave the city to the north and west. In either direction, the response time would be about ten minutes less than if it started from the base station. My wondering focussed on what conditions prompt such deployment. Is it when the traffic is reported to be at a particular state? Or simply at particular times of day? Has anyone worked on this?
I was reminded of the policy of French traffic police that I saw on holiday; they were deployed to busy roads and junctions and set up tables to deal with on-the-spot fines.
So the ambulances are deployed away from the station at times of peak traffic. Yesterday, Tina and I were walking by the river and we spotted such a redeployed ambulance parked by the footpath. It made me wonder ... about the policy for deploying ambulances. This one was placed so that it could cross the river, or leave the city to the north and west. In either direction, the response time would be about ten minutes less than if it started from the base station. My wondering focussed on what conditions prompt such deployment. Is it when the traffic is reported to be at a particular state? Or simply at particular times of day? Has anyone worked on this?
I was reminded of the policy of French traffic police that I saw on holiday; they were deployed to busy roads and junctions and set up tables to deal with on-the-spot fines.
EURO XXIV (EURO24) in Lisbon
I spent some time in Lisbon this week for the 24th EURO conference. EURO is the association of national OR societies from Europe (plus those in Israel and Africa). It was based on the university campus, running from the evening of Sunday 11th July and ending late on Wednesday 14th July. For various reasons I couldn't stay for the last day.
As usual, I have come away from the conference with mixed feelings. It was a huge event, with about 2,700 delegates from the European nations and beyond. Many of them were research students presenting their work in a forum related to Operational Research.
As usual, when things went wrong, I stopped to wonder how things could be improved. So here are some general suggestions for any conference ....
1) Learn from the mistakes of other people. Some things go wrong every time, in different details. One of the disadvantages of EURO is that there is insufficient corporate memory. Each conference is arranged without much having beenlearnt from earlier ones.
2) Consider all the bottlenecks in the queues and points of service associated with a conference. Delegates need service with their registration and need to be able to use the conference website to answer a range of questions quickly and without having to go thorugh too many hoops. So the website should be simple to use and comprehensive. Registration on site is the first queue most people encounter and it should be as simple and quick as possible, which means that efforts should be made in advance to make service times as short as possible OR to have lots of people to give service. To complete my registration I needed to join three queues (for my badge, for my confernece bag and papers, for my banquet ticket). If I had gone on the excursion, there would have been another queue. At other events, these queues could be replaced by one. Similarly, catering queues need to be minimised. It doesn't take advanced use of queue theory to work out that 2,000 people gathering for a buffet meal need a lot of service points. 100 servers perhaps?
3) Help the delegates to find their way around. The home team knows its way around the buildings, but everyone from elsewhere doesn't so they need signs that can be found easily and read quickly.
4) Make sure that the rooms are suitable for the meetings. I spent an afternoon in a room directly underneath the waste pipes of the ladies' toilets, so there were regular sounds of flushing. Another session was in a warm room, and the window opened in such a way that the screen was obscured by the frame.
5) For presenters. Do think about what you should put in your presentation. Nobody will take in your equations and constraints with a hundred variables -- my record was seven different subscripts in the equations on one screen. And large tables are too much to take in during a fifteen minute presentation. There is only time for two or three main points, and then these need to be put simply and clearly.
6) Also for presenters. Do rehearse the presentation, and do it with an audience who will be honest with you. Because the presenters come from all over the place, some of them are less fluent in English than the Brits and other English-speaking countries. Going through the presentation several times before will deal with nervousness, and keep the talk to its time slot.
7) For session chairs. Keep strictly to the timetable and follow your instructions carefully. At EURO the majority of sessions lasted 80 minutes with four papers. They were supposed to keep to 15 minutes presentation, and 5 minutes discussion. Chairs were to keep an eye on the time and stop the speaker. That allowed delegates to move between sessions at those 20 minute intervals. And if presenters didn't show up, then there should be a gap, because there could be people switching sessions to hear the talks at their scheduled times. Did this happen? No ... talks over-ran, chairs failed to stop them, and if there were no-shows, they just went on with the next paper.
8) For everyone, especially those with major responsibilities; there is a time and place for everything, and some plenary sessions are not the times for unnecessary announcements and speeches. For many EURO delegates, a lasting memory of the conference will be the description of how to adjust the conference souvenir bag that was given after the conference banquet!
As usual, I have come away from the conference with mixed feelings. It was a huge event, with about 2,700 delegates from the European nations and beyond. Many of them were research students presenting their work in a forum related to Operational Research.
As usual, when things went wrong, I stopped to wonder how things could be improved. So here are some general suggestions for any conference ....
1) Learn from the mistakes of other people. Some things go wrong every time, in different details. One of the disadvantages of EURO is that there is insufficient corporate memory. Each conference is arranged without much having beenlearnt from earlier ones.
2) Consider all the bottlenecks in the queues and points of service associated with a conference. Delegates need service with their registration and need to be able to use the conference website to answer a range of questions quickly and without having to go thorugh too many hoops. So the website should be simple to use and comprehensive. Registration on site is the first queue most people encounter and it should be as simple and quick as possible, which means that efforts should be made in advance to make service times as short as possible OR to have lots of people to give service. To complete my registration I needed to join three queues (for my badge, for my confernece bag and papers, for my banquet ticket). If I had gone on the excursion, there would have been another queue. At other events, these queues could be replaced by one. Similarly, catering queues need to be minimised. It doesn't take advanced use of queue theory to work out that 2,000 people gathering for a buffet meal need a lot of service points. 100 servers perhaps?
3) Help the delegates to find their way around. The home team knows its way around the buildings, but everyone from elsewhere doesn't so they need signs that can be found easily and read quickly.
4) Make sure that the rooms are suitable for the meetings. I spent an afternoon in a room directly underneath the waste pipes of the ladies' toilets, so there were regular sounds of flushing. Another session was in a warm room, and the window opened in such a way that the screen was obscured by the frame.
5) For presenters. Do think about what you should put in your presentation. Nobody will take in your equations and constraints with a hundred variables -- my record was seven different subscripts in the equations on one screen. And large tables are too much to take in during a fifteen minute presentation. There is only time for two or three main points, and then these need to be put simply and clearly.
6) Also for presenters. Do rehearse the presentation, and do it with an audience who will be honest with you. Because the presenters come from all over the place, some of them are less fluent in English than the Brits and other English-speaking countries. Going through the presentation several times before will deal with nervousness, and keep the talk to its time slot.
7) For session chairs. Keep strictly to the timetable and follow your instructions carefully. At EURO the majority of sessions lasted 80 minutes with four papers. They were supposed to keep to 15 minutes presentation, and 5 minutes discussion. Chairs were to keep an eye on the time and stop the speaker. That allowed delegates to move between sessions at those 20 minute intervals. And if presenters didn't show up, then there should be a gap, because there could be people switching sessions to hear the talks at their scheduled times. Did this happen? No ... talks over-ran, chairs failed to stop them, and if there were no-shows, they just went on with the next paper.
8) For everyone, especially those with major responsibilities; there is a time and place for everything, and some plenary sessions are not the times for unnecessary announcements and speeches. For many EURO delegates, a lasting memory of the conference will be the description of how to adjust the conference souvenir bag that was given after the conference banquet!
Tuesday, 1 June 2010
Revenue management in the news
Two stories about revenue management have been in the news recently. As I heard about them, I wondered what data had been used within the companies concerned to inform the decisions.
Ryanair, the budget airline, has announced that the cost per item for checked baggage will be higher in July and August than at other times. (£15 per item normally, £20 in July/August; those are the online fees; in person at the airport costs more, and so does the second item). Ryanair reckons that the introduction of fees for checked baggage has reduced the number of passengers with hold baggage from 80% to about 25%. Presumably the company expects that there will be an increase during the holiday months, which will mean that they will need more ground staff, more fuel and possibly fewer passengers.
The other story concerns telephone charges. For many years in the UK, phone calls between 6pm and 8am during the week have been cheaper. Earlier this year, BT (British Telecom, phone provider) changed this period to be 7pm to 7am, and recently another supplier, TalkTalk, has followed suit. It is suggested that the motive is more concerned with profits than regulating peak demand, since the hour 6pm to 7pm is not generally used for business calls, more for domestic. It may be that there is high demand for domestic internet services in the early evening, and therefore this is an attempt to shift telephone demand away from that period. But the companies are not saying.
One of the speakers on this subject was described as working in "Pricing consulting" and I thought to look up such businesses on the internet. I really should know better! "Pricing consulting" led to numerous pages advising how much to charge for consultancy! The perennial problem of words which can be nouns or verbs.
Ryanair, the budget airline, has announced that the cost per item for checked baggage will be higher in July and August than at other times. (£15 per item normally, £20 in July/August; those are the online fees; in person at the airport costs more, and so does the second item). Ryanair reckons that the introduction of fees for checked baggage has reduced the number of passengers with hold baggage from 80% to about 25%. Presumably the company expects that there will be an increase during the holiday months, which will mean that they will need more ground staff, more fuel and possibly fewer passengers.
The other story concerns telephone charges. For many years in the UK, phone calls between 6pm and 8am during the week have been cheaper. Earlier this year, BT (British Telecom, phone provider) changed this period to be 7pm to 7am, and recently another supplier, TalkTalk, has followed suit. It is suggested that the motive is more concerned with profits than regulating peak demand, since the hour 6pm to 7pm is not generally used for business calls, more for domestic. It may be that there is high demand for domestic internet services in the early evening, and therefore this is an attempt to shift telephone demand away from that period. But the companies are not saying.
One of the speakers on this subject was described as working in "Pricing consulting" and I thought to look up such businesses on the internet. I really should know better! "Pricing consulting" led to numerous pages advising how much to charge for consultancy! The perennial problem of words which can be nouns or verbs.
Subscribe to:
Posts (Atom)