OR in an OB World

OR and Base Voters: Common Pitfalls

2012-02-21T14:44:00.000-05:00

My adopted state of Michigan is currently afflicted with the Republican presidential primary. (Symptoms include repetitious attack ads on television, robocalls to one's house, and the general malaise associated with staring at any crop of candidates for political office.) Primaries tend to draw out "base" voters (those committed to one party or the other); we swing voters just stay at home, hiding under the covers until it is over.

Last night the local TV news included a sound bite from a generic Republican voter, an apparently intelligent and articulate woman (to the extent one can judge these attributes from a two sentence interview) who said she was still undecided because she wanted to vote for the "most conservative" candidate. The logic, or lack of logic, behind that statement caused me to take notice of the similarities between how some "base" voters think and common errors in operations research.

A single criterion is easy, but multiple criteria may be correct. There are quite a few pressing issues these days, ranging from foreign policy to budget deficits to global warming to unemployment to ... (I'll stop there; I'm starting to depress myself). Our base voter, henceforth Mme. X, has apparently condensed these criteria down to a single value, on a scale from hard core liberal (arbitrarily 0) to hard core conservative (arbitrarily 1). What is not apparent is how the multiple dimensions were collapsed to a single one. OR people know that multiple criterion optimization is hard, more from a conceptual standpoint than from a computational one. Using a single composite criterion (weighted sum of criteria, distance from a Utopia point in some arbitrary metric, ...) makes the computational part easier, but there are consequences (frequently hidden) to the choice of the single criterion. Goal programming has its own somewhat arbitrary choices (aspiration levels, priorities) which again can have surprising consequences. Picking the "most conservative" candidate simplifies the cognitive process but may lead to buyer's remorse. Similarly, arbitrarily collapsing multiple objectives into a single objective may simplify modeling, but may produce solutions that do not leave the client happy.

Averages can be deceptive. Point estimates also make modeling and decision making easier, but they can mask important things. (A colleague has a favorite, if politically incorrect, quotation: "Statistics are like bikinis. What they reveal is interesting, but what they conceal is critical.")

Suppose that Mme. X has narrowed her choices down to two candidates, and that they have both weighed in on five important issues (A through E). If candidate 1 is consistently to the right of candidate 2 on all issues, we have a dominated solution: Mme. X can eliminate candidate 2 and vote for candidate 1. On the other hand, consider the following scenario, where each candidate's position is rated on a scale from 0 (liberal) to 1 (conservative).

Candidate 1 is more conservative than candidate 2 in both mean (0.780 versus 0.756) and median (0.80 versus 0.75); yet candidate 2 is to the right of candidate 1 on two of five issues (A and B), and close to a wash on a third (C). So if Mme. X truly wants a conservative candidate, it is not all that clear which she should prefer. Likewise, OR models that consider only point estimates without taking dispersion into account can result in solutions that should do well "on average" but sometimes do quite poorly.

A solution that goes unimplemented is not a solution. Missing in Mme. X's search for the most conservative candidate is the quality referred to by pundits as "electability". Neither major political party claims a majority of registered voters in the U.S., so to win a general election, a candidate must capture a significant number of moderates and independents. The most ideologically pure candidate (for either party) may not be able to do so. This is a bit of a paradox in recent elections, where candidates find that they must appeal to "base" voters at one end of the political spectrum to get the nomination, then appeal to voters in the middle of the spectrum to win the election. Ideological "base" voters may not grasp this particular reality; they expect the "correctness" of their candidate's views (which are also their views) to triumph. [This may be at least partly explained by the false consensus fallacy.]

OR modelers sometimes have a similar blind spot. We can pursue perfection at the expense of good answers. We can opt for the approach that uses the most sophisticated or "elegant" mathematics or the most high-powered solution technique available. We may try for more scope or more scale in a project than what we can accomplish in a reasonable time frame (or what users can realistically cope with, in terms of data requirements and solution complexity). Professional journals often encourage this trend by requiring "novel" solution methods in order to publish a paper. The end result can be a really impressive solution that sits on a shelf because the client is unwilling or unable to implement it, or because it is too complex for the client to understand and trust.

Garbage in, garbage out. OR models rely on data, as inputs to the decision process or to calibrate parameters of the model. Feed bad data to an otherwise correct model and no good will come of it. I have seen estimates that as much as 60% of the time in an OR project can be spent cleaning the data.

Meanwhile, Mme. X has to rely on a variety of unreliable sources to gauge how conservative each candidate may be. Candidates famously say things they may not entirely believe, or express intentions they may not carry out, either in an overt effort to curry voters or because their views change between campaigning and governing. Historical data may be faked or misreported, and sometimes facts may not be what they seem. For instance, a generally pro-military candidate might vote against a military appropriation bill because there is a rider on it that would fund an inordinately wasteful project, or something unpalatable to the candidate and/or the candidate's constituents. Opponents will characterize this as an anti-military stance. Budget projections, and indeed any sort of projections, are subject to forecast errors, so a candidate's magical plan to fix deficits/unemployments/Mme. X's dripping kitchen faucet may turn out not to be so magical after all. Unfortunately for Mme. X, she probably has less ability to filter and correct bad data than an OR analyst typically does.

So, in conclusion, voters and OR analysts face similar challenges ... but OR analysts do not have to cope with a glut of robocalls.

Java Plugin for Firefox 10

2012-02-13T17:57:00.001-05:00

Today marked yet another upgrade in Firefox, from version 10.0 to 10.0.1. Whether it was this upgrade or the previous one I cannot be sure, but I discovered (the hard way) that one of them broke the use of Java applets on my office PC. Specifically, the Java plugin (which I use infrequently, but which had worked a while back) was simply gone.

Well, the plugin itself (which comes from the portion of Oracle that once was Sun) couldn't be gone -- Firefox can't delete chunks of my JRE. Only the link to it was gone. There is a handy Synaptic meta-package (sun-java6-plugin) in one of the Ubuntu repositories, intended (I think) to make the connection between plugin and browser. I reinstalled it, to no avail. I'll skip the full litany of web search results (many out of date) and failed attempts, and cut to the chase scene. Besides having a recent Oracle/Sun Java JRE installed (and, of course, Firefox), you need to do something to tell Firefox where to find the Java browser plugin. The rest of this is specific to Linux; Windows and Mac users will have a somewhat different task.

You need to find a Firefox plugins directory, in which to place a symbolic link to the plugin. There are multiple choices, and more than one of them may be suitable. Some documents refer to a plugins folder under ~/.mozilla (although I suspect this now should be ~/.mozilla/firefox/<your configuration>). I didn't have such a folder, so I created one (although I ended up not using it). Another possibility is /usr/lib/firefox/plugins. I'm not sure if that one is scanned, or if it's just vestigial from some earlier version. I ended up using /usr/lib/firefox-10.0.1/plugins ... which I may regret if I have to go through this again with the next upgrade.
You need to find the right plugin file. This is where I wasted most of my time. Older documentation refers to libjavaplugin_oji.so, which I found in /usr/lib/jvm/java-6-sun/jre/plugin/i386/ns7. It's in a folder named "plugin", so it must be the right file, mustn't it? Oops, no. It turns out there's a "next generation" plugin named libnpjp2.so, and apparently FF 10 will only recognize the new plugin. Oracle's installation docs refer to it, but I could not find it in the plugin directory. That's because it's not in the plugin directory. I guess they thought that would be too obvious. It's in /usr/lib/jvm/java-6-sun/jre/lib/i386.
Once the targets are in sight, shut down Firefox, go to the directory you selected in step 1 (in a terminal), delete any symlinks to older plugins, then execute sudo ln -s /usr/lib/jvm/java-6-sun/jre/lib/i386libnpjp2.so, adjusting the path as needed if your JVM is installed elsewhere. (The sudo is unnecessary if you chose a folder in your home partition in step 1.) Restart Firefox and check the plugins tab (or enter about:plugins in the URL bar) and make sure Firefox acknowledges the plugin.

Update: I just checked my home PC (same configuration as the office PC, other than being 64 bit rather than 32 bit). There's no problem with the Java plugin at home. So perhaps I was wrong in blaming a FF update at the office for zapping the connection to the plugin ... but if not an update, then what?

The Case of the Dormant Function Keys

2012-02-11T11:32:00.001-05:00

There's an intermittent problem on my home PC (Linux Mint) that's been driving me slightly buggy (okay, slightly buggier). My mail client is Thunderbird, and when composing messages I frequently hit the F9 key, which should open the "Contacts Sidebar", from which I can select recipients. Usually it does. On my office PC and laptop it always does. At home, though, it sometimes doesn't -- the F9 key goes mysteriously dead in T-bird. I can work around it by opening the contacts sidebar from a menu, and eventually the problem disappears (for a while).

Today, though, it happened again and I decided to try to sort it out. Testing with other programs showed that all the function keys, not just F9, were dead, and in all applications. I checked system settings in the control panel, and could find nothing that would be remapping the F keys. A bit of work with Google, though, turned up the culprit: my keyboard.

I have a Microsoft ergonomic keyboard at home (and only on the home PC). Microsoft decided to assign alternate functions to all the F keys, so that, for example, F9 does double duty as the "Send" key (with a different key code). At the end of the row of function keys is an "F Lock" key. (For reasons that will become clear, I cannot get out of my head another name for it, also starting with "F" and ending with "ck".) The F Lock key toggles function keys between their normal key codes and the alternate codes. It apparently cannot be controlled by the operating system -- or at least nobody has figured out how. Microsoft being Microsoft, they decided that the F Lock key has to be on for function keys to act as function keys (which seems to suggest that the being a function key is not the normal role of the function key). Whatever.

The problem, as reported by various people, is that the F Lock apparently toggles randomly, without the key being struck. In my case, this may mean that the state of the function keys at startup is random -- the keyboard sometimes wakes with F Lock on and sometimes with F Lock off. With the culprit identified, there are two possible resolutions. For now, I'll try the lazy approach: do nothing special, but keep an eye on the F Lock status light. If it becomes too hard for me to remember this (the problem is, after all, intermittent), the more involved solution is to use the xev utility (which displays keyboard events, including key codes) to make a list of the key codes of the 12 function keys, both with and without F Lock engaged, and then use the xmodmap utility to map the key codes for the non-standard functions (undo, redo, reply, send, ...) back to the same virtual keys as the function keys (so that F9 looks like F9 to the system, regardless of the status of F Lock).

Slaying a Zombie Browser Extension

2012-02-04T14:51:00.000-05:00

I just finished a marathon session (on Linux Mint Katya) trying to uninstall Stylish, a zombie extension for the Firefox web browser. I have nothing against Stylish, and I don't think it was the culprit in this story, but I'm recording my methods here both to preserve them for myself and in case anyone else is locked in this battle.

Somewhere along the line, I must have installed a version of Stylish, although I don't recall when or why. As Firefox went to its current whirlwind upgrade cycle, the installed version of Stylish (1.0.7) became incompatible. With each upgrade, I would instruct Firefox to look for a compatible version, and it would either report failure or find one, attempt to install it, and report that the upgrade attempt had failed (with no explanation why). Either way, the browser would open with Stylish 1.0.7 installed and disabled.

This dance got boring after a while, and I could not think of a reason for keeping Stylish, so when Firefox upgraded itself to version 10.0 today I decided to uninstall Stylish ... which is when I discovered it was now a zombie. If you know anything about zombies, you know that they are difficult to kill. The instructions for uninstalling an extension are simple: open the extensions tab, find the one you no longer want, and click the uninstall link. If there is an uninstall link -- and with Stylish, there was not. Further searching revealed the helpful session that one boot Firefox in safe mode and then click the previously disabled uninstall link ... except there was no uninstall link, disabled or otherwise (nor did one magically appear when I switched to safe mode).

One can invoke Help > Troubleshooting Information in Firefox and find the file or directory name of the extension, then track the file or directory down in the Firefox extensions folder and nuke it manually. I was able to find the folder name this way (a hex string inside braces), but no folder or file of that name existed in my profile's extensions folder. This may mean it is installed globally, and sure enough, I found a folder of the correct name in /opt/firefox/extensions. I nuked it (as root) and restarted Firefox. The zombie still lived (still listed as disabled).

Upon further searching, I found an SQLite database belonging to Stylish: /opt/firefox/defaults/profile/stylish.sqlite. I nuked it (as root) and restarted Firefox. The zombie persisted.

Well, perhaps I was overthinking this. With Firefox in safe mode, I installed the latest version of Stylish (1.2.5), then restarted Firefox. Although Firefox had failed to do the upgrade on its own, this worked. The new version was installed and not disabled ... which meant it had a functioning uninstall link ... and there was no mention of version 1.0.7. So I clicked the uninstall link. After restarting Firefox, I found that Stylish 1.2.5 had successfully uninstalled ... and the 1.0.7 zombie had reappeared.

So I closed Firefox and opened the extensions.sqlite database (in my Firefox profile folder) using the SQLite database browser. Here I was able to find an entry for Stylish 1.0.7. It pointed to a directory (with the same hex string name as the one I'd nuked from /opt/firefox/extensions), this time located in /usr/lib/firefox-10.0/extensions. Nothing I'd turned up in any of my Google searches pointed to /usr/lib (other than perhaps references to "globally installed" extensions, with no indication of where that would be -- hence my earlier search of /opt/firefox). I deleted the newly found subdirectory (as root), restarted Firefox, and woo-hoo! No sign of the zombie.

OR in Restaurants

2012-01-30T17:56:00.000-05:00

The topic for this month's INFORMS blog challenge is "OR and Food". I suspect that a number of my fellow bloggers will jump on the diet problem example, also known as the Stigler diet. That also happens to be the name of Tim Hopper's blog, so I'm inclined to leave it to him. Also, while LP diet models may be suitable for selecting animal feed, I think the Geneva Conventions prohibit their use on humans.

My expanding circumference and history at restaurants (*, **) makes it reasonable for me to write, instead, about applications of OR to food service. There are, in fact, a surprising (at least to me) number and variety of these.

Here at Michigan State University we have The School of Hospitality Business (SHB), the second-ranked hospitality business school in the country (behind Cornell's). Years ago, one of my colleagues from SHB, Dr. Michael Kasavana, told me that restaurant chains (and perhaps individual restaurants) use linear programming as part of menu engineering. (***) That's Mike getting credit in the first footnote of the Wikipedia entry, putting him one up on me in the Internet fame competition. See, for instance, "How Do Restaurants Use Linear Programming for Menu Planning?" for a (very) non-technical introduction. Unfortunately, I couldn't find a more suitable link for an OR-savvy audience.
Researching this entry, I tripped over a few papers using Data Envelopment Analysis to determine whether restaurants in general, and specifically their use of IT in at least one case, are operating "efficiently".
I found a doctoral dissertation entitled "Managing Restaurant Tables Using Constraint Programming", whose connection to OR should be self-explanatory. The problem encompasses the assignment of tables to diners, both via reservations and walk-in traffic, the possible combination of tables for larger parties, negotiation of reservation start times, and possible on-the-fly reallocation of tables.
Linear programming has been applied to staffing problems, including the staffing of restaurants (where service personnel, including cooks, are assigned to shifts).
The "Caterer Problem" is a classic LP/IP application, in which a hypothetical caterer using linen napkins has to plan how to cover demand at minimum cost by acquiring new napkins and laundering soiled napkins (typically via either of two methods with differing lead times and costs). I don't know how often LP models are actually used by caterers or restaurants, but "it's the thought that counts".
It is well-known that simulation is used to help design both facilities and production systems. Simulation modeling at Burger King was documented in an Interfaces article, and they apparently went so far as to distribute a simulation model to restaurant operators as part of a "Productivity for Planning for Profit Kit". Although I can't find the articles documenting it, BK famously redesigned their restaurants (quite a while back) using a simulation model. At that time I was a fairly regular BK customer. Originally, when I walked up to the counter inside, there would be multiple production lines oriented orthogonal to the counter, so that beef patties started at the back of the store and, in the process of moving toward me, magically transformed into ready-to-eat hamburgers. One day I entered a BK and discovered that there was now a single, U-shaped production line, with the long sides parallel to the counter. A patty started at one end of the line and morphed into a burger by the time it reached the other end of the line. Apparently this redesign was the result of a simulation study.

So OR has its fingerprints all over the food service industry ... and is therefore to blame for the steepest ascent trajectory of my waistline. (This being an election year, I will join the candidates in abdicating all personal responsibility.)

(*) True story #1: In graduate school, friends would invite me to dine with them at a local all-you-can-eat buffet restaurant just to watch the carnage.

(**) True story #2: A local sub shop once experimented with pizza sales. Someone posted a handwritten sign on the wall: "Pizza by the slice, Sunday noon to 4:00, all you can eat". So I stopped by on Sunday. The following week, the sign was amended: "Pizza by the slice, Sunday noon to 4:00, all you can eat except Paul".

(***) True story #3: Early in my career, I was teaching linear programming to MBA students. This being before the advent of free or affordable optimization software, I was in fact teaching them the simplex algorithm, by hand. (I have since realized the error of my ways.) At the end of one term, a young lady in the class came up to me, identified herself as a hospitality business major, and proceeded to "chew me a new one", pointing out to me in graphic detail just how useless all this simplex stuff was for her, particularly given her concentration. I later learned that, the very next term, she had a course in her major from the aforementioned Prof. Kasavana ... in which she had to solve linear programs ... by hand. The universe does, in fact, have a sense of humor.

The Most Desperately Needed Degree Program

2012-01-19T18:06:00.000-05:00

This morning I stumbled across an article on Yahoo! Eduction with the provocative title "College Majors That Are Useless". Curiosity made me look at the article. What I saw made me double down on my morning coffee intake, since I assumed my brain was not yet functioning.

Two disclaimers are warranted. First, my majors were mathematics and mathematics (with a little statistics in between), so I have no personal attachment to the listed majors. Second, and somewhat contrary, I've spent almost 39 years at Michigan State University (the former Michigan Agricultural College), a land-grant institution with a very strong College of Agriculture and Natural Resources (CANR) and a respected agricultural extension service. While we are a typical, well-rounded university (strong in physics, education and a variety of other fields), we're very proud here of both our land-grant tradition and our strength in agricultural fields. (Note to snobs: Cornell University is another land-grant university.)

CANR is not hurting for majors, and I have not heard of any problems with placement of those majors, so I was rather shocked to see that the first, fourth and fifth "most useless" majors (agriculture, animal science and horticulture) all came from their domain. As a sidebar, we also offer the other two listed majors, apparel design and theater, albeit in different colleges. The article cites the "National Association of Colleges and Employers' (NACE) 2012 Job Outlook study", which is free to members (whoever they may be), and which apparently "surveyed almost 1,000 employers on their future hiring plans". Our library system does not have it, so I can comment on neither their methods of data acquisition and analysis nor the accuracy with which their findings were reported in the article. Naturally, that won't stop me from commenting on the article itself.

First, as a colleague pointed out to me, the article states that 24,988 agriculture degrees (baccalaureate? all levels?) were awarded (in the United States?) in 2008-2009. Amazingly, again according to the article, 24,988 horticulture degrees were awarded that same year. (I should have gone to commencement exercises. Do you suppose that the two majors paraded together in pairs, as if boarding the ark?) The article reports 89,140 degrees awarded in fashion design that year, which in another coincidence is exactly the number of theater degrees awarded. Two cosmic coincidences in the same article ... I wonder what the probability of that is?

For what it's worth, the article cites the source of the degree counts as The Daily Beast's list of "20 Most Useless Degrees". The first "useless degree" cited on that list, in what I consider to be a multilayered bit of irony (and with an apology to yet more of my colleagues), is journalism.

Second, referring to the NACE study, the article states that "[m]any areas of study, such as fashion design and the performing arts, didn't even make the list". Does this mean that two of the five "useless" majors were designated that way because there was little or no data in the study on them? The article does quote job growth or decline projections for all five majors, including fashion design and theater, obtained from the U.S. Department of Labor.

Third, the criterion of "uselessness" of a major is not clearly spelled out in the article. From the focus on numbers of jobs and projected trends in those numbers, I infer that "uselessness" relates in some way to job prospects. Operations researchers know that if you are going to develop a normative model, you need to define your criterion or criteria carefully. This is what drove me to blog about the article: not just that the criterion is at best implicitly specified, but that it is not tied to the data in any logical way that I can see.

Is a major "useless" if the number of related jobs is declining? That is suggested in the discussion of agriculture, the first (and therefore most?) "useless" major on the list. "... That means less [sic] jobs. In fact, the U.S. Department of Labor projects 64,000 fewer jobs in this field over the next seven years." Okay, then why is theater (with projected job growth of 11% in the same time frame) third on the list of "useless" majors.

Is "uselessness" based on a glut of applicants? You might speculate that from the inclusion of fashion design, where the government says there were 22,700 jobs in 2008 (with a projected 1% growth over the next seven years) and the article claims that 89,140 students (all with a dual major in theater?) graduated with degrees. That would be rather scary if the only relevant job for someone with a fashion or apparel design degree were as a fashion designer (and assuming that fashion designers had a projected career span of more than three months). My impression, though, is that retail chains like to hire fashion/apparel design majors as buyers, because they bring an understanding of the product to their work. Similarly, agriculture majors are in demand for more than managing farms; food safety inspectors, sales representatives and marketers for firms selling agricultural equipment or products, buyers for grocery chains etc. may all benefit from that degree. In any case, if the ratio of jobs to graduates is the concern (and I assume that jobs here include occupied positions, not just open positions), then agriculture (25,000 degrees in '08-'09 versus 1,234,000 "agricultural managers" in 2008) would seem to be a pretty appealing choice. That's roughly one graduate for every 49 positions, which would be about replacement rate if you assumed 2% turnover per year. For comparison purposes, if you ran a company with a fixed number of positions, and your employees stayed for life and retired after an average of 40 years on the job, that would be 2.5% turnover. (By the way, in an article full of statistical "coincidences", I have to look at the first four digits of "1,234,000" and wonder if that's another one.)

I've ranted long enough, so let's just conclude this with two thoughts. The first is that I am, shall we say, unpersuaded by the article. The second, referring back to the title of this post, and tying into recent posts by Mike Trick and others, is that if I were trying to devise a new college major today, based on need, it would be titled something like "journalistic analytics", and it would focus not on parsing server logs at a site like the Daily Beast but rather on how to draw and present meaningful conclusions from the analysis of data.

Donating a Computer? Wipe the Drive!

2012-01-15T13:41:00.000-05:00

Months ago I replaced my old single-core PC with a new quad-core machine. Being a champion procrastinator, I'm only now getting around to donating the old box to charity. The easy part is assembling all the documentation, peripherals, etc. (I'm also a bit anal-retentive about storing documents.) The hard part turns out to be wiping the drive.

It should be common knowledge that you never give away a computer without first wiping its hard drive. Over the years, your various user IDs and passwords are stored on the computer in all sorts of places, some of which (at least with Windows) are a bit arcane. Stories have been written on the subject (see, for instance, "The Dangers of Donating or Discarding Your Old Computer", or "Hard Drives Exposed"), although I was unable to find any statistics on actual instances of identity theft from discarded drives. (I found lots of general discussion of the threat, much of it shockingly coming from companies that sell disk wiping software or services.) The same caution also applies to smart phones and USB (thumb) drives, and I suspect people are even less cautious about cleaning out their phones before recycling them. Anything that still works and has ever held a password is a candidate for scrubbing before you recycle or donate it, or before you hand it off to someone that you think is going to toss it in a landfill.

There is quite a variety of software, both free and commercial, designed to delete files and wipe drives "securely" from PC disks. I put "securely" in quotes because security is a matter of degree. The only 100% secure way to eliminate sensitive information is to physically destroy the drive (break the platters into pieces, bathe them in acid, launch the remnants into the core of the sun, ...). Runner up is to run a shredder program that overwrites each disk block with various random patterns. The least secure approach is reformatting the drive, which typically does not wipe out old contents.

I'm not worried about an identity thief going over my donated hard drive with forensic equipment, so I'm satisfied with shredding all the files. For reasons unclear to me, though, that turned out to be problematic on the old machine. In fact, just booting the bugger turned out to be problematic. In my years of fighting with PCs, thermal expansion has usually been a problem when the machine was turned on and off, not when it was serving as an unplugged doorstop. Nonetheless, it took three tries reseating memory and PC cards before the old machine would boot, and a fourth try to get it to recognize the keyboard and mouse. Whether that relates to the subsequent adventures, I'm not sure.

My plan was to wipe the lone hard drive entirely and then reinstall Windows XP. To do so, I downloaded Darik's Boot And Nuke, which seems to be a highly regarded solution. Burn it to a CD or DVD, boot from the disk, follow a few simple instructions and watch your disk get wiped. Unfortunately, it consistently failed with a sequence of error messages that did not tell me what was going on. The old computer has a bunch of media readers (which I explicitly did not select for wiping); maybe they were causing problems. Maybe not.

As at least an interim measure, I installed Linux Mint Katya, using the entire hard drive and overwriting the Windows installation. That does not wipe all the data, although I feel moderately confident that the portion of the disk containing actual Linux files is sufficiently overwritten to defeat the casual data thief. The problem is all the unused space on the disk, which still contains whatever it held before I loaded Katya. After a bit of searching, I found the Linux shred command. The suggestion was to boot from a CD or DVD (I used the Katya installation CD) and run shred -vzf /dev/sda (replacing /dev/sda with the name of the actual hard drive partition). Small problem: the hard drive was not showing up in /dev. The Katya installation disk lets you mount the existing hard drive, so I did that. It mounted as /media/<long number>. Okay, fine, I would just shred /media/<long number> ... except I couldn't: the shred command said it was a directory and not writable (even with the -f flag, which should force things to be writable). Running shred with administrator privileges via sudo did not help.

After more searching, I found a helpful answer by David Spillett. Booting the clunker from the hard drive (Mint Katya), I opened a terminal in /tmp and entered the following commands:

dd if=/dev/zero of=zero.small.file bs=1024 count=102400
cat /dev/zero > zero.file
rm zero.small.file
rm zero.file

The drive capacity is 165 GB, and Katya's footprint is not all that large, so the second line was quite time consuming. The second line eventually ended in an abort due to lack of free memory. I'm not sure that was an intended result, but it does not seem like a bad thing.

Overwriting with one layer of zeros is not a very secure shred, but (again) I'm not that worried about someone using forensic hardware to recover my drive. If they do, they'll find their investment of time not well rewarded.

Max/Min Bounds

2012-01-04T14:19:00.000-05:00

Motivated by a recent question on OR-Exchange, this post expands on a previous post about constraints that set a variable equal to the maximum or minimum of other variables in a mathematical program. Here I'll deal with inequality bounds (and with more than two variables involved in the maximum/minimum).

The setting is a mathematical programming model containing variables $x_1,\dots,x_n$ and $y$, where you want to bound $y$ either above or below by either $\max_{i=1,\dots,n} x_i$ or $\min_{i=1,\dots,n}x_i$. Let's dispense with the easy cases first. Since \begin{eqnarray*}y\ge\max_{i=1,\dots,n}x_{i} & \iff & y\ge x_{i}\forall i=1,\dots,n\\y\le\min_{i=1,\dots,n}x_{i} & \iff & y\le x_{i}\forall i=1,\dots,n\end{eqnarray*}those two cases are handled by expanding one nonlinear inequality into $n$ linear inequalities, with no requirement that the variables be bound and no introduction of integer variables.

Now let's consider the case $y\le\max_{i=1,\dots,n}x_i$. (The case $y\ge\min_{i=1,\dots,n}x_i$ is symmetric and left to the reader as an exercise.) The key to our approach is that \[y\le\max_{i=1,\dots,n}x_i\iff \exists i \ni y\le x_i.\]To handle this case, we need a priori bounds on the $x$ variables, say $L_i\le x_i\le U_i\ \ \forall i$. Let $\bar{U}=\max_{i=1,\dots,n}U_i$, and note that if the constraint $y\le\max_{i=1,\dots,n}x_i$ is to hold, then clearly $y\le\bar{U}$.

We introduce binary variables $\delta_1,\dots,\delta_n$ and the constraint \[\delta_1+\cdots+\delta_n=1.\]Depending on the solver being used, it may be beneficial to specify to the solver that the $\delta$ variables form a type 1 special ordered set (SOS1). Now add the following $n$ constraints:\[y\le x_i + (\bar{U}-L_i)(1-\delta_i)\ \ \forall i=1,\dots,n.\]If $\delta_i=0$, the right hand side becomes $x_i+\bar{U}-L_i\ge\bar{U}$, and the constraint is vacuous. For the one index where $\delta_i=1$, the constraint reduces to $y\le x_i$, which is all we need.

Addendum 1: It belatedly occurred to me that it would be equally valid to replace $\delta_1+\cdots+\delta_n=1$ with $\delta_1+\cdots+\delta_n\ge 1$ (in which case it is no longer an SOS1 constraint). Requiring $y\le \max_{i=1,\dots,n} x_i$ is equivalent to saying $y\le x_1$ OR $y\le x_2$ OR ... OR $y\le x_n$, with the ors being inclusive. I have no idea whether this second version is more or less efficient computationally than using the SOS1 constraint.

Addendum 2: Erwin Kalvelagen posted some alternative, possibly tighter, formulations on his blog.

Resolutions, Seasonality and Transient Effects

2012-01-01T11:00:00.001-05:00

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).

Launching Windows Apps with Wine

2011-12-29T16:01:00.000-05:00

Although I work almost 100% with Linux these days, I have a few Windows applications I find useful (including IrfanView for quick image edits and OCR -- much simpler, albeit less powerful, than GIMP) and PathSync for synchronizing local directories with my thumb drives. I also find PDF-XChange Viewer handy for adding annotations to PDF files. All these programs run fine under Wine, with one small "gotcha". When I install them (by downloading the Windows installer and then running "wine name-of-installer.exe" in a terminal), shortcuts to them are added to the Wine submenu of the GNOME menu ... but the shortcuts are often dysfunctional. They attempt to launch the Windows .lnk file added to the (virtual) Windows start menu, and typically I either get a "file not found" pop-up or the launch simply fails silently.

The solution I have found is to manually edit the shortcuts. Suppose that I am logged in as user "paul" and I've just installed IrfanView. My first step is to track down the Windows path to the executable. Assuming defaults were used (generally a good thing when installing software under Wine), I open a terminal and drill down to /home/paul/.wine/drive-c/Program\ Files, where I find the IrfanView directory and, in that, the i_view32.exe executable.

The next step is to run

env WINEPREFIX="/home/paul/.wine" wine "C:\Program Files\IrfanView\i_view32.exe"

in a terminal and make sure that it launches correctly. Note that the path to the executable is written Windows-style (backslashes, no escaping things) in quotation marks. If the program launches properly, I close it, copy the entire line to the clipboard, find the launcher in the GNOME menu, right-click and choose "Edit properties", and replace the contents of the "Command:" field with the contents of the clipboard. I also confirm that launcher type is "Application" and not "Application in Terminal". With that done, I close the launcher edit panel and test it. Sometimes it seems to take a while before the menu detects and adopts the change I just made. I'm not sure, shy of logging out (overkill?), what the best way to impose the change immediately is. I've tried "killall gnome-panel" (possibly also overkill) with mixed success.

Extracting Variables in CPLEX

2011-12-22T15:55:00.000-05:00

It's never happened to me, but apparently some CPLEX users (working with one of the programming APIs) inherit a fully formed problem, an instance of IloCplex or perhaps IloModel, without having access to the Concert code that constructed it. You only need the problem object to solve it and get the solution status and objective value; but in order to get the values of the variables in an optimal solution, you need to pass either an array of variables (IloNumVar[]) or individual variables in function calls (so that CPLEX can return values matched to the corresponding variables). If all you have is the problem object, how do you know what the variables are?

This has been asked more than once on help forums, so I list below a Java function that I believe will extract all variables from an instance of IloCplex. Something quite similar should work in the C++ API, and hopefully if you use the C API you can make the leap from the Java code. The Python API seems to provide a VariablesInterface class that I think provides a mechanism (if it's even needed in Python -- I don't really know). I'm blissfully ignorant about the Matlab API.

I've tried to stress-test the Java code, but nonetheless you use it at your own peril.

  private IloNumVar[] parse(IloCplex cplex) throws IloException {
    HashSet<IloNumVar> vars = new HashSet<IloNumVar>();
    Iterator it = cplex.iterator();
    IloLinearNumExpr expr;
    IloLinearNumExprIterator it2;
    while (it.hasNext()) {
      IloAddable thing = (IloAddable) it.next();
      if (thing instanceof IloRange) {
        expr = (IloLinearNumExpr) ((IloRange) thing).getExpr();
        it2 = expr.linearIterator();
        while (it2.hasNext()) {
          vars.add(it2.nextNumVar());
        }
      } else if (thing instanceof IloObjective) {
        expr = (IloLinearNumExpr) ((IloObjective) thing).getExpr();
        it2 = expr.linearIterator();
        while (it2.hasNext()) {
          vars.add(it2.nextNumVar());
        }
      } else if (thing instanceof IloSOS1) {
        vars.addAll(Arrays.asList(((IloSOS1) thing).getNumVars()));
      } else if (thing instanceof IloSOS2) {
        vars.addAll(Arrays.asList(((IloSOS2) thing).getNumVars()));
      } else if (thing instanceof IloLPMatrix) {
        vars.addAll(Arrays.asList(((IloLPMatrix) thing).getNumVars()));
      }
    }
    IloNumVar[] varray = vars.toArray(new IloNumVar[1]);
    return varray;
  }

Indexing an Array with a Variable

2011-12-07T20:49:00.001-05:00

Sometimes, in the context of a mathematical program, someone wants to use a variable $x$ to index a vector $y$, as in \[z = y[x].\] As a starting point, we should assume that $x$ is an integer variable whose domain equals, or at least is a subset of, the index set of $y$. If you try to set $z=y[2.71828]$, or $z=y[5]$ when $y$ is indexed by ${1,\dots,4}$, you should expect Bad Things To Happen.

With that stipulation, $z=y[x]$ poses no problem in a constraint program. It cannot, however, be expressed directly in a mathematical program. If the domain of $x$ is not too large, it can be implemented somewhat obliquely in a mathematical program using binary variables.

Let's assume that $y$ is indexed over $1,\dots,N$ (with $N$ known at the outset), and that $y$ is a parameter. (We'll treat the case where $y$ is a variable in a minute.) Create $N$ binary variables $x_1,\dots,x_N$ and add the constraint \[x_1+\dots+x_N=1,\] which makes $\{x_1,\dots,x_N\}$ a type 1 special ordered set (SOS1). Then define $z$ via \[z=\sum_{i=1}^N y[i]*x_i.\]

You can do exactly this when $y$ is a vector of variables, but it adds a nonconvex quadratic constraint to the model, which likely prevents you from finding a guaranteed optimum, and greatly restricts what algorithms/software you can use. If we know a priori lower and upper bounds for $y$, say \[L_i \le y[i] \le U_i \forall i\in {1,\dots,N}\] with $L_i$ and $U_i$ parameters, we can add the $x_i$ as above and use the following set of constraints to define $z$: \[\begin{eqnarray*}y[i] -z \le (U_i - \hat{L})(1-x_i) \forall i\in {1,\dots,N}\\ y[i] - z \ge (L_i - \hat{U})(1-x_i) \forall i\in {1,\dots,N}\end{eqnarray*}\]where $\hat{L}=\min_{i=1,\dots,N} L_i$ and $\hat{U}=\max_{i=1,\dots,N} U_i$.

Charlotte's Literary Park

2011-11-26T17:32:00.001-05:00

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.)

Android-Linux File Transfers

2011-11-25T18:53:00.001-05:00

I recently acquired a Toshiba Thrive tablet (Android Honeycomb, currently version 3.2.1), in part because it comes with two USB ports (one full size, one mini). The USB ports theoretically allow me to move files between my Ubuntu PC and the tablet by mounting the tablet as a disk drive on the PC. I say "theoretically" because Google recently moved to Media Transfer Protocol for handling connections over USB. This seems to be okay for Windows PCs and Macs, but for Ubuntu (and other Linux systems) it requires using the mtpfs package. I've found connections to be excruciating slow, and for some reason (probably a setting I'm missing), when I do get connected, all I see is an empty root and an empty Playlists subdirectory. Trust me, there are tons of files on the Thrive.

Fortunately, I found WebSharingLite File/Media Sync, a free app in the Android Market. (As one might expect from the "Lite" part, there is a paid version, rather economically priced.) I have a WiFi DSL gateway at home (and of course my laptop has WiFi). Running WebSharingLite on the tablet, I can connect via a web browser from my PC or laptop and upload/download files considerably faster than what mtpfs over USB seems to allow. (Again, though, I should stress that there's no guarantee I'm setting up mtpfs correctly, despite hours of poking around the web looking for help.) The connection requires a password; coupled with the fact that it's on a nonroutable segment, behind the firewall in my gateway, I think the security is adequate.

I can definitely recommend WebSharingLite.

Back to Back Conferences

2011-11-25T09:29:00.001-05:00

I'm back from two conferences in consecutive weeks: INFORMS (Charlotte NC) and DSI (Boston). (The link to the DSI meeting is a bit ephemeral -- it will eventually point to the 2012 meeting.) Two conferences in two weeks is a bit hard on both the waistline and the brain. I have a few odds and ends to share.

Repeating something I posted on the INFORMS conference blog, I found out from Peter Horner (editor of Analytics Magazine) that a recent change in the magazine’s URL (from analytics-magazine.com to analytics-magazine.org) may have broken some people’s RSS subscriptions to the web site, as well as screwing up the site's Google ranking. If you subscribe to the magazine's RSS feed, you might want to test the feed and resubscribe if necessary. If you're unfamiliar with the magazine, it is worth taking a look (and, if you choose, using the RSS button at the lower left to subscribe). For readers of this blog who are active on social networks, please help spread the word.

Changing gears, in a previous post I wrote about PowerPoint users suffering from invisible math formulas when they ran their presentations on someone else's laptop at a conference. Out of curiosity, I made a list at the INFORMS meeting of how many presenters I saw using different types of software. My classification system was a bit fuzzy. Beamer presentations tend to be distinctive, but PowerPoint presentations are not as obviously PowerPoint unless you see the presenter launching them from the PowerPoint program. Similarly, the only ways I have to determine that a presentation was done in Keynote (Apple's presentation software) are if it contains tons of eye candy, or it is being played from an MOV file, or if I see the presenter using a Mac. Besides Beamer, there are several other ways to produce presentations in LaTeX (including FoilTeX and Powerdot), and I don't know how to tell the end products of those apart. So my classification systems was Beamer, PowerPoint, Keynote or "Other" (where "Other" could include any misclassified presentations).

As it turns out, I did not see any presentations that I could detect were done in Keynote. (I think Tim Hopper might have used it for his portion of our panel session on social media, but I had my back to the screen when he was presenting.) My final count was 24 Beamer files, 9 PowerPoint files and 8 "Other" files.

I came away with two conclusions. The first is that PowerPoint may be losing market share among the INFORMS crowd, since a few years ago my informal survey had an even split between Beamer and PowerPoint. Then again, this may reflect a decrease in the number of US presenters at INFORMS, since LaTeX (and Beamer) seem to be more popular among European and possibly Asian users than among Americans. PowerPoint was pretty ubiquitous at the DSI meeting (which is populated mainly with business school faculty and doctoral students). The second conclusion is that either PowerPoint has gotten better or people have gotten better at using it: there were no missing formulas in any of the papers I saw presented.

Blogging at INFORMS 2011

2011-11-11T17:00:00.001-05:00

I volunteered to be a guest blogger at the 2011 INFORMS national meeting in Charlotte, NC. I haven't even hopped a plane yet, and I've already spammed the blog (er, posted) once. You can find the post, if you're curious, at http://meetings2.informs.org/charlotte2011/blog/?p=145. There is quite a cast of bloggers for the meeting, so if you are attending (or just interested), I recommend subscribing to the RSS feed.

Mint/Ubuntu Update Broke Printing

2011-11-07T14:55:00.000-05:00

Today I was suddenly unable to use my home HP ink jet printer with Linux Mint, despite the fact that this morning it was printing fine from Windows (my system is dual-boot). The error message informed me that /usr/lib/cups/backend/hp had failed for unspecified reasons. Toggling the printer off and back on did not help, nor did rebooting the system, nor did switching the driver.

A quick web search, however, revealed the fact that some unspecified update had screwed up permissions on the /usr/lib/cups/backend directory (restricting it to root only). Most of the executables in that directory looked okay, but the permissions for cups-pdf were also root only, so I'm guessing that it was an update to cups-pdf that blew things up.

The solution: sudo chmod -R 755 /usr/lib/cups/backend.

I thought Microsoft had a patent on destructive updates. Guess not.

Scalable Images in Blogger

2011-10-29T17:50:00.001-04:00

Questions about a recent post containing a couple of flow charts made me regret the fact that Blogger does not support SVG graphics. Although I made the charts using the excellent TiKZ LaTeX package (which produces vector output in the form of a PDF file), I had to convert the PDF output to PNG for Blogger, and the images are a tad fuzzy (and do not scale well when zoomed), which may have led to some confusion. So I was on a mission today to find a workaround.

The first thing I discovered that SVG is not nirvana. I generated the images as separate PDF files from the TiKZ source. (Hint to people doing this: use the LaTeX standalone document class and the output file will automatically be cropped to the smallest rectangle containing the image.) I then used ImageMagick to convert the PDF files to SVG files ... which blew them up from around 54 KB to about 8+ MB. Each. Oops! I tried a tool I found to convert the SVG files to "canvas" files, which got me another 5x or so increase in size. So back to PDF files. Blogger does not consider PDFs to be images, to the plan now is to use a PNG file as the image and link it to the corresponding PDF, allowing readers to click on the image and at least get a scalable version in a new window or tab.

Blogger does not allow you to upload arbitrary files, only images in formats it recognizes (which are actually stored in Picassa, another Google product/service). I thought about putting the PDFs on a personal server somewhere, but I worry about moving things (including them) to a new server at some future date and not remembering to update the links. Enter Google Documents. I just have to upload the PDFs to Google Docs, make them public, grab the URLs and set the links on the PNGs (which by default point to the PNG files in Picassa) to point to the PDFs in Google Docs instead.

I did this with the aforementioned post, and I think it's working. The one question mark for me is whether everyone can see them. I can, but Google knows I'm the owner. If either of my loyal readers runs into problems, or wants me to convert images from earlier posts, please drop a comment here.

Time Series, Causality and Renting a Congressman

2011-10-21T17:03:00.001-04:00

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.

Benders Decomposition Then and Now

2011-10-09T12:09:00.001-04:00

A couple of years ago, a coauthor and I had a paper under review at a prestigious journal that shall remain nameless. In the paper we solved a mixed integer linear program (MILP) using Benders decomposition, with CPLEX link as the solver, and we employed callbacks to check each potential solution to the master problem as it occurred. One of the reviewers asked me to justify the use of callbacks. My first inclination was a variation on “because it's standard practice”, but since I have not actually surveyed practitioners to confirm that it is standard (and because, as an academic, I'm naturally loquacious), I gave a longer explanation. What brought this to mind is a recent email exchange in which someone else asked me why I used callbacks with Benders decomposition. It occurred to me that, assuming I'm correct about it being the current norm, this may be a case of textbooks not having caught up to practice. So here is a quick (?) explanation.

If I recall correctly, the original paper by Jack Benders [1] dealt with continuous nonlinear optimization, not discrete linear optimization, and I do not know who first made the connection to MILP models. The application I have in mind here deals with problems that, without loss of generality, can be modeled as follows:
\[\begin{array}{lrclcc}\textrm{minimize} & c_{1}'x & + & c_{2}'y\\\textrm{subject to} & Ax & & & \ge & a\\ & & & By & \ge & b\\ & Dx & + & Ey & \ge & d\\ & x & \in & \mathbb{Z}^{m}\\ & y & \in & \mathbb{R}^{n}\end{array}\]
Benders decomposition splits this into a master problem and a subproblem. The subproblem must be a linear program (LP), so all the discrete variables have to go into the master problem (a MILP). You can optionally keep some of the continuous variables in the master, but I will not do so here. You can also optionally create multiple subproblems (with disjoint subsets of $y$), but again I will not do so here. Finally, in the spirit of keeping things simple (and because unbounded models are usually a sign of a lazy modeler), I'll assume that the original problem is bounded (if feasible), which implies that both the master and subproblem will be bounded (if feasible).

The master problem is as follows:
\[\begin{array}{lrclccc}\textrm{minimize} & c_{1}'x & + & z\\\textrm{subject to} & Ax & & & \ge & a\\ & g'x & + & z & \ge & f & \forall (g,f)\in\mathcal{O}\\ & g'x & & & \ge & f & \forall (g,f)\in\mathcal{F}\\ & x & \in & \mathbb{Z}^{m}\\ & z & \in & \mathbb{R}\end{array}.\]Variable $z$ acts as a surrogate for the objective contribution $c_{2}'y$ of the continuous variables. Set $\mathcal{O}$ contains what are sometimes known as “optimality cuts”: cuts that correct underestimation of $c_{2}'y$ by $z$. $\mathcal{F}$ contains what are sometimes known as “feasibility cuts”: cuts that eliminate solutions $x$ for which the subproblem is infeasible. Initially $\mathcal{O}=\emptyset=\mathcal{F}$. The subproblem, for a given $x$ feasible in the master problem, is:\[\begin{array}{lrcl}\textrm{minimize} & c_{2}'y\\\textrm{subject to} & By & \ge & b\\ & Ey & \ge & d-Dx\\ & y & \in & \mathbb{R}^{n}\end{array}\]Optimality cuts are generated using the dual solution to a feasible subproblem; feasibility cuts are generated using an extreme ray of the dual of an infeasible subproblem. The precise details are unnecessary for this post.

Back in the '60s ('70s, '80s), solvers were essentially closed boxes: you inserted a problem, set some parameters, started them and went off to read the collected works of Jane Austen. Intervening in the algorithms was not an option. Thus the original flowchart for Benders decomposition looked like the following.

The modern approach, using callbacks, looks like this:

Obviously the modern approach can only be implemented if you are using a solver that supports callbacks, and requires more advanced programming than the classical approach. Other than that, what are the advantages and disadvantages?

The main advantage of the callback approach is that it is likely to avoid considerable rework. In the original approach, each time you add a cut to the master problem, you have to solve it anew. Although the new cuts may change the structure of the solution tree (by changing the solver's branching decisions), you are probably going to spend time revisiting candidate solutions that you had already eliminated earlier. Moreover, you may actually encounter the optimal solution to the original problem and then discard it, because a superoptimal solution that is either infeasible in the original problem or has an artificially superior value of $z$ causes the true optimum to appear suboptimal. With the callback approach, you use a single search tree, never revisit a node, and never overlook a truly superior solution.

The potential disadvantage of the callback approach is that you potentially generate a cut each time a new incumbent is found, and some of those cuts quite possibly would have been avoided if you followed the classical approach (and added a cut only when an “optimal” solution was found). Modern solvers are good at carrying “lazy” constraints in a pool, rather than adding the cuts to the active constraint set, but there is still a chance that the modern approach will take longer than the classical approach. I believe (but have no data to support my belief) that the modern approach will typically prove the faster of the two.

[1] Benders, J. F., Partitioning Procedures for Solving Mixed-Variables Programming Problems, Numerische Mathematik 4 (1962), 238--252.

OR, the Environment, and the Law of Unintended Consequences

2011-09-30T17:09:00.001-04:00

The topic of the INFORMS blog challenge for September is "OR and the Environment", and I'm slipping this in just under the wire. My guess is that most if not all of the other challenge entries will extol some way in which the use of OR helps the environment. I shall be (slightly) contrarian here.

*****

Problem: Reduce the cost of shipping raw materials and manufactured goods by sea.

Solution: Companies use OR techniques to pack vessels more efficiently (reducing the number of loads), route vessels more efficiently (reducing transit times and, hopefully, total travel distances), etc.

Short-term Environmental Impact: Fewer ships covering less distance means less consumption of fossil fuels, so less air (and water) pollution.

Long-term Environmental Impact: Lower shipping costs make it more cost effective for manufacturers in Europe and the US to purchase materials and components from distant countries such as India and China, shifting the manufacturing operations from regions with relatively stringent environmental reg (medium environmental regulation) ulations to regions with more lax regulations. The increased volume being shipped by ocean more than offsets the reduction in distance per shipment and results in an increase in ocean traffic.

*****

Problem: Make alternative fuel sources for automobiles more cost-effective.

Solution: Employ OR techniques to improve the manufacture and distribution of gasohol (gasoline/alcohol mixtures), reducing the pump price and therefore expanding the consumption of gasohol.

Short-term Environmental Impact: Some of the demand for a non-renewable source (fossil fuels) with a relatively high pollutant output is shifted to a renewable source (crops such as corn) with a lower pollutant content.

Long-term Environmental Impact: Crops previously grown as animal feed or for human consumption are diverted to the more profitable biofuel production, causing shortages or price increases in food. In some countries, this causes farmers to clear forest areas for replanting with food crops. Forests capture carbon more efficiently than food crops do, and clearing a forest by burning it releases significant amounts of carbon. (There are also arguments in both directions as to whether biofuels actually produce a net gain in energy or reduce net pollution when the activities involved in growing the crops are factored in.)

*****

Does this mean that I think OR is bad for the environment? Not at all; but it's not automatically good for the environment either. What OR brings to the table that might be most important, in the context of environmental impact, is a systems perspective. Hopefully OR practitioners can help decision-makers view problems in sufficient breadth, and yet with sufficient (model-aided?) clarity, to recognize the secondary and tertiary effects of their choices. That still leaves the issue of getting environmental impact on the table as a criterion for evaluating choices -- which is a political, not mathematical problem.

Fixing TiKZ/PGF to Work with Gnuplot

2011-09-25T18:01:00.001-04:00

While working on a new presentation today (in Beamer), I grabbed a slide from a previous presentation (one I reuse annually). The slide contains PGF code that uses Gnuplot to plot functions (which I then annotate using PGF commands). Small problem: the transplanted slide didn't work (no curves on the plot) ... which led me to attempt to recompile the original presentation and discover that it, too, no longer worked. Grrr!

Poking in the files in the /tmp directory showed me that Gnuplot was crabbing about a command (set terminal table) that PGF uses to tell it to create a text file with the points to be plotted. A bit of searching led me to a blog post by
Toine Bogers containing the fix. Instructions for Linux follow (I haven't tried it on Windows yet):

Open a terminal and run 'kpsewhich pgfmoduleplot.code.tex' to locate the file you need to edit. (The location varies with the LaTeX distribution you use; this takes the work out of finding it.)
Issue 'sudo gedit <path>/pgfmoduleplot.code.tex' (where <path> is the path you found in the previous step) and give your password when prompted. (Feel free to use a different editor if gedit is not your cup of tea.)
Find the line containing 'set terminal table' and delete the word 'terminal', so that it becomes 'set table' (the rest of the line staying unchanged).
Save the modified file, and you should be good to go

In LyX, you also have to go to Tools > Preferences... > File Handling > Converters, locate the converter for LaTeX (pdflatex) -> PDF (pdflatex), and tweak the Converter: entry to read 'pdflatex -shell-escape $$i'. Then click Modify and Save. If you use other formats besides PDF (pdflatex) to view/export Beamer presentations, you may have to add the -shell-escape flag (or something similar) to them as well. The flag allows pdflatex to run an external program (in this case gnuplot) in a shell. Users of other other LaTeX editing software will likely need a similar tweak.

I love open source software, but one of the challenges of using lots of separate pieces of software is that developers will change something in the latest version of one program or library, and that change will break some interaction with another program/library from an entirely separate developer. To modify a saying from my misspent youth: "You pays your money [or, in this case, you don't] and you takes your chances."

Fixing CUPS-PDF

2011-09-24T15:40:00.000-04:00

Not that I needed to find another bug in Mint 11 Katya/Ubuntu 11 Natty, but I just discovered that the "Print to PDF" printer (cups-pdf) was writing a 2.1 KB PDF file containing a single blank page, regardless of what I printed. A quick web search turned up multiple reports of this. I used Synaptic to reinstall the cups-pdf package, to no avail. The solution (which I found on a bug report web page) was to go into Control Center > Printing, delete the "Print to PDF" printer entirely, then use Server > New Printer to reinstall it. It seems to be working now. I wonder what the interarrival time for the next gremlin is. :-(

Comment Spam

2011-09-15T09:33:00.000-04:00

In the interest of free and open discussion (and because I've been known to make mistakes, which I hope someone will correct), I leave this blog open to comments from anyone, with no registration requirement. To date I've gotten very little comment spam. (If you're not sure what "comment spam" is, it's some self-promoting poster child for rectal problems leaving a comment that has nothing to do with the actual blog entry and everything to do with drawing attention to a website they own.) On the rare occasions when I do get comment spam, Blogger is fairly good about moving it to the spam file on its own.

That raises a point I should make for actual readers (and you both know who you are): if you write a comment and shortly thereafter it seems to have disappeared, don't worry. Blogger has moved it to the spam file for some reason, but I still get an email ping that the comment was posted. I always check comments to be sure they ended up in the right place, and if your comment was mistakenly classified as spam (this has happened at least once and at most twice in the history of the blog), I will restore it to its rightful place in the sunshine.

In the past couple of days, I've gotten the same comment spam message twice. Curiously, Blogger correctly identified it as spam the first time but not the second time. It's a link to "Team PotentiaMED" web site. The information blurb on their site is long on meaningless buzz phrases and a bit short on specifics, but I think they are some sort of consulting operation. I'll let you judge their merits for yourself, if you're curious. Personally, I automatically assume that any business relying on spam to get customers probably lacks solid reasons to patronize them (the sort of reasons that would make for an effective conventional marketing campaign). I also don't trust anyone who spams.

By way of contrast, the proprietors of Online Engineering Degree contacted me by email to ask permission to post a comment pointing to one of their pages, a list of Q&A sites. Instead, I devoted a short post to providing the link, since (a) I thought it might be relevant to readers with an interest in industrial engineering and (b) it was not really relevant as a comment to any particular existing post. A writer from Masters in Engineering wrote to me asking if I would like to mention a page listing forums and boards for engineers. The sites listed were potentially useful to engineers in general but did not seem very useful to IEs, so I declined. I want to give both of them credit for doing things the right way.

Now if I can just find a way to report comment spammers to Blogger ...

Piecewise-linear Functions Redux

2011-08-21T15:57:00.000-04:00

A recent question on OR-Exchange about step functions in mathematical programs made me decide to update an earlier post about piecewise-linear functions.

In the prior post I dealt with continuous piecewise-linear functions (of a single variable) in mathematical programs. As a quick recap, if the function represents a diseconomy of scale (convex in the objective of a minimization problem or concave in the objective of a maximization problem), as in the first plot below, it can be modeled strictly with linear inequality constraints (no binary variables needed). Note that convexity implies continuity everywhere except possibly the endpoints (where you can have a jump discontinuity and still be convex or concave). The method I previously described requires continuity at the endpoints as well.

If the function is continuous but lacks the appropriate convexity/concavity, as in the next plot (which is neither convex nor concave), the all-inequality trick fails. It may also fail for convex or concave functions that appear in constraints, either because the convexity of the function does not match the direction of the inequality (you have $f(x)\ge b$ where $f()$ is convex or $f(x)\le b$ where $f()$ is concave), or because $f()$ is tied to other variables in the constraints in such a way that there is a diseconomy of scale to the direct contribution of $f()$ to the objective value but an economy of scale overall (overestimating the value of convex $f()$ or underestimating the value of concave $f()$ allows the other variables to take values that should be infeasible given the value of $x$). If $f()$ appears in any constraints and you are not absolutely certain that it matches the directions of the constraints in which it appears and represents an overall diseconomy of scale, treat it as an arbitrary continuous piecewise-linear function, as discussed next.

Again recapping the previous post, for an arbitrary continuous piecewise linear function $f(x)$ with break points $a_{1}\lt a_{2}\lt\cdots\lt a_{n+1}$ and values $f_{i}=f(a_{i})$ at the break points, we introduce continuous variables $\lambda_{1},\dots,\lambda_{n+1}$, add the constraint $\lambda_{1}+\cdots+\lambda_{n+1}=1$, and tell the solver that the $\lambda$ variables form an SOS2 set. We then add the constraint $x=a_{1}\lambda_{1}+\cdots+a_{n+1}\lambda_{n+1}$ and replace $y=f(x)$ with $y=f_{1}\lambda_{1}+\cdots+f_{n+1}\lambda_{n+1}$. If the solver does not understand SOS2 sets, it is necessary to introduce binary variables (as described in the previous post).

Step functions, such as the one plotted below, are not continuous, so nothing from the earlier post applies to them. Suppose we have break points $a_{i}$ as above, with $f(x)=f_{i}$ when $a_{i}\le x\lt a_{i+1}$. The first problem we confront is that mathematical programs abhor strict inequalities. To a mathematical programming solver, there is no difference between $x\lt a_{i+1}$ and $x\le a_{i+1}$ unless $x$ is a discrete variable (i.e., there is a largest possible value for $x$ strictly less than $a_{i+1}$. That will not be the case here, so we will simply have to deal with the fact that if the solver decides it wants $x=a_{i+1}$, it will set $f(x)$ arbitrarily to whichever of $f_{i}$ and $f_{i+1}$ makes for the better objectiveresult.

To model a step function, we use an SOS1 rather than SOS2 set. Add binary variables $u_{1},\dots,u_{n}$ constrained by $u_{1}+\cdots+u_{n}=1$, declare them to be an SOS1 set, and include the constraints \begin{eqnarray*} \sum_{i=1}^{n}a_{i}u_{i} &\le & x &\le &\sum_{i=1}^{n}a_{i+1}u_{i}\\ y & &= && \sum_{i=1}^{n}f_{i}u_{i}. \end{eqnarray*} (Explicit declaration of the SOS1 set may not be necessary; some solvers recognize SOS1 sets automatically, and some may not exploit the useful properties of an SOS1 set even if the set is identified for them by the modeler.)

One last point: both the SOS1 and SOS2 methods require that $x$ have a finite upper bound ($a_{n+1}$). That upper bound will show up as a coefficient in the constraint matrix. The larger it is, the more likely the model is to be numerically unstable. So avoid the temptation to set $a_{n+1}$ equal to the largest floating point value your compiler can handle. Infinity is not your friend here.

Hmm. This is all a bit dry. Maybe a soundtrack would help?

The Heisenberg Budget Principle

2011-08-20T14:36:00.000-04:00

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).

Spontaneous Reboots

2011-08-16T15:02:00.002-04:00

Mint Katya (a derivative of Ubuntu Natty Narwhal) on my AMD-64 system has suddenly developed a penchant for spontaneously rebooting. So far, it has only happened while I'm typing. I think it has happened twice when I was typing messages in Thunderbird and once or perhaps twice when I was typing in the Yoono plug-in for Firefox. I don't recall any recent updates to T-bird, Firefox or Yoono, nor have I changed my keyboard (in case this is related to n-key rollover -- my fingers sometimes get ahead of my brain when I'm typing). The mosquitoes have gotten quite aggressive (and numerous) around my house; maybe they drove some gremlins indoors?

Update #1: I was sloppy above. It's not Mint that is rebooting; it's the X server. This is apparently a common problem,although the variety of symptoms posted there suggest that this is in fact multiple distinct bugs with a common end result (X crashing). Things I have discovered:

Unlike several of those reports, I have not experienced any crashes as a result of clicking. Only typing triggers a crash.
Unlike the reports from laptop users, power management is not the culprit (the machine that crashes for me is a desktop).
Someone pointed the finger at running the AMD-64 version of Natty on an Intel CPU. My copy of Mint is in fact based on the AMD-64 Natty, but my box has an AMD-64 CPU.
Turning the proprietary NVIDIA driver off and then on did not help. (I have a GPU from NVIDIA.)
Installing xserver-xorg-video-nv did not help.

Update #2: I used the wizardous sgfxi script to update my NVIDIA drivers a few days ago. Since then I have had no spontaneous X crashes. I hesitated to claim victory lest it be premature, but today I wrote a moderately lengthy blog post (touch-typing at my usual subsonic speed) with nary a glitch. So hopefully the driver reload cured this problem. Thanks to Harald Hope for a handy script!

Q&A Sites for Engineers

2011-08-12T09:16:00.000-04:00

One of the authors at Online Engineering Degree asked me to mention an article there: 25 Q&A Sites for Engineers. It's a compendium of links to exactly what the title describes. I'm not sure anyone reading this blog will be interested (industrial engineering does not seem to get much play among the sites listed), but I'm happy to pass the link along.

Tab Completion Bug in Mint 11

2011-08-06T11:23:00.001-04:00

This is really a tab completion bug in Ubuntu 11.04 - and may actually be a pair of bugs (I'm not sure), one not the fault of Ubuntu. Details can be found in this bug report. The short form is that command line tab completion (where you start typing a path and hit TAB to complete it) started breaking down on one of my Mint machines. Hitting TAB would add an unwanted space at the end of the path (forcing me to backspace if I were not yet done) and also failed to escape spaces. In fact, if I typed the portion of the path containing the space and escaped it, then hit TAB, the escape character (backslash) would be removed.

The bug report contains two possible fixes. As it happens, I had started out with Acrobat Reader 9 installed from the repository on this machine, then replaced it with the version downloaded from Adobe's web site. This is my 64 bit box, and there's an issue with Acrobat Reader looking for 32 bit versions of libraries (which I have installed), finding the 64 bit versions instead, and tripping over them. I thought maybe using the Adobe version would fix the problem. (It did not.)

At any rate, I tried one of the two suggestions in the bug report: deleting /etc/bash_
completion.d/acroread.sh (which is a symlink to a script that comes with the Adobe version of Reader). That seems to have fixed the tab completion bug (knock on virtual wood). It does not seem to have done any harm to Reader, either.

A GNOME Panel Hack

2011-08-04T15:33:00.000-04:00

Linux Mint 11 (Katya), built on Ubuntu 11.04 (Natty Narwhal), continues to act goofy at times, notably with intermittent boot failures on both my home PC (AMD 64 bit quad-core) and my laptop (Intel 32 bit dual-core). On the desktop, when a boot fails I get a set of messages that stop abruptly; the failure point is a bit random (sometimes it stops after the battery check, sometimes it goes deeper). On the laptop, the screen stays blank; two of the LED indicators (either numeric lock and caps lock or caps lock and scroll lock; I forget which pair) blink in unison. On both machines, rebooting eventually succeeds.

Another intermittent problem has to do with the GNOME panel. Again on both machines, I sometimes get a message that one of the panel components failed to load (sometimes the indicator applet, sometimes the clock applet, this morning the Mint Menu button). I'm asked if I want to delete it, to which I always reply in the negative.

Killing the GNOME panel will cause it to spontaneously regenerate, and usually it regenerates correctly. (Occasionally it needs to be killed a second, or even third, time.) So I cobbled together a menu entry to do this. I put a file named Fix\ Panel.desktop into ~/.local/share/applications. The contents of the file are listed below. Now all I have to do is click the Menu button, find "Fix Panel" and click it to (hopefully) repair the panel.

#!/usr/bin/env xdg-open

[Desktop Entry]
Version=1.0
Type=Application
Terminal=false
Icon[en_US]=gnome-panel-launcher
Name[en_US]=Fix Panel
Exec=killall gnome-panel
Comment[en_US]=Restarts GNOME panel if it's glitched
Name=Fix Panel
Comment=Restarts GNOME panel if it's glitched
Icon=gnome-panel-launcher

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

2011-07-31T17:46:00.001-04:00

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.

Princeton Consultants Is Hiring

2011-07-26T15:55:00.001-04:00

This is a first for me. I received an email this morning for someone at Princeton Consultants, asking if it would appropriate to list some job openings on the blog. Given the current unemployment rate in the U.S., who am I to say no -- especially since their name is "Princeton Consultants" and that they are headquartered in Princeton, NJ (although as far as I know are unaffiliated with Princeton University).

Quoting the message I got:

Our firm, Princeton Consultants, does IT and Management Consulting (optimization, systems integration, business process improvement, etc.) for a variety of Fortune 500 companies. We are currently looking for 10-15 new employees to start immediately as an Associate, Senior Associate or Analyst.

These are apparently all full-time positions. Interested readers can learn more about the company from their careers page, and can find a brief application form on their site. If you know any OR types in the job market, please pass the word to them.

USENET: A Remembrance

2011-07-25T18:57:00.001-04:00

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.

Social Networks at Work

2011-07-24T14:31:00.001-04:00

The theme for the INFORMS Blog Challenge for July is "O.R. and Social Networking". I suspect that most posts will deal either with how O.R. tools can be applied to social networks (algorithms that recommend new "friends", managing network traffic, ...) or how social networks can benefit O.R. people. I hope to take a slightly different tack here. Operations research, management science and analytics propose to help people make better decisions and help systems operate more smoothly, and I think we have something to offer in better understanding and managing the role of social networks in the workplace.

Let me start by disclaiming any originality of the following ideas. Researchers in organizational behavior have already taken note of social networks in and between organizations. The central notion is that individual workers and groups of workers gain productivity by leveraging contacts in other units of the same organization or in other, separate organizations. Often those are direct contacts, but sometimes not. (To be concrete, if we picture a social network as a graph with actors or groups of actors as nodes and relationships as edges, direct contacts are nodes adjacent to a given node. Indirect contacts are nodes connected to a given node by a path of length greater than one.) There are various reasons why an organization might be concerned about social networks within it and between it and other organizations:

If workers become more productive by exploiting links, the organization might benefit from fostering the development of such links.
A social network within an organization may improve intra-organizational communication.
Conversely, a social network within an organization might contribute to the development of cliques and cause a rise in "political" behaviors.
Contacts with members of allied organizations might improve the relationship between the organizations (for instance, helping coordinate a supply chain).
Contacts with members of competing organizations might foster cooperation on some issues, but also might lead to leakage of proprietary information.
Individuals with many valuable connections (nodes with high degree, either weighted or unweighted) may be of particular value to the organization, warranting extra effort to retain and reward them.
Unmanaged development of social networks, both within the organization and leading to the outside, might result in the workforce being divided into "ins" (highly connected individuals) and "outs" (nodes with low degree). To the extent that the social network improves performance, the "outs" may be at a disadvantage in career development. This can undermine mentoring and retention efforts, and may be a particular concern for minorities and non-domestic workers.

To manage social networks, organizations need to be able to quantify them. This means:

defining what constitutes a network;
mapping the network;
finding a way to quantify things such as influence level and value to productivity (which may not be symmetric, meaning the network is directional);
identifying options for creating or manipulating networks (decision variables);
estimating the cost and potential impact of each option;
assessing risks of various options (including allowing networks to grow unmanaged); and
finding an optimal program of network construction/management.

(Being an optimization guy, I had to squeeze that last item in.) The measurement aspects, including mining existing data (emails, phone records, reports) to help identify existing networks, sound like analytics; the mapping, analysis of costs and impacts, and prescriptive recommendations sound like operations research. So I think we have something to contribute here.

And the great thing about being a blog author is that I'm not required to come up with any solutions (or even brilliant insights). :-)

Farkas Certificates in CPLEX

2011-07-23T16:45:00.001-04:00

This is a post about linear programs, specifically infeasible linear programs, and how to deal with them in CPLEX. In response to a question on a CPLEX forum, I played around a bit with Farkas certificates as implemented in CPLEX 12.2. I've never really worked with them, as I have a tendency to produce feasible models. The posted question, though, aroused my curiosity. It asked how to extend a Farkas certificate to a ray for the (unbounded) dual when the primal problem contains bounds on variables.

A Farkas certificate is a vector of constraint multipliers that proves a primal linear program to be infeasible. The name comes from Farkas's Lemma. Assume, without loss of generality, that we have a linear program of the form\[
\textrm{(P) }\begin{array}{lrcl}
\textrm{minimize} & 0\\
\textrm{subject to} & Ax & \ge & b\\
& x & \ge & l\\
& x & \le & u
\end{array}.
\]We are interested here only in the feasibility of (P), so we may as well assume the objective function (irrelevant to feasibility) is zero. Vectors $l$ and $u$ are lower and upper bounds for the variables $x$. To simplify the discussion, we will assume that $l$ and $u$ are finite (but not necessarily nonnegative). What will transpire extends easily to infinite bounds.

Assume that the lower and upper bounds are entered as bounds, rather than as constraints (so that the solver sees $Ax\ge b$ as the only set of constraints). A Farkas certificate for (P) will be a vector $y\ge0$ with the following property. Set $q'=y'A$ and define a vector $z$ of the same dimension as $x$ as follows:\[
z_{j}=\begin{cases}
l_{j} & \textrm{if }q_{j}<0\\
u_{j} & \textrm{if }q_{j}\ge0
\end{cases}.
\](Actually,the definition of $z_{j}$ is arbitrary and irrelevant if $q_{j}=0$; I chose $u_{j}$ just for concreteness.) The key property of the Farkas certificate is that it will satisfy\[
q'z=y'Az < y'b.
\]Now suppose that $x$ is any feasible solution, so that in particular $l\le x\le u$. Then \[
q_{j}\ge0\implies z_{j}=u_{j}\ge x_{j}\implies q_{j}z_{j}\ge q_{j}x_{j}
\]and
\[
q_{j}<0\implies z_{j}=l_{j}\le x_{j}\implies q_{j}z_{j}\ge q_{j}x_{j}.
\]So $q'x\le q'z<y'b$. If $x$ is feasible in (P), though, we have $Ax\ge b$; given that $y\ge0$, it must follow that $q'x=y'Ax\ge y'b$, a contradiction. Thus the existence of a Farkas certificate for (P) tells us that there cannot be any feasible solutions $x$ to (P).

Now let's tie this to the dual (D) of (P), which is\[
\textrm{(D) }\begin{array}{lrcl}
\textrm{maximize} & y'b+v'l-w'u\\
\textrm{subject to} & y'A+v'-w' & = & 0\\
& y,v,w & \ge & 0
\end{array}
\]if we now include the bounds on $x$ as constraints (and treat $x$ as unrestricted in sign). The feasible region of (D) is a cone with vertex at the origin. Denoting by $h^{+}$ and $h^{-}$ the positive and negative parts respectively of a vector $h$ (i.e., $h_{j}^{+}=\max(h_{j,}0)$ and $h_{j}^{-}=-\min(h_{j},0)$), let $y$ be a Farkas certificate for (P), let $q'=y'A$ as before, and let $v=q^{-}$ and $w=q^{+}$. Then $(y',v',w')\ge0$ and $(y'A+v'-w')'=q+v-w=q+q^{-}-q^{+}=0$;
so $(y',v',w')$ is a feasible solution to (D). Moreover, based on our definition of $z$ above, $q'z=-(q^{-})'l+(q^{+})'u=-v'l+w'u$, and so $y'b+v'l-w'u=y'b-q'z>0$. By extending the Farkas certificate $y$ with $v=q^{-}$ and $w=q^{+}$, we obtain a feasible solution to the dual with a positive dual objective value. Since the dual is a cone, $(y',v',w')$ is a recession direction along which the dual objective is unbounded.

Let's go in the other direction. Suppose that (D) is unbounded (making (P) infeasible), and let $(y',v',w')$ be a feasible dual solution with objective value $y'b+v'l-w'u>0$. Let $q'=y'A=w'-v'$ and define $z$ as before. Then $l\le z\le u$, so\[
q'z=w'z-v'z\le w'u-v'l<y'b
\](the last step since the dual objective is positive at $(y',v',w')$); thus $y$ must be a Farkas certificate for (P).

To answer the original question (finally!), suppose we are solving an infeasible primal problem in CPLEX. CPLEX provides a mechanism (the IloCplex.dualFarkas method in the Java API) to retrieve a Farkas certificate $y$. To extend that to the corresponding dual multipliers $v$, $w$ for the lower and upper bounds respectively, compute $y'A$ and assign the positive parts to $w$ and the negative parts to $v$. It would be nice if there were a more direct method (one that would avoid the multiplication $y'A$), but I do not know of one.

One last note: the point of extending the Farkas certificate to a full dual solution is usually to obtain an extreme ray of the dual. As shown above, any solution to (D) with positive objective value provides a Farkas certificate, not just extreme rays. So we rely on the mechanism by which the solver generates the certificate to pick one corresponding to an extreme ray.

The Continuing Adventure of Mint 11

2011-07-18T11:49:00.003-04:00

I should have left "well enough" alone. Mint 11 Katya (AMD 64 bit version) was running well on my Acer Inspire home PC, other than one little annoyance: when I booted, before and after the grub menu, my monitor would nag about a suboptimal resolution (and tell me that 1440x900 at 60Hz was optimal). So I decided to change the screen resolution used by the boot loader (Control > Startup-Manager). Now I can't swear that was the cause (cf. "post hoc ergo propter hoc fallacy"), but ever since then normal boots freeze, sometimes after the battery state is reported as OK and sometimes before. I'm still able to get Linux up and running, but by one of a couple of circuitous routes:

booting into recovery mode, starting in the failsafe X mode, then rebooting normally seems to work;
booting into recovery mode, then using the option to reboot with a file system check routinely works, even though the file system check appears to find no problems.

I also tried the dpkg repair option after booting into recovery mode. It found no packages but did give me the option to upgrade the system core (which I did -- another slow process). That proved to be no help either.

Channeling my inner Sherlock Holmes, I review the facts: a change to display parameters immediately preceded the problems; booting in failsafe X mode appears to help bypass the problem. So perhaps something in the display subsystem is the culprit (although that does not explain why a mandated disk check gets the machine to boot properly).

A search of the Internet shows that I'm not alone in experience the boot problem, although it is unclear that what's going splat on my system is the same as what's going splat on other systems. The author of this post, for instance, appears to have encountered multiple maladies, sufficient that he abandoned the attempt to use Mint. Someone experiencing the same symptoms with an earlier release had some success hiding the xorg.conf file. I tried moving it (and eventually deleted it), but to no avail. Another user found success by deleting and reinstalling the NVidia driver. I tried that (strangely slow to uninstall, very slow to download and reinstall!), but no joy for me. At least I think not. My first reboot after reinstalling the NVidia driver failed to make it even as far as the battery check. So I rebooted, again in normal mode, and the system started properly. Previously, rebooting repeatedly in normal mode failed (every boot attempt got stuck in the same place). Is this progress? Will the beast boot normally from now on? Only time will tell. Meanwhile, I have to go back to doing actual work. If anything changes or I find new information, I'll update this post.

Update #1: The day after I reloaded the NVidia driver, the machine booted normally. So I was cautiously optimistic that maybe the reload had fixed the problem, and the hang immediately after the reload (previous paragraph) was just a last gasp of the bug. No such luck. The first boot this morning hung somewhere around the line saying that flushing the log to disk had stopped. I did a plain reboot, and the second attempt made it to the battery status ok line. I did a third plain boot, and lo and behold it booted properly. So the bug is still there, but either unsuccessful boots make some sort of progress now (write something to disk?) or else it's just stochastic (race condition?).

Update #2: Thinking that perhaps I'd messed up something in grub, I reinstalled grub and reverted something (a config file? a script?) to the package maintainer's version when asked. The next couple of boots went fine, but the bug then reappeared. So no joy there. However, after a few days of win some/lose some boots, my AMD box has gone on a tear of 30 straight successful boots. I can't think of anything I did that could account for this, and none of the updates pushed down to the machine appear to be related to booting. So maybe Loki just remembered he had business elsewhere. My laptop, however, continues to occasionally conk out during a boot, which is probably an entirely different bug.

Facts, Beliefs ... and Budgets

2011-07-16T22:36:00.000-04:00

Melissa Moore (@mooremm), Executive Director of INFORMS, recently tweeted the following question: "What #ORMS or #Analytics tools would you use if you were asked to help solve the US Federal #budget/#debt impass?" My initial reaction (after verifying that a flammenwerfer is not considered an OR tool) was that OR and analytics would be of no use in the budget debate (debacle?). OR and analytics rely on facts and logic; it is unclear that either side of the debate is interested in facts or willing to be constrained by logic.

The question did set me to thinking about the difference between facts and beliefs. I have a hard time sorting out when demagogues, whether politicians or media bloviators, are espousing positions they actually believe and when they are simply pandering for ratings/votes. (My cynicism is hard won: I grew up in New York, went to school in New Jersey, and cast my first vote to reelect Richard M. Nixon. It's been downhill from there.) For the sake of argument, let's stipulate that both sides are acting on beliefs they truly hold. When I was younger it seemed to me that, however venal either side's motives might be, both the left and the right were capable of negotiating based on some common understanding of governance and the political, social and economic realities of the country they governed. It's hard to trade horses, though, when one side can't tell a horse from a zebra and the other can't tell a horse from a camel. Today, one party thinks that the answer to any question that does not contain the phrase "gay marriage" is "cut taxes". The other side thinks that the answer to any question that does not contain the phrase "gay marriage" is "tax the rich". That the proposed solution might not work is simply inconceivable (as is the possibility that the other side's solution might work).

The somewhat unnerving truth, however, is that everything we think we know as a fact (raw data aside) is ultimately a belief. My training is in mathematics. Casual users of mathematics, and even forgetful mathematicians, tend to think that what has been "proved" (i.e., a theorem) is definitively true. In reality, theorems are merely statements that must follow logically from a set of axioms (beliefs). The system of logic we accept is itself a matter of belief, but in the interest of avoiding a painful flashback to an undergraduate formal logic course I'll drop that line of thought right now. As in mathematics, so too in the physical sciences: theory arises from a mix of assumptions and empirical evidence; when new evidences clashes with the theory, modifications are made; and when the modifications become untenable, some assumption is altered or deleted and the theory is rebuilt. (Remember when the speed of light was a constant?)

So if mathematics and physical sciences are built on leaps of faith, we really cannot fault elected representatives (and economists) from doing the same. What we perhaps can demand, though, is that these beliefs at least be acknowledged as beliefs (not "proven facts"), and that decision makers attempt to examine the likely impact of any of those beliefs turning out false. As a parallel (pun deliberate), consider Euclid's Elements, written ca. 300BC, in which Euclid developed many theorems of what we now refer to as "Euclidean" geometry based on five postulates. The postulates appear self-evident, and mathematicians over the centuries tried unsuccessfully to derive one from the others (turning the derived one into a theorem). In the 19th century, Nikolai Lobachevsky famously replaced Euclid's fifth postulate with a negation of it, perhaps hoping to prove the fifth postulate from the others by contradiction. Rather than finding a contradiction, he invented hyperbolic geometry, which is not only consistent as a mathematical system but has actually found use (those bleeping physicists again).

So, back to the original question: can OR bring any useful tools to bear on the budget debate? With enough time and effort, and exploiting the systems perspective that underlies OR, perhaps we could diagram out the interplay of all the assumptions being made (consciously or unconsciously) by each side; and perhaps, using simulation models based on those assumptions and calibrated to historical data, we could explore the consequences of each side's preferred solution (or, for that matter, any compromise solution) should any specific assumption not hold up. It would be a massive undertaking, and I am not confident it would be productive in the end. Zealously held beliefs will not yield easily to "what if" analyses.

Perils of "Big M"

2011-07-11T19:39:00.000-04:00

A somewhat recent Twitter exchange with Bo Jensen, which I believe was triggered by a post on an optimization forum (details of which are fading rapidly from my memory), motivated this entry. It deals with optimization models (specifically linear or integer linear ones) that are constructed using what is sometimes referred to as the "big M" method.

Terminology

First, I need to clarify terminology. Any reference to "big M" means the incorporation into a model of coefficients (usually represented by $M$) that are in a sense surrogates for $\infty$. The phrase "big M method" is frequently used to cover two somewhat different modeling techniques.

One eliminates the first phase (finding a feasible solution) of the two-phase simplex method by merging the phase I and phase II objective functions into a single function, penalizing the artificial variables with very large coefficients ($M$). It's an example of using a penalty function, and requires a sufficiently large value of $M$ to ensure that violating a constraint is never optimal.
The other provides a way for binary variables to turn constraints on or off. Consider, for example, a lockbox problem in which the number $x_{ij}$ of checks from customer $i$ assigned to lockbox location $j$ cannot exceed some capacity limit $M$ if the location is used (binary variable $y_j=1$), but should be zero if the location is not used ($y_j=0$). This is formulated as $$x_{ij}-My_j\le 0.$$

Rounding error

My first course in graduate school was in numerical analysis, and it came as a bit of a shock to my system. We covered rounding, truncation and representation errors rather extensively -- very disconcerting stuff to a pure mathematician. One would like to think that computers do arithmetic accurately. One would like to believe that politicians are honest and competent. One is destined to be disappointed both times.

I won't go into a lengthy introduction to the aforementioned types of error (which I'll somewhat cavalierly lump together under the name "rounding error"). Let me instead give a small example. The code is in Python (which represents all floating point numbers in double precision), but it could be any language.

x = 1.0e10
y = 1.0e-9
z = x - y
w = z - x
print x, y, z, w
print (z == x)
print (w == -y), (w == 0)

The output of the first print line is:

1.00000000000000e10 1.00000000000000e-9 1.00000000000000e10
 0.000000000000000

Note that z looks suspiciously like x (it should be strictly smaller), and w (which should be -y) is zero. That could just be limited precision in the output. The next three prints, however, tell the tale. The first (z==x) and third (w==0) should be false, while the second (w==-y) should be true. What we actually get:

True
False True

Whoops!

This leads me to a few truisms from that long-ago numerical analysis course:

Addition or subtraction of numbers introduce rounding errors, and addition or subtraction of numbers with substantially different magnitudes introduce rounding headaches. (Multiplication and division can also introduce small errors, but addition and subtraction tend to be the killers. The biggest problem with multiplication or division is probably overflow or underflow.)
Comparisons are closet subtractions. It's generally unsafe to test $x=y$ when $x$ and $y$ are floating point numbers. Instead, test $|x-y|\lt \epsilon$ for a suitably small (but not too small) $\epsilon \gt 0$.
In particular, things that should be zero often come out not quite zero (commonly referred to as "decimal dust"). More than once I've seen someone ask why some solver gave an optimal solution to his problem that had a binary variable equal to 1.0e-9 (throw in a few more junk digits if you like). It should be either 0 or 1! Well, yes; but if the solver held out for exactly 0 or exactly 1, you'd get a lot of wrong answers due to decimal dust. So the solver accepts that "darned near 0" is 0 and "darned near 1" is 1.

$M$ in the objective or RHS

Having $M$ in the objective function (as in the first definition of "big M" above, eliminating phase I of the simplex method) or having it as the right hand side of a constraint introduces rounding error (per my first bullet above). Specifically, $M$ in the objective can cause rounding errors in reduced costs, which may confuse the solver about which columns are candidates for entry to the basis. $M$ in the right hand side can introduce rounding errors in the right hand sides of subsequent tableaus, which may cause problems selecting the variable to leave the basis. As far as I know, those issues are generally survivable, and I've not seen any crash landings caused by it. Perhaps someone who has will comment with an example of a bad outcome from $M$ on the perimeter of the model.

$M$ in the constraints

The lockbox formulation illustrates the situation where $M$ shows up as a coefficient in the constraint matrix. This is where serious misadventures can occur. If $M$ creeps into the basis matrix $\textbf{B}$ (or a column that is a candidate for entry into the basis matrix), the ensuing rounding errors can cause $\textbf{B}$ to look singular (or can cause a column that should be ineligible for entry to the basis, because it would make $\textbf{B}$ singular, look eligible). The rounding errors can also cause severe loss of precision in the computation of $\textbf{B}^{-1}$. In technical terms, $M$ (or $1/M$) appearing in $\textbf{B}$ can make $\textbf{B}$ ill-conditioned.

Suppose that, in a formulation with $M$ in constraints, we bump into the following candidate for a basis matrix$$\textbf{B}=\left[\begin{array}{ccc} 1 & 0 & \frac{1}{M} \\ M & 0 & 1 \\ 1 & M & 0\end{array}\right].$$Since $$\textbf{B}\ \left[\begin{array}{c}1 \\ \frac{-1}{M} \\ -M\end{array}\right]=\left[\begin{array}{c}0\\0\\0\end{array}\right]$$it is obvious that $\textbf{B}$ is singular. Right? Well, let's check the determinant of $\textbf{B}$. I did the calculations using Sage 4.7, but I have no reason to think other packages would do any better (although pathologies might well vary).

Here is the Sage code I used to compute the determinants:

B = matrix(3,3,[1.0,0.0,1.0/M,M,0.0,1.0,1.0,M,0.0]);
[det(B.substitute(M=10.^k)) for k in (28, 29, 30, 31)];

Here is a table of the results:$$\begin{array}{rccc}M & 10^{28} & 10^{29} \\ \det(\textbf{B}) & 0.000000000000000 & 0.000000000000000 \\ \\
M & 10^{30} & 10^{31} \\ \det(\textbf{B}) & -1.40737488355328e14 & 0.000000000000000\end{array}$$
So something inexplicable (but bad) happened when $M=10^{30}$, presumably due to loss of precision in some key computation.

You won't see exactly this glitch in a typical "big M" model, but if you play with enough "big M" formulations, sooner or later (probably sooner) you will trip over numerical instability attributable to mixing disgustingly large coefficients with considerably smaller ones.

$M$ in MIP models

As I mentioned above, one common use of "big M" formulations (illustrated by the lockbox example) is to allow a binary variable to turn a constraint on or off. Even if ill-conditioned basis matrices do not occur, large values of $M$ can cause branch-and-bound solvers to make slow progress solving the mixed-integer programming model (MIP). Consider our simple lockbox constraint: $x_{ij}-My_j\le 0$. There will be an associated penalty cost (say, $c_j y_j$) in the objective function for using location $j$. Now suppose that, at some point, the solver is considering a node where $x_{1j}=2$, $x_{2j}=5$ and $x_{ij}=0$ for other values of $i$. Logically, we know this requires $y_j=1$ and incurs cost $c_j$; but in the LP-relaxation of the node problem, $y_j=5/M$ is sufficient, incurring a cost of just $5c_j/M$. For large values of $M$, this substantially underestimates the true cost, leading to loose node bounds. Loose bounds at nodes in turn make it hard for the solver to prune nodes based on objective value, and so more nodes need to be examined, slowing the solution process.

$M$ and (dubious) pedagogy

I can't write a post this long without at least one rant. Let me stipulate up front that neither text book authors nor instructors can be expected to cover every exigency. That said, many instructors and authors introduce students to "big M" formulations in the abstract, because they are mathematically neat and easy to explain, and then move on to the next topic without regard to the grubby implementation details. I confess to having done this myself when I was young and foolish.

At least one thing, though, is simply notational laziness. That $M$ in my lockbox example? It should be $M_j$. There is no reason why a single value should be used for all instances of $M$ in a model, and very good reasons why the values should differ. I don't recall seeing $M$ subscripted very often, if ever. (Are text book authors charged for each subscript they use?) In certain examples, including lockbox problems, there is a natural and obvious value for $M$ (typically a capacity limit), and in those cases you see individualized values being used. More often, though, there is just this undifferentiated symbol $M$ floating throughout the model. I think that influences users to actually use a single, very large value everywhere. (I recently saw a model on a CPLEX support forum that was clearly a "big M" model with a single large value of $M$ in about half the constraints.)

Concluding thoughts...

... and if you're still with me, you're very ready for this post to conclude.

If you are going to use a "big M" formulation, look for the smallest values of $M$ that work in the context of the model. (I once wrote a paper in which I analytically derived a sufficiently large but not horribly inflated value for $M$. There are tricks for doing so.)
$M$ does not need to be one size fits all.
Particularly if $M$ will show up as the coefficient of a variable in a constraint, be prepared for numerical instability. Learn how to detect numerical problems and what levers your solver has for coping with instability.
Consider alternatives to a "big M" approach (two phase simplex, Benders decomposition, ...) if you have stability or accuracy problems you cannot resolve.

Hitting the Muggles from All Sides

2011-06-19T18:10:00.001-04:00

The theme of the June INFORMS Blog Challenge is "O.R. for Muggles". I mention that at the outset because I do not want to be accused of using the word "Muggles" to drive search engine traffic to my blog. (For that I use references to naughty videos featuring Dumbledore.) The rationale for the theme is articulated as follows:

[T]hese conversations tend to reach an already involved audience. We’d love to spread the word about OR/MS and analytics to a wider audience.

So we shall assume here that "Muggles" are people who are not part of the O.R. community (and not students likely to join the O.R. community).

If our goal is to spread the word about the value of O.R. and analytics, and particularly if the ultimate aim is to generate work for O.R. experts and to raise its prestige (and priority) in academic institutions, we might want to adopt a three-pronged strategy.

Top Down

This approach targets C-level executives (or at least executives as high in the corporate food chain as we can reach) along with their governmental counterparts. The key is to convince them that they can achieve competitive advantage using O.R. and analytical modeling (or that they will suffer a competitive disadvantage if they fail to do so). Hopefully they will then give marching orders to subordinates to seek out opportunities to exploit this wonderful new (?) type of magic.

Business honchos are famous both for being very busy and for having short attention spans. Discussing mathematical or statistical details would be the kiss of death here. What might work would be to present them with short, non-technical but compelling stories of organizations that have benefited significantly from O.R. or analytics. Benefiting from O.R. models hard-coded into "canned" software is not what I have in mind; the stories need to involve customer-specific analysis by human (or plausibly human) experts.

I'm pretty sure consultants have been doing this for years, and I think INFORMS is doing a decent job as well. Publicizing the Edelman awards is a step in the right direction, although my impression is that the Edelman videos are way too long to engage a C-level executive. We should probably be doing more along this line, though, perhaps including more focus on non-profits and government organizations. How you get to these people is a question above my rather modest pay grade. Articles in key publications (Forbes? Business Week? Harvard Business Review?) may be part of the answer. Guest speakers at business round tables may be another component.

Bottom Up

Here we try to plant seeds in the minds of students about to enter the working world. I don't mean students majoring in O.R., industrial engineering, management science and augury (oops, make that "analytics"). We need to target generic business students (especially MBA candidates) and try to convince them that there is an arsenal of really useful tools that may avail them down the road (provided they acquire artisans capable of using those tools).

I'm inclined to grade our performance here as at best a C. When I began my academic career (about the same time transistors -- not integrated circuits -- were pushing vacuum tubes out of the computing business), it was fairly common for both undergraduate and graduate business curricula to include mandatory "quantitative methods" courses. Unfortunately, we tended to shoot ourselves in the foot (repeatedly) by putting way too much emphasis on theory and hand computation, too little emphasis on the business consequences of the solutions to the models ("you will save $XXX") ("and earn a quick promotion"), and way too little emphasis on problem identification and classification (where you will actually see this problem in the "real world", how your problem might be amenable to a "transportation model" even though it has nothing to do with transportation, why your actual mess will not be nearly as neatly structured as a textbook problem, etc.). This was exacerbated by a lack of user-friendly software, or perhaps any software at all.

The result was that we produced, at least in the U.S., generations of business graduates who's main take-away from their quant methods course was that they hated it and never wanted to deal with that stuff again. Their lack of enthusiasm when giving feedback to administrators paved the way for other disciplines to push aside quant methods courses and grab their space in the curriculum. Quant methods is still required at many schools, and is very popular at some, but its "footprint" in the curriculum is often diminished, and it is all too frequently no longer required at all (excluding perhaps a basic statistics course).

Software and hardware are ubiquitous now, and the software quality is quite good. Based on recent market-leading textbooks, though, I believe we are still focusing general quant methods courses heavily on application of specific O.R. tools (linear programming, simulation, decision trees). Some skill building is fine, but it is hard to say whether planting graduates with good skills at small-scale modeling in supply chain, marketing or finance positions will lead organizations to attack larger and more complex problems (where O.R. analysts are needed), or will diminish the need for workers with O.R. training (because the generic business graduate can do enough of the analysis on his or her own). Perhaps more critically, it is not clear to me that a non-O.R. graduate with decent modeling skills for the scope and scale taught in a classroom will necessarily be able to identify larger opportunities that would justify bringing in consultants or creating an internal O.R. group.

The key here may be to dial back a little on teaching specific models and algorithms, and put more emphasis on general modeling and problem-solving skills (including recognizing the actual problem and delineating its scope).

Sideways

This is the direction that I think is most often overlooked. Small to medium businesses (SMBs), small non-profits and small governmental institutions (think your local school district) are probably underserved by the operations research community, particularly as they may tend not to be lucrative potential clients for consultancies. The key decision makers are often not business school graduates, and may have no idea that O.R. and analytics even exist (unless they know "analytics" in the sense of parsing web server logs). Presentations at local Chamber of Commerce meetings, participation in local business forums (do your local businesses have a LinkedIn group?), and even pro-bono consulting will help show people both what O.R. is about and how it can pay off. My guess is that this group is particularly ripe for word-of-mouth marketing.

As I said, this segment is probably not particularly lucrative monetarily. Every once in a while, though, one of those SMBs will take off and become a large company; hopefully they will remember the role O.R. played in their growth. Organizations in this category that benefit from O.R. help may also have the ear of politicians and university administrators, which may foster some growth in O.R. curricula. Finally, press reports of success stories at this level may catch the eyes of executives in larger firms.

Do Gremlins Find Mint Tasty?

2011-06-15T18:01:00.065-04:00

In my two most recent posts I mentioned upgrading Linux Mint (to "Katya", version 11) and then tweaking it. The upgrade created one or two adventures, notably a loss of the ability to reorder the application buttons in the GNOME panel by dragging them. Editing GNOME panel properties such as its size, or whether it automatically expands, would restore the drag option, but no fix that I found survived the end of a session.

That changed on my office PC, for reasons unknown to me, after a routine application of updates. I'm not sure which update did what, but suddenly the ability to drag buttons is back. The fix came at a bit of a cost, though. The first time I logged in at the console after the upgrade (which I did remotely), I found that buttons dragged (good news) and windows minimized and maximized (not news), but that I could neither resize nor move windows (bad news!). Neither could I switch to any of the other workspaces I have set up. (Workspace Switcher is set for four workspaces.)

A little desperate Googling failed to find any report of the same problem but did lead me, indirectly, to the fix. In Control Center > CompizConfig Settings Manager > Window Management, Move Window and Resize Window had somehow become deselected and needed to be turned back on. Similarly, under Desktop the Desktop Wall control had to be turned on. I have no idea what turned them off -- moving, resizing and switching workspaces all worked the last time I was in the office -- but I assume it was something in the update. At least the fix was easy.

Meanwhile, I got a new machine at home and configured it to dual-boot Windows 7 (which came preinstalled) and Mint 11. This time I used the 64-bit version of Mint (my laptop and office PC run the 32-bit version). Whether due to my choice of the 64-bit version or because it was a clean install (not inheriting any settings from an earlier installation), button dragging worked from the outset on the home machine (once I made a change I will discuss momentarily), and so far there have been no sudden behavioral changes regarding windows.

That one change I made is rather important, though. When first installed, the 64-bit version did not create buttons for windows. If you minimized a window, it simply disappeared (though the app was still running), with no obvious way to recover it. Dragging buttons was not an issue, since there were no buttons. I can't picture working in an environment where minimized windows can be reopened. With a little digging, I discovered that the Window List (the container for the buttons) was not installed on the GNOME panel. It was easy to install it (right-click the panel, select "Add to Panel..." and then choose it from the menu). Positioning it was a bit trickier. You position it the same way you position any applet on the panel: right-click, choose "Move", slide it where you want it and then right-click again and choose "Lock to Panel". The problem is that the Window List itself is invisible, with neither drawn boundaries nor a distinct background color; so you have to grope for it (right-click where you think it might be and see what context menu you get). At least that's fixed now (unless another update brings a new gremlin with it).

Tweaking Mint Settings

2011-06-08T17:37:00.000-04:00

I got myself into a bit of an adventure with my office PC, recently upgraded to Mint 11 (Katya), and I'd better take some notes before I forget and have to relive the adventure.

As installed, Alt-Tab popped up a panel with thumbnails of all open windows, and let me cycle among them in a rather static way. (Choice of the word "static" relates to what follows.) In past versions, I've had Mint set up to task-switch with a bit more flair: displaying a rotating list of snapshots of the app windows in a horizontal bar, three at a time, with the center one brought to the foreground behind the switcher, and cycling through the list (ring) each time I hit Tab while holding down Alt. Bear with me if I don't use the official terminology for this effect, because part of today's adventure was learning some terminology that I do not find entirely intuitive. All I remembered going in was that (a) Alt-Tab was the key combination to make it happen (the same one used for "cool tabbing" in Windows, and thus easy to remember), (b) it required Compiz (installed by default with Mint), and (c) it was not a default behavior and thus needed to be set.

So I went to the Control Center, thence to CompizConfig Settings Manager, and stared at a multitude of choices, not many of which are self-explanatory. In tweaking settings, I managed to cause the maximize/minimize/close buttons on all windows to disappear (not desired -- I really use those a lot). I also found a setting labeled "Compiz Fusion Icon" (in Control Center > Hardware). It seemed odd that there would be a setting for an icon (doing what? choosing which version of the icon to display?), so I clicked it a couple of times but observed no results (because I'm unobservant ... more about this in a second). Finally, somewhere in the process of mucking with settings and dealing with messages about conflicts over certain key-combinations (most notably Alt-Tab and Shift-Alt-Tab) I managed to disable Alt-Tab entirely.

So I'll note here the key information necessary to resolve all this, since I'm sure I'll forget it by tomorrow. First, the "Compiz Fusion Icon" button in Control Center > Hardware actually did something: it added a "Compiz Fusion" icon to the GNOME panel (in fact, one per click, so I ended up with two side by side). Right-clicking the icon lets you switch between Compiz and Metacity, and gives easy access to the Compiz settings in the Control Center. I suppose the icon is handy if you plan to switch between Compiz and Metacity regularly; I don't, so I banished the icon again.

Second, to get the desired Alt-Tab variant, I needed to deselect "Static Application Switcher" in CompizConfig > Window Management and select "Application Switcher" instead, then modify key combinations as desired. (In point of fact, I ended up opting for the fanciest switcher, the "Shift Switcher", once I read about the choices.) Having very limited memory, I decided to change the keys for "Shift Switcher" so that Alt-Tab and Shift-Alt-Tab rotate forward/backward among windows in the current workspace, and Super-Tab and Shift-Super-Tab do the same in all workspaces. (Now if I can just remember that second part ...)

Third, the missing maximize/minimize/close controls for the windows were the result of the "Window Decoration" option under CompizConfig > Effects being deselected. (I don't think I did that, but it's possible an errant click was the culprit. I've seen one or two forum messages suggesting that it might be the action of a gremlin.) Here's a prime example of what I mean by unintuitive terminology. To me, calling those controls a decoration is like calling a door know a decoration. They're controls! I think of "decorations" as being not particularly functional, which those controls are. For that matter, I don't find them all that decorative. Anyway, turning "Window Decoration" back on restored the controls to their normal positions (and my blood pressure to its normal level).

Upgrading Linux Mint

2011-06-02T17:02:00.000-04:00

I believe that the Mint distribution of Linux, which I use, has a six month release cycle. Something I learned from watching cowboy shows on TV as a kid was that you don't change horses in the middle of a river, so I skip the upgrades that occur during the school year and just do the ones that occur late spring/early summer. As a result, I only get the odd numbered versions, which is fine. I've been champing at the bit to install Mint 11 (Katya), because I want to upgrade to LyX 2.0. I've already done so on my Windows box, but the dependencies for the Linux version would have created issues with Mint 9 (Isadora). Somewhat to my surprise (I've come to expect servers and mirrors to be slammed any time a major software distribution drops), I was able to download Katya within a few days of its release. I think the upgrade on my office machine is done (subject to the inevitable tweaking here and there), and I decided to jot down my notes on the process.

Problems:

The upgrade installs a new version of /etc/apt/sources.list.d/local-repository.list. Unfortunately, the sole line of text in it is buggered. It should end with "binary/" but instead ends with "katya". The result is that attempts to update packages after the installation fail. Fortunately, editing the file is an easy fix. I found the information fairly quickly after a Google search, but I'm surprised it's not listed among the "Known Issues", nor prominently posted on the Mint blog, nor posted in the vicinity of the download instructions.
Once I'd fixed the aforementioned bug and started updating packages, I got a lot of error messages about repositories. It turns out that the installation added to Synaptic's repository list a bunch of URLs for ubuntu.com and canonical.com that used "Katya" as the distribution name. The problem is that "Katya" is a Mint name, not an Ubuntu name. (I believe the corresponding Ubuntu distribution is "Natty", and in fact similar URLs containing "Natty" are also present.) So I weeded out the offending repository entries, and after that updates worked just fine.
For some reason, I cannot reload the r-cran-vr package. First it complained that several other R packages were unfilled dependencies. Then, after I updated those packages to current versions, it said I would have to revert to earlier versions of them. Perhaps the VR package is for an earlier version of R. In any case, I don't really need it, so I'll leave it uninstalled.
While attempting to reinstall software from a backup list of all installed packages, I kept getting an error message saying "fix broken packages first" -- even though Synaptic said there were no broken packages. This might have been related to the r-cran-vr problem. I skipped installing a bunch of packages, including r-cran-vr, and that got rid of the message.

Smooth bits:

Once again, having /home in a separate partition paid dividends. I told the installer to remount that partition as /home with the same file system it already had (ext3), and without reformatting. Voila, all personal stuff (including pretty much all software settings) was preserved. The only problem with this approach is that eventually Linux will be using the ext9287 file system, and my home partition will still be ext3.
Usually I have the installer reformat everything else to the latest file system, but my other main partition (/) was already ext4, so I told the installer to remount it there but not format it. Most of it gets overwritten anyway, but /opt came through intact, so a couple of (large) software packages I'd installed there survived the upgrade without needing to be reinstalled.
I used mintBackup to create a list of installed packages. After fixing the aforementioned problems with Synaptic and doing a couple of updates of the new installation (I'm not sure why two updates were required, but no big deal), I started reloading packages from this list (again via mintBackup). Although it's possible to select all the packages on the list from known repositories and reload in one gulp, I found it more useful to upload in groups. First, it meant that if a problem were going to occur, I didn't have to wait through eight petabytes of downloads to find out. Second, it's a nice way to do a little housecleaning. In particular, I did not select any of the lib* packages. My guess is that quite a few of them were vestigial, and any that were needed would presumably be installed automatically as dependencies of the package(s) that needed them.
The few apps I installed under Wine survived the upgrade (since they live in the home partition).

Minor Pains in the Posterior:

I have OpenSSH and the free version of NoMachine's NX server installed on my office machine, so that I can remote desktop to it. With every upgrade, I have to remember to: install new keys for OpenSSh; convince client machines to accept the new keys (not a big deal); install new keys for the NX server; distribute the public NX key to every machine running the client; and install the new key into each client session. Life would be easier if someone came up with a script to preserve all public/private key pairs during OS upgrades.
I use POPFile to filter spam (it runs continuously on my office PC and filters at the IMAP server, so my laptop and home machines get the benefit of the filtering). Sadly, the corpus (database) for POPFile seems to live somewhere in /usr, which means it gets clobbered by the upgrade, and so I have to retrain POPFile from scratch. Maybe next time I'll remember to track it down and back it up.
Apparently printer definitions are not housed in the home partition. I'm having to reselect them, and it took a couple of tries to get the right driver for our networked printer.
After the reload, I found I could not reorder application icons (for maximized and windowed applications, not applets) in the GNOME panel. Usually that is just a matter of grabbing the "button" for an application and dragging it laterally. (The corresponding functionality in Windows XP requires a third party application.) A Google search turned up similar reports on a support forum, but nothing very helpful by way of a solution. So I fooled around a bit, and at one point turned the "expand" property of the GNOME panel off (which causes it to size itself just big enough to hold its contents) and then back on (the default, which stretches it to the full width of the screen). I'm not sure if that fixed the problem (could be the post hoc ergo propter hoc fallacy), but after I did that, icon reordering returned.

Peeking Inside the Black Box

2011-05-29T17:33:00.000-04:00

From the perspective of an analyst, rather than a developer of algorithms, the computational side of operations research might be described in terms of a black box: insert model and data; turn crank; make sense of the results. When it comes to the question of how much the analyst needs to know about what goes on inside the box, I find myself walking a somewhat narrow line between the Um and the Yang.

When teaching statistics to end users, I resist the exhortations of some of my colleagues that students must do computations by hand to “really learn” about statistics. For instance, said colleagues will argue that in order for a student to grasp the concept of correlation, they must take a set of observations of a pair of variables and (manually) center the variables, compute squares and cross-products, total the squares and cross-products, and use the totals to compute standard deviations and the Pearson correlation coefficient. To me, that is just gratuitous grunt work. Students need to know the domain of the correlation coefficient (-1 to +1), when to use it (looking for linear relationships) or not (looking for nonlinear relationships), and its interpretation (including the dangers of making a leap from correlation to causation). The actual computation can safely be left to software.

On the other hand, the widespread availability of modeling software and powerful solvers has changed the practice of optimization in a very fundamental way. Once the exclusive province of people who had taken extensive coursework in the mathematical theory behind the pertinent algorithms (not to mention formal training in numerical analysis), optimization is now increasingly being undertaken by people who apparently have minimal formal training, and who may understand the contextual domain of the problem they are trying to solve but perhaps do not understand the mathematical underpinnings of the methods being used. I've seen evidence of this in a number of forums recently. One of the symptoms is a failure to understand issues relating to rounding error and numerical stability, ranging from the subtle (poor scaling leading to incorrect answers or solver failures) to the blatant (“My binary variable came out 0.99999999999 -- what went wrong??”).

A few recent posts suggested that some users either do not understand the difference between local and global optima or do not understand the role of convexity in optimization models. In particular, I cringe whenever I see nonlinear equality constraints in a model, whereas they don't seem to bother the model authors very much. (I'm not saying that nonlinear equality constraints are fundamentally wrong; I'm just saying that I'd really like not to have any in my model.) A very simple example will illustrate why.

Consider the following trivial optimization problems:\[\begin{array}{clccclc}\textrm{(D)} & \min & x & \,\,\, & \textrm{(C)} & \min & x\\ & \textrm{s.t.} & x^{2}+y^{2}\le1 & & & \textrm{s.t.} & x^{2}+y^{2}=1\\ & & -2\le x\le2 & & & & -2\le x\le2\\ & & -2\le y\le2 & & & & -2\le y\le2\end{array}\]The (convex) feasible region of problem (D) is a disk, while the (nonconvex) feasible region of problem (C) is a circle. The solution to both problems is clearly $(x,y)=(-1,0)$.

Let's perform a little experiment (using AMPL to model the problems and MINOS 5.51 to solve them). We will solve both (D) and (C) with initial values $(x,y)=(cos(\theta),sin(\theta))$ where $\theta$ is an integer multiple of $\frac{\pi}{4}$. The AMPL code is as follows:

# problem definitions
var x >= -2 <= 2;
var y >= -2 <= 2;
minimize Obj: x;
s.t. Disk: x^2 + y^2 <= 1;
s.t. Circle: x^2 + y^2 == 1;
problem D: x, y, Obj, Disk;
problem C: x, y, Obj, Circle;

# bit used to define starting locations
param pi4 := atan(1); # pi/4
set ANGLE := 0..7; # from 0 to 7/4*pi

# storage for optimal solutions
param dsol {ANGLE};
param csol {ANGLE};

# solve disk problem from all starting angles
problem D;
for {t in ANGLE} {
  let x := cos(t*pi4);
  let y := sin(t*pi4);
  solve;
  let dsol[t] := x;
}

# solve circle problem from all starting angles
problem C;
for {t in ANGLE} {
  let x := cos(t*pi4);
  let y := sin(t*pi4);
  solve;
  let csol[t] := x;
}

display dsol, csol;

The results? For all starting angles, MINOS determines that $(x,y)=(-1,0)$ is the optimal solution to (D). That also applies for (C), with one glaring exception: when $\theta=0$, MINOS decides that the initial value $(x,y)=(1,0)$ is the optimal solution.

The figure below tells the tale. MINOS uses a reduced gradient method, which is a souped-up form of steepest descent. If allowed to, it will move in the direction pointed to by the gradient of the objective function at the current point when maximizing, and in the opposite direction when minimizing. (In this example, the gradient is a constant $(1,0)$.) When movement in that direction is infeasible, it will project the positive or negative gradient onto the hyperplane tangent to the feasible region at the current point, and search in that direction.

The red arrows indicate the (constant) negative gradient direction; the blue arrows are the projections of the gradient onto the unit circle. Having a hard time seeing the blue arrows anchored at $(\pm1,0)$? That's because they have length zero. So for any starting point other than $(\pm1,0)$ in problem (D), MINOS moves right to left across the unit disk until it reaches the boundary (the unit circle), then wends its way around the circle until it reaches the optimum at $(-1,0)$. If it starts from $(+1,0)$, it cuts straight across the $x$-axis and arrives directly at the optimum. For problem (C), cutting across the disk is not an option. Given any start other than $(\pm1,0)$, MINOS winds around the circle. Started at $(+1,0)$, however, MINOS sees a zero projection of the gradient, declares victory, stages a photo op and goes home.

The behavior of MINOS on problem (C) is correct given what's inside the black box. MINOS only guarantees local optima, and even that can only be delivered if the problem is moderately well behaved and/or the starting point is chosen well. Ipopt, another popular nonlinear solver, has similar limitations. From some recent posts that I've seen, though, I have the impression that some users are creating highly nonconvex models and expecting optimal solutions they are not destined to get. Compounding this, of course, is the fact that the solver will generally not know it has arrived at a suboptimal solution, and therefore will not alert the user that the solution is suboptimal.

Perhaps modeling languages and solvers should ship with a “warning label” stating that use of the software without first reading a book or taking a course in linear/nonlinear/integer programming is inadvisable.

Speaking of books, I can recommend David Luenberger's "Linear and Nonlinear Programming" (an updated version of which has apparently been published with coauthor Yinyu Ye).

Stepwise Regression in R: Part II

2011-05-23T17:37:00.000-04:00

Someone requested a demonstration of how to use the R stepwise function I previously posted, so here goes. I'll use the "swiss" data set that comes with R (in the datasets package). There are six variables in the data set; I will use Fertility as the dependent variable (mainly because that is what the example code in the help file for regsubsets does). The code below assumes that my function is saved in a file named stepwise.R, and that the working directory is set to the folder containing that file.

Decisions to add or delete a variable in my function are based on an F-test comparing the model with and without the variable. In both cases, the null hypothesis is that the variable's true coefficient is zero, so a variable is deleted if we fail to reject the null hypothesis and added if we succeed in rejecting the null hypothesis. For demonstration purposes, I will use significance levels $\alpha=0.05$ for deletions and $\alpha=0.10$ for additions.

Here is the code:

source('./stepwise.R') # load the stepwise function
data(swiss) # 47 observations of 6 variables, from dataset package
attach(swiss) # so we don't have to prefix every variable
# we will (arbitrarily) use alpha = 0.05 to add a variable and alpha = 0.10 to remove one
# the first run will start with just a constant term
stepwise(Fertility ~ 1 + Agriculture + Examination + Education + Catholic + Infant.Mortality, Fertility ~ 1, 0.05, 0.10)
# the second run starts with the complete model and initially winnows it
stepwise(Fertility ~ 1 + Agriculture + Examination + Education + Catholic + Infant.Mortality, Fertility ~ 1 + Agriculture + Examination + Education + Catholic + Infant.Mortality, 0.05, 0.10)

Created by Pretty R at inside-R.org

The output for the first call (which starts with just a constant term, and builds from there) is as follows:

            Estimate Std. Error  t value     Pr(>|t|)
(Intercept) 70.14255   1.822101 38.49542 1.212895e-36

S = 12.491697, R-sq = 0.000000, R-sq(adj) = 0.000000, C-p = 94.805296
=====
+++ Adding Education 

              Estimate Std. Error   t value     Pr(>|t|)
(Intercept) 79.6100585  2.1040971 37.835734 9.302464e-36
Education   -0.8623503  0.1448447 -5.953619 3.658617e-07

S = 9.446029, R-sq = 0.440616, R-sq(adj) = 0.428185, C-p = 35.204895
=====
+++ Adding Catholic 

              Estimate Std. Error   t value     Pr(>|t|)
(Intercept) 74.2336892 2.35197061 31.562337 7.349828e-32
Education   -0.7883293 0.12929324 -6.097219 2.428340e-07
Catholic     0.1109210 0.02980965  3.720974 5.598332e-04

S = 8.331442, R-sq = 0.574507, R-sq(adj) = 0.555167, C-p = 18.486158
=====
+++ Adding Infant.Mortality 

                    Estimate Std. Error   t value     Pr(>|t|)
(Intercept)      48.67707330 7.91908348  6.146806 2.235983e-07
Education        -0.75924577 0.11679763 -6.500524 6.833658e-08
Catholic          0.09606607 0.02721795  3.529511 1.006201e-03
Infant.Mortality  1.29614813 0.38698777  3.349326 1.693753e-03

S = 7.505417, R-sq = 0.662544, R-sq(adj) = 0.639000, C-p = 8.178162
=====
+++ Adding Agriculture 

                   Estimate Std. Error   t value     Pr(>|t|)
(Intercept)      62.1013116 9.60488611  6.465596 8.491981e-08
Education        -0.9802638 0.14813668 -6.617293 5.139985e-08
Catholic          0.1246664 0.02889350  4.314686 9.503030e-05
Infant.Mortality  1.0784422 0.38186621  2.824136 7.220378e-03
Agriculture      -0.1546175 0.06818992 -2.267454 2.856968e-02

S = 7.168166, R-sq = 0.699348, R-sq(adj) = 0.670714, C-p = 5.032800
=====

So all the predictors other than Examination are added. Now here is the output from the second call:

                   Estimate  Std. Error   t value     Pr(>|t|)
(Intercept)      66.9151817 10.70603759  6.250229 1.906051e-07
Agriculture      -0.1721140  0.07030392 -2.448142 1.872715e-02
Examination      -0.2580082  0.25387820 -1.016268 3.154617e-01
Education        -0.8709401  0.18302860 -4.758492 2.430605e-05
Catholic          0.1041153  0.03525785  2.952969 5.190079e-03
Infant.Mortality  1.0770481  0.38171965  2.821568 7.335715e-03

S = 7.165369, R-sq = 0.706735, R-sq(adj) = 0.670971, C-p = 6.000000
=====
--- Dropping Examination 

                   Estimate Std. Error   t value     Pr(>|t|)
(Intercept)      62.1013116 9.60488611  6.465596 8.491981e-08
Agriculture      -0.1546175 0.06818992 -2.267454 2.856968e-02
Education        -0.9802638 0.14813668 -6.617293 5.139985e-08
Catholic          0.1246664 0.02889350  4.314686 9.503030e-05
Infant.Mortality  1.0784422 0.38186621  2.824136 7.220378e-03

S = 7.168166, R-sq = 0.699348, R-sq(adj) = 0.670714, C-p = 5.032800
=====

We start with the full model, delete Examination, and stop there.

Not content to leave well enough alone, let's see what happens if we start with the "E" variables (Education and Examination) and go from there. The code for the function call is

stepwise(Fertility ~ 1 + Agriculture + Examination + Education + Catholic + Infant.Mortality, Fertility ~ Examination + Education, 0.05, 0.10)

Created by Pretty R at inside-R.org

and the output is

              Estimate Std. Error   t value     Pr(>|t|)
(Intercept) 85.2532753  3.0854981 27.630312 1.945244e-29
Examination -0.5572183  0.2319374 -2.402451 2.057160e-02
Education   -0.5394570  0.1924380 -2.803277 7.497224e-03

S = 8.981812, R-sq = 0.505485, R-sq(adj) = 0.483007, C-p = 28.135883
=====
+++ Adding Infant.Mortality 

                   Estimate Std. Error   t value     Pr(>|t|)
(Intercept)      55.2746618  8.8077340  6.275696 1.451652e-07
Examination      -0.5108888  0.2063175 -2.476226 1.729132e-02
Education        -0.5225093  0.1709099 -3.057221 3.832793e-03
Infant.Mortality  1.4556114  0.4064507  3.581274 8.644778e-04

S = 7.973957, R-sq = 0.619096, R-sq(adj) = 0.592521, C-p = 14.252399
=====
+++ Adding Catholic 

                    Estimate Std. Error    t value     Pr(>|t|)
(Intercept)      50.02820666 8.66076269  5.7764204 8.325568e-07
Examination      -0.10580461 0.26036962 -0.4063631 6.865390e-01
Education        -0.70415772 0.17969218 -3.9186887 3.221868e-04
Infant.Mortality  1.30567908 0.39150335  3.3350393 1.790664e-03
Catholic          0.08631125 0.03649293  2.3651501 2.271709e-02

S = 7.579356, R-sq = 0.663865, R-sq(adj) = 0.631853, C-p = 9.993398
=====
--- Dropping Examination 

                    Estimate Std. Error   t value     Pr(>|t|)
(Intercept)      48.67707330 7.91908348  6.146806 2.235983e-07
Education        -0.75924577 0.11679763 -6.500524 6.833658e-08
Infant.Mortality  1.29614813 0.38698777  3.349326 1.693753e-03
Catholic          0.09606607 0.02721795  3.529511 1.006201e-03

S = 7.505417, R-sq = 0.662544, R-sq(adj) = 0.639000, C-p = 8.178162
=====
+++ Adding Agriculture 

                   Estimate Std. Error   t value     Pr(>|t|)
(Intercept)      62.1013116 9.60488611  6.465596 8.491981e-08
Education        -0.9802638 0.14813668 -6.617293 5.139985e-08
Infant.Mortality  1.0784422 0.38186621  2.824136 7.220378e-03
Catholic          0.1246664 0.02889350  4.314686 9.503030e-05
Agriculture      -0.1546175 0.06818992 -2.267454 2.856968e-02

S = 7.168166, R-sq = 0.699348, R-sq(adj) = 0.670714, C-p = 5.032800
=====

All roads seem to lead to the same model. Also note that the constant term was not explicitly stated in the third call (no "1+" in the formulas). As usual with R, a constant term is assumed unless explicitly omitted (using "0 +").

A Shoutout to Anki

2011-05-21T19:43:00.000-04:00

I'd like to point out Anki, an open source (GPL 3) virtual flashcard program I've been using. Anki runs on all major PC platforms (and an impressive array of mobile devices), and is feature-rich. It has a plug-in architecture. Cards can contain not just text but also images and audio files. Anki supports LaTeX, so it should be easy to put mathematical formulas on cards. Use of card decks is very flexible (including an easy way to have cards representing difficult concepts repeat sooner than cards representing easy concepts). It is easy to create or import card decks, and you can share card decks (and plug-ins) with other people through their AnkiWeb site. (Disclaimer: I have not looked at the available shared decks, nor have I looked at any plug-ins. The basic download fills my needs.)

My use for Anki has been to learn my students names. At the outset of each semester, I acquire a class list with student photos, strip out the photos, and turn them into an Anki deck. During idle moments at coffee shops, I play the decks and learn to associate names with faces. (Addressing students by name on the first day of class freaks them out; I think they tend to be more docile thereafter.)

I'm not a big fan of rote memorization in education, but I suppose it has its place. I could see using Anki to learn formulas from queuing theory (for instance, "M/M/1 steady-state queue length" on the front, the corresponding formula on the back) or perhaps some terminology from linear programming (graph of a feasible region and an objective hyperplane tangent along an edge on the front, "multiple optima" on the back). As there are more things in heaven and earth than are dreamt of in my philosophy, I suppose there are more ways Anki could be used in the teaching of operations research.

My Infinity Is Bigger Than Your Infinity

2011-05-17T11:27:00.000-04:00

Mathematicians are used to the concept that some infinities (e.g., $\aleph_0$) are bigger than other infinities (e.g., $\aleph_1$). In mathematical programming, though, "infinity" is really just a placeholder for "I know there is a finite limit but I don't know what it is" (or "I know there is a finite limit but I'm too lazy to look for it"). The only place you'll see $\infty$ in a mathematical program is as an omitted bound on a variable.

There are two other truisms, related to this post, that are well known to anyone with a reasonable amount of experience solving mathematical programs via user-written code (including APIs to solver libraries). The first is that solvers run on double-precision floating point arithmetic, and $\infty$ is not a d-p number. So it is reasonable to treat any d-p number larger than some specified limit $M$ as a surrogate for $\infty$. In the CPLEX APIs, $M=1e+20$. (In the Java version of the Concert API, the static constants Double.MAX_VALUE and Double.POSITIVE_INFINITY work well for $\infty$, while -Double.MAX_VALUE and Double.NEGATIVE_INFINITY work for $-\infty$; but you can just as easily use $\pm 1e20$.) The second truism is that mixing very large coefficients with not-so-large coefficients in constraints is an invitation to numerical instability.

This brings me to something I tripped over accidentally a day or so ago. Consider the following trivial linear programming problem: $$\begin{array}{lc}\mathrm{maximize} & x \\ \mathrm{s.t.} & x\le M\end{array}$$ where $M>0$ is a large (but finite) number. The problem has an obvious (and trivial) optimal solution ($x=M$) ... unless you are using a solver, and $M$ is large enough to look like $\infty$. Indeed, for $M\ge 1e+20$, CPLEX (using any of the APIs) will (and should) declare the problem unbounded.

The following table shows the results of a little experiment I did (with CPLEX 12.2.0.2, but the results are not version-dependent):

	Presolve	No Presolve
$M\lt 1e+10$	Optimal ($x=M$)	Optimal ($x=M$)
$M= 1e+10$	Unbounded	Optimal ($x=M$)

Note the result in the lower left corner: the CPLEX presolver asserts that the problem is unbounded. An e-mail exchange with Dr. Ed Klotz of IBM sorted this out for me, and the rationale does in fact make sense. Suppose that the presolver encounters a variable $x$ that it can fix at a large bound $M$. As it eliminates the variable from the model, any instance of $x$ in the model (say, $a_i x$ in the $i^{\mathrm{th}}$ constraint) is replaced by a potentially large number ($a_i M$), which may introduce numerical instability (see second truism above). So CPLEX is somewhat conservative during presolve about how large is too large. In effect, $\infty=1e+20$ in the solver but $\infty=1e+10$ in the presolver.

I discovered this purely by accident, because I'm a firm believer that no model should have coefficients (including bounds) that require me to type two digit exponent fields in scientific notation. If there are values that large, it's time to rescale. It just caught me by surprise that the surrogate for $\infty$ in the presolver was not the same one used in the APIs.

Rejiggering an R Data Frame

2011-05-15T07:29:00.000-04:00

This is a new experience for me. Mark Allen (author of the Open Source Research blog) tweeted a question about rearranging a data frame in R. The question being longer than 140 characters, he used Deck.ly to post an extended tweet. So I learned something new about the Twitterverse. I don't have a TweetDeck account, though, so my best option to post a response is to put it here.

Mark has a data frame with one row for each response to any of a set of questions, and three columns: respondent ID; question number; response. Here's a chunk of R code to create a small demo data frame along those lines:

# create some data
m <- matrix(c(1,1,11,2,3,23,1,2,12,2,1,21,2,2,22,1,3,13), nrow=6, ncol=3, byrow=TRUE)
d <- data.frame(m)
names(d) <- c("ID","Question","Answer")
print(d)

Created by Pretty R at inside-R.org

The output is:


  ID Question Answer
1  1        1     11
2  2        3     23
3  1        2     12
4  2        1     21
5  2        2     22
6  1        3     13

Here is code to rearrange it:

# sort the data by ID, then by Question
d <- d[do.call(order,d),]
# extract a list of unique IDs and Question numbers
id <- unique(d[,"ID"])
q <- unique(d[,"Question"])
# rearrange the answers into the desired matrix layout
m <- matrix(d[,"Answer"], nrow=length(id), ncol=length(q), byrow=TRUE)
# add the ids and make a new data frame
m <- cbind(id, m)
dd <- data.frame(m)
names(dd) <- c("ID", paste("Q", q, sep=""))
print(dd)

Created by Pretty R at inside-R.org

The output of the last line (the rejiggered data frame) is:

  ID Q1 Q2 Q3
1  1 11 12 13
2  2 21 22 23

Will Analytics Drag O.R. Back to Its Roots?

2011-05-13T20:06:00.000-04:00

The INFORMS blog challenge for May is "O.R. and Analytics", so here goes ...

There are about as many definitions of "analytics" as there are explanations for the recent global economic crash. My take on "analytics" has been that, at least until now, what it meant to business executives was "take this huge pile of data and make sense of it". Operations research models in the real world have always relied on some level of data analysis, because models contain parameters and parameters must be estimated. (Outside the real world -- which is to say in academe and government service -- modelers get to make up whatever parameter values they like.) That said, I've never really associated heavy duty data analysis with O.R. Statisticians analyze data and data miners try to read sheep entrails (according to the statisticians); O.R. analysts build and use models.

As the term "analytics" grabs mind share among executives, though, O.R. societies and O.R. practitioners are trying, to borrow a phrase from Microsoft, to "embrace and extend" it. The societies see this as a way to boost membership and conference attendance, and both the societies and practitioners see it as a way to enhance the visibility of O.R. to the people who will (hopefully) employ O.R. analysts, directly or as consultants. I would not be surprised if the data analysis crowd see this as O.R. people trying to share the spotlight uninvited. Fortunately, since their forte is recognizing patterns as opposed to prescribing solutions, they'll see us coming but probably won't be able to keep us out.

Extending the O.R. brand will require more than just saying "operations research ... including data analysis" or "operations research is analytics ... plus so much more". If we're serious about this, we'll need to reconsider what we mean by "operations research", and perhaps how we go about its practice. Therein lies an opportunity to return to O.R.'s roots.

The history of O.R. traces back to World War II, and the stories from that era have a common thread. Someone has a problem. The problem appears somewhat quantitative in nature (or at least amenable to measurement and quantification). We want to model it, and see what the model suggests might solve the problem. Absent from this description is any pigeon-holing of the problem as a linear program, or a queueing problem, or a discrete event simulation. One of the classic examples was finding ways to move men and materiel from the U.S. to the U.K. more safely during the Battle of the Atlantic. The answer involved determining the optimal shape of a convey (which was not a mathematical programming problem, the word "optimal" notwithstanding), recognizing that small convoys of fast ships (small possibly meaning a single ship) might not need an escort (they were too fast for the U-boats to pick on), and so forth.

As O.R. bloomed after the war, we developed more and better tools (theory, algorithms, software) ... and along the way, we became more specialized. So now we have experts in optimization and experts in simulation and so on, and we tend to adhere to the maxim (which I will shamelessly bastardize) that if you're really good with a screwdriver, everything looks like a screw. At a recent INFORMS conference, I attended a session about teaching modeling to MBAs. Given the topic, I suspect most of the attendees were fellow academics, so I apologize if I offend any practitioners by tarring them with the same brush. At one point in the session, the presenters posed a scenario to us (the Red Cross is thinking about paying for blood donations, and wants some consulting on it), and, with not much more detail than what I just gave, turned us loose on it. The optimizers started writing optimization models. The simulators started sketching out simulation models. If there were any decision analysts in the room, I'm sure they were drawing decision trees. In other words, most of us framed the problem in terms of our favorite tools, rather than fleshing out the problem (which was quite vague) and then looking for tools (possibly mathematically unsophisticated tools) that would match it.

As we try to figure out how data mining and "business intelligence" (note that I'm skipping all oxymoron jokes here, a severe exercise in restraint) fit with O.R., perhaps we can seize the opportunity to starting conceptualizing (and teaching) O.R. as first and foremost sorting out and describing what the problem actually is. My very limited understanding of data mining suggests that it leans more toward letting the data tell you what it wants to tell you than to making the data fit a preconceived model; extend that to the overall problem, rather than just the data, and we're back to something I think the progenitors of O.R. would recognize.

An Unbalanced Round Robin Bridge Schedule

2011-04-30T22:54:00.000-04:00

Ages ago, while studying (sort of) for my doctorate in mathematics, I played a significant amount of duplicate bridge, frequently with my grad school buddies Bluto and Dawn and my now-long-lost love (She Who Will Not Be Named). Bluto and Dawn (who are married) are now retired, and not too long ago I got an e-mail from Bluto. He and Dawn continue to play bridge with a group of friends, and they have a sort of league set up. Since he and Dawn both studied math, the duty of constructing a schedule for the league naturally fell to them.

The way their league functions is as follows. Once a month, couples get together at various houses, with four couples at each house (that being the most people couples are willing to host). Their league has 12 couples, so there are three venues operating simultaneously. At each house, each of the four couples plays against each of the other couples (so three games per venue per date). The objectives in forming the schedule are to minimize the variation in how often any pair of couples faces each other, and simultaneously to minimize the variation in how often a couple is called upon to host a game. The planning horizon is eight dates.

Dawn (the brighter of the two) was apparently able to construct a balanced schedule for 16 couples, four venues per date and an unspecified horizon (which I'm sure was divisible by five), despite being hampered by a degree in abstract algebra. Neither of them could find a schedule for 12 couples/eight dates, in part because it cannot be balanced: each couple plays three games per date, so 24 games total, which means they cannot play the other 11 couples an equal number of times. Bluto asked me if this was an operations research problem, which it most definitely is.

It can be attacked in a variety of ways (mixed integer program, constraint program, metaheuristic); I chose to try a MIP model first, since that's the type of software with which I'm most familiar. As with many MIP problems, the model was easy but the solution was a bit time-consuming, even after tweaking the model to eliminate some of the symmetry that plagues the problem.
I won't bore anyone with the model details, but I thought I'd post the best schedule I found, in case anyone else happens to be trying to schedule 12 team round-robins (although I suspect the parameters of this particular problem are rather unusual). In the tables below, couples are identified with the letters 'a' through 'l'; hosts are capitalized.

Date	Game 1	Game 2	Game 3
1	abcD	efgH	iJkl
2	aeFj	Bdhl	cgIk
3	agHj	Bfkl	cdeI
4	Abek	Cghl	dFij
5	ahiK	bcfG	dejL
6	acEl	bGij	dfhK
7	adgL	bEhi	Cfjk
8	Afil	bchJ	Degk

Charitably assuming I transcribed that correctly, each team plays every other team either two or three times. (With 12 teams playing three games on each of eight dates, for 24 games total per team, you would expect to play nine of the other 11 teams twice and the other two three times each, so this tracks.) Everyone hosts exactly twice. In terms of meeting Bluto's stated criteria, it does pretty well; but looking at it, I wonder if I should have added a penalty for couples hosting on consecutive dates, or tried to maximize the minimum elapsed time between hosting assignments for any couple?

Data Mining and Pharmaceutical Bar Tending

2011-04-17T18:32:00.000-04:00

In a recent article in OR/MS Today (a sequel to his excellent article in Analytics), Douglas Samuelson writes about various OR opportunities as the health care industry in the U.S. reacts to the Mother of All Health Care Bills. OR in health care also happens to be the theme of this month's INFORMS blog challenge (for which today's post is my entry).

Let me focus on one particular statement in Samuelson's latest article:

Another aspect of uncoordinated care is polypharmacy, the use of multiple prescription medications in combination, with too little attention to possible interactions. According to the medical examiner’s official report, polypharmacy killed high-profile celebrities Anna Nicole Smith and Michael Jackson, both of whom used multiple doctors and multiple pharmacies. Safety testing is usually done one medication at a time, so interactions can take quite some time to become identified and publicized. This is a growing problem, and information technology offers a promising answer.

I've seen statistics asserting that accidental drug interactions cause a staggering number of "adverse results" (dying being counted as an adverse result). Those events include not only prescriptions of multiple drugs whose interactions are unknown, but prescriptions of combinations with known interactions where the prescriptions may be issued by multiple doctors and/or filled at multiple pharmacies. My physician's office asks patients to bring all their meds with them on visits (but of course I don't). My guess is that many patients never think to mention some medications they are taking (or incorrectly remember names, which is fairly easy given the choice between an unpronounceable generic name and a brand name devoid of mnemonic value). There are also patients who partially self-medicate (borrowing unprescribed medications from friends or relatives, taking left over pills from long-expired prescriptions, or ordering cheap drugs over the Internet, from suppliers who couldn't spell "prescription", let alone recognize one).

Since drug manufacturers cannot possibly test all possible combinations of medications, to a large extent risky interactions have to be identified the hard way. As Samuelson states in the quote above, information technology (combined with data analysis) offers some hope there. If changes to the health care system lead to more thorough (and more accurate) record keeping, there is an opportunity for data analysis to ferret out potential problems, which can then be tested in laboratories. Better use of electronic record keeping will also help pharmacists detect when a customer is purchasing drugs that may interact in unfortunate ways, even if the purchases are being made at multiple pharmacies.

I think there is one more opportunity for "predictive analytics", though, and that is in identifying patients likely to be at greatest risk of an adverse interaction. Just as considerable effort is going into profiling likely terrorists, so that time and energy screening travelers or inspecting cargo can be focused where it will do the most good, we can think about profiling patients. If analytics allows us to identify patients at greatest risk, whether it be due to their errors or to errors by doctors or pharmacists, then perhaps either government or insurers can intervene (assign a case manager, warn pharmacists to ask extra questions, use a cell phone application to nag the patient, ...) and reduce the danger. Making intelligent, data-driven decisions to achieve the best possible outcome: sounds like OR to me.

Mixed Case Titles

2011-03-27T17:13:00.000-04:00

Writing pointless academic papers requires citing other pointless academic papers. Thus do academicians, in a symbiotic process eerily similar to those of lawyers and nuclear weapons manufacturers, keep each other in business. Since I write in LyX and generate the documents with LaTeX, it is unsurprising that I process bibliographies using BibTeX. My preferred tool for maintaining BibTeX databases is JabRef, which is cross-platform, has a decent feature set, and just plain works.

When I add references to by BibTeX databases, I'm careful to capitalize most of the words in the title. Anyone who has had the misfortune to deal with journals knows that every journal publisher employs at least one or two people with obsessive/compulsive disorder, who are tasked with ensuring that this journal formats various things (possibly tables or figure captions, but always, always references) in a way that visually distinguishes it from every other journal in the galaxy. Thus I have to find (or cobble together) a BibTeX style file specific to whatever journal makes the mistake of accepting of my paper. BibTeX style files can "downshift" titles to lower case, but as far as I know they do not "upshift" to what I'll call "title" case (nouns, verbs, adjectives, adverbs and initial articles capitalized, other articles and conjunctions not). So it behooves me to insert the reference into the database in "title" case.

On the other hand, I'm a firm believer in copying and pasting to avoid retyping. So I frequently copy article information from a web page or PDF file and paste it into JabRef. Small problem: as far as I know, JabRef does not have an editing feature to adjust cases. That led me to some searching, which in turn led me to discover that gedit (my primary editor on Linux) comes with a preinstalled plug-in to shift cases. Said plug-in can shift to lower, upper or (drumroll) "title" case. On Windows, NoteTab (including the free "Light" version) has a similar feature. If I recall correctly, NoteTab's converter is available with no configuration. In gedit, though, it needs to be turned on (Edit > Preferences > Plugins > Change Case), a revelation to which I have recently (and belatedly) come.

Semicontinuous Variables

2011-03-20T14:36:00.001-04:00

This question pops up from time to time on various forums. In a math programming model, how does one handle a variable that can either be zero or in some range not containing zero? The mathematical description of the variable would be something like $$x\in {0} \cup [a,b]$$where $a>0$. A couple of common applications in supply chain models include quantity discounts (a vendor offers a discounted price if you buy in bulk; $x$ is the amount purchased at the discounted price and $a$ is the minimum amount to qualify for the discount) and minimum lot sizes (where $x$ is the amount of a custom-made product obtained from a vendor who requires a minimum order of $a$ to justify the setup cost of the order).

The variable $x$ is known in math programming jargon as semicontinuous. For whatever reason, the term is not well publicized; I taught a graduate course on integer programming for years without coming across it. Some solvers can model these variables directly. For instance, the C++ and Java APIs for CPLEX contain a class named IloSemiContVar. I'm not sure which other solvers directly support semicontinuous variables. For solvers that do not recognize semicontinuous variables, there is a generic formulation. You introduce a binary variable $y$ that will be 1 if $x$ is nonzero and 0 if $x$ is zero, and you add the contraints $x\ge ay$ and $x\le by$.

AMPL allows you to define a semicontinuous variable without explicitly adding constraints. Our example could be written in AMPL as

param a > 0;
param b > a;
var x in {0} union interval[a, b];

Currently, AMPL converts that into the pair of constraints mentioned above, even if the chosen solver is CPLEX. Whether that will change in the future I do not know.

One potential virtue of directly modelling semicontinuous variables is that it may lead to a more parsimonious formulation. If the solver understands semicontinuous variables, it can modify the branching logic to separate nodes based on $x=0$ versus $x\ge a$ without having to add the binary variable $y$ and the extra constraints.

Forming Competitive Teams

2011-03-16T20:00:00.000-04:00

This post is motivated by the March INFORMS blog challenge: O.R. and Sports.

A couple or so years ago, someone contacted me about a model to assign children to sports teams. My correspondent volunteered for a youth recreation league in his home town. Two things are significant in that sentence. The first is "volunteered", which comes from the Latin phrase meaning "budget = zero". So whatever solution we came up with had to be cost-free. The second is "youth". In recreational sports leagues (at least for the youngest competitors), the tendency is for the parents to enroll their children in a league, rather than a specific team. The league then has to form rosters, and the goal is not to produce winners (which would imply losers as well), but to form teams that are as close to competitive parity as possible.

The approach taken by this league was to try to get the average (mean) value of various attributes as close to constant across teams as possible, subject to some constraints (minimum and maximum team sizes, for instance). For qualitative attributes, such as gender, we can treat this as averaging indicator variables (1=girl, 0=boy or 1=experienced, 0=inexperienced). So far, this looks like a modified version of the Hitchcock (transportation) problem, with kids as unit-supply "sources" and teams as "sinks". The modifications include some additional constraints (a utilized "sink" has to contain at least enough players to field a full team) and a rather funky (and, as it turns out, nonlinear) objective function. The nonlinearity occurs because attribute averages involve dividing by team size, which is not constant.

Anyone who has designed a model for a real-world (not textbook) problem is probably painfully aware that the problem you are initially asked to model winds up not being the problem you actually have to model. Sure enough, additional wrinkles creep in. Parents with twins want/need to have the kids on the same team (to avoid car-pool nightmares). Some kids may need to be separated (to avoid fights). Some kids have parents who volunteer (that word again) to be assistant coaches, but only for the team their kid is on; there are not enough assistant coaches to go around, so we really don't want two on the same team, which means separating the kids with volunteer parents. And so on.

I won't go into mind-numbing details (I'll save that for students that can't outrun me :-)), but the code I ended up writing (called Parity Builder) is available open-source. All it requires for infrastructure is Sun Java (1.6 or higher), and it comes with a tutorial.

One last point, which I find interesting. One of my colleagues in organizational behaviour (the "OB world" in the blog title) pointed me to some literature alleging that competitive performance may depend more on the within-team variance of certain attributes than the mean. If true (and if it applies to any of the attributes used by the recreational league), perhaps the approach we took does not really optimize balance. On the other hand, it almost surely optimizes the appearance of balance, and the true objective function was probably "minimize parental bitching". So maybe we're good after all.

Random Sampling in AMPL

2011-03-13T18:15:00.000-04:00

This came up on the AMPL user group; I figured I'd "double dip" and post an edited version of my solution here. The question was how to randomly sample without replacement in AMPL. The code below shows one way.

#
# randomly sample items from a set, with or without replacement
#
set UNIVERSE ordered;  # set of items to sample -- must be ordered
param ssize integer > 0;  # sample size desired
param sample {1..ssize} symbolic;  # will hold generated sample

data; # data below is just for demonstration purposes
set UNIVERSE := 'cat', 'dog', 'bird', 'fish', 'turtle', 'snake', 'frog', 'rock';
param ssize := 4;
model;  # back to the code

let ssize := min(ssize, card(UNIVERSE));  # omit if sampling with replacement
param item symbolic;  # dummy parameter to hold each selection
for {i in 1..ssize} {
  let item := member(ceil(Uniform(0, card(UNIVERSE))), UNIVERSE);
  let sample[i] := item;
  let UNIVERSE := UNIVERSE diff {item};  # omit if sampling with replacement
}

display sample;

I might mention a few things about the code:

I used symbolic data in the example. If you are sampling from a set of numbers, you can omit the two instances of the keyword symbolic.
If you want to sample with replacement, there are two lines (marked by comments) that you need to omit.
The code puts the sample in a (vector) parameter. If you are sampling without replacement, an alternative is to put the code into a set. Define the set with a default value of {}, and use the union operator with second argument {item} to add the item to the sample set inside the loop.

Configuring R for Java

2011-03-10T12:23:00.000-05:00

I have two R packages that have consistently refused to be updated: rgl (which I believe is used for 3D visualization) and rJava (an API for accessing Java from R). I probably don't really need either one, but at least one R GUI (JGR), needs rJava. I must have figured out (and then forgotten) the configuration magic that allows rJava to update, because the update.packages() command on my office PC (Linux Mint) has not problem with it ... but update.packages() on my laptop (also Linux Mint) kept running into an error.

So here is the solution (which I found here), just in case I need it again.

Run sudo update-alternatives --config java (in a terminal) and pick Sun Java as the default. (I thought I'd already done that, but apparently not.)
Add export JAVA_HOME=/usr/lib/jvm/java-6-openjdk/jre to .bashrc (again, thought I'd done that but hadn't).
Run sudo R CMD javareconf in a terminal. (That I had done -- multiple times, with no error messages -- but apparently with the wrong configuration in place.)
Run R as root and update the package.

I hope that, the next time this comes up, I at least remember I put the necessary steps here.

Honey, I Shrank the Registry!

2011-03-09T16:12:00.000-05:00

I have one rather superannuated PC running Windows XP, which I refuse to upgrade to Win 7 for various reasons (not least being that I suspect it would run at the speed of glacial drift, if at all). Lately, it's been complaining at boot that the system registry is too large, and that future requests for registry space will be denied (and the offending programs no doubt will be executed).

So I did a little searching and found a pair of free programs by a programmer in Germany named Lars Hederer: ERUNT and NTREGOPT. The former backs up and restores the registry (not a bad idea when you plan to perform surgery on it), while the latter compresses it. In my case, NTREGOPT reduced the registry size by 75% (!!), from around a quarter GB to something in the 70 MB range.

Hmm ... wonder if it could reduce my size (weight please; advancing age is already attacking my height) (and preferably not 75%).

A Vote for VIFs

2011-03-08T18:17:00.000-05:00

Shown below is output from a linear multiple regression model run in Minitab:

Predictor   Coef SE Coef     T     P
Constant  2.4765  0.7055  3.51 0.001
DIAMETER -0.7880  0.1826 -4.31 0.000
WEIGHT   0.44314 0.03633 12.20 0.000

Other statistics programs I've used, or whose output I've seen, may format things differently, but they generally stick to the same fundamental ingredients: the estimated coefficient value; the standard error of that coefficient; the T-ratio; and the p-value of that ratio. Note that there is a certain redundancy here. If I know any two of the first three items, I can figure out the third rather easily. If I know the T-ratio (and the degrees of freedom), I can get the p-value. (Going the other direction is subject to accuracy problems, since small p-values tend to be truncated).

Redundancy is not really the issue, though. What do we care about in that output? Certainly we want the coefficient, and quite possibly we want the standard error (if we are going to hand compute confidence intervals, for instance). If we care about statistical significance (and we generally should), we want to see the p-value. Since the sole reason for computing the T-ratio is to get to the p-value, I consider it a waste of space. I suspect it is a holdover from bygone days when software did not compute p-values, and users had to look up the T-ratio in tables.

Meanwhile, there is something missing from the standard output that I think really should be there: the variance inflation factors (VIFs). VIFs give you a quick diagnostic check of whether you need be concerned about multicollinearity. In a doctoral seminar on regression that I've taught in recent years, we read papers from the business and social science literature in which regression models are presented (and used to test hypotheses). The vast majority of these papers contain no indication that the authors checked for multicollinearity. In a few cases, the authors state that because the correlation matrix of the predictors exhibits no large pairwise correlations, multicollinearity is not a concern. This sense of security is entirely unfounded when there are more than two predictors, as multicollinearity can occur without any large pairwise correlations.

Perhaps if we saw VIFs every time we ran a multiple regression, we would get in the habit of spot-checking for multicollinearity. Most software will produce VIFs, but you may have to dig to find out how to get them. (In R, for instance, I have to load the "car" library to find a VIF function.) If software vendors are concerned about real estate on the screen/page, I nominate the T-ratio column as something we can sacrifice to make room for VIFs.

Syntax Highlighting

2011-03-06T16:56:00.003-05:00

I just burned about an hour of my life going back and retrofitting syntax highlighting to some of my old posts. The fault lies entirely with Bo Jensen, who first suggested it. Some of the code to be highlighted (including what triggered the suggestion) is in R, some in Java, a bit in Bash. (Thank goodness I got over APL decades ago; that would be a font nightmare.) Obviously, for blogging purposes, I need a highlighter that generates HTML, not just a syntax highlighting code editor. Given my rather modest output rate, an online highlighter would be just fine (no need to install it locally). Finally, and this turns out to disqualify several of the available R highlighters, I like having function names highlighted, not just keywords.

So I scrounged around the 'Net a bit and found two very useful sites:

Quick Highlighter, which handles most of my needs other than R; and
Pretty R, which does a great job highlighting R code.

Thanks to both sites for making my life easier.

One side note: This morning, by sheer coincidence, I received a couple of tweets from Hakan Kjellerstrand indicating that he was experimenting with a GPL version of the J programming language. Curious, I took a look at some code samples on the Jsoftware site and started having flashbacks to APL. While perusing the Wikipedia page for APL (linked above), I discovered that the flashback was not just random: Kenneth Iverson, the designer of APL, was also a designer of J.

I need to stare at some FORTRAN for a while to clear my head.

Update (9 March 2011): It's official -- I'm stupid. On my Windows box, I've been using Notepad++ for some time now (not so much for programming as for general editing of text files). As it turns out, Notepad++ does syntax highlighting for a variety of languages, including both R and Java, and can export to an HTML file.

Fine, but I do most of work on Linux Mint these days, and Notepad++ is a Windows-only program. It's based on Scintilla, though, as is SciTE, which I use for similar purposes on my Mint PC and laptop. (SciTE is also available for Windows, but I'm already using NP++ and, as we say here, if it ain't broke, don't fix it.) SciTE does Java highlighting out of the box, and with a small tweak, it does R syntax highlighting. It also exports to HTML. (The tweak: run SciTE via sudo, open the global options file, scroll down near the bottom and uncomment "import r", then save.)

So I'm set for highlighting with tools I'm already using.

Update (13 March 2011): I discovered a Linux command line utility named (shockingly) highlight. It converts code files in a variety of languages (including AMPL, which I needed today, but sadly not including R) to a variety of output formats (notably HTML, but also LaTeX). The utility is available from the Ubuntu universe repository, so you can load it via Synaptic without having to add a new source.

Of course, life can't be quite that simple. The executable is installed as /usr/bin/highlight. I already have a program of the same name at /usr/local/bin/highlight. I don't know where it came from or what it does, but it seems to expect input from stdin regardless of any command line switches. Since it's in the local bin directory, it loads ahead of the one I want (grrr). Not knowing whether it's part of a larger package, I'm reluctant to nuke it. So I've added alias highlight=/usr/bin/highlight to my .bashrc file, which gives me a safe (I think) workaround.

Math and Science Can Be Sexy

2011-03-01T13:32:00.000-05:00

I just tripped over the following facts (one of which I already knew):

Hedy Lamarr, vintage Hollywood hottie, co-invented frequency hopping, used by cell phones today.
Danica McKellar, teen age TV star (and successful actress since), is co-author of the Chayes–McKellar–Winn theorem (as an undergraduate math major). (This one I knew.)
Mayim Bialik, who as a teen had the title role in the TV series "Blossom" and now plays a neurobiologist on "The Big Bang Theory", actually has a Ph.D. in neurobiology.

Now we just need some sexy male mathematicians and scientists (besides me, that is) to balance the list.

Stepwise Regression in R

2011-02-27T19:06:00.003-05:00

Let me start with a disclaimer: I am not an advocate of stepwise regression. I teach it in a doctoral seminar (because it's in the book, and because the students may encounter it reading papers), but I try to point out to them some of its limitations. If you want to read some interesting discussions on the issues with stepwise, search the USENET group sci.stat.math for references to stepwise. (If you are a proponent of stepwise, I suggest that you don flame retardant underwear first.)

Since I teach stepwise in my seminar, I would like to demonstrate it in R (not to mention some of my students are learning R while doing their homework, which includes a stepwise problem). The catch is that R seems to lack any library routines to do stepwise as it is normally taught. There is a function (leaps::regsubsets) that does both best subsets regression and a form of stepwise regression, but it uses AIC or BIC to select models. That's fine for best subsets, but stepwise (at least as I've seen it in every book or paper where I've encountered it) uses nested model F tests to make decisions. Again, if you search around, you can find some (fairly old) posts on help forums by people searching (fruitlessly, it appears) for a stepwise implementation in R.

So I finally forced myself to write a stepwise function for R. My knowledge of R coding is very, very limited, so I made no attempt to tack on very many bells and whistles, let alone make it a library package. Unlike most R routines, it does not create an object; it just merrily writes to the standard output stream. There are a number of limitations (expressed in the comments), and I've only tested it on a few data sets. All that said, I'm going to post it below, in case someone else is desperate to do conventional stepwise regression in R.

=== code follows ===

    #
    # This is an R function to perform stepwise regression based on a "nested model" F test for inclusion/exclusion
    # of a predictor.  To keep it simple, I made no provision for forcing certain variables to be included in
    # all models, did not allow for specification of a data frame, and skipped some consistency checks (such as whether
    # the initial model is a subset of the full model).
    #
    # One other note: since the code uses R's drop1 and add1 functions, it respects hierarchy in models. That is,
    # regardless of p values, it will not attempt to drop a term while retaining a higher order interaction
    # involving that term, nor will it add an interaction term if the lower order components are not all present.
    # (You can of course defeat this by putting interactions into new variables and feeding it what looks like
    # a first-order model.)
    #
    # Consider this to be "beta" code (and feel free to improve it).  I've done very limited testing on it.
    #
    # Author: Paul A. Rubin (rubin@msu.edu)
    #
    stepwise <- function(full.model, initial.model, alpha.to.enter, alpha.to.leave) {
      # full.model is the model containing all possible terms
      # initial.model is the first model to consider
      # alpha.to.enter is the significance level above which a variable may enter the model
      # alpha.to.leave is the significance level below which a variable may be deleted from the model
      # (Useful things for someone to add: specification of a data frame; a list of variables that must be included)
      full <- lm(full.model);  # fit the full model
      msef <- (summary(full)$sigma)^2;  # MSE of full model
      n <- length(full$residuals);  # sample size
      allvars <- attr(full$terms, "predvars");  # this gets a list of all predictor variables
      current <- lm(initial.model);  # this is the current model
      while (TRUE) {  # process each model until we break out of the loop
        temp <- summary(current);  # summary output for the current model
        rnames <- rownames(temp$coefficients);  # list of terms in the current model
        print(temp$coefficients);  # write the model description
        p <- dim(temp$coefficients)[1];  # current model's size
        mse <- (temp$sigma)^2;  # MSE for current model
        cp <- (n-p)*mse/msef - (n-2*p);  # Mallow's cp
        fit <- sprintf("\nS = %f, R-sq = %f, R-sq(adj) = %f, C-p = %f",
                       temp$sigma, temp$r.squared, temp$adj.r.squared, cp);
        write(fit, file="");  # show the fit
        write("=====", file="");  # print a separator
        if (p > 1) {  # don't try to drop a term if only one is left
          d <- drop1(current, test="F");  # looks for significance of terms based on F tests
          pmax <- max(d[-1,6]);  # maximum p-value of any term (have to skip the intercept to avoid an NA value)
          if (pmax > alpha.to.leave) {
            # we have a candidate for deletion
            var <- rownames(d)[d[,6] == pmax];  # name of variable to delete
            if (length(var) > 1) {
              # if an intercept is present, it will be the first name in the list
              # there also could be ties for worst p-value
              # taking the second entry if there is more than one is a safe solution to both issues
              var <- var[2];
            }
            write(paste("--- Dropping", var, "\n"), file="");  # print out the variable to be dropped
            f <- formula(current);  # current formula
            f <- as.formula(paste(f[2], "~", paste(f[3], var, sep=" - ")));  # modify the formula to drop the chosen variable (by subtracting it)
            current <- lm(f);  # fit the modified model
            next;  # return to the top of the loop
          }
        }
        # if we get here, we failed to drop a term; try adding one
        # note: add1 throws an error if nothing can be added (current == full), which we trap with tryCatch
        a <- tryCatch(add1(current, scope=full, test="F"), error=function(e) NULL);  # looks for significance of possible additions based on F tests
        if (is.null(a)) {
          break;  # there are no unused variables (or something went splat), so we bail out
        }
        pmin <- min(a[-1,6]);  # minimum p-value of any term (skipping the intercept again)
        if (pmin < alpha.to.enter) {
          # we have a candidate for addition to the model
          var <- rownames(a)[a[,6] == pmin];  # name of variable to add
          if (length(var) > 1) {
            # same issue with ties, intercept as above
            var <- var[2];
          }
          write(paste("+++ Adding", var, "\n"), file="");  # print the variable being added
          f <- formula(current);  # current formula
          f <- as.formula(paste(f[2], "~", paste(f[3], var, sep=" + ")));  # modify the formula to add the chosen variable
          current <- lm(f);  # fit the modified model
          next;  # return to the top of the loop
        }
        # if we get here, we failed to make any changes to the model; time to punt
        break;
      } 
    }

Created by Pretty R at inside-R.org

Finding Multiple Solutions in a Binary MIP

2011-02-26T12:46:00.001-05:00

I'm going to post some AMPL code here that illustrates how to find more than one solution to a mixed integer program in which all integer variables are binary. The problem I'll use is a multiple knapsack where the supply of each item is one. The AMPL code should be pretty self-explanatory, with the possible exception of the exclusion constraints. The notion for those is as follows. Suppose that my binary variables are $x\in \{0,1\}^d$. I solve the original model and obtain a solution with $x=\tilde{x}$. I now add the following constraint:$$\sum_{i : \tilde{x}_i = 0} x_i + \sum_{i : \tilde{x}_i =1}(1-x_i)\ge 1.$$Note that this constraint forces at least one of the binary variables to change its value. (Exclusion constraints for general integer variables are harder to come by. The only way I know off-hand involves binary expansions of the general integer variables.)

The AMPL code solves the model in a loop, recording each solution and adding an exclusion constraint. The small example I created happens by chance to have multiple optimal solutions, enough so that the five solutions generated by the code are all optimal (but distinct). More generally, you could get a sequence of increasingly suboptimal solutions.

Three things are perhaps noteworthy in the code. The first is the check for infeasibility: if you've already enumerated all possible solutions (and excluded them), the model will become infeasible. The second is that I gave default values for the exclusion constraint coefficients (and right hand sides). AMPL otherwise solved the base model (with no exclusion constraints) but then nagged me when I tried to record the result, because the first exclusion constraint used undefined coefficients. Apparently recording the result (or even trying to display it) triggered a reevaluation of the model. I think I could have ducked that by waiting to update nfound, but default values were an easy fix. Third, note that I did not check whether a binary variable equaled 0 or 1; that might bump into rounding issues. Saying that anything above (below) 0.5 is a 1 (0) is a very safe test. (If your rounding error is that bad, you need to clean the beads on your abacus.)

One last comment is that this is not the most efficient way to find multiple solutions, in that it requires the (expanded) model to be solved ab initio each time. If the solver supports callbacks, a more efficient approach is to use callbacks to record incumbents, reject them, and add exclusion constraints on the fly. CPLEX has a "solution pool" feature that lets you track multiple solutions (and if CPLEX has it, my guess is that other commercial solvers do or soon will). Using that is probably even more efficient than using callbacks. If the model is easy enough to solve, though, or if your solver lacks those features, the method demonstrated below may be a good choice.

Here is the code:

# Example of how to generate and record multiple solutions to a binary MIP.
#
# The sample problem is a 0-1 multiple knapsack.
#
set ITEMS;  # items available for the knapsacks
set KNAPSACKS;  # available knapsacks
param value {ITEMS} > 0;  # item values
param size {ITEMS} > 0;  # item sizes
param capacity {KNAPSACKS} > 0;  # knapsack capacities
var Pack {ITEMS, KNAPSACKS} binary;
  # Pack[i,k] = 1 iff item i is packed in knapsack k
maximize LoadValue: sum {i in ITEMS, k in KNAPSACKS} value[i]*Pack[i,k];
  # maximize value of load
s.t. Capacity {k in KNAPSACKS}:
  sum {i in ITEMS} size[i]*Pack[i,k]  <= capacity[k];  # capacity limits
s.t. Supply {i in ITEMS}:
  sum {k in KNAPSACKS} Pack[i,k]  <= 1;  # only one of each item available

option solver cplexamp;  # to use CPLEX as the solver

data;  # ordinarily I'd use a separate file for the data
set ITEMS := 1 2 3 4 5 6 7 8 9;
set KNAPSACKS := 1 2;
param capacity := 1 6 2 4;
param:  value  size  :=
   1       6     3
   2       5     2
   3       4     4
   4       3     1
   5       2     1
   6       4     5
   7       7     6
   8       2     3
   9       1     1  ;

model;

# we now create some structure to record multiple solutions
param want := 5;  # number of solutions we want
set SOLUTIONS := 1..want;  # index set for solutions
param packed {ITEMS, KNAPSACKS, SOLUTIONS};
  # packed[i,k,s] will be 1 if solution s packed item i in knapsack k
param payoff {SOLUTIONS};  # objective values of recorded solutions
param coef {ITEMS, KNAPSACKS, SOLUTIONS} default 0;
  # coefficients of solution exclusion constraints
param rhs {SOLUTIONS} default 0;  # right hand sides of exclusion constraints
param nfound default 0;  # number of solutions found

# we add constraints to the previous model to exclude
# solutions we've already seen
s.t. Exclude {s in 1..nfound}:
  sum {i in ITEMS, k in KNAPSACKS} coef[i,k,s]*Pack[i,k] >= rhs[s];

# solve until either the problem becomes infeasible or
# the right number of solutions has been found
for {s in SOLUTIONS} {
  solve;  # solve the model
  if solve_result = 'infeasible' then break;
    # if the model has become infeasible, give up
  let nfound := s;  # bump the counter for solutions found
  let payoff[s] := LoadValue.val;
  let rhs[s] := 1;
  # create an exclusion constraint that forces at least
  # one binary variable to change value
  for {i in ITEMS, k in KNAPSACKS} {
    if Pack[i,k] > 0.5 then {
      # treat this as a 1
      let packed[i,k,s] := 1;
      let coef[i,k,s] := -1;
      let rhs[s] := rhs[s] - 1;
    }
    else {
      # treat this as a 0
      let packed[i,k,s] := 0;
      let coef[i,k,s] := 1;
    }
  }
}

An R Resource

2011-02-15T11:04:00.000-05:00

Catching up on some backlogged blog reading, I came across several interesting posts about R on John D. Cook's blog (The Endeavor). Happily, there is an index of all R-related posts there, so I can record one link here (where I'm unlikely to lose it) and catch any new posts with it. There's a ton of information to ~~mined~~ acquired from those posts. (I didn't want to get the data-mining crowd whipped into a frenzy, hence the edit). Among other things, I learned why S (and R by inheritance) has the convention of using a dot to create compound variable names (apparently underscore is an assignment operator in S). That's one less itch to scratch.

On the same blog, there is also an interesting (and interactive) diagram of the relationships among various distributions. This could be quite useful in a probability and statistics course.

Bounding Dual Variables

2011-02-08T11:41:00.001-05:00

An interesting question came up on sci.op-research today: can we (easily) determine bounds for the variables in the dual of an linear program? If the goal is tight bounds, I don't see any easy solution; but it turns out that, at least in some problems, there may be finite (reasonable?) bounds to be had cheaply.

Let's start with a primal problem in canonical form (alternative forms are left to the reader as an exercise):\[\begin{array}{lrclr}\textrm{minimize} & c'x\\\textrm{s.t.} & Ax & \ge & b & \textrm{(P)}\\ & x & \ge & 0\end{array}\] with dual\[\begin{array}{lrclr}\textrm{maximize} & b'y\\\textrm{s.t.} & A'y & \le & c & \textrm{(D)}\\ & y & \ge & 0\end{array}.\]To get an upper bound on dual variable $y_j$, we could solve a modified form of the dual problem:\[\begin{array}{lrclr}\textrm{maximize} & y_j\\\textrm{s.t.} & A'y & \le & c & \textrm{(D*)}\\ & y & \ge & 0\end{array}.\]This looks for the largest value of $y_j$ (which we hope is finite) consistent with the dual constraints. The dual to this problem is:\[\begin{array}{lrclr}\textrm{minimize} & c'x\\\textrm{s.t.} & Ax & \ge & e_j & \textrm{(P*)}\\ & x & \ge & 0\end{array}\]where $e_j$ is a vector whose $j$-th component is 1 and whose other components are all 0.

Now suppose we know a primal vector $\tilde{x}\ge 0$ for (P) such that $A\tilde{x}=h\gg 0$, where $h\gg 0$ means that $h$ is strictly positive in every component. Let $x^*=(1/h_j)\tilde{x}$. Then $x^*$ is feasible in (P*), which means $c'x^*$ is an upper bound for the optimal value of (P*), and therefore also an upper bound for the optimal value of (D*). So we can safely assert $y_j\le c'x^*$ in (D).

If $b\gg 0$, then any feasible solution to (P) is a candidate value of $\tilde{x}$, and the closer $\tilde{x}$ is to optimal, the tighter the bound on $y_j$. Also note that a single $\tilde{x}$ provides bounds for all of the dual variables $y_j$. So the trick is to know a vector $x\ge 0$ for which $Ax\gg 0$.

Twitter and Firefox

2011-02-05T14:50:00.001-05:00

In the beginning, I completely ignored Twitter. Recently, I started following a few Twitter feeds (from OR people) in Google Reader, mainly because they tended to post links to things I actually found interesting (i.e., not what the tweeter had for lunch, nor where said lunch occurred). Finally, I bit the bullet and opened a Twitter account, largely so that I could respond to the occasional provocative tweet. (I think I'm up to three tweets so far, which should hold me for a while.)

The next step was to look for an extension to either Thunderbird or Firefox (both of which I keep open when being abused by a computer), so that I could tweet, retweet or ___ (is there a term for responding to a tweet? tweeply?) easily. Of course, I could just open Twitter in a Firefox tab, but that would be too low tech, right? I found one Tbird extension, but it was an alpha version. I found several promising looking Firefox extensions, of which the most complete and polished seemed to be Echofon. So yesterday I installed in on my office PC (Linux Mint Isadora), where it worked well, and this morning I installed it on my home PC (Win XP), where it also worked well.

Unfortunately, in between I installed it on my laptop (also Mint Isadora), where it proceeded to spew authentication errors in an alarmingly OCD way. In fact, short of killing Firefox from a terminal, the only way I could stop the error messages (which popped up an average of about two seconds apart) was to turn off my WiFi connection. (I couldn't log out of Twitter, nor exit Firefox gracefully, because the incessant error dialogs were modal.)

Fortunately, I could diff my settings between the laptop and the (working) office PC. It turns out there was a conflict with another Firefox extension, the Electronic Frontier Foundation's HTTPS-Everywhere. This extension automatically converts insecure HTTP connections to many sites to secure HTTPS connections. I installed it on my laptop (which likes to go out for a cup of coffee pretty often) but not my office PC (which hides behind a firewall) (although I may eventually install it there as well). It works fine with Twitter when I surf to my Twitter account, but apparently it does not get along at all well with Echofon. Fortunately, HTTPS-Everywhere allows you to configure which sites it will try to seduce into secure connections; by deselecting Twitter.com, I got Echofon to work properly (if perhaps not entirely securely).

Binary Exclusive Or

2011-02-01T18:19:00.001-05:00

Lately I've been playing with a mixed integer programming model that involves Hamming distances between binary vectors. This involves what amounts to computing the exclusive or between two binary variables. In a previous post I made a comment about exclusive or being somewhat tricky to implement, but that was in reference to general linear constraints -- requiring that exactly one of two possible linear equalities/inequalities be satisfied. Fortunately, an exclusive or between to binary variables is easy.

Let $x$ and $y$ be two binary variables, and let $z=x\oplus y$ be the exclusive disjunction of $x$ and $y$, also declared as a binary variable. The truth table is as follows:

$x$	$y$	$z=x\oplus y$
0	0	0
0	1	1
1	0	1
1	1	0

We accomplish this with the following inequalities:\begin{eqnarray*}z\le x + y\\z\le 2 - x - y\\ z\ge x - y\\z \ge y-x.\end{eqnarray*} Verification that this works is left to the reader as an exercise.

The Diogenes Problem

2011-01-30T11:15:00.000-05:00

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?

OR v. CYA

2011-01-22T17:59:00.001-05:00

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.)

Home Field Advantage

2011-01-19T21:18:00.000-05:00

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.

Numberjack

2011-01-13T10:44:00.000-05:00

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."

Physiology and Mathematics Education

2011-01-09T17:40:00.000-05:00

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.

Max and Min Functions in a MIP

2011-01-07T18:57:00.001-05:00

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$.

Credit Card Rebates

2010-12-26T10:59:00.000-05:00

Periodically I see questions or comments about how we use operations research in our personal lives. The truth, of course, is that for the most part we don't. We may use the systematic analysis and critical thinking inherent in OR, but generally we neither need nor bother with the mathematical models. (As an example of the "critical thinking", consider the ads you see on TV for insurance companies, touting that "customers who switched to <insert company name> saved an average of <insert large positive amount> on their premiums". A typical viewer may think "wow, they're pretty cheap". An OR person thinks "no kidding -- people with negative savings didn't switch, so the data is censored".) Recently, however, I actually found an application for an OR model in my personal life.

In the aftermath of the "Financial Debacle of 2008" (or the "Great Recession", or whatever you prefer to call it), banks are scrambling to make money. Thus, among other things, credit card rebate programs have become more byzantine. Once upon a time, my Chase credit card earned rebates that were simply posted monthly, automatically and in the full amount I'd earned. Couldn't have been simpler. Didn't last.

I now "enjoy" the benefits of the Chase Ultimate Rewards program. Rebates are no longer credited automatically; I have to log in each month and claim them. There can be delays in how quickly they post. Rebate balances below $20 cannot be redeemed (they carry over to the following month). I have options for claiming the rewards, including buying things I don't need through Chase (probably at higher than market prices) or asking them to cut me a check (then waiting for it to arrive, then depositing it somewhere). The most convenient (or should I say least inconvenient?) way to redeem them may be what Chase calls the "pay yourself back" option, in which you apply the rebate to purchases made within the past 60 days. The amount redeemed shows up as a credit on your next statement.

Besides the delay in receiving the credit, there are other minor hassles with the "pay yourself back approach". You cannot pay yourself back for part of a purchase; you must have sufficient rebate credit accumulated to pay back the entire amount. The web form only allows you to pay back one purchase at a time, and the $20 minimum limit applies to each individual redemption, not to the combined set of redemptions. Most of the time, this is a non-issue for me, since it usually takes me more than one billing cycle to accrue a rebate balance above $20, at which point I immediately repay myself for a recent $20+ purchase and drop the remaining balance back below $20, to sit for another cycle or two.

Occasionally, however, some combination of unusual expenditures gets me a larger balance. The trick then is to find a collection of purchases within the past 60 days, each $20 or more, whose combined total comes closest to my available rebate balance without exceeding it. That's probably trial-and-error for most people, but readers of this blog may recognize the problem as a binary knapsack, where the value and "size" of an item are both the amount charged, the constraint limit is the available rebate balance, and only recent purchases of $20 or more make it into the model. So I now have a spreadsheet containing just that model, which I'll probably need once or perhaps twice a year.

OR in an OB World

OR and Base Voters: Common Pitfalls

Java Plugin for Firefox 10

The Case of the Dormant Function Keys

Slaying a Zombie Browser Extension

OR in Restaurants

The Most Desperately Needed Degree Program

Donating a Computer? Wipe the Drive!

Max/Min Bounds

Resolutions, Seasonality and Transient Effects

Launching Windows Apps with Wine

Extracting Variables in CPLEX

Indexing an Array with a Variable

Charlotte's Literary Park

Android-Linux File Transfers

Back to Back Conferences

Blogging at INFORMS 2011

Mint/Ubuntu Update Broke Printing

Scalable Images in Blogger

Time Series, Causality and Renting a Congressman

Benders Decomposition Then and Now

OR, the Environment, and the Law of Unintended Consequences

Fixing TiKZ/PGF to Work with Gnuplot

Fixing CUPS-PDF

Comment Spam

Piecewise-linear Functions Redux

The Heisenberg Budget Principle

Spontaneous Reboots

Q&A Sites for Engineers

Tab Completion Bug in Mint 11

A GNOME Panel Hack

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

Princeton Consultants Is Hiring

USENET: A Remembrance

Social Networks at Work

Farkas Certificates in CPLEX

The Continuing Adventure of Mint 11

Facts, Beliefs ... and Budgets

Perils of "Big M"

Terminology

Rounding error

$M$ in the objective or RHS

$M$ in the constraints

$M$ in MIP models

$M$ and (dubious) pedagogy

Concluding thoughts...

Hitting the Muggles from All Sides

Top Down

Bottom Up

Sideways

Do Gremlins Find Mint Tasty?

Tweaking Mint Settings

Upgrading Linux Mint

Peeking Inside the Black Box

Stepwise Regression in R: Part II

A Shoutout to Anki

My Infinity Is Bigger Than Your Infinity

Rejiggering an R Data Frame

Will Analytics Drag O.R. Back to Its Roots?

An Unbalanced Round Robin Bridge Schedule

Data Mining and Pharmaceutical Bar Tending

Mixed Case Titles

Semicontinuous Variables

Forming Competitive Teams

Random Sampling in AMPL

Configuring R for Java

Honey, I Shrank the Registry!

A Vote for VIFs

Syntax Highlighting

Math and Science Can Be Sexy

Stepwise Regression in R

Finding Multiple Solutions in a Binary MIP

An R Resource

Bounding Dual Variables

Twitter and Firefox

More Presentation Software

Binary Exclusive Or

The Diogenes Problem

OR v. CYA

Home Field Advantage