Learning-Driven Algorithms for Discrete Optimization
University of Southern California
Tuesday, November 06, 2018|
4:00pm - 5:30pm
Add to Google Calendar
About the Event
This talk focuses on a novel fruitful synergy between machine learning and optimization --- in particular, how ML techniques can improve the design of algorithms for Discrete Optimization, both complete algorithms such as branch and bound as well as incomplete ones such as heuristic greedy search. Branch and Bound solvers for Mixed Integer Programs (MIP) such as CPLEX, Gurobi and SCIP are used daily across different domains and industries to find solutions with optimality guarantees for NP-hard combinatorial problems. Leveraging the plethora of rich and useful data generated during the solving process, we illustrate the potential for ML in MIP on two crucial tasks in branch and bound: branching variable selection and primal heuristic selection. Empirical results show that our novel approaches can significantly improve the performance of a solver on both heterogeneous benchmark instances as well as homogeneous families of instances. In the second part of the talk, we show how to leverage a unique combination of reinforcement learning and graph embedding to infer very effective data-driven greedy strategies for solving well-studied combinatorial optimization problems on graphs such as Minimum Vertex Cover, Max Cut and Traveling Salesman.
Bistra Dilkina is a Gabilan Assistant Professor of Computer Science at the University of Southern California and an Associate Director of the USC Center for AI in Society (CAIS), since January 2018. Before that, Dilkina was as an Assistant Professor in the College of Computing at the Georgia Institute of Technology and a co-director of the Data Science for Social Good Atlanta summer program. She received her PhD from Cornell University, and was a Post-Doctoral Associate at the Institute for Computational Sustainability. Her work spans discrete optimization, machine learning, network design, and stochastic optimization. Dilkina's research focuses on advancing the state of the art for solving real-world large-scale combinatorial optimization problems, particularly ones that arise in sustainability areas such as biodiversity conservation planning and urban planning. Dilkina is one of the junior faculty leaders in the young field of Computational Sustainability, and has co-organized workshops, tutorials, special tracks at AAAI and IJCAI, as well as a doctoral consortium on Computational Sustainability.
Faculty Sponsor: Satinder Singh
Open to: Public