Speaker: John Hooker, Carnegie Mellon University
Title: Discrete Optimization with Decision Diagrams
We show how binary and multivaled decision diagram can form the basis for a general discrete optimization method. This approach combines elements of integer programming (IP), constraint programming (CP), and dynamic programming (DP). The problem is formulated for the decision diagram using state variables as in DP. Optimization bounds and primal heuristics are used as in IP but are obtained from relaxed and restricted decision diagrams, respectively. Constraint propagation is stronger than in CP because it is based on deleting arcs from a decision diagram rather than domain filtering. We report preliminary computational results on the maximum independent set problem.
This is joint work with David Bergman, Andre Cire, and Willem van Hoeve.
For additional information contact: Erin Delisle