Parallel Declarative Solutions of Sequencing Problems using Multi-valued Decisio
summary
A time-bounded solver is built that repairs destroyed permutations by combining Multi-valued Decision Diagrams with Large Neighborhood Search and GPU parallelism; it launches thousands of independent LNS repairs (example: width-5 MDDs with ~10,000 copies on the GPU) and also runs wider MDDs on CPU threads. Evaluated with a 60s timeout on sequential ordering, open-shop and cable wiring benchmarks, it often finds near-best solutions in ~30s (average ~50% gap across instances), beating some state-of-the-art LNS/CP baselines on two of three benchmarks.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 0:45Overview
- 1:04Problem
- 1:39Context
- 3:24Transition System
- 5:28Semantics
- 6:08Multivalued Decision Diagrams
- 7:19Large Neighbor Search
- 8:24Restrict MDD
- 10:39Perform Large Neighbor Search
- 11:33CPU Large Neighbor Search
- 13:21GPU Implementation
- 13:54Benefits vs Backtracking
- 15:00Tradeoff
- 16:06Tradeoff Benefits
- 17:30Example
- 22:25Observations
related talks
16mDecouple and Decompose: Scaling Resource Allocation with DeDe
13mA Fast Solver-Free Algorithm for Traffic Engineering in Large-Scale Data Center Network
16mAccelerating Design Space Exploration for LLM Training Systems with Multi-experiment...
21mMassive proofs for the masses
22mCustom Pipeline Parallelism for Frontier-Scale Model Serving
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
32mDynamic Scheduling for Large Language Model Serving
58mParallelism in Linear and Mixed Integer Programming