DIMACS Challenge and Workshop 2014
19th December 2014
I have very little experience with the Steiner tree problem. I think that the only thing that I knew prior to this challenge was the first couple of paragraphs from the Wikipedia page. This is certainly not the case any longer. The opportunity to participate in the DIMACS Challenge provided a great learning experience, greatly improving my knowledge in a previously unknown field. I enjoyed the challenges that arose with this project. I feel that in the end our team produced a very good solver that achieved good results.
There were many aspects of this project - the solver, the challenge organisation and the workshop. My involvement in each of these parts was both interesting and very rewarding. Each exposed me to a different aspect of the challenge and there were many things to learn in each step. This blog will look at the challenge as a whole and describe my experience.
The start of the challenge
I say "the start of the challenge", but what I really mean is "the start of the challenge for me". From the DIMACS Challenge website, the first news item was posted on the 5th June 2013. My supervisor, Thorsten Koch asked me to join the project at the start of October 2014, so by the time I started looking at Steiner trees the challenge had been running for a while. In fact, the team from SCIP had been working on the DIMACS Challenge for over a year by the time I joined. I was asked to help towards the end of the project to provide a little more manpower in order to meet the challenge deadline.
Just as a little background, the Steiner tree problem on graphs is defined as: given a set of vertices (a subset of which are terminals) connected in a graph by a set of edges, connect all terminals using a minimum number of edges (and subsequently vertices). So, the inputs for the Steiner tree problem on graphs is a set of vertices and edges. There are many different variants of this problem, such as the standard Steiner tree problem, (rooted) prize collecting, rectilinear and hop constrained, which were all part of the challenge. Our aim was to develop a solver, SCIP-Jack, to solve as many variants as possible.
My job in the team was to make sure the graph presolving worked for the directed variants of the Steiner tree problem. One reason for asking me to investigate this was that graph presolving has been shown to significantly improve a solver's performance. Before I joined, SCIP-Jack was only able to apply presolving to the undirected instances, so there was a little bit of work for me to do. It was something that seemed interesting, and definitely something that I could really get into and try to understand.
Getting into work
Many things occurred between me joining the team and the finale of the competition. First, I had planned to travel back to Australia for my PhD graduation and visit the family. That meant that I would be unable to work on SCIP-Jack for about 1.5 weeks. Second, the competition was being partly organised by Thorsten, so SCIP-Jack team was asked to help out with different parts of that. Finally, there was a very short deadline before the competition had to finish, specifically less than two months.
Travelling back to Australia was not such a big issue. I had my laptop prepared and I was ready to get work done whenever I could. I even switched the laptop on during my 3 hour stopover in Dubai just to get a little more work done (this was also an attempt to keep me awake, which turn out to be a good strategy). My trip to Australia was for both business and pleasure, first visiting family and then returning to UNSW to discuss some work with colleagues. So, when I arrived to UNSW I was ready to continue my work on SCIP-Jack.
The organisation of the competition was a little bit of fun. I was asked to put together the competition rules. In the end I only put together the first version. Gerald Gamrath also put a lot of effort into this. During my time in Australia the rules kept changing and evolving into what ended up defining the competition. One thing that stressed me out though was that while I was writing the competition rules, the deadline was being set. There were three deadlines (three different phases of the competition), each occurring while I was away in Australia. This meant that I had a bit of work to do while abroad.
The final deadline for the competition was the 24th November. This was the day after I returned to Berlin. However, there were many issues that arose in the evaluation of each of the codes and as a result the deadline kept being pushed back. In the end, the last commit of our code (done by Daniel Rehfeldt) was performed on the 2nd December, only two days before the actual workshop. This was the result of having many little things to tidy up. The work mainly entailed fixing bugs, ensuring the correct solutions were being output and finalising our paper for submission to the workshop. While at times this work can be a little frustrating, it was really great see the solver being finally submitted to the challenge.
I have to comment on the work done by Gerald. He was involved in performing the evaluations of every code submitted to the competition. That meant that scripts had to be written (and debugged), submitted codes needed to be checked to ensure they worked correctly and the evaluations had to be performed. Gerald was working tirelessly to get all of this done prior to the workshop. Unfortunately this was not possible, and he continued working right up until the results were to be released. I commend Gerald for the time and effort that he put into this competition.
Travelling to the USA - first stop Boston
The team working on SCIP-Jack involved five peoeple - Gerald Gamrath, Thorsten Koch, Daniel Rehfeldt, Yuji Shinano and myself. It was decided that we should all attend the DIMACS Workshop in Providence that was held on the 4th and 5th December. In addition to this, Thorsten was supposed to have a meeting in Boston on the 3rd December, so we were all going to attend this too. Unfortunately, Thorsten was unable to travel to the USA for the meeting and workshop, so that meant only four of us would be representing ZIB.
We arrived in Boston in the afternoon of Tuesday 2nd December. It was a little lucky that me made it at all since Lufthansa were in the middle of a pilot strike the day we were due to depart. Lufthansa were very professional and they were able to rebook all of us onto an alternative flight with Swiss Airlines.
Since we were in Boston a day prior to the DIMACS Workshop - which was planned for Thorsten's meeting - Yuji managed to organise a meeting with Dimitris Bertsimas at MIT. This was a really good meeting and a great opportunity for us to talk with a famous professor in our field. We had an interesting discussion and then Gerald gave a great presentation about SCIP for Bertsimas' research group. Something that I really enjoyed was just having the opportunity to be on the campus of such a famous university. Following this meeting, it was time to take ourselves down to Providence and get ready for the DIMACS Workshop.
The DIMACS Workshop - Providence
We arrived in Providence on Wednesday afternoon. Just in the walk from the train station to the hotel, I got the impression that this was a very nice city. Also, Providence is on a bay and has a few rivers around it, so parts of the city were very hilly. This I really enjoyed since it gave me the opportunity to go for run in the mornings and tackle a few good hills, something that is not really possible in Berlin.
The workshop was held at ICERM, since it was jointly hosted by them and DIMACS. Daniel gave his talk about SCIP-Jack in the session prior to lunch. He did very well and provided great explanation of the solver's key features. Since this challenge focused on the many different variants of Steiner tree problems, the talks were diverse and varied. The workshop provided a good overview on some of the work that is currently being performed on Steiner tree problems. One talk that really stuck with me was related to the Maximum Weight Connected Subgraph problem. This is because that problem type is closely related to the Unrooted Set Covering Connected Subgraph problem that I have done some work on. It was great to see a wide variety of talks on Steiner tree problems and the many related applications.
The challenge results!!!
All throughout the workshop, Gerald was constantly working on the evaluation of the competition submissions. The evaluation runs were planned to finish just before the workshop. However, there was a problem with the some of the instances that required the rerunning of the evaluations. This meant that Gerald had to work on the evaluations through the night on Thursday and then during the workshop up to 30 minutes before he was due to present the results. Luckily they all the evaluations finished in time.
Since there were many different variants for the Steiner tree problem, it was difficult to name a single winner. However, a collaboration between the University of Padua and the University of Vienna developed a solver that was most consistent in winning the variants that they challenged. SCIP-Jack was able to solve the most variants of all the solvers and were reasonably competitive, even winning one of the challenges for the Rooted Prize Collecting Steiner Tree problem. We were very happy with that result.
All over now - well nearly
So we developed SCIP-Jack, submitted it to the challenge, attended the workshop - we should be all done. That is not true, this solver has been developed so we can release it with SCIP in the future so that people can have access to a general solver for Steiner tree problems. So we need to make sure the code is up to standard for public use. Additionally, we have written the first parts of the paper related to SCIP-Jack. Very soon we will be looking to submit this to a journal. So there is a little bit more work to do.
This little more work is very worthwhile though. This project involved a lot of learning for me and it was a lot of fun being part of a team striving for success in a challenge. Additionally, I was able to meet a number of great people during my trip to the USA. The trip also gave me an opportunity to post a large number of tweets about the DIMACS Challenge, which is always a bit of fun. There is always the added benefit of having something to blog about. So, overall the DIMACS Challenge has been a really great experience.