Sunday, January 30, 2011

The Diogenes Problem

Shiva Subramanian's post yesterday about "The honest politician and other rare events", his contribution to the January INFORMS blog challenge, got me thinking about the following OR problem.  Suppose that, in Philip José Farmer's Riverworld (of recent TV movie fame), we are able to take all the politicians that ever were (excluding those still living) and pack them into a finite rectangular enclosure.  Suppose further that we are able to assign a probability to each of them being honest (and that the probability function is not identically zero, which may be the hardest assumption to swallow in this Gedankenexperiment).  Now let's say we are able to map out a path for Diogenes that minimizes the expected time until his first encounter with an honest person (I'm assuming both male and female politicians are present) in the room.  Would that path be a space-filling curve?

Saturday, January 22, 2011


People who work in operations research tend to believe that governments (and everyone else, but especially governments) would benefit from making more and better use of it. At the heart of operations research is logical, dispassionate analysis of how a system works, and how it can work better, quantifying options and possible outcomes using hard data where possible.

One of the most challenging areas in operations research is risk analysis. The challenges are many, and frequently the most difficult aspects are not algorithmic but rather in assessing probabilities using scant or messy data (how likely is a nuclear power plant to release radiation? we happily lack a large sample of incidents) and in attaching values to outcomes. Particularly problematic is assigning a value to a human life. It is done all the time, by insurers, by juries and, consciously or not, by government agencies. Adding to the difficulty is that mathematical analysis may produce results we as people find uncomfortable.

An example I've heard more than once (for which I have no citation) is whether government (here the Federal Aviation Administration) should require that infants on airline flights be parked in some version of a car seat. I imagine most people, at least before hearing the arguments, would say yes. The picture of an infant turning into a projectile during turbulence or a hard landing is very discomfiting. Against that, the analyst weighs the facts that (a) requiring the infant to be in a conveyor most likely imposes on the parents the requirement to buy another ticket, (b) the cost of an extra ticket will, at the margin, impel some number of families to drive rather than to fly and (c) on a per-mile basis, commercial flight is safer than driving. So requiring a safety seat for infants on flights might, paradoxically, lead to more injuries or deaths to infants during long trips, rather than fewer. (I'm restraining myself from saying something about "throwing the baby out with the bathwater".) (Apparently, I was not successful.)

Enter your friendly federal, state or local government representatives. They are locked into a perpetual (re)election cycle, so making decisions that would at first blush seem insensitive or uncaring is bad for business. When it comes to national security, the worst thing they can do is appear to do nothing. The guiding principle seems to be that good theater trumps good analysis.

Thus, after the attacks on the World Trade Center and Pentagon in 2001, the federal government instituted a variety of security procedures at airports that many fliers view as cosmetic at best. Some of the perpetrators were in the U.S. on expired student visas, so the federal government made student visas harder to get (and, in the process, scared off a significant number of international students, costing U.S. universities a fair bit of money.) In the aftermath of an attempt to smuggle explosive devices into the U.S. on cargo flights, the Transportation Safety Administration has moved up its target date for screening of 100% of air cargo, a move that was already in the works. What is unclear is the extent to which any rigorous analysis of costs and benefits went into any of these decisions. At least some of the new policies likely have helped avert additional attacks. Some may have created new jobs. Some assuredly imposed new costs on businesses, and some make air travel (already less than a thrilling prospect for those of us in sardine class) even less comfortable.

Whenever another event triggers a panicky reaction (and I'm waiting to see what the Tucson shootings yield), I think back to what my English relatives lived through during the Blitz, and the "duck-and-cover" drills of my childhood. (I lived about midway between New York City and Brookhaven National Laboratory, so I figured no matter which way the wind blew I was going to be in the radiation's path.) Back then people seemed a bit more accepting of risk, and the fact that Bad Things Happen and sometimes they just cannot be prevented, and elected officials were less concerned about theatrics.

In there era of sound-bite politics and tweet-length policy discussions, though, I'm afraid that OR is trumped by the political credo CYA. Better to be seen doing something pointless than to be perceived as doing nothing.

(The preceding rant was motivated by the INFORM blog challenge for January: O.R. and Politics.)

Wednesday, January 19, 2011

Home Field Advantage

The January 17, 2011 issue of Sports Illustrated contains an interesting article, "What's Really Behind Home Field Advantage?" by Tobias J. Moskowitz and L. Jon Wertheim.  It's an excerpt from the book "SCORECASTING: The Hidden Influences Behind How Sports Are Played and Games Are Won" by the same two authors.  The premises of the article are that
  • home field advantage is real (in most if not all sports);
  • its primary (sole?) cause is biased officiating (the bias likely being unconscious); and
  • the magnitude of the advantage is an increasing function of crowd size.
The article is something of a "meta-analysis".  The authors do no statistical research themselves, but rather cite a number of studies that consistently support those premises.

As a (non-rabid) sports fan, and having done a bit of low-level officiating myself, I found the conclusions interesting; but I mention it here because the studies it cites illustrate nicely how to do solid, persuasive statistical analysis using observational data.  It's a good example of what some of us are now calling "descriptive analytics" done right.

Thursday, January 13, 2011


A response over at OR-Exchange led me to discover Numberjack, an open-source (LPGL) constraint programming platform written in Python.  I haven't had time to look at it carefully, and won't for a while (among other things, I need to learn more Python first), but I had to give them a shout-out just for the slogan on their home page (superimposed on a photograph of a forest): "Cuts your exponential search tree into logs."

Sunday, January 9, 2011

Physiology and Mathematics Education

As a math lifer, I'm concerned about what more and more people are calling a crisis in STEM (Science, Technology, Engineering and Mathematics) education in the United States. It seems as if every few days we read about the U. S. lagging behind other countries in math or science test scores. We continue to lead the world in innovation for the moment, but it's hard to picture how we can sustain that lead without producing (or importing) more scientists and engineers (and, dare I say, mathematicians).  Equally importantly, in the age of the "information economy", if average U. S. citizens (not the ones in the right tail on math scores) come up short in STEM ability, where are they going to find jobs that pay respectable salaries?  (This is very important to me:  I'm on the cusp of retirement, and I'm counting on them both to pay down the burgeoning national debt and to sustain my lifestyle once my paychecks stop.)

The press (and, thus, the populace) are gradually waking up to the looming crisis, as evidenced by government panels, legislation, academic workshops and periodic episodes of public hand-wringing.  Naturally, this spawns a wave of finger-pointing as we seek (a) one single explanation for what is undoubtedly a phenomenon with multiple roots and (b) someone (other than ourselves) whom we can blame.  A backgrounder from the Heritage Foundation aptly points out that if the K-12 pipeline does not produce students well grounded in science and math, colleges and universities will be hard-pressed to find students willing and able to major in those subjects (and, by extension, graduate program enrollments will also suffer).

Now please indulge me in an apparent digression that will actually tie back (I hope).  I recently found myself engaged in a conversation about math education, math ability and its connection (if any) to gender.  In this conversation, I recalled a colleague (a professor of economics) complaining to me that his daughter had essentially been told outright by a high school teacher that, being female, she should have diminished expectations for learning upper level mathematics (I suspect this meant calculus, but the conversation was long ago and the details elude me).  My colleague was justifiably apoplectic.

I also recalled some misadventures from my graduate student days, when I taught a math class for elementary education majors.  On paper, the course dealt with how to teach math to K-6 students.  In practice, it meant (gulp) teaching K-6 math to college students majoring in elementary education.  Lest you think I exaggerate, let me share an anecdote.  My then girlfriend also taught the course, in the summer, when the students were elementary school teachers returning to pick up additional credits.  One student asked if she could bring her eight year old son to class to avoid daycare hassles, which request my girlfriend was happy to accommodate.  On the day of the first exam, she saw him sitting with nothing to occupy him, so she game him a spare copy of the exam, figuring he could color on the back.  Instead, he flipped it over, did the exam -- and received the highest score in the class!

So, on the one hand, we have people telling children that they are doomed to be weak at math (and science?) because they lack a Y chromosome.  I suspect similar comments are made based on race or other factors.  On the other hand, we have teachers (at least in elementary school) who themselves are weak in math (and science?) and are inclined to pass their fear of the subject on to their students.  (If the teacher finds something difficult, he or she is likely to communicate to the pupil that the pupil should not worry about finding it challenging.)  On the gripping hand (and this is purely my conjecture), I suspect we also discourage students of all levels from taking STEM courses by rewarding them for weak work in non-STEM courses.  I think it's harder to give inflated grades in STEM subjects because they tend to have definitive correct and incorrect answers.  (At least it's harder for me to give them.)  At the same time, it's easy for a student to be discouraged at having to work hard for medium grades in STEM subjects when they can get better grades with less effort in other classes.

What ties this to the STEM crisis, for me, is a recent article in Newsweek about physiological triggers for improvement (or degradation) in the human brain.  Specifically, according to author Sharon Begley,
Finally, being told that you belong to a group that does very well on a test tends to let you do better than if you’re told you belong to a group that does poorly; the latter floods you with cortisol, while the former gives you the wherewithal and dopamine surge to keep plugging away.
So the effect of communicating diminished expectations to students may be more than psychological; it may trigger physiological changes that create a self-fulfilling prophecy ... and, in doing so, deepen the STEM crisis.

Friday, January 7, 2011

Max and Min Functions in a MIP

Previously I wrote about how to work the "positive part" function ($y^+=\max(y,0)$) into a mixed integer programming model. More general uses of the $\max$ and $\min$ functions are really just an extension of this, but the extension may not be entirely obvious. In this post I'll explain how to set $z=\max(x,y)$ in a MIP model, where $x$, $y$ and $z$ are all variables. If the model was in fact a linear program before introducing the $\max$ or $\min$ function, it may remain an LP, or it may become a MIP, depending on exactly what you are doing.  I'll use the $\max$ function for explanatory purposes; the necessary tweaks to deal with the $\min$ function are left to the reader as an exercise.

Let's start with the obvious part: if $z=\max(x,y)$ then $$z\ge x$$ and $$z \ge y.$$In fact, adding those two constraints will be sufficient if the nature of the model ensures that the smallest feasible value of $z$ will always be chosen  Typically this means that (a) $z$ has a positive coefficient in an objective function being minimized, or a negative coefficient in an objective function being maximized, and (b) $z$ does not connect to other variables, through constraints, in a way that might allow an inflated value of $z$ to cause other variables to change enough that their improved objective contribution would more than pay for the damage done by inflating $z$.

There are also occasional cases where inflation of $z$ is not actually a concern: you need $z$ to be at least as big as both $x$ and $y$ (which the constraints ensure), but a larger than necessary value of $z$ will not affect the objective function or the values of other variables, and can be corrected manually once a solution is found.

The (slightly) tricky case is when you cannot be sure that the "pressure" of the  objective function will prevent inflated values of $z$ from occurring, and you really do need the value of $z$ to be correct.  To handle this case, we will need finite bounds for $x$ and $y$, so from here on I will assume that $L_x \le x \le U_x$ and $L_y \le y \le U_y$.  We have to introduce a new binary variable $w$, which will switch values depending on whether $x$ or $y$ is the larger of the two. In addition to the two previous constraints, we add the following:$$z \le x + (U_y - L_x)w$$and$$z \le y + (U_x-L_y)(1-w).$$The combined effect of the constraints is that $w=0\implies z=x\ge y$ and $w=1\implies z=y\ge x$.