UConn Researchers Earn Best Paper Award for Speeding up Decision Diagrams with GPU Computing

Posted on by

Researchers at the University of Connecticut and Carnegie Mellon University have developed new methods that harness the parallel computing power of graphics processing units (GPUs) to accelerate dynamic programming for combinatorial optimization. One of the studies, GPU-Accelerated Relaxed Decision Diagrams for Branch-and-Bound Optimization, received the Best Paper Award at the 2026 International Conference on Principles and Practice of Constraint Programming (CP 2026).

The research was conducted by UConn School of Computing researchers Fabio Tardivo and Laurent Michel, the Synchrony Chair in Cybersecurity, together with Willem-Jan van Hoeve of Carnegie Mellon University’s Tepper School of Business.

Dynamic programming is a foundational optimization technique that solves complex problems by breaking them into sequences of smaller decisions. Its use as a general-purpose optimization method, however, can be constrained by the enormous number of possible states that must be considered. The researchers showed that the highly parallel architecture of modern GPUs is particularly well suited to accelerating this search, allowing many states to be processed simultaneously.

Diagram showing relaxed decision diagrams processed on a GPU and restricted decision diagrams processed on a CPU.
The researchers developed a decoupled architecture in which relaxed decision diagrams are compiled in parallel on a GPU while restricted decision diagrams are processed in parallel on a multi-threaded CPU. Figure adapted from Tardivo, Michel, and van Hoeve (2026), licensed under CC BY 4.0.

The work is described in two related studies. In Complete Anytime Decision Diagram Search with GPU-Accelerated State Expansion, the researchers used GPUs to process large groups of states simultaneously, substantially accelerating the search for solutions to difficult routing problems. In the CP 2026 study, they developed a complementary approach in which GPUs accelerate the construction of relaxed decision diagrams used to bound the search and prove that a solution is optimal.

Across the two studies, GPU computing produced substantial performance gains over CPU-based approaches. The CP 2026 work achieved speedups of up to an order of magnitude on challenging combinatorial optimization benchmarks, while the companion study demonstrated large gains on the Traveling Salesman Problem with Time Windows. Together, the results show how modern GPU hardware can expand the scale of problems that can be addressed efficiently with general-purpose dynamic programming and decision-diagram methods.

Learn more: Read Carnegie Mellon University’s coverage of the research.