Bridging the Gap Between Theory and Practice: Structure and Randomization in Large Scale Combinatorial Search.

摘要

This research effort focused on three core research challenges: (1) How to explain the gap between formal analysis and practical performance for combinatorial search; (2) How to characterize and capture hidden tractable structure in real-world problems; and, (3) How to further boost combinatorial search methods for real-world problems. A series of advanced formal models for predicting the runtime of combinatorial search methods were developed. Models of runtime distributions of search methods capturing exponential and power law (heavy-tailed) regimes for both complete and incomplete randomized search methods were introduced, together with a generative model that generates search trees with any pre-defined degree of heavy-tailedness. New methods for the efficient computation of the number solution clusters and their marginal distributions were developed. The notion of backdoor sets, a measure that characterizes hidden problem structure was extended to encompass combinatorial optimization problems as well as learning during search, thereby providing novel insights into the connection between the hidden structure of optimization problems and the surprising efficiency of today s optimization engines. A novel Markov Chain Monte Carlo sampling strategy, inspired by a flat histogram method from statistical physics, was developed to compute the density of states of a Boolean formula. Multi-agent inference problems in dynamic environments were formulated into the framework of message passing algorithms and graphical models, generalizing the standard Kalman filter to the distributed case. A new hybrid strategy for the MaxSAT problem was also proposed, combining the complementary strength of local search and systematic search, bringing the best of both worlds in a way that is ideal for current multi-core architectures.