Goal of Appetizer

Constraint Programming with

Underlying principles
Mozart – An Appetizer

Sketch of how to do in Oz

Modeling techniques
Christian Schulte
Mozart advantages and disadvantages
KTH – Royal Institute of Technology, Sweden
[email protected]
…no time for hands-on tutorial

Constraint Programming Send More Money (SMM)

Modeling and solving combinatorial
Find distinct digits for letters, such that
problems
SEND
start with a first toy problem
+ MORE
= MONEY

Constraint Model for SMM Solving SMM

Variables and values
Find values for variables

S,E,N,D,M,O,R,Y ∈ {0,…,9} such that

Constraints all constraints satisfied
distinct(S,E,N,D,M,O,R,Y)
1000×S+100×E+10×N+D
+ 1000×M+100×O+10×R+E
Enumerate values, test constraints…
= 10000×M+1000×O+100×N+10×E+Y …poor: we can do better than that!
S≠0 M≠0

1
Constraint Programming Propagation for SMM

Compute with set of possible values
Results in

as opposed to assignments S=9 E∈{4,…,7} N∈{5,…,8} D∈{2,…,8}

Prune impossible values M=1 O=0 R∈{2,…,8} Y∈{2,…,8}

constraint propagation

Search
Propagation alone not sufficient!

distribute search tree of
create simpler sub-problems
simpler subproblems
distribution and exploration

explore find solution in tree

Overview
Principles:

Principles

constraint propagation Constraint Propagation

search

Summary of principles and significance

Modeling techniques

Oz and Mozart

Important Concepts Constraint Store

Constraint store

Basic constraint

Propagator x∈{3,4,5} y∈{3,4,5}

Non-basic constraint

Constraint propagation

Stores basic constraints
map variables to possible values

2
Constraint Store Constraint Store

finite domain constraints

x∈{3,4,5} y∈{3,4,5} x∈{3,4,5} y∈{3,4,5}

Stores basic constraints
Stores basic constraints

map variables to possible values map variables to possible values

Domains: finite sets, real intervals, trees, …

Propagators Propagators

Implement non-basic constraints x≥y y>3

distinct(x1,…,xn) x∈{3,4,5} y∈{3,4,5}

x + 2×y = z

smart algorithmic components
Amplify store by constraint propagation

Propagators Propagators

x≥y y>3 x≥y y>3

x∈{3,4,5} y∈{3,4,5} ∈{4,5}

x∈{3,4,5} y∈

Amplify store by constraint propagation
Amplify store by constraint propagation

3
Propagators Propagators

≥y
x≥ y>3 ≥y
x≥ y>3

∈{4,5}
x∈{3,4,5} y∈ ∈{4,5} y∈{4,5}
x∈

Amplify store by constraint propagation
Amplify store by constraint propagation

Propagators Propagators

x≥y y>3 x≥y

x∈{4,5} y∈{4,5} x∈{4,5} y∈{4,5}

Amplify store by constraint propagation
Amplify store by constraint propagation

Disappear when done (entailed)
Disappear when done (entailed)

no more propagation possible
no more propagation possible

Computation Space

x≥y y>3 Principles: Search

x∈{4,5} y∈{4,5}

Store with connected propagators

4
Important Concepts Distribution (Branching)

Distribution x≥y y>3

Exploration x=4
x∈{4,5} y∈{4,5}
x≠4

Heuristics

Best solution search x≥y y>3 x≥y y>3

x∈{4} y∈{4} x∈{5} y∈{4,5}

Yields spaces with additional constraints

Enables further constraint propagation

Distribution Strategy Search

Pick variable x with at least two values

Pick value n from domain of x

Distribute with
x=n and x≠n

Iterate propagation and distribution

Part of model


Orthogonal: distribution exploration

Nodes:
• Unsolved • Failed • Succeeded

SMM: Solution Solving SMM in Oz

SEND
Program script
+ MORE
script implements model

unary procedure: argument (root variable) is
= MONEY solution

Script
9567
introduce variables

basic constraints
+ 1085
post constraints
= 10652
create branching

5
 Oz Script for SMM: Oz Script for SMM:
Solution and Basic Constraints Post Propagators
proc {SMM Sol} proc {SMM Sol}
S E N D M O R Y …
in {FD.distinct Sol}
Sol=smm(s:S e:E n:N d:D m:M o:O R:r y:Y) S\=:0 M\=:0
Sol ::: 0#9 1000*S+100*E+10*N+D
… + 1000*M+100*O+10*R+E
end =: 10000*M+1000*O+100*N+10*E+Y
…
end

Oz Script for SMM:

Distribution Strategy Complete Oz Script for SMM
proc {SMM Sol} proc {SMM Sol}
… S E N D M O R Y
{FD.distribute naive Sol} in
end Sol=smm(s:S e:E n:N d:D m:M o:O R:r y:Y)
Sol ::: 0#9
{FD.distinct Sol}
S\=:0 M\=:0
1000*S+100*E+10*N+D
+1000*M+100*O+10*R+E
=: 10000*M+1000*O+100*N+10*E+Y
{FD.distribute naive Sol}
end

Solving SMM in Oz Heuristics for Distribution

{ExploreOne SMM}
Which variable

least possible values (first-fail)

application dependent heuristic

Which value

Use Oz Explorer
minimum, median, maximum

interactive, visual search x=m or x≠m

allows access to nodes in search tree
split with median m

gain insight into propagation and distribution x<m or x≥m

Other engines available
Problem specific

6
SMM: Solution With First-fail Send Most Money (SMM++)
SEND
Find distinct digits for letters, such that
+ MORE
SEND
= MONEY
+ MOST
9567 = MONEY
+ 1085
and MONEY maximal
= 10652

Best Solution Search Branch-and-bound Search

Naïve approach:

compute all solutions

choose best

Branch-and-bound approach:

compute first solution

add “betterness” constraint to open nodes

next solution will be “better”

prunes search space

Find first solution

Branch-and-bound Search Branch-and-bound Search

Explore with additional constraint
Explore with additional constraint

7
Branch-and-bound Search Branch-and-bound Search

Guarantees better solutions
Guarantees better solutions

Branch-and-bound Search Branch-and-bound Search

Last solution best
Proof of optimality

Modeling SMM++ SMM++: Branch-and-bound

Constraints and branching as before SEND

Order among solutions with constraints + MOST

so-far-best solution S,E,N,D,M,O,T,Y
= MONEY

current node S,E,N,D,M,O,T,Y

constraint added 9782
10000×M+1000×O+100×N+10×E+Y
< + 1094
10000×M+1000×O+100×N+10×E+Y = 10876

8
SMM++: All Solution Search
SEND Summary
+ MOST
= MONEY
9782
+ 1094
= 10876

Modeling and Solving

applications Constraint Programming in Oz

Modeling
Script

variables with domain
implements constraint model

constraints to state relations

branching strategy
Solution order
principles
defined by binary procedure

solution ordering

Solving
Exploration

constraint propagation
interactive: Oz Explorer

constraint branching
search module: plain, best, parallel, …

search tree exploration

Application Areas Why Does CP Matter?

Timetabling

Middleware for combining smart algorithmic

Scheduling

Crew rostering components (propagators)

Resource allocation
scheduling

Workflow planning and optimization
graphs

Gate allocation at airports
flows

Sports-event scheduling
…

Railroad: track allocation, train allocation, schedules …for strong propagation

Automatic composition of music

Essential extra constraints…

Genome sequencing

Frequency allocation …for flexibility

…

9
SMM: Strong Propagation Significance
SEND
Constraint programming identified as a
+ MORE strategic direction in computer science
= MONEY research
[ACM Computing Surveys, December 1996]
9567
+ 1085
Applications are ubiquitous
= 10652

Modeling Strategy

Modeling
Understand problem

identify variables

identify constraints

identify optimality criterion

Attempt initial model simple

try on examples to assess correctness

Improve model much harder

scale up to real problem size

Modeling Techniques Modeling Techniques

Find variables and values
Remove useless solutions

decrease symmetries
symmetrical: symmetry breaking

dual models: change values and variables
same cost: dominance constraints

combine models: channeling
Good heuristic for distribution

Increase propagation
which variable: size, degree, regret, …

strong methods
how to split domains: single value, bisection,

redundant (implied) constraints but non- …
redundant propagation
in which order to split: minimum, median,
maximum, …

10
 Getting Started with Mozart

Oz and Mozart
Use tutorial shipped with Mozart

Schulte, Smolka. Finite Domain Constraint
Programming in Oz. A Tutorial.

Little knowledge on Oz required

scripts are unary procedures

orders are binary procedures

introducing variables

conditional statements

calling functions and procedures

tuples (records) for solutions

loops for iterating over tuples

Mozart Features Mozart Advantages

Finite domain integers
Incremental and interactive development

general purpose: arithmetic, …
understand problem and refine model

rich tool support

scheduling

Integration with concurrency and distribution

Finite sets
multi agent applications

Search: orthogonal exploration
Well documented

basic + interactive + parallel + …
Freely available

Tools
Programmable and Extensible

OPI, Explorer, Browser, Inspector, …

Programmable and Extensible Mozart Disadvantages

Programming [Oz]
Small set of good propagators

scripts
"global constraints"

distribution
will worsen due to lack of contributors

exploration (Explorer, parallel search, …)
Inflexible interface for propagators

combination mechanisms
unrealistic assumptions

Extending [CPI in C++]
Initial burden to learn Oz

propagators

variables
Not easy to embed

11
 Constraint Programming with
Mozart

Summary
Powerful technology for combinatorial

optimization

Mozart free, programmable, and accessible
system for constraint programming

requires more propagators

Most effort is in modeling (understanding)

not dependent on Oz and Mozart

12