Learning-Driven Algorithms for Discrete Optimization

Speaker: Bistra Dilkina , USC

Date: Tuesday, April 30, 2019

Time: 4:00 PM to 5:00 PM

Public: Yes

Location: 32-G449 Patil/Kiva

Event Type: Seminar

Room Description:

Host: Govind Ramnarayan, Quanquan Liu, Sitan Chen, MIT CSAIL

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Bistra Dilkina: Learning-Driven Algorithms for Discrete Optimization

Abstract: 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. I will conclude with  some new directions on 1) learning novel heuristics that apply to any MIP problem distributions, as well as 2) decision-focused learning.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms & Complexity Seminars 2018-2019.

Created by Rebecca Yadegar Email at Thursday, April 25, 2019 at 2:31 PM.