# Constraint Programming

The goal of constraint programming is to provide a declarative and procedural formulation for a discrete optimization problem. The declarative formulation states the constraints and objective function and also provides a way to describe the sort of solution one is seeking for, without distraction of algorithmic details.
The search is directed by the procedural formulation, which specifies how to search for a solution.

### Basic idea

A constraint can be viewed as a procedure which operates on the solution space. Each constraint provides a relaxation to the constraint store which limits the portion of search base. The constraint store should contain constraints for which generating feasible solutions is easy.

Steps to do to solve a constraint programming problem:
* choose the decision variables
* identify the constraints and express them in terms of decision variables.

### 8 queens problem:

Consider the problem where you have to place 8 queens on a chessboard so that no two fo them attack each pther.Two queens attack each other if they are on same column or diagonal.


GOAL OF CONSTRAINT PROGRAMMING: Remove all values which are impossible.

So,you start by placing queens one by one and when you reach a point where you cannot move any further you come back and reconsider the position.This is equivalent of making a choice when no more deduction can be made. So when the choice is wrong solver backtracks.
Here the decision variable : associate a decision variable with each column.Then a variable denotes the row of a queen placed in this coloumn.Validity : no two queens can be placed in the same row so this is valid.
Constraints : queens cannot be placed on the same
* row
* upward diagonal
* downward diagonal

### Map colouring :

Problem : Colour a map such that no two adjascent territories recieve the same colour.

So in the above problem ,
decision variable : color given to a country
domain of decision variable : set of values the variable can take.here 4 different colors ( As the 4 color theorem says every map can be coloured using 4 colors)
constraints : two adjascent countries cannot have the same color.

### conversion of character case and ascii codes.

Instead of following a set of instructions with only one way to compute values constraint programming declares the relationship between variables and constraints.

To see the difference of constraint programming approach we will see the example of converter which changes character cases(lower-case to/from capital/upper-case) and return the ASCII codes for each. So at any point of time the converter is aware of all 4 values.

The problem is translated into a constraint system consisting of connectors(variables) and nodes (constraints).connectors check for variable domain.When one value changes a particular connector changes/notifies all its connected nodes about the change.Nodes satisfy constraints calculate new values and propagate the them to other connectors.


All the connectors are linked to nodes (defined by constraints),when one value is set in any one of the four connectors the system automatically calculates and sets the values on the rest of the connectors.This is the main advantage of using constraint programming ,as recaculation is reduced and values are automatically set.

#### Constraint programming is a combination of Branch and Prune.
Pruning is reducing the search space as much as possible. Constraints are used to remove the values from the variable domain that can not belong to any solution.

Branching is decomposing the problem in subproblems and discovering the subproblems. All the possible values are tried until a solution is found or it can be proven that there is no solution.

The structure of the constraint can be explored to prune the search base as best as it can. This is the strength of constraint programming.

### Computational paradigm

- Feasiblity check:
Can a constraint be satisfied given the values in the domains of its variables.
- Pruning:
If the constraint is satisfiable, determining which values in the domains can not be part of any solution.
- The Propogation engine:
This a simple (fixpoint) algorithm which is the core of any constraint-programming solver. The basic idea behind the algorithm is, selecting a constraint and checking its feasiblity. If it is not feasible, the algorithm returns failure, else pruning algorithm related to the constraint is applied until no constraint can remove any value from the domain of its variables. Each constraint has a dedicated algorithm.

### Linear constraints over integers

##### Consider a constraint
$$ a_1x_1 + . . . + a_n x_n \ge b_1y_1 + . . . + b_my_m$$

$$ a_i, b_j \ge 0 \ are \ constants
\\ x_i, y_j \ are \ variables \ with \ domains \ D(x_i), D(y_j) $$

##### Feasiblity test
Checking the feasiblity of the constraint, the constraint is satisfied if for the largest possible value of left hand side and smallest possible value of right hand side, the constraint is satisfied.

$$ a_1 max(D(x_1)) + . . . + a_n max(D(x_n)) \ge b_1 min(D(y_1)) + . . . . . + b_m min(D(y_m)) $$

$$ l = a_1 max(D(x_1)) + . . . + a_n max(D(x_n))
\\ r = b_1 min(D(y_1)) + . . . . . + b_m min(D(y_m)) $$

where *l* denotes the largest value of the left hand side *r* denotes the smallest value of right hand side for the given constraint.

##### Pruning
$$ a_i x_i \ge r - (l - a_i max(D(x_i))) $$

thus,

$$ x_i \ge \lceil {r - (l - a_i max(D(x_i))) \over a_i} \rceil $$

and

$$ y_j \le \lfloor {l
(r - b_j min(D(y_j))) \over b_j} \rfloor $$

### Cryptarithmatic puzzles

Another classic example of Constraint programming is Cryptarithmatic puzzles.

A cryptarithmetic puzzle is a mathematical exercise where the digits of some numbers are represented by letters (or symbols). Each letter represents a unique digit. The goal is to find the digits such that a given mathematical equation is verified.
Let us consider

CP + IS + FUN = TRUE

Let us see the stepwise method:
1. Modelling the problem -
The constraints are:
- The equation: CP + IS + FUN = TRUE
- Each of ten letters must be distinct digits
- C,I,F and T are non-zero (as we do not write leading zeroes in numbers)
2. For Feasiblity checking and Pruning:

This step can be performed by coding up the propogation engine. The important parts of the code are
1\) The function which ensures that all the letters have different values.
2\) The function which creates constraints that enforce add and carry operations.

### Rich language of constraint programming:

Example of Magic series -
A series $$ (S_0,...,S_n) $$ is magic if $S_i$ represents number of occurences of i in S

for example
$$ 2,1,2,0,0 $$ is a magic series which can be seen from the following table -

| | 0 | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|---|
|Occurences| 2 | 1 | 2 | 0 | 0 |

We use the concept of Reification for obtaining a magic series.

Reification:
- The ability to transform a constraint into 0 or 1 variable
- Where the variable has value 1 if constraint is true and 0 if the constraint is false.

Thus for finding the magic series, say for n=5
the stepwise execution can be given by
1. Calculating the frequency of occurence of k in the series and storing in an array at kth index
For this, we will loop through the series and increment a count if we get series[i] = k.

Reification comes in play in this step.

Consider that every decision variable has been already given a value, and now we are checking if condition hold for that value, that is does the number actually have that much occurences. If the condition is satisfied, we assign it a value 1 else 0.

Looking at this in terms of coding, we develope ternary constraints with boolean variables.
Constraint booleq(b,x,v) holds if b is equal one and then x is to be equal to v, or if b equals zero, then x is to be different from v.

In terms of Boolean algebra:

$$booleq(b,x,v) \iff (b = 1\ \land x =v)\ \lor (b=0\ \land x \ne v) $$

So initially we considered reified constraints, and replaced them by these ternary constraints and their new booleq values.
Thus we have a system which reasons about natural, simple constraints between booleq variables and other variables.

#### Stable Marriage Problem
This is a scientific problem.
we have a bunch of men and a bunch of woman,and we have to marry them together. The inputs that we get, is that every woman is going to provide a ranking for the man.
And similarly every man is going to do the same for every woman.

The stability rules for a marriage are -
A and B are married, but according to the rankings they provide, say A has given a higher rank for C than B and similarly B has given a higher rank for D than A. Thus A and B want to switch over such that A is with C and B is with D.

But the switch is not possible because C is married with say E who has a higher rank than A with respect to C and D is married with say F who has a higher rank than B with respect to D.

As the switch is not possible, the marriage is stable.

In terms of coding, the basic conditions that we follow are
For every man, the husband of the wife of that man is to be the man itself.And the wife of the husband of a woman has to be the woman herself.

The array of variables is indexing another array of variables, we are using this very expressive feature of constraint programming.

Looking at the logical constraints:
If a man prefers a woman w over his wife, then we must have that w prefers her husband over m.

Similarly, if w prefers m over her husband, then m must prefer his wife over m.

The two interesting features of this problem-
- Element constraint
The ability to index an array/matrix with a variable or an expression containing variable
- Logical combination of constraints
can be handled by reification for instance

More about the features
1. Element constraint
variables x and y
c is an array of integers
constraint x = c[y]

These constraints can be used for pruning the search base.

### Global constraints

Global constraints capture the combinatorial substructures arising in many applications.They make modelling easier. In terms of problem solving, global constraints exploit dedicated algorithms and convey the problem structure to the solver so that they don't need to rediscover it.

A simple example of the global constraint is the$$ alldifferent (x_1,x_2,..x_n)$$ constraint which implies all the values x1,x2..xn are different.

let us see the application of this global constraint using an example,

**8 queens problem using alldifferent constraint** :

initially we saw that the conditions for the 8 queens problem is $$row[i] \ne row[j]$$$$row[i]+i \ne row[j]+j$$$$row[i]-i \ne row[j]-j$$ $$\forall \ i,j \in [1..8] $$

we can also express it as $$alldifferent(row) $$$$alldifferent(all(i\ in\ R)\ row[i]+i)$$$$alldifferent(all(i\ in\ R)\ row[i]i-i)$$ where R = [1..8]
There isn't a big difference when we look at both for the first time, but the statement alldifferent(all(i int R) row[i]+i) means take all the row[i]+i and check if all of these are different.

**checking the feasibility of the all different constraint :**

the constraint is $$C(x_1,x_2..x_n):where\ x_1\ has\ domain\ D(x_1),\ x_2\ has\ domain\ D(x_2),..,\ x_n\ has\ Domain\ D(x_n) $$

$$\ni\ v_1\in D_1,\ v_2\in D_2,..\ v_n\in D_n:
C(x_1=v_1,x_2=v_2..x_n=v_n)=true
$$

Having checked the feasibility of the constraint, now we will see how global constraints help pruning the search space better.

Consider, $$ D1\ = \{1,2\}$$$$ D2\ = \{1,2\}$$$$ D3\ = \{1,2\}$$

We can say that logically this is not feasible as there are 3 variables and only 2 values(pigeon hole principle).

when we check individually $$x1\ne x2,x2\ne x3,x3\ne x1 $$ as $$(x_1=1,x_2=2)\ satisfies\ x_1\ne x_2 $$$$(x_2=1,x_3=2)\ satisfies\ x_2\ne x_3 $$$$(x_3=1,x_1=2)\ satisfies\ x_3\ne x_1 $$ seperately these constraints are satisfied but if we put global constraint alldifferent(x1,x2,x3) these don't satisfy.Hence the global constraint helps us prune the search space more effectively.
Global constraint interacts with all the domains at the same time so helps in pruning the search space better.

SUDOKU :
$$ $$
$$ $$
We are going to solve sudoku using constraint programming!.So,what are the variables here? every square has a decision variable and its value will be the number associated with the square.

**What are the constraints here?**

each value of the square should be different from the values in the same row,same column and the values in the respective square.

expressing this in terms of all different constraints,
$$ forall(i\ in\ R):\ \ \ alldifferent(all(j\ in\ R)\ S[i,j])\ \ \ \leftarrow for\ rows$$$$\ forall(i\ in\ R):\ \ \ alldifferent(all(j\ in\ R)\ S[i,j])\ \ \ \leftarrow for\ column$$$$forall(i\ in\ 0..2,j\ in\ 0..2):\ \ \ alldifferent(all(r\ in\ i*3+1,..i*3+3,c\ in\ j*3+1,..j*3+3)\ S[i,j])\ \ \ \leftarrow for\ squares$$

The system starts propagating using these values,if there are 2 values possible then system makes a choice.

The following is the sample code for a sudoku problem:

def dataNormalize (data):
    """
    args: data; output from sudoku_solve()
    returns: Normalized output of input - Diplayed at console
    """
    ans=""
    sudoku_nums = [ eachPos[1] for eachPos in sorted( data[0].items() ) ]
    for step in range(0,81,9):
        print(sudoku_nums[step:step+9])
        ans = ans+str(sudoku_nums[step:step+9])+"<br>"
    #for step in range(0,81,9):
    return ans

# Solves the sudoku puzzle
def sudoku_solve ():
    """
    args: None
    returns: Sudoku solution
    return type: list
    description:
        * Creates problem instance, sudoku = Problem()
        * Adds sudoku input and their indices as variables
        * Adds constraints to the problem
            1. No two numbers in a row should be same
            2. No two numbers in a column should be same
            3. No two numbers in a 3x3 box shoud be same
        * returns the solution as a list
    """
    puzzleNums = "9 0 5 0 0 0 0 0 8\n4 0 0 5 7 0 1 0 6\n0 2 7 6 0 0 0 4 0\n0 9 6 0 0 3 5 1 2\n7 0 4 0 1 0 3 0 0\n2 1 0 9 8 0 0 0 4\n0 8 1 0 0 4 0 9 0\n3 0 0 8 0 0 0 5 1\n0 0 2 0 0 7 0 6 0"
    print(puzzleNums)
    # stores the numbers in a list. Ex: [1,2,9,0,3...]
    puzzleNums = [ int(eachNum) for eachNum in puzzleNums.split() ]
    # Problem instance created.
    # Recursive backtracking is used here
    sudoku = Problem( RecursiveBacktrackingSolver() )
    # List of 9x9 sudoku puzzle indices. Ex: [(0,0), (0,1).. (9,9)]
    sudokuIndex = [ (row, col) for row in range(9) for col in range(9) ]
    # adding variables to the sudoku instance
    for eachIndex,eachNum in zip(sudokuIndex, puzzleNums):
        # If empty location is found, its range is set to 1-10
        if eachNum == 0:
            sudoku.addVariable(eachIndex, range(1,10) )
        # If not an empty location, its a value is assigned
        else:
            sudoku.addVariable(eachIndex, [eachNum] )

    # constraints for each row and column
    # counting from 0-9 (numeber of rows/ columns)
    var = 0
    for aCount in range(9):
        # A list of locations present in a row.
        rowIndices = [ (var, col) for col in range(9) ]
        # Adding constraint
        # No two numbers in a row should be same
        sudoku.addConstraint( AllDifferentConstraint(), rowIndices )
        # A list of locations present in a column
        colIndices = [ (row, var) for row in range(9) ]
        # Adding constraint
        # No two numbers in a column should be same
        sudoku.addConstraint( AllDifferentConstraint(), colIndices )
        var+=1

    # constraints for each block (3x3) of board
    # Finding all boxes in sudoku board. Its 9 in this case
    rowStep = 0
    colStep = 0
    while rowStep < 9:
        colStep = 0
        while colStep < 9:
            # list of locations present in a box
            boxIndices = [ (row, col) for row in range(rowStep, rowStep+3) \
                            for col in range(colStep, colStep+3)]
            # Adding constraint
            # No two numbers in the box should be same
            sudoku.addConstraint( AllDifferentConstraint(), boxIndices )
            colStep+=3
        rowStep+=3
    # return the solution
    return sudoku.getSolutions()

**SYMMETRY:**

Exploring symmetric parts of the search space is just repeating the same procedure twice.There are two kinds of symmetries:
* variable symmetry
* value symmetry

**Variable Symmetry:**

We will see this using an example. It is called the BIBD problem i.e balanced incomplete block designs.

**problem:**

input : v,b,r,k,l

output : A v by b 0/1 matrix with exactly r ones per row,k ones per column and a scalar product of value l.

eg:for input(3,3,2,2,1):

| 1 | 1 | 0 |
| ----- | ----- | ----- |
| **0** | **1** | **1** |
| **1** | **0** | **1** |

**Can you see any symmetries here?**

We will look for symmetries using a bigger example.lets say we take (7,7,3,3,1):


Swap any row or column ,you can see the consitions still hold.

**how to break variable symmetry?**

ans: impose lexicographic order.

eg:

left is lexicographically greater than the right one.

**value symmetry:**

Take the example of scene allocation.The days in scene allocation are interchangeable i.e swapping day1 and day2 is also a solution.If S is a solution then P(S) is also a solution where the days of S have been permuted by permutatuion p.

**how can we eliminate these symmetries?**

You have to look at the days aldready allocated and add one more extra day.
$$D(S_k)\ =\ \{ 1,2,..max(S_1,S_2..S_{k-1})+1\}$$
**REDUNDANT CONSTRAINTS**

They don't exclude any solution but they reduce the search space.

We will see about redundant constraints using the magic series:

A series $$ (S_0,...,S_n) $$ is magic if $S_i$ represents number of occurences of i in S

for example
$$ 2,1,2,0,0 $$ is a magic series which can be seen from the following table -

| | 0 | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|---|
|Occurences| 2 | 1 | 2 | 0 | 0 |

while constructing the solution can the entry under four have the value 17?
| | 0 | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|---|
|Occurences| ? | ? | ? | ? | 17 |

The series itself is of length 5 so you can't put 17 occurences of 4.Hence, the number of occurences is bounded.

so introducing the redundant constraint,
$$sum(i\ in\ D)\ series[i]\ =\ n
$$

This constraint helps in pruning search space better.We can deduce another constraint due to the definition of magic series:
$$sum(i\ in\ D)\ i*series[i]\ =\ n
$$

* first role of redundant constraints:
1. express the properties of the solution
2. boost the propagation of other constraints
* second role of redundant constraints:
1. provide more global view
2. combine existing constraints
3. improve communication between domains

_______________________________________________________________________________________

**Car Sequencing problem**

To illustrate redundant constraints, visualise a car sequencing problem, where cars go into an assembly line for options to be applied to them. Each production unit of the option has a capacity constraint, for example, at most 2 out of 5 successive cars can require a moonroof.
Problem:
So, we have a list of options, i.e., option 1, option 2, etc. and a class of car requirements that shows which options are needed and not needed for each class. There is a demand constraint of how many cars of each class should be included in the assembly line and a capacity constraint for each option.

To solve it:
We start by defining the demand constraint, that the sum of slots in the assembly line ends up producing the required demand of each class type. Then define the setup variables of option required in slot. Then define the capacity constraint for each option.
An important point is to merge the capacity and demand constraint which will reduce the search base:
Consider an option o where at most 2 out of 3 consecutive cars can have this option and 12 cars need this option. This implies that only 2 out of the last set of 3 slots can have this options, therefore out of the remaining slots at least 10 cars have to be included. Repeating this constraint, out of the second last set of 3 slots at most 2 cars can be included, therefore out of the remaining preceding slots at least 8 cars have to be included. This propagation greatly reduces the search base and gives us a solution.

INTERESTING FEATURE:
We used refine, element and sum constraints.

**Dual Modeling**

If there is no one way of modeling a problem, we can put 2 models into the system and link them using constraints.

For example, the 8-queens problem.

Problem:
The first model was to associate a decision variable with each column. The other model was to associate a decision variable with each row.
To solve it:
After defining the row and column constraint, the important thing is to define the constraint that links both the models: For a row and a column, if the row of column c is r then the column of r has to be equal to c and vice versa. This not only gives a link between the models, we can propagate from one model to the other which gives us a deduction on both.

### Implementing global constraints

We are going to show binary knapsack and alldifferent constraint examples. The idea is to combine feasibility and pruning.
*Golden standard of pruning* : *If value v is in the domain of variable x then there exists a solution to the constraint with value v assigned to variable x*

**Binary knapsack**
General problem:

$$l \le \sum_{k=R} w_kx_k \le u $$$$\forall \ x_k \in \{0,1\} $$

Example:
$$10 \le 2x_1 + 3x_2 + 4x_3 + 5x_4 \le 12 $$

To solve it:
1. Forward phase: Compute feasibility, keep dependency links.
2. Backward phase: Remove values that don't satisfy constraint, i.e, pruning; or update dependency links.

For this example we create paths based on whether we take or don't take each variable and see where it leads, i.e, what sum it results in. This is the forward phase. In the backward phase we remove all paths that lead to a sum that is not 10, 11 or 12. This gives us a result $$x_4 = 1$$

Therefore we prune the value 0 from the domain of x4.

**Alldifferent constraints**
Consider a problem: $$x_1 \in \{1,2\}, x_2 \in \{2,3\}, x_3 \in \{1,3\}, x_4 \in \{2,4\}, x_5 \in \{3,4,5,6\}, x_6 \in \{6,7\} $$
$$ alldifferent (x_1,x_2,..x_6)$$
question: can x4 take value 2?

To solve it:
Step 1 is to check if the constraint is feasible.
So we create a bipartite graph where one type of vertex is the variable and the other type is the values. An edge exists if the value is in the domain of the variable. A matching for a graph G=(V,E) is a set of edges E such that no 2 edges in E share a vertex. A maximum matching M is a matching with the largest number of edges.
Therefore, the feasibility constraint is defined as *a maximum matching M where the number of edges is equal to the number of variables.*

*How to find a maximum matching?*
1. Start with any matching
2. Improve the matching.

To find an improvement, start from a free vertex x, if there is an edge (x,v) where v is not matched then insert (x,v) in the matching. Otherwise, take a vertex v matched to y. Remove (y,v) and add (x,v) from the matching and restart with y instead of x.

Essentially what we used is an alternating path. An alternating path P for a matching M is a path from vertex x in X to a vertex v in V(both of which are free) such that the edges in the path are alternatively in E\M and M.

*How to find alternative paths?*

* Create a directed graph
* Given a matching: edges in the matching are oriented from bottom to top and edges not in the matching are oriented from the top to the bottom.
* We can use depth first or best first search.
* O(|X|+|E|) where X is set of vertices and E is set of edges.

What we did is start at a free edge and go up and down until we reach a free value to assign values to all the edges.

This was feasibility. Now we need to prune.

*How to prune?*

v must be removed from the domain of x if the edge (x,v) appears in no max matching. This can be done easily for this problem using this property:
*An edge belongs to some but not all max matchings iff given a max matching it belongs to either an even alternating path starting at a free vertex or an even alternating cycle.*
This property tells us whether the edge belongs to at least one max matching.

Now,
* Given a matching M, create a directed graph like before but reserve the direction of the edges.
* Search for even alternating path starting from free vertex: P
* Search for all strongly connected components and collect all the edges belonging to them: C.
* Remove all the edges not belonging to M,P or C.
* *Complexity*:*O((|X|+|V|)***|E|)*

**Using these two examples (alldifferent and binary knapsack) we've seen that for each global constraint we can exploit the structure using a specific algorithm.**

---------------------------------------------------------------------------------------
There are two critical aspects in a constraint programming system. One of them has already been discussed - constraint propagation. The other one is 'search'.
Search is based on feasibility information. Constraint programming system prunes the search base based on constraints and feasibility. Search basically explores this information.
### First-Fail Principle
This principle tells you to "try first where you are most likely to fail". That is, if you have a bunch of tasks that you need to finish and you know that one of them is really difficult, you focus on that difficult task first instead of postponing it because you don't want to spend time doing the easy stuff first. By starting with the hard stuff first we try to make sure that we have a small search tree.
`
Example: For a graph colouring problem, we'll try to assign colour first to a node that has maximum neighbours and then we move to the remaining nodes.
`
##### Euler knight problem
Visit all positions of the chessboard exactly once using a knight.
Using the first fail principle,
- First, we have to decide where we are most likely to fail. If we start from the corner of the chessboard, we can see that there are only 2 positions where the knight can go so the corners are tough and hence we start at the corners.

So the first-fail principle is finding the variables that are the toughest to assign, i.e. they have the smallest domains.

#### Search Procedure components
Three major components in search procedures are:
- iterate over the variable
- non-deterministically choose a value for the variable
- add a constraint inside a constraint store

#### Various kinds of search in constraint programming
- variable/value labelling
- value/variable labelling
- domain splitting
- focusing on the objective
- symmetry breaking during search
- randomization and restarts

#### Variable/value Labeling
There are two steps:
- choose the variable you want to assign -- reiterate for the variable
- choose the value to assign -- non deterministic step

Now, we want to apply first-fail principle. So we find the variable that is the toughest to assign. The domain of the variable will be a good indication of what is tough and what is not. If a variable has a smaller domain, it means the variable is probably interacting with a lot of other constraints and hence assigning a value to that variable is difficult. Thus, we choose the variable with the smallest domain. For multiple variables with same domain, we choose the most constrained variable.

The ordering of the variable is dynamic. This is so because, if after reducing the search space, the domain of some other variable(which was originally not the second choice) has the smallest domain we need to choose that variable next.

We can use the Lexicographic criteria in case of the 8-queen problem, where we first check the domain size and if we have ties then priority is given to the queen which is the closest to the middle of the chess board. This is because placing a queen in the middle reduces more values than the case when a queen is placed in corners. Looking in terms of coding perspective, we are considering two criterial here, first the domain size and second, the closeness to the centre of the board.

Since we are using dual modelling in 8-queen problem, where we had variable associated with column and variable associated with row, this is a good example to show how we can both choose a variable ordering in a dynamic fashion, and a value ordering in a dynamic fashion.

we look at the raw variables as the one that we want to assign and we choose the one which has the smallest domain and then we have to assign a value. We choose a dynamic holder for the
variables. Then we choose a dynamic holder for the values. In both cases, you're actually applying the first-fail principal. Thus in constraint programming we can choose a dynamic ordering for the variable and choose a dynamic ordering for the values.

Thus for variable/value labelling, for variable ordering we choose the most constrained variable, that is the variable which is having the smallest domain and which fails most often.
And for value ordering we choose the value which leaves as many options as possible to variables.
This helps in finding a possible solution.

#### Value/variable Labeling
Two steps again:
- choose the value you want to assign
- choose the variable to which you want to assign the above chosen value
This technique is useful in cases when we know that a particular value must be assigned to some variable, like in scheduling problemsand resource allocation problems. For example, in time tabling problem we know that a particular professor *has* to be assigned to particular class.

##### The perfect square problem
The problem: There are several squares of different sizes given to us. We need to rearrange them and pack them to form a single large square.

First we need to find the decision variables. Let's take that to be the x and y coordinates of the bottom-left corner of every given square (You can also choose the top right corner).
Then we identify the constraints. Here, we have:
- all smaller squares must fit in the larger square
- the smaller squares shouldn't overlap

One redundant constraint which is also considered is that, considering a vertical line drawn on the larger square made by joining all the squares, the sum of sides of the squares which the line is intersecting is equal to the size of the larger square.
Now we have everything to write a simple pseudocode for this problem :).
Let us see why we should use value/variable labeling for this problem. We know that there is no empty space in the larger square. Visually, if we are trying to fill up the larger square using smaller squares, whenever we see an empty space we know that it needs to be filled by a square. This is the basic idea behind the following value/variable labeling procedure.

The process which we can follow is -
- Choose a x coordinate p
- For all the squares, check whether a square can be placed at the coordinate p, that is whether the value of bottom left x coordinate for the square is equal to p.
- Repeat this process for all x and y coordinates.

Thus we are taking a value and then checking the square which fits for the value.

#### Domain splitting

Considering example of magic square problem
Numbers are placed in each block such that all numbers are different and the numbers in a each row, column and diagonal sum up to the same number.

Approach we can follow -
Select a square and decide what value it can take, but this is a completely random guess. And assigning value in such a way is a strong commitment.

Instead of this, we can select a variable and split its domain into two or more sets which is a much weaker commitment as compared to the previous approach. For example we can say that the value lies in the upper domain or the lower domain of its actual domain.

This strategy is extremly useful for solving car sequencing problems. The car sequencing problem consists of cars placed on the assembly line where cars require a specific option (leather seats, moonroof) and some capacity constraints on the production units are given (only 2 out of 5 consecutive cars require moonroof). We need to find a sequence of the cars such that the capacity constraints are satisfied.

Domain splitting in car sequencing -
- We focus on the difficult options and decide which slots take these options.
- We do not assign the configurations to the slots, we are just deciding whether the slot can take the option.

So we are splitting the slots in two sets, one which are requiring the options one which are not requiring the option.

#### Focusing on the objective function
Comparing Feasiblity and Optimality:

Till now, our focus was feasiblity branching, that is pruning the search base which essentially provides a lot of information about the problem we are trying to solve. We may also focus on the objective function, that is instead of just looking at the feasible information we can provide reasoning about the objective function itself.

#### ESDD Deployment Problem
Electronic software distribution deployment problem
Serializable data services problem:
The problem is about implementing protocol which can give reliable software.
Where we want to map set of software components to a set of hardware components and we also need to satisfy some reliability conditions. We want the mapping to be as efficient as possible thus we need to reduce the communication traffic.

The problem can be seen as Generalized quadratic assignment problem where a set of data such as the frequency of communication of two components (f), distance between two components (h), decision variables (assignment vector x), set of components (c), constraints (separation and colocation, separation constraint tells that two software components can not be on the same machine and colocation tells two components are on the same machine) and the objective function is to minimize the communication traffic, which can be represented as

$$ \min_{x \in N} \sum_{a \in c} \sum_{b \in c} f_{a,b}\ \cdot \ h_{x_a,x_b} $$

(The multiplication of frequency of communication matrix and distance matrix with respect to the assignments done will represent the communication traffic)

#### Symmetry Breaking in search
The basic idea is to take advantage of the symmetries in optimization problems, by adding constraints that reduce the search space size and eliminate symmetries. Symmetries in a problem increase the size of the search space and therefore, time is wasted in visiting new solutions which are symmetric to the already visited solutions.

Symmetry-breaking constraints can be added to the problem such that some of the symmetric solutions are eliminated from the search space while making sure that atleast one solution exists in the search space. Symmetry is common in many real-life combinatorial problems. For example, certain vehicles in the vehicle routing problem might be identical. For a valid routing plan, every permutation of such identical vehicles yields another valid routing plan with the same objective function value. The same goes for the scene allocation problem we've seen previously for static constraints.

#### Randomization and restarts
Sometimes there is no obvious search ordering but the structure of the problem is such that there is a good ordering. It's just very difficult to find. So in these cases we use brute force. We randomly generate some ordering and if it doesn't work and we can't find a solution in reasonable time we stop early and restart the search by generating a different ordering.
The key idea:
- apply a heuristic but with randomization
- limit the time in the search
- if the time limit is reached, restart the search and possibly increase the limit

Let's go back to the magic square problem discussed in domain splitting. There are very slight modifications to be made in that approach. Instead of selecting the variable with the smallest domain, we randomly select one of the 3 variables which have the smallest domain. Also the entire process continues inside a repeat loop that runs until the time limit is reached. On reaching thee time limit, the time limit is increased by some small amount and the search starts again.

### Constraint-based scheduling
Example:
Minimizing the duration of a big project which has which needs to take in consideration different points for scheduling such as
- precedence constraints
There may be some task which needs to come before some other task.
- disjunctive constraints
This means two tasks assigned on the same machine can not overlap.

Taking a real life example of building a bridge, the different components that need to be built need to be in an order and the resources that are used to build in the tasks can be exactly same and thus need to be shared.

The method of model-based computing is used to state the problem. For stating the problem domain specific concepts such as activities, resources, precedence constraints are used. Behind the scene, these are compiled into decision constraints and global variables.

### The Jobshop scheduling problem

In this problem, we have a set of tasks that we have to schedule, where
- Each task **t** has a duration **d(t)** associated with it.
- Each task **t** executes on machine **m(t)** and following the disjunctive constraints, two tasks scheduled on the same machine can not overlap in time.
- There is a set of precedence constraints (b,a)
which states that task **a** must start after task **b** has been completed.

The main objective of the problem is to minimize the project completion time.


The Job1 represents the sequence of activities and the activities with the same colour use the same machine for execution, for example as shown in the figure, all the tasks coloured in blue use the Machine k and that is why they can not overlap in time. In order to do so, the machine must handle the tasks in a sequential manner and thus we need to find an ordering of the tasks associated with a particular machine.


The machine executes the jobs sequentially where the ordering of the jobs depends on the precedence constraints provided. In the figure above we have all the possible links between every two tasks which are using a particular machine. We have to choose a subset of these links which are making a sequence. One of the orderings can be -


Thus, all the tasks associated with a machine are in a well defined order and machine follows the order while executing the tasks.

Once we have defined the order of tasks for every machine, we just need to consider the precedence constraints. We minimize the project duration under the precedence constraints, which is a polynomial time problem and thus we can use topological sorting for this purpose. For more sophisticated precedence constraints which also involve distances we use transitive closure (Floyd-Warshall algorithm).

**Model compilation**
- Every activity has three variables, the start date, the end date and the duration of activity, where the constraint linking these variables is
s + d = e
Thus for each activity we have three interdependent decision variables linked by the above constraint.

- According to the precedence constraint (b,a)
The start date of task a should be greater than or equal to the end date of task b.

- The resource constraints are compiled into global constraints which are disjunctive in nature, disjunctive($t_1$,...,$t_n$) tells that the activities $t_1$ to $t_n$ can not overlap.

#### Feasibility of Disjunctive constraints

Checking the feasiblity of Disjunctive constraints:
If for a single machine, we are given 3 jobs and the interval in which they can be scheduled and we want to schedule these tasks in such a manner that there is no overlap.
But, detecting feasiblity of Disjunctive constraints is a NP-complete problem.
Thus, instead of solving this exact problem, we will try relaxing the constraints.
The notation used is
$$s(\Omega) = min(t \ in \ \Omega) \ min(s_t)\\
e(\Omega) = max(t \ in \ \Omega) \ max(e_t)\\
d(\Omega) = sum(t \ in \ \Omega) \ min(d_t)$$
$s(\Omega)$ is the earliest time at which any task in $\Omega$ can start.
$e(\Omega)$ is the latest end date that any task in $\Omega$ can have.
$d(\Omega)$ is the total time taken by all tasks in $\Omega$

The Feasibility test we apply is
$s(t) + d(t) \le e(t)$

A better Feasibility test can be given as
for all $\Omega \in T:s(\Omega) + d(\Omega) \le e(\Omega)$
where we are looking at all subsets inside Task T and we need to consider only quadratic number of subsets.
The task interval for an interval t~1~ to t~2~ is the number of tasks having start date after t~1~ and end date before t~2~ and is represented as
$s(t_1,t_2) = \{ t \ in \ R \ | \ s(t) \ge s(t_1) \ and \ e(t) \le e(t_2) \}$
Thus now our feasibility test only looks at the all the task intervals.
The complexity is $O(|T|^3)$ as there are quadratic number of task intervals and the test itself is linear time.

Another algorithm which is quadratic time can be given. In this algorithm end date e is fixed and for tasks we perform the following process


where the task having latest starting date is considered first.
We can do better than quadratic time, where we use preemptive scheduling and we get $O(|T|log|T|)$ algorithm.

#### Disjunctive Pruning
Edge finding rules are the set of rules used for pruning.
- Select a set of tasks $\Omega$ and a task $i \notin \Omega$
- Determining if $i$ must start after all tasks in $\Omega$:
$s(\Omega \cup i) + d(\Omega \cup i) > e(\Omega)$
then we have to update the starting time of i accordingly:
$max(\gamma \subseteq \Omega)s(\gamma) + d(\gamma)$
and same can be done for ending date.
The edge finding rules can be strongly enforced in polynomial time.

Thus the basic strategy for Disjunctive Scheduling involves
1. Choose a machine
2. Sequence the tasks for the chosen machines
3. Repeate the process for other machines

For choosing the machine, we can apply first-fail principle. And in terms of choosing taks, we look at the tasks which can be scheduled first or last and the task is as tight as possible.

### Appendix:
1) Discrete optimization:
Discrete optimization is a branch of optimization in applied mathematics and computer science. some or all of the variables used in a discrete mathematical optimisation are restricted to be discrete variables—that is, to assume only a discrete set of values, such as the integers.
2) Decision variables:
Variables is a set of quantities that need to be determined in order to solve the problem. The variables are sometimes called decision variables because the problem is to decide what value each variable should take.
3) Domain of decision variables:
The domain of decision variables is the set of all possible values that can be taken by the variables.
4) Global constraints:
A global constraint is a constraint that captures a relation between a non-fixed number of variables. An example is the constraint alldifferent(x1, . . . , xn), which specifies that the values assigned to the variables x1, . . . , xn must be pairwise distinct. Typically, a global constraint is semantically redundant in the sense that the same relation can be expressed as the conjunction of several simpler constraints. Having short hands for frequently recurring patterns clearly simplifies the programming task. What may be less obvious is that global constraints also facilitate the work of the constraint solver by providing it with a better view of the structure of the problem.
5. Symmetry:
Solution Symmetry - A solution symmetry is a permutation of the set of <variable, value> pairs which preserves the set of solutions.
Problem Symmetry: A problem symmetry is a permutation of the set of <variable, value> pairs which preserves the set of constraints.
6. Redundant constraints:
A redundant constraint is a constraint that can be removed from a system of linear constraints without changing the feasible region.
7. Domain splitting:
This involves splitting a problem into a number of disjoint cases and solve each case separately. The set of all solutions to the initial problem is the union of the solutions to each case.
8. Disjunctive constraints:
Disjunctive constraints are widely used to ensure that the time intervals over which two activities require the same resource do not overlap in time.
9. Constraint based scheduling:
Constraint-based scheduling is an approach for solving real-life scheduling problems by stating constraints over the problem variables. By providing generic constraint satisfaction techniques on one side and specialised constraints on the other side, constraint programming achieves a very good generality and efficiency and thus it becomes very popular in solving real-life combinatorial (optimisation) problems.
10. Symmetry Breaking:
the method of symmetry-breaking constraints can be used to take advantage of symmetries in many constraint satisfaction and optimization problems, by adding constraints that eliminate symmetries and reduce the search space size.
Symmetries increase the size of the search space and therefore, time is wasted in visiting new solutions which are symmetric to the already visited solutions. The solution time can be reduced by adding new constraints, referred as symmetry breaking constraints, such that some of the symmetric solutions are eliminated from the search space while preserving the existence of at least one solution.