Finding Adversarial Inputs for Heuristics Using Multi-level Optimization

Explore a cutting-edge research presentation on finding adversarial inputs for heuristics using multi-level optimization. Delve into the development and application of MetaOpt, a system designed to analyze heuristics in production environments. Learn how MetaOpt efficiently encodes heuristics and optimal solutions for solver analysis, revealing performance gaps and corresponding adversarial inputs. Discover the system's built-in optimizations that enable it to scale to practical problem sizes. Examine case studies across three domains: traffic engineering, vector bin packing, and packet scheduling. Gain insights into how MetaOpt uncovered a 30% capacity inefficiency in a production traffic engineering heuristic and how researchers used these findings to reduce the performance gap by 12.5 times. Understand the implications of adversarial inputs in vector bin packing heuristics and the resulting new lower bound on performance. This 17-minute presentation from USENIX's NSDI '24 conference offers valuable knowledge for practitioners and researchers interested in optimizing heuristic algorithms and improving system performance.