Blog

Posted on

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.

Posted on

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.

Posted on

The unsustainable lack of analytical skills for a sustainable environment

Developing an analytical model to support decision-making is a really tricky task. I did many of them in order to decide whether it was a good idea to buy an apartment or to keep renting. What differed among them was the level of detail taken into account, which progressed slowly as I learned from my previous mistakes. While most of my models pointed out that it was better to keep money on a savings account and do not lend any instead of buying an apartment for the rent that can be earned (or that I would avoid paying since I had to live somewhere), I often forgot to regard the probability that apartments would appreciate considerably in a near future. Looking back, I see that my renter did an excellent investment by renting to me and waiting for what would come. Nevertheless, that moment is gone and it does not make any sense to bet that real estate in São Paulo will keep rising in price as it did in recent years.

When it comes to a trending topic like sustainability, that is supposed to represent the concern of people with protecting the environment for future generations while exploiting it for their own survival, I have been often told of misconceptions and lost opportunities that made many initiatives on that regard produce the opposite effect. And what is worst: as conceived, sustainability is a great but sometimes overlooked application domain to leverage analytical tools.

For instance, I was told of a workplace where someone had the idea of asking for shelves above the toilet washbasins. Since the washbasins were often wet, people got used to place a paper towel below their toiletries bags. As an experiment, such shelves were placed in half of the toilets of a floor. Long after, people started to ask when those shelves would be placed in the other half, since the experiment seemed to be successful. However, they were informed that someone had to collect data to assess if less paper towels were used in the first half of the toilets or not. As many people did not bother to walk more to use the toilets with shelves, it is very likely that the person undertaking such experiment will be surprised after realizing that the use of paper towels actually increased in that half and decreased in the other half. I hope that the person manages to sum up the use on both halves to realize what happened instead of concluding that shelves increase the use of paper towels.

It is attributed to Ronald Fisher the following quote: “To consult the statistician after an experiment is finished is often merely to ask him to conduct a post mortem examination. He can perhaps say what the experiment died of.”. While it would be interesting to count with professional help, I believe that we would be better off if people working with sustainability were aware of the importance of developing analytical skills to avoid working against their own goals.

Posted on

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/

Posted on

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.

Posted on

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.

Posted on

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/

Posted on

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:

Posted on

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.

Posted on

Resolutions to optimize O.R. blogging

My blog is on air for almost one year. Despite having a modest audience, lots of data has been stored about its visits and it would be ironic if a blog about Operations Research and Analytics does not use such data to improve itself. Based on some data from 2011, I’d like to commit myself to give the audience more of what they expect in 2012 and share some conclusions with other bloggers interested in doing the same.

Top 5 most viewed posts (out of 26):

# 1 Drug discovery optimization: a meeting point for data mining, graph theory and operations research
(204 unique views)

Context:

  • Motivated by an INFORMS blog challenge.
  • It is something I like and worked with in the past.
  • I found a catchy title (I guess).
  • It was a family work (my mother-in-law has a ph.D. in organic chemistry).
  • Referenced by the SYSOR Reddit channel (that made a huge difference).

# 2 Revisiting operations research elements – part I: problem, model and solution
(133 unique views)

Context:

  • Motivated by crazy discussions about what a problem, a model and a solution are.
  • I read a lot before writing.
  • It was a family work [x2] (the discussions were started by my mother-in-law and Sabrina read my drafts until they were clear to someone outside the field).
  • People look for those things on Google.

# 3 How Analytics makes Operations Research the next big thing
(111 unique views)

Context:

  • Motivated by an INFORMS blog challenge [x2].
  • It has something to do with my job.
  • I found a catchy title (I guess) [x2].
  • People look for those things on Google [x2].

# 4 Optimizing Public Policies for Urban Planning
(84 unique views)

Context:

  • Motivated by an INFORMS blog challenge [x3].
  • It is something I like and worked with in the past [x2].
  • It was a family work [x3] (Sabrina has a degree in urban planning).
  • People look for those things on Google [x3].

# 5 When the Network becomes Social: Small World Graphs and O.R.
(67 unique views)

Context:

  • Motivated by an INFORMS blog challenge [x4].
  • I read a lot before writing [x2].
  • I found a catchy title (I guess) [x3].

Lessons learned:

  • People love creative applications of O.R.
  • Telling about what you like the most helps you writing better.
  • Listening to a person around you is worth reading a dozen of papers.
  • You can learn a lot by studying further the topic you want to post about.
  • It is important to focus on being direct, concise and provide resources to those interested in more.
  • Participating on INFORMS blog challenges is a win-win strategy.

Resolutions for 2012:

  • Write more posts like those above.
  • Use more visual resources and hands-on materials.