An Unbalanced Round Robin Bridge Schedule

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

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.