MTH4410 MTH4410 Constraint Programming Programming Constraint Merci Willem-Jan van Hoeve, CMU. Outline Successful Applications Modeling Solving Some details global constraints scheduling Integrated methods (MIP+CP) Constraint Programming Overview Artificial Intelligence search

logical inference Operations Research optimization algorithms Constraint Programming Computer Science data structures formal languages Evolution events of CP 70s: Image processing applications in AI; Search+qualitative inference 980s: Logic Programming (Prolog); Search + logical inference 1989: CHIP System; Constraint Logic Programming 990s: Constraint Programming; Industrial Solvers (ILOG, Eclipse,) 94: Advanced inference for alldifferent and resource scheduling 000s: Global constraints; integrated methods; modeling languages

2006: CISCO Systems acquires Eclipse CLP solver 20 10 20 00 19 90 19 80 19 70 2009: IBM acquires ILOG CP Solver & Cplex Successful applications applications Successful Sport Scheduling Week 1 Week 2 Week 3

Week 4 Week 5 Week 6 Week 7 Period 1 0 vs 1 0 vs 2 4 vs 7 3 vs 6 3 vs 7 1 vs 5 2 vs 4 Period 2 2 vs 3

1 vs 7 0 vs 3 5 vs 7 1 vs 4 0 vs 6 5 vs 6 Period 3 4 vs 5 3 vs 5 1 vs 6 0 vs 4 2 vs 6 2 vs 7 0 vs 7 Period 4

6 vs 7 4 vs 6 2 vs 5 1 vs 2 0 vs 5 3 vs 4 1 vs 3 Schedule of 1997/1998 ACC basketball league (9 teams) various complicated side constraints all 179 solutions were found in 24h using enumeration and integer linear programming [Nemhauser & Trick, 1998] all 179 solutions were found in less than a minute using constraint programming [Henz, 1999, 2001] Hong Kong Airport Gate allocation at the new (1998) Hong Kong airport System was implemented in only four months, includes constraint

programming technology (ILOG) Schedules ~800 flights a day (47 million passengers in 2007) G. Freuder and M. Wallace. Constraint Technology and the Commercial World. IEEE Intelligent Systems 15(1): 20-23, 2000. Port of Singapore One of the worlds largest container transshipment hubs Links shippers to a network of 200 shipping lines with connections to 600 ports in 123 countries Problem: Assign yard locations and loading plans under various operational and safety requirements Solution: Yard planning system, based on constraint programming (ILOG) 8 Railroad Optimization Netherlands Railways has among the densest rail networks in the world, with 5,500 trains per day Constraint programming is one of the components in their railway planning software, which was used to design a new timetable from scratch (2009) Much more robust and effective schedule, and $75M additional annual profit INFORMS Edelman Award winner (2009) Modeling in

in CP CP Modeling CP Modeling basics CP models are very different from MIP models Virtually any expression over the variables is allowed e.g., x3(y2 z) 25 + x2max(x,y,z) CP models can be much more intuitive, close to natural language As a consequence, CP applies a different solving method compared to MIP 1 CP Variables Variables in CP can be the same as in your regular MIP model: binary, integer, continuous In addition, they may take a value from any finite set e.g., x in {a,b,c,d,e} the set of possible values is called the domain of a variable Finally, there are some special variable types for modeling scheduling applications 1 CP Constraints

A constraint is a relation between one or more variables. Let R(i,j) be the following Let i and j be two integer variables When R(i,j) is asserted: constraint The domain for i is i in {0..10}; j in {0..10}; restricted to {1,2,5,7} R i j 1 2 1

3 2 4 5 3 7 10 The domain for j is restricted to {2,3,4,10} 1 3 CP Constraints A solution to a constraint problem assigns a value to all the variables in such a way that all the constraints are satisfied i=2, j=4, k=8 is a solution of the system of three constraints R,S,T below R i

k 2 2 1 1 4 1 3 1 8 1 3 2 4 2

8 2 7 5 3 5 1 5 3 7 10 4 10 8

4 i j 2 S T k j CP Constraints What does a constraint do? Feasibility checking can the constraint be satisfied given the domains of its variables Pruning remove values from the domains if they do not appear in any solution of the constraint. Constraint Propagation When the domain of a variable is reduced, constraints may imply domain reductions for other related variables. Example:

Remove 1 from the domain of i R i j 1 2 1 3 2 4 5 3 7 10 It results in removing 2 from the domain of j The value 3 is still in the domain of j

Constraint Propagation When the domain of a variable is reduced, the effects of this change are propagated through all the constraints In this example, let us set i to the value 2 R i j i k 2 2 2 1 1 4 1

3 1 8 8 2 2 4 2 8 2 4 5 3 5 1

10 3 7 10 2 10 8 4 S T k j Constraints as Algorithms In most cases, it is inefficient to implement constraints using actual relational tables. CP languages thus use propagation algorithms to implement arithmetic constraints and all others.

The propagation algorithm must behave in the same way as the corresponding extensional relation. < x y 1 2 1 1 2 1 3 1 2 3 1

4 2 1 3 2 3 2 2 4 2 4 3 1 4

+ Example: Magic Series A series S = (S0,,Sn) is magic if Si is the number of occurrences of i in S 0 ? 1 ? 2 3 ? ? 4 ? Example: Magic Series A series S = (S0,,Sn) is magic if Si is the number of occurrences of i in S 0 1

2 3 4 2 1 2 0 0 Reification Reification n = 5 D = {0..n-1} var s[D] in D forall(k in D) s[k] == sum(i in D) (s[i]==k)); Reification

Allow constraints inside constraints Replace the constraint in () by a 0/1 variables representing the truth value of the constraint Example: Stable Marriages Example: Stable Marriages A marriage is stable between James and Kathryn provided that: Whenever James prefers another woman, say Anne, to Kathryn, then Anne prefers her husband to James; Whenever Kathryn prefers another man, say Laurent, to James, then Laurent prefers his spouse to Kathryn. Example: Stable Marriages Men = {Richard,James,John,Hugh,Greg} Women = {Helen,Tracy,Linda,Sally,Wanda} preferm[Men,Women] = preferw[Women,Men] = var wife[Men] in {Women} var husband[Women] in {Men}

Element Constraint Reification forall(i in Men) husband[wife[i]] == i forall(i in Women) wife[husband[i]] == i forall(i in Men,j in Women) (preferm[i,j] > preferm[i,wife[i]]) => (preferw[j,husband[j]] > preferw[j,i]) forall(i in Men,j in Women) (preferw[j,i] < preferw[j,husband[j]]) => (preferm[i,wife[i]] < preferm[i,j]); } Implication Element Constraints Element constraints ability to index an array/matrix with a decision variable or an expression; Logical constraints ability to express any logical combination of constraint see also reification The Element Constraint X : variable Y : variable C : array

Constraint: X = C[Y] X3 Y1&Y4 3 0 4 1 2 [0] [1] [2] 3 4 5 5 3 4 5 [3] [4] [5]

5 4 3 Assignment Problem Model the following assignment problem with CP Given 5 tasks (t1 to t5 ) and 5 employees (e1 to e5) Assign one and only one task to each employees such that the assignment minimizes the following costs: T\E 1 2 3 4 6 1 2 3

5 1 8 2 3 4 3 4 5 3 1 3 4 7 9

4 3 3 2 6 4 5 5 7 2 8 5 Can you compare with a MIP version of this problem ? Another example of Element: the

TSP The traveling salesperson problem asks to find a closed tour on a given set of n locations, with minimum total length. Input: set of locations and distance dij between two locations i and j 2 TSP: CP model Variable xi represents the i-th location that the tour visits (variable domain is {1,2,,n} ) Objective n 1 min d xn ,x1 d xi ,xi1 i1 Another way to write Element constaints is to put variables as subscripts! Constraint this is a global alldifferent(x1, x2, , xnconstraint

) 3 Example: Alldifferent Alldifferent(x1,x2,...,xn) semantically equivalent to { xi xj for all i j } Model 1:x1 {a,b}, x2 {a,b}, x3 {a,b,c} x1 x2, x1 x3 , x2 x3 no domain values will be filtered Model 2:x1 {a,b}, x2 {a,b}, x3 {a,b,c} alldifferent(x1,x2,x2) global view of alldifferent: x3 {c} Grouping constraints together allows more domain Filtering for alldifferent Observation [Rgin, 1994]: matching in bipartite graph solution to alldifferent covering all variables Example: x1 x2

x3 a b c x1 {a,b}, x2 {a,b}, x3 {b,c} alldifferent(x1,x2,x3) Filtering: remove all edges (and corresponding domain values) that are not in any matching covering the variables Find initial matching: O(mn) time1 Filter all inconsistent edges? [Hopcroft and Karp, 1973] 3 MIP and CP model compared The CP model needs only n variables, while the MIP model needs n2 variables (n is #locations) The MIP model is of exponential size, while the CP model only needs one single constraint The CP model is more intuitive, as it is based directly on the problem structure: the ordering of the locations in the tour

Note: The special-purpose MIP solving methods outperform CP on pure TSP. In presence of side constraints (e.g., time windows), CP becomes competitive. 3 Illustration: Sudoku each row contains numbers 1 up to 9 each column contains numbers 1 up to 9 each block contains numbers 1 up to 9 6 3 9 7 8 2 4 1 5 Sudoku puzzle: try to complete partially filled square 2 5 1 9 4 3 7 6 8 4 7 8 6 1 5 9 2 3 3 6 2 1 7 9 5 8 4 1 8 7 5 3 4 6 9 2 5 9 4 8 2 6 3 7 1 9 4 3 2 6 8 1 5 7 8 1 6 3 5 7 2 4 9 7 2 5 4 9 1 8 3 6 CP model for Sudoku variables and domains: xij in {1,2,3,4,5,6,8,9} for all i,j in 1..9 constraints:

alldifferent(xij : j=1..9) for all rows i alldifferent(xij : i=1..9) for all columns j 3 1 4 alldifferent(xij : i,j in block b) for all blocks b8 4 6 1 5 3 8 4 xij = k if cell (i,j) is pre-set to value k 1 5 4 2

5 9 9 2 6 1 2 1 7 5 3 Solving time Experimental results over larger Sudoku instances (1616) 1 not-equal constraints { xi xj for all i j } alldifferent constraints alldifferent(xij) solved: 94% solved: 100% total time: 249.21s total time: 6.47s backtracks: 2,284,716 backtracks: 3020

1 time limit 600s What is the effect of changing the inference level from default to extended in our AIMMS model? 3 Global Constraints Examples Alldifferent, Count, BinPacking, SequentialSchedule, ParallelSchedule, NetworkFlow, Global constraints represent combinatorial structure Can be viewed as the combination of elementary constraints Expressive building blocks for modeling applications Embed powerful algorithms from OR, Graph Theory, AI, CS, Essential for the successful application of CP Summary of CP modeling Variables range over finite or continuous domain:

v {a,b,c,d}, start {0,1,2,8,9,10}, z [2.18, 4.33] Algebraic expressions: x3(y2 z) 25 + x2max(x,y,z) Variables as subscripts: y = cost[x] (here y and x are variables, cost is an array of parameters) Reasoning with meta-constraints: i (xi > Ti) 5 Logical relations in which (meta-)constraints can be mixed: ((x < y) OR (y < z)) (c = min(x,y)) Global constraints (a.k.a. symbolic constraints): Alldifferent(x1,x2, ...,xn) SequentialSchedule( [start1,..., startn], [dur1,...,durn], [end1,...,endn] ) CP Solving Solving CP CP Solving In general CP variables are discrete (i.e., integer valued) while CP constraints are non-linear non-differentiable discontinuous Hence, no traditional Operations Research technique can solve these

models (LP, NLP, MIP, etc) 4 Basics of CP solving CP solving is based on intelligently enumerating all possible variablevalue combinations called backtracking search similar to branch&bound for MIP Unlike branch&bound, CP does not solve a LP relaxation at each search node, but applies specific constraint propagation algorithms These propagation algorithms are applied to individual constraints, and their role is to limit the size of the search tree 4 Solving Example: variables/domains x1 {1,2}, x2 {0,1,2,3}, x3 {2,3} constraints x1 > x2 x1 + x2 = x 3 alldifferent(x1,x2,x3) 4 Solving Example:

variables/domains x1 {1,2}, x2 {0,1,2,3}, x3 {2,3} constraints x1 > x 2 x1 + x 2 = x 3 alldifferent(x1,x2,x3) x1 2 1 x2 0 1 x3 2 x2 x3 3 2 3 2

0 x3 3 2 x3 3 2 1 x3 3 2 x3 3 2 3 2

x3 3 2 x3 3 2 3 4 Solving Example: variables/domains x1 {1}, x2 {0,1}, x3 {2,3} constraints x1 > x2 x1 + x2 = x3 alldifferent(x1,x2,x3) x1 2 1 x2 0

1 x3 2 x2 0 x3 3 2 1 x3 3 2 x3 3 2 3 4

Solving Example: variables/domains x1 {2}, x2 {0,1}, x3 {2,3} constraints x1 > x2 x1 + x2 = x 3 alldifferent(x1,x2,x3) x1 2 1 x2 x2 0 1 x3 2 x3 3 2

3 4 CP - Summary The solution process of CP interleaves Domain filtering remove inconsistent values from the domains of the variables, based on individual constraints Constraint propagation propagate the filtered domains through the constraints, by re-evaluating them until there are no more changes in the variable domains Search implicitly all possible variable-value combinations are enumerated, but the search tree is kept small due to the domain filtering and constraint propagation Another example Partial Latin Square (order 3) A number in {1,2,3} in each cell

Numbers on each row must be pairwise different Numbers on each column must be pairwise different Some cells are pre-filled 3 1 2 1 2 3 2 3 1 A possible solution Another example Partial Latin Square (order 3)

A number in {1,2,3} in each cell Numbers on each row must be pairwise different Numbers on each column must be pairwise different Some cells are pre-filled 3 1 2 1 2 3 2 3 1

As a CSP: Variables and domains Constraints Another example Partial Latin Square (order 3) A number in {1,2,3} in each cell Numbers on each row must be pairwise different Numbers on each column must be pairwise different Some cells are pre-filled 3 1 2 1

2 3 2 3 1 As a CSP: Pairwise different on rows Pairwise different on cols Pre-filled cells Another example Before propagation {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3

{1,2,3} 3 {1,2,3} Another example After propagation {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} Another example

How to search for a solution? The simplest approach is using Depth First Search Open a choice point On each branch post a new constraint So as to partition the solution space A typical example: xi xi = vj xi vj Choose a variable xi Choose a value vj in Di Post xi = vj on the left branch Post the opposite constraint on backtrack binary choice point Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored Lets see that in action: Choose var with smallest index Choose smallest value {1,2,3}

{1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 {1,2,3} {1,2,3} {1,2,3}

{1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 {1,2,3} {1,2,3} {1,2,3} {1,2,3}

{1,2,3} 3 {1,2,3} 3 {1,2,3} Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 domain wipeout {1,2,3} {1,2,3} {1,2,3} {1,2,3}

{1,2,3} 3 {1,2,3} 3 {1,2,3} Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 fail x11 domain wipeout {1,2,3} {1,2,3}

{1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 {1,2,3} {1,2,3} {1,2,3}

{1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 x11 1 {1,2,3} {1,2,3} {1,2,3}

{1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} x11 Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 x11 1 {1,2,3} {1,2,3}

{1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} x11 x11 = 2 Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 x11 1 another

wipeout {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} x11 x11 = 2 Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1

x11 x11 1 another wipeout {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} x11 x11 = 2

fail Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 x11 1 {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3

{1,2,3} x11 x11 = 2 Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 x11 1 {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3}

3 {1,2,3} x11 x11 = 2 x11 2 x12 Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 x11 1 {1,2,3} {1,2,3} {1,2,3} {1,2,3}

{1,2,3} 3 {1,2,3} 3 {1,2,3} x11 x11 = 2 x11 2 x12 x12 = 1 Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 x11 1

{1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} x11 x11 = 2 x11 2 x12 x12 = 1 Another example Key mechanism: The new constraints narrow the domains And cause propagation

On backtrack, the domains are restored x11 = 1 x11 x11 1 {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} x11 x11 = 2 x11 2

x12 x12 = 1 Another example Key mechanism: The new constraints narrow the domains And cause propagation On backtrack, the domains are restored x11 = 1 x11 x11 1 3 1 2 1 2 3 2 3

1 x11 x11 = 2 x11 2 x12 x12 = 1 Another example Propagation can have a huge impact With: 3 leaves x11 = 1 x11 Without: 2,187 leaves x11 1 3 1 2 1

2 3 2 3 1 x11 x11 = 2 x11 2 x12 x12 = 1 Redundant Constraints Redundant constraints Sometimes it is worth adding a constraint Even if it is not necessary Because of the additional propagation Example: Lets add a redundant constraint {1,2,3} {1,2,3}

{1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} there must be a 3 in row 1 (x11 = 3) (x12 = 3) (x13 = 3) Redundant Constraints Redundant constraints Sometimes it is worth adding a constraint Even if it is not necessary Because of the additional propagation first round of propagation Example: Lets add a redundant constraint

{1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} there must be a 3 in row 1 (x11 = 3) (x12 = 3) (x13 = 3) cst = 0 cst = 0 Redundant Constraints Redundant constraints Sometimes it is worth adding a constraint Even if it is not necessary

Because of the additional propagation first round of propagation Example: Lets add a redundant constraint {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3 {1,2,3} there must be a 3 in row 1 (x11 = 3) (x12 = 3) (x13 = 3) this is 1

cst = 0 cst = 0 From here, we find a solution with no fail at all! Redundant Constraints Global Constraints A constraint reasoning on many variables at the same time Specialized, powerful filtering Example No more propagation after this {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3}

3 {1,2,3} Redundant Constraints Global Constraints A constraint reasoning on many variables at the same time values 1,2 must Specialized, powerful filtering go to those vars Example No more propagation after this {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3} 3

{1,2,3} But if we reason on a whole row Redundant Constraints Global Constraints A constraint reasoning on many variables at the same time so, this Specialized, powerful filtering must be 3 Example No more propagation after this {1,2,3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} 3 {1,2,3}

3 {1,2,3} But if we reason on a whole row we can deduce (and filter) more Remember: from here, we find a solution with no fail at all! Redundant Constraints Meta constraints vs globals Meta-constraints allow to model just about everything But they often have poor filtering Advice: use globals whenever it is possible Redundant constraints vs globals Redundant constraints must be carefully engineered based on domain knowledge But they provide someglobal propagation Advice: add if the additional propagation is not subsumed