Decision Diagrams for Optimization (Artificial Intelligence: Foundations, Theory, and Algorithms)

This book introduces a novel approach to discrete optimization, providing both theoretical insights and algorithmic developments that lead to improvements over state-of-the-art technology. The authors present chapters on the use of decision diagrams for combinatorial optimization and constraint programming, with attention to general-purpose solution methods as well as problem-specific techniques. The book will be useful for researchers and practitioners in discrete optimization and constraint programming. "__Decision Diagrams for Optimization is one of the most exciting developments emerging from constraint programming in recent years. This book is a compelling summary of existing results in this space and a must-read for optimizers around the world.__" [Pascal Van Hentenryck] This Book Introduces A Novel Approach To Discrete Optimization, Providing Both Theoretical Insights And Algorithmic Developments That Lead To Improvements Over State-of-the-art Technology. The Authors Present Chapters On The Use Of Decision Diagrams For Combinatorial Optimization And Constraint Programming, With Attention To General-purpose Solution Methods As Well As Problem-specific Techniques. The Book Will Be Useful For Researchers And Practitioners In Discrete Optimization And Constraint Programming. Decision Diagrams For Optimization Is One Of The Most Exciting Developments Emerging From Constraint Programming In Recent Years. This Book Is A Compelling Summary Of Existing Results In This Space And A Must-read For Optimizers Around The World. [pascal Van Hentenryck]. Introduction -- Historical Overview -- Exact Decision Diagrams -- Relaxed Decision Diagrams -- Restricted Decision Diagrams -- Branch-and-bound Based On Decision Diagrams -- Variable Ordering -- Recursive Modeling -- Mdd-based Constraint Programming -- Mdd Propagation For Sequence Constraints -- Sequencing And Single-machine Scheduling -- Index. By David Bergman, Andre A. Cire, Willem-jan Van Hoeve, John Hooker. Front Matter....Pages i-xii Introduction....Pages 1-9 Historical Overview....Pages 11-22 Exact Decision Diagrams....Pages 23-54 Relaxed Decision Diagrams....Pages 55-81 Restricted Decision Diagrams....Pages 83-94 Branch-and-Bound Based on Decision Diagrams....Pages 95-122 Variable Ordering....Pages 123-136 Recursive Modeling....Pages 137-156 MDD-Based Constraint Programming....Pages 157-181 MDD Propagation for sequence Constraints....Pages 183-204 Sequencing and Single-Machine Scheduling....Pages 205-234 Back Matter....Pages 235-254