Wednesday 08 December 2010, 4pm-5.30pm
NAB 2.06, New Academic Building
Professor John Hooker
Professor of Operations Research
Tepper School of Business, Carnegie Mellon University
Personal Profile
Abstract:
Multivalued decision diagrams (MDDs) have recently shown promise as a new approach to discrete optimization. They combine propagation ideas from constraint programming with relaxation ideas from mathematical programming. After an introduction to MDDs and their historical use for circuit analysis and product configuration, I will illustrate how MDDs can be used for propagation, relaxation, a feasibility heuristic, and a guide to branching. Computational experiments to date show that MDDs yield substantial speedups for solving vertex colouring and employee scheduling problems, provide an effective feasibility heuristic for set covering problems, and permit in-depth postoptimality analysis. I will conclude by describing nonserial MDDs and their connection with nonserial dynamic programming, tree width, induced width, and related concepts.