In my last post I was trying to decide whether to use Swing or SWT when using WindowBuilder. I am using the Eclipse IDE.
Learning to use Swing and SWT
The problem is, there does not seem to be any clear cut view as to which is best. This post on stackexchange is typical.
Researching the options
Most of the forums/tutorials I found on Google tended to jump in at the deep end, assuming that you know the basics and it was not very helpful in making this decision. Then I came across this youtube video.
The sound quality is not that good, but it takes you from how to install WindowBuilder, all the way to using Swing to create a window. I actually followed the tutorial in real time and managed to get the same results (a window with a text button in it), which I though was quite impressive.
The tutorial uses Swing, and I have since heard that Swing is better for Windows applications. Whether that is true or not, I don’t know, but as I have to make a decision, I have decided (for now anyway) to adopt Swing.
If I am honest, I don’t think it actually makes that much difference. The applications that I intend to write will be fairly simple from a GUI point of view, so I doubt that I would really push the limits of either Swing or SWT.
Eclipse IDE (Dowsnloaded from Google, vis Creative Commons – 06 Mar 2014)
Whether, this is a good decision remains to be seen – but at least I am making some decisions. I have decided to use Eclipse, and now Swing.
I think that these represent two of the major decisions and even they are not reversible. I can always switch at a later date.
Probably of more importance now, is to actually write some Java code. Knowing C++ should make this relatively easy, but bolting everything together within a GUI might be the major challenge!
In my previous post, I outlined the reasons why I was switching to Java as the programming language of choice for a football prediction system that I am developing. In this post, I try to decide what Java GUI development tool I should use? Should I use Swing or SWT?
Getting to grips with Java
Eclipse IDE (Dowsnloaded from Google, vis Creative Commons – 06 Mar 2014)
I still need to get my head around Java. As I said before, I have done some Java programming but I’ll need to get a lot more skilled with the language. But, as one of the key reasons for switching to Java is to try and find an easier way (for me) to develop a graphical user interface, I thought that I ought to try and make that decision now.
Digging around, there are some tools that I could use. Eclipse WindowBuilder seems to get a decent write up, so I decided to use that. At the time of writing, I have installed this as part of my Eclipse installation. So far, so good.
Swing or SWT?
Once I started digging a little deeper, I found that I had to make another decsion, whether to use Swing or SWT. This does not seem so easy to answer. Searching for comparisons (this one is typical) tends to brings up pros and cons for each, with the conclusion that there is no right or wrong answer, in the same way that there is not clear cut answer whether you should use Eclipse, NetBeans or IntelliJ as your IDE.
So, at the moment, I am still none the wiser whether to use Swing or SWT. Unless anybody has any insights (please feel free to leave a comment) I think I might have to try both. Probably eaiser said than done, as I am no where near the stage where I can get a Window to display on the screen, let alone decide the best tool to do it!
I want to do the project justice so I thought I would start from the most basic decision. What programming language should I use?
The Problem with C++
For the past 20 years, I have been using C++ (before that I was using all sorts of mainframe languages). I can do what I need to do with C++, but I have never been entirely happy with it.
As a language, I quite like it, but it is all the stuff that goes with it that has always been frustrating. And most of that stuff is around Visual Studio (VS), MFC (Microsoft Foundation Classes) and Templates. Don’t get me wrong, this is not a Microsoft bashing exercise. I know of many people who use VS and are very happy with it, develop great applications and know how to use the tools that are available.
But I have never really got my head around it. I run into all sorts of problems with namespaces, linking errors, deciding whether to use MFC (Micosoft Foundation Classes), or not – and then regretting it, whether to use the classes available in VS so that I could port my code to another compiler should I wish to do so; and the list goes on.
The end result is that I have never really developed as a C++ programmer. I can do all the usual stuff (classes, inheritance, operator overloading, polymorphism) but I have never been able to get to grips with Windows (Graphical User Interface – GUI) programming and so have always stuck with a Command Line Interface (CLI).
To be honest, using a CLI has served me well and I have managed to churn out some nice programs. But for my football prediction project, I really want to develop some sort of GUI. The question I asked is, should I have another go at getting to grips with MFC, Windows programming and all that is need to get an application developed in VS to display a Window on the screen, or do I change to something else, in the hope that I will find it a little easier to understand?
So why Java?
After a lot of soul searching, and Googling, I decided that it was time to switch to Java. I have written a couple of programs in Java before, but nothing too much beyond “Hello World”.
But is like C (syntax wise), and like C++ (class wise), it is well supported, many of my academic colleagues use it, it is platform independent and, I hope, that GUI programming is a little easier than VS.
More questions that answers
Of course, making the decision to use Java just raises a whole load more questions. What IDE should I use (I have chosen Eclipse), how big is the learning curve, can I easily access Excel files, can I (should I) use MySQL, what Java tools are available to support developing a a GUI etc.
All these questions will have to wait. For now, I have to learn the basics of Java and get my head around the Eclipse IDE (Intergrated Development Environment).
Knight’s Tour (screen shot from Numberphile video)
If you are interested in Chess, you may have come across Knight’s Tour problem before.
Your task is to take a knight and place it anywhere on the chess board. Then, by performing legal Knight’s moves. can you visit each square on the chess board? Moreoever, you are only allowed to visit each square once (so 64 moves)?
If you end up at the final square, and it would be possible to move to your starting square with a legal Knight’s move, this is know as a close tour. Mathematicians would also recognise this as a Hamiltonian Path.
If you end up on a square where it is not possible to get to your starting position (via a legal Knight’s move) this is know as an open tour.
When you first see this problem, you tend to think that it would be impossible to find any tour, whether open or closed.
You might be surprised to learn that there are 26,534,728,821,064 closed tours. Yes, that’s right, 26 TRILLION of these tours. So if you tried it and could not find one, then shame on you :-).
How many open tours do you think there are? At the time of writing, nobody knows!
The video below does the job of exaplaining Knight’s Tours much better than I can, and it also includes some extra information about semi-magical squares.
I have a particular interest in this video and I had some discussions with Brady Haran (the producer of this series) as I have published a couple of papers on this topic (see here and here) , where we used ants to find Knight’s tours.
If you are interested in the Vehicle Routing Problem (although the actual problem being considered is called Swap-Body Vehicle Routing Problem (SB-VRP)), you might be interested in this competition.
The deadline, to register, is the 31st Dec 2013 although the actual submission deadline is not until April, so you can register and still have plently of time to get your entry ready.
The competition is run by VeRoLog and full details are available here.
A brief descition of the competition (from their web site) is as follows:
“VeRoLog, in collaboration with PTV group, is proud to announce the first edition of the VeRoLog Solver Challenge (VSC2014). This challenge is aimed at comparing on a specific variant of Vehicle Routing Problem (VRP), this year proposed by PTV, the computer codes implemented by the participants and submitted in executable form to the jury. The codes will be compared by considering the quality of the solutions obtained within a specific time limit on a set of test instances that will be defined by the jury. The declaration of the winners will take place at VeRoLog 2014 in Oslo, June 22-25, 2014.
The problem that is the subject of VSC2014 is called the Swap-Body VRP (SB-VRP) and is described in detail in the attached document. The participant teams have to pre-register BEFORE December 31, 2013 by sending an email to the jury at email@example.com indicating the name and affiliation of all team members and the name of the team leader.”
This post also appeared on a University of Nottingham blog post.
It’s a little late to help Santa this year, but as this Kagglecompetition (essentially a 3D bin packing problem) does not close until the 26th January 2014, you can contribute towards the planning that will no doubt start as soon as he touches down at the North Pole after delivering all the presents this year.
In the competition you are asked to pack Santa’a sleigh in the most efficient way possible, so that he can carry as many presents as possible.
3D bin packing
The problem is actually an abstraction of the 3D bin packing problem, which has many practical uses, such as loading lorries, packing containers and loading pallets.
I admit to having a liking for this problem as my PhD was in a related area; 2D bin packing. Some of my papers in this area can be seen here, and since finishing my PhD I have published on the 3D bin packing problem. Most of this work has been to do with meta- and hyper- heuristic approaches, rather than exact methods, which tend to be too computationally expensive for reasonably sized problems.
In this festive version of the 3D bin packing problem you are asked to help Santa load up his sleigh with as many presents as possible. You should be warned that this is a very difficult problem to solve, especially if you want to find the optimal solution but, If you think that you are good enough, give it a go. At least the problem is very easy to understand and, unlike, other versions of the problems (e.g. 2D packing where the shapes can contain holes), the geometry is fairly easy to get to grips with.
Note: I also posted a similar post at the University of Nottingham blog (the post will not appear until the 27th Dec 2013).
Packing Santa’s Sleigh (Screen shot from Kaggle web site – https://www.kaggle.com/c/packing-santas-sleigh)
In a few hours Santa will begin his annual tour of the world, dropping down chimney’s and delivering presents to all the children who have behaved themselves this year. He may not realise it, but he is solving a Traveling Salesman Problem as he plans which route to take.
What is more amazing that he can deliver all these presents in a single night, even if we account for the fact that time differences gives him some extra time. How does he manage to do this?
I recently publsihed a post that suggested that if Santa could travel faster than the speed of light then all of his problems would be solved. I also published another post that enabled you to add your home to Santa’s list, so that he does not forget you (we made sure that UNMC would get a visit!).
Some of the science that might also help Santa is given in this piece which has just been published in TheConversation, specifically in the Science + Technology section. It considers whether the Traveling Salesman Problems is the answer to all Santa’s problems.
Note: I also published a similar post at the University of Nottingham
World Airline Route Maps: Downloaded from Google (22 Dec 2013, labaled as free to reuse) – URL: http://en.wikipedia.org/wiki/File:World-airline-routemap-2009.png
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)
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)).
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.
 Gass S.I. and Assad A.A. An Annotated Timeline of Operations Research: An Informal History, Springer. ISBN-10: 1402081162, ISBN-13: 978-1402081163
 Historical Origins of Operations Research, http://en.wikipedia.org/wiki/Operations_research#Historical_origins, last accessed 2nd Mar 2013
 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 (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
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).
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.
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.
Chelsea have produced artist’s impressions of how a new stadium at Battersea Power Station would look. Photograph: Chelsea/PA (19 Jun 2013: downloaded via Google where the image was labeled as free to reuse)
Football fixture forecasting is something I have expressed an interest in recently. Actually, this blog contains a forecasting category, that you might be interested in.
In my last post, I mentioned a crowdfunding project that I am trying to get off the ground. This prroject aims to investigate football fixture forecasting, utilising methodologies such as Artificial Neural Networks and algorithms based on Darwin’s prnciples of natural evolution (survival of the fittest).
Doing research for this project, I looked around a few football forums and found that there is a brisk business in football forecasting competitions (usually just for fun).
FootballForums.net have a Football Forum thread, which can be accessed here.
Total Football Forum also has a prediction thread.
I mention these now, as they might be of interest as the new season approaches.
Of course, one of football’s most well known pundits (Mark Lawrenson) makes predictions every week (on Radio Five Live I believe) and these are tracked at various web sites including MyFootballFacts.com. This site does a great job of showing the actual league tables and what would have happended if all Lawro’s predictions had come true. It’s interesting to see the fairly signisficant differences league table based on actual resuts. I guess it is no that surprising that there are large differences as, if Lawro, was an excellent preditor all the time, the bookies would be bankrupt.
I think I am also right in saying that Lawro tries to predict the actual score. This has got to be difficult. If I ever get my project off the ground, I think I’ll just try to predict whether the home team will Win, Lose or Draw.
Crowdfunding: Money from many contributors? (picture courtesy of freefoto.com (by Ian Britton))
A few weeks ago I came across something called crowdfunding. I have known about crowdsourcing for a while, but crowdfunding had escapsed me.
I am not sure it is a good idea but I thought I would try it out (see my project here, it develops my project for football prediction or, for more general blogs on forecasting, see here).
Of course, it would be nice to get the project funded but it is also an experiment as, if crowd funding does take off, I want to be able to have some knowledge/experince of the medium.
The idea is that you get a crowd of people to fund a project by contributing small amounts in the hope that you can reach the goal required for you to carry out the project. In order to motivate people to contribute, you offer a series of rewards with the rewards getting better the more that is contributed.
The research community has recently started to show an interest in this model of rasing funds for research. It is still in the very early stages, but I believe that it will become a more pominent feature of the funding landscape in the coming months/years.
If you are interested, there has been some limited scientific publications on Crowdfunding. This is certainly not a complete list, but here are some publications I found via a quick search on Web of Knowledge.