|%m*kc$7r
J``?PFC
jxcDĶW=>enUdn#>*YHm+$HXw@A~[q:+<`UF3寠>?ЯLeAfj
<[<%hխ|
F˘*d9$9+վ"I&
VȰ*(Fp8ɯ^xCco 67no%{STtdUlG*Ęps|5Wz]o[yy,=9#=*oP1v݉^]xkD_F(KnnړBn$`N2spc|
>L]?ENHsKErtEmZ.
gT߱xz61Hl"eRDl'9oIrǦJ}!9`_~bO5{m6v
C2:5ߴ5ЭbhͤehiD8c86g$q?)8 gzi WQh%z'GzY@Q-v-o(U,pqt<8||d#Lth`Z#
W'#)
oW2j~ՙ$2·WX 95^Q*HEq(oFz3HEesAWY^;$&;I
y(r?'ZGe@n{=iL
7
AP3u Nqon\D#CF\Ѵבi^t߀6.7m^q(x1uh{7VKY+s/x,~R_Nch_("` 4:.hWcFV0Lŀe<(I"_B^=i]_#*:䁐OS_MJ/&Q$YC1#$q^Qq\x>b9̯~Q'{ڀxAּ1=7m_HZ]|d,7rw|jRYYw!rJ]OZuU_KhmFĿdO&GcY!24oz9J↵|}3b>6`3Z>)md#)Y亂6纟Vkiu{Bᥑa0[nc|u8gPo
u˔uzwG;Ty[E8biij_7oW|s
cbx9ϮOzg/zHԴjM,}[v@~D3|=w(
\&b
fer@$rFx_.x+ºg>2om֟1J2yZj:krBN1kxPĒ[Kx !y9%g|mKMz(QlY-N|(80=jox3ZmwX'=H:|X/߀=iٹ̍$&i@U>Dzqꗌ$W`w9a`Y?Ps&<
qiܫPqiA&fH3ȭ}aSE0O*$sP&QS~
*ƎDHE
K\kkz+g E!Qgz=ɮ>DHyQ6}{:ljcΐI=skm4v PPo_wKH][9I4.3r8$ggw?h6k-[I1+WY?j\;^!K
=8$>wJpvIDOb) 5K=-ne)ᦝѦ))f^'O?0|(
0h0DCourier NewmanH=|dv0|(
0h1a.
@n?" dd@ @@``/+
+) !"#$%&'()*+,-./,R$f.f?C:/SU:h0e0eA@A5%8c8c
?1d0u0@Ty2 NP'p<'p@A)BCD|E?@87uʚ;2Nʚ;g4AdAdv0pppp@<4!d!d`
0,4><4dddd`
0,4>?%GConstraint Programming\Michael Trick
(actually 75% Pascal Van Hentenryck, 20% Irv Lustig, 5% Trick)
Carnegie Mellon$]?,'
OutlineMotivation
An Overview of Constraint Programming
Constraint Programming at Work
Getting Started
Sports Scheduling
Manufacturing
Perspectives6P0
P0
Combinatorial Optimization?Many, many practical applications
Resource allocation, scheduling, routing
Properties
Computationally difficult
Technical and modeling expertise needed
Experimental in nature
Important ($$$) in practice
Many solution techniques
Integer programming
Specialized methods
Local search/metaheuristics
Constraint programming"Z*ZZuZZ[Z"*u[Constraint programming"Began in 1980s from AI world
Prolog III (Marseilles, France)
CLP(R)
CHIP (ECRC, Germany)
Application areas
Scheduling, sequencing, resource and personnel allocation, etc. etc.
Active research area
Specialized conferences (CP, CP/AI-OR, & )
Journal (Constraints)
Companies Z<ZZEZZMZ<E3Constraint ProgrammingTwo main contributions
A new approach to combinatorial optimization
Orthogonal and complementary to s
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVtandard OR methods
Combinatorial versus numerical
A new language for combinatorial optimization
Rich language for constraints
Language for search procedures
Vertical extensionsl-S.Q-S.Q The TutorialGoal: to provide an introduction
What is constraint programming?
What is it good for?
How does it compare to integer programming?
How easy is it to use?
What is the underlying technology?&!!
Constraint ProgrammingConstraint programming by example
Illustrate rich language
Contrast with integer programming
Illustrate some underlying technologies
Disclaimers
Can t cover all of CP
I want to make you curious
Language/system used
Could use many; choose OPL"ZcZZ1ZZZ"c1"Modeling in Constraint ProgrammingA rich constraint language
Arithmetic, higher-order, logical constraints
Global constraints for natural substructures
Specification of a search procedure
Definition of search tree to explore
Specification of search strategyL[$F[$FComparison of CP/IPBranch and Prune
Prune: eliminate infeasible configurations
Branch: decompose into subproblems
Prune
Carefully examine constraints to reduce possible variable values
Branch
Use heuristics based on feasibility info
Main focus:constraints and feasibilityZNZZAZZ)Z'ZNA)'S Branch and Bound
Bound: eliminate suboptimal solutions
Branch: decompose into subproblems
Bound
Use (linear) relaxation of problem (+ cuts)
Branch
Use information from relaxation
Main focus: objective function and optimalityZIZZ,ZZ Z.ZI, .,"!
Illustrative artificial exampleColor a map of (part of) Europe: Belgium, Denmark, France, Germany, Netherlands, Luxembourg
No two adjacent countries same color
Is four colors enough?
OPL exampleenum Country {Belgium,Denmark,France,Germany,Netherlands,Luxembourg};
enum Colors {blue,red,yellow,gray};
var Colors color[Country];
solve {
color[France] <> color[Belgium];
color[France] <> color[Luxembourg];
color[France] <> color[Germany];
color[Luxembourg] <> color[Germany];
color[Luxembourg] <> color[Belgium];
color[Belgium] <> color[Netherlands];
color[Belgium] <> color[Germany];
color[Germany] <> color[Netherlands];
color[Germany] <> color[Denmark];
};
$Z6A ZVariables non-numeric
Constraints are non-linear
Looks nothing like IP!
Perfectly legal CPConstraint ProgrammingDomain store
For each variable: what is the set of possible values?
If empty for any variable, then infeasible
If singleton for any variable, then solution&
VConstraints
Capture interesting and well studied substructures
Need to
Determine if constraint is feasible WRT the domain store
Prune impossible values from the domains
XZ;ZdZZ;dConstraintsCan have differing techniques to handle a constraint type:
3x+10y+2z + 4w = 4
x in {0,1}, y in {0,1,2}, z in {0,1,2}, w in {0,1}
Simple bound on sizes gives y in {0}
More complicated handling gives
x in {0}, y in {0}, z in {0,2}, w in {0,1}L=FE+P3p
Constraint SolvingGeneral algorithm is
Repeat
select a constraint c
if c is infeasible wrt domain store
return infeasible
else apply pruning algorithm of c
Until no value can be removed*Gb BranchingOnce the constraint solving is done, if the problem is not infeasible nor are the domains singletons, then apply the search method
Choose a variable x with non-singleton domain (d1, d2, & di)
Foreach d in (d1, d2, & di)
add constraint x=di to problem and solve
*P!Show OPL solving coloring problemStrength of CPSince there is no need for a linear relaxation, the language can represent much more directly (no need for big-M IP formulations.!Examples of formulation abilitiesFacility location: want a constraint that customer j can be assigned to warehouse i only if warehouse open. (y[i]=1 if warehouse i open)
IP: x[i,j] is 1 if cust j assigned to i
x[i,j] <= y[i]
CP:x[j] is the warehouse cust j assigned to (not a 0,1 variable)
y[x[j]] = 1;
$ZZ,<6Similar exampleRouting type constraints.
Let x[i] be the ith customer visited and d[i,j] be distance from i to j
sum (i in 1..n) d[x[i],x[i+1]]
gives total distance traveled
LI c *uFormulation strengthsLogical requirements: if A=1 and B<=2 then either C>=3 or D=1.
Really painful in IP. Straightforward in CP:
((A=1) &(B<=2)) => ((C>=3)\/(D=1))*n#n#Global ConstraintsRecognize that some types of constraints come up often
Create specialized routines to handle
Strong pruning
Efficient handling
Extend system to include these N7&" 7&" Global constraint: alldifferent:Most well known and studied constraint.
alldifferent(x,y,z)
states that x, y, and z take on different values. So x=2, y=1, z=3 would be ok, but not x=1, y=3, z=1.
Clear uses in routing (x[i] is ith customer visited, alldifferent[x] says each customer visited at most once), very useful in many other situations. `(ZZZ(
t>(U$Alldifferent feasibility and pruning
CFeasibility? Given domains, create domain/variable bipartite graph$Alldifferent feasibility and pruning
)Pruning? Which edges are in no matching?Global constraints0Many different types of constraints have specialized routines
distribute(card,value,base): the number of times value[i] appears in base is card[i]
circuit(succ) : the values in succ form a hamiltonian circuit (so if you follow the sequence 1, succ[1], succ[succ[1]] etc, you will get a loop through 1..n.L>ZZ>9
t*,Global constraintsMany others, and new ones being created all the time
Strengthen and expand the language
Make modeling easier and more natural
System is faster at finding solutions
Details hidden to user&55Vertical language extensionsCan add constraints and definitions to make modeling even more natural
Ideas remain the same: there are domains and constraints; constraints check for feasibility and prune domains; a search strategy guides the system in finding solutions
SchedulingWant concepts of jobs, machines, before , after , jobs requiring machines, and so on.
Easy to extend"Example of scheduling!Search StrategyCombined with model, search strategies are integral to constraint systems.
Allow choice of branching variables or more powerful search strategies
Can be key in solving problems
Two steps
Specify tree to search
Specify how to explore the tree*Z7Z7Example of Search Strategiesforall(s in Stores ordered by increasing regretdmax(cost[s]))
tryall(w in Warehouses ordered by increasing supplyCost[s,w]) supplier[s] = w; };
implements a maximum regret ordering (find a store with maximum regret then order the warehouses by increasing cost) uH"&#Example ProblemPainting cars (from Magnanti and Sokel).
Sequence cars to minimize paint changeover
Cars cannot be sequenced too far out of order, \$
Small exampleSmall Example: 10 cars in sequence. The order for assembly is 1, 2, ..., 10. A car must be painted within 3 positions of its assembly order. For instance, car 5 can be painted in positions 2 through 8 inclusive. Cars 1, 5, and 9 are red; 2, 6, and 10 are blue; 3 and 7 green; and 4 and 8 are yellow. Initial sequence 1, 2, ... 10 corresponds to color pattern RBGYRBGYRB and has 9 purgings. The sequence 2,1,5,3,7,4,8,6,10,9 corresponds to color pattern BRRGGYYBBR and has 5 purgings.
2Z"", V %!Constraint Programint n=& ;
int rnge=& ;
int ncolor=& ;
range Slots 1..n;
var Slots slot[1..n];
var Slots revslot[1..n];
int color[1..n]= & ;
minimize
sum (j in 1..n-1) (color[revslot[j]] <> color[revslot[j+1]])
subject to {
forall (i in Slots)
i-rnge<=slot[i] <= i+rnge; /*Must be in range */
alldifferent(slot); /*must choose different slots */
forall (i in Slots)
revslot[slot[i]] = i;
};Z
6
(
,(Personal useTremendous help in my work on sports scheduling: much easier to formulate idiosyncratic constraints
Very fast to create prototypes
Competitive (at least!) to IP approaches&"Result|Formulation is much easier than IP formulation
Gets good solutions much faster than IP
Is competitive in proving optimality'#Finding optimal solutionsConstraint programs can find optimal solutions. Typically works by finding a feasible solution and adding a constraint that future solutions must be better than it. Repeat until infeasible: the last solution found is optimal($PerspectiveskMany solution techniques
Integer programming
Constraint programming
Local search
Combinations
Which to use?6EE)%Comparing IP and CPComplementary technologies
Integer programming
Objective function: relaxations
Constraint programming
Feasibility: domain reductions
Might need to experiment with both
CP particularly useful when IP formulation is hard or relaxation does not give much information *&Combining MethodsLocal and Global Search
Use CP/IP for very large neighborhood search (take a solution, remove large subset, find optimal completion)
Combining CP and IP
Use LP as constraint handler
Use CP as subproblem solver in branch and price
& & TZmZZPZmP+'ConclusionsConstraint programming should become a part of every OR person s toolkit
Combinations of CP and IP represent a big thing in future techniques
Blurring of lines between optimization and heuristics
t$(
tr
t Sq# U
#
r
t S#
#
H
t0h ? 3333
~v`(
r
S"Q U
Q
r
S̉Q
Q
A
. `cars.jpgT`TT`T"BQH
0h ? 3333
p$(
r
SQ U
Q
r
S8Q
Q
H
0h ? 3333
$(
r
SPQ U
Q
r
Snf
f
H
0h ? 3333
$(
r
S4f U
r
S2f
f
H
0h ? 3333
$(
r
Sf U
Q
r
SԦf
f
H
0h ? 3333
$(
r
Sf U
Q
r
SĢf
f
H
0h ? 3333
$(
r
Sf U
Q
r
Sof
f
H
0h ? 3333
$(
r
Sp\Q U
Q
r
Sf
f
H
0h ? 3333
$(
r
S܀f U
Q
r
S Sf
f
H
0h ? 3333
$(
r
Sf U
Q
r
Sf
f
H
0h ? 3333r<L#wM9խ%
L,>Q(
/00DTimes New RomanH=|dv0|(
0hDTahomaew RomanH=|dv0|(
0h" DWingdingsRomanH=|dv0|(
0h0DCourier NewmanH=|dv0|(
0h1a.
@n?" dd@ing MethodsConclusionsFonts UsedDesign Template
Slide Titles) @@``/+
+) !"#$%&'()*+,-./,R$f.f?C:/SU:h0e0eA@A5%8c8c
?1d0u0@Ty2 NP'p<'p@A)BCD|E?@87uʚ;2Nʚ;g4AdAdv0pppp@<4!d!d`
0,4><4dddd`
0,4>?%HConstraint Programming\Michael Trick
(actually 75% Pascal Van Hentenryck, 20% Irv Lustig, 5% Trick)
Carnegie Mellon$]?,'
OutlineMotivation
An Overview of Constraint Programming
Constraint Programming at Work
Getting Started
Sports Scheduling
Manufacturing
Perspectives6P0
P0
Combinatorial Optimization?Many, many practical applications
Resource allocation, scheduling, routing
Properties
Computationally difficult
Technical and modeling expertise needed
Experimental in nature
Important ($$$) in practice
Many solution techniques
Integer programming
Specialized methods
Local search/metaheuristics
Constraint programming"Z*ZZuZZ[Z"*u[Constraint programming"Began in 1980s from AI world
Prolog III (Marseilles, France)
CLP(R)
CHIP (ECRC, Germany)
Application areas
Scheduling, sequencing, resource and personnel allocation, etc. etc.
Active research area
Specialized conferences (CP, CP/AI-OR, & )
Journal (Constraints)
Companies Z<ZZEZZMZ<E3Constraint ProgrammingTwo main contributions
A new approach to combinatorial optimization
Orthogonal and complementary to standard OR methods
Combinatorial versus numerical
A new language for combinatorial optimization
Rich language for constraints
Language for search procedures
Vertical extensionsl-S.Q-S.Q The TutorialGoal: to provide an introduction
What is constraint programming?
What is it good for?
How does it compare to integer programming?
How easy is it to use?
What is the underlying technology?&!!
Constraint ProgrammingConstraint programming by example
Illustrate rich language
Contrast with integer programming
Illustrate some underlying technologies
Disclaimers
Can t cover all of CP
I want to make you curious
Language/system used
Could use many; choose OPL"ZcZZ1ZZZ"c1"Modeling in Constraint ProgrammingA rich constraint language
Arithmetic, higher-order, logical constraints
Global constraints for natural substructures
Specification of a search procedure
Definition of search tree to explore
Specification of search strategyL[$F[$FComparison of CP/IPBranch and Prune
Prune: eliminate infeasible configurations
Branch: decompose into subproblems
Prune
Carefully examine constraints to reduce possible variable values
Branch
Use heuristics based on feasibility info
Main focus:constraints and feasibilityZNZZAZZ)Z'ZNA)'S Branch and Bound
Bound: eliminate suboptimal solutions
Branch: decompose into subproblems
Bound
Use (linear) relaxation of problem (+ cuts)
Branch
Use information from relaxation
Main focus: objective function and optimalityZIZZ,ZZ Z.ZI, .,"!
Illustrative artificial exampleColor a map of (part of) Europe: Belgium, Denmark, France, Germany, Netherlands, Luxembourg
No two adjacent countries same color
Is four colors enough?
OPL exampleenum Country {Belgium,Denmark,France,Germany,Netherlands,Luxembourg};
enum Colors {blue,red,yellow,gray};
var Colors color[Country];
solve {
color[France] <> color[Belgium];
color[France] <> color[Luxembourg];
color[France] <> color[Germany];
color[Luxembourg] <> color[Germany];
color[Luxembourg] <> color[Belgium];
color[Belgium] <> color[Netherlands];
color[Belgium] <> color[Germany];
color[Germany] <> color[Netherlands];
color[Germany] <> color[Denmark];
};
$Z6A ZVariables non-numeric
Constraints are non-linear
Looks nothing like IP!
Perfectly legal CPConstraint ProgrammingDomain store
For each variable: what is the set of possible values?
If empty for any variable, then infeasible
If singleton for any variable, then solution&
VConstraints
Capture interesting and well studied substructures
Need to
Determine if constraint is feasible WRT the domain store
Prune impossible values from the domains
XZ;ZdZZ;dConstraintsCan have differing techniques to handle a constraint type:
3x+10y+2z + 4w = 4
x in {0,1}, y in {0,1,2}, z in {0,1,2}, w in {0,1}
Simple bound on sizes gives y in {0}
More complicated handling gives
x in {0}, y in {0}, z in {0,2}, w in {0,1}L=FE+P3p
Constraint SolvingGeneral algorithm is
Repeat
select a constraint c
if c is infeasible wrt domain store
return infeasible
else apply pruning algorithm of c
Until no value can be removed*Gb BranchingOnce the constraint solving is done, if the problem is not infeasible nor are the domains singletons, then apply the search method
Choose a variable x with non-singleton domain (d1, d2, & di)
Foreach d in (d1, d2, & di)
add constraint x=di to problem and solve
*P!Show OPL solving coloring problemStrength of CPSince there is no need for a linear relaxation, the language can represent much more directly (no need for big-M IP formulations.!Examples of formulation abilitiesFacility location: want a constraint that customer j can be assigned to warehouse i only if warehouse open. (y[i]=1 if warehouse i open)
IP: x[i,j] is 1 if cust j assigned to i
x[i,j] <= y[i]
CP:x[j] is the warehouse cust j assigned to (not a 0,1 variable)
y[x[j]] = 1;
$ZZ,<6Similar exampleRouting type constraints.
Let x[i] be the ith customer visited and d[i,j] be distance from i to j
sum (i in 1..n) d[x[i],x[i+1]]
gives total distance traveled
LI c *uFormulation strengthsLogical requirements: if A=1 and B<=2 then either C>=3 or D=1.
Really painful in IP. Straightforward in CP:
((A=1) &(B<=2)) => ((C>=3)\/(D=1))*n#n#Global ConstraintsRecognize that some types of constraints come up often
Create specialized routines to handle
Strong pruning
Efficient handling
Extend system to include these N7&" 7&" Global constraint: alldifferent:Most well known and studied constraint.
alldifferent(x,y,z)
states that x, y, and z take on different values. So x=2, y=1, z=3 would be ok, but not x=1, y=3, z=1.
Clear uses in routing (x[i] is ith customer visited, alldifferent[x] says each customer visited at most once), very useful in many other situations. `(ZZZ(
t>(U$Alldifferent feasibility and pruning
CFeasibility? Given domains, create domain/variable bipartite graph$Alldifferent feasibility and pruning
)Pruning? Which edges are in no matching?Global constraints0Many different types of constraints have specialized routines
distribute(card,value,base): the number of times value[i] appears in base is card[i]
circuit(succ) : the values in succ form a hamiltonian circuit (so if you follow the sequence 1, succ[1], succ[succ[1]] etc, you will get a loop through 1..n.L>ZZ>9
t*,Global constraintsMany others, and new ones being created all the time
Strengthen and expand the language
Make modeling easier and more natural
System is faster at finding solutions
Details hidden to user&55Vertical language extensionsCan add constraints and definitions to make modeling even more natural
Ideas remain the same: there are domains and constraints; constraints check for feasibility and prune domains; a search strategy guides the system in finding solutions
SchedulingWant concepts of jobs, machines, before , after , jobs requiring machines, and so on.
Easy to extend"Example of scheduling!Search StrategyCombined with model, search strategies are integral to constraint systems.
Allow choice of branching variables or more powerful search strategies
Can be key in solving problems
Two steps
Specify tree to search
Specify how to explore the tree*Z7Z7Example of Search Strategiesforall(s in Stores ordered by increasing regretdmax(cost[s]))
tryall(w in Warehouses ordered by increasing supplyCost[s,w]) supplier[s] = w; };
implements a maximum regret ordering (find a store with maximum regret then order the warehouses by increasing cost) uH"&#Example ProblemPainting cars (from Magnanti and Sokel).
Sequence cars to minimize paint changeover
Cars cannot be sequenced too far out of order, \$
Small exampleSmall Example: 10 cars in sequence. The order for assembly is 1, 2, ..., 10. A car must be painted within 3 positions of its assembly order. For instance, car 5 can be painted in positions 2 through 8 inclusive. Cars 1, 5, and 9 are red; 2, 6, and 10 are blue; 3 and 7 green; and 4 and 8 are yellow. Initial sequence 1, 2, ... 10 corresponds to color pattern RBGYRBGYRB and has 9 purgings. The sequence 2,1,5,3,7,4,8,6,10,9 corresponds to color pattern BRRGGYYBBR and has 5 purgings.
2Z"", V %!Constraint Programint n=& ;
int rnge=& ;
int ncolor=& ;
range Slots 1..n;
var Slots slot[1..n];
var Slots revslot[1..n];
int color[1..n]= & ;
minimize
sum (j in 1..n-1) (color[revslot[j]] <> color[revslot[j+1]])
subject to {
forall (i in Slots)
i-rnge<=slot[i] <= i+rnge; /*Must be in range */
alldifferent(slot); /*must choose different slots */
forall (i in Slots)
revslot[slot[i]] = i;
};Z
6
(
,(Personal useTremendous help in my work on sports scheduling: much easier to formulate idiosyncratic constraints
Very fast to create prototypes
Competitive (at least!) to IP approaches&"Result|Formulation is much easier than IP formulation
Gets good solutions much faster than IP
Is competitive in proving optimality'#Finding optimal solutionsConstraint programs can find optimal solutions. Typically works by finding a feasible solution and adding a constraint that future solutions must be better than it. Repeat until infeasible: the last solution found is optimal($PerspectiveskMany solution techniques
Integer programming
Constraint programming
Local search
Combinations
Which to use?6EE)%Comparing IP and CPComplementary technologies
Integer programming
Objective function: relaxations
Constraint programming
Feasibility: domain reductions
Might need to experiment with both
CP particularly useful when IP formulation is hard or relaxation does not give much information *&Combining MethodsLocal and Global Search
Use CP/IP for very large neighborhood search (take a solution, remove large subset, find optimal completion)
Combining CP and IP
Use LP as constraint handler
Use CP as subproblem solver in branch and price
& & TZmZZPZmP+'ConclusionsConstraint programming should become a part of every OR person s toolkit
Combinations of CP and IP represent a big thing in future techniques
Blurring of lines between optimization and heuristics
This talk at http://mat.gsia.cmu.edu/INFORMS/cp.pptP
$(
r
Sf U
Q
r
Sf
f
H
0h ? 3333r+'
ݳ~,>