Uncovering Hidden Structure through Parallel Problem Decomposition


  • Yexiang Xue Cornell University
  • Stefano Ermon Cornell University
  • Carla Gomes Cornell University
  • Bart Selman Cornell University




Combinatorial Search, Parallel Algorithm, NP-complete Problem, Set Basis Problem


A key strategy for speeding up computation is to run in parallel on multiple cores. However, on hard combinatorial problems, exploiting parallelism has been surprisingly challenging. It appears that traditional divide-and-conquer strategies do not work well, due to the intricate non-local nature of the interactions between the problem variables. In this paper, we introduce a novel way in which parallelism can be used to exploit hidden structure of hard combinatorial problems. We demonstrate the success of this approach on minimal set basis problem, which has a wide range of applications in machine learning and system security, etc. We also show the effectiveness on a related application problem from materials discovery. In our approach, a large number of smaller sub-problems are identified and solved concurrently. We then aggregate the information from those solutions, and use this to initialize the search of a global, complete solver. We show that this strategy leads to a significant speed-up over a sequential approach. The strategy also greatly outperforms state-of-the-art incomplete solvers in terms of solution quality. Our work opens up a novel angle for using parallelism to solve hard combinatorial problems.




How to Cite

Xue, Y., Ermon, S., Gomes, C., & Selman, B. (2014). Uncovering Hidden Structure through Parallel Problem Decomposition. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.9093