Category: Books

The Golden Ticket

The Golden Ticket

I picked up Lance Fortnow’s new book The Golden Ticket: P, NP and the Search for the Impossible.  Lance is chair of the School of Computer Science at my alma mater Georgia Tech (I got my PhD there in Industrial Engineering) and the co-author of the excellent Computational Complexity blog.

The title of the book comes from the Willy Wonka story of finding a golden ticket that allows passage into a chocolate factory and a lifetime supply of candy.  But golden tickets are rare:  how can one find one?  Can finding golden tickets be done fast?  The difficulty of finding rare items in a sea of possibilities is at the heart of the P=NP issue.

After a brief introduction to the sort of problems that are in NP (problems whose solution can be checked quickly, with some being in P, problems whose solution can be found quickly), Lance moves on to an extended fantasy of what would happen if a proof of P=NP (in other words: problems whose solutions can be checked quickly can also have their solutions found quickly) were to be discovered.  An initial proof leads to inefficient (but polynomial) codes which are used to improve on themselves culminating in the “Urbana algorithm”  (I bet it would be the “Carnegie Algorithm”, but this is Lance’s story):

… 42 million lines of unintelligible code.  And it solved NP problems fast, very fast. [without becoming self-aware.  No Skynet in this book.]

Lance then explores the effect of the Urbana algorithm.    Some of his predictions seem a bit far-fetched.  I don’t think the difficulty in predicting snow storms a year in advance (as he suggests will happen) is an issue of algorithm speed, but rather limits on data availability and modeling limits, but, again, this is Lance’s fantasy so I really shouldn’t quibble.

One of Lance’s stories has a father and daughter going to a baseball game, and the father muses on the effect the Urbana algorithm has had on baseball:

First, of course, is the schedule of this particular game.  As late as 2004, a husband-and-wife team, Henry and Holly Stephenson, scheduled games for Major League Baseball.  They used a few simple rules, like the number of games played at home and away by each team, and some local quirks, like the Boston Red Sox like to host a daytime baseball game on Patriot’s Day in mid-April, as the runners in the Boston Marathon pass nearby [a story that takes on a whole different flavor now].  In 2005, Major League Baseball contracted with a Pittsburgh company, the Sports Scheduling Group, because its scheduling could better avoid teams playing each other in consecutive weeks.

Hey, that’s me!  I made it into Lance’s book!  Well, me and my colleagues at the Sports Scheduling Group.  Lance goes on to say a few more words about the effect of the Urbana algorithm on scheduling:

So the baseball czars want to schedule games in a way that everyone has the best possible weather and good teams play each other at the end of the season, not to mention more mundane cost savings like reducing the amount of travel for each team.  Handling all these issues and the multitude of possible schedules would have been impossible a mere fifteen years ago [the story is based in 2026], but the Urban algorithm spits out the best schedule in  a matter of minutes.

If I were to continue the story, I would include something Lance did not:  the Sports Scheduling Group would likely have gone out of business shortly after the release of the Urbana algorithm.  While part of our skill is understanding sports leagues, a big part of our competitive advantage is that we can solve sports scheduling problems pretty darn quickly, despite the fact they are all NP-complete (the hardest of the NP problems).  In short, while a proof of P=NP might be a golden ticket for some, our golden ticket is is the difficulty caused by P <> NP.  In Warren Buffet’s terms, computational complexity is our business’s moat, preventing others from following too easily.

So far, I love the book (and not just because of the shout-out!).  It is a book on a technical subject aimed at a general audience.  I’m only partway through (I am kinda stuck on showing the baseball story to those around me), but Lance’s mix of technical accuracy with evocative story telling works for me so far.

 

A Love Letter to the Traveling Salesman Problem

Bill Cook of Georgia Tech has a new book out on the Traveling Salesman Problem entitled “In Pursuit of the Traveling Salesman” from Princeton University Press (or from Amazon or B&N).  Unlike his previous book (with David Applegate, Bob Bixby and Vašek Chvátal), this book is aimed at a general audience. Bill takes his readers down a beautiful path covering the history, applications, and algorithms associated with the TSP. It is a fascinating story, and one that shows a researcher who truly loves his research area. You would think such a love was  common among researchers, but I have seen many researchers who seem bored by, or positively hate, their research areas. Bill is obviously enraptured by the TSP.

The Traveling Salesman Problem is remarkable easy to state:  given a set of points with distances between them, find the shortest tour through all the points.  For example, as Bill wrote about recently, given 99 towns in Iowa to visit and the road distances between every pair, what is the quickest way to see all the cities, returning to your starting position?

Despite its simple statement, the problem of finding good or optimal tours has generated thousands of research papers.  The TSP is the standard testbed for discrete optimization:  practically every possible approach to optimization can be tried out on the TSP.  So research on the TSP has had a tremendous effect on approaches for all sorts of other optimization problems.  Bill covers every aspect of this research corpus.

Perhaps the most interesting part about this book is that Bill pulls no punches when it comes to presenting work. Most of us would be tempted to go only so deep into an area and then start hand-waving believing “well, no one would understand this area anyway”. Here is how Bill begins a description of finding comb inequalities, a type of constraint necessary to determine the TSP polytope:

Subtour-elimination constraints? No problem. Comb inequalities? Not so good.
At the moment there is no known polynomial-time algorithm that is guaranteed to
spot a violated comb inequality if one exists. The comb-separation problem is also
not known to be in the NP-complete complexity class, so its status is wide open.
A great need coupled with inconclusive results translates into an important research
problem.

This is not to say that combs are currently skipped over in computations. By
hook or by crook computer codes must generate combs to push LP bounds after
subtour-elimination constraints fail. This is accomplished by hit-or-miss strategies
for growing handles, shrinking teeth, splicing sets, and a host of other operations.

If I tried to write this book, I don’t think I would have even got to comb inequalities, let alone continued to the nice description Bill provides of comb-finding heuristics.  This level of discussion requires some concentration when reading but the book is accessible to a wide audience.  This is an ideal book to get a college student or a smart high school student interested in operations research and combinatorial optimization.

This is a highly personal look at the TSP. Bill tells you his favorite heuristic (farthest insertion), his favorite exotic computing model (time traveling solver: take as long as you like to solve but then go back in time to report the solution), and much more.

Chapters have interesting lead quotes (the book begins with Listen, mate, I’ve traveled every road in this here land. from Geoff Mack in the song “I’ve Been Everywhere”), and the illustrations throughout are fantastic.  I also love the way that Bill includes pictures of practically everyone who has done research in this area. Putting faces to the names is a wonderful way to personalize the research.

Through this book, you’ll learn all about the Traveling Salesman Problem and, more broadly, about the different research directions in combinatorial optimization. And you’ll also see why top-notch researchers like Bill Cook find the TSP endlessly fascinating. And you might just want to be a researcher like Bill.

I guess a bit of a disclaimer is needed here: Bill has included a very nice mention of this blog in the book (thanks Bill!) with a picture of me,  and his publisher sent me an advance copy of the book. I failed miserably in getting a nice quote in on time, but that is due to my own failings. I really love the book!

 

The Plight of the Traveling Politician

Bill Cook, Professor at Georgia Tech, has an article in the “Campaign Stops” blog of the New York Times outlining the plight of the candidates vying for the Republican nomination for the U.S. presidency currently campaigning in Iowa.  It is a quirk of American politics that  a small state can take on outsized importance in the U.S. political process, but historically states such as Iowa and New Hampshire vote early on “their” nominees, while larger states such as California and New York come later.  The effect of this is that candidates spend a tremendous amount of time in relatively low-population states.  This is not necessarily a bad thing:  the rest of the country gets to watch the candidates do practically one-on-one politics and we get to see how they handle the varied interests in these states in great detail.

At least two of the candidates in Iowa (Rick Santorum and Michelle Bachmann) will have visited all 99 counties in that state, leading up to the January 3, 2012 caucus date (it is a further quirk of American politics that some state don’t hold elections as such: a caucus is a gathering of neighbors to discuss, debate, and choose their delegates to a state convention which then will choose among the candidates).

The question Bill asked was “What is the quickest way to visit all 99 counties?”.  Actually, Bill asked the question “What is the quickest way to visit the county seats of all 99 counties?”, a somewhat easier problem.  This is an instance of the Traveling Salesman Problem, and problem Bill has studied for years.  Bill is the primary author of Concorde, clearly the best code for finding optimal Traveling Salesman tours.  As Bill explains in the New York Times article, the TSP is formally a hard problem, but particular instances can be solved to optimality:

Leaving Des Moines, we have 98 choices for our second stop, then, for each of these, 97 choices for the third stop, then 96 choices for the fourth stop, and so on until we hit our last county and drive back to Des Moines. Multiplying all of these choices gives the number of possible routes through Iowa. And it is a big number, roughly 9 followed by 153 zeros. No computer in the world could look through such an enormous collection of tours one by one.

The task of choosing the best of the tours is known as the traveling salesman problem, or T.S.P. I work in an applied mathematics field called operations research, which deals with the optimal use of scarce resources, and the T.S.P. is a specialty of mine.

…

This is a tough challenge, but to tour Iowa we do not need a general solution for the problem, we just have to handle our particular 99-city example. We were able to do this using a technique known as the cutting-plane method.

The Iowa instance is, presumably, not much of a challenge for Concorde:  that code has found solutions to TSP instances with tens of thousands of cities.  I am sure that most of the work, which Bill did together with Alain Kornhauser and Robert Vanderbei of Princeton, was in determining the distances between the 99 county seats.  The actually route optimization would be a matter of seconds or less.  The result is a 55.5 hour tour, traveling at legal speed limits.

If you would like to experiment with TSPs of your own, the excellent NEOS solvers allow you to upload your own instances and run Concorde on them.

Stay tuned for more from Bill Cook as we count down to the publication of his book In Pursuit of the Traveling Salesman, to be published in January.  Trust me, you are going to like the book, so show some support for Bill by liking the Facebook page!

 

Reading “Numbers Rule” by Szpiro

It is Labor Day weekend here in the US, so, in addition to the mandatory grilling and bicycling with Alexander, I have some time to laze about on the porch reading books (and drinking beer, which is also legally required in my jurisdiction).  I have been reading Numbers Rule by George Szpiro.  This is a fascinating book on the history of thought about voting rules, starting back with Plato and continuing with Pliny the Younger, Llull, Cusanus, Borda, Condorcet, Laplace, Dodgson, and ending with the impossibility results of  Arrow, Gibbard, and Satterthwaite.  Interleaved are a few chapters on the problem of allocating seats in a parliament.

I have done work in this area (and Bartholdi, Tovey and Trick even make an appearance on page 115) but I don’t consider myself a specialist.  Even specialists, however, might learn something on the history of the field from this book.  The Llull-Casanus period (roughly 1200 A.D. to 1450 A.D.) in particular was new to me.  This pre-Renaissance period was not one that generally generated a lot of deep insights into non-religious issues (in the Western world), but voting was one area that was of great interest to the ecclesiasticals, most notably in the election of the Pope, but also in electing people for lesser positions such as abbot.

Voting seems to be an easy problem:  we do it all the time.  “How many people want A?  How many people want B?  OK, A wins” is certainly used in our three-person household.  But voting is much harder when there are more than two possible outcomes.  With A, B, and C as possibilities, having each elector vote for one and then taking the one with the most votes (plurality elections) leads to all sorts of bad outcomes.  For instance, it is arguable that having Nader in the 2000 election with Bush and Gore (in the U.S. Presidential election) led to Bush winning while without Nader, Gore would have won.  This is an example of violation of “Independence of Irrelevant Alternatives”:  shouldn’t an election result be consistent whether or not a third (or fourth or fifth) candidate enters?  In other words, if A beats B when only the two run, if C also runs then it should be that either C wins or A continues to win.  Stands to reason! But plurality voting is terrible with respect to this condition, so “splitting the opposition” is a standard way to strategically manipulate such an election.

The book makes it clear that issues of fairness in elections with more than two candidates go back to Greek times.  There have been two main approaches in getting beyond plurality voting.   In both cases, electors rank all of the candidates (unlike in plurality where only the most-preferred candidate is listed).  In the first method, candidates get points based on their placements.  For a 4 candidate election, every “first place” vote is worth 4, every second place vote is 3, and so on.  The candidate with the most votes wins.  In the second approach, the pairwise matchups are analyzed and the person who would win the most pairwise elections is deemed the overall winner.  Ideally, there is a candidate who would win against any other candidate in a pairwise election, and that person is a natural choice for winner (and a choice that plurality is not guaranteed to choose).  Such a candidate is known as a Condorcet winner.

I had always credited the foundation of these two approaches to Borda and Condorcet respectively.  Both lived in the 1700s in France, Borda being a mathematician and military officer, Condorcet being a “pure” scientist and government official.  But the real credit for these approaches should really go to Casanus and Llull four hundred years earlier.  Numbers Rule gives a very good description of their work and all that was new to me.

One aspect of Numbers Rule that I really like is the brief biographical summary at the end of every chapter. Every chapter is based on one (or a few) key figures.  Rather than try to weave the biography of that person in with the description of their findings in voting, only the key features are in the main text, while the biographical summary provides a deft summary of the rest of their lives.  The people came alive through those summaries, but extraneous details did not hinder the main exposition.

The book is non-mathematical, in the that the very few equations are exiled to chapter appendices, but it is analytical in the sense that concepts are clearly and completely described.  There is no hand-waving or “This is neat but really too hard for you”.  Even NP-Completeness gets covered in a reasonable manner (in the context of my own work).

It is only in the coverage of my own work that I really disagree with the author.  Briefly, Charles Dodgson (better known as Lewis Carroll of Alice in Wonderland fame) proposed that the winner of an election should be the one who becomes the Condorcet winner with the fewest number of changes to the electors’ ballots.  Bartholdi, Tovey and I proved that determining the Dodgson winner is NP-Hard.  Szpiro writes that this result was the “death knell” of Dodgson’s Rule, which I think vastly overstates the case.  We solve NP-Hard problems all the time, through integer programming, constraint programming, dynamic programming, and practically any other -programming you like.  There are very, very few practical elections for which we could not determine the winner of the election in a reasonable amount of time (exceptions would be those with a vast number of candidates).  In my mind, the main problem with NP-Hard voting rules is that the losers cannot be succinctly convinced that they really lost.  Without a co-NP characterization, losers have to be content with “The computer program I wrote says you lost”, which is unlikely to be satisfying.  But I don’t think Dodgson’s rule is dead and I certainly don’t think I killed it!

Operations research comes out very well in the book.  In addition to accurately describing Bartholdi, Tovey and me as Professors of Operations Research (kinda accurately:  I was a doctoral student when the paper was written but an Assistant Professor at CMU when it was published), OR takes a star turn on page 189 when the work of Michel Balinski is described.  Here is part of the description:

One of Balinski’s areas of expertise was integer programming, a branch of operations research.  Developed before, during and after World War II, operations research originated in the military where logistics, storage, scheduling and optimization were prime considerations.  But it soon acquired enormous importance in many other fields, for example in engineering, economics and business management.  While game theory, developed at the same time, was mainly of theoretical interest, operations research was immediately applied to practical problems.  Whenever something needed to be maximized or minimized – optimized for short – and resources were constrained, operations research offered the tools to do so.

What a lovely paragraph!

If you have any interest in learning about why voting and apportionment are not straightforward, and want a readable, history-oriented book on approaches to these problems, I highly recommend Numbers Rule:  reading it has been a great way to spend a lazy weekend.

Operations Research in Summertime Reading

I am just back from attending the PATAT (Practice and Theory of Automated Timetabling) Conference in Belfast, a conference I will write about in the next few days.  During the trip, I was never without my trusty itouch.  I used to travel with a Kindle, but since I started downloading my Kindle books to my itouch, my Kindle sits beside my computer with a forlorn “Your battery is empty” message on it.  While I like the Kindle screen, the itouch works much better for me for two reasons.  First, the itouch is much smaller, so it fits in my pocket.  I have a great fear of being without a book to read, and it is comforting to know that I always have a half-doze on me at all times.  Second, I often read in dark bars, and the backlight of the itouch means I can always read, albeit while looking more nerdy than normal.

On this trip, I had a good opportunity to get through some guilty pleasures:  books that are fun, without being particularly challenging.  I’m not talking Dan Brown territory here, but these are not exactly Proust’s À la recherch du temps perdu.  But I got a surprise in two of the books I read.

The first came from Tongues of Serpents by Naomi Novik.  This is a series that combines Napoleonic era naval combat with dragons (kind of Patrick O’Brian meets Anne MacCaffrey).  The initial books in the series were a revelation.  At book number six, Tongues no longer has the ability to astonish, but I still find the series enjoyable.  Early in the book, the heroes of the book receive a letter from the dragons back in England who have had to find work in order to support their prodigious appetites.  The letter goes:

But we contrived:  Majestatis suggested we should send Lloyd to Dover, to inquire after carting work, and we have worked out than men will pay a great deal just for us to carry things to London, and other Towns,  as we can do it much more quickly than Horses; and I have worked out a very nice Method by which one can calculate the most efficient Way to go among all of them, taking on some goods and leaving off others; only it grows quite tiresome to calculate if one wishes to go to more than five or six places.

It is not clear whether this is the Prize Collecting Traveling Salesman Problem or a Pickup and Delivery Problem, but it is clear that the dragon-author has found a difficulty in solving NP-complete problems.

The second appearance of operations research occurs in the Fuller Memorandum, a comedy/horror/science fiction/spy novel by Charles Stross.  This is not my normal type of reading (I don’t do suspense very well) but this series is fun and creative.  In this scene, the girlfriend of the main character is discussing a research result with a scientist.  The scientist has shown that the world is about to end due to an infestation of “class three abominations” who do all the normal things abominations do:  suck out brains and the like.  The scientist explains:

You must understand previous models all seem to have looked at how possession spreads through a sparse network, like classical epidemiological studies of smallpox transmission, for example.  But that’s flawed:  if you posit an uncontrolled outbreak, the people can see their neighbors, random strangers, being possessed.  And that in turn weakens the …[another paragraph in the same vein]

Wow!  It looks like Stross has been reading Punk Rock Operations Research!  But then we get the killer line, which suggests he really does read Laura McLay’s blog:

I modeled it using linear programing and the results are, well, they speak for themselves.

Sometimes people laugh at me and say “You see operations research everywhere!”.  While that is true, sometimes it is pretty obvious!

Great Book on Integer Programming

I just received the book “50 Years of Integer Programming 1958-2008”  published by Springer and edited by the blue-ribbon group of  Michael Jünger, Thomas Liebling, Denis Naddef, George Nemhauser, William Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence Wolsey (full disclosure:  I received a complimentary copy, presumably hoping I would post something entitled “Great Book on Integer Programming”.  Of course they risked me posting “Someone’s Littering My Mailbox with Junk” if I didn’t like the book. That is the risk when you give a free book to someone with a day job:  I don’t really rely on this blog to support my family so I can afford to just post what I think).

This book grew out of a 2008 workshop held in Aussois, France.  The “50 years” aspect dates the beginning of integer programming to Gomory’s famous cutting plane approach to integer programming.  Given the “50 years” aspect, it is appropriate that the first part of the book (about 340 pages) consists of reprints of some of the most important foundational papers in this field.  These papers begin with Dantzig, Fulkerson, and Johnson on solving a “large-scale” traveling salesman problem (49 cities), and continue with papers by Kuhn (Hungarian Algorithm for assignment), Hoffman and Kruskal (total unimodularity), Gomory (cutting planes), Land and Doig (Branch and Bound), Balinski ( 1965 survey), Edmonds (matroid partition), Karp (reducibility), Geoffrion (Lagrangian relaxation), and Balas (disjunctive programming).  I have read all of these papers, some as an undergraduate at Waterloo, some as a doctoral student, and some in my professional life as a professor.  Seeing them again was like seeing old friends.  The best part is the introductions to each of the papers.  We are fortunate that many of these authors are still with us and were able to provide some background on where the papers came from.  For some, the authors have passed away, but the editors have done a good job of finding people who could offer insightful perspectives.

I particularly enjoyed re-reading the paper on the Traveling Salesman Problem by Dantzig, Fulkerson and S. Johnson.  This paper formally belongs in the pre-history of integer programming, having been published in Operations Research in 1954.  In the paper, the authors show how to find a solution to a 49 city TSP.  I was struck again how much work this took to solve without the use of computers.  This paper occurred even before terminology was fixed (so constraints become restraints in this paper).  Dual variables are solved for directly by taking advantage of the structure of sparse linear programming solutions to this problem, since all the subproblems were solved by hand (over 1176 variables!).  And I loved the conclusions:

It is clear that we have left unanswered practically any question one might pose of a theoretical nature concerning the traveling-salesman problem;  however, we hope that the feasibility of attacking problems involving a moderate number of points has been successfully demonstrated, and that perhaps some of the ideas can be used in problems of a similar nature.

If only some of today’s researchers had the same level of perspective and humility!

I also loved a paragraph from Gomory’s introduction to his two papers.  After developing what would later be known as “Gomory cuts”, he decided to test it on a (1958) computer:

During the exciting weeks that followed, I finally worked out a finiteness proof and the programmed the algorithm on the E101, a pin board computer that was busy during the day but that I could use after midnight.  The E101 had only about 100 characters and the board held only 120 instructions at one time, so that I had to change boards after each simplex maximization cycle and put in a new board that generated the cut, and the put the old board back to re-maximize.  It was also hard work to get the simplex method down to 120 E101 instructions.  But the results were better and more reliable than my hand calculations, and I was able to steadily and rapidly produce solutions to four- and five- variable problems.

I thought I was hard core, reminiscing about working with punch cards, but Gomory reveals me as a slacker!

The historical section is followed by three general survey articles:  Conforti, Cornuéjols, and Zambelli on polyhedral approaches, Bill Cook on combinatorial integer programming, and Vanderbeck and Wolsey on reformulations and decomposition.  The final section are a series of surveys on modern topics:  geometry of numbers, nonlinear integer programming, MIP computation, symmetry, semidefinite relaxations, and group theoretic approaches.  The authors chosen are the leading people in each area, and the articles are extremely well done.   With these papers, this book now is the reference book for the current state of the art in integer programming.  The Amazon page for the book has the first dozen or so pages available with their “Look Inside” feature, so you can check out the full table of contents.

The book comes with two DVDs.  One contains the presentations from Section II in hour-long sessions.  The second DVD has a very entertaining discussion between moderators George Nemhauser and Bill Pulleyblank and “founders” Egon Balas, Michel Balinski, Jack Edmonds, Ralph Gomory, Art Geoffrion and Richard Karp (Alan Hoffman, Harold Kuhn, and Aisla Land were unable to attend).  I haven’t watched the whole thing yet, so if it ends in a brawl, don’t spoil it for me!  It was great to see that panel all together.

Overall, I haven’t enjoyed getting a book as much in a long time (certainly not since Bill Cook’s Traveling Salesman book, and I wouldn’t want to choose between these two).  I think I would even pay Springer’s list price of $99 for it, though I really wish they would price this more reasonably (though the price is not absurd:  they have many books that offer far less that cost far more) .  Everyone even vaguely interested in integer programming should have this on their bookshelf.

Pushing back boundaries

It is 1AM here in Cork, and an adenoidal singer with a very eclectic song selection is screaming outside my hotel window, making it difficult to sleep. So I am reading “The Science of Discworld III: Darwin’s Watch” by Terry Pratchett, Ian Stewart, and Jack Cohen. Terry Pratchett is my second favorite author (next to Patrick O’Brian), and I enjoy the “Science of Discworld” series. In these books, chapters from a novelette by Pratchett alternate with scientific discussion by Stewart and Cohen.

The first part of the book has some good things to say about the scientific process. From Pratchett:

It [a large piece of machinery in a lab] also helps in pushing back boundaries, and it doesn’t matter what boundaries these are, since any researcher will tell you it is the pushing that matters, not the boundary.

That, in essence, is the problem with much of faculty reviews, paper refereeing, and conference paper selection. Most of the time, we evaluate the pushing, with insufficient attention to the boundary. Pratchett, as (almost) always, gets it right.

The Numerati

Stephen Baker of BusinessWeek has just published a book entitled The Numerati, and has a blog related to the book.  The purpose of the book is to look how mathematicians are using data to to profile people in their shopping, voting, and even dating habits.

I am not exactly an unbiased reader of the book.  I talked with Stephen during the writing of the book, and he asked me to review the two pages he wrote about “operations research” (I made a couple suggestions which didn’t make it into the final version:  I guess this is my “cutting room floor” experience).  He was kind enough to send me a review copy of the book, which I received a few weeks ago.  He also accepted my invitation to speak here at CMU to the Tepper School Faculty and doctoral students.

The book is divided into chapters corresponding to the different uses of data:  “Worker”, “Shopper”, “Voter”, “Terrorist”, “Patient” and “Lover”.  For instance, in the “Voter” section, the emphasis is on predicting voter behavior.  In the past (perhaps), geography and economics were very good predictors of voting behavior.  Now, people seem much more in flux as to their behavior.  Perhaps there are better predictors.  Or perhaps there are useful clusterings of like-minded people that would respond to a particular pitch.  If Barack Obama were to identify a cluster of “people who blog about obscure  but important mathematical modeling methods”  and would send a mailer (or email more likely) showing his deep understanding of operations research and a promise to use that phrase in his acceptance speech, then perhaps he would gain a crucial set of voters.  Barack, are you listening?

I greatly enjoyed reading the book, and did so in one sitting.  For someone like me who perhaps could be seen as one of the Numerati, there is not much technical depth to the book, but there are a number of good examples that could be used in the classroom or in conversation.  There is a bit too much “The Numerati know much about you and can use it for good or EEEVVVIILLLL” for my taste, but  perhaps I take comfort in understanding how poorly data mining and similar methods work in predicting individual behavior.  The book is very much about modeling people, so essentially ignores the way operations research is used to automate business decisions and processes.  This is a book primarily about what I would call data mining and clustering, so there are wide swathes of the “numerati” field that are not covered.  But for a popular look on how our mathematics is used to characterize and predict human behavior, The Numerati is an extremely interesting book.

Opening Session at IFORS

IFORS 2008 BannerAfter a somewhat rocky start (an electricity substation in Joburg failed, resulting in large traffic delays, so the student assistants were late so the rooms didn’t have computers on time), the IFORS conference officially opened with a fantastic opening session. Of course, I am biased, since I am on the IFORS board with responsibility for meetings. But I do think it went very well.

IFORS 2008 Minister Mangena and Hans IttmannFirst, there was dancing and singing by a choir and drums which set the African mood. Then Elise del Rosario gave a terrific welcome, talking about the promise of Africa and the role operations research plays in achieving that promise. This was followed by a welcome by the Minister for Science and Techology, Mosibudi Mangena. Minister Mangena is one of us: he has a masters degree in applied math, and he gave a talk that suggested he understood operations research. As a colleague said, the talk also suggested a speech writer familiar with the Science of Better web site. The minister took the opportunity to tweak Hans Ittmann, Organizing Chair for the conference, for not offering enough operations research to his department. Hans promptly promised to work hard to embed OR throughout the South African government. Could people even 15 years ago imagine a South Africa where an esteemed black Cabinet Minister would tease a (white) operations research professor about the role operations research plays in the government? I will write later about how I feel holding a conference in South Africa at this time, but I loved the exchange.

One person who gets credit in South Africa for the amazing transformation over the last two decades was the opening speaker Clem Sunter. Clem is a Brit who has been in Africa for 35 years, working for the Anglo American Corporation and more recently heading up the Anglo American Chairman’s Fund, a corporate social responsibility fund.

Clem does “scenario planning” and has been described as Africa’s Alvin Toffler. In short, he is a futurist. In the 1980s, he developed two scenarios for South Africa. The “High Road” was a South Africa transformed by negotiation leading to political settlement (I do not need to remind people that South Africa in the 1980s was torn by the odious apartheid). The “Low Road” was confrontation leading to a wasteland. He talked about these scenarios to both FW de Klerk, leader of the National Party, and the imprisoned Nelson Mandela. Mandela and de Klerk shared the Nobel Prize for their combined work to end apartheid.

Clem opened his talk by suggesting scenario planning is like poetry, where operations research is like an essay. He uses possible futures to frame debates about where companies, countries, and societies are going. When speaking about South Africa, he clearly sees the problems: crime, HIV/AIDS, and a declining infrastructure for some. But he also understands the strengths: resources, tourism, and its role (like that of Dubai in the mid-east and Hong Kong in Asia) as a gateway to Africa. In his view, one key to success is the turnaround in Zimbabwe. He believes that President Mugabe is in an endgame, and once he is gone, tremendous investment will flow back into Zimbabwe, with much going through South Africa, and with much of the rebuilding being done by South Africans.

I must say I am not a great fan of futurists. They are either so vague they become like horoscopes in that you can read almost anything into what they say, or make so many “predictions” that almost any future will have been predicted by them. Clem seemed more thoughtful on the purpose of scenarios. He has scenarios not to predict the future but to frame the debate. It is in this approach that he sees poetry in scenario planning.

There was a terrific question right at the end of the talk (if anyone noted who asked the question, please let me know September 8 addition: asked by Jonathan Rosenhead of LSE) about the role of operations research in scenario planning. We do scenarios all the time: we create stochastic models of the future and simulation then provides us with scenarios that we can optimize over. How does this relate to Clem’s use of scenarios. He said that there was a large difference, whereby his scenarios change conversation while technical scenario building has not had the same broader impact. And, he said, there is a Nobel Prize in the waiting for someone who combines the two. You can find out more about Clem and his thoughts at a website for him and his colleague Chantell Ilbury

I enjoyed the talk a lot, and learned a lot about South Africa and the challenges the country faces. And I was a little inspired to think about how the things I do can change conversations. I am sure there are differing opinions, since this was not a typical OR talk.

Unusually for an operations research conference, not a single person (out of 500 or more) left the plenary once Clem began speaking. That is the sign of a successful opening plenary!

Up tomorrow, back to traditional OR with one of my favorite people in the field (and my co-advisor 20 years ago), Don Ratliff from Georgia Tech on Lean Supply Chains.