Applications of Combinatorial Optimization, 2nd Edition

Chapter 8

Parallel Combinatorial Optimization

8.1. Impact of parallelism in combinatorial optimization

The progress made in the parallelism domain (architectures, systems, languages, execution environments and algorithms) over the last decade has brought about real advances in combinatorial optimization at the start of the 21st century. The recent media “storm” following the solving of several hard instances of famous problems like the traveling salesman or quadratic assignment is proof of this.

Interest in the latter problem was revived in the last three years, in particular for solving the example called Krarup30a (size 30 elements to be assigned), by Peter Hahn from the University of Pennsylvania, in a continuation of his work since 1998 [HAH 98a, HAH 98b, HAH 01], and the examples Nugent27 and Nugent30 by Anstreicher, Brixius, Goux and Linderoth from the University of Iowa and the Argonne National Laboratory [ANS 01a, ANS 01b, ANS 02]. Solving the instance of Nugent30 was reported widely in the American press (Chicago Tribune, Chicago Sun Times, HPCWire, WNCSA Access Magazine, etc.) and in a number of French papers and journals (InfoScience, Le Monde, Transfert, etc.). The extent of the impact of this solution was as important as that provoked by the victory of IMB’s chess-playing machine DeepBlue against the “human” world champion Gary Kasparov.

In 1998–2000, the Applegate team, Bixby, Chvátal and Cook [APP 98, CON] successively solved the instances usa13509 and d15112 of ...