Highly Scalable Branch-and-Bound for Maximum Monomial Agreement
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Presents an exact solver for Maximum Monomial Agreement inside LPBoost using a custom branch-and-bound with equivalence-class upper bounds, strong multiway branching and a ramp‑up phase to use massive parallelism. Implements this in the open‑source Pebble library, runs on a 22,000‑core cluster and scales nearly perfectly to about 8,000 cores, cutting hard separations to seconds or minutes (often 1–3 minutes). Also supports parallel enumeration to return the 25 best columns for faster boosting convergence.
AI-written summary · about
chapters (25)
- 0:00Intro
- 0:40Classification: Distinguish 2 Classes
- 1:34Binary Monomial
- 2:35Example: Coverage
- 3:02Maximum Monomial Agreement
- 4:40LPBoost
- 5:30Branch and Bound
- 8:39Solution Quality
- 9:09B&B Representation for MMA
- 10:22Upper Bound
- 14:15Branching
- 15:53Pebbl's Parallelism (Almost) Free
- 17:19PEBBL Features for Efficient Parallel B&B
- 18:10PEBBL Ramp-up
- 19:46Crossing over
- 20:37Hubs and Workers
- 21:17Load Balancing
- 23:32Red Sky
- 23:58Value of ramp up (no enumeration)
- 24:37Number of tree nodes hung253
- 24:57Spam, tree nodes
- 25:25Parallel Enumeration
- 26:38Enumeration Experiments
- 27:03Results: Enumeration
- 27:42Open-Source Code Available
related talks
20mFlexLLM: Token-Level Co-Serving of LLM Inference and Finetuning with SLO Guarantees
17mSolving Max-Min Fair Resource Allocations Quickly on Large Graphs
01h 05mGraph Algorithms in the MPC Model
21mMassive proofs for the masses
48mPersonalized Collaborative Learning with Affinity-Based Variance Reduction
26mParallel Declarative Solutions of Sequencing Problems using Multi-valued Decisio
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
17mSatisfiability Algorithms Based on Concentrated Shrinkage