When people talk about large discrete optimization problems the first thing that comes to mind is usually the Travelling Salesman Problem, or TSP. The classic version of this famous problem involves finding the route, or "tour" through n cities that minimizes the total distance travelled. The TSP has many, many applications is logistics and manufacturing. The largest TSP ever solved to optimality is the "usa13509" problem, which is the shortest tour through the 13,509 cities in the United States with population more than 500. See http://www.keck.caam.rice.edu/tsp/ for details, here's a picture of the tour. We estimate that the total computation to solve nug30 was roughly twice that required to solve usa13509.

QAP and TSP are both "NP-Hard" optimization problems, but QAP is much harder in practice. It is also harder by some theoretical measures. For example, for many NP-Hard optimization problems, including metric TSP, there exist "constant-factor approximation algorithms." An algorithm of this type runs in so-called polynomial time, and returns a solution of the problem whose objective value is guaranteed to be within a given factor of optimality (like 10%, or 50%, or 100%, or whatever.) However it is known that there can be no such approximation algorithm, for ANY constant factor, for QAP, unless P=NP. ("P=NP" is the outstanding open problem in theoretical computer science. This got some press recently since the problem is one of the "millenium" problems, for which the Clay Institute has offered a prize of $1 million. See http://www.ams.org/claymath/.)

Another good comparison for the nug30 problem is the RSA-155 challenge problem (factoring a 512 bit composite number), which was solved during the summer 1999. The NY Times article is at http://www.arx.com/corporate/publications/pub3.htm, and a technical description of the solution process is at http://www.interesting-people.org/199908/0070.html. The factoring was accomplished using about 300 computers, over a total period of about 7 months. We estimate that if the same computational power applied to the nug30 problem had been applied to RSA-155, it could have been solved in about 2 weeks.