Table of Contents
Constraint Programming: An Oz Perspective
Overview
Overview Part I: Getting Started
Overview Part I: Getting Started
Combinatorial Problems
Examples
SAT
Timetabling
Scheduling
Puzzle Solving: Example SEND + MORE = MONEY
SEND + MORE = MONEY
Overview Part I: Getting Started
Modeling
A Model for MONEY
A Model for MONEY (continued)
Solution for MONEY
A Different Model for MONEY: Idea
A Different Model for MONEY: Idea
A Different Model for MONEY
A Different Model for MONEY (continued)
Variation: Combinatorial Optimization SEND + MOST = MONEY
Overview Part I: Getting Started
SAT
Local Search
Local Search
Local Search
Local Search
Local Search
Global Search
Global Search
Global Search
Search Graph
Global Search
Global Search
Global Search
Global Search
Search Tree
Exploration of Search Tree
Overview Part I: Getting Started
Constraint Programming
PPT Slide
Domain Restriction
Domain Restriction
Pruning
Pruning
The Constraint Programming Principle
S E N D + M O R E = M O N E Y
S E N D + M O R E = M O N E Y
S E N D + M O R E = M O N E Y
S E N D + M O R E = M O N E Y
S E N D + M O R E = M O N E Y
S E N D + M O R E = M O N E Y
S E N D + M O R E = M O N E Y
S E N D + M O R E = M O N E Y
S E N D + M O R E = M O N E Y
Where Do We Go From Here?
Demos
Constraint Programming Systems
Constraint Programming Language Oz
Programming System DFKI Oz
Further Reading
Overview
Overview Part II: Constraint Propagation
Overview Part II: Constraint Propagation
Issues
Completeness
Overview Part II: Constraint Propagation
Basic Constraints vs. Propagators
Current Domain
Example Session: Basic Constraints vs. Propagators
Overview Part II: Constraint Propagation
Domain vs. Interval Consistency
Domain Consistency
Domain Consistency
Interval Consistency
Interval Consistency
Example Session: Domain vs. Interval Consistency
Overview Part II: Constraint Propagation
Propagator Classes
0/1 Propagators
All 0/1 Propagators
Symbolic Propagators Example: The “Element” Propagator
More Symbolic Propagators
Arithmetic Propagators
Scheduling Propagators
Reified Constraints
More Reified Constraints
Overview Part II: Constraint Propagation
Case Study: Domain-Consistent Sum
Propagator Interface
CPI of DFKI Oz
Domain-Consistent Sum: Idea
Defining a Class AddProp
Implementing Propagation for AddProp
Actual Propagation Code for AddProp
Using Domain-Consistent Sum
Case Study Domain-Consistent Sum: Summary
Further Reading
Overview
Overview Part III: Tree Search
Overview Part III: Tree Search
PPT Slide
Overview Part III: Tree Search
Timetabling: Problem
Timetabling: Model
Timetabling: Implementation
Case Study Timetabling: Summary
Further Reading
Overview
Overview Part IV: Constraint Programming Techniques
Overview Part IV: Constraint Programming Techniques
Symmetries
Example: Grocery Puzzle
Model for Grocery Puzzle
Solution to Grocery Puzzle
Performance of Symmetry Breaking
Overview Part IV: Constraint Programming Techniques
Parameterized Scripts
Example: N Queens
Model for N Queens: Idea
Model for N Queens
Solution to N Queens
Parameterized Scripts
Overview Part IV: Constraint Programming Techniques
Multi-level Distribution
Example: Map Coloring
A Model for Map Coloring
Solution Strategy for Map Coloring
Solution to Map Coloring
Multi-level Distribution
Overview Part IV: Constraint Programming Techniques
Redundant Constraints
Example: Fractions
Model for Fractions
Additional Constraints for Fractions
PPT Slide
Redundant Constraints
Overview Part IV: Constraint Programming Techniques
User-defined Distributors
Examples of Distributors
Implementation of Distributors
Overview Part IV: Constraint Programming Techniques
Problem Characteristics
Techniques for Handling Precedence
Techniques for Handling Capacity
Techniques for Handling Optimization
Demo: Building A Bridge
Demo: MT10
Scheduling Demo
Summary Scheduling
Further Reading
Overview
Overview Part V: Programming Search Engines
First Solution Depth-First Search
All Solution Depth-First Search
Branch-And-Bound
Branch-and-Bound: Ordering
Branch-and-Bound: Implementation
Recomputation-based Search
Recomputation-based Search
Recomputation-based Search
Recomputation-based Search: Demo
Limited Discrepancy Search
Limited Discrepancy Search
Limited Discrepancy Search
Limited Discrepancy Search
Limited Discrepancy Search
Limited Discrepancy Search
LDS: Implementation
Programming Search Engines: Summary
Further Reading
Overview
Personal Remarks on Constraint Programming in Oz
Research Directions
Further Information
|