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:

Tasting more wine with dynamic programming

The INFORMS blog suggested that O.R. bloggers wrote about food. Figuring that a good meal is usually accompanied by a good wine, I’ve decided to focus on using an Operations Research technique to maximize the number of wines someone can taste at a time. I warn in advance to connoisseurs accessing this blog by chance that my knowledge about wine tasting is very short (once in a while, I resume my reading of Jancis Jobson’s book “How to Taste Wine”, but I’m closer to the first pages than to the last ones). Anyway, I hope that some of them find dynamic programming useful for their practice.

First of all, how wine should be tasted? According to a book that I just browsed during lunch time, the following rules must be followed:

  • white before red;
  • young before old;
  • light before heavy;
  • dry before sweet.

To simplify matters, I will assume that those rules are unbreakable (are they?), I will ignore that it is recommended to taste only similar wines each time, and get to the following question: under such circumstances and provided a collection of bottles, how can I maximize the number of tastings one can do at a time?

Let’s consider as an example the following wines, which this novice considered good and attempted to roughly classify in a binary way:

W1 Argentina Finca Martha 878 Malbec 2008 red, young, heavy, dry
W2 Brazil Miolo Gammay 2010 red, young, light, dry
W3 Brazil Terranova Late Harvest Moscatel 2005 white, young, heavy, sweet
W4 Brazil Terranova Shiraz 2010 white, young, light, dry
W5 Chile Casillero del Diablo Carmenère 2009 red, young, heavy, dry
W6 Portugal Dão Cabriz 2007 red, young, heavy, dry
W7 Portugal Ramos Pinto Late Bottled Red Port 2000 red, old, heavy, sweet
W8 Portugal Sandeman White Port 2005 white, young, heavy, sweet
W9 South Africa Obikwa Pinotage 2008 red, young, light, dry

Without loss of generality and for the sake of breaking ties to avoid equivalent solutions (e.g., tasting W2 before W9 or W9 before W2), we will consider that one must proceed incrementally another in the case of a tie (i.e., W2 before W9 but not W9 before W2).

Now suppose that we start with W3 because it is white and young. Soon we will realize that only two wines can remain in our list for being also heavy and sweet: W8 and W9. Hence, W3 might not be a good starting point. However, it is easy to figure that the optimal path from W3 on is to taste W8 and then W9 because the former is white and the later red. Similarly, the optimal path starting from W8 is to proceed to W9, and from W9 is to do nothing.

Beyond the wines, do you “smell” something interesting here? We have overlapping subproblems and those optimal solutions share optimal substructures with each other. That’s where Dynamic Programming (DP) fits in! Using DP, we consider optimal solutions to varied subproblems as building blocks to find optimal solutions to increasingly bigger problems. Thus, even if those subproblems arise many times, it suffices to solve each of them once.

In the current case, we could do that by finding the best option between the following subproblems: Pi = “How many wines can I taste if I start from Wi?”, for i = 1 to 9. In turn, answering to each of those questions consists of adding one to the best answer found among wines that can be tasted after that first one. For instance, we start with W1, W2, …, or W9 to find the answers P1, P2, …, and P9. Picking W1, we have that P1 = 1 + MAX(P5, P6, P7) because W1 can only be followed by P5, P6 or P7. Note that once we answered P1, we already know the answers to P5, P6 and P7, and therefore we do not need to recalculate them in the remainder of the solving process. The act of memorizing such solutions for later recover is called memoization.

Applying DP to the current case, we will find the following answer to the subproblems:

P1 P2 P3 P4 P5 P6 P7 P8 P9
4 6 3 7 3 2 1 2 5

Working backwards, we start from W4 (P4=7) to find which wine can that can be tasted after W4 and from which point on it is possible to taste 6 wines, and so on until the last one. The final answer to our problem is the sequence W4, W2, W9, W1, W5, W6, W7.

As a final remark, I would like to remember that quantity does not mean quality. Drink responsibly and remind that a tasting experience does not necessarily means getting drunk in the end: you can always spit and enjoy the rest of your day in a better shape.

Once said that, “saúde”, “cheers”, or – as my Polish friends from the Erasmus program would say – “na zdrowie”!

 

Update: Shiraz is a grape that produces red wine, not white. Anyway, it is still possible to taste 7 out of the 9 wines at once.

Latin American higher education: the good, the bad and the ugly at The Economist

There is an article at The Economist with some overly strong generalizations about Latin American higher education. I’ve been wondering a lot if I should waste my time writing an answer since the day I read it. Despite acknowledging that one can’t expect much from a general-purpose magazine from far away, I felt that the magazine covering was pretty unfair and potentially prejudicial to many hard working researchers across the region. To sum up the article’s point, the University of São Paulo (USP) is good (in fact, an example to be followed), leading “old-established public universities […], Catholic institutions or secular non-profit places […]” are bad and the environment is ugly. Indeed, the ugly issues raised across the article are true and put our institutions in bad shape. However, the extent to which they affect each institution varies a lot. It’s important to review part of that ugliness and detach some strings.

The bad “old-established public universities”
Few colleges and even fewer universities in Brazil are more than a century old. However, four Nobel Prize laureates studied or taught at the University of Buenos Aires, which is among The Economist’s “bad list”.

The bad “Catholic institutions”
What’s wrong with being a leading Catholic institution? For years along, PUC-Rio’s Computer Science post-graduate program was rated above the rest of the programs in Brazil according to a peer-reviewed process endorsed by the Brazilian Ministry of Education, what is even more impressive if one consider that there were only 4 possible grades (from 3 to 7). Not to mention that many important Brazilian researchers studied or taught at such places.

“Research output is unimpressive”
There are many subjects that are not much studied in Brazil, including the one I’m working with, but there are many others in which Brazilian research is cutting edge as the article itself pointed out. Broadening our range of expertise is much more a matter of establishing more universities and making them compete for funding at a fair environment than blaming the institutional framework.

“teaching techniques are old-fashioned and students drop out in droves [..] Good teaching and research are not rewarded with extra funding or promotions; institutions do not lose money if their students drop out”
Students drop out in droves only when the admission acceptance rate is high, which is not the case in well-paid careers at top notch universities in Brazil. In practice, universities in some other countries might accept anyone but the selection that would occur at the admission exams is transferred to the junior classes. I don’t think that such model is reasonable for the size of the junior classes that it incurs. Anyway, that does not happen in Brazilian public universities.

At least in the State University of Campinas (Unicamp), institutional evaluations are promoted at the end of every term and are used to periodically evaluate professors whereas some student unions also promote independent evaluations that are occasionally used to recognize teaching excellence by the institution itself. As for research excellence, there is a special funding for highly productive researchers in Brazil and of course that it counts if someone is evaluated for tenure.

“Nowhere else in Latin America can match USP. […] ‘No one in the United States tries to figure out what a great university is; they just look at the Ivy League,’ he says [Andreas Schleicher of the OECD]. ‘It’s very important to have great institutions: they define success.’”
I think that our problem here is the opposite. There are some self-fulfilling prophecies in Brazil that discourage competition and academic excellence, most of which telling that good research is only made at some places or regions. Not surprisingly, many people leave their alma matter universities and cross the country under such suppositions. In fact, USP is the oldest, biggest and wealthiest university from the richest Brazilian state; but Unicamp – the second biggest and wealthiest university from the same state – holds much more patents and was invited in 2010 to nominate candidates to the Nobel Prize in Medicine. Moreover, there are great institutions supported by the federal government across the country, such as UFMG, UFRJ and UFPE; as well as some other state universities and private ones. According to the subject of interest, the ranking of those institutions may vary a lot and USP is not in the top of many of them.

I once studied at Unicamp and now I study at USP. I think that both have their merits and are able to develop good researchers through their post-graduate programs. However, I believe that a bit more of bureaucracy centralization would be beneficial to USP.

“staff are unsackable”
Despite earning above average, staff usually is on strike every year. For that reason, universities opt for outsourcing as much as they can and it usually works.

“the curriculum is old-fashioned and politicized”
Let’s say that a “left-wing perspective” does help you scoring high at the humanities topics in the admission exams, especially at USP. However, my experience in the humanities being an undergraduate student at Unicamp was not that bad: once, an economics professor invited another one with whom he did not agree at all just the give the class the opposite perspective. Still, I think that there exist some issues to be discussed about curriculum but the role of the top universities is to provide a solid basis instead of teaching trending topics that always change.

“At many Latin American public universities students pay nothing […] No country in the region has worked out satisfactorily how to share the cost of degrees between students and taxpayers”
Indeed, our biggest issue is the imbalance between higher and primary public education: despite both being for free, the former is always privileged. In practice, if parents want their children to be accepted in a public university in Brazil, they shall never consider putting their kids at a public primary school – or be very lucky.

Conclusion
If there is one thing that Brazilians are good at, I believe that is how much we can criticize each other: we have very few unquestionable heroes in our history. Personally, I was always complaining about something at Unicamp and now I’m always irritating colleagues for comparing Unicamp favorably against USP. However, comparisons are not harmless and must be made with care. If it was not by the strong sentences in The Economist’s article, I would get a little uncomfortable with what they wrote but, as a criticizer, I could not deny anything. I hope that no one abroad takes seriously that USP is way better than everything else and keep working with the other universities to help us improving our academic excellence and competitiveness.

And so SBPO is gone…

The 2011 Brazilian Symposium on Operations Research (SBPO) has come to an end and the balance is very nice. Putting the articles running for the awards on tracks apart from the rest prevented me from missing them. I had the privilege to have a paper among the nominated ones but it was not as good as the ones from Manoel Campelo and Silvio Hamacher groups, who shared the best paper award. I also crossed my fingers for Rafael Cano’s work at Unicamp in the best undergraduate research award, but Lucas Pierezan work at UFRJ was unbeatable. I had the opportunity to do a lot of networking with other authors, Petrobras employees and current Unicamp students (no matter how long I’m not there, this alma matter issue induces me to hang around with Unicamp people). It was the second time that I attended to SBPO and this edition improved a lot over the other in what comes to organization, the venue and the quality of the works. Congratulations to all involved on that.

It seems that the pictures from the previous post provoked the desired effect on those who did not attend. Hope to see some of them next time.