Tweeting #ismp2015

ISMP 2015 was an amazing conference for the diversity, depth, and quality of the talks. But besides that, it was also a landmark for online coverage of OR meetings, as some active online contributors have noted:

As an example of the latter, look for #ismp2015 on twitter and you’ll get the most detailed ever journal of an OR conference I have seen.
Jean-François Puget: Where Is Operations Research In Social Media?

Indeed, it was impressive to see sequences of tweets about two or maybe more simultaneous talks, which made you feel like achieving that sweet spot of being able to somehow attend every interesting talk that you found in the conference proceedings.

But what has changed? Speaking for myself, I have decided to follow what I saw Jeff Linderoth doing for #mip2015 and David Morrison for #informs2014: I just tweeted every interesting or funny piece I saw (battery allowing, of course), and mentioned topics discussed in talks to make those who were not attending get a taste of what looked hot.

In addition, I was also maintaining the account @ISMP2015, which I used to retweet as much as I could from the relevant tweets while avoiding to put too much of the same thing. I don’t know how much doing that helped, but what I noted as the conference days passed was that people were becoming more active: those who would publish just occasionally were now more frequent, and some who were not tweeting at all have decided to do so.

What makes me believe that the level of tweeting was raised by peer observance was how limited its scope seemed to be: sometimes most of the tweets came from a single session, and many people in other areas simply did not tweet during the event. But since it was something that did please those who did not attend, I believe that the behavior will spread further and possibly #ismp2015 will be surpassed by #informs2015, who knows?

While I cannot claim with certainty that a conference account for retweets makes a big difference, I believe that it is an idea worth trying in future meetings. If not to incentivize people to tweet more, at least to record a good deal of what was going on. After all, someone has to chase those guys who do not use hashtags correctly!

Getting to the coolest part of a PhD: Conceiving ideas and discussing with people (in any order)

I always pictured being a PhD student to learn new things by myself, go after other people on campus with which I could endeavor great projects, and make a great impact by consequence. Well, it took 18 months into the program to get over coursework, qualification exams, and the crucial third-semester review. While craving for this moment since I was applying for PhD programs, the training was definitely worth it. It corrected several misconceptions (some quite ugly, I have to admit) and keep polishing how I think and work (or else, how picky I am with my own ideas and writings).

Now I have been reading more, sitting in random classes out of curiosity, and going to diverse seminars. But getting to meet and productively discuss with other people takes more than that, and here are two approaches I have found quite useful for this purpose:

Dinner discussions at the INFORMS Student Chapter

Starting from the assumption that everybody has to eat dinner and Monday is not a busy night for most, my colleague Tarek Elgindy suggested that we could meet every week to discuss a topic of interest to someone in the group. This became the main activity of our recently created INFORMS Student Chapter.

I contributed with a talk about lift-and-project normalization, which was mostly a lecture on the board in which I presented the main results and current issues to colleagues from my PhD program. Not only it was a good exchange of ideas, but also a great training for teaching since some of them are just learning about the topic. It also helped me adhering to the trending idea that board presentations are much better than slides. Besides, it also helped me training to be ready for “almost impromptu” talks: one of Tarek’s claims is that we are not supposed to over prepare to such discussions, and in fact mine was just summarizing formulations from a few papers I have been reading for research.

Speed networking thought CMU’s Public Communications for Researchers

I recently became officer of PCR, a student organization that has been very successful in training communication skills of graduate students at CMU. Along with Rohit Girdhar, my role is to conceive and organize social events to complement the other activities PCR has been doing. Our first attempt was a speed networking event, which was aimed at introducing people from diverse fields to each other in the hope that they start collaborating. While attendance to this first event was small and we had to break it to a group conversation instead of the traditional pairing of people, some interesting possibilities already came out of the group. I am confident that we can make it work in a larger scale by reflecting on what could be better, in particular when it comes to attracting people and advertising the event.

My 2014 take-away

(Originally posted in the 2014 INFORMS blog).

I came to San Francisco aiming to know what is going on in the field. In most part, I have tried to stretch the boundaries of what is in my comfort zone. The result has been awesome: I got aware of many interesting research work going on, of great people behind them, and also got some interesting notes for my own research agenda.

Besides that, I met in person a number of people I have been following online, like Sertalp and Pelin Çay, Marc-André Carle, and Marco Lübbecke (got all your special characters right?). Not to mention those I saw before in the 2012 meeting. We even managed to promote a sequel to the official tweetup in a local pub before the last conference reception!

Finally, participating in the chapters/fora meeting was instrumental for me and Alex Kazachkov, my colleague at CMU who lead the foundation of our student chapter. I hope we can soon put some interesting ideas we heard here in practice.

Hope to see all of you next year in Phillie!

PS: Thank you for the iPad, Gurobi!

What prospective PhD applicants can make out of the meeting?

(Originally posted in the 2014 INFORMS blog).

In 2012, I went to the INFORMS meeting in Phoenix aiming a bit of everything related to applying to PhD programs: I wanted to show my research work as a master’s student, engage with the ORMS community in as many ways as I could, get a feeling of what life as a graduate student in the US would be like, get to know more about the schools I was intending to apply, and even get acquainted with other areas of research that could interest me (an exhausting list just to read, isn’t it?).

Two years later, here I was in Phoenix again, waiting for my connection towards SF while writing this. Looking back at those days and thinking about the Portuguese poet who said that there is nothing that could not be made any better (which also means that there is infinite room for ORMS in anything!), I believe I did a good job back then. In many ways, that was thanks to amazing people willing to share their experience and give invaluable advice. The best thing about INFORMS is the people you get to know.

Even though things went well and I got where I wanted, I am an optimizer and I cannot help but think of how they could be even better. Hence, if I were to go back in time and talk to the 2012 Thiago Serra with all those goals in mind, the one thing I would say to him is to be even more ambitious in learning about other areas. This not only broaden your application perspectives, but is extremely important in the long run either in the academia or in the industry.

The only problem, of course, is that you will soon realize that you can easily end up with a conference schedule in which you are supposed to be in 2 or 3 places at each technical session. But this is the sort of problem one should be glad to have!

Heading to #informs2014 tomorrow!

Starting tomorrow, I will be in San Francisco being one of the bloggers of the 2014 INFORMS Annual Meeting.

Since the beginning of my PhD at CMU, I haven’t posted at all and probably will only resume for good in 2015. The experience of pursuing a PhD is amazing, but the first 3 semesters are very intensive in course taking and also include a research project. I have been learning a lot, and I hope to put some of it here when resume blogging often!

On the pursuit of a PhD program: What would be your ‘School of Sagres’?

As a native Portuguese speaker and descendant, I was told in history classes about the so-called School of Sagres. This school is regarded as responsible for many technological advancements between the XV and XVI centuries that enabled, among other things, the first world circumnavigation (and nowadays puzzle people from other cultures for the fact that the language of such a small country like Portugal is spoken in almost all continents and borrowed words to diverse cultures like the Japanese and Indonesian). However, there was never a physical place with such label: some historians now believe that it was simply a gathering of the best European experts along taverns in the Iberian Peninsula. This is somewhat what I feel about the academic world, and five centuries later I wanted to find the best corridors along which I could move my coffee mug while pursuing a PhD degree. And the experience was an interesting one!

I wondered whether to pursue a PhD or not for quite a while. During such time I earned a MSc degree, kept publishing the results of my work, explored some topics that could be the subject of a doctoral thesis, and interacted as I could with the OR community. Despite doing all of this, I was yet undecided about pursuing a PhD mostly because I already had a good job in the industry doing what I like – something that I meant to have after obtaining a PhD. It was at such point that I went to ICAPS last year, and I had an intense week that reminded me of many good things from academia that were absent from my work routine. In the following week, I was already studying for the TOEFL, and the application process was only over a couple of months ago. As a result, I got some amazing formal offers, some polite rejections, and gave up on some other ongoing applications after receiving those offers.

The application process and the general tips to excel at it abound on the internet: apply only for places to which you would definitely go if offered admission; ask for recommendations from professors that know a lot about you instead of those who gave you the best grades; do not attach yourself to specific lines of research, specially to methodologies; let it clear why you would like to pursue a PhD; be concise; etc. However, I read little advice about how to effectively target schools. I have heard from very successful applicants that I should try every top school that I could, but the fact that I could barely see myself in many of them made me include in the list a few more than those in which I was already planning to apply. As a matter of fact, all of my formal offers came from applications in which I mentioned faculty members and extensively discussed common interests in the essays. Some of those schools were in my radar as the obvious choices for my interests but there was an outlier which was somewhat a surprise: I decided to apply to that school only after accessing their website for the second time and reading every word about their program. Despite that first impression, I ended up feeling that it could be a good match, they felt the same way upon reading my application, and that made the final choice even harder!

Choosing among those programs who replied positively was difficult for the same reason that I had such an enthusiasm for applying for each of them: I read about what they were doing, I feel that I understood what they were targeting, and I wanted to be part of each of those efforts. And then everyday new information came to me that tempted me to accept one of those offers, but it was the fact that CMU was my top choice before receiving any offer and that visiting the school did not change my impression of it which make me accept their offer. Declining the other offers was very hard and belated second thoughts are inevitable, but I feel that I would have deeper regret feelings if I had chosen differently. Besides, I have an entire career ahead to join those schools in other ways that not as a student.

In short, the most important advice – and the only one I would dare to offer to a prospective student already full of them – is to focus more on those schools that are closely related to your interests, but still make a comprehensive scan of the programs out there in the hope to be surprised. There are too many great schools and some of your friends will advise you to try a lot of them, but the fact that you are unable to make a strong claim for studying somewhere also means that your chances in this place are smaller and you are wasting time that could be used in other applications. When you find your personal ‘School of Sagres’, words go out much more easily.

A new home in many senses: My blog, my city and my workplace

As opposed to my blog’s activity, a big change has started in my life since that last post in February: I got some offers to pursue a PhD degree abroad, visited two schools in March, decided to join the OR program at Carnegie Mellon University, and am preparing my relocation to Pittsburgh since then.

If it was not by the fact that Posterous is shutting down, I would take a bit longer to post again. After applying to doctoral studies and prior to receiving those offers, I was having a great time writing about some topics of my interest and I want to resume that soon. In addition, I am looking forward to share some thoughts about the doctoral application process: it was a bit stressful, but it was a great opportunity for self-discovery and to get acquainted with people sharing similar research interests.

Until then, please update your bookmarks and subscriptions to keep following my blog!

The pursuit of asymmetrical models in CP: Backtracking hardness is, after all, a tricky business!

Last week I wrote a post on the effectiveness of using backtracking alone to solve combinatorial problems. It was an interesting exercise to develop the discussion from theory to practice and back to theory again. However, there was a mistake in that development. As pointed by Jean-François Puget in his comment, it is possible to add a small number of symmetry breaking constraints to efficiently refute that class of infeasible instances of the pigeonhole principle used as example. After all, what was actually claimed by the theoretical development that I shortly mentioned is that the refutation of a specific formulation of the problem has an exponential lower-bound. While that could be a case for using a global constraint, it could also be addressed by symmetry breaking.

Symmetries arise naturally in combinatorial problems, but the extent to which they cause concern varies with the solving method used. They matter a lot for backtracking because of their impact in the size of the search space to be explored. We have a formulation with a symmetry breaking constraint if, compared to the formulation without such a constraint, only solutions differing by symmetry from the solutions of the more restricted formulation are feasible for one and not for the other.

There is an intuitive notion that symmetry breaking is a good thing, but care must be taken: what if it makes an easy problem harder? It might be the case that the original problem was underconstrained and additional constraints would rule out exactly the solutions that are easier to find, therefore making the search longer than without them. However, that was not the case of the problem in the previous post and is not likely to be the case in most applications. It is even interesting to ask if there are conditions in which this can be in fact observed.

Nevertheless, symmetry breaking is a bit challenging because it requires taking into account the whole formulation instead of reasoning about each constraint separately. For each symmetry identified in a subproblem, we may come up with an additional constraint that introduces information about the problem context that breaks it. As a consequence, symmetry breaking inference mechanisms cannot be encapsulated within global constraints and we are left with two options: expect good formulations from the modeler or develop some sort of general mechanism to find them.

The current practice is based on the former option, and thus the expertise of the modeler plays an important role in the process. However, the quest for a truly autonomous solver of broader use would demand further advances in the latter possibility. Honestly, I was not aware of the importance of reformulation until thinking about all of this, and it made me look again for Barry O’Sullivan’s paper at AAAI-10 discussing the automation of both modeling and solving. Among recent papers, it is a good start on the topic.

In conclusion, proving that backtracking cannot suffice is a bit trickier that I thought at first. Unless P=NP, there must exist an asymmetrical CSP class (or at least one for which breaking its symmetries would not be an easy problem) with lower-bound refutation asymptotically worst than any polynomial function in the size of the problem. If such a class is yet unknown, the interesting part of looking for it would be to find a number of general inference rules for symmetry breaking that we could use to solve other problems.

Why backtracking alone cannot suffice to solve combinatorial problems: CP perspective, empirical hardness models evidence, and proof complexity results

Constraint Programming (CP) is a technique with particular strength to solve classes of combinatorial problems for which global constraints were identified and exploited in the design of specialized algorithms. However, I have been convinced that CP is, above all, a general model to understand combinatorial problems and their solution – using the term ‘model’ in a broader sense, as explained in a previous post and based on John Hooker’s article at CP Letters.

Regardless of the solving method used, the classic aim of CP is to tackle the Constraint Satisfaction Problem (CSP), which ultimately encodes any problem involving variables with discrete and finite values as the intersection of the regular languages defined by each of its constraints. When special properties are observed in a class of such languages that would allow us to make strong and efficient inferences among those variables, we have found one of those so-called global constraints. Not surprisingly, the concept is in fact a formalization of the widespread practice of exploiting problem structure, which was also discussed in a previous post linking the implementation of local search operators to CP concepts.

In spite of such claimed ‘agnosticism’ regarding solving methods, CSP solving is often associated with backtracking search algorithms. The rationale is that, if compared to other general solving techniques like dynamic programming, backtracking scales better in memory use with the size of the problem being solved. As a consequence, CP lectures and many lines of research are developed with the premise of using backtracking-based search. In practice, however, that post on CP and local search also points that the converse is true: local search methods like variable neighborhood search have been successfully used in commercial CP solvers.

One of such lines in which backtracking was extensively studied is the adaptive selection of algorithms, which is aimed to select the most suitable algorithm to solve a given instance according to predictive models of performance. From the characterization of CSP instances by means of properties like constrainedness, which is the ratio of pairwise constraints to variables, empirical hardness models were developed that also documented easy-hard-easy phase transitions. In short, it is easy to solve an unconstrained problem or to infer that an overconstrained one is unfeasible, but those in the ‘feasibility frontier’ are much harder to solve. A short reference about the topic is the 2005 article of Carla Gomes and Bart Selman in Nature entitled ‘Can get satisfaction’, and a precise figure of such hardness can be seen in the graph at slide number 6 of Kevin Leyton-Brown’s talk at the Workshop on Beyond Worst-Case Analysis.

Although a well-documented phenomenon, until very recently it was yet unclear to me why this happens. I was only convinced of it this week, when I came across some lecture notes of KTH Professor Jakob Nordstrom on proof complexity that discussed the resolution of formulas for the pigeonhole principle. Proof complexity is a discipline concerned with understanding the hardness of theorem proving, and comprises the study of characteristics and strengths of different proof systems as well as their equivalence. Among such systems is resolution, which is equivalent to solving through backtracking a CSP in which variables can only assume two values – true or false, or 0 or 1 – and constraints only use the logical operators NOT, OR, and AND in Conjunctive Normal Form (CNF): a set of clauses using NOT and OR joined by AND. This is a special form of the satisfiability problem, or simply SAT, for which the backtracking search with only local inference corresponds to the well-known DPLL algorithm.

The pigeonhole principle states that it is not possible to assign n pigeons into m pigeonholes without putting two of them in the same pigeonhole if n > m. It turns out that encoding an instance of this problem in polynomial size in n and m such that n = m+1 as a satisfiability problem (SAT), i.e., a CSP with variable domains of size two and constraints built of logical operators in CNF, results in an unsatisfiable problem that requires an exponential lower-bound resolution. That happens because a valid refutation requires exploring a large number of combinations of assignments to prove that none would lead to the satisfaction of the problem constraints. [check the erratum at the end of the post]

In short, backtracking really needs global constraints!

Erratum

According to the first comment to this post, there is an enconding for which the mentioned refutation is efficiently found. The discussion is continuned in the sequel of this post.

The problem with the problem

Operations research is a field with many problematic words, of which ‘problem’ is an interesting example. The word is generally used to describe a difficulty, but it has found an additional meaning in mathematics as a well-defined question that one may use an algorithm to answer. That would not be bad if it was not by a problem (of the first kind): both meanings are often interchangeably used.

The unavoidable consequence is that new developments targeting a given application sometimes present a meaningless criticism against mathematical problems, which are abstract entities that exist in spite of their use. Such a concern may sound pedantic because the mathematical problem is usually only serving as a proxy to its interpretation as the solution to the problem (of the first kind) associated with a given application. However, this bothers me because it is the tip of an iceberg of misguided conceptualization. And, of course, that is not how one should treat guys like the poor traveling salesman and his problem, who did not intend to do any harm against the problems of others.

Even though this is not a common mistake among reputed researchers in optimization, it happens pretty often among those in fields that need optimization as a means but do not delve further into theoretical concerns. This is bad because many of them go to the industry and will eventually come back to hire an expert in operations research to solve their most challenging problems, which will also involve detaching their needs from fixed ideas on how to model them.

I have already written previously about the meaning of problem, model, and solution in this blog, but coming across yet another bunch of writings and sayings with similar issues made me do it again. Personally, I only realized the problem with that after talking about my work with people in other fields, to which a problem has only one meaning (the full story is on that previous post). If I ever have the opportunity to teach an introductory course on OR, I would try to make this point clear in the most funny way that I could conceive (the funny part takes longer to be forgotten). As a matter of fact, this issue reminds me of a poem of my favorite writer. It is entitled XXVIII and is from The Keeper of Flocks, a book written by the Portuguese poet Fernando Pessoa under the name Alberto Caeiro (translation from the blog Fernando Pessoa: Alberto Caeiro: Complete Poems):  

 

Today I read almost two pages
In a book by a mystical poet
And I laughed like someone who’d cried a lot.

 

Mystical poets are sick philosophers
And philosophers are crazy.

 

Mystical poets say flowers feel
And they say stones have a soul
And they say rivers have ecstasies in the moonlight.

 

But flowers wouldn’t be flowers if they felt,
They’d be people;
And if stones had a soul, they’d be living things, they wouldn’t be stones;
And if rivers had ecstasies in the moonlight,
Rivers would be sick people.

 

You need to not know what flowers and stones and rivers are
To talk about their feelings.

Talking about the soul of stones, of flowers, of rivers,
Is talking about yourself and your false thoughts.
Thank God stones are only stones,
And rivers are nothing but rivers,
And flowers are just flowers.

Me, I write the prose of my poems
And I’m at peace,
Because I know I comprehend Nature on the outside;
And I don’t comprehend Nature on the inside
Because Nature doesn’t have an inside;
If she did she wouldn’t be Nature.

Continue reading “The problem with the problem”