Blog

Posted on

How Analytics makes Operations Research the next big thing

Engineers enjoy laughing at buzzwords that they don’t sell. Despite that, some buzzwords represent important paradigm-shifts. They might not propose any technical novelty but they do contribute to empower our methodologies by valuating the presence of certain skilled specialists in large scale projects. Analytics is one of them: it represents the application of IT to support business decision processes. This post aims at showing that its existence can help leveraging O.R. practice in the industry.

The O.R. filet: there is no such thing as a free lunch!

Who did not wondered about that dream job in which all you have to do is what you do for fun? Suppose that you are an O.R. analyst hired by a company which provides you perfect data and a well-defined problem that you know how to tackle. And that’s not all: they do not underestimate the amount of effort that the project will demand from you and your co-workers. In such a perfect world, you just pick that traveling salesman or bin packing problem with that idealistic instances and expend some time experimenting your favorite techniques until you get satisfied with the results. You would probably finish your work very early and have the rest of the day to share a beer and French fries with your friends at the bar (if that happens in São Paulo).

Back to real life realm: from problem solver to problem finder

Unfortunately, there is a huge gap from being hired until possessing that well-defined problem and that perfect data. That is, if you manage to reach that point. If companies had already all of that figured, they would probably have gone beyond with an in-house approach to their decision problems. In such case, the benefit of an external OR consultant work would be often quite shy. Hence, one must mind that the work is not only about solving an optimization problem but rather helping the company to understand what the problem is and how to collect data to properly solve it.

Some interesting discussions about those issues have been recently raised by a couple of OR professionals called Patricia and Robert Randall on their blog Reflections on Operations Research. They have a blog post about data cleanup and two other posts about understanding what is the right solution for the client’s problem (by the way, I’m waiting for the promised sequel – check the first and the second posts).

And then the O.R. team becomes the Analytics division…

What I exposed before reflects the change that is going on in industry, including my workplace. The O.R. team is no longer called once someone “magically” finds an optimization problem that must be tackled within an IT project. By “magic”, I mean that someone working in a project knew about O.R. by chance and decided to invite an O.R. analyst to check it. Instead of that, new projects are supposed to pass through a preliminary assessment of the need of an O.R. approach. The analytics professional comes into scene to complement the team of software architects, software engineers, data modelers, project managers and stakeholders of any non-ordinary project. The role of that professional is to understand how the system can be used to support business decision-making and define whether statistics, data mining or operations research tools are required to accomplish that. Such assessment avoids that something pass uncaught or misunderstood and, of course, creates lots of interesting opportunities for O.R. professionals both at the assessment and later at the project development phase. As a matter of fact, we have plenty of people ready for the job, as I told last month in a post about O.R. job market in Brazil.

A gain-gain scenario: let’s spread the word about Analytics to empower O.R.!

An Analytics assessment of strategic projects would endorse a broader application of Operations Research, what usually means maximizing profit and reducing costs. Moreover, there is a huge workforce available to the demand that such paradigm-shift would incurs, including me and probably you. So let’s make that happen!

This post is my contribution to the INFORMS’ blog challenge of May: O.R. and Analytics. The INFORMS’ blog challenge consists of a monthly topic about O.R. that is proposed at the INFORMS’ blog. If you happen to write about the topic of the month, send an e-mail to them to get your post mentioned.

Posted on

Revisiting operations research elements – part II: results, research… and failure!

This post resumes the discussion about key concepts of operations research started previously in this blog. However, instead of focusing only on the meaning of terms, this time I’d like to discuss about which results are worth of publishing and the unacknowledged importance of failure.

Are you the “brand new champion”?

“I never knew a soul who ever took a licking.
My friends have all been champions at everything.”
(Fernando Pessoa, Portuguese poet)

For a while, I thought that the idea described by Fernando Pessoa explained what happens in O.R.: an article is only worth of being published if it has noticeable results. However, which results are we talking about? In “Testing Heuristics: We Have It All Wrong”, John Hooker stresses many concerns about how results-driven approaches have been transforming research into plain development. He summarized most of them by the maxim “The tail wags the dog as problems begin to design algorithms”. In fact, such concerns were wide spreading by that time. In the article “Generating Hard Satisfiability Problems”, Bart Selman and others warned that bad benchmarks may lead to wrong conclusions about how hard a problem is and, conversely, about how good an algorithm to such problem is. Moreover, theoretical results such as the No Free Lunch theorems state that there is no best overall algorithm and there are always weaknesses to be acknowledged. Otherwise, it would not make sense to talk about a subject called meta-learning, which aims at selecting the most appropriate algorithm to solve each problem instance.

I remember to hear about the importance of reporting bad results in experimental physics classes, but that was quite lost in my mind after my junior and sophomore years. The big picture suggested by Selman’s group and Hooker was that many approaches being done in the area strive to be claimed the best one to solve a given problem at the cost of biasing the tests towards situations that are better suited to what is being proposed, intentionally or not. Besides, hardware differences, coding abilities and several other issues might influence what is being presented. Minding that metaphor that I used in the previous post, one must not confuse the power of an idea with the performance of a source code when dealing with a given benchmark set at a given machinery architecture. For instance, if someone is proposing an algorithm that explores fewer branches during search, it would be better to measure the number of branches instead of the running time, since it might be the case that a bad choice of data structures might hinder an adequate comparison of different techniques. Hence, one must strive to write an article that does recognize when its solution fails along with when it succeeds, whilst striving to diminish perturbation factors on its results.

After all, operations research is research, right?

What would you answer if asked that? I let it go unanswered last time. Most often, O.R. does involve scientific research: if the problem being solved was quite simple to skip that part, it would be unnecessary to have someone thinking about it. Since I was asked that while working on a long-term project, that was quite true. Notwithstanding, even if there is no scientific research involved, O.R. is still sort of a research: one wants to find the most appropriate way of performing certain operations. Therefore, some of the subtleties and misconceived concepts mentioned previously come from the differences among scientific research and operations research: research involves a problem, solutions and it may fail sometimes. Indeed, the word research in O.R. is also the same used to denote research in terms like R&D in Brazil (pesquisa), Portugal (investigação) and France (recherche). Not surprisingly, the list of ambiguous terms is far from complete. For instance, programming means both planning something or the act of producing computer code, as stressed by Lusting and Puget in the article “Program Does Not Equal Program: Constraint Programming and Its Relationship to Mathematical Programming”, in which they explain why it means both things for mathematical programming but just the later for constraint programming.

Yet another conclusion

I have decided to place the most important conclusions along with the most confusing term of the previous post – solution, but I can repeat them once more. Being aware of the differences between the common O.R. terminology and what researchers adopt anywhere else is important to be more effective when spreading the word about what you did beyond your close peers. In these two posts, I aimed at sharing some thoughts that I would be glad to have heard before. In order to succeed with that, I had the valuable help of my fiancée Sabrina, which helped me by revising this text in order to avoid that I committed the same mistakes that I was pointing. It might still not be completely accurate or clear cut, since I’m just a graduate student striving to figure out my area.

Posted on

Drug discovery optimization: a meeting point for data mining, graph theory and operations research

How can I help finding the best compound to save a life?

In a glance, the answer is what research in optimizing drug design is about. Its main goal is to cheapen and speed-up drug development whilst producing more effective and less toxic pharmaceuticals. It is an interesting topic that involves much of what business analytics and optimization professionals use daily to solve problems in many other areas. For that reason, I decided to write about that for April’s INFORMS Blog Challenge: O.R. in Health Care.

Drug design basics: in vitro vs. in silico methods and QSAR analysis

Before a drug can be prescribed to humans, it must pass through a careful evaluation. However, it would not be reasonable or even feasible to test every possible compound for each desired effect, especially if such tests involve animals. Pharmaceutical researchers are interested in screening molecules on a huge data set, so that only those molecules that are most likely to work are ultimately tested in vitro, in animals and ultimately in humans. They accomplish that with computer-aided predictive analysis commonly called in silico tests.

In silico tests are designed in the belief that there exists a valid theory to extrapolate quantitatively the activity of a compound based on similar ones, using tools like Quantitative Structure-Activity Relationship (QSAR) analysis. The goal of a QSAR analysis is to find a function capable of predicting the activity of the main molecule of a compound based on the presence and quantity of certain molecular substructures. We are then lead to the quest for a way of representing molecules and to use available data about an activity to create trustable predictions for similar molecules.

The role of data mining and molecules as graphs

For many purposes, a molecule is just a graph with vertices and edges. However, the fact that molecular data are more structured does not mean that the problem is easier. Roughly* deciding whether one graph can be found inside another one is know as the Sub-Graph Isomorphism problem. That problem is NP-Complete, what means that there is not know an efficient algorithm to solve it.

(* By roughly, I ask you to forgive the lack of formality in which I defined sub-isomorphism: graphs are not said to be inside each other. A one-to-one correspondence between one graph or sub-graph and another one is called an isomorphism. However, if I was to tell it at first, I would lose most of the audience.)

More than just finding a sub-graph isomorphism, one is usually interested in find the most frequent ones. One interesting approach to Frequent Sub-Graph (FSG) mining is gSpan, a DFS-based mining algorithm proposed by Yan and Han. It consists of defining a unique lexicographic encoding for each sub-graph so that it can be counted more easily while exploring molecular data. There is also a controversy about the validity of 2D models such as graphs for modeling molecules, specially because some geometric subtleties differ a innocuous molecule from a a carcinogenic one. Thus, it is worth of notice that predictive models are not intended to skip in vitro tests but just point out which molecules are most likely to work out.

How can operations research fit in?

There are a number of O.R. applications for what we have been discussing here.

I would like to mention one interesting application of Linear Programming (LP) to QSAR analysis by Saigo, Kodawaki and Tsuda. Their approach consisted of using LP to build a regression function for prediction in which error is minimized. It is based on positive and negative relations between molecules and activities, that is, a quantitative relation among each molecule and the activity or a constraint imposing that such relation is not relevant. The decision variables of the problem are the coefficients associated with every possible substructure. Since there can be a lot of possible substructures, they start with a small problem and there is a column generation algorithm that tries to find a new variable whose addition to the problem might improve the results.

Final remarks: OR and the invisible good

The fun of many professions is to see the benefit of what you are doing. That is even more present in health care, since you are dealing with people and their lives. On the other hand, OR is the kind of invisible science, which is on its best use when the average people can not sense its presence. Notwithstanding, OR practitioners enjoy numbers and are glad to know that things are a bit better because of their work behind the scenes. Despite that, blogging about OR can help people notice the importance of the area to support others that are commonly visible to everyone.

I would like to thank my mother-in-law for some helpful advises to write about QSAR.

 

Posted on

Brazilian IT (and OR) salaries, and our rickshaw-like cars

Contemporary economy and the rickshaw-like cars

The first elected president after the military dictatorship in Brazil was quite a controversial figure. He was responsible for the first steps towards opening our economy to free trade. By that time, he argued that the Brazilian cars were like rickshaws. Still, two decades after, I bought a brand new car from FIAT whose floor gets wet inside when it rains. Nevertheless, things have been changing quite a lot due to what he and his successors did.

IT demand and IT paycheck

Due to a number of favorable conditions, our economy is growing faster now. That implies a greater demand for qualified workers, what includes IT experts. However, both Brazilian and foreign companies are reacting as if a free lunch was still possible: they complain about the scarcity of high skilled workers but also say that the available professionals are asking too much to be hired, as told on a report of Info magazine. It might be true that many people are earning more than their technical skills deserve, but that only happens if the recruitment process is scant. Besides, such higher salaries only exist because some employers sensed that IT has a great value in their business. Such conclusion became crystal clear to me when I saw a debate among three professionals in a class of optimization in finance at IME-USP. Two of them were agreeing on that common-place complaint when they were interrupted by the third, which has just arrived in Brazil to start a branch of his investment firm. In his opinion, technical skills are not as valued in Brazil as interpersonal skills are, which means that a salesperson earns a lot more than those that make things work behind the scenes.

What about OR?

I wish I could say that things are better for OR analysts here, but that is not often the case. Albeit the fact that our profession demands higher academic degrees and the availability of technical resources is not so generous when compared to what is offered to software development, the relation between workforce offer and market demand is smaller. In São Paulo state, I would guess that there are as many specialized consulting firms to work in as there are good degree programs involving OR, which means that those firms can bargain salaries very easily. Instead, I think that it is better to be an OR specialist outside such consulting firms, moving towards the end user or bigger software houses. Doing that, you can be considered as an IT professional that is specialist in strategic software, which alone means a better paycheck. Of course, there is yet another option: starting your own consulting firm.

Is it the end of “rickshaw-like salaries”?

For the good of our profession and all those which are very specialized, things have been changing a lot. Brazilian companies like Petrobras and Vale have been investing a lot in research institutes as well as on hiring and valuating high skilled professionals. Besides, foreign companies like DuPont, GE and IBM have decided to create research units here, whilst other companies like Google are developing their products here (as opposed to simply adapting them as global manufactures have been doing for ages). I read somewhere that there are two times more PhDs working outside than inside the universities in the USA. According to a report of Estado, our balance in Brazil is quite the opposite right now but there is a clear trend that this is changing. I hope that those companies used to how things were in the old times starting considering a new approach for their own good. With a higher demand and better recruiting, it seems that unfair “rickshaw-like salaries” in Brazil might be about to end.

Posted on

Revisiting operations research elements – part I: problem, model and solution

People often admit that they have just discovered to know nothing about something they thought they knew. I felt that about terms like “problem”, “model” and “solution” during the last year. At a first sight, those words seem quite simple to anyone: a problem is a quest one wants to resolve, a model is an insightful description of such problem and a solution is an attempt of resolving the problem. As I want to show next, big messes are made of such simple things, especially in OR.

What is your problem?

Once, when I practiced a presentation at home saying “My problem is that I have those decision variables Xi, Yi and Zi”, I was interrupted by my mother-in-law with a “No! Your problem is that you have expensive machinery, oil wells to develop and you want to maximize the profit of the company”, as I indeed had! She might not know much about combinatorial optimization problems or other related class of optimization problems, but after two daughters, Ph.D. and Post-Doc in organic chemistry and a published book, she definitely knows better what a problem is.

I used to consider the “problem” as a class of purely abstract formulations or a domain-targeted specialization of such a class. However, I was ignoring the actual problem – something that must be fixed or enhanced –, which was occasionally mentioned as a motivation for the study. Indeed, such mistake can be the first step to detach a promising subject from its context and devalue its importance. As a matter of fact, I should have done the converse path: to consider my problem as a real matter from which disclosure is motivated by the resemblance with other problems of practical importance.

What does your model explain?

For a long time, I’ve been used to denote as a “model” what I write as input to an optimization solver. However, after reading “Good and Bad Futures for Constraint Programming (and Operations Research)” by John N. Hooker, I decided to get a step back about that. In his article, Hooker emphasizes the importance of models to leverage scientific progress according to their original meaning: an elegant description of a natural phenomenon. Under that assumption, a model is as valuable as its ability to explain how a given system works and why it works that way. For sure, that is not achievable by simply stating a bunch of equations.

The input of an optimization solver is always computer source code, even if it is at a very high level of abstraction when compared to generic programming languages. Nevertheless, what you are able to describe with such programming language – its syntax – can be considered as the “model” for some sort of class of abstract formulations, and my code was just a specialization of it. Therefore, it would be more accurate to say that I’ve spent much more time coding upon a model of the problem than modeling the problem. Metaphorically, the model is an ethereal inspiration to a substantial source code (hold that thought for the next post).

What are you solving?

The term “solution” has been so often associated with variable assignments of a given problem formulation that its use in its original assertion sounds like an invitation to confusion. I felt that when reading an article about Case-Based Reasoning (CBR) applications to constraint programming (CP), in which the authors had to manage such nomenclature conflict: in CBR, a solution is understood as a technique for solving a given problem and was forcefully redefined as a “resolution”, given that, in CP – and OR in general –, a solution is the output of a technique that solves some problem. I can’t imagine a better way of handling it than theirs: the ambiguity was acknowledged and possibly taught to some unaware readers, and the article moved forward.

Maybe it is a lost battle trying to associate the term “solution” in the OR field with what the general public would expect it to be. However, if that is not possible, one must emphasize the difference, since the benefit of succeeding on that – as well as in the other cases exhibited – is to present an original work in a more accessible language to researchers of other fields. Therefore, the reward for that is a higher probability of having your effort being recognized and used somewhere else.

Why to write about this?

Operations research possesses a powerful toolset, which can be applied almost everywhere. However, many authors acknowledge that OR is in a constant danger of extinction for being self-centered and detached from the outside world. I believe that one of the reasons for such belief is the misconception of terms. For that reason, I aimed to make my point as clear as possible to someone outside the field, what demanded a great number of revisions by my fiancée Sabrina. Doing that was much harder than writing the post at once and I am very grateful for her patience with my attempt to escape my own ivory tower.

Posted on

Integer Programming is Smart

I’ve just read a funny post from Michael Trick about the sexiness of Integer Programming. He made some points about how good IP modeling is not as straightforward as one might think.

I would like to add a few things about modeling and optimality.

The day I felt “cheated” by an IP solver

Some years ago, I was modeling a scheduling problem that aimed to minimize setup costs in a production line. Surprisingly, it was solved way too fast and with a solution of zero cost, what was simply impossible.

Then I found the “cheat”: as I’ve stated that a setup happens only if you change the product for the next day, the optimal solution was to stop producing for one day between consecutive products in the line, since no setup would happen in that case.

It was my fault not to state that the production line should not stop, but such simpler constraints are the first to be forgotten sometimes.

Missing the real model

Conscious or not, most people embed problem domain knowledge in the search algorithm rather than in the model. It is just when you switch to a technique in which modeling plays an important role that you realize how tricky the modeling task can be.

Sometimes, you might discover that the problem you are tackling is full of tacit constraints that will be discovered only when your client dislikes what you delivered.

Modeling for optimality

If feasibility is under doubt, what about optimality? One does not need to use IP to present an optimality bound, but few people design their own algorithms to estimate optimality gaps when not using IP.

Moreover, IP modeling is not meant to be precise in the whole domain but rather in the optimal solutions. If you can model an integer decision variable as real because it is always integer in any optimal solution, you’ve just won the day. The same happens with the constraint set: you do not have to be worried about constraints that are not tight in the optimal solutions.

Feeling the magic of optimal solvers

Being trapped by your own solver teaches you a lot. You became a better modeler and a better interviewer for your next project.

Posted on

Optimizing Public Policies for Urban Planning

Another possible title would be “Marrying an urban planner up to her research problems”.

It all happened when I started hearing my fiancée explaining the problems of Brazilian housing policy and ended up with an interesting model for sustainable housing subsidy that she presented at the Latin American Real Estate Society meeting of 2009.

The problem: Housing policy in Brazil 

The main housing subsidy for low-income families in Brazil is based on a federal program roughly called “My House, My Life”, in which public subsidy consists of an amount of money for each constructed housing unit that varies solely according to the city.

In a place like São Paulo, the unavoidable consequence of such policy is to further sprawl low-income families towards suburban areas.
Most of them already spend much more than two hours per day to go to work.
Moreover, great distances prevent them from going to work on foot or bicycle, what raises public transportation demand and decreases their purchasing power.

15183601

São Paulo in 2009: Job offer vs. low-income settlement (source: SEMPLA).

What we did: A model for variable subsidy

We started looking for the main problems of distant placement of such families:

  • Bad life quality due to the time wasted for displacing. 
  • More pollution due to the large displacements. 
  • Public expenditures to support the public transportation system.

    Instead of creating a complex multi-criteria model to tackle that, we just considered that people must be placed at most one hour apart from 50% of the jobs in the city (seems fair, right?) and considered the criteria in which anything is actually done: money!

    After all, how much does it cost to the government if families are so far from their jobs?

    • If the place is too far, one must account the per-family cost on bringing adequate public transportation infrastructure up to there. 
    • Depending on the modal of transportation, there must be public subsidies and also the carbon footprint cost, which were accounted for two people per family to work for one generation (25 years).

      Thus, if you have a 20K subsidy to place a house or apartment anywhere in the city, it would be fair to raise that in places where nothing else must be done. For instance, we realized that extending a subway line costs about 20K per family, that is, government actually spends the double to bring adequate infrastructure, if not more.

      15795412

      São Paulo’s downtown: A very good infrastructure and many abandoned buildings.

      What’s next?

      To what concern the O.R. community, it is not a challenging problem in terms of algorithms but there is a lot of room to improve modeling.
      Unfortunately, we did not apply our model completely due to the lack of data, but we hope to do that someday.
      However, it is already possible to devise the possibilities of reducing public expenditures, and forthcoming approaches would provide integrated decision models for housing subsidy and infrastructure investments.

      Talking about multidisciplinary: O.R. at the Public Sector

      A multidisciplinary approach might start at your own home, and it may point out interesting challenges that academia might not have been devised so far.
      In Brazil, where public sector decisions are all but technical, there are big opportunities yet to be explored.

      About the paper

      We were glad to have had support from Prof. J.C.S. Gonçalves, which previously was Sabrina’s advisor at FAU-USP and also coauthored this paper.

      S. Harris, T. Serra, J.C.S. Gonçalves: Critical Analysis of Brazilian Housing Policy and Proposal of Subsidy Calculation Model Based on Transportation Sustainability Criteria.
      In: Proceedings of LARES Conference 2009, São Paulo, Brazil.