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.

ORlimpics: Making an OR medal list from OR-Exchange scores and badges

After reading Michael Trick’s blog post on ways of scoring countries according to the medal list, I wondered how to come up with a similar list in the OR world. After all, we have OR-Exchange, an online community where users are scored for their questions and answers as well as recognized with badges for certain achievements (gold, silver and bronze badges: quite similar to the Olympic Games). The results that I found provide an interesting picture of the community. In fact, I was glad that Brazil was better ranked in this list than in the one of the 2012 Summer Games!

I decided to summarize the results of all participants with a score of at least 200 (at first, I wanted to consider at least 100, but there were too many people without a declared country in the range 100-200, so I kept a smaller but reliable sample). I counted each badge as a medal, and I also considered two extra sets of medals to valorize the score of the participants.

The first set is equivalent to the marathon: who are the most diligent contributors? Gold for Paul Rubin, silver for DC Woods, and bronze for Bo Jensen. The second set accounted for team work: which countries had the higher combined score? Gold for the USA (Rubin alone guaranteed that), silver for Germany (mostly due to Florian Bahr and Marco Lüebbecke), and bronze for Denmark (Bo Jensen again).

After counting those, the final ranking was the following:

# Country Participants w/ score > 200 Total score Gold Silver Bronze
1 USA 18 25315 2 29 150
2 Denmark 2 3854 1 3 17
3 Sweden 1 211 1 1 5
4 India 6 3237 0 7 54
5 Germany 5 4340 0 7 32
6 Australia 1 3787 0 5 26
7 Brazil 2 2599 0 3 17
8 Greece 2 1078 0 3 13
9 Ukraine 1 253 0 3 6
10 Iran 1 1925 0 2 12
11 Canada 1 299 0 2 10
12 Iceland 1 680 0 2 7
13 Belgium 2 2445 0 1 18
14 Finland 1 413 0 1 10
15 Singapore 1 305 0 1 7
16 New Zealand 1 231 0 1 7
17 France 1 333 0 1 5
18 UK 1 236 0 0 2

 

Kudos to the OR-Exchange maintainers

Finally, even if not considered in the medal list ranking, we must account for something similar to the Pierre de Coubertin medals, which are offered to athletes who represented the truly Olympic spirit. In the context of OR-Exchange, the first thing that comes to my mind is the effort of some individuals and of INFORMS as well to keep OR-Exchange up and running properly. Among the top scores in the website, I know for sure that I can count Michael Trick, Mary Leszczynski, and Herman Strom as medalists for their effort on that. There are probably other “OR athletes” who deserve this medal, so I will consider this list as open-ended and I would appreciate any comment to include other contributors in the list.

An advanced school on handling big data for academic purposes (with full grants for Brazilian and foreign students): São Paulo Advanced School on e-Science

São Paulo state’s research council (FAPESP) is sponsoring an interesting school on e-science, which I would describe to the blog audience as analytics for academic purposes. It is said that they will offer full financial support for 25 Brazilian and 25 foreign students. The school will be held next October in the surroundings of my alma matter, Unicamp.

Further information can be found at: http://www.vision.ime.usp.br/~liu/escibioenergy/

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.

CFP: OR/MS Applications in the Energy Sector of Emerging Countries at 2012 INFORMS Annual Meeting

I am organizing a session on “Applications in the Energy Sector of Emerging Countries” within the invited cluster “Operations Research and Management Science in Emerging Economies” at the INFORMS Annual Meeting.

If you are interested in presenting your abstract in this section, please contact me.

The abstract submission deadline is May 15, 2012. The title must have at most 100 characters and the abstract at most 500 (about 50 words). The conference will be held on October 14-17, 2012 in Phoenix, AZ. More information can be obtained at the conference website: http://meetings2.informs.org/phoenix2012/

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: