Category: Books

Knuth and Multicore Systems

Donald Knuth has been publishing “fascicles” from his Volume 4 (Combinatorial Algorithms) of his epic The Art of Computer Programming. These are shortish (100-150 page) sub-chapters of a work on an area that expands faster than Don can write. You can download some of the preliminary versions on Knuth’s page to get the flavor.

Knuth was interviewed by Andrew Binstock of InformIT. Great interview with very provocative questions and answers! I particularly liked the exchange on parallel algorithms and multicore systems. Don is not a fan:

Andrew: One of the emerging problems for developers, especially client-side developers, is changing their thinking to write programs in terms of threads. This concern, driven by the advent of inexpensive multicore PCs, surely will require that many algorithms be recast for multithreading, or at least to be thread-safe. So far, much of the work you’ve published for Volume 4 of The Art of Computer Programming (TAOCP) doesn’t seem to touch on this dimension. Do you expect to enter into problems of concurrency and parallel programming in upcoming work, especially since it would seem to be a natural fit with the combinatorial topics you’re currently working on?

Donald: The field of combinatorial algorithms is so vast that I’ll be lucky to pack its sequential aspects into three or four physical volumes, and I don’t think the sequential methods are ever going to be unimportant. Conversely, the half-life of parallel techniques is very short, because hardware changes rapidly and each new machine needs a somewhat different approach. So I decided long ago to stick to what I know best. Other people understand parallel machines much better than I do; programmers should listen to them, not me, for guidance on how to deal with simultaneity.

Andrew: Vendors of multicore processors have expressed frustration at the difficulty of moving developers to this model. As a former professor, what thoughts do you have on this transition and how to make it happen? Is it a question of proper tools, such as better native support for concurrency in languages, or of execution frameworks? Or are there other solutions?

Donald: I don’t want to duck your question entirely. I might as well flame a bit about my personal unhappiness with the current trend toward multicore architecture. To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks!

I have been struggling to take advantage of my (now not so-)new computer and its 8 cores. Since about 90% of my used CPU cycles are done in CPLEX, and I only have a single-core license, I am actually running at about 10% capacity on that machine. And my efforts to write some specialized codes have not been successful, though that is perhaps more due to lack of time and effort than any inherent difficulty. Does the new generation of OR researchers understand and feel comfortable with multi-core programming? Or are we now just going to stall in terms of computation speed in practice?

Genetic Programming

Ricardo Poli, William Langdon, and Nicolas McPhee have just published a book “A Field Guide to Genetic Programming” and have blog to support it.  The neat thing about this book is that the pdf is freely downloadable, with printed copies available cheaply through lulu.com.  I spent a half hour thumbing through the book, and am very impressed with it.  It is highly readable, and not hype-driven.  I found it a very good introduction to the method, along with a fair assessment of its strengths, weaknesses, and prospects.

The copyright on this is a form of “Creative Commons”, perhaps the sign of a trend away from the expensive, restrictive copyrights of commercial publishers.

Andy Boyd, Pricing, and “The Engines of Our Ingenuity”

Andy Boyd, formerly chief scientist of PROS (he is actually still on their scientific board, but is not an active employee) visited CMU today as part of our CART (Center for Analytical Research in Technology) seminar series. He talked about the challenges those in pricing research face. The main point he made is that it is very difficult to figure out demand curves (hence elasticity of demand) through data. Having even lots and lots of transaction level data doesn’t help much in generating demand curves. This is not a new insight (economists refer to these sorts of issues as “identification problems”) but it was interesting to hear this from someone who has made a living doing pricing for the last decade. Without demand curves, how can pricing be done? Airlines have enough separate flights (for which you can assume no substitution) to do a fair amount of experimentation. How can other areas get similar data? Further, Andy makes the point that without understanding the sales process, it is impossible to interpret any data. For instance, for a given kind of car, there will be a few sales at a low value, lots of sales at a medium value, and a few sales at a high value. This does not mean that the demand for cars goes up then down as a function of price! Since car prices are generally negotiated, only a few of the best negotiators will get the lowest price.

Andy makes a strong case that operations research needs to be applied more in the entire sales domain, from customer segmentation through pricing to negotiation. The lack of underpinning in something as fundamental as a demand curve is a little disconcerting, but he stressed for many markets (those without “posted prices”), demand curves may be the wrong modeling approach in the first place.

Andy is now “semi-retired” (I guess he did well when PROS went public) but certainly seems to have lots going on. Once a week, he does a radio show on the Houston public radio radio station. The show is called Engines of Our Ingenuity and Andy does his version on Thursdays. The transcripts are available for the shows. Andy is normally referred to as “guest scientist” but he is sometimes called “operations researcher”, which makes me happy. A recent show of his was on operations research legend George Dantzig, concentrating on his development of the simplex algorithm and his lack of Nobel Prize. Other episodes involve the four color theorem, mathematical models, parallel computing, and operations research itself, along with much, much more. John Lienard is the driving force behind The Engines of Our Ingenuity.

Also, Andy has a new book out on pricing entitled The Future of Pricing: How Airline Ticket Pricing has Inspired a Revolution. Andy and I go back more than twenty years: it was great to see him and see all the amazing things he is doing, even if he is “semi-retired”.

Sports Scheduling and Rubik’s Cube

The October 6, 2007 edition of The Spectator (an English weekly with a right-of-center, Olde England bias but wonderful cartoons, chess column, and commentary once the bias is accounted for) contains a “review” of a book The Blind Eye: A Book of Late Advice by the poet Don Paterson (I don’t think the book is available in the US). The review is actually just a collection of 30 or so extracts from the book. The review alone left me chuckling all morning. Some quotes:

I can see exactly what not to do at the moment. No doubt through the usual process of elimination, I’ll arrive at my favourite strategy of total paralysis.

I enjoyed L.’s creeping senility. I could have him repeat my favorite stories as often as I wanted, sometimes several times in the space of the same afternoon. X’s sudden lurch into his anecdotage, on the other hand, was a disaster: until then, his shyness had prevented our discovering what a bore he was.

and

You’ve made a blog … clever boy! Next: flushing.

One really hit home for me:

A poem with one line wrong is like a Rubik’s Cube with one square wrong: what it is precisely not is one move away from completion.

I have been looking for an intuitive explanation to various sports leagues on why a schedule that is perfect except for one flaw is likely a long way from a perfect schedule. I will proceed to rip off this analogy and pretend it is my own.  I admit that comparing a schedule to Rubik’s cube is not as clever as comparing a poem to the cube:  I wonder if I should compare a schedule to a poem?

Math, Poker, and Peter Winkler

Peter Winkler was kind enough to send me a copy of his new book Mathematical Mind-Benders. It is full of wonderful puzzles, at a level similar to the level aimed at by Martin Gardner (I have written about Peter’s work before): go and buy it! Here is a question (for which I will provide the answer in a day or so):

In poker, what is the best full house?

Comment: You may assume you are playing straight five-card stud poker (everyone gets five cards, all closed, no exchange] with (say) five companions, using a single normal deck. As a result of God owing you a favor, you are entitled to a full house, and you get to choose the full house you will get. Which should you choose?

This one I got (I get about 1 in 10 of the puzzles, mainly because either I have seen them or I know the relevant professional literature). I wonder how many professional poker players get it? Answer in a day or two. Comments with guesses welcome.

The Traveling Salesman Problem: A Computational Study

The Traveling Salesman Problem: A Computational Study is a new book by David Applegate, Bob Bixby, Vasek Chvatal, and Bill Cook (published by Princeton University Press) and it is terrific. I was asked by OR Letters to provide a review, which I have done. I won’t spoil the review for the journal, but here is my final paragraph(before editing):

At one level, this book may appear to be about a particular computer code for a particular combinatorial optimization problem, but I believe it is far more. Much of the research we do is incremental, involving a small step on a subproblem of a subproblem of a subproblem. Rarely do we step back and see the big picture. This book is, fundamentally, about the big picture. The authors, in their computer code and in their writings, have taken the best from the extensive literature and shown how we as a field have moved forward. At this point, algorithms, implementation, and computing have advanced sufficiently that almost any instance of practical interest can be solved to optimality with sufficient, but reasonable, computing resources. The incremental improvements add up to a tremendous success. By bringing together the best work from a wide array of researchers, describing it in a book, and implementing it in a code, the authors show how research in computational combinatorial optimization should be done.

I really like the book. And I particularly appreciate the publisher for putting it out at a reasonable price: under $50.

Six Key Ideas of Operations Research?

For most of us, teaching a first course in operations research involves trotting out our old friends linear programming, sensitivity analysis, integer programming, and so on. Twenty years ago, we used linear algebra; today, we concentrate more on modeling. But it is not clear that students get the Big Picture. Like “Modeling is useful” or “Decisions can (sometimes) be made on marginal information” or even “If you add constraints, the best solution gets worse”.

Steven Baker, whose Blogspotting I regularly visit and which often provides material here, has a posting entitled Economics and Braille Keyboards pointing to an interview with the economist Robert Frank. Frank has a new book out based on the idea that there are really only about six key ideas in economics, and if you can get students to think about and apply those six ideas, then you have really had a successful introductory course. The title comes from a student essay on why drive-through banks have braille on the keyboard. If blind people can’t drive, why provide braille? The answer is in cost-benefit analysis: it would cost more to have two types of keyboards, so standardization is better (assuming putting on those dots is not costly in itself). As for benefits, this holds even if the benefit is zero. If the benefit is positive (blind people in cabs, say), then it holds even stronger.

What would be the six key ideas/insights about operations research? I listed a few above. Some others might include “If there is randomness, systems without slack run out of control” and “Nonbinding constraints don’t affect the optimal solution” (these are more insights than key ideas). As a prescriptive science (rather than the descriptive science of most economists), it is not clear that this method of teaching works as well, but it is useful for us to think about what we really want to get across in our classes.

Operations Research in the New York Times and I am annoyed and depressed

The term “Operations Research” appears in the New York Times today (May 20, 2007) in an article entitled “Reaping Results: Data-Mining Goes Mainstream“. Here is the start:

RODNEY MONROE, the police chief in Richmond, Va., describes himself as a lifelong cop whose expertise is in fighting street crime, not in software. His own Web browsing, he says, mostly involves checking golf scores.

But shortly after he became chief in 2005, a crime analyst who had retired from the force convinced him to try some clever software. The programs cull through information that the department already collects, like “911” and police reports, but add new streams of data — about neighborhood demographics and payday schedules, for example, or about weather, traffic patterns and sports events — to try to predict where crimes might occur.

Later comes the “Operations Research” reference:

The desire to exploit computing and mathematical analytics is by no means new. In the 1960s and ’70s, “operations research” combined computing and math mainly to make factory production work more efficient. And in that period, “decision support” software was intended to help managers more intelligently use information in the big computing file cabinets — databases — that were becoming common in corporations.

That really burns my butt. I hate the idea that operations research is shunted into history and it is the new analytics that is the key. It is all Operations Research!

Otherwise, the article is great. Analytics are a key success path for companies. Here is a quote from Wired on why Yahoo! lost out to Google:

At Yahoo, the marketers rule, and at Google the engineers rule. And for that, Yahoo is finally paying the price.

On the personal side, I also cringed when I saw the following in the New York Times article:

“It’s really starting to become mainstream,” says Mr. Davenport, co-author with Jeanne G. Harris of “Competing on Analytics: The New Science of Winning” (Harvard Business School Press, 2007). The entry barrier, he says, “is no longer technology, but whether you have executives who understand this.”

This was really the theme of my Hood Lecture, and I had the inklings of writing something longish on the subject. I will have to see if this book does a good job on this.

Mathematical Puzzles, Martin Gardner, and Peter Winkler

I am certainly not alone when I say that interest in mathematics was sparked by Martin Gardner’s Mathematical Games column in Scientific American. I have a strong memory of many boring physics classes in high school which I whiled away reading through the stack of Scientific Americans in the corner. Those columns led to mathematics in university (where I probably not coincidently received a “D” in physics) and onward through my interest in discrete optimization.

While Gardner has long since stopped writing the column, his influence remains strong. Every year, a group of mathemeticians, magicians, jugglers, puzzle makers and so on meet at a “Gathering for Gardner“, a get-together that looks to be a blast!

Last year, Peter Winkler, formerly of Lucent and now at Darmouth, put together a set of puzzles, cleverly and correctly entitled “7 Puzzles You Think You Must Not Have Heard Correctly”. Here is one I particularly like:

The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.

The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed. Find a strategy for them which which has probability of success exceeding 30%. Comment: If each prisoner examines a random set of 50 boxes, their probability of survival is an unenviable 1/2^100 = 000000000000000000000000000008. They could do worse if they all look in the same 50 boxes, their chances drop to zero. 30% seems ridiculously out of reach but yes, you heard the problem correctly.

Is this really possible? Check out Peter’s writeup for the solution (and seven other problems). Also check out his book for more.

Math, Poker, and Perfectly Reasonable Deviations

The Math and Poker blog is one I like to go to periodically (not the least because I am part of his blogroll). The thing I like best is the use of simple probability/queueing/stochastic systems to point out the misconceptions of many gamblers. A little probability goes a long way, but it seems that many gamblers are not willing to even take the first steps in probability theory.

A recent post on that blog pointed me to Perfectly Reasonable Deviations, a blog on “random ramblings on science, technology, and other such stuff”. A recent entry there reviewed the book Convex Optimization by Boyd and Vandenberghe. An excerpt from his review:

It’s a wonderful book! A masterpiece! A joy to read! Quite likely one of the best math books I have ever read.

I agree!