Research Reflections

Blog moved

2010-12-19T19:43:00.001Z

I have decided to move this blog to my own domain. All the old posts will be there, along with any future posts.

You can find the new blog at:

http://graham-kendall.com/blog/

PATAT 2010: Multi-objective Sports (Football) Scheduling

2010-08-24T21:36:00.021+01:00

At the recent PATAT (8th International Conference on the Practice and Theory of Automated Timetabling) conference I was fortunate enough to be invited to give a plenary presentation.

My talk focussed on sports scheduling. Indeed, the title was "Scheduling Football (Soccer) Fixtures: Progress Made to Date and Future Challenges". I focussed on the conflicting objectives when trying to minimise travel distances, whilst also trying to reduce pair clashes (which can be considered as local derbies for the sake of this discussion).

This is a classic case of a multi-objective problem where minimising one objective causes the other to increase and vice versa. It is not (usually) possible to minimise both objectives, instead you are looking for a trade off. These are plotted on a pareto front where a user would then decide which trade off solution is the best.

In the plenary talk, I showed that it was possible to reduce both the distance and the pair clashes such that (sometimes) the distance did not significantly increase. This is a potentially useful result as it means that supporters do not have to travel any further (statistically) and the policing costs are reduced as they do not have to police so many local derbies.

I should say that this result is only work in progress at the moment in that it has not been verified by the football authorites or the police, but I would hope that it would be of interest to them.

In the same talk, I also discussed how I collected the data for this work (which essentially is the various distances between football clubs). This involved using Google maps and Multimap APIs. I'll talk about this in the next blog. I'll also provide a link to the paper (as I don't have it to hand at the moment). But, if you are interested the reference is:

Kendall G., McCollum B., Cruz F. and McMullan P. (2010) Scheduling English Football Fixtures: Consideration of Two Conflicting Objectives. In proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2010), 11-13 August 2010, Queen’s University, Belfast, UK, pp 1-15

2010 Pac-Man Competition at CIG 2010

2010-08-22T18:45:00.000+01:00

Last week I attended the IEEE Conference on Computational Intelligence and Games (CIG 2010). This conference (it was actually a symposium in the early days) was started by Simon Lucas and myself in 2005. I also co-chaired the conference with Susil Louis in 2006. The conference has been run every year since 2005, with the lastest one being held in Copenhagen, chaired by Georgios N. Yannakakis and Julian Togelius.

This year I had a paper that was developed as part of a 2nd Year Group Project (the teams members are shown in the picture).

As part of the Computer Science undergraduate degree at the University of Nottingham, second year students are assigned to groups and given a software engineering task to work on. Last year, I set the following:

Your task is to write a computer program that can play the game of Pacman, without human intervention. This is a challenging task and, without some support would, perhaps, be impossible for a second year group project. However, this task has been an ongoing competition for a number of years and there is lots of information/support available, as well as examples as to what can be achieved.

Your starting point should be the web pages of Professor Simon Lucas at the University of Essex, who organises the competition. Therefore, take a look at this web page. This is ESSENTIAL reading and you should study this page (and associated links) before our first meeting. You should also make regular visits to the page as I know that Professor Lucas is planning to update it on a regular basis. Using the information on this web site you should be able to get a system up and running quite quickly and then you have to develop your own algorithms to produce the best automated player that you can.

I would expect you to carry out (at least) the following tasks, with the first two feeding directly into your literature review:

By referencing the competition entries, find out what algorithms appear to have worked well in the past.

Investigate and draw up a set of algorithms that you think could be used as a Pacman Controller. These algorithms might be based on various criteria such as those identified in 1 (above), "Manhattan Distance", "Straight Line Distance", "Trying to eat the ghosts", "Trying to avoid the ghosts", "Trying to eat the fruit", "Maximising the score, whilst minimising your chances of being eaten", etc. There is probably not one good overall strategy and you might consider changing strategies as the game state changes. You might also want to consider how much you plan ahead and how much you just make quick decisions, given that this is a real time game.

As part of the supplied toolkit you are provided with screen capture software (and a window showing you a representation of the captured game state), the game screen itself and a small screen showing the current direction of the Pacman character. As part of this project, I would also like you to develop another GUI element which enables you to select from amongst the algorithms that you have implemented, keeps track of their high score, enables you to choose how "adventurous" the player will be, enables you to mix/match the algorithms etc. Part of the project will be to design this GUI element, deciding what role it should play in the overall software architecture. You can then use this captured information as a basis for the analysis in your final dissertation.

Implement the int move(GameState gs) that is provided in the sample toolkit in order to test out the various game playing algorithms that you have investigated in points 1 and 2 above.

You might want to look at look at the YouTube Video for the competition entry from WCCI 2008 (google "YouTube WCCI pacman"). To give you some indication of the current state of the art, the most recent competition (run in Milan in August 2009), the winning entry achieved a score over 30,000 and reached (from memory) level 5 (it might have been level 4). If you can get anywhere near that you will be doing very well.

The project group did so well that the team not only won the prize for the best project but the School also agreed to fund one of the team members to attend the conference to enter the competition. As a result we also wrote a paper which was a accepted at the conference and the student presented it (a big undertaking for an undergraduate student, but he did very well).

In the competition, we came a VERY respectable third. In second place were last years winners. In first place was a new team who used an Ant Colony based method.

The difference between the top three entries was not that large, with the winning entry getting about 21,000 points.

In fact, during pre-competition testing our team achieved scores of over 22,000 on many occasions, with our best ever score being just over 30,000 (I am sure that the other entrants also have similar sob stories to tell :-)).

If you are interested the reference for our paper is.

Bell N., Fang X., Hughes R., Kendall G., OReilly E. and Qiu S. (2010) Ghost Direction Detection and other Innovations for Ms. Pac-Man. In proceedings of the the 2010 IEEE Conference on Computational Intelligence and Games (CIG'10), 18-21 Aug 2010, Copenhagen, Denmark, pp 465-472

It can be downloaded from here.

The references for the first and second placed entries are.

Emilio M., Moises M., Gustavo R. and Yago S. (2010) Pac-mAnt: Optimization Based on Ant Colonies Applied to Developing an Agent for Ms. Pac-Man. In proceedings of the the 2010 IEEE Conference on Computational Intelligence and Games (CIG'10), 18-21 Aug 2010, Copenhagen, Denmark, pp 458-464
Thawonmas R. and Ashida T. (2010 Evolution Strategy for Optimizing Parameters in Ms Pac-Man Controller ICE Pambush 3. In proceedings of the the 2010 IEEE Conference on Computational Intelligence and Games (CIG'10), 18-21 Aug 2010, Copenhagen, Denmark, pp 235-240

More details about the Pac-Man competition can be found at Simon Lucas' Pac-Man page.

Summer Conferences

2010-08-22T11:43:00.005+01:00

It's been a busy couple of weeks as I have been attending two scientific conferences. Last week I was at the PATAT (Practise and Theory of Automated Timetabling) conference in Belfast and I have just returned from the IEEE Conference on Computational Inetlligence in Games (CIG 2010) in Copenhagen.

Both conferences consider very different areas (not surprisingly one is about timetabling and the other is about computer games).

I'll report more on each conference in blogs in the next few days.

SlideShare

2010-06-18T23:39:00.008+01:00

It was only recently that I came across slideshare. It is one of those ideas (I suppose a bit like YouTube) that you have heard about, but you don't really know how useful it is until you have used it.
In essence, slideshare is a very simple concept (like most of the very succesful internet applications). It enables people to upload presentations that other people can access.
Like YouTube and Wikipedia you can spend a lot of time looking at subjects that you never really thought you had an interest in. It is also a convinient place to store your own presentations in case your laptop crashes, your USB breaks etc. etc.
So far, I have only uploaded a couple of presentations but I hope to add to that in the near future.

INFORMS 2010: Buenos Aires

2010-06-18T23:19:00.007+01:00

I have just returned (well returning actually - I am at the airport) from the INFORMS conference in Buenos Aires. In fact, we stayed on a few days and a very good colleague of mine is Argentinian and we toured round the North of the country. The highlight, undoubtedly, being Iguazu Falls. They are spectacular (see picture for just a small part of the falls).

This is only the second INFORMS conference I have been two (the previous one was in Puerto Rico in 2007). I find them very good.
The tutorials are especially useful and the one by Mike Trick on Benders Approach for Hard Problems was particularly beneficial. At the time of writing, the powerpoint slides for this presentation we available from Mike's web site (PPTX and PPT). If I can ever get my head around the ideas underlying Bender's approach, I can see this being a very useful technique for a variety of problems.

Geocoding: Trials and Tribulations

2009-11-17T18:01:00.009Z

For the past few months I have had a small project on the back burner to try and make geocoding easier.

The motivation can be traced back to the data collection I had to do for the data I needed for my research on minimising the amount of travelling that football supporters have to do over the Christmas holiday period (if you are interested in this see this link).

When I collected the original data I used greenflag.com. I could have used theaa.com or rac.co.uk. The problem with the latter two is that you had to type in the to/from postcode into a web form. At least with greenflag.com the postcodes were part of the URL so it was a simple case of generating the correct URLs (which I did with Excel), uploading to a web site and then clicking on each link.

But this was a long winded process in that I had to a) click on every to/from link (about 900) and then scroll the screen to collect the actual mileage. That takes a long time and as I have done this for seven seasons I thought it was about time to try and automate the process.

The obvious candidate was to use Google maps. When I started the sports scheduling research Google maps did not provide the facilities that I required. Things have moved on since then and Google maps now has an API which makes this type of automation a possibility.

So, over the last few months I have been investigating how to use Google maps, which does not come without its problems. For example, it is not that accurate when using UK postcodes, you have to learn the API, ideally you need to geocode UK postcodes to longitude and latitude etc.

I think that I have now resolved most of these problems and am just doing the last stages of test. So, more soon.

Vehicle Routing Datasets

2009-10-25T18:41:00.005Z

For reasons which will become apparent in the fullness of time I have recently been trying to track down all the vehicle routing datasets that are out there; specifically the Capacitated Vehicle Routing Problem (CVRP).

I know that the problem was introduced in 1959 (with small instances being made available in that paper¹) and I think I have tracked down the majority of datasets since then, but if anybody out there has a list (or a reference to a list) it would be helpful.

¹ Dantzig, G.B., Ramser, J.H., 1959. The truck dispatching problem. Management Science 6, 80–91

Conjuring Trick: Revealed

2009-10-03T22:25:00.003+01:00

Thank you for all the feedback to my last blog, both personally and through facebook.

The answer is that information is communicated via the four remaining cards. It is not obvious how it is done but take a look at the article by Colm Mulcahy, which explains all.

If you are interested in these sort of puzzles I fond this one at Gurmeet Singh's blog. It is an excellent blog and contains many other puzzles like this.

Conjuring Trick

2009-10-03T21:20:00.010+01:00

I recently came across another blog (I'll point you to that blog at a later date), which has a number of puzzles on it. One, in particular caught my eye (probably because of a long time fascination with conjuring).

The trick works as follows.

A volunteer chooses five cards from a normal pack of cards. You take the five cards, look at them and return one of the cards to the volunteer. The other four cards are handed to another volunteer. You leave the room and a colleague enters. The second volunteer reads out the cards you gave them and your colleague names the card that the first volunteer is holding.

How is this done (post your ideas)?

If you want to know, click the "interesting" box at the bottom of this blog and, if there is enough interest, I'll point you to the original blog and the answer (unless somebody already knows, of course).

Claude Shannon, Edward Thorp, Roulette and Blackjack

2009-09-18T17:09:00.008+01:00

I guess many people have heard of Claude Shannon (information theory/entropy).

Perhaps not as many people have also heard of Edward Thorpe? I have known of his work for many years as he was chiefly responsible for making the gambling industry change the rules of blackjack^1,2. Not only did he develop something called basic strategy (the best strategy to minimise the house edge) but he also developed card counting (keeping track of certain cards to maximise the chances of winning). Due to Thorp's work (and also earlier work by Baldwin et al.³) casinos started using more than one deck and shuffling before the end of the shoe (the implement used to hold the cards) so as to minimise the effect of card counters (card counting is not actually illegal, but casinos don't like it and can ask you to leave).

So, I had known of the work of both Shannon and Thorp but I never realised that they had worked together on roulette. I found this gem in a book I am currently reading⁴. They worked together on a device to predict what segment of the wheel the ball would land in. I'm not sure of the outcome of their work yet, as I am still reading the book. But, the point is, I had never associated these two scientists as working together; which I found interesting.

References
1: Thorp E.O. (1961) A Favorable Strategy for Twenty-One. Proceedings of the National Academy of Sciences, 47:110-112

2: Thorp E.O. (1966) Beat the Dealer: A Winning Strategy for the Game of Twenty-One. New York: Random House (revised edition of 1962 book)

3: Baldwin R.R., Cantey W.E., Maisel H. and McDermott J.P. (1956) The Optimum Strategy in Blackjack. Journal of the American Statistical Association, 51:429-439

4: Poundstone W. (2005) Fortune's Formula: The Untold Story of the Scientific Betting System that Beat the Casinos and Well Street, Hill and Wang

P vs NP

2009-09-12T20:03:00.005+01:00

I have just read an excellent article in the latest issue of Communications of the ACM.

Fortnow L. (2009) The Status of the P versus NP Problem Communications of the ACM, 52(9):78-86 (doi:10.1145/1562164.1562186)

The article not only describes what the P=NP problem is (and it is one of the best non-technical descriptions I have seen) but also provides some of the research directions that might lead to a proof that P=NP (or, more likely (in my view - and many others), that P≠NP).

If you are any sort of computer scientist, then I would urge you to take a look at this article.

You can stay up to date with this area on the author's blog (http://blog.computationalcomplexity.org)

The 2009 IEEE Symposium on Computational Intelligence and Games: Report

2009-09-11T05:33:00.013+01:00

I have just spent the last week at the 2009 IEEE Symposium on Computation Intelligence and Games in Milan (see last post).

It has been an excellent week both from a scientific point of view and from a networking point of view (I have even added a few new facebook friends as a result of the symposium).

There really is some fantastic work going on around the world. The plenaries and tutorials showed just some of this. The work being done by people such as Ken Stanley, Michael Mateas, Yngvi Björnsson, David Stern (Microsoft Research), Stefano Lecchi (Milestone) and James Vaccaro is very impressive and the products they produce have the commercial sector (some of which work in this area anyway) really taking notice.

Of course, there is other excellent work being done, by a great many other people, and to list them all would mean listing most of the presentations given at the conference. So, although I have highlighted just a few presentations, it does not detract from all the other work being done in this area. Indeed, the newly established IEEE Transactions journal in this area is a testament to how bouyant the area is.

Another highlight at CIG'09 was the competitions. This year they really seem to have come of age. In previous years (at both CIG and other conference) the competitions were very popular, and well received, but it just has a slightly different feel this time around.

At this year's conference there were four competitions:

Screen-Capture Ms Pac-Man. There is also a new competition where you evolve the ghosts as well as control Pac-Man being planned. This should be up and running soon.
The 2K Bot Prize
The Defcon AI Competition
Mario AI Competition
The Simulated Car Racing Competition

I will try and blog about each one in the future.

We hope that the presentations from the symposium will be available to view soon. They were all recorded but there are some copyright issues to resolve.

The symposium will be run again in 2010. The venue has just about been decided but it needs to be rubber stamped so I cannot say on a public forum where it will be.

The 2009 IEEE Symposium on Computational Intelligence and Games

2009-09-06T17:19:00.014+01:00

I have just arrived in Milan for the 2009 CIG (Computational Intelligence and Games) conference. This was a conference that Simon Lucas and I started in 2005. Simon is now editor-in-chief of the IEEE Transactions on Computational Intelligence and Artificial Intelligence in Games. The 2005 conference, I believe, was partly responsible for paving the way to enabling this journal to be established. I am fortunate enough to serve as an Associate Editor for the journal.

As I said above, the first conference (actually it's a symposium, as the correct title is The IEEE Symposium on Computational Intelligence and Games) was held in 2005 in Essex (UK). The original plan was to hold the symposium every two years, but it was so successful that we decided to hold it again in 2006. This time, Sushil Louis and I chaired it. It was held at the University of Reno in Nevada.

In 2007 it was held in Hawaii, as part of the then newly formed Computational Intelligence Symposium Series of conferences (CISS). Simon, again chaired this symposium, along with Sung-Bae Cho and Alan Blair. Actually, at the 2007 CISS, I chaired the associated scheduling conference (Computational Intelligence in Scheduling (CISched).

In 2008, CIG was held in Perth, Australia, chaired by my good friends Luigi Barone and Phil Hingston.

The sympsium has now moved to Milan (chaired by Pier Luca Lanzi). It has certainly done the rounds (Essex, Reno, Hawaii, Perth and Milan) and, having been to all of them, I know from first hand experience that it is going from strength to strength.

Looking at this years program it promises to be a very interesting week. If you have an interest in computational intelligence or games, take a look at http://www.ieee-cig.org/.

Random Number Generation

2009-08-28T17:44:00.006+01:00

We all know that computer generated random numbers are not really random at all, but just pseudo-random. And I know that is a lot of discussion about how best to generate random numbers.

To be honest, I have not taken much notice of this in all the programming that I have done but today I found out that it is important.

Without going into the (boring) details, I have been generating a random number that is either 1 or 2 - but I generate quite a few very quickly.

For anybody that is interested the code is something like

r = rand() % n +1 [where n is the range you are interested in]

The problem is, I was returning the same number every time. Only very occasionally did I get the odd difference.

If I increased the range (say generating numbers between 1 and 20), this made no difference (I always got the same number).

However, if I put in a delay between each call to rand(), this "solved" the problem, but this is not a good solution.

Doing some reading around the subject, I think it is to do with the low/high order bits when generating the random numbers.

But that does not help me generate a decent distribution when making very frequent calls to rand().

I seem to recall that there is a C++ class called RNG (Random Number Generator) available and I am sure that Numerical Recipes in C will have something to say on the issue, but I need to look into these.

Football Prediction: A decision to be made

2009-08-26T19:03:00.017+01:00

Today I have been working on my research that is investigating if it is possible to predict the outcome of football matches. The measure I will eventually use, to see if the predictions can be considered successful, will include if it can make money at the bookmakers, if it it more successful than other tipsters etc.

One of the functions I have in my system is to be able to generate the league table for a given date. That is, taking into account the fixtures played to date, generate the league table for any point in the season.

I believe that my function is working correctly and today I was carrying out some tests to see if the league tables I generated were:

Correct at the end of the season. That is, taking into account every match played, is my input data correct and does my algorithm process that data correctly.
Does my algorithm, given a date, generate the correct table for that point in the season.

I initially thought that point 2 would be very time consuming to check but I found a very useful web site. http://www.statto.com is not only a very useful web site (for all sorts of reasons) but one of the facilities it offers is to generate a league table for a particular point in the season.

When doing my checks (and there are still a lot more to do), I have found some problems where my generated tables are not correct. This is almost certainly down to my inputting the results incorrectly, so I need to check all those.

However, my checks also highlighted another problem. Actually, I knew this was something that I needed to address but I had not really thought it through.

The problem arises when teams having points taken away. I knew that this happened and I had yet to include it in my system so I was expecting the tables not to match exactly.

However, I had assumed that the points were deducted at the start of the season but this does not seem to be the case. It appears that the points can be deducted at any time in the season.
This is not too much of an issue. It just makes the programming more complex than I had hoped.

The real issue is what do I do when a team has had points deducted?

Let me give you an example. A team has won 3 games and drawn 2. That means that they have received 11 points (you get 3 points for a win and 1 point or a draw). But, if they have had 10 points deducted then they will only have 1 point. This obviously affects their league position. If I am using the league position as one of the contributory factors in my predictive model, is this fair - or should I ignore the points deduction for the purposes of prediction?
On the other hand, their league position, with the points deduction, may affect the way they play, and could be a factor in the prediction.

I'm not quite sure what I am going to do yet.

How General is Your Algorithm?

2009-08-25T06:00:00.001+01:00

One of the research issues that has been tackled for at least 50 years is attempting to develop algorithms that are better than other algorithms on a certain type of problem (for example, vehicle routing, traveling salesman problem etc.). And it is easy to judge if you have a better algorithm. You run it on a benchmark problem from the literature and if yours is better you write a paper claiming as much. Of course, you should also show statistical significance, robustness of your approach, provide some discussion etc.

There has been some recent work where the goal is to develop an algorithm that works well on many different problem domains. This is a challenging objective as even small changes to a problem instance can make an algorithm that used to perform well, now perform poorly. See a previous blog where I gave a simple example.

So, if we have an algorithm that works well on a particular problem instance, but a small change to the problem renders it useless (or at least worse than it was) then imagine the challenge in trying to get an algorithm to work on a totally different domain without any changes being made to the algorithm. To make it clearer what we are trying to achieve, let's say you have an algorithm that works well on a Vehicle Routing Problem. Is it possible, without any changes to that algorithm, to get it to work well on a (say) a staff rostering problem?

This is one (if not THE) goal of hyper-heuristics. In a future blog, I'll give some more concrete examples, but the challenge of developing more general search algorithms is an area that is attracting quite a lot of interest at the moment.

Football Fixture Scheduling: Are all clashes equal?

2009-08-24T06:00:00.000+01:00

In a paper published in JORS:

Kendall G. (2008) Scheduling English Football Fixtures Over Holiday Periods. Journal of the Operational Research Society, 59(6), pages 743-755 (doi:10.1057/palgrave.jors.2602382)

I investigated if it was possible to produce superior fixtures for the Christmas/New Year Period with respect to minimising the distance that is traveled by supporters on two particular days.

One of the issues that the underlying model had to capture was that certain teams could not play at home on the same day. For example:

Manchester United and Manchester City
Liverpool, Everton and Tranmere
Chelsea and Fulham
Colchester, Ipswich and Norwich
etc.

Teams that are paired in this way are called pairs (even though there might be more than two teams involved). A problem arises as it is not possible to eliminate all the pair clashes. That is, some paired teams have to play at home on the same day.

In the JORS paper, all the pair clashes were treated equally (e.g. Manchester United and Manchester City playing at home on the same day is not considered any more, or any less, important than Liverpool and Tranmere playing at home on the same day).

I am not sure if any given pair clash should be considered more (or less) important than any other, but I suspect so.

One of the things I plan to do is analyse the past few seasons fixtures and gauge if certain pair clashes are allowed more than others. Then I will use this evidence to weight the clashes during the process of searching for a good set of fixtures.

Examination Timetabling: Carter Dataset

2009-08-23T10:15:00.001+01:00

In a previous blog I mentioned two examination timetabling datasets. The Carter dataset and the ITC (International Timetabling Competition) dataset. I thought it would be worthwhile describing these datasets for anybody that is interested, as they are the datasets that everybody in the scientific community uses in order to test any proposed algorithms.
In this blog, I'll discuss the Carter dataset and save the discussion of the ITC datasets for a later blog.

The Carter dataset were introduced in 1996 by Carter, Laporte and Lee in a paper published in the Journal of the Operational Research Society.

M.W. Carter, G. Laporte, S. Lee, (1996) Examination timetabling: Algorithmic strategies and applications, Journal of the Operational Research Society 47(3), 373 – 383 (doi:10.1057/jors.1996.37)

In this paper they made the observation that "One of the major drawbacks of most articles in the timetabling literature is that testing is limited to randomly generated problems and perhaps to one practical example."

They go on to say "In this study, in addition to running randomly generated problems, we carried out a comparison of thirteen unconstrained real-life examples."

The thirteen problems were taken from Canadian institutions (10), the London School of Economics (1), King Fahd University of Petroleum and Minerals (1) and Purdue University (1).

One of the main characteristics of these problems is that the objective we are trying to minimise is quite simple. We are trying to ensure that the spread of examinations for a given student is as wide as possible. That is, if a student is sitting one exam followed immediately by another, the penalty is greater than if the student has an exam, a rest period, and then another examination. If the student has two rest periods, this is even better, and so on, until there are five rest periods. At this point anything greater than or equal to five rest periods incurs no penalty.

The formulation for the Carter dataset does not capture some aspects such as:

The room capacities for the examination rooms (which is why is it considered an uncapacitated problem).
The fact that two consecutive examinations, which are on different days, is better than two consecutive examinations on the same day. Both of these scenarios would give the same penalty cost using the usual objective function used in the Carter dataset, even though the student would have the evening (indeed, all night) to revise, as opposed to no time at all if the examinations were truly consecutive. Indeed, each instance in the dataset just has a number of timeslots. There is concept of different days.

However, capturing all the complexities inherent in the real world was not the point of the 1996 paper.
The point was, for the first time, Carter et al. provided the scientific community with a standard set of problems and these thirteen instances have been the bedrock of examination timetabling research since that time.

If you decide to use this dataset you should be aware that there was some confusion about five of the instances as there were two different versions available. The recent paper by Qu et al. provides the definitive source for the variants.

R. Qu, E. K. Burke, B. McCollum, L. T. G. Merlot and S. Y. Lee (2009) A survey of search methodologies and automated system development for examination timetabling, 12(1):55-89 (doi:10.1007/s10951-008-0077-5)

Non-symmetric Vehicle Routing

2009-08-21T22:05:00.002+01:00

For a while I have been thinking about Vehicle Routing (you can see a previous blog here). Most of the problems I come across (though I am happy to be corrected) assume that distances are symmetric. That is, the distance between location i and location j is the same as the distance between location j and location i. I know that there has been some work done on the asymmetric Traveling Salesman Problem, but I am not aware that the asymmetric VRP has received a similar amount of research attention.

It is not always the case, particularly in real world problems, that the distances are symmetric. For example, the driving distance between two locations might be different depending on the direction you are traveling.
I guess there are many reasons why symmetric distances are used. For example:

If we are storing the coordinates of each location we can calculate the distances algorithmically, as part of the pre-processing to the main optimisation algorithm.
We could ask if it really matters if we work with symmetric distances? Does it really affect the results that much, or make any difference to the conclusions we can draw about the algorithm we are using?

But I have been wondering if there is any mileage (sic) in looking at asymmetric distances, in the context of real world VRPs?

With these questions in mind I have recently (a couple of months back) been looking at Google Maps as a way of being able to collect data. Google actually provide a very nice API (Application Programming Interface) which is quite easy to use and there (as you would imagine) is a lot of information available.

I got to the point where I have a Google Maps application up and running, really just to prove to myself that what I wanted to do was possible. Then I had to abandon it for a while as I had other, more urgent things to do. However, it is still on my mind about the research that is possible and I plan to address some of them in the near future.

Hyper-heuristics: An Ongoing Research Idea

2009-08-20T19:24:00.009+01:00

For the past few months a colleague and I have been putting a day aside every six weeks or so to work on a joint project. This is the first time I have programmed with somebody but its working out well. We each take responsibility for a C++ class and then plug everything together at the end of the day.

The first few days went very well and we got results that were close to the best known, but things have slowed down a bit recently and we have stood back and looked at exactly what we are trying to achieve. The programming today was about redesigning the software framework. We did not quite finish, but we made good progress.

The domain we are tackling is the examination timetabling. We chose this as the data is readily available, there has been a lot of work done in this area already and there are lots of results that we can compare against.
(In case you are interested, we are initially using the Carter datasets. There is more recent dataset known as the ITC (International Timetabling Competition) datasets which we might look at in the future.)

But, the main focus of the research is not to solve examination timetabling problems, but to investigate an idea we had about hyper-heuristics. We are not sure if it is going to work yet (that's the idea of research!) but the outline idea is that we evolve sequences of add/delete heuristics, perhaps in a co-evolutionary environment. That may sound a bit woolly at the moment, and you'd be right as we are still very much in the planning phase. In essence, we are just developing a software development framework that will enable us to test a variety of hypotheses.

So, at the moment, work in progress and more later.

Football Fixture Scheduling: Another Project

2009-08-19T22:26:00.012+01:00

Over the past nine months or so I have been working with a local company who provides an online service to schedule various types of sporting events. They contacted me after seeing my contact details on wikipedia (which was a nice way to be contacted).
The company need to produce double round robin tournaments but they have some factors which are not present in the major English leagues. For example

Teams might share pitches so those two teams cannot play at home on the same day.
There are a number of different leagues and the teams in different leagues might share pitches (see above) but the leagues play in different timeslots. That is, pitches are available in certain timeslots and teams can play in certain timeslots and these are not consistent across divisions.
We want to provide a good spread of games such that repeat fixtures (team i vs team j and team j vs team i) are as far apart as possible.

There followed a series of meetings (at 7:30am for reasons best known to ourselves), which discussed the problem so that we both fully understand the task at hand.

At the moment, I am trying to develop a constructive heuristic and then carry out some additional optimisation with simulated annealing.

It has proven to be a very interesting problem and there is still a lot that I want to do, but I have just about got a constructive heuristic that works (in that it produces a feasible solution).

My focus over the coming week or so (as I have some time to work on the problem) is the following.

Investigate if I can produce a more efficient constructive heuristic. At the moment, it takes many iterations to get a feasible solution and I'd like to do it much more quickly.
Run the local search optimisation (in this case simulated annealing) which will take the feasible solution from the constructive heusristic and try to improve on it. In addition, it will also attempt to spread out the repeat fixtures.
Once I have something that seems worthwhile I want to document the algorithm. This is for the purposes of a potential paper (the holy grail in our world!) and also to discuss the approach with the company.

So, the next couple of weeks should be very interesting (well, at least for me!).

MISTA Conference: Venue for 2011 announced

2009-08-14T23:36:00.007+01:00

MISTA 2009 finished in the time honoured fashion of a social day. On this occasion it was a cruise down the River Liffey, followed by a two hour guided tour around Dublin, ending up at Trinity College Dublin (which, strangley enough is where MISTA 2009 started as it was the first place we visited when looking for a venue for the conference (in the end, we decided against TCD for various reasons)).

But, as the 2009 conference ends, planning for the 2011 conference begins.

So far, the conference has taken place in Nottingham (2003), New York (2005), Paris (2007) and Dublin (2009). At the conference banquet we announced that the 2011 conference will take place in Phoenix, Arizona. The conference will be chaired by John Fowler, Barry McCollm and myself.

Starting to plan two years in advance might seem excessive but we have found the further out you plan, the easier it is.

MISTA Conference: Plenary Talk (David Hine)

2009-08-12T07:14:00.010+01:00

The last plenary at MISTA was given by David Hine. He is a sergeant with the Public Order Unit at New Scotland Yard (in particular Football Intelligence). His talk gave the delegates an overview of the issues and problems he faces in organising resources to police football matches in London, the wider UK and also when fans travel overseas (whether visiting other countries or fans coming to the UK).
He said that he wanted to take us into his world and also take us out of our comfort zone and he certainly did that, with some of the shocking videos that he showed. The feedback I received after his talk is captured by comments such as "an excellent presenter", "one of the best conference talks I have ever seen" and "it really brings home the impact that the schedules have on everybody's life."
I invited Dave to give the talk a few months back (after meeting up with him in London) and I would like to offer my personal thanks to him for taking a couple of days out of his busy schedule (and at the start of the football season) to give the talk to the MISTA audience.

MISTA Conference: Plenary Talk (Edmund Burke)

2009-08-11T16:08:00.005+01:00

The MISTA conference had two plenary talks today (Raymond Kwan - see earlier blog) and Edmund Burke. Edmund's talk was entitled A Comparison of Two Methods for Reducing Take-Off Delay at London Heathrow Airport and focussed on his work (and Jason Atkin and John Greenwood) that investigates scheduling aircraft at Heathrow in preparation for take off.
The picture shows Edmund Burke (foreground) and Jacek Blazewicz (session chair).

MISTA Conference: Plenary Talk (Raymond Kwan)

2009-08-11T13:31:00.011+01:00

Our second plenary talk took place this morning. Raymond Kwan, from The University of Leeds, gave a talk entitled "Case Studies of Successful Train Crew Scheduling."
The talk was based on his spin out company (TrainTRACS) that markets software to UK train operators across the UK and is used to schedule train crews. As well as giving an overview of the problem, his talk discussed how complex the problem is and the methodologies that they use to solve it.
In the picture is Raymond Kwan (foreground) and Barry McCollum (session chair).

MISTA Conference: Plenary Talk (Moshe Dror)

2009-08-10T13:35:00.005+01:00

The MISTA conference is now well underway, after a busy morning. Our first plenary talk was by Prof. Moshe Dror (University of Arizona) and co-authored with George Steiner. His talk was entitled ‘Strong’-‘Weak’ Precedence in Scheduling: Extended Order Implications.
The picture shows Prof. Dror's talk.

Football Scheduling: News Story

2009-08-10T13:25:00.006+01:00

The English football season has just started and, to coincide with the kick off, the Communications Office at The University of Nottingham offered to issue a press release about my work is this area.

This resulted in an interview on BBC Radio Nottingham (broadcast 8th Aug 2009) and a colleague, from another university, sending me a link (thanks Mike) that he had come across.
The story also contains a link to the University of Nottingham press release.

MISTA Conference: Almost There

2009-08-09T22:50:00.000+01:00

The MISTA conference is almost upon us.

It was an early start this morning (3am) in order to get to Dublin on the 06:35 flight out of East Midlands Airport. We were actually in the hotel by 09:00 and, thankfully, they had rooms ready so it was not too bad.

We spent the day getting things ready, as far as we could. The real work will start tomorrow and it looks like being a long day. I think we'll open the registration desk at 07:30 and we'll return from the Guinness Storehouse at around midnight.

In between that, we have a Plenary Talk by Moshe Dror ("‘Strong’-‘Weak’ Precedence in Scheduling: Extended Order Implications"), followed by 36 papers, split into nine sessions (the full program can be downloaded from here).

For me (and this is a personal viewpoint; not talking as the conference chair) the highlight is the Sports Scheduling session as this is a particular interest of mine, as you'll see from my previous blog postings. The papers in this session are:

Mathematical Modeling for Maximising Gate Receipt Problem, Abdul-Hamid N.H., Kendall G. and Sagir M.
A Heuristic for Minimizing Weighted Carry-Over Effects in Round Robin Tournaments, Guedes A.C.B. and Ribeiro C.C.
Soccer Schedules in Europe: An Overview, Goossens D.R. and Spieksma F.C.R.
Round-Robin Sports Scheduling from a Graph Colouring Perspective: A Case Study in Rugby Union Scheduling, Lewis R. and Thompson J.

... but there are many other excellent papers also being presented throughout the day and your preferences will depend largely on your research interests.

MISTA Conference: Program

2009-08-03T20:01:00.002+01:00

With the MISTA conference just a week away (this time next week we'll be in the Guinness Storehouse for the reception) we have just released the scientific program.

The list of papers is available at

http://www.mistaconference.org/2009/programme/index.html

A PDF (more detailed) version can be downloaded from the same page (see the link at the top of the web page)

MISTA Conference: Proceeedings

2009-08-03T19:27:00.007+01:00

I wonder if there is a good (and I mean simple) way to produce conference proceedings?

In a previous post, I was talking about the MISTA conference that I chair and that we were in the process of collecting all the papers and registrations. This is now done and, with the conference just a week away, we are trying to finalise the proceedings.

It could be worse. In 2003 we had hardcopy proceedings so we had to get things sorted out a lot sooner as we had to deliver the proceedings to the printers. At least, with the proceedings on CD, the timescales are not so tight and we are in charge of our own fate. On the downside you effectively have to develop another web site to enable the delegates to access the papers in a variety of ways.

But that is not the main problem (time consuming as it is). The main problem (at least for me) is three-fold

Ensuring that all the papers actually make it to the proceedings and that all the authors and titles are spelt correctly in the contents pages.
Making sure that the contents pages have the correct page numbers on (for reasons I won't go into now, it's important that we have page numbers).
Putting together an accurate author index so that authors can easily find their papers.

I have put together a number of conference proceedings in my time but I have never found a quick, simple and reliable of doing it, other than just taking your time and constantly checking that you have not missed anything.

Any suggestions welcome, for the next time.

Football (Soccer) Prediction: Data Collection (#002)

2009-07-30T18:45:00.000+01:00

If you have read previous versions of this blog you'll know that a) I have an interest in trying to predict football (soccer) matches and b) I am currently developing a system (as a research project) that I hope to get up and running in the next month or so.

What kept me busy for a lot of last season was collecting the data.

Fixtures
The fixtures were easy to collect, being readily available from various sources. As my basic reference guide I used the Sky Sports Yearbook as this is a piece of published work that will be available to future generations. I could have used may of the web sites that are available but as a scientist we don't really like to rely on web sites as they may not stand the test of time. The fact that web sites are not peer reviewed are another factor we also have to consider.

Results
The results are also easy to collect as they are a matter of public record and are reported in the media and, from a research point of view, we can validate them for years to come (e.g. newspapers, next seasons Sky Sports Yearbook etc.)

Bookmakers Odds
One of the other things I wanted to collect was the bookmakers odds. This proved a lot more challenging. There are a couple of problems. As far as I am aware they are not a matter of public record (at least that stand the test of time). Or, to put it another way, can you go and verify what the odds were for a given match at a given time - just by accessing publicly available information? Importantly, if two (or more) people are independently given the same task will they come back with the same answer? And, is it the correct answer anyway?
The second problem is that odds change over time anyway, with the weight of money that has been bet.

Anyway, over the course of last season, I made regular visits to the bookmakers to pick up their fixed odd coupons and I filed them away as evidence of the odds I was using.

Since carrying out the data collection (particularly the odds) I have discovered a couple of interesting other sources. I believe that the Racing Post (which, importantly, is also published as a daily paper, so is a matter of public record) publishes the best odds available on the fixtures for a given day.
I was also pointed to a web site recently (http://www.football-data.co.uk). This is a very good web site that not only has a lot of information but also has at least seven seasons worth of fixtures data including results and odds information from a selection of bookmakers.

I have checked the odds I collected last season against the ones on this web site and they match up, which is encouraging.
It also provides me with more than just last season to carry out initial testing before I use the system in anger on this season.

The downside of the http://www.football-data.co.uk web site is two-fold.

I don't think they will make their data available until a few hours before the kick off time. This might be a problem for the system that I am developing.
The data is still a web site so, from a research point of view, I should not really cite it as the web site may not be available in 1/10/100 years time.

Please don't take this as a criticism of the web site. They have done (and are doing) a fantastic job of collating all this data and, for this particular research project, will save me HOURS of data collection and data entry time.

Bin Packing Made Easier?

2009-07-28T23:59:00.000+01:00

I have always found the following example interesting. I remember that it was Peter Ross who first showed me this during a presentation at a conferenec we were both attending.

The example demonstrates that an algorithm can act in an unexpected way when you make a very small change to the input data.

The example is drawn from bin packing. In this problem, you are given a number of items, all of which have a weight. Let's assume that we have the following 33 items.

442, 252, 127, 106, 37, 10, 10, 252, 252, 127, 106, 37, 10, 9, 252, 252, 127, 85, 12, 10, 9, 252, 127, 106, 84, 12, 10, 252, 127, 106, 46, 12, 10

We are also given an infinite number of bins, each one having a certain capacity. Let's assume that the capacity of our bins is 524.

The aim is to pack all 33 items into as few bins as possible.

How would you do it? What algorithm would you use?

One possible algorithm is as follows:

1) Sort the items into descending order of size, thus:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 46, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9

2) Take each item in turn and place it into the first bin that will accommodate it. The bins are also considered in the order they were first used.
So, to start we have no bins available, so we open one. We take the first item (442) and place it in that bin. Now we take the next item (252). We cannot fit this into the bin we have just opened (as 442+252 > 524) so we open another bin.
The next item (252) will be placed in the second bin. The next item (252) will have to open a third bin.

... and so on.

If you apply this algorithm, you will get this solution

Bin 1: 442, 46, 12, 12, 12 = 524
Bin 2: 252, 252, 10, 10 = 524
Bin 3: 252, 252, 10, 10 = 524
Bin 4: 252, 252, 10, 10 = 524
Bin 5: 252, 127, 127, 9, 9 = 524
Bin 6: 127, 127, 127, 106, 37 = 524
Bin 7: 106, 106, 106, 85, 84, 37 = 524

You'll notice that we have a solution that requires 7 bins and, moreoever, each bin is completely full. Therefore, we know we have found an optimal solution.

As an aside, what we have just done is used a heuristic (a rule of thumb). This one is known as Largest Fit, First Fit. We could come up with many more. For example, we could sort the pieces in different ways, we could consider all the open bins before deciding which one to use etc.

The question now arises, is the largest fit, first fit heuristic always the best heuristic to use for the bin packing problem?

Let's see.

Take our list of sorted items again. That is:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9

But this time remove an item (say 46 - which has been removed from the list above).
We know that we can use seven bins to pack these items, and have 46 units left over.

So, let's apply the largest fit, first fit heuristic and see what happens.

This is the result.

Bin 1: 442, 37, 37 = 516
Bin 2: 252, 252, 12 = 516
Bin 3: 252, 252, 12 = 516
Bin 4: 252, 252, 12 = 516
Bin 5: 252, 127, 127, 10 = 516
Bin 6: 127, 127, 127, 106, 10, 10, 10 = 517
Bin 7: 106, 106, 106, 85, 84, 10, 10, 9 = 516
Bin 8: 9 = 9

This is quite surprising (well, it is to me). We have removed an item, but had to use an extra bin.

Of course, we could develop another heuristic that only used 7 bins, but would that heuristic work well on other problem instances? Or, to put it another way, if you were presented with an instance of a problem you had not seen which heuristic would you use?

There is some work being done in an area termed hyper-heuristics (which I'll blog more about in the future) which is trying to address problems such as those described above.

If you are interested in reading more about hyper-heuristics, you might like to visit my publications page (http://www.cs.nott.ac.uk/~gxk/gxk1/publications.html).

Good introductory articles are:

Cowling P., Kendall G., Soubeiga E.A Hyperheuristic Approach to Scheduling a Sales Summit. In LNCS 2079, Practice and Theory of Automated Timetabling III : Third International Conference, PATAT 2000, Konstanz, Germany, August 2000, selected papers (eds Burke E.K. and Erben W), Springer-Verlag, pp 176-190, ISBN : 3-540-42421-0
Burke E.K., Kendall G. and Soubeiga E. (2003) A Tabu-Search Hyper-Heuristic for Timetabling and Rostering. Journal of Heuristics , 9(6), 451-470, 2003
Burke E., Hart E., Kendall G., Newall J., Ross P. and Schulenburg S. (2003) Hyper-Heuristics: An Emerging Direction in Modern Search Technology. Handbook of Meta-Heuristics (Glover F., ed), pp 457 – 474, Kluwer

Football (Soccer) Prediction: Development Framework (#001)

2009-07-27T17:21:00.018+01:00

As the new football (soccer in the USA) season approaches I am trying to get a football prediction system up and running. I think I will struggle to get it ready for the start of the new season (which starts Aug 7th) but that is not so important as this is mostly a research project. In any case, the system I have in mind will take a few weeks before it is usable as I need to get some results posted for the prediction system to work on.

I did a quick check on how much time I have spent so far on the programming. As a rough estimate, I think it is about 100 hours, mostly (if not all) at weekends. I still have a lot to do but I almost have the "football framework" that I need. That is, I can read in the data that I have been collecting, generate a league table for a given date in the season and collate various other statistics that I will eventually need. I also have various data structures that I will "pass around" the prediction part of the system.

I reckon that I need about another 20 hours and then I'll have the framework completed. Then I can start to work on the prediction parts of the system.

One thing that I need to implement is an Artificial Neural Network (ANN). I have one from another project I worked on (stock market forecasting) but I want to re-engineer it. At the moment the ANN is only a feed forward network as it was used in an evolutionary setting. That is, the predictions were evolved rather than a more traditional training mechanism.
One thing lacking in my ANN class (I program in C++) is a back propagation training (BP) mechanism So, apart from tidying up the code, I also want to implement a back propagation method, as this seems one potential way to carry out the prediction.

So I have my work cut out over the coming weeks, but I hope that it will be interesting and, you never know, it might just work.

Football Prediction: Follow up

2009-07-22T13:37:00.002+01:00

Whilst searching around the net looking for relevant resources for my plan to predict football matches, I came across The Sports Exchange. It looks like a relatively new web site, but seems very nice.

I posted a comment in their blog (about football pools prediction), and received a number of replies. The blog entry can be seen here.

Predicting the Results of Football Matches

2009-07-20T20:20:00.000+01:00

I have recently become interested in trying to predict the results of football matches.

The interest grew from wondering what else I could use the data for, that I had collected for generating football fixtures (see JORS paper). The data included the travel distances between all the teams in each division. I also maintained the fixtures that were actually played over the Christmas/New Year period so that I could compare the fixtures I generated against those that were actually played. Needless to say, it took a long time to collect all this data.

As I had gone to all the time and trouble of collecting the data I want to maximise its usage, so I began to look for other uses that I could put it to, and prediction seemed an obvious challenge.

With this in mind, for most of last season I collected additional data that I think might be important in predicting football matches. For example, I have been updating all the scores as each fixture was played. I have also been keeping a record of the odds that bookmakers were offering. Just collecting this data was a large data collection exercise in itself and I certainly did not get the odds on every fixture, but I have enough to be going on with.

I'm not totally sure what I am going to do with this data yet but I know if I don't collect some of it as and when it is available, it becomes almost impossible (or at least a lot more difficult) to collect.

I have started programming some support functions. For example, given a date and a set of results I can generate the relevant league table for that point in the season.

My ultimate goal is to develop a prediction model and test out how good it is on the 2008-2009 season and, if I find a good model I will try and predict the fixtures for the 2009-2010 season before the matches are actually played.

The new season starts quite soon (kick off is 8th August 2009, but there is one match scheduled on the 7th August 2009).

If I am going to have ever chance of testing the prediction model over the coming season, I need to get programming!

Research Assessment in the UK

2009-07-19T22:36:00.008+01:00

Like it or not the academic world is slowly (or perhaps not that slowly) moving towards being judged by how highly cited our work is. Actually, it is not a bad measure as if you publish something and nobody ever reads it, or refers to it (i.e. cites it in their own work), then was their any point in publishing that research?

The problem is, of course, that it might takes years (perhaps decades; or even more) for somebody else to recognise the value in a particular piece of research. The other problem is that once scientists know that they are being evaluated in this way, they find ways to maximise their citations (they are typically quite clever people!).

The next research assessment that will be carried out in the UK (called the Research Excellence Framework (REF)) will using citations as a major way to measure the impact of the research that is carried out by individuals, research groups and universities.

If you are interested in the REF take a look at http://www.hefce.ac.uk/Research/ref

At the moment, in the UK, this area is the subject of heated debate in the scientific community and this will be the case for the foreseeable future, especially when you bear in mind that the last research assessment (Research Assessment Exercise (RAE)) has only just been completed (the results were announced in December 2008 - http://www.rae.ac.uk).

Vehicle Routing: Case Study at EURO

2009-07-06T14:15:00.013+01:00

I am at the EURO 2009 conference at the moment and have just been to a very interesting presentation (the picture was taken during the presentation).

A few days ago I wrote a blog on various formulations of the Vehicle Routing Problem (VRP) (see original post). This blog talked about the many variants of the VRP.

The talk (6th July 2009: 13:35) was entitled Vehicle Routing Problem: A Case Study in Local Government. It considered six different VRPs (eight if you also take into account the ones which do not transport people around (laundry and meal deliveries)) that Coventry City Council face.
They all have lots of constraints that you may not normally associate with the VRP. For example:

They want people to spend as little time on the bus as possible;
Usually the aim is to minimise the distance but in this case we want to minimise the time between locations (a subtle difference, and something I have been looking at recently with the help of Google Maps API - more on this later).
They require pickups to be as efficent as possible (i.e. they want to pick up people who are close to one another in one go rather than back-tracking);
etc.

Unfortunately, I don't have access to the slides which listed all the constraints, but it made interesting reading.

I hope the authors are able to publish this work as it would make a good case study paper

General Algebraic Modeling System (GAMS)

2009-07-06T08:07:00.006+01:00

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

2009-07-05T17:20:00.007+01:00

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.

Cloud Computing

2009-06-30T18:12:00.011+01:00

I have spent the day (30th June 2009) in London, attending a Microsoft Cloud Computing forum.

The picture shows Microsoft's Offices in Victoria.

I was not really sure what Cloud Computing was before I went and I am still not totally sure now! I am also not sure of the real differences between Grid Computing and Cloud Computing.

Whatever Cloud Computing is, Microsoft seem to be investing heavily in this technology and are looking at working with academic partners.

The upside of the day is that I got lots of pointers that I can follow up so, given a couple of weeks, I should be able to at least understand the terminology.

If you have any useful pointers, hints, tips etc. I would not be upset if you shared them with me!

Google Scholar

2009-06-29T11:50:00.000+01:00

I guess that most people are aware of Google. It is so well known that it is almost a verb now; if not so already - a bit like hoover.
Most people will also be aware of other Google tools such as maps and blogs (indeed this is a blog that I set up through Google).

However, there are some tools which you may not be aware of. One that is particularly useful to the scientific community is Google Scholar. This is available via the Google home page, using their menu system, and can also be accessed via http://scholar.google.co.uk.

Google Scholar searches in the same way as the normal Google search engine, but it only searches through the scientific literature. There is actually no replacement for going to the original source of the material (e.g. scientific journals) but this is not always possible. For example, you may not know which journals to look for and you may not be able to access them (you usually have to pay; fortunately, as I work in a university, I am able to access many of the journals that I need).
But using Google Scholar, even if you intend to go to the original source later, can still be a useful starting point for your search, just to see what material is out there.

So if you want to see what scientists have to say about your favourite subject, try searching through Google Schoolar, instead of using the usual Google interface. You might actually find that we have something interesting to say!

Model Formulation: Vehicle Routing Problem (VRP)

2009-06-25T22:31:00.002+01:00

If you are aware of the Vehicle Routing Problem (VRP), you will know that it is quite an easy problem to state, although it has many variations which make it one of the more complex standard models.

Here is a fairly standard description (model):

You are given:
- a set of customers (each one having a demand);
- the location for each customer (perhaps as x,y coordinates or, perhaps, as a distance matrix between each customer);
- a set vehicles, each with a given capacity (usually identical for all vehicles);
- a depot; where each vehicle must start and end.

Then the problem is to come up with a number of routes (the number of routes is usually the same as the number of vehicles) that

a) minimises the distance travelled and
b) ensures that a vehicle does not exceed its capacity taking into account the customers it visits and their demand.

And that is all well and good and a lot of excellent research has been carried out using this relatively simple model.

Of course, there are many variations. For example, trying to minimise the number of vehicles (routes), introducing the concept of backhauls (i.e. doing all the deliveries and then going back to each customer and picking things up) and having time windows (i.e. a customer has to be visited at a certain time).

However, even these variations (and there are many others) do not capture many real world issues that often need to be addressed. Take, for example, supermarkets that deliver to your door. It is usually a Vehicle Routing Problem with Time Windows (the supermarkets often give you a two hour slot when they will deliver). But what about other factors that might have to be considered? How about:
- Time might be an issue with respect to how long perishable goods can be in the delivery van.
- Perhaps the vehicle has to be packed in such a way that the deliveries which are delivered first have to be loaded last.
- Perhaps the vehicle can only carry a certain weight, in addition to a certain volume.
- Perhaps the weight has to be evenly distributed over the vehicle.
- What happens if there is a breakdown.
- When do you "pick" the goods from the shelves and when do you "dispatch" the vehicles.

Some of these may not actually be problems for the supermarket delivery problem but you can imagine these factors coming into play for other types of delivery problems.
And trying to take a standard vehicle routing model and developing it to model a real world problem is often far from easy.

Horse Race Prediction with Neural Networks

2009-06-20T17:26:00.017+01:00

I was sorting through some old papers recently and I came across my undergraduate final year dissertation. I recall that it started as a project about genetic algorithms but quickly turned into a project that used neural networks to predict the outcome of horse races.

I trained a back propagation network and used the final network to predict the outcome of (selected) races that the network had not been trained on. One of the biggest challenges was finding suitable data. I was lucky enough that a couple of companies (Timeform and Raceform - thank you) sent me their databases which made the data collection side of things a lot easier than it might have been.

One item that was missing from both datasets were the starting prices. Due to this I could not really judge if the predictions would result in a profit. However I did a few calculations and assumed that the average odds were either 2/1 (3.00), evens (2.00) or 1/2 (1.50) (see note, for a description of the odds calculation). I also made an assumption that the odds would also capture any tax that had to be paid.
Using these figures it was possible to make a profit even when the average odds were as low as 1/2 (1.50).

I wonder if it really is possible to develop a prediction system that can make a profit from backing horses? Although my undergraduate dissertation suggested that it is, it would need a lot more development, testing and analysis.
I would also like to investigate other methodologies, in addition to neural networks - but that needs a little more thinking about.

Of course, it's not possible to predict the result of every race but you only need to predict enough races, at good enough odds, to show a profit.

One of the issues when betting is the amount of tax you have to pay but with new methods of betting (such as spread betting and betting exchanges) becoming ever more popular, perhaps this might not be so much of an issue.
I know that betting exchanges (such as betfair) still charge a tax but at least you are betting against other punters and are not limited by the odds being offered by the bookmakers.

I'll keep this one of the back burner for a while, but I think there is some potential in exploring it further.

Note on odds: I have shown the odds in two ways. The UK way of expressing odds is (for example) 2/1 which means you have to place a stake of 1 unit to win 2 units. You also receive back your stake. So if you bet 1 unit at odds of 2/1, and the horse wins you receive 3 units back (the 2 units you won + your 1 unit stake = 3 units; less any tax - but let's ignore that for the purpose of this discussion).
Another way of expressing odds is the decimal format (which I have shown in brackets). This is used, for example, on betfair. This says how much you will receive for 1 unit, including getting your stake back. So if you bet 1 unit at odds of 3.00, and the horse wins, you get 3 units back.
So the two ways are just the same way of expressing the same thing, but you might be more used to seeing one system over another, depending on where you live/bet.

MISTA Conference

2009-06-19T23:16:00.009+01:00

Since 2003 I have chaired the Multidiscplinary Conference on Scheduling: Theory and Applications (MISTA). The first conference (2003) was held in Nottingham, the second (2005) was held in New York and the third conference (2007) took place in Paris.

The 2009 conference (the 4th in the series) is due to take place in Dublin (10th - 12th August 2009).

The conference is now only about eight weeks away and, as anybody knows who has organised a conference, it is a busy time for all concerned (both organisers and authors).

Our main efforts at the moment are being directed at ensuring that revised papers (taking into account the comments of the reviewers) have been uploaded and checking that each paper has an registered author.

Once we have registration/paper uploads resolved (in the next few days we hope), we will close the web site (we are using easychair) so that nobody tries to "sneak" in a late paper.

Then the task of producing the proceedings begins. This has to be done with great care as just a single mistake will haunt us forever.

Scheduling Football Fixtures

2009-06-18T19:26:00.032+01:00

The fixtures for the English football season have just been published (Wednesday 17th June 2009), ready for the kick off in August. Paul Fletcher's (another blogger) excellent article describes some of the complexities that have to be considered when generating the fixtures.

My research has focused on scheduling the fixtures over the Christmas/New Year period. On Boxing Day and New Years Day every team has to play. If a team plays at home on Boxing Day, they must play away on New Years Day (and vice versa), but they are not allowed to play a reverse fixture (for example, if Chelsea play Liverpool on Boxing Day, Liverpool cannot play Chelsea on New Years Day). There are also other factors which have to be considered (such as the number of fixtures that can take place in London etc.)

One of the most important aspects for the fixtures on Boxing Day and New Years Day fixture is to reduce the amount of traveling for the supporters. If you look at these fixtures for (at least) the past seven seasons you will see that these two days have the lowest travel distances when compared to other dates when all the teams play.

This was the focus of a paper I published in Journal of the Operational Research Society (you can access the paper here, or from the journal itself). The paper shows that it is possible to produce a set of fixtures which involves less travel than the fixtures that were actually used.

There are a couple of caveats.

I have tried to make sure that I have captured all the aspects of the real world problem, but I cannot be totally sure. For example, I consider all pair clashes (see the paper if you are interested in what a pair clash is) as being equal. Perhaps, some should be avoided more than others?
There are some seasons (typically World Cup years) where, over the Christmas and New Year period, every team has to play four matches and they must be sequenced Home, Away, Home, Away (or Away, Home, Away, Home). This makes the scheduling problem a lot more difficult, especially when you still attempting to minimise the travel distances. I still need to address this aspect of the problem.

The paper referred to above only considers four seasons. I have other work in progress which not only uses seven seasons of data but also uses more sophisticated search techniques. Not only am I able to significantly speed up the search (from about 30 hours to a matter of minutes) but I also managed to improve on the results reported in the JORS paper. I'll report more if/when the paper is published.

In the meantime, my attention is turning towards the 2009-2010 season. One of the biggest tasks each year is to collect the data representing distances between each football club. For the past seven years I have used http://www.greenflag.com. It is a time consuming task as I have to manually collect the data for each pair of teams. This year I am looking at exploiting google maps. They have an API (Application Programming Interface) which I hope will enable me to automate this data collection task. I will report on the success (or failure) of this approach soon.

Operational or Operations Research?

2009-06-17T20:00:00.003+01:00

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.

Welcome

2009-06-17T19:52:00.002+01:00

Welcome to my blog.

Through this blog I'd like to discuss areas that are related to my research interests.

I will post on an irregular basis as, I am guessing, that there will be more important things to do on many days but I hope to post regularly enough to make it worth visiting every so often.