2024-2025

Willem-Jan VAN HOEVE - Carnegie Mellon University 

Tuesday, October 1 2024 from 12pm to 1pm

Title: Decision Diagrams for Discrete Optimization

Abstract: Over the last decade, decision diagram-based optimization has emerged as a competitive novel paradigm for solving combinatorial optimization problems.  This presentation will provide an overview of this new methodology and its applications.  We start with describing a generic branch-and-bound framework based on decision diagrams: working from a state-based formulation (e.g., a dynamic program), relaxed decision diagrams provide dual bounds, restricted decision diagrams provide primal bounds, and an exact search is defined based on the nodes of the diagrams.  We demonstrate that this approach outperforms or is competitive with state of the art solvers on various problem domains including the maximum independent set problem and single-machine scheduling.  We will also discuss how an extension of this method called 'column elimination' can be integrated with a linear programming solver to obtain strong dual bounds for large-scale integer programming problems, including vehicle routing applications.