Caltech Logo

Rigorous Systems Research Group (RSRG) Seminar

Thursday, April 5, 2018
12:00pm to 1:00pm
Add to Cal
Annenberg 213
Machine Learning helps Discrete Optimization
Bistra Dilkina, Assistant Professor, Computer Science, University of Southern California,

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.

For more information, please contact Yanan Sui by email at [email protected] or visit Upcoming Seminar & Events.