Parallelism in Linear and Mixed Integer Programming
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
LP is mostly a solved problem in practice but the interior‑point (Barrier) solver gains from matrix‑matrix kernels while Simplex relies on cheap sparse LU updates; on a quad‑core i7 Barrier averages ~5% faster, but its Cholesky factorization scales poorly (4 cores 1.51x, 12 cores 1.7x) and the crossover phase is dominated by Simplex work. MIP parallelism is limited because the root‑node dominates runtime; embarrassingly parallel search gives modest speedups (4 cores ~2.2x, 12 cores ~3.3x) though random‑seed variance can change runtime 22x.
AI-written summary · about
chapters (31)
- 0:00Intro
- 0:53Problem Statement - MIP
- 1:29Three Important Characteristics
- 2:45Linear Programming
- 4:27LP Mostly a Solved Problem SGM: Schedule Generation Model 157323 rows, 182812 columns
- 7:24MIP solution framework: LP based Branch-and-Bound
- 10:37MIP Definitely Not a Solved Problem
- 11:46Financial Impact
- 13:07Throw Hardware at the Problem?
- 13:53Simplex Steps
- 16:08Barrier Steps
- 17:38For Any LP/MIP
- 18:50Comparison of Steps
- 21:32Performance Comparison
- 23:52Exclude Simpler Models
- 24:58Peak Performance
- 27:01Parallel Barrier Performance
- 27:25Barrier Runtime Breakdown For models that require more than 1s
- 33:43Concurrent Optimization
- 34:50MIP - Embarrassingly Parallel?
- 35:04Parallel MIP - Reality
- 35:39Parallel Speedup By Model (P=12)
- 36:53A Bit of Noise Mixed In
- 40:30Root Computations
- 41:40Example - Cutting Planes
- 43:39Example - Symmetry
- 46:05MIP Speedup 2009-Present
- 47:03The Nature of the Improvements
- 47:48Concurrent MIP
- 49:37Distributed MIP
- 51:16Conclusions
related talks
06mInteger Programming to optimize costs in Kubernetes
01h 05mGraph Algorithms in the MPC Model
26mParallel Declarative Solutions of Sequencing Problems using Multi-valued Decisio
01h 27mKeynote: Multidimensional Parallel Standard C++
47mMassively Parallel Evaluation of Relational Queries I
29mParallel Cluster-BFS and Applications to Shortest Paths
21mMassive proofs for the masses
01h 21mComputational Complexity in Theory and in Practice