- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Combinatorial Problem Solving with Serial and Nonserial...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Combinatorial Problem Solving with Serial and Nonserial Decision Diagrams Hooker, John
Description
Decision diagrams (DDs) are an old concept in computer science but in recent years have been repurposed as a novel approach to combinatorial optimization and constraint solving. Part 1 of this talk is a brief survey of developments in this area. It covers DD basics, relaxed and restricted DDs, DD-based branch and bound, DD-based Lagrangian relaxation, and DD-based constraint propagation in constraint programming. Part 2 describes recent research that generalizes the serial DDs of previous work to nonserial DDs. These can achieve dramatic speedups on problems with small treewidth; that is, problems in which the variables are loosely coupled. Computational results are presented.
Item Metadata
| Title |
Combinatorial Problem Solving with Serial and Nonserial Decision Diagrams
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2026-01-13
|
| Description |
Decision diagrams (DDs) are an old concept in computer science but in recent years have been repurposed as a novel approach to combinatorial optimization and constraint solving. Part 1 of this talk is a brief survey of developments in this area. It covers DD basics, relaxed and restricted DDs, DD-based branch and bound, DD-based Lagrangian relaxation, and DD-based constraint propagation in constraint programming. Part 2 describes recent research that generalizes the serial DDs of previous work to nonserial DDs. These can achieve dramatic speedups on problems with small treewidth; that is, problems in which the variables are loosely coupled. Computational results are presented.
|
| Extent |
59.0 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Carnegie Mellon University
|
| Series | |
| Date Available |
2026-01-19
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0451304
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International