Decision Diagrams for Optimization | springerprofessional.de

Springer Professional

Top

2016 | Book

Read chapter Read first chapter

Decision Diagrams for Optimization

Authors: David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Publisher: Springer International Publishing

Book Series : Artificial Intelligence: Foundations, Theory, and Algorithms

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access

About this book

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]

Advertisement

Table of Contents

Frontmatter

Chapter 1. Introduction

Abstract

This introductory chapter explains the motivation for developing decision diagrams as a new discrete optimization technology. It shows how decision diagrams implement the five main solution strategies of general-purpose optimization and constraint programming methods: relaxation, branching search, constraint propagation, primal heuristics, and intelligent modeling. It presents a simple example to illustrate how decision diagrams can be used to solve an optimization problem. It concludes with a brief outline of the book.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 2. Historical Overview

Abstract

This chapter provides a brief review of the literature on decision diagrams, primarily as it relates to their use in optimization and constraint programming. It begins with an early history of decision diagrams and their relation to switching circuits. It then surveys some of the key articles that brought decision diagrams into optimization and constraint solving. In particular it describes the development of relaxed and restricted decision diagrams, the use of relaxed decision diagrams for enhanced constraint propagation and optimization bounding, and the elements of a general-purpose solver. It concludes with a brief description of the role of decision diagrams in solving some Markov decision problems in artificial intelligence.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 3. Exact Decision Diagrams

Abstract

In this chapter we introduce a modeling framework based on dynamic programming to compile exact decision diagrams. We describe how dynamic programming models can be used in a top-down compilation method to construct exact decision diagrams. We also present an alternative compilation method based on constraint separation. We illustrate our framework on a number of classical combinatorial optimization problems: maximum independent set, set covering, set packing, single machine scheduling, maximum cut, and maximum 2-satisfiability.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 4. Relaxed Decision Diagrams

Abstract

Bounds on the optimal value are often indispensable for the practical solution of discrete optimization problems, as for example in branch-and-bound procedures. This chapter explores an alternative strategy of obtaining bounds through relaxed decision diagrams, which overapproximate both the feasible set and the objective function of the problem. We first show how to modify the top-down compilation from the previous chapter to generate relaxed decision diagrams. Next, we present three modeling examples for classical combinatorial optimization problems, and provide a thorough computational analysis of relaxed diagrams for the maximum independent set problem. The chapter concludes by describing an alternative method to generate relaxed diagrams, the incremental refinement procedure, and exemplify its application to a single-machine makespan problem.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 5. Restricted Decision Diagrams

Abstract

This chapter presents a general-purpose methodology for obtaining a set of feasible solutions to a discrete optimization problems using restricted decision diagrams. A restricted diagram can be perceived as a counterpart of the concept of relaxed diagrams introduced in previous chapters, and represents an under approximation of the feasible set, the objective function, or both. We first show how to modify the top-down compilation approach to generate restricted diagrams that observe an input-specified width. Next, we provide a computational study of the bound provided by restricted diagrams, particularly focusing on the set covering and set packing problems.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 6. Branch-and-Bound Based on Decision Diagrams

Abstract

This chapter proposes an alternative branch-and-bound method in which decision diagrams take over the functions of the traditional relaxations and heuristics used in general-purpose optimization techniques. In particular, we show an enumeration scheme that branches on the nodes of a relaxed decision diagram, as opposed to variable-value assignments as in traditional branch-and-bound. We provide a computational study of our method on three classical combinatorial optimization problems, and compare our solution technology with mixed-integer linear programming. Finally, we conclude by showing how the diagram-based branch-and-bound procedure is suitable for parallelization, and provide empirical evidence of almost linear speedups on the maximum independent set problem.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 7. Variable Ordering

Abstract

One of the most important parameters that determines the size of a decision diagram is the variable ordering. In this chapter we formally study the impact of variable ordering on the size of exact decision diagrams for the maximum independent set problem. We provide worst-case bounds on the size of the exact decision diagram for particular classes of graphs. For general graphs, we show that the size is bounded by the Fibonacci numbers. Lastly, we demonstrate experimentally that variable orderings that produce small exact decision diagrams also produce better bounds from relaxed decision diagrams.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 8. Recursive Modeling

Abstract

This chapter focuses on the type of recursive modeling that is required for solution by decision diagrams. It presents a formal development that highlights how solution by decision diagrams differs from traditional enumeration of the state space. It illustrates the versatility of recursive modeling with examples: single facility scheduling, scheduling with sequence-dependent setup times, and minimum bandwidth problems. It shows how to represent state-dependent costs with canonical arc costs in a decision diagram, a technique that can sometimes greatly simplify the recursion, as illustrated by a textbook inventory management problem. It concludes with an extension to nonserial recursive modeling and nonserial decision diagrams.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 9. MDD-Based Constraint Programming

Abstract

This is the first of three chapters that apply decision diagrams in the context of constraint programming. This chapter starts by providing a background of the solving process of constraint programming, focusing on consistency notions and constraint propagation. We then extend this methodology to MDD-consistency and MDD-based constraint propagation. We present MDD propagation algorithms for specific constraint types, including linear inequalities, ALLDIFFERENT, AMONG, and ELEMENT constraints, and experimentally demonstrate how MDD propagation can improve conventional domain propagation.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 10. MDD Propagation for sequence Constraints

Abstract

In this chapter we present a detailed study of MDD propagation for the sequence constraint. This constraint can be applied to combinatorial problems such as employee rostering and car manufacturing. It will serve to illustrate the main challenges when studying MDD propagation for a new constraint type: Tractability, design of the propagation algorithm, and practical efficiency. In particular, we show in this chapter that establishing MDD consistency for sequence is NP-hard, but fixed-parameter tractable. Furthermore, we present an MDD propagation algorithm that may not establish MDD consistency, but is highly effective in practice when compared to conventional domain propagation.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Chapter 11. Sequencing and Single-Machine Scheduling

Abstract

In this chapter we provide an in-depth study of representing and handling single-machine scheduling and sequencing problems with decision diagrams. We provide exact and relaxed MDD representations, together with MDD filtering algorithms for various side constraints, including time windows, precedence constraints, and sequence-dependent setup times. We extend a constraint-based scheduling solver with these techniques, and provide an experimental evaluation for a wide range of problems, including the traveling salesman problem with time windows, the sequential ordering problem, and minimum-tardiness sequencing problems. The results demonstrate that MDD propagation can improve a state-of-the-art constraint based scheduler by orders of magnitude in terms of solving time.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker

Backmatter

Title: Decision Diagrams for Optimization
Authors: David Bergman
Andre A. Cire
Willem-Jan van Hoeve
John Hooker
Copyright Year: 2016
Publisher: Springer International Publishing
Electronic ISBN: 978-3-319-42849-9
Print ISBN: 978-3-319-42847-5
DOI: https://doi.org/10.1007/978-3-319-42849-9

Premium Partner