ICAPS 2016 -- Tutorial #4

Title: Decision Diagrams for Discrete Optimization
Author: John Hooker

Abstract:
Decision diagrams have been used for decades as a compact representation of Boolean functions. More recently, they have emerged as a powerful tool for discrete optimization. They provide a discrete relaxation of the problem that does not require linearity or convexity. The relaxation yields useful bounds and a novel search strategy, leading to a general-purpose solver that is competitive with or superior to state-of-the-art integer and constraint programming on several classical benchmark problems. The solver accepts models in the form of a dynamic programming recursion and therefore affords an alternative approach to defeating the ìcurse of dimensionalityî in dynamic programming.

The specific application to sequencing and scheduling problems will be discussed in the following tutorial by Willem-Jan van Hoeve. Both tutorials are stand-alone presentations.

Bio:
John Hooker is Professor of Operations Research and Holleran Professor of Business Ethics at Carnegie Mellon University. His research interests include integration of optimization and constraint programming, logic-based methods for optimization and data analytics, optimization with decision diagrams, and modeling systems, as well as ethics, cross-cultural management, and musical composition. He introduced logic-based Benders decomposition, and with T. Hadûi?, decision diagrams as an optimization method. His research website is web.tepper.cmu.edu/jnh.

свернуть