Modern GPUs Extend the Reach of Dynamic Programming for Complex Optimization

Researchers at Carnegie Mellon University (CMU) and the University of Connecticut (UConn) have developed new methods that use the parallel computing power of graphics processing units, or GPUs, to accelerate dynamic programming, a fundamental approach for solving complex optimization problems. The advances make dynamic programming a more practical general-purpose tool for complex optimization problems such as production planning, scheduling, and finding efficient routes through transportation networks.

Two recent publications, “Complete Anytime Decision Diagram Search with GPU-Accelerated State Expansion” and  “GPU-Accelerated Relaxed Decision Diagrams for Branch-and-Bound Optimization,” which received the Best Paper Award at the 2026 CP Conference in Lisbon. Both papers were written by Fabio Tardivo and Laurent Michel of UConn, and Willem-Jan van Hoeve, Carnegie Bosch Professor of Operations Research from CMU’s Tepper School of Business.

Dynamic programming, pioneered by mathematician Richard Bellman in the 1950s, solves complex problems by breaking them into a sequence of smaller decisions and using information from earlier computations to avoid unnecessary work. It has led to powerful algorithms for specific problems, including DNA sequence alignment, where it can determine how closely two genetic sequences correspond.

Applying dynamic programming more generally, however, presents a major computational challenge: the number of possibilities can grow extraordinarily quickly. Specialized algorithms control this growth by exploiting the structure of individual problems. But increasingly large computer memories have begun to change what is computationally practical, motivating researchers to develop general-purpose approaches in which users describe the decisions in a problem and a solver searches for the best solution.

Two new companion studies take another step in that direction, showing how GPUs can dramatically accelerate different parts of this search. Originally developed for computer graphics and now central to artificial intelligence, GPUs can perform large numbers of calculations simultaneously—a capability well suited to exploring many possible decisions at once.

In the first study, the researchers developed a method that organizes the search so large groups of possibilities can be processed simultaneously on a GPU. Tested on difficult routing problems in which locations must be visited within specified time periods, the GPU implementation was 10 to 20 times faster than the corresponding sequential implementation.

“Our goal is not simply to make one optimization algorithm faster,” said Willem-Jan van Hoeve, Professor of Operations Research at Carnegie Mellon University’s Tepper School of Business. “We are interested in whether advances in computer hardware can make dynamic programming a practical, general-purpose way to model and solve optimization problems.”

The second study addresses a complementary challenge: determining whether a solution is verifiably the best possible one. The researchers showed that GPUs can accelerate calculations that rule out large portions of the search and help prove that a solution is optimal. In tests, the method achieved speedups of up to an order of magnitude over CPU-based approaches. The study, “GPU-Accelerated Relaxed Decision Diagrams for Branch-and-Bound Optimization,” received the Best Paper Award at CP 2026.

Together, the studies show that GPUs can accelerate both the search for high-quality solutions and the work needed to prove optimality. Combined with much larger computer memory capacity, these advances expand the range of problems that can be tackled efficiently with dynamic programming, bringing it closer to becoming a broadly applicable way to model and solve complex optimization problems.

###

Summarized from:

Fabio Tardivo, Laurent Michel, and Willem-Jan van Hoeve, “Complete Anytime Decision Diagram Search with GPU-Accelerated State Expansion,” Proceedings of CPAIOR, 2026. https://doi.org/10.1007/978-3-032-27242-3_34

Fabio Tardivo, Laurent Michel, and Willem-Jan van Hoeve, “GPU-Accelerated Relaxed Decision Diagrams for Branch-and-Bound Optimization,” Proceedings of CP, 2026. Best Paper Award. https://doi.org/10.4230/LIPIcs.CP.2026.53