Parallel Hybrid Solving of Challenging Decision Problems
Project Overview
This project addressed the Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP) by encoding instances as Boolean Satisfiability (SAT) problems. To parallelise large instances across many cores, we used a technique called Cube and Conquer, which employs lookahead solvers to partition a problem into smaller, more manageable "cubes" that can then be solved independently by specialised SAT solvers. To implement this, pipelines were developed to automatically schedule this process on a high-performance computer environment.
What were the key results of your research project?
Out of 550 problem instances in the MMLIB50 dataset, most could be solved with the SAT pipelines developed (and many where able to be solved even with simpler techniques, without requiring large-scale parallelisation at all). However, for the remaining 50 instances, cube difficulty followed a power-law distribution: a small minority of cubes took disproportionately long to solve, dominating the overall runtime regardless of how many cores were available. This showed that some MRCPSP instances remain intractable even with state-of-the-art SAT solvers and substantial supercomputing resources. Parallelisation alone cannot overcome the underlying combinatorial difficulty concentrated in a handful of hard cubes.
How do you feel you have benefitted from completing this internship and has it made you consider future career paths?
This internship gave me an invaluable insight into the world of academia and what research would look like as a career. By taking on this project, it has influenced my thinking on whether I want to do a PhD in the future, and what potential topics I would be interested in.