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/

People who are too concerned about a problem are the least ones capable of figuring its answer. That's why I am so ashamed of telling people about Operations Research: how come that we have not found an answer for the issue of whether P=NP after so long? For instance, some years ago I took a taxi to the airport after attending to the Brazilian OR Symposium. After explaining the reason of my trip to Goiânia, I told the driver about the Traveling Salesman Problem and how solving it well would be worth a million dollars. He could not believe it. I mean, if I had been more confident when I told him about the million dollar prize, he would leave me half way and try to solve the problem himself. After all, he has been looking for and finding short routes for quite a while in his profession. So much a piece of cake that I thought: maybe I have been driven through bad directions after a while in this field.

(Happy April 1st! May this mock proof of P=NP enlighten your thoughts!)

And I think I got it now! I was not smart enough to figure it through the Traveling Salesman Problem, but the 3-SAT became a lot more easier when I tried using the most elementary reasoning! You know that kind of stuff that all kids learn when they have 10 years old? It works, and quite better than any stuff of discrete mathematics books! Say you have a 3-SAT problem like this: (X or not Y or Z) and (not X or Y or Z). And you just, sort of, "multiply" all of it: X and not X or X and Y or X and Z etc. Isn't it the same problem? Also, isn't it surprising that, after doing this thing of "multiplying" stuff, you just have to check if there is a term that can be satisfied regardless of the others? For instance, in this case I know the instance is satisfiable because I can have X and Y set as true and the second term is true. It is just a matter of a linear-time check over my new input. Where is all the problem of which people have been complaining for so long?

(The argument is indeed correct, except that the size of the transformed input is exponential if compared to the original one).

C.Q.D. Q.E.D. and sorry for finishing a job that so many people are dreaming about solving! In fact, it was so easy that I think that this proof is not worth being published anywhere else than in this blog. And now that OR is not a challenge anymore, I will try to solve something a bit harder: São Paulo's traffic-jam issues. Have a good April 1st!

(Or maybe I should learn how to explain correctly the Traveling Salesman Problem, instead of creating false expectations).

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:

• eating cheese bread (pão de queijo);
• eating Pan’s chocolate popcorn;
• taking an outside look at the São Paulo Art Museum (MASP);
• hanging around in the Paulista Avenue;
• wasting a worthwhile afternoon at our best bookshop (Livraria Cultura);
• taking an inside look at the São Paulo State Art Gallery (Pinacoteca do Estado);
• watching the audiovisual show of the Portuguese Language Museum;
• crossing São Paulo’s weird-but-awesome cable-stayed bridge (Ponte Estaiada);
• having a sushi at the Liberdade district or a pizza at the Bixiga district.

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:

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:

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 red wine, not white. Anyway, it is still possible to taste 7 out of the 9 wines at once.

Tatu-Search Optimization 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.
• Prove that P=NP on April 1st.

People are having fewer children, families are becoming smaller but some combinatorial problems involving them are becoming harder to solve. New families are facing harder planning and scheduling problems during Christmas and other holidays than their parents or grandparents ever did. Anyway, that’s an interesting way to explain what over-constrained problems and soft constraints are.

Suppose that you are the head of a family and you decide to run a party at Christmas evening or a banquet in the day after. One or two generations ago, it was not that hard: people used to live closer and have lots of children (I mean, more than two at least). In such case, it would not be a disaster if five out of your nine sons are not able to come over. It might be the case that families sharing common members agree on celebrating at different times. Anyway, the other parties would be so close to yours that everybody would eventually step by sometime.

However, with fewer children, people easily moving far away to pursue a career or for resting after retirement, divorced parents and grandparents running concurrent parties (maybe four grandparents married to four step-grandparents sharing a single grandchild), we must agree that pleasing everybody might become impossible.

That´s roughly what happens when some companies look for the help of an Operations Research consultant: they have a set of resources to produce goods or deliver services to their costumers and they are not sure if it became impossible to support the increasing demand with what they have or whether if they are only having a harder time to find a solution.

It might be the case that some constraints are not as important as it appeared to be. An over-constrained problem is said to be a problem upon which too many constraints are imposed, ruling out any possible solution. Looking carefully to the set of constraints, one might realize that some of them represent desirable but not mandatory situations, in which case they actually represent what we call soft constraints.

In the case of the families, what does a couple with no children and four parties in four cities at two different times do? At least in my case, we have to split in order to meet the scale. In the future, we aim at tackling this problem by running the party ourselves. :-)

A conference about mathematical modelling in industry is going on at the University of São Paulo. I'm very impressed by the ambition of the event still on its first edition: three full days with three simultaneous tracks involving experienced speakers from varied countries. There are sessions of applications in flow simulation, new materials, aerospace, finance, medicine and much more. To be honest, I've no idea about many of the techniques mentioned on the abstracts of the program. I hope to leave the conference a bit less dummy about them. As usual in most of conferences I've been attending lately, I'm about to meet people working in my company that I've never heard about. I like it.

Despite everything I've written about, what really cheer me up about an event like this is that there is a huge gap between academia and industry in Brazil that we need to reduce.

If you want to know more about the event, check the website of the International Conference on Mathematical Modelling in Industry. If you are close by, the event is for free and you can subscribe at the front desk.

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 faculties 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 very poorly studied in Brazil, including the one I’m working with, but there are many others in which Brazilian research is leading edge as the article itself pointed out. Broadening our range of expertise is much more a matter of establishing more universities and forcing them to concur 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, what 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.

There are many ways in which one can devise the importance of O.R. to protect our environment, many of which dealing with optimization problems related to directly reducing the costs to prevent its destruction and so on. However, what about the environmental impacts of our patterns of consumption? Shall we change our way of living dramatically or rather find a balance between what we want and what we can use from our environment? Maybe O.R. can help us on that.

Roughly speaking, Operations Research (O.R.) deals mostly with finding the best way of doing something subject to a lot of different kinds of restrictions. Thus, one can indirectly consider the protection of the environment whilst solving a wide range of different optimization problems related to the daily needs of our society. For that sake, I figure two possibilities to consider the protection of the environment:

• pricing natural resources appropriately as a subtraction to the profit of the operation;
• limiting their use so as to avoid that we steal the share that belongs to the future generations.

I’ve already written about the first possibility in my post about optimizing public policies for urban planning. My girl and I devised a model to consider the environmental costs of subsidizing low income housing units at different parts of the city in what comes to daily displacement to work. However, finding the right data to run the model turned out to be our biggest problem. When one defines a penalty to the environmental impact related to the profit of an operation – for instance, using the value of carbon credits – it represents a cost to the problem. However, sometimes we might not have data to price it. But if the consumption of a given natural resource is limited by a constraint instead of penalized in the profit, it is still possible to figure the economic importance of such resource through duality. Therefore, let’s take a look at the second possibility as an alternative to finding the price of natural resources – as well as avoiding an excessive use of them.

The concept of duality in linear programming allows us to associate costs to our constraints. Suppose that our optimization problem is about finding the amount of goods of each kind to produce in order to maximize the profit that they generate subject to the limited resources available. The dual of this problem consists of finding the price of each unity of our limited resources in order to define the minimum price at which it is worthier to sell them instead of processing subject to how much profit each finished good would give us. The relationship between those two problems is quite strong: if a resource is not used up to its limit, its dual cost is zero – meaning that it does not have an economic importance according to the model. Therefore, duality can help us devising how much a limited resource is worth (if it is worth something) and thus provide a way of valuating resources according to their limitation and importance. 

As a matter of fact, the more you understand the relation between primal and dual problems, the easier it becomes to talk face-to-face to economists. Indeed, this topic has a lot to do with the 1975 Nobel Prize in Economics. If you want to know more about that, the prize lectures from Kantorovich and Koopmans are a good starting point. 

This post was written to the September’s INFORMS blog challenge: O.R. and the Environment.

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 helped 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.