Monday, 29 December 2014

Complexity Theory - a Tool for Operational Research?

From time to time, I come across a book which I would have liked to have read and had on my academic bookshelves years ago.  Here is one.  It is Neil Johnson's book on complexity theory, which is published under two titles:  the copy that has come from a UK library has the title: Two's Company, Three is Complexity: a simple guide to the science of all sciences, but Amazon has a similar book:
Simple Complexity.

There is comparatively little about Complexity Theory, as Johnson defines it, in the O.R. literature.  Type "complexity" into International Abstracts in O.R. and you come up with analyses of the complexity of various algorithms, and a very few references to complexity theory in the sense of the book.  But Johnson is writing about the complexity of large systems, and so it overlaps with systems theory in O.R., with knowledge management, and with agent-based simulation (among others).  

Johnson comes from a background in physics, but his work links to the work of others in traffic modelling, conflict analysis, epidemiology, financial modelling, and much else.

In this book, Johnson defines the key components of complexity and complex systems as follows:
  • The system contains a collection of many interacting objects or "agents"
  • These objects' behaviour is affected by memory or "feedback"
  • The objects can adapt their strategies according to their history
  • The system is typically "open"
  • The system exhibits emergent phenomena which are generally surprising, and may be extreme
  • The emergent phenomena typically arise in the absence of any sort of "invisible hand" or central controller
  • The system shows a complicated mix of ordered and disordered behaviour

Other entries in this blog have mentioned the need in O.R. for the analyst to define the extent of the system being considered in a project.  Learning about complexity theory from the book has emphasised the importance of that.  I thought of two linked studies that I did; the first involving the long-term strategy for managing some water resources, and the second with the hour-by-hour management of part of those resources.  In the first part, we assumed that there were good rules for the hour-by-hour management, and for the latter we used the long-term results as a constraint on the control policies.  But throughout these two studies, we were aware that the interaction of the two models needed much more refining - but we lacked the data and computing power to do it.  One system had a time horizon of years, the other, used models with a horizon of a few hours.  The two time scales differed by several orders of magnitude.  We might have made progress by introducing some concepts and techniques from complexity theory.    

In another study, we looked at the deployment of patrol vehicles along a motorway; there was a "basic" policy for assigning them.  But as soon as those vehicles were being "used", their deployment needed active human intervention.  Traffic on the motorway, and the patrols, created a complex system which matched the list of components above.  

My recent blog about supermarket shopping in the run-up to Christmas touched on some aspects of the complexity of human beings going shopping!

Johnson's work on financial models overlaps with some models in O.R.  What I found especially interesting was the discussion of time series analysis ... there was a lot of material which deserved a place in an O.R. module about forecasting.

The one gap in the book for me was how to use some of the models to do what O.R. people do - answer questions "What happens if?"  The models work to describe real-life phenomena, but don't always offer opportunities for studying the effects of change through management decision-making.   There's scope for a follow-up book.  When I looked in the International Abstracts in O.R, one abstract was for a paper which covered some of this, and the abstract claimed that the paper would be the first of two papers.  I can't find the second paper!

All in all, if you are doing O.R., and you want to learn a little about how complexity science is modelling systems which are of interest to O.R (and many of us ought to have done this a few years ago!), have a look at this introduction!

Wednesday, 24 December 2014

When did you do your Christmas food shopping this year?

According to one of Britain's leading supermarket chains, Morrisons, the optimum time to go shopping for perishable food for Christmas was in a window between 6:30am and 7:30am on December 23rd. 

This suggestion was the result of some analysis of footfall at stores, and also used arguments about the freshness of perishable foods.  Because the stores receive deliveries in the small hours, and the fresh deliveries are stacked on the shelves early in the day, the early shoppers will have fresh goods, and there will be a large number of assistants working in the shop to help customers.  Also, footfall statistics show that this hour is not a popular time for shopping, so there will be fewer customers to battle with. 

As the result was announced in the news media the previous day, one wonders how many people changed their behaviour and did their food shopping in that time window this year.  I don't know if enough people did so to make the time non-optimal. 

I confess that I did consider suggesting to Tina that we might change our plans ...

But we did observe an interesting phenomenon when we turned up at our nearest supermarket where we planned to use a discount voucher before it expired.  It was 10am, and the car park was full.  All the checkouts were busy.  It took us about 45 minutes to complete our shopping, and by then the queues at the checkouts had almost gone, and the car park had plenty of space.  We concluded that many people had set out to shop in the 9am to 10am window ... maybe the rush had started earlier, but the observation of our shopping time, the queues and congestion suggested that many shoppers were coming first thing after breakfast.  (We felt smug, as we had been swimming for nearly an hour first thing after breakfast, before shopping.)  So, maybe there is another good window for shopping if you arrive at about 10:30am?

And, late this afternoon, after the crib service at church, we cycled to the same store, on the lookout for bargains at the end of the trading day.  (Yes, we did find some food that had been reduced in price.)  We had expected that most customers would have finished their purchasing, but it wasn't so.  There were queues for the car park, and busy checkouts.  It was busier than in the last two years, when we have also wandered up after the crib service, seeking bargains.  (Even the cycle racks were full.) 

Modelling customer demand for this supermarket would be interesting.  We got the impression that customers have been adapting the time when they shop - in response to their own and other people's experience?  If so, how does a modeller make forecasts?  It is a reminder that operational research modelling that involves people and their actions needs to acknowledge the complexity of people's psychology.  As is often the case, modelling humans is much more complex than modelling machines!

Saturday, 20 December 2014

A Christmas tipple, statistically

Did you know that half Britain's adults have their first glass of wine on Christmas Day at 1:12pm?  It must be true - it is in a newspaper!

Leaving aside the silliness of recording such an item of data (I can't tell you to the nearest minute what time today I had any drinks, and I doubt if many of the readers of this can either), there is the interpretation of the data.  I suspect that what was meant was

half Britain's adults have started their first glass of wine on Christmas Day by at 1:12pm soon after 1pm

Cheers!  And Happy Christmas!

Everyday heuristics

Fifty-six years ago, a paper appeared in Operations Research (vol 6, p1-10) with the title: "Heuristic Problem Solving: The Next Advance in Operations Research".  Written by Herbert A. Simon and Allen Newell, it daringly proposed advances in the power of computers to solve problems by heuristic methods, and not by purely algorithmic methods.  It caused a flurry of discussion in the correspondence section of the journal. 

Since then, we have become accustomed to the use of heuristic methods as part of the tool-kit of O.R.  But we do not have one heuristic method for problem solving - we have many.  Some of them have developed into the well-established metaheuristics of simulated annealing, tabu search, genetic algorithms, ant-based algorithms, and many others.  A glance at the content pages of our journals, or (even better since it classifies papers) through the index of the International Abstracts in O.R., will show how often heuristics have been used to advantage in the "Science of Better".  Of course, heuristics are for finding "better" rather than "optimum", although there are many situations where the heuristics do find an optimum.

But it is salutary to look at the frequency of heuristics in the equipment we use in everyday life.  Usually the heuristic is hidden in some computer chip or electronic circuitry, and only by stopping to think about it do we recognise that someone, somewhere, has realised that a heuristic is needed and has programmed it.  One of the earliest papers on heuristics that I ever read (and I can't find a reference to it - any suggestions?) gave a list of simple, everyday heuristics.  "Use an old golf ball when there is water hazard".  "Order a new chequebook when you reach the reminder slip in your present one" and so on.  The second of these examples is now outdated with my bank; the bank's computer has a heuristic which recognises when I am nearing the end of the chequebook, and issues a new one without my need to remind the bank.  I wonder whether the heuristic also has a parameter based on the average number of cheques that I write each month.  So there is a heuristic that affects my life.  

What about others?  We replaced our old car with a newer model a few months ago.  This one has several heuristics built into its control electronics.  With the headlights set to an automatic setting, the lights come on when a sensor detects the ambient light levels to be too low.  That is wonderful - except that the headlights come on when we drive the car into or out of the garage.  They also come on in some Devon lanes, when the hedges or banks create a dark canyon.  The heuristic is good, but it isn't optimal.  The car has sensors for the drag on the windscreen wipers, so adjusts the sweep if there is light rain.  That heuristic can be disconcerting, if, like us, you are used to regular sweeps of the wipers.

The kitchen is another place where everyday life encounters heuristics.  The freezer pump switches on when it detects an internal temperature which is too high - but it is not so sensitive that it will switch on immediately the door is opened.  The oven has a thermostat which controls the heating elements and fan - according to a simple heuristic.  I was surprised to see an advert for an oven which claimed that it could be controlled to an accuracy of one degree Celsius.  None of the recipes that I use require such excessive accuracy.

The radio tunes when there is a signal of sufficient strength.  The mobile phone operates with numerous heuristics.  

So are these heuristics that solve problems part of the breakthrough that Simon and Newell anticipated?  Yes.  They are parts of the hidden application of O.R. in twenty-first century life.  And there are many, many more.

Tuesday, 16 December 2014

Choosing how to travel

When operational research was in its infancy, many O.R. teams prided themselves that they were interdisciplinary.  As the subject has matured, it has become increasingly specialised and a little distant from the idealism of the infant interdisciplinary pattern.  Before I am targeted by correspondents who do work in interdisciplinary or multidisciplinary teams, I know that there are many teams where insights from  biology, engineering, mathematics, physics, psychology and zoology are brought together to solve problems.  But for many people doing O.R., the impact of disciplines other than the corpus of operational research techniques only comes from the language of the client, whether the client is in advertising, production or finance.

What makes me think of this?  A friend was sent a U.K. government brochure, "Britain in 2014", subtitled "Your essential guide to the issues that matter" and produced by the U.K.'s Economic and Social Research Council (E.S.R.C.).  The contents describe a number of sponsored research programmes, without getting into technical detail.  There were many interdisciplinary programmes, and many were tackling the type of "What happens if?" questions that O.R. specialises in.

So I was both interested and disappointed to read an interesting article about commuting to work by bicycle, which has been using GIS data to study peoples commuting in several cities, and modelling behaviour using agent-based simulation.  (Actually, not many O.R. studies in the literature use agent-based simulation, which is also a shame.)  Interested, because throughout my career, I did commute to work by bicycle.  Disappointed, because it was an ideal piece of work for the skills of O.R. to have contributed to.  The link for the reports is here.   It was part of a wider study of transport options for the future in cities.   I wonder whether there were O.R. people who could have helped but for their own reasons did not.  From my own academic experience, it is difficult to work across academic departments; maybe we have dug our own compartments in the ivory tower?  And to write this is not to be critical of the researchers; they have done an excellent job;  it was a study that I would have loved to be part of.

Commuting patterns vary across the country.  London has a very high proportion of commuters.  Parking cars in the city is very expensive.  But the study draws in the GIS and usage data for the use of "Boris Bikes" (cheap hire bikes available across London) which show how many commuters are using these bicycles every day.  Their behaviour has changed because the bikes are available.  What would happen if similar hire bikes were made available in another city?  Agent-based simulation would help answer such a question.

The data for studying commuting falls into the current themes of "Big Data" and "Analytics"; but some of the modelling tools are well-known from the established O.R.corpus - network flow models, epidemiology, time series analysis, stochastic processes. etc.

So, here is a quote from the short report in "Britain in 2014":

The practice of cycling to work can change, with meanings, abilities and stuff all connected.
For example, in the 1980s, virtually no one wore a cycle helmet in the UK; now it is often seen as essential. But this supports cycling being seen as a dangerous activity requiring specialist gear (in high-cycling countries, people wear everyday clothes). The ‘stuff’ you need to cycle depends on what you think cycling means, and what others do. Similarly, the ‘abilities’ you need depend on the cycling environment, and the demands it places on users. 

The project team is developing a model that will represent these practices and how they change, as people interact with each other. The approach, agent-based modelling, represents decisions of individual cycle commuters (agents) who learn from and influence each other and their environments. An agent will only cycle to work if she/he thinks she has enough abilities and stuff to cycle, and on balance cycling has positive meanings for him or her. The stuff, skills and meanings that make up the practice of cycling will vary from place to place.

The project will then explore the medium term impacts* of policies, such as building cycle paths or providing cycle training, as they affect the stuff and skills people think are necessary or as they change the meanings associated with cycling. The impact is then played out through the social networks. For example, improving infrastructure might reduce the skills needed to cycle meaning a wider range of people feel able to cycle. Other people then see these different kinds of people cycling or hear about their experiences, changing the meanings of cycling.

* "What happens if?"

How do we make other researchers be aware of the skills that operational research might contribute to their programmes?  

I followed links from the project's webpage to find some splendid maps of transport in the UK, and - nothing to do with O.R. - interesting and amusing maps of London. 

Thursday, 4 December 2014

A change in UK stamp duty

Earlier this year, I posted about the step function tax on buying a house in the UK.  (See here)  The media referred to it as a "block" tax, but mathematicians would tend to think of it as a discontinuous step function on the integer line.

Happily, it was announced that this tax would cease from 00:01 today, to be replaced by a piecewise linear tax on the cost of a house.  So, instead of a tax on the whole price of a house, which meant that the tax on  a £250,000 house was £2500, and if the property costs one pound more, £250,001, the tax was  £7500.03p, there are a series of thresholds, where the tax rate changes, but only for the price in excess of that threshold.

I don't think that the government reads my blogs, but numerous other people have protested at the step function tax regime.  So I think that it is their influence which has swayed the government - that, and the prospect of an election in May 2015.  As this change was announced yesterday, today's media are full of reports of the effect.  One could plot the tax (stamp duty) paid as the dependent variable against house price under the old and new regimes, and find where the lines cross, but most of the media have simply opted to say that if the house costs less than £937,500, the tax will now be less than under the old scheme.  Well over 95% of houses in the UK sell for under that price, so lots of people will rejoice. 

There is an online calculator of stamp duty here.

I referred to the earlier scheme as a bit of game theory.  That no longer applies to the same extent.