The above figure compares the meta-algorithm developed by Hochbaum’s research group, Meta-Sweep-Algorithm (MSA), to Google’s OR-tools and one leading fast Algorithm of Clark-Wright (CW). The figure shows the running time required to generate a solution for the Vehicle Routing Problem across 46,000 instances. Each dot corresponds to one instance. The better algorithmic results can be found in the lower left of the figure. The algorithm’s running time improves as you move further to the left, and the lower on the vertical axis, the better the value of the routing generated. As compared with Google and CW, the orange dots, for MSA, are located further to the lower left of the chart, demonstrating the effectiveness of the Meta-Sweep Algorithm.

Led by Distinguished Professor Dorit Hochbaum, the new Meta-Algorithms Research Group is advancing the AI Institute for Advances in Optimization mission by developing automatic algorithm/model selection for optimization problems and machine learning tasks. The group addresses real-world issues, including Vehicle Routing, Multi-Agent Pathfinding and Classification, Satisfiability (SAT), Travelling Salesperson Problem (TSP), and Planning.

The Meta-Algorithms Research Group organizes biweekly seminars and has research subgroups that hold regular meetings during the academic year. Professor Hochbaum and her research group co-authored the paper, Fast algorithms for the Capacitated Vehicle Routing Problem using Machine Learning Selection of Algorithm’s Parameters, which was recently accepted for publication and will also appear in KDIR 2022. 

Learn More

Meta-Algorithms Research Group Website