CPAIOR 2011 is coming to its end. Despite not being the first international conference that I have ever been, it was the most interesting so far. Among the reasons for that is the fact that it is very focused if compared to other O.R. meetings. I had the opportunity to meet many people that I only knew as authors of papers I’ve read. I also met many young researchers like me, some of which as excited as I am on working in the industry with O.R.. Some of those people were impressed by how far I came from. As a matter of fact, with internet (and free access to articles) it is possible to be a researcher anywhere in the world, even if your country does not have a tradition on the topic you work with. However, talking to experienced people at such environments saves a lot of time and helps you getting further.
As for the organization, the Zuse Institute staff did a great job at everything. They managed to have something going on every night after the conference presentations. I wish I could attend to the informal meeting after the conference today, but I have bought tickets to leave Berlin in advance.
I’ve just attended a presentation from Thorsten Koch entitled “Which Mixed Integer Programs could a million CPUs solve?” at CPAIOR 2011. Like any presentation of a challenging research topic would be, it has left more doubts than answers at the end of it. Let’s understand part of the rationale of that.
As many people had already noticed, the frequency of individual processors are not increasing any longer due to technological restrictions of the current technology. Instead of that, our computers are having more and more cores. Despite the performance improvement being still noticeable for a standard user which otherwise would have many different applications being handled by the same processor, having more cores does not help a single software if it is not designed to take advantage of that.
In the case of optimization applications, that can be even more dramatic, since solvers like CPLEX does a lot of processing at the root node. Koch suggests that algorithms like the Interior Points Method would gain part of the Simplex share in the future, as is the case of parallel algorithms for matrix factorization. Hence, it seems that algorithm design researchers will have an increased budget in the forthcoming years.
CPAIOR is an interesting environment for gathering researchers from diverse but close areas, ranging from mathematical programming to artificial intelligence. That reflects the 4 organized master classes, all of which related to search: the first about mixed-integer programming (MIP, that I missed for being late), then constraint programming (CP) with Giles Pesant (I arrived at the middle of it), satisfiability (SAT) with Marijn Heule and now A* with Nathan Sturtevant. The two later speakers were invited for the sake of bringing something different to the conference.
Despite being possible to describe SAT as a proper subset of CP, research on that topic has a very different focus for being concerned with only one type of constraint (predicates) and a bi-valued domain (true and false). With a more strict focus, the SAT community has been presenting outstanding results in the last years. In fact, there are people that envy how fast SAT solvers has been progressing compared to the CP ones. However, that’s the cost of being generalist.
Nathan Sturtevant presented an interesting animated example that does explain why Dijkstra’s shortest path algorithm can be very slow for certain cases, endorsing A* search.
PS: Lunch and coffee breaks are very tasty. I can’t wait for the barbecue and the gala dinner.
On May 25th, I will present an extended abstract at CPAIOR, which will be held in Berlin next week. It is about characterizing adaptive search methods for constraint programming. I have had the support of many colleagues along the process, which will be remembered at the end of the presentation. I’m also excited for the opportunity to meet other people with the same interests there, including those that I only know as authors of papers that I’ve read.
My presentation topic has nothing to do with my master thesis. The idea went out during the last summer (of the Southern hemisphere), right on time to submit a short paper for CPAIOR at the end of January. Despite the rejection, two of the reviewers suggested that a longer version would be worth of try. So I took one step back and submitted an extended abstract, since CPAIOR environment seems to be the most appropriate to discuss the topic. Besides, all 2011 master classes will be about search. I hope to post next week about how it went out. Click here to check the conference program.