Our experience has been that it is fairly straightforward to implement SWO in a new domain, because there are usually fairly obvious ways to construct greedy solutions, and to analyze a solution to assign ``blame'' to some of the elements. Naive implementations of SWO tend to perform reasonably well.
We have found the view of SWO as performing a ``coupled search'' over two different search spaces to be very informative. It has been helpful to characterize the kinds of moves that SWO makes in each of the search spaces, and the effect this has on avoiding local optima, etc. We hope that by continuing to gain a deeper understanding of what makes SWO work we will be able to say more about the effective design of SWO algorithms.
As the number of directions for future research suggests, we have only begun to scratch the surface of ``Squeaky Wheel'' Optimization.
The authors wish to thank Robert Stubbs of Lucent Technologies for providing the data used for the scheduling experiments. The authors also wish to thank George L. Nemhauser, Markus E. Puttlitz and Martin W. P. Savelsbergh with whom we collaborated on using SWO in a hybrid AI/OR approach. Many useful discussions came out of that collaboration, and without them we would not have had access to the Lucent problems. Markus also wrote the framework for the scheduling experiments and the TABU and IP implementations.
The authors also thank the members of CIRL, and James Crawford at i2 Technologies, for their helpful comments and suggestions. We would like to thank Andrew Parkes in particular for suggestions and insights in the graph coloring domain.
This effort was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number F49620-96-1-0335; by the Defense Advanced Research Projects Agency (DARPA) and Rome Laboratory, Air Force Materiel Command, USAF, under agreements F30602-95-1-0023 and F30602-97-1-0294; and by the National Science Foundation under grant number CDA-9625755.
The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Defense Advanced Research Projects Agency, Rome Laboratory, the Air Force Office of Scientific Research, the National Science Foundation, or the U.S. Government.
Most of the work reported in this paper was done while both authors were at CIRL.