Uncovering Hidden Structure through Parallel Problem Decomposition for the Set Basis Problem: Application to Materials Discovery

Yexiang Xue, Stefano Ermon, Carla P. Gomes, Bart Selman

Introduction

The Set Basis Problem (SBP) is a fundamental NP-complete challenge in computer science. Given a collection of sets, the goal is to identify the smallest possible "basis"—a minimal collection of sets—from which every original set can be reconstructed using only the union operation. While conceptually similar to finding basis vectors in linear algebra, the discrete nature of set unions makes SBP significantly more difficult to solve at scale.

SBP has broad applications across various domains, including role-based access control in security, matrix factorization in machine learning, and biological sequence analysis. However, one of its most critical applications lies in the field of materials discovery, where it helps scientists identify the constituent phases of new chemical compounds.

The Set Basis Problem in Materials Discovery

In materials science, researchers often use high-throughput techniques to discover new materials, such as catalysts for fuel cells. A common method involves depositing different combinations of metals onto a silicon wafer and then using X-ray diffraction (XRD) to analyze the resulting structures.

Figure 1: Application of SBP to materials discovery, showing how complex X-ray diffraction patterns are composed of underlying basis crystal structures (phases).

As shown in Figure 1, the XRD patterns produced are mixtures of signals from individual "basis" crystal structures, known as phases (e.g., $\alpha, \beta, \gamma$). Identifying these pure phases from the mixed signals is a classic instance of the Set Basis Problem. Traditional sequential solvers often struggle with these datasets due to the non-local interactions between variables and the sheer size of the search space.

A Two-Phase Parallel Decomposition Strategy

To overcome the limitations of traditional solvers, researchers have developed a novel parallel decomposition strategy. Unlike standard parallel approaches that split the search space or run multiple independent solvers, this method decomposes the data itself to uncover "hidden structures" that simplify the global problem.

The strategy consists of two primary phases:

1. Exploration Phase

The algorithm begins by creating numerous small sub-problems. Each sub-problem is formed by selecting a subset of the original sets, often grouped using Jaccard similarity to ensure that related sets are processed together. These sub-problems are solved concurrently across multiple processing cores to identify "local" bases.

2. Aggregation Phase

The "secret sauce" of this approach lies in how these local solutions are combined. The researchers observed that basis sets found in sub-problems often act as "sponsors" — they are frequently supersets of the true global basis sets.

Figure 2: The two-phase parallel scheme, illustrating the transition from parallel sub-problem exploration to the iterative deepening re-solving step.

As illustrated in Figure 2, the aggregation phase involves two steps:

  • Pre-solving: The local solutions are intersected to generate a high-confidence "best guess" for the global basis. Sets that appear frequently across different sub-problems are assigned higher confidence scores.
  • Re-solving: This guess is used to initialize a complete Mixed Integer Programming (MIP) solver. The solver performs an iterative deepening search, starting with a highly constrained search space based on the high-confidence sponsors and gradually relaxing these constraints until the exact global solution is found.

This process effectively identifies "backdoors" — a small set of critical variables that, once determined, make the remaining NP-complete problem significantly easier to solve.

Key Results and Performance

The parallel decomposition method was evaluated against both synthetic benchmarks and real-world materials science data. The results demonstrate a dramatic improvement in both speed and accuracy:

  • Order-of-Magnitude Speedups: On the most challenging synthetic benchmarks (A7 and A8), traditional sequential solvers failed to find a solution even after 72 hours of computation. In contrast, the parallel scheme found the exact solution in as little as 3 to 115 minutes.
  • Guaranteed Exactness: While many fast heuristic solvers exist, they often produce error rates exceeding 50% on complex problems. This new method remains a complete solver, meaning it is guaranteed to find the exact minimum basis with 0% error.
  • Real-World Efficiency: In practical materials discovery tasks, the parallel solver consistently outperformed sequential versions by 3x to 10x, enabling the analysis of larger and more complex material systems than previously possible.

Conclusion

By leveraging parallel sub-problem decomposition to identify hidden structural "backdoors," this research transforms the Set Basis Problem from a computational bottleneck into a manageable task. While the current implementation uses Jaccard similarity for sub-problem selection, future work may explore alternative grouping strategies or apply this theoretical framework to other hard combinatorial problems like the Boolean Satisfiability Problem (SAT). This approach not only advances the state of the art in combinatorial optimization but also provides a powerful tool for accelerating discovery in the physical sciences.

Summary updated

BibTeX
@inproceedings{xue2015uncovering,
  author = {Yexiang Xue and Stefano Ermon and Carla P. Gomes and Bart Selman},
  title = {{Uncovering Hidden Structure through Parallel Problem Decomposition for the Set Basis Problem: Application to Materials Discovery}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure