Learn Operations Research, Make Millions

Russ Ohlendorf received his bachelors degree in 2006 and now, a mere five years later, he will be making $2.025 million in 2011.  The degree was in operations research and financial engineering at Princeton.  It just goes to show how far you can go in operations research:  salaries in the millions are possible!

Perhaps Russ has some skills beyond operations research, since he is a starting pitcher for the Pittsburgh Pirates which, against all rules of logic or fairness, is part of Major League Baseball.  Still, I’m marching right into my dean’s office and asking for a raise to match the highest operations research salary in Pittsburgh!

Postdocs and Special Year at the IMA

In 1987-88, I spent a great year in Minneapolis as a postdoc at the Institute for Mathematics and its Applications (and this picture of me comes from that time). Every year at the IMA has a special theme, and the theme my year was “Applied Combinatorics”. There were about a dozen of us postdocs that year: 11 combinatorialists, and me, the OR guy, who I guess satisfied the Applied in year’s title. It was a fantastic year. The other combinatorialists were scary-smart and doing amazing things. One of the postdocs was Bernd Sturmfels who was working on Grobner Bases at the time and has gone on to an amazing career in applying algebraic methods in optimization, statistics, and other fields. I look at his list of 190 papers and 15 books and realize what a slacker I am!

The year at the IMA was important for my career. It gave me the chance to finish my dissertation papers and move on to new research. I met a great group of people and learned about some aspects of an academic career without being saddled with teaching or administrative duties.

Depending on the year, the IMA may be more or less interesting to operations researchers. Next year (2011-12) looks to be a good one. It is on “The Mathematics of Information”. There are a couple versions of the description of the year. I like the one on the Geomblog:

During the academic year 2011-2012, the annual program at the Institute for Mathematics and its Applications (IMA) at the University of Minnesota will be in the Mathematics of Information. Information, broadly defined, plays an ever increasingly large role in our scientific and technological endeavors, as well as our daily lives. Collectively, we search the web over billions of times per day, we keep our medical records in digital repositories, we share videos and photos over the web, and we listen to music on MP3 players. Our ability to collect, store, and generate vast quantities of data far outstrips our ability to analyze, process, and understand these data. Many scientific, engineering, and medical applications depend on our ability to handle enormous amounts of complex information. Network engineering involves massive datasets at high speeds, medical imaging generates large data with intricate geometric relationships, and astronomical observations include data at different wavelengths or spectral bands. Our current technology and scientific tools for information lag far behind our ability to collect enormous amounts of data, our need to analyze that data as efficiently as possible, and, finally, our ability to use that analysis to make sound, timely decisions.

“Sound, timely decisions” is what operations research is all about.

The postdoc deadline was January 7, 2011 but applications will be considered until February 4, 2011. So get a move on if you are interested!

There is also funding for more established researchers to spend time at the IMA. It is a great way to get started in new research directions and to rub off the administrative barnacles that attach if you stay at one place too long.

How Operations Research Helps Me Understand Politics and Voting

Over the years, operations research, politics, and voting have intersected often for me. Going back almost 25 years now, I have done research on voting systems. I have blogged on elections, and written about predicting results and presenting results. I have written about political leaders who were trained in operations research, and even countries run on O.R. principles.

Over time, I have been both elated and disillusioned by politics at both the national and local scale. I use what I know about elections when I run committees, and get very frustrated by others running committees without an understanding of the basics of voting theory.

While I will not claim to be an expert on how theory and practice interact in politics and elections, I do have some insights. Many of these are well known to those in voting theory, but some are a little idiosyncratic. Perhaps we can have an election afterward on which is the most useful.

  1. When there are more than two possibilities, Plurality voting is just plain wrong. Plurality voting is what many of us (particularly here in the U.S.) think of as “normal” voting: everyone votes for their favorite and whichever alternative gets the most votes wins. We use this system a lot, and we should essentially never use it. The difficulties it causes with vote-splitting and manipulation are ridiculous. It is plurality voting that causes Republicans to support a left-wing candidate in the U.S. Presidential election (and vice versa for Democrats and a right-wing third party): if the third candidate takes votes away from the Democrat then the Republican has a better chance of winning.I feel strongly enough about this that I cannot be on a committee that uses Plurality voting: I will simply argue about the voting system until it changes (or until they start “forgetting” to tell me about meetings, which is kinda a win-win).
  2. I can live with practically any other voting system. There are quasi-religious arguments about voting systems with zealots claiming one is far superior than all the others. Nothing has convinced me: the cases where these voting systems differ are exactly the cases where it is unclear to me who should be the winner. So whether it is approval voting (like INFORMS uses), or some sort of point system (“Everyone gets six votes to divide among the candidates”), or multi-round systems (“Divide three votes, then we’ll drop the low vote getter and revote”) or whatever, most of it works for me.
  3. The person setting the agenda can have a huge amount of power. While I may be happy with lots of systems, I am hyper-aware of attempts to manipulate the process. Once you give people the chance to think about things, then the agenda-setter (or voting-rule setter) can have an undue amount of power. Of course, if I am the agenda-setter, then knowing lots of voting rules can be quite helpful. Even without knowing committee preferences, it is handy to know that the following rule can help A win in an election with A, B, and C.

    Let’s do B against C then the winner against A.

    That is pretty obviously to A’s advantage (with voters voting their true preferences, A will win unless one of the others is a Condorcet winner — a candidate who could beat every other candidate in a two-person election). Less obvious is

    Let’s do A against B, then A against C, then the winners against each other

    This seems to favor A, but it does not. The only way A can win this election (with truthful voters) is for A to beat both B and C (hence be the Condorcet winner).

    In fact, my research shows that you can arrange for A to win in a four-candidate election no matter what the preferences are provided A is not the Condorcet loser (loses to every other candidate in a pairwise election) and no other candidate is a Condorcet winner. Unfortunately, no committee is willing to sit still for the 12 votes required, beginning

    We’ll go with A against B, then A against C, then take the winners against each other, and take the winner of that against D, then…

    This leads to my favorite voting tree, as in the diagram.

  4. When there is block voting, power is only weakly related to the size of the block. I have in mind systems where different “voters” have different numbers of votes. So, in a parliamentary system with party-line voting, if there are 40 representatives for party A, then party A gets 40 votes. It might seem that if the overall support is 40% for party A, 40% for party B, and 20% for party C, then it would only be fair to give parliamentary seats in that proportion. Unfortunately, if bills need 50% of the vote to pass, “proportional representation” gives undue power to party C. In fact, in this case C has as much power as A or B: two of the three parties are needed to pass any bill. Conversely, if the support is 51%, 48%, 1%, and a 50% rule is used to pass, then the first party has all the power.

    This simple observation has helped me understand the various issues with the recent U.S. Senate vis-a-vis the filibuster rules (which essentially required 60% of the votes to move anything of substance forward): the Senate vacillated between having the Democrats having all the power (51 votes to pass a bill) and having Democrats and Republicans having the same power (60 votes to end a filibuster). With no solution representing reality (either 58% of the Senate seats for the Democrats or perhaps a lower number representing nation-wide party support), the system cannot equate power with support.

    This is seen even more starkly in the election of a single individual like the U.S. President. George Bush in 2004 claimed a “mandate” after winning 51% of the popular vote. While 51% might not seem like a mandate, it is difficult how else to map 51% to a single person.

    Understanding this power relationship makes U.S. Electoral College analysis endlessly fascinating, without adding much insight into whether the Electoral College is a good idea or not.

  5. The push towards and away from the median voter explains a lot about party politics. One fundamental model in economics is the Hotelling Model.  Traditionally this model is explained in terms of ice cream vendors along a stretch of beach.  If there is one vendor, he can set up anywhere on the beach:  he has a monopoly, so no matter where the beach-goers are, they will go to the vendor.  But suppose there are more than one vendor and beach-goers go to the closest vendor. If there are two vendors, the only stable place for them to be (assuming some continuity in the placement of beach-goers) is to have both at the median point, right next to each other!  This seems counter-intuitive:  why aren’t they, say, 1/3 and 2/3 along the beach (for the case of uniformly distributed beach-goers)?  In that case, each vendor gets 1/2 of the customers, but the vendor at 1/3 would say “If I move to 1/2 then I’ll get 5/12 of the customers, which is more than my current 1/3”.  Of course, the vendor at 2/3 also has an incentive to move to the middle.  So they will happily set up next to each other, to the detriment of the beach-goers who must travel farther on average to satisfy their needs.

    How is this related to politics? I believe it gives the fundamental pressures on parties in two-party systems. In the U.S., both the Democrats and Republicans are pressed towards the middle in their efforts to get to the median voter. But the most interesting aspects are the ways in which the political system does not meet the modeling assumptions of the Hotelling model. Here are a couple:

    • The Hotelling Model assumes customers will purchase no matter what distance they need travel to the server. In a political model, voters sufficiently far away from all candidates may simply choose not to participate. While non-participation is often seen as abdicating a role, that need not be the case. Take the case of the “Tea Party Movement”. There are many interpretations of their role in politics, but one threat to the Republicans is a willingness to of the Tea Partiers to simply not participate. This has the effect, in a simplistic left-right spectrum model, to move the median voter to the left. If the Republicans want to move to the resulting median, they would have to hop over the Democrats, something that is simply infeasible (the effort to convince the left wing will take generations to believe the Republicans are really their party). So the threat of non-participation is a strong one, and can only be counteracted by the Republicans by having policies sufficiently appealing to the Tea Partiers to keep them participating. Of course, this rightward movement opens the opportunity for the Democrats to appeal to the crowd in the resulting gap between Democrats and Republicans, though the Democrats undoubtedly face non-participation threats at their own extremes.
    • Another sign of the pressures towards and away from the median occur in the primary/general election form of U.S. politics. During the primaries, a candidate (either local or national) needs to appeal to voters in their party (in most cases). This leads to movement towards the median of a party, particularly if there are only two candidates. Once the candidate has been chosen by the party, though, the candidate is now facing median pressure from the general population. this should result into a movement towards the center, which certainly seems to be the case. Party activists try to stop this move towards the center by forcing pledges or other commitments on candidates, which keep them more towards the median of their own party, perhaps at the expense of general election success.

    The Hotelling Model in politics is a wonderful model: it is wrong but useful. By understanding how the model doesn’t work, we can get insight into how politics does work.

It would be easy to be disillusioned about voting and politics based on theory (and practice, some days). No voting system is fair or nonmanipulable; pressures on candidates force them to espouse views that are not their own; consistency is obviously a foible of a weak mind.

Instead, my better understanding of voting and elections through operations research leaves me energized about voting. However imperfect it is, the system does not need to be mysterious. And a better understanding can lead to better systems.

This topic has been on my list of “to-do”s for a while. I am glad that the Second INFORMS Blog Challenge has gotten me to finally write it!

The Sexiness of Integer Programming

Suresh Venkatasubramanian, of the excellent Geomblog, is at SODA and covered some preconference conferences. When covering a paper that used integer programming (via CPLEX), his comment was:

It’s not the “sexiest” thing in the world to solve algorithms problems in practice by using large industrial strength packages.

Oh, he didn’t say that, did he?

I spend most of my life “solving algorithms problems in practice by using large industrial strength packages”. I solve sports scheduling problems, logistics problems, and even problems in social choice with large scale integer programming software as my primary tool. Who says I am not sexy? Or, worse, that my research is not sexy?

I can think of a few misconceptions that might lead one to doubt the sexiness of integer programming.

  • Integer Programming is uncreative. After all, you just formulate the problem in terms of variables, linear objective, and linear constraints, toss it in a code, and you are done. Where is the research?

    Such a view ignores the tremendous number of choices once must make in formulating integer programming. The choice of variables, constraints, and objective can have a tremendous impact on the effectiveness of the solver. While solvers continue to get better at automatically identifying formulation improvements, formulating integer programs is still an art. It is an art, however, enhanced by theory. As we better understand the polyhedral characteristics of integer programming formulations, we create better and better formulations.

    This creative effort is expanded when alternatives to “basic” formulations are included. Creating a branch-and-price, branch-and-cut, Benders, or other type of formulation can be the key to solving real problems, but may require significant research effort.

  • Integer programming is slow. This seems to be the most common response I get from those outside the integer programming subfield. One quote from a person at a well-known computer science-oriented firm: “I tried integer programming. It doesn’t work.” Not “It doesn’t work for this problem” or “I couldn’t make it work”. Just “It doesn’t work”. How can a topic be sexy if it doesn’t work?

    I think one of the great stories in all of mathematics and business is the incredible confluence between increased data, faster computers, algorithmic improvements, and implementation successes that have led to many orders of magnitude speed increases in integer programs. Over the last fifteen years, we have gotten much, much better at solving integer programming models. With the underlying linear programming solvers being more than million times faster (no hyperbole: both computers and algorithms provide more than a 1000 time speedup each), lots of instances formerly out of reach can now be solved routinely.

    Of course, integer programming is exponential time in the worst case. But I am not sure why a polynomial time algorithm that gets an approximate solution within a factor of, say, 42 is any “sexier” than an algorithm that finds the optimal solution in a reasonable amount of time for any instance of practical import.

  • Integer programming is expensive. Hey, if you have to spend tens of thousands of dollars for solutions, that really doesn’t count does it? It is like a troll dressed up in a $5,000 suit: it might look OK, but it’s not sexy!

    No one has to pay a lot for high quality integer programming software. Suresh refers to this in his post:

    This was surprising to me on two levels: firstly, that CPLEX is actually free for academic use (who knew!) and that such a simple approach is so effective.

    Actually, all the major programs offer a way for free academic use. I particularly like Gurobi’s approach, which is based on periodic validation through a “.edu” domain, but academics can also get CPLEX (as you would have read on my blog last year) and XPRESS.

    And if you are not an academic? COIN-OR offers “industrial strength” linear and integer programming in an open source approach.

In Suresh’s defense, here is the full quote, where he makes clear his support for this type of research:

It’s not the “sexiest” thing in the world to solve algorithms problems in practice by using large industrial strength packages. However, both CPLEX and SAT solvers are examples of tools that can be used in practice to solve fairly intractable problems. It still takes a lot of engineering and skill to make the heuristics work well, but it’s something that we should be using as a matter of course when designing heuristics before trying to invent an algorithm from scratch.

Suresh obviously gets it: let’s hope his post expands interest in integer programming methods for these problems.

Integer programming is useful, fast, and cheap. If that isn’t sexy (for an algorithm!), then I don’t know what is.

OR Job at Waste Management

I don’t normally do job postings on this blog:  there is OR/MS Today and INFORMS Job Placement Service and so on for that, but sometimes a job catches my eye.  A company is looking for a Masters level OR specialist to provide analysis for them.  They run a nice sized network:  hundreds of sources and transfer points with presumably thousands of trucks linking them.  It is clear there are lots of interesting things you can do with the network.

It is a little unusual since it is a waste product network, involving transporting waste to landfills, energy plants, recycling plants and so on.  This is one industry that strikes me as being pretty resistant to the peaks and valleys of the overall economy (as opposed to, say, financial portfolio optimization).

Here is part of the description:

Waste Management, Inc. is the leading provider of comprehensive waste and environmental services in North America. The company serves nearly 20 million municipal, commercial, industrial, and residential customers through a network of 367 collection operations, 355 transfer stations, 273 active landfill disposal sites, 16 waste-to-energy plants, 134 recycling plants, and 111 beneficial-use landfill gas projects.

Waste Management currently has a opportunity for a Operations Research Specialist at our downtown Houston, TX, headquarters.

Job Summary

Formulate and apply mathematical modeling and other optimizing methods to develop and interpret information that assists the entire Waste Management organization with decision-making, policy formulation, or other managerial functions. Additionally the Operations Research Specialist frequently concentrates on collecting and analyzing data and developing decision support software. The Operations Research Specialist will develop and supply analytic support for optimal time, costing, pricing, or logistics networks for evaluation and/or implementation.

Essential Duties and Responsibilities include the following:

To perform this job successfully, an individual must be able to perform the essential duties satisfactorily.  Other minor duties may be assigned.

· Formulate mathematical models (linear and non-linear) of problems, relating constants and variables, restrictions, alternatives, conflicting objectives, and their numerical parameters.

· Conduct simulation (discrete event) studies of existing and proposed systems, including definition of data requirements; capture and validation of information, model formulation, design experimentation, and application of appropriate statistical analysis.

…


The skills needed are a mix of simulation and optimization skills:

Demonstrated ability to apply operations research techniques including decision analysis, optimization, simulation and statistical and stochastic modeling.

· Significant experience utilizing mathematical programming software packages such as IBM ILOG CPLEX, LINDO, or Xpress.

· Demonstrated ability to develop simulation models and conduct studies utilizing commercial simulation software such as Arena, AutoMOD, Witness, etc.

· Strong problem solving and analysis skills: ability to identify root causes of problems, create effective practical solution approaches, implement solutions under the tactical demands of business operations.

· Programming experience, preferably in C or C#.

· Committed and highly motivated team player with strong communication skills.

· Demonstrated work and familiarity with data mining and visualization tools.

· Experience with working as part of an integrated solutions development team to provide value to systems engineering and development for specific decision support application

If you are interested in this, contact Maurice Bobb of Waste Management for more information. And if you get the job, be sure to write back to me on the sort of problems you look at. This could be a really fascinating operations research job.