On my way to Quebec City for CP 2012 and heading for INFORMS 2012 in one week!

I am right now in a bus from Montreal to Quebec City. CP 2012 will officially start on Monday, but a gathering of those who arrived earlier was suggested for tomorrow in the late afternoon. The same happened last year at CPAIOR, and that was one of the reasons why I decide to come as soon as possible: to avoid missing the first gathering again.

I will be presenting a talk and a poster about the application that I approached during my MSc, which is described in a full paper in the conference proceedings. This work helped me being accepted in the CP Doctoral Program, which will promote some events directed to the graduate students attending to the conference and has assigned a mentor to each one. The CP DP organizers were very kind to help a number of us with registration costs and hosting. On top of that, I was told last week that my position paper about characterizing adaptive search methods (a sequel of my extended abstract from CPAIOR 2011) entitled me 2 minutes to give my 2 cents in a panel about the future of CP, which is being organized by Professor Pascal Van Hentenryck. In short, I am really looking forward this meeting!

In the following, I will go to Phoenix for the INFORMS Annual Meeting. I will give two talks there, one of which at the sessions about OR applications in the energy sector of emerging markets, which I am organizing, and the other at the sessions about CP, organized by Professor van Hoeve. I will also contribute to the blog of the conference, which will have as authors many of the usual OR bloggers. As soon as the blog is officially released, I will post the link here. I have interacted with a number of those guys online but I saw very few of them in person so far. Therefore, my expectations for Phoenix are also very high!

When CP becomes local search and local search becomes CP, and the same about CP and machine learning

As it is said in a Brazilian song entitled Sobradinho, “o sertão vai virar mar, dá no coração o medo que algum dia o mar também vire sertão [the hinterland will become sea, it comes to the heart the fear that someday the sea also will turn into hinterland]”. However, such an occurrence in the academic field is often reason for joy instead of worries – as well as for joint conferences where you can be delighted by funny flamewars.

In the case of Constraint Programming (CP), I have been observing the development of a strong relationship with local search as well as with machine learning. Coincidentally, while I was writing this post, a presentation of a local search solver at the 2012 ISMP (International Symposium on Mathematical Programming) seems to have caused some buzz on Twitter about local search and CP. To the argument that local search has not been exploited by major commercial solvers (as far as I could understand about the controversy), some observed that there is much of local search embedded inconspicuously in CP solvers etc. In the sequence, the discussion extended to the limits between what is CP and what is not.

However, why do we suppose that such techniques must be mutually exclusive?

From CP to local search…

Local search has been increasingly used within CP solvers, as is the case of Comet and of many papers authored by researchers from IBM describing what is behind CP Optimizer’s curtains. Many of them regard Large Neighborhood Search (LNS) as a must to solve cumulative scheduling problems, i.e., scheduling problems in which many activities can be simultaneously processed by the same resource. LNS is based on separate operators to generate modified solutions from a starting pool of solutions, and to adjust feasibility issues of those modified solutions. This latter type of operator addresses a common drawback of local search: the need to fix what the neighborhood operator unintentionally broke. [check the erratum at the end of the post]

For some, it might look strange to associate CP with local search and detach it from standard systematic techniques. While those techniques are important to tackle combinatorial problems in the general case, the size of many real-world problems is far beyond what it is possible to do in a lifetime. Hence, who cares if the search space is not fully explored by the search procedure if that is more of a theoretical matter than of a practical one? In addition, CP is about exploiting problem constraints, from the modeling with more semantic to the propagation that reduces the search space to the search that attempts to obtain feasible solutions. That leaves plenty of space to define the search according to the constraints in the model.

… and back from local search to CP!

A few weeks ago, I had the chance to observe the opposite trend: I saw a presentation about another commercial local search framework, but this one was using the concept of global constraints. As far as I could grasp, it was not on purpose. In order to reduce the problem of generating invalid solutions with standard local search operators on a broad range of problems, specialized constraints were defined to model certain combinatorial problems whose solutions cannot be modified at random. In other words, they are using specialized operators according to the structure of the problem, what is quite similar to performing propagation with specialized constraints in the context of CP models. As stated previously, the use of global constraints in CP is not only about propagation, but rather about exploiting problem structure for the sake of a better performance. And that is what they did on that local search solver. When I see such coincidences of design, I wonder how powerful but at the same time still unknown is the principle beneath CP.

Now from CP to machine learning…

And since constraints can be leveraged not only to improve propagation but also to improve search, why not mix the latter with the feedback received along the solving process in order to improve the selection of algorithms? That is a topic in which I am very interested: the development of adaptive search methods for constraint solving. It has been studied in great depth for the past decade and a half, and has received even more attention in recent years. One of the venues dedicating space to this topic is the LION (Learning and Intelligent OptimizatioN) conference series, which will have its seventh edition in Catania at the beginning of 2013. That is one of the conferences that I want to attend in the following years (monetary and job vacation constraints prevent my prompt participation).

… and back again to CP!

And if local search and CP each show off in the context of the other, one should expect the same in this case. At least, that seems to be the thought of the proponents of the recent call for papers of the first COCOMILE workshop (COmbining Constraint solving with MIning and LEarning), which will be held next August in Montpellier during the 2012 ECAI (European Conference on Artificial Intelligence). The workshop CFP emphasizes the two-way relationship between both fields. While I know that there exist some research on the CP-machine learning direction (even though I am not following it very closely), I think that a single and very specific event that attempts to look for both directions is of great help to foster further development. And, of course, that is yet another event that I want to attend in a nearby future (hopefully, publishing about at least in one of such directions).

Erratum

The description of LNS as stated in the post is not correct. It would be more precise to define that the first type of operator fixes values for part of the variables, and that the second attempts to find a feasible solution by assigning values to the remaining variables. The prior definition that I gave resembles somewhat what I understand as standard local search operators: procedures that fix the value of all variables on each solution that they generate. In the case of LNS, however, just part of the values is fixed and an iterative process is aimed at complete such partial solution.

4 summer activities you must do before graduating + late remarks about ICAPS 2012

I recently attended to the 2012 International Conference on Automated Planning and Scheduling (ICAPS), which was held at a car distance from São Paulo (what a rare opportunity!). It was the first time that I saw something like Festivus, which featured funny debates about the relevance of the research developed by the P&S community and even a bossa nova song about three blocks that wanted to be moved. Beyond the fun and cheap transportation cost, the most remarking experiences I had there were the satellite event to gather and mentor graduate students – ICAPS Doctoral Consortium – as well as observing the differences between planners and schedulers – the former of which somewhat belonging to the OR community.

ICAPS Doctoral Consortium (DC)

DC consisted of four talks directed to PhD students and a poster presentation, during which at least two mentors were assigned to talk with each student to discuss his/her research topic.

Alan Fern managed to invite young and mid-career researchers that followed varied directions after earning their PhD and were willing to tell their stories to us.

Andrew Coles presented a talk entitle “Now what?” describing his career and how much time does it take to achieve certain positions in the academia.

Silvia Richter’s talk was mostly focused on issues such as finding motivation and realizing that it takes a lot of time to have a good idea. She also provided good figures regarding how many papers you should publish (3-4 is nice) and how much effort should you put on writing your thesis (not as much as you suppose, since only 5 people will probably read it entirely), and suggested an interesting website: 3monththesis.com.

Minh Do showed some interesting graphs to compare salaries, freedom, possibilities for changing career afterwards etc for positions like working in the industry, researching in the industry, researching in the academia and striving to be a professor with tenure. On top of that, he listed four activities that any CS undergrad student should experience to know what to do with his/her life afterwards (and that I wish I was told years ago):

  • Do a research internship in academia
  • Do an internship at the headquarters of a company
  • Work in a local startup with a good tech team
  • Work in an open source project

Scott Sanner finished the session with good tips for social networking and external presence. In the former case, he stressed the importance of talking to other researchers and getting to know more about their work (and not bragging about yours) and of giving memorable talks, or at least striving to do that. In the latter case, he talked about building a professional website and he showed his first website as a funny example of what you should not do.

I presented a poster about adaptive search methods for Constraint-Based Scheduling (CBS). The first mentor who showed up was Amanda Coles (wife of Andrew Coles, the first speaker above). We had a long and interesting talk, that let me realize how much of the theoretical background of adaptive search methods for combinatorial optimization is also valuable for planning. The second mentor was Stephen Smith, who was the advisor of a number of works related to my topic of interest. I was glad that both mentors enjoyed my research plan and gave me good advices to succeed with it.

Planning vs. Scheduling (and OR)

I have already mentioned in a former post the divide between planners and schedulers: the summer school consisted of three courses about planning and one about scheduling, the latter being easier to me than the others. While some recognize that planning methods can theoretically be used to solve scheduling problems, planners strive to be as generalist as possible when approaching a problem. Schedulers, however, prefer the opposite path and delve themselves into the structure of each problem to take the most of it. In practice, their application domains barely touch each other. Nevertheless, there are some researchers that, as we say in Brazil, are on the top of the wall that divides those areas. Even though I was feeling an outsider at some moments, there were a number of talks related to OR and a few others discussing the limits of application of each type of technique. Thus, tying together planners and schedulers seems to be a good long-term strategy to both areas.

First impressions about ICAPS – or “How much I do not know”

ICAPS 2012 is being held nearby São Paulo. The Planning and Scheduling Summer School (well, it is winter here in the Southern hemisphere right now) was really interesting, but I might say that there is much that I need to learn about planning. Up to now, I was just an operations research practitioner with a lot of interest in scheduling problems. That changed somewhat with Roman Barták’s class about solving planning problems with CP (which is a technique I enjoy a lot). Besides, planning represents a quite different way of observing the reality and solve its problems. I will try to play a little with its methods someday.

To conclude with these first impressions, the Doctoral Consortium held this morning was a valuable source of advice from young post-docs and professors. I wish I heard some of those when I was still an undergrad student. Nevertheless, many of them are still valid to plan my career.

It is still time to share your work at ICAPS’12 workshops, to be held nearby São Paulo!

The upcoming edition of the International Conference on Automated Planning and Scheduling (ICAPS) will be held next June in Atibaia, São Paulo. The deadlines of some workshops has been recently extended, thus allowing more people to put together on a paper what they have been doing and have not published so far. Even if you are not thinking about submitting anything, attending to such a conference can be a double score for the opportunity of visiting an unusual place in Brazil (i.e., somewhere but Rio de Janeiro and the Northeast beaches).

Maybe I am not the right person to praise about Atibaia because I’ve never been there despite invitations from friends and living less than 50 miles away. However, it seems an interesting place for activities such as paragliding due to a big rock they have there. Besides, you will be near Brazil’s largest and most cosmopolitan city (well, that is the humble opinion of many “paulistas”, but might not be shared by our neighbors from Rio). To name but a few things worth tasting or seeing here:

Offshore Resources Scheduling and the Brazilian Symposium on Operations Research

On August 17th, I will present an article about what I’ve been working on my M.Sc. thesis at the Brazilian Symposium on Operations Research (shortened SBPO in Brazil). This article is authored by me and some colleagues from work. We are tackling the problem of scheduling offshore resources to develop oil wells with Constraint Programming (CP). It took a great effort to present so much about the problem and how to solve it in a way that it accessible to a broader audience (I hope we have managed to do that). There are four other papers competing for the best paper award. We will try our best there. Anyway, I’m glad by the nomination.

The 2011 SBPO will be held in Ubatuba, a beach town half-way between São Paulo and Rio de Janeiro.