Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2010-11 > Multivalued Decision Diagrams in Optimization
How to contact us

 

LSE 10 logo master_6


Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE

  

Enquiries: dom.events@lse.ac.uk 

  

Follow us online

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

Multivalued Decision Diagrams in Optimization

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.

Share:Facebook|Twitter|LinkedIn|
 John Hooker