Atnaujinkite slapukų nuostatas

El. knyga: Decision Diagrams for Optimization

5.00/5 (2 ratings by Goodreads)
, , ,
Kitos knygos pagal šią temą:
Decision Diagrams for OptimizationDidesnis paveikslėlis
Kitos knygos pagal šią temą:

DRM apribojimai

  • Kopijuoti:

    neleidžiama

  • Spausdinti:

    neleidžiama

  • El. knygos naudojimas:

    Skaitmeninių teisių valdymas (DRM)
    Leidykla pateikė šią knygą šifruota forma, o tai reiškia, kad norint ją atrakinti ir perskaityti reikia įdiegti nemokamą programinę įrangą. Norint skaityti šią el. knygą, turite susikurti Adobe ID . Daugiau informacijos  čia. El. knygą galima atsisiųsti į 6 įrenginius (vienas vartotojas su tuo pačiu Adobe ID).

    Reikalinga programinė įranga
    Norint skaityti šią el. knygą mobiliajame įrenginyje (telefone ar planšetiniame kompiuteryje), turite įdiegti šią nemokamą programėlę: PocketBook Reader (iOS / Android)

    Norint skaityti šią el. knygą asmeniniame arba „Mac“ kompiuteryje, Jums reikalinga  Adobe Digital Editions “ (tai nemokama programa, specialiai sukurta el. knygoms. Tai nėra tas pats, kas „Adobe Reader“, kurią tikriausiai jau turite savo kompiuteryje.)

    Negalite skaityti šios el. knygos naudodami „Amazon Kindle“.

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. 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 optimizatio

n and constraint programming.

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.

Daugiau informacijos

"This book goes far beyond answering natural questions about how to use Decision Diagrams in Discrete Optimization: it rigorously defines a comprehensive methodology, shows impressive potential from the computational standpoint and highlights unexpected and exciting research venues. A great and inspiring read!" (Andrea Lodi, Ecole Polytechnique de Montreal) "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, University of Michigan) "This book provides an excellent demonstration of how the concepts and tools of one research community can cross into another, yielding powerful insights and ideas ... The authors show how the main strategies used in discrete optimization, including problem relaxation, branching search, constraint propagation, primal solving, and problem-specific modeling, can be adapted and cast into a decision diagram framework." (Randal E. Bryant, Carnegie Mellon University)
1 Introduction
1(10)
1.1 Motivation for the Book
1(1)
1.2 A New Solution Technology
2(2)
1.3 An Example
4(4)
1.4 Plan of the Book
8(3)
2 Historical Overview
11(12)
2.1 Introduction
11(1)
2.2 Origins of Decision Diagrams
12(3)
2.3 Decision Diagrams in Optimization
15(8)
2.3.1 Early Applications
15(1)
2.3.2 A Discrete Optimization Method
16(1)
2.3.3 Decision Diagrams in Constraint Programming
17(1)
2.3.4 Relaxed Decision Diagrams
18(1)
2.3.5 A General-Purpose Solver
19(2)
2.3.6 Markov Decision Processes
21(2)
3 Exact Decision Diagrams
23(32)
3.1 Introduction
23(1)
3.2 Basic Definitions
24(1)
3.3 Basic Concepts of Decision Diagrams
25(2)
3.4 Compiling Exact Decision Diagrams
27(5)
3.4.1 Dynamic Programming
28(2)
3.4.2 Top-Down Compilation
30(2)
3.5 Maximum Independent Set Problem
32(2)
3.6 Set Covering Problem
34(3)
3.7 Set Packing Problem
37(2)
3.8 Single-Machine Makespan Minimization
39(3)
3.9 Maximum Cut Problem
42(2)
3.10 Maximum 2-Satisfiability Problem
44(2)
3.11 Compiling Decision Diagrams by Separation
46(4)
3.12 Correctness of the DP Formulations
50(5)
4 Relaxed Decision Diagrams
55(28)
4.1 Introduction
55(2)
4.2 Top-Down Compilation of Relaxed DDs
57(2)
4.3 Maximum Independent Set
59(1)
4.4 Maximum Cut Problem
60(3)
4.5 Maximum 2-Satisfiability Problem
63(1)
4.6 Computational Study
64(10)
4.6.1 Merging Heuristics
64(1)
4.6.2 Variable Ordering Heuristic
65(1)
4.6.3 Bounds vs. Maximum BDD Width
66(1)
4.6.4 Comparison with LP Relaxation
67(7)
4.7 Compiling Relaxed Diagrams by Separation
74(9)
4.7.1 Single-Machine Makespan Minimization
76(7)
5 Restricted Decision Diagrams
83(12)
5.1 Introduction
83(2)
5.2 Top-Down Compilation of Restricted DDs
85(1)
5.3 Computational Study
86(9)
5.3.1 Problem Generation
87(2)
5.3.2 Solution Quality and Maximum BDD Width
89(1)
5.3.3 Set Covering
90(2)
5.3.4 Set Packing
92(3)
6 Branch-and-Bound Based on Decision Diagrams
95(28)
6.1 Introduction
95(1)
6.2 Sequential Branch-and-Bound
96(1)
6.3 Exact Cutsets
97(1)
6.4 Enumeration of Subproblems
98(2)
6.4.1 Exact Cutset Selection
100(1)
6.5 Computational Study
100(9)
6.5.1 Results for the MISP
101(3)
6.5.2 Results for the MCP
104(4)
6.5.3 Results for MAX-2SAT
108(1)
6.6 Parallel Branch-and-Bound
109(14)
6.6.1 A Centralized Parallelization Scheme
112(1)
6.6.2 The Challenge of Effective Parallelization
113(1)
6.6.3 Global and Local Pools
113(1)
6.6.4 Load Balancing
114(2)
6.6.5 DDX10: Implementing Parallelization Using X10
116(1)
6.6.6 Computational Study
116(7)
7 Variable Ordering
123(14)
7.1 Introduction
123(2)
7.2 Exact BDD Orderings
125(5)
7.3 Relaxed BDD Orderings
130(1)
7.4 Experimental Results
131(6)
7.4.1 Exact BDDs for Trees
132(1)
7.4.2 Exact BDD Width Versus Relaxation BDD Bound
132(2)
7.4.3 Relaxation Bounds
134(3)
8 Recursive Modeling
137(20)
8.1 Introduction
137(2)
8.2 General Form of a Recursive Model
139(2)
8.3 Examples
141(5)
8.3.1 Single-Machine Scheduling
141(1)
8.3.2 Sequence-Dependent Setup Times
142(2)
8.3.3 Minimum Bandwidth
144(2)
8.4 State-Dependent Costs
146(7)
8.4.1 Canonical Arc Costs
147(4)
8.4.2 Example: Inventory Management
151(2)
8.5 Nonserial Recursive Modeling
153(4)
9 MDD-Based Constraint Programming
157(26)
9.1 Introduction
157(1)
9.2 Constraint Programming Preliminaries
158(6)
9.3 MDD-Based Constraint Programming
164(9)
9.3.1 MDD Propagation
166(1)
9.3.2 MDD Consistency
167(2)
9.3.3 MDD Propagation by Intersection
169(4)
9.4 Specialized Propagators
173(5)
9.4.1 Equality and Not-Equal Constraints
173(1)
9.4.2 Linear Inequalities
174(1)
9.4.3 Two-Sided Inequality Constraints
174(1)
9.4.4 Alldifferent Constraint
175(1)
9.4.5 Among Constraint
176(1)
9.4.6 Element Constraint
177(1)
9.4.7 Using Conventional Domain Propagators
178(1)
9.5 Experimental Results
178(5)
10 MDD Propagation for Sequence Constraints
183(22)
10.1 Introduction
183(3)
10.2 MDD Consistency for Sequence Is NP-Hard
186(3)
10.3 MDD Consistency for Sequence Is Fixed Parameter Tractable
189(1)
10.4 Partial MDD Filtering for Sequence
190(6)
10.4.1 Cumulative Sums Encoding
191(1)
10.4.2 Processing the Constraints
192(2)
10.4.3 Formal Analysis
194(2)
10.5 Computational Results
196(9)
10.5.1 Systems of Sequence Constraints
198(3)
10.5.2 Nurse Rostering Instances
201(2)
10.5.3 Comparing MDD Filtering for Sequence and Among
203(2)
11 Sequencing and Single-Machine Scheduling
205(30)
11.1 Introduction
205(2)
11.2 Problem Definition
207(1)
11.3 MDD Representation
208(3)
11.4 Relaxed MDDs
211(3)
11.5 Filtering
214(4)
11.5.1 Filtering Invalid Permutations
214(1)
11.5.2 Filtering Precedence Constraints
215(1)
11.5.3 Filtering Time Window Constraints
215(1)
11.5.4 Filtering Objective Function Bounds
216(2)
11.6 Inferring Precedence Relations from Relaxed MDDs
218(1)
11.7 Refinement
219(2)
11.8 Encoding Size for Structured Precedence Relations
221(1)
11.9 Application to Constraint-Based Scheduling
222(13)
11.9.1 Experimental Setup
223(1)
11.9.2 Impact of the MDD Parameters
224(3)
11.9.3 Traveling Salesman Problem with Time Windows
227(1)
11.9.4 Asymmetric Traveling Salesman Problem with Precedence Constraints
228(2)
11.9.5 Makespan Problems
230(3)
11.9.6 Total Tardiness
233(2)
References 235(14)
Index 249
Daugiau apie elektronines knygas Daugiau apie elektronines knygas
Pastovi nuoroda: https://www.kriso.lt/db/97833194284992e.html
Raktažodžiai: