A Math Puzzle as a Network

There is a standard type of math puzzle that has been around at least since I was a child. The details vary, but the concept is consistent. You are typically given a few initially empty containers of various (integer) capacities, an essentially infinite reservoir of something that goes in the containers, and a goal (integer) for how much of that something you want to end up with. You have to figure out how to reach the goal without having any measuring instruments, meaning that your operations are limited to emptying a container into the reservoir, filling a container from the reservoir, or moving content from one container to another until you empty the source or fill the destination, whichever happens first. (All this is done under the assumption of no spillage, meaning the originator of the puzzle did not have me in mind.) I think I've seen a variant that involves cutting things, where your ability to measure where to cut is limited to stacking pieces you already have as a guide to the piece you want to cut.

A question popped up on Mathematics Stack Exchange about how to solve one of these puzzles using dynamic programming (DP) with backward recursion. The problem at hand involves two jugs, of capacities seven and three liters respectively, and a lake, with the desired end state being possession of exactly five liters of water. The obvious (at least to me) state space for DP would be the volume of water in each jug, resulting in 32 possible states ($\lbrace 0,\dots,7\rbrace \times \lbrace 0,\dots,3 \rbrace$). Assuming the objective function is to reach the state $(5,0)$ with a minimal number of operations, the problem can be cast just as easily as a shortest path problem on a digraph, in which each node is a possible state of the system, each arc has weight 1, and arcs fall into one of the categories mentioned in the previous paragraph.

I was looking for an excuse to try out the igraph package for R, and this was it. In my R notebook, a node label "5|2" would indicate the state where the larger jug contains five liters and the smaller jug contains two. Arcs are labeled with one of the following: "EL" (empty the larger jug); "FL" (fill the larger jug); "ES" (empty the smaller jug); "FS" (fill the smaller jug); "PLS" (pour the larger jug into the smaller jug); or "PSL" (pour the smaller jug into the larger jug).

Assuming I did not screw up the digraph setup, a total of nine operations are required to get the job done. If you are interested, you can see my code (and the solution) in this R notebook.

Optimization Pro and Con

A tweet by Nate Brixius (@natebrix) led me to read the article "The Natural Order and Divine Order of Optimization" published by the Wisconsin Institute for Discovery, a rebuttal/counterpoint to a New York Times Magazine article titled "A Sucker is Optimized Every Minute". The former sings the praises of optimization (somewhat) and the latter vilifies it (somewhat).

As someone whose research focuses on optimization, I'm generally in the pro camp, but I'll concede that it can be overdone. One of my favorite quotes is of rather fuzzy provenance. I've seen variations of it from multiple authors, phrased as a monologue by, variously, a Zen master, a playboy or a dying man (but not, so far, a dying playboy Zen master). The version I recall:

I had my chances to marry, but I was looking for the perfect woman. Then one day I found her; but she was looking for the perfect man.

Optimization is fine for some things, inappropriate for others, and (like everything else in life) not a good idea if taken to an extreme.*

* I'm rather proud of myself that I resisted the nearly-inevitable "extreme point" pun there.

A Musical Random Walk

I just read a blog post here at MSU about The Infinite Jukebox, a web tool that will analyze a song (either one you upload or one from their library) and map out links between segments of the song that have approximately the same beat. You then see a visualization of the song as a loop, with the links (arcs) added, forming a directed graph. (The visualization does not display arcs as arrows, though, just as, well, arcs.)

When you replay the song in The Infinite Jukebox, as it passes the tail node of each arc, it randomly chooses whether to keep going on the original path or cross the arc and continue playing, along the original path, from the head node. Thus the "infinite" part of the site's name -- the song will continue until you stop it.

I don't know the algorithm they use for playback, but it appears superficially to be a Markov process, so perhaps this really is a random walk over the song's graph.

If you want to try it out, I can recommend The Trashmen's version of "Surfin' Bird", which I was happy to discover is in the site's library. The randomly looped version sounds suspiciously like the original (which is what I expected). Although the visualization of the progress through the song is interesting, for the full multimedia experience you'll want to have the You Tube video playing (muted) on a second screen.

Sadly, their library does not include "Papa-Oom-Mow-Mow" by The Rivingtons, and I don't happen to own a copy, so I could not compare the action of The Infinite Jukebox on that with what it did to "Surfin' Bird". As I listened to the looped "Surfin' Bird", though, I couldn't help but think "and thus another enhanced interrogation technique is born".

A Modest Terminology Proposal

I just finished shoveling snow, an exercise I will have to repeat later today and possibly tomorrow, as we enjoy the first of multiple winter storms queued up all the way from mid-Michigan (where I live) to the central Pacific, each patiently awaiting its turn to annoy me. With that in mind, I would like to point out cardinal failings of our terminology for climate phenomena.

Global Warming

This term was in vogue several years ago, but seems to have been surpassed by "climate change" (next item). One problem with "global warming" is that while it may be true in an average sense, it frequently does not resonate in an instantaneous sense. When you've lived through a "polar vortex" and are awaiting the rumored arrival of another one, "global warming" seems neither likely nor a bad idea.

Climate Change

This is the phrase currently in vogue. Its two main faults are that (a) change is not necessarily bad and (b) change is inevitable (except, as some wag once noted, from a vending machine).

My Proposal

With those thoughts in mind, I would like to propose a new phrase that I think is both more descriptive of current climate phenomena and better conveys a sense of concern about them:

Bipolar Climate Disorder

There Was a World (and Music!) Before Punk Rock

This is in response to Laura McLay's latest blog post, "famous punk songs about climate change and optimization". Like so many young whippersnappers (and the former Soviet Union), she seems to think everything was invented by her generation. I'm here to refute that. (You'll probably want to read her post before this one, for context.)

Long before "punk rock" meant anything beyond the Jets and the Sharks:

• Johnny Mathis looked at applications of probability ("Chances Are", 1957);
• The Kingston Trio examined the connection between tax policy and Hamiltonian circuits ("M.T.A.", 1959);
• The Marcels analyzed low frequency events ("Blue Moon", 1961, remaking a song written in 1934!);
• Martha and the Vandellas warned us about global warming ("Heat Wave", 1963);
• Herman's Hermits warned us about violating capacity constraints ("Dandy", 1966: "Two girls are too many, three's a crowd and four you're dead!");
• Dionne Warwick discussed route-finding problems ("Do You Know the Way to San Jose", 1968).

I've probably just scratched the surface here. Heck, maybe it's true that "Everything Old Is New Again" (Peter Allen, cowritten with Carole Bayer Sager, 1974).

Update: Since Marc-André Carle brought up geometry, I feel obligated to point out that geometry begins with basic shapes:

• The Diamonds (1953-present);
• The Cyrkle (1961-1968).

What's Wrong with a Gerontocracy?

The digital version of the June 24, 2013 issue of Time magazine contains a viewpoint column by Grace Wyler titled "Washington is a Gerontocracy". The subtitle adequately conveys her central point:

A 20-something can be the CEO of a billion-dollar company but can't run for the Senate. That doesn't make sense.

Given some of her arguments, I thought an operations research/mathematics perspective might be in order (plus it's a holiday and I have nothing better to do with my time).

First, I should stipulate that I'm actually somewhat in agreement with her. Here, in no particular order, is a partial list of things that a 21 year old US citizen legally can do:

• consume alcohol (most places, anyway);
• own property;
• sign contracts;
• wed;
• reproduce;
• drive an automobile;
• vote;
• control a variety of lethal military ordinance;
• serve (and perhaps die for) his/her country.

Here, per Ms. Wyler, is a list of things that same citizen cannot do:

• serve in the House of Representatives (minimum age: 25);
• serve in the Senate (minimum age: 30);
• serve as President of the United States (minimum age: 35).

Now, one of the truisms of operations research (albeit one not often taught in classrooms) is that when confronted with constraints for a decision, the first question should be something along the lines of "Why do those constraints exist?" It is not uncommon that the actual reason, if you can drill down to it, is something like "Because <insert name of previous or current big-wig> thinks/thought it should be that way" or "Because that's how we've always done it" (since the last time anybody bothered to think about it). With that in mind, I am not ready to dismiss the validity of lower age limits in general and those specified in the Constitution in particular, but I do think it is worth reviewing them and asking whether they are still appropriate.

I also happen to agree that, to some extent,

Capitol Hill could probably take some cues from people who aren’t afraid to move fast and break a few things.

I further agree that

Congress is struggling to keep up, spinning its wheels in a bygone era when people thought the Internet was a “series of tubes.”

Some of their votes on electronic privacy, protection of intellectual property and other technology-related bills have suggested a less than stellar understanding of technology ... but when the current 20-somethings are 40-somethings, that will resolve itself, much as the current "gerontocracy" knows how to drive a car without smacking it with a buggy whip.

Those points made, I have to take issue with some of Ms. Wyler's arguments.

But if any of these wunderkinder want to direct their powerful young minds toward governing the country, they will have to wait a few years. ... [T]here is a serious downside to barring young people from seeking federal office: with the public debate determined and dominated by senior citizens, the country doesn’t get to hear from — and vote for — the interests of young adults[.]

Having earlier touted a few 20-something billionaires who made their money from Internet businesses, Ms. Wyler suddenly seems to have forgotten their online presence (and the online presences of the multitude of non-billionaire 20-somethings who patronize those businesses). Television is also awash in good-looking 20- and 30-somethings, whether on scripted shows or reality shows. If there is one thing young people do not currently lack, it is platforms to make their opinions heard. Furthermore, I'm fairly sure the Constitutional limits on the ages of office-holders do not apply to staff (else the occasional Congressman-page scandal would be reported in the AARP newsletter and not in Time). Our current leaders have ample opportunity to listen to the opinions of their (considerably) younger constituents, whether they exercise those opportunities or not.

The result is that Capitol Hill remains at least a generation behind the rest of the country. In the 113th Congress, elected in 2012, the average age in the House is 57, and the average age in the Senate is 62.

In support of Ms. Wyler's position, using 2012 demographic data from the US Census Bureau, 57 is roughly the 70th percentile of adults (those over age 20) and roughly the 78th percentile of the entire population. So Congress does in fact skew a bit old. On the other hand, if we equate a "generation" to approximately 25 years, the "average" member of Congress is a bit more than a generation older than the 20-somethings and roughly a generation younger than the eldest segment of the population. So if they are "a generation behind the rest of the country", the "rest of the country" must exclude anyone with an AARP membership ... and trust me, you do not want to meddle with us. (Old proverb: Old age and treachery will overcome youth and skill.)

In his book Too Young to Run?: A Proposal for an Age Amendment to the U.S. Constitution, [Pomona College politics professor John] Seery writes that the age restrictions imposed by the Constitution lower the incentive for young adults to participate in what is supposed to be a representative democracy.

This is certainly plausible, the key being that "lower" conveys a direction but not a magnitude. The young adults in question can run for many local, regional and state offices. Where I live, we had a recent college graduate serve on our city council at 24 and serve as mayor well before his thirtieth birthday. I'm not one to advocate for career politicians, but an apprenticeship before taking national office does not seem unduly burdensome. There is something comforting to the notion that the people steering the ship are not out on their maiden voyage.

On to my personal favorite:

New Jersey Senator Frank Lautenberg, who died June 3 at 89, was the 298th Senator to die in office. Of the 22 Senators who have died in office since 1970, 16 were over 70.

This is again presented in the context that the Congress is too old, so presumably the reader is expected to infer that (a) having 16 of the last 22 senators who died in office be over 70 is somehow bad and that (b) electing younger people to Congress would reduce this number.

Electing younger Senators and Representatives would indeed bring the percentage of those expiring in office who are 70+ down, at least marginally, because it would create more opportunities for someone relatively young to die in office. According to the Social Security Administration actuarial tables, though, the average life expectancy for a 25 year old male is 52 years (death at age 77) and the average life expectancy for a 25 year old female is almost 57 years (death around age 82). If our goal is to decrease the percentage of in-office deaths that occur beyond age 70, let's look at some options that would have a more significant impact:

• elect younger Senators and Representatives with serious, preferably terminal, illnesses;
• elect younger Senators and Representatives who enjoy participating in extreme (and hazardous) sports;
• elect younger Senators and Representatives who drive without using seat belts or ride motorcycles without helmets (preferably at high speed in both cases);
• elect younger Senators and Representatives who are on active duty in war zones;
• elect younger Senators and Representatives who are active members of street gangs or drug cartels;
• elect substantially more young Senators and Representatives with strict term limits (so that they cannot grow old in office).

I kind of like the last one; the other suggestions may not be very practical. More to the point, though, is that we need to ask why it is a bad thing that so many of the Senators who died in office were relatively old (or, from my current vantage point, "not particularly young"). If someone is going to die in office, I personally would just as soon have them lead a long and hopefully fulfilling life first. Now if we want to reduce the frequency of deaths in office, as opposed to the average age of those who go out with their boots on, I can think of a few measures (including cutting back on free food and alcohol provided by lobbyists), and electing younger members of Congress (of reasonable health and with reasonably conservative personal habits) would likely lead to a nontrivial reduction in frequency.

Streaking - Automotive Edition

If you came here expecting something about driving around nekkid, sorry to disappoint you: that's not the theme of this post. (Trust me when I say that nobody wants to see a guy my age tooling around in the buff.) This post is about cleaning car windows.

Among the many things I'm not good at (a very long list), washing car windows is a prominent item. I've tried glass cleaners, bleach-based cleaners, soap-and-water, plain water, even windshield washer solvent, and inevitably the windows end up with streaks. A bit of research turned up the fact that there are special purpose sprays, allegedly used by people who "detail" cars. I'm not that anal (and too cheap) to buy them. Fortunately, I've had a bit of luck recently, which I'm writing down here so that I won't forget it.

As a starting point, if the windows are really grungy, it's probably a good idea to wash off the bulk of the dirt with plain water, blotting stuff up with paper towels so that you don't leave mud caked on the windows. (Between endless road construction and my driving with the sun roof open, this is a nontrivial consideration, both exterior and interior.)

Next comes the secret elixir: vinegar and water. I read someplace that white vinegar works best, but I've been getting good results with apple cider vinegar, which is what I happen to have in the kitchen. The exact proportions of the mixture are a mystery to me, but I think it's safe to say more than half should be water. (Note to self: less vinegar next time. We're not making salad dressing.)

The other key tool is newspaper. For whatever reason, newpaper works better than even paper towels at both absorbing the dirt and not leaving streaks. I worried at first that the ink would bleed onto the windows, but that does not seem to be the problem. After a few brief experiments, it appears that (as with other uses) the New York Times does better than my local paper, but either will work. I'm not sure if really conservative papers will work as well; they may insist that you outsource the job. In any event, you'll want to read the paper before washing the windows with it.

One or two web sites talked about devoting a spray bottle to applying the mix, but that strikes me as overkill. Wad up one sheet of newsprint, dip one end in a bowl of the mix, and apply it. Wipe, and use the dry end to blot up any excess. Repeat as needed.

The results are not perfect, but they're better than anything I've achieved in the past.

Most Memorable Student Evaluations

Cleaning out my office at Michigan State University, I came upon a stockpile of Student Instructional Rating Systems forms (i.e., student evaluations). Over nearly 40 years of instruction (counting my time as a teaching assistant in graduate school), I accumulated thousands of these. Most were measured in tone, but some were glowing -- either glowing with pleasure at the course, or (more frequently) radioactive. Among those thousands of evaluation forms, three stand out in my memory.

Second Runner-up

A student (male, from the handwriting) once suggested to the administration that "Professor Rubin should be executed on public television". Left to the reader as an exercise: did he mean broadcast television generally (as opposed to cable), or the Public Broadcasting Service specifically? I'm not sure ratings on the latter would justify my sacrifice.

First Runner-up

This evaluation came in a freshman-level mathematics course I taught as a graduate assistant. As I recall, the course was populated mainly by juniors and seniors who had deferred it as long as they possibly could, and now had to face the music. The department evaluation form had a number of criteria on the front, with scores on a scale from 1 (excellent course/instructor) to 5 (terrible course/instructor). On the back there was space for an essay. The student (again, male based on handwriting) circled 5 for every question on the front, then wrote on the back "Best prof I've had at MSU!" Neglecting the minor discrepancy of calling a TA a "prof", this again introduces an element of uncertainty: did the student mistake the direction of the scale on the first page, or was he testifying to three or four truly horrid years of college?

And The Winner Is ...

My single most memorable evaluation has to be seen to be appreciated. It was submitted in a junior-level lecture course on quantitative models, required of all business undergraduates and populated primarily by seniors who had run out of room to procrastinate. Handwriting suggests a female author. The evaluation is actually quite lucid and rather well written. You can see by the author's use of available space that her response was rather impassioned (and prone to setting off Geiger counters).

One line from the first page clinches the trophy for this submission. The question asks for input on "Reading materials and written and oral assignments". The first line of the young lady's response: "Overhead packets [copies of transparencies used in lecture] were good but often times confusing as the formulas contained so many consonants."

I received this evaluation at the end of a fall quarter, and I was scheduled to teach the same course twice more that academic year. In the first class of winter quarter, amid the usual "welcome to the course" stuff, I mentioned that when I wrote a formula on the projector, students should treat 'Y' as a vowel. Unsurprisingly, most of them looked a bit confused at this.

Endnote

There is one more anecdote to pass along about this. Years after collecting all three of these submissions, I was attending a social hour for MBA students and chanced to speak with a brand new student from Korea (the one with the functional economy). He suggested something -- I forget what -- that arguably would have enhanced learning in the core quantitative methods course (which I taught), but at some cost to students' peace of mind. I explained to him that if I tried to implement his suggestion, students would "rip me a new one" on the evaluation forms. He asked me what I meant by "evaluation forms", and I explained our system to him. At the end of my explanation, he looked me square in the eye and said that the system was "stupid".

I learned that, approximately a year later, his undergraduate institution in Korea implemented evaluation forms.

Resolutions, Seasonality and Transient Effects

Today is New Year's Day (at least on the Gregorian calendar), and it is traditional for some people to usher in the new year by making personal resolutions. The theme for this month's INFORMS blog challenge is "O.R. and Resolutions", and to an O.R. person "resolutions" frequently implies "transient responses".  We make a resolution, attempt to adhere to it for a while (introducing a transient change in our behavior), then eventually revert to what we were doing pre-resolution (return to steady state).

I work out at a local YMCA. The Y does its programs in seven week sessions for the most part, with one- or two-week gaps sprinkled around near holidays. I'm not privy to enrollment data, but through decades of empirical study I and other members have identified a distinct seasonal pattern. Building use spikes at the start of the first session of the year (which will be tomorrow). Regulars who come in the evening will discover that parking spots are suddenly quite scarce. The spike is visible but considerably smaller in the mornings. Morning attendance skews toward retirees and the odd academic (pardon the redundancy). I suspect that retirees are less inclined to make resolutions, or alternatively more inclined to stick with them. Academics probably simply forget to make resolutions (just as we forget about matching socks, etc. -- we're too occupied with "profound" thoughts).

After the initial spike in attendance, there is a bit of gradual erosion, as "resolvers" discover that exercise is in fact a euphemism for physical exertion.  There's an abrupt drop (think step function) right around the end of the first seven-week session, and then a bit more erosion as attendance returns to a new steady state, barely distinguishable from the pre-New Year's steady state. Other seasonal patterns occur later in the year: a drop in building use during the summer, when outdoor activities and vacation trips lure people away; and a modest increase (noted only in the evening) between mid-April and perhaps mid-May (which I think of as "preparation for bikini season", and which does not seem to involve any retirees).

Besides offering an example of seasonality, the New Year's resolution phenomenon offers a metaphor for O. R. practice. The "resolver" diets, exercises, stops smoking or whatever for a while because the "boss" (their conscience) is paying attention.  When the "boss" stops watching, the "resolver" makes excuses for why the new regime is too difficult, and reverts to previous behavior.  An O. R. solution to a business problem that is implemented top-down, without genuine commitment by the people who actually have to apply the solution (and change behaviors in doing so), is likely to end up a transient response leading to a return to the previous steady state.

Addendum: Thanks to Mary Leszczynski for pointing out an article in Atlantic Monthly titled "This Is Why You Don't Go to the Gym". The article suggests that penalizing yourself for skipped workouts is a way to motivate follow-through on that New Year's resolution to get in shape. I've occasionally given some thought to why I'm as regular with my workouts as I am. One factor, which fits with the article, is that a little voice in the back of my head reminds me that I've already paid for the workout. (I'm a bit of a cheapskate, so that little voice gets heard.) Another factor is that I mainly do group workouts (aerobics, Tae Kwon Do), with occasional solo forays to the weight room or stationary bicycle. Group workouts can be more fun, but they also mean that slacking will be noticed by someone other than yourself. At my age, though, the principal motivator is fear of the alternative (what my body will turn into if I don't work out).

Charlotte's Literary Park

Across the street from the Charlotte (NC) Convention Center, site of the recent INFORMS conference, is a small park/shopping area that I think is known as "The Green". It contains a bit of statuary and some rather amusing "street signs" that I thought were worth remembering. In no particular order (and demonstrating no photographic skill whatsoever), here are some shots I snapped with my tablet's camera.

These two sculptures flank the entrance to the park:

(Sorry about the largely illegible engraving; the sun deserted me in my hour of need.) Toward the middle of the park, we have this somewhat curious choice:

I'm not sure what (if anything) they have to do with literature, and I could swear they were extras in an episode of Voyage to the Bottom of the Sea (a major contributor to my aversion to fish in restaurants).

Now for the lamp posts:

There was one other signpost, which I did not shoot because no angle did it justice. It had a half dozen or so signs pointing to other cities and towns named "Charlotte" (including Michigan's Charlotte, mispronounced "shar-LOT" by the locals). I have to wonder whether having a sign already devoted to the name "Charlotte" is why Charlotte Bronte did not earn a lamp post. (Alternate theories: Texas has the only town named "Bronte" in the U.S.; or Emily's shade bribed someone to one-up her sister.)

Time Series, Causality and Renting a Congressman

This morning I was reading an article, in a national (US) news magazine, that discussed energy policy decisions. It mentioned executives of companies in various energy-related industries contributing to the coffers of various congressmen (from both parties), and it mentioned their votes on key policy issues. The implication was clear: the votes were being bought, or at least influenced, by interested parties.

I understand why writers do this: it spices up the articles (a hint of corruption) without making any explicit charges that cannot be backed up with hard evidence; and it appeals to voters looking for confirmation of their prior belief that congressmen are crooks. I tend to view our elected representatives as by and large venal to some extent myself. The last part of the title of this post is motivated by a quote from Simon Cameron (Abraham Lincoln's first Secretary of War): "An honest politician is one who, when he is bought, will stay bought." As you can tell from the title, I am not sanguine about finding honest politicians.

As an OR professional, though, I understand the flaw in the argument (if we can characterize what is really innuendo as an "argument"). It relates in part to confusing correlation with causation and in part with confusing the direction of causation. Let's say that our fearless reporter accurately reports that Representative A votes for subsidies for domestic production of buggy whips, and Ms. B, CEO of a large manufacturer of buggy whips, donates regularly and/or generously to Rep. A's election campaigns. With minimal effort choosing words, our reporter can make this sound as if A voted for subsidies because B (and perhaps others of a similar mind) paid him off. That is indeed one possibility.

Another possibility is that A voted for subsidies first and then B donated, recognizing A (from his vote) as a friend of the buggy whip industry. There's causation, but in the opposite direction from what the reporter implied, and nothing venal. The nature of political contributions is that you usually contribute to candidates with whom you agree. (I say usually because lobbyists sometimes contribute to both sides, hoping the winner will remember their contribution to her and not to her opponent.)

Yet another possibility is that B contributed to A first, either anticipating a pro-buggy whip platform or for reasons unrelated to industrial policy, and A favors subsidizing domestic production for sincerely held (if possibly misguided) reasons. This is a case of trying to infer causation from what may be mere correlation.

How can we tell whether A's vote is in fact being purchased? Anyone who has done much with statistics recognizes how hard it is to establish causality, especially in the absence of a designed experiment with an appropriate control group. We could try tracking A's votes over time, matching them with B's contributions (or the contributions of B and other pro-subsidy individuals or groups), and look for a positive cross-correlation with lag 1 or higher (so that swings in donations lead swings in votes). A positive cross-correlation would still not be solid proof of vote-buying, though, and might also lack "power" as a test of vote-buying:  if A fits Cameron's definition of an honest politician, and consistently votes pro-buggy whip because he is taking graft, there will be no variance in his votes and therefore no cross-correlation.

This leaves me in the unsatisfying position of not knowing whether or not A is a crook. There have been enough US congressmen convicted of malfeasance to convince me that the proportion of occupants of Capitol Hill who are crooks is not zero.  Still, there is also a well known aphorism (of uncertain provenance) that might apply: "Never ascribe to malice that which is adequately explained by incompetence." We have ample evidence that incompetence is not in short supply on the Hill.

The Heisenberg Budget Principle

Watching Congress turn sirloin into (bad) hamburger during the recent borrowing limit debate/debacle, I realized that the Heisenberg Uncertainty Principle translates somewhat cleanly from particle physics to political economics:

The difference of two numbers can simultaneously have both positive and negative sign, depending on the position of the viewer (left or right side of the aisle).

I don't think this actually works in the real universe, but in the bubble universe of Washington D.C. it appears to hold.

Edit: I confess that I suck at physics. This probably is a manifestation of Einstein's special relativity rather than Heisenberg's uncertainty principle. First, it's not the act of observing the difference from a particular vantage point that makes it positive or negative; it's the location of the observer (and/or the observer's velocity toward the extreme of his/her party's ideology). Second, there is no uncertainty involved: one party is absolute, irrefutably certain the difference is positive; and the other party is equally certain the difference is negative. To admit a grain of doubt is to cause your party's bubble universe to collapse noisily and, worse still, to concede the possibility the other guys are right (this once).

The Curse of Basic Numeracy (or Why I Keep Gaining Weight)

Like all O.R. people (I hope!), and perhaps 2% of political officeholders in the U.S. (fewer if you restrict the count to Congress), I am functionally numerate. In particular, when ordering food at restaurants or high-calorie beverages (like the one I'm slurping as I type this) at coffee shops, I recognize when multiple sizes of the same order are priced so as to give the consumer an economy of scale.  For instance, the price of the frozen mocha in front of me comes from the following table:

Size (oz.)	Price (USD)	Marginal Cost (USD/oz.)	Average Cost (USD/oz.)
10	3.75	0.375	0.3750
16	4.35	0.100	0.2719
20	4.65	0.075	0.2325
24	5.05	0.100	0.2104

There is a modest diseconomy of scale in marginal cost going from the 20 oz. size to the 24 oz. size, the reason for which eludes me. That in turn bothers me at one level (I teach in a business school, so I feel that I should understand pricing models) and not at another (I occasionally fly on commercial airlines, whose ticket pricing algorithms appear to be the first "practical" application of chaos theory).

Obviously, being an O.R. person (and a business prof at that), I was compelled to order either the 20 oz. size (best marginal cost) or the 24 oz. size (best average cost). Thus do I, being perfectly rational, give the locker room scale one more reason to shudder when I walk in the door. I did order a reduced-calorie version, which is somewhat like playing stickball on a busy one-way street as opposed to a busy two-way street.

Update: I'm now sitting in another coffee shop, where I buy beans. They have a pretty sweet deal: buy a pound of beans (slightly more expensive bargain brands at the local supermarket, but not much more) and get a free drink, any type, any size.  I'm not sure exactly how many ounces in this drink, but the fact that it has its own lifeguard on duty is not a good sign. I truly do not want to think about how many calories it contains.

USENET: A Remembrance

Although I've already submitted a post to the July INFORMS blog challenge ("O.R. and Social Networking"), I cannot let the topic go by without a (an?) homage to sci.op-research. It is probably premature (albeit barely) to write an epitaph for USENET: in fact, its traffic apparently continues to grow, and where once you needed access to a USENET server, now much of it is accessible via Google Groups.

(image source: Wikipedia)

I suspect, though, that the traffic growth is more a tribute to our insatiable appetite for naughty pictures, bootleg videos and software, and passionate debates about atonal musicians than a testimonial to continued use of USENET as a social network for professionals.

I'm sure a lot of younger people think "social networks" started with MySpace and Facebook. For those of use who predate the Internet (yes, kids, a few of us remain), social networks were once both virtual and analog (cf. "Old Boy Network"). After the introduction of the Internet, but before the advent of the World Wide Web (second note to the kiddies: yes, the two are distinct, and came into being several years apart), we began to enjoy a new way of connecting with people outside our sphere of physical contact: bulletin boards systems (BBSes). These tended to be text only and slightly cumbersome, but they were for many of us the first medium for broadcast communication, where your message is not directed at a specific individual, unlike letters, telephone calls etc. (For me they were the second such medium; I was an amateur radio operator briefly in my teens.)

Then came the mother of all BBSes, USENET.  I think it caught on first with system operators, programmers and other "computer geeks", then with a smattering of other technical types. (Bear in mind that, in the early days of the Internet, access was somewhat limited, largely to universities and the military here in the U.S.)  Then came the flood of, um, less technical stuff (alt.animals.otters? alt.amazon-women.admirers??).  Circa 1993, Mohan Sodhi came up with the idea for a USENET group for operations researchers, and sci.op-research was born.

For a while, at least, sci.op-research was a way for individuals in the O.R. community to ask and answer questions, and for the occasional non-O.R. person to get help.  By 2009, Mike Trick was ready to pronounce it, and the rest of USENET, irrelevant. Today, sadly, it has little non-spam activity. (Mike gets the self-fulfilling prophecy award for creating OR-Exchange, which likely is the nail in sci.op-research's coffin.) Someone with a quick O.R. question or thought today may think Twitter first; for a longer question, they likely will look to a web forum (such as OR-Exchange). Google+ may yet become another viable alternative for communications with and among O.R. people.

Still, in its heyday sci.op-research (and at least portions of USENET) served a useful purpose ... and not just to let O.R. professionals network with each other. One time I answered a question from a practitioner (MS in some engineering discipline, no formal O.R. training that I recall) that led to an exchange of emails as we pinned down the answer to his question.  A year later he contacted me again, offering co-authorship in a paper (which landed in a respectable journal). To this day I've never met my co-author. Neither the collaboration nor the paper would have happened without USENET.

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?

A Seasonal TSP (Traveling Santa Problem)

You can tell when academics with blogs are between semesters by the increased frequency of their postings.  Yesterday Laura McLay posted a pointer to a 12-city traveling Santa problem (PDF file) at Math-Drills.Com.  Faced with a Christmas Eve choice of (a) paying bills, (b) performing some overdue data analysis for a paper-to-be or (c) playing with a TSP ... well, let's just say that I didn't need the Analytic Hierarchy Process to sort that one out.

Slightly (well, very slightly) more seriously, I was curious about the difficulty of the problem.  The TSP is one of the quintessential NP-hard problems, with all sorts of special purpose algorithms devised for it.  Sometimes, though, I think we confuse NP-hard with hard.  NP-hard refers to a class of problems.  At the risk of starting a flame war with purists (which will at least drive up my site stats), all optimization problems get pretty darn hard when they're big enough; we tend to believe that NP-hard problems get pretty darn hard faster than NP-not-so-hard problems as their size grows.  What is sometimes overlooked, though, is that all this is a sort of asymptotic result; we can solve not horribly large problems pretty easily (I can do the three city TSP in my head, at least after a cup or two of coffee), and the dividing line between doable and not doable continually shifts with improvements in hardware and software.

I wasn't really motivated enough to look up the latest and greatest algorithms for TSPs, so I started with an old, and I'm sure now "obsolete", method due I believe to Miller, Tucker and Zemlin ca. 1960.  It's a mixed integer linear programming formulation using binary variables to determine which links are included in the Hamiltonian circuit (route).  There are additional nonnegative variables that assign what we might call "potentials" to each node.  We require each node to be entered and exited once, and we require that any time a link is used, the potential of the destination city be at least one greater than the potential of the origin city, unless the destination city is the starting point for the circuit (i.e., unless the link closes the loop).  The MTZ formulation is more compact than formulations built with subtour elimination constraints (of which exponentially many can occur), but I believe it tends to have weaker bounds (and I've seen some papers on tightening the bounds in the MTZ formulation, but can't recall any details).

Anyway, driving back and forth between home and the YMCA (one of two loci of physical self-abuse for me), I mapped out a general strategy:  write a MILP model using the MTZ approach and see how long it takes to solve (using the Java API to CPLEX 12.2); see if identifying the single entry/single exit constraints as SOS1 sets (with "cleverly chosen" weights) helps; maybe try adding cuts on the fly to eliminate dominated segments of the tour (don't go A-B-C-D if A-C-B-D is shorter); maybe try depth-first search; etc., etc.  As always, to paraphrase someone (Napoleon?), the first casualty in every battle is the plan.  I wrote the basic MILP model with MTZ constraints pretty quickly (copying the data out of the PDF and into the Java editor, suitably reformatted, actually took longer than writing the code itself) and turned CPLEX loose with all default settings.  CPLEX found an optimal solution in something around 0.3 seconds (on my dual core laptop).  So much for any experiments in parameter tweaking, SOS1, and so on.

I won't publish the optimal route here, in case anyone is still working on it, but I will say that the length of the optimal solution is 30,071 miles -- and this is only 12 of the cities Santa must visit.  I hope he remembered to feed the reindeer.

New Toy for the Holiday: Google N-gram Viewer

Staring at one of the graphs in a recent post on the bit-player blog ("Googling the lexicon"), I was struck by a downward trend in the frequency of the phrase "catastrophe theory".  That led me to do a few searches of my own on Google's n-gram viewer, which is one of those insidiously fascinating Internet gadgets that suck away so much productivity. (Who am I trying to kid?  It's Christmas break; how productive was I going to be anyway??) Being a closeted mathematician, I first did a comparison of three recent "fads" (perhaps an unfair characterization) in math:  catastrophe theory, chaos theory and fractal geometry.

Then I took a shot with a few terms from optimization: genetic algorithms, goal programming, integer programming and linear programming.

I find it a bit surprising that chaos theory gets so much more play than fractal geometry (which has some fairly practical applications, as Mike Trick noted in his eulogy for Benoit Mandelbrot). Two other things (one I find serendipitous, one less so) struck me about the graphs.

The serendipitous note is that references to catastrophe theory are tailing off.  I recall sitting at a counter in a chain restaurant during my graduate student days, scarfing down breakfast while trying to chew my way through a journal article on catastrophe theory (which was rather new at that time).  Differential equations (especially nonlinear PDEs) were not my strong suit, to put it charitably, and the article was heavy going.  A few years later social scientists heard about catastrophe theory.  As I recall, the canonical image for it was a trajectory for a PDE solution on a manifold that "fell off a cliff" (picture your favorite waterfall here).  Social scientists are in the main clueless about differential equations (let alone PDEs on manifolds), but waterfalls they get.  The next thing I knew, all sorts of political science and maybe anthropology papers (not sure about the latter) were saying "catastrophe theory this" and "catastrophe theory that", and I'm pretty sure they were abusing it rather roundly.  So I interpret the decline in references as at least in part indicating it has reverted to its natural habitat, among a fairly small group of mathematicians who actually grok the math.

The less serendipitous note is that all the graphs are showing downward trends.  Since the vertical axis is in percentage terms, I cannot attribute this to a reduction in the number of published books, nor blame it on the Blackberry/iPod/whatever technical revolution.  My fear is that interest in mathematics in general may be on the decline.  Perhaps what we need now is for the next installment of the "Harry Potter" series to have Harry defeating the Dark Lord by invoking not incantations but mathematical models (but not catastrophe theory, please).

OR and ... Parking??

'Tis the season to shop our brains out.  Two trips to a local mall today (neither, oddly enough, for the purpose of shopping) has me reflecting on the science (art?) of finding and selecting parking spots.  Choosing a parking spot involves elements of stochastic search (anyone have a link for this?), optimization of a distance function, and (when the mall is busy) stochastic stopping rules.

The application of stopping rules is fairly obvious, although the rule to use may not be.  You're running a search pattern through the packed parking lot of a mall, looking for an empty spot, when lo and behold you find one.  Now comes the stopping rule:  do you grab it, or do you continue the search, hoping for one closer to your immediate destination (the first store you plan to hit)?  If you pass it up and fail to find something closer, it likely will not be there the next time you go by.  Add an objective function that balances your patience (or lack thereof), your tolerance for walking, the cost of fuel, any time limits on your shopping spree and the possibility of ending up in a contest for the last spot with a fellow shopper possessing less holiday spirit (and possibly better armed than you), and you have the stopping problem.

The other obvious aspect is optimization of a distance metric, and this part tends to amuse me a bit.  Some people are very motivated to get the "perfect" spot, the one closest to their target.  My cousin exhibits that behavior (in her defense, because walking is painful), as did a lady I previously dated (for whom it was apparently a sport).  Parking lots generally are laid out in a rectilinear manner (parallel rows of spaces), and most shoppers seem to adhere rather strictly to the L1 or "taxicab" norm.  That's the appropriate norm for measuring driving distance between the parking spot and the store, but the appropriate norm for measuring walking distance is something between the L1 and L2 or Euclidean norm.  Euclidean norm is more relevant if either (a) the lot is largely empty or (b) you are willing to walk over (or jump over) parked cars (and can do so without expending too much additional energy).  Assuming some willingness to walk between parked cars, the shortest path from most spots to the store will be a zig-zag (cutting diagonally across some empty spots and lanes) that may, depending on circumstances, be closer to a geodesic in the taxicab geometry (favoring L1) or closer to a straight line (favoring L2).  The upshot of this is that while some drivers spend considerable time looking for the L1-optimal spot (and often waiting for the current occupant to surrender it), I can frequently find a spot further away in L1 but closer in L2 and get to the store faster and with less (or at least not much more) walking.

This leaves me with two concluding thoughts.  The first is that drivers may be handicapped by a failure to absorb basic geometry (specifically, that the set of spots at a certain Euclidean distance from the store will be a circular arc, not those in a certain row or column of the lot).  Since it was recently reported that bees can solve traveling salesman problems (which are much harder), I am forced to conclude that bees have a better educational system than we do, at least when it comes to math.  The second is that, given the obesity epidemic in the U.S., perhaps we should spend more time teaching algorithms for the longest path problem and less time on algorithms for the shortest path problem.

[Confession:  This post was motivated by the INFORMS December Blog Challenge -- because I thought there should be at least one post that did not involve pictures of food!]

Obscure Engineering Conversion Factors

The following came around in this morning's e-mail, and I think it's amusing enough to be worth archiving. I've enlisted the aid of the Wikipedia to explain some of the jokes that rely on immersion in American culture.

1. Ratio of an igloo's circumference to its diameter = Eskimo Pi
2. 2000 pounds of Chinese Soup = Won ton
3. 1 millionth of a mouthwash = 1 microscope
4. Time between slipping on a peel and smacking the pavement = 1bananosecond
5. Weight an evangelist carries with God = 1 billigram
6. Time it takes to sail 220 yards at 1 nautical mile per hour = Knotfurlong
7. 365.25 days of drinking low calorie beer = 1 Lite year
8. 16.5 feet in the Twilight Zone = 1 Rod Serling
9. Half a large intestine = 1 semicolon
10. 1,000,000 aches = 1 megahurtz
11. Basic unit of laryngitis = 1 hoarsepower
12. Shortest distance between two jokes = a straight line
13. 453.6 graham crackers = 1 pound cake
14. 1 million microphones = 1 megaphone
15. 1 million bicycles = 1 megacycle
16. 365 bicycles = 1 unicycle
17. 2000 mockingbirds = two kilomockingbirds
18. 10 cards = 1 decacard
19. 52 cards = 1 deckacard
20. 1 kilogram of falling figs = 1 Fig Newton
21. 1000 ccs of wet socks = 1 literhosen
22. 1 millionth of a fish = 1 microfiche
23. 1 trillion pins = 1 terrapin
24. 10 rations = 1 decaration
25. 100 rations = 1 C-Ration
26. 2 monograms = 1 diagram
27. 8 nickels = 2 paradigms
28. 5 statute miles of intravenous surgical tubing at Yale University Hospital = 1 I.V. League

INFORMS Debrief

The national INFORMS meeting in Austin is in the rear-view mirror now (and I'm staring at the DSI meeting in San Diego next week -- no rest for the wicked!), so like most of the other bloggers there I feel obligated to make some (in my case random) observations about it.  In no specific order ...

• The session chaired by Laura McLay on social networking was pretty interesting, particularly as we got an extra guest panelist (Mike Trick joined Anna Nagurney, Aurelie Thiele and Wayne Winston, along with Laura) at no extra charge. Arguably the most interesting thing from my perspective was the unstated assumption that those of us with blogs would actually have something insightful to say. I generally don't, which is one reason I hesitated for a long time about starting a blog. 
• On the subject of blogs, shout-out to Bjarni Kristjansson of Maximal Software, who more or less badgered me into writing one at last year's meeting. Bjarni, be careful what you wish for! :-)  It took me some digging to find Bjarni's blog (or at least one of them). Now if only I could read Icelandic ...
• I got to meet a few familiar names (Tallys Yunes, Samik Raychaudhuri ) from OR-Exchange and the blogosphere.
• Thanks to those (including some above) who've added my blog to their blogrolls.  The number of OR-related blogs is growing pretty quickly, but with growth come scaling issues. In particular, I wonder if we should be looking for a way to provide guidance to potential readers who might be overwhelmed with the number of blogs to consider. I randomly sample some as I come across them, but if I don't see anything that piques my interest in a couple or so posts I'm liable to forget them and move on, and perhaps I'm missing something valuable. This blog, for instance, is mostly quantitative (math programming) stuff, but with an occasional rant or fluff piece (such as this entry).  I wonder if we could somehow publish a master blog roll with an associated tag cloud for each blog, to help clarify which blogs contain which sorts of content.

Getting off the social network tram for a bit ...

• A consistent bug up my butt about INFORMS meetings is their use of time. Specifically, the A sessions run 0800 to 0930, followed by coffee from 0930 to 1000. There is then an hour that seems to be underutilized (although I think some plenaries and other special sessions occur then -- I'm not sure, as I'm not big on attending plenary talks). The B sessions run 1100 to 1230 and the C sessions run 1330 to 1500. So we have an hour of what my OM colleagues call "inserted slack" after the first coffee break, but only one hour to get out of the convention center, find some lunch and get back. It would be nice if the inserted slack and the B session could be flipped, allowing more time for lunch. My guess is that the current schedule exists either to funnel people into plenaries (who might otherwise opt for an extended lunch break) or to funnel them into the exhibits (or both).
• We're a large meeting, so we usually need to be in a conference center (the D.C. meeting being an exception). That means we're usually in a business district, where restaurants that rely on office workers for patronage often close on Sundays (D.C. and San Diego again being exceptions). Those restaurants that are open on Sunday seem to be caught by surprise when thousands of starving geeks descend en masse, pretty much all with a 1230 - 1330 lunch hour. For a society that embraces predictive analytics, we're not doing a very good job of communicating those predictions to the local restaurants. (Could INFORMS maybe hire a wiener wagon for Sundays?)
• The layout of the Austin convention center struck me as a bit screwy even without the construction. For non-attendees, to get from the third floor to the fourth floor you had to take an escalator to the first floor (sidebar: the escalator did not stop at the second floor), walk most of the length of the facility, go outside and walk the rest of the length, go back inside and take an escalator to the fourth floor (sidebar: this escalator did not stop at either of the two intervening floors). Someone missed an opportunity to apply the Floyd-Warshall algorithm and embed shortest routes between all nodes in the map we got.
• The sessions I attended ranged from fairly interesting to very interesting, so I have absolutely no complaints about that. I also had good luck networking with people I wanted to see while I was there. Since sessions and networking are my two main reasons for attending a conference (my own presentation ranks a distant third), it was well worth the trip.

The conference, like all its predecessors, allowed me to collect some new observations that add to the empirical evidence supporting my theories of Geek Physics (which depart from classical Newtonian physics in a few regards). In particular:

• A geek in motion will come to rest at the location that maximizes interdiction of other traffic (particularly purposeful traffic).
• A geek at rest will remain at rest until someone bearing a cup of coffee enters their detection range, at which point they will sharply accelerate on an optimized collision course.
• A geek entering or exiting a session in progress will allow the door to slam shut behind them with probability approaching 1.0. (Since I have no empirical evidence that geeks are hard of hearing, I attribute this to a very shallow learning curve for things outside the geek's immediate discipline, but I'm having trouble collecting sufficiently specific data to test that hypothesis.)

If anyone has observed other laws of Geek Physics that I'm missing, I'd be interested in hearing them.

Enough about the conference, at least for now. It was interesting, I enjoyed interacting with some people I otherwise only see online, and I brought home a bunch of notes I'll need to sort through. I'm looking forward to next year's meeting.