Christmas 2015: Advent calendar of research

In the run up to Christmas I have been posting each day that is (loosely) related to Research and Knowledge Exchange, and is also Christmas related.

I thought it worthwhile just summarsing them here so that you can take a look at them from from one easily accessible place.

  1. Deck the halls with research stories
  2. The Christmas Present Problem: It’s Hard – NP-Hard
  3. Packing Santa’s Sleigh
  4. How will Santa deliver all those presents this Christmas?
  5. The 12 days of Pascal’s triangular Christmas
  6. Brian Cox: Can Santa travel faster than the speed of light?
  7. Five tricks retailers will use to make you shop this Christmas
  8. Problems with your wi-fi? It could be your Christmas lights!
  9. Santa is really a Travelling Salesman
  10. How do Christmas TV adverts keep your attention
  11. Have a go at solving this Christmas cryptographic problem
  12. How does electricity usage change on Christmas day?
  13. Is your oven big enough for the turkey
  14. How will (retail) Christmas compare to 2014?
  15. Should shops open on Christmas day?
  16. Could your Christmas decorations be a hazard to planes?
  17. How Christmas lights helped guerrillas put down their guns
  18. Program your own Christmas Tree
  19. Festive spices and their intoxicating history
  20. What makes a Christmas gift good?
  21. The appeal of the Christmas song
  22. Buying Christmas presents is a real dilemma
  23. Wisdom of the Crowds at the Graduate School Christmas Party
  24. Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks

What is Operations Research?

This post was originally posted on a University of Nottingham blog.


What is Operations Research (OR)?

The terms Operations Research (American term) and Operational Research (European term) are used interchangeably. The discipline is also referred to as:

  • Management Science (most often used in a Business Management sense)
  • Decision Science (less frequently used, but is used most often when statistics are involved)
  • Analytics (a relatively new term but is increasingly used)

Operations Research has close links with Mathematics and Computer Science. It draws on many areas to solve the various problems that it is presented with. Included in these are

  • Optimization (drawing on mathematical programming and and areas such as Linear Programming)
  • Modelling
  • Simulation
  • Heuristics
  • Meta-heuristics
  • Hyper-heuristics
  • Evolutionary Computation
  • Game Theory
  • Statistics

 

A Traveling Salesman Problem solution for USA (Figure credit: David Applegate, Robert Bixby, Vasek Chvatal and William Cook)
A Traveling Salesman Problem solution for USA (Figure credit: David Applegate, Robert Bixby, Vasek Chvatal and William Cook)

The essence of Operations Research is to provide (ideally) optimal, or near optimal solutions to complex decision problems. Probably, the most well known problem (at least in the scientific arena) is the Traveling Salesman Problem (TSP) which can be described as follows:

A salesman has to visit a number of cities. He can choose which one he starts at, but he must complete his tour at the same city. He must visit every other city exactly once. The aim is to minimize the distance traveled.

Whilst being very easy to describe, the TSP gets very difficult to solve (at least in polynomial time) due to the fact that the number of possible tours grows exponentially with the number of cities (the actual number of tours is n!/2 (we divide by two as a tour in one direction is the same as a tour in the opposite direction)).

Historical Details

Like many things, especially in Computer Science, many of its origins can be traced back to the second world war, necessity being the mother of invention, although some would argue that OR’s roots can be traced back beyond this point. Given the subject, you’d expect that many people would have documented the history of the subject and, indeed, this is the case. I have provided below some sources which the interested reader might want to follow.

  • [1] Gass S.I. and Assad A.A.  An Annotated Timeline of Operations Research: An Informal History, Springer. ISBN-10: 1402081162, ISBN-13: 978-1402081163
  • [2] Historical Origins of Operations Research, http://en.wikipedia.org/wiki/Operations_research#Historical_origins, last accessed 2nd Mar 2013
  • [3] Gass, S. I., A.A. Assad. History of operations research. J. Geunes, ed. INFORMS TutORials in Operations Research, Vol. 8. INFORMS, Hanover, MD, pp. 1–14

Why is OR so hard?

The type of combinatorial explosion we see in problems such as the TSP often underpins the problems that we face in OR. In fact, the problems where is is easy to verify (i.e. in polynomial time) if a solution is correct but to find the optimal solution cannot be done (we suspect) in polynomial time is often at the heart of the problems we are trying to solve in OR.

These problems are NP-Complete. That is, we can easily verify a solution is correct (given a TSP solution, we can easily add up the distances to verify that the solution we have been given is correct) but we do not know of a polynomial time algorithm that is guaranteed to return an optimal solution. Indeed, proving P=NP (or not) is one of the Millenium Problems and if you are able to do it, you will receive a prize of $1M USD.

There are some common problems that you will often come across in OR. We have already mentioned the TSP.

The Vehicle Routing Problem!
The Vehicle Routing Problem!

The Vehicle Routing Problem (VRP) is another classic OR problem. As the name suggests, this problem is about scheduling deliveries for vehicles. The classic version is the Capacitated Vehicle Routing Problem (where we minimize total distance traveled, but have to respect vehicle capacities) but there are many variants, such as VRPTW (Vehicle Routing with Time Windows), where deliveries have to be made at certain times. In fact, VRP and TSP are very closely related.

Another classic problem is graph coloring. That is, given a graph with various connections between the nodes you have to try and color the nodes, using as few colors as possible, such that no nodes which are connected have the same color. This problem has an obvious application is coloring maps but you might be surprised to know that it underpins many (many, many) other problems. As an example, university examination timetabling (i.e. scheduling the exams for our students) can be modeled (and solved) as a graph coloring problem. There are almost an infinite number of problems that can be modeled as a graph coloring problem.

Second to the TSP (and this is debatable, it might be first), with respect to the number of papers written, machine/job shop scheduling problem. This problem, in its simplest form, looks at scheduling factories.

Given a number of machines, and a number of processes that have to be gone through to produce a product, what is the best way to utilize the machine(s) to maximize the throughput?

Graph Colouring Problem
Graph Colouring Problem

Like the graph coloring problem, Job Shop Scheduling (JSP) and Flow Shop Scheduling (FSP) can be used to represent many other problems, that are about as far away from the factory floor as you can imagine (how about having telescope(s) in space and trying to schedule their usage for various scientists).

Methodologies

If we could prove that P=NP (which most people think unlikely) then we would be able to find the optimal solution to many of the important problems in OR. That is, we would have a polynomial time algorithm that would give us an optimal solution in a reasonable time. Of course, it might still take a long time but this better than an exponential time algorithm that might take millions of years to return the optimal solution, even on the fastest computers. In fact, there are many problems (or many problems of sufficient size) where we would have only considered a small number of the possible solutions even if we started the algorithm when the dinosaurs were roaming the earth.

However, there are sophisticated algorithms (such as linear programming) that are increasingly able to solve moderately sized problems to optimality.

When these fail (or we find it difficult to model the problem in sufficient detail to use a mathematical programming approach) we tend to use either heuristics, meta-heuristics, hyper-heuristics  or evolutionary computation.

The definition of these is not formal (in that, we could argue where they blur at the edges) but:

  • Heuristics tend to be one pass algorithms and are quite quick.
  • Meta-heuristics are based on phenomena seen in the real world. Things like tabu search (based on memory) and simulated annealing (based on the way we cool metal).
  • Hyper-heuristics are a development of meta-heuristics (although their roots, strangely, can be traced back to before the term meta-heuristics was coined). They are based on the idea of exploring the heuristic space, rather than searching the solution space directly.
  • Evolutionary Computation are algorithms that are based on Darwin’s principles of natural evolution (survival of the fittest) where we have a population of solutions which compete against each other for survival. Common algorithms in this domain include genetic algorithms, genetic programming, honey-bee mating algorithms and particle swam optimisation.

 

Where do we publish?

If you are looking for journals that you might want to consider publishing in then Thomas Reuters, Web of Knowledge, Journal Citation Reports has a specific category for Operations Research & Management Science. For the 2011 journal rankings, this category contained 77 journals. Of course, not all of them will be suitable for a given piece of research but these 77 journals all most (if not all) areas of Operations Research.

 

Want to know more?

There are too many resources to list here, and a serch on a bibliographic search engine such as Science Direct is likley to throw up more references than you would imagine.

But, youtube has a god set of videos where you can Learn About OR.

A couple of videos that caught my eye are OR in Sport and OR in Transport

 

About the author

Graham Kendall is a Professor of Computer Science who works in the Automated Scheduling, Optimisation and Planning Research Group (ASAP). He is a Fellow of the OR Society, as well as an Associate Editor of the Journal of Operational Research Society (in addition to several other journals). He has published widely in Operations Research, as well as other areas. His publications can be seen here.

He has over 30 years experience in OR, both in industry and academia.

Graham is currently based on the University of Nottingham’s Malaysia Campus (UNMC) where he is the Vice-Provost of Research and Knowledge Transfer.

Contact details:

 

References

[1] Gass S.I. and Assad A.A. (Author) An Annotated Timeline of Operations Research: An Informal History, Springer. ISBN-10: 1402081162, ISBN-13: 978-1402081163

[2] Historical Origins of Operations Research, http://en.wikipedia.org/wiki/Operations_research#Historical_origins, last accessed 2nd Mar 2013

[3] Gass, S. I., A.A. Assad. History of operations research. J. Geunes, ed. INFORMS TutORials in Operations Research, Vol. 8. INFORMS, Hanover, MD, pp. 1–14

 

General Algebraic Modeling System (GAMS)

Yesterday (5th July 2009) I attended a workshop run by GAMS (run as part of the EURO 2009 conference – see previous post). They provide a piece of software called GAMS (General Algebraic Modeling System: http://www.gams.com) which enables an easy way to develop mathematical models and then solve them by calling various solvers (such as CPLEX, COIN-OR etc.).

I had heard of GAMS before, but had never really looked into it, played with it or talked to anybody who had used it.

I realise that the workshop was really a sales pitch but from what I saw it was very good.

You can download the software and try it (on small models) and this is something that I will be doing in the next couple of weeks. I’ll report how I get on.

EURO 2009 Conference


I am at the EURO conference at the moment (see http://www.euro-2009.de) (the picture was taken during the opening ceremony).

This is an annual conference for the European Operational Research Societies. This year it has attracted around 2000 delegates, which was a lot more than we had expected (I know as I am on the main Program Committee and have been actively involved in planning and organising the conference, although I have not worked anything like as hard as some people I could mention – but won’t mention them by name for fear of embarassing them).

As the conference progresses I’lll report on anything that grabs my interest/attention.

Operational or Operations Research?

Some of my research is carried out in the area of Operations Research. This term is actually the American version. The English version is Operational Research and (although being biased), I believe that this is the correct version, bearing in mind that Operational Research was founded in England (around the time of the Second World War).

You will find the distinction between these two terms no more apparent than in the naming of academic journals. The oldest OR journal in the world is called Journal of the Operational Research Society (JORS). Another journal is called European Journal of Operational Research (EJOR) .
The journals published in America have titles such as Operations Research.