Finding Adversarial Inputs for Heuristics using Multi-level Optimization
Talkat 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24) · 2024-04-16..04-18·
summary
MetaOpt is a solver-backed tool that encodes heuristics and an optimal baseline as a bilevel optimization, automatically rewrites inner problems into single-level constraints for Gurobi or Z3, and searches a quantized input space for adversarial cases. It finds concrete gaps—up to 30% capacity loss for a production demand pinning TE heuristic—then recommends a threshold fix that reduces the gap by ~12.5× and yields measured delay improvements (2.5×), and it proves new lower bounds for vector bin packing.
AI-written summary · about
chapters (9)
- 0:00Adversarial inputs for heuristics
- 2:12MetaOpt and its purpose
- 3:58MetaOpt as multi-level optimization
- 6:27Efficient optimization solving
- 8:54Scaling MetaOpt techniques
- 10:18MetaOpt use cases
- 12:24Demand pinning case study
- 15:09MetaOpt future directions
- 16:13Q&A
related talks
15mHeuristic Analysis from Source Code via Symbolic-Guided Optimization
25mStructure-guided Local Improvement for Maximum Satisfiability
30mAdmiral-Driven ML Framework for Marine Operations
01h 04mProtective Optimization Technologies
18mResizing Your Expectations: Mastering Timing Closure with OpenROAD's Evolving Optimizer
33mInteger Programming to Optimize Costs in Kubernetes
14mALERT: Machine Learning-Enhanced Risk Estimation for Databases Supporting...
30mMachine Learning Techniques for Class Imbalances & Adversaries