A High-Performance Approach for Solution Space Traversal in Combinatorial Optimization
Authors: Wendy K. Tam Cho (University of Illinois at Urbana-Champaign), Yan Y. Liu (University of Illinois at Urbana-Champaign)
Abstract: Many interesting problems, including redistricting and causal inference models, have heroically large solutions spaces and can be framed within a large-scale optimization framework. Their solution spaces are vast, characterized by a series of expansive plateaus rather than a rapid succession of precipices. The expansive plateaus coupled with the sheer size of the solution space prove challenging for standard optimization methodologies. Standard techniques do not scale to problems where the number of possible solutions far exceeds a googol. We demonstrate how a high performance computing environment allows us to extract insights into these important problems. We utilize multiple processors to collaboratively hill climb, broadcast messages to one another about the landscape characteristics, and request aid in climbing particularly difficult peaks. Massively parallel architectures allow us to increase the efficiency of landscape traversal, allowing us to synthesize, characterize, and extract information from these massive landscapes.
Two-page extended abstract: pdf