# Fundamentals of Constraint Processing

## Lecture 2

### Resources

• check website – has many, many links
• conferences
• journals
• include logic programming and CSP
• Linear Programming, Integer Programming, Mixed Integer Programing, Dynamic Programming
• journals are also pretty big – and tend to be easier to get into
• many good ways to get jobs with this

### Constraint Satisfaction 101

• examples
• generating optimal decisions
• have unary, bynary, n-ary constraints
• often have many choices, but restrictions can make it easier to make the right decision
• modeling constraints remains an art
• sets of variables with sets of choices, and aset of constraints restricting combinations of values
• applications
• radio resource management
• databases
• temporal and spatial reasoning
• allocation
• design/config
• graphics, visualization, interfaces
• verification and engineering
• HCI and decision support
• molecular biology
• analytical chemistry
• robotics, machine vision, computational linguistics
• transportation
• qualitative and diagnostic reasoning
• constraint processing is modeling, plus inference and search
• modeling – variables, domains, constraints, query
• inference – enforcing consistency (filtering) and propogation (AC, PC)
• search – systematic (chronological backtracking, with or without intelligence, etc) or non-systemactic (hill climbing, taboo, etc)
• Real Example
• Netherlands have dense network
• wanted more robust schedule that’s more effective, increasing profit
• used OR and AI
• Singapore
• large container hub
• has custom, special loading built using CP
• CP is:
• solving decision problems
• with arbitrary constraints
• providing concise and high-level feedback about alternatives and conflicts
• Very Practical

### Defining a problem

• has a given and a question
• given is a set of objects, the relations, etc
• question ex: find $$x$$ such that condition $$y$$ is satisfied
• these can be simple or advanced
• a problem must always, always, always have a question!
• Given $$\mathcal{P} = (\mathcal{V}, \mathcal{D}, \mathcal{C})$$
• $$\mathcal{V} = \{V_1, V_2, \ldots, V_n\}$$ Variables
• $$\mathcal{D} = \{D_{V_1}, D_{V_2}, \ldots, D_{V_n}\}$$ Domains for Variables
• Constrants $$\mathcal{C} = \{C_1, C_2, \ldots, C_l\}$$ where $$C_{V_i,V_j,\ldots,V_k} = \{(x,y,\ldots,z)\} \subseteq D_{V_1} \times D_{V_2} \times \ldots \times D_{V_n}$$
• Query whether we can find a value for each variable such that all constraints are satisfied, queries can include weights (making it a Constrained Optimization Problem)
• Various levels of consistency
• AC
• GAC
• SAC
• SGAC
• Sudoku can be done with consistency, but whether or not search is required for all
• find solution – decisions
• find sumber of, all solutions – counting
• find set of constraints that can be removed so that a solution exists – optimization
• specials
• binary CSPs have only two variables
• restricted to $$\{0, 1\}$$, boolean CSP
• finite, discrete domains, enumeration can work
• continuous domains require sophisticated algebraic techniques are needed – consistency techniques are then used on domain bounds

## Lecture 3

• always a given $$\mathcal{P} = (\mathcal{V}, \mathcal{D}, \mathcal{C})$$
• Constraints are relations
• relations are a subset of the cartesian product of $$n \geq 2$$ sets
• relations can be represented as a table, which are refered to as allowed tuples, or supports, which is a table constraint, being an enumerated
• extension in a set with all members enumerated
• conflicts are the set of tuples that are no good
• Constraints can also be in intention – they’re defined in terms of a logical function, equivalent to extension, but can be easier to understand
• A check function should always be a simple implementation – to build with them
• Code must always be well structured!

## Lecture 4

• $$P = (V, D, C)$$
• $$V$$ variables
• $$D$$ domains
• $$C$$ constraints
• Constraints are defined as $$C_1 = \langle\mathrm{scope}(C_1), \mathrm{rel}(C_1)\rangle$$
• Scope is the variables it discusses – the set of variables over which the constraint is defined
• relation is an abstract relation – may be in extension (listed as either supports or conflicts) or intension (roughly as a function or boolean expression)
• Also have arity, the cardinality of the scope
• universal constraints allow any member of the relevant cartesian product, but may be induced so as to be something else – equivalent to know constraint, and is binary alone
• VVP – Variable Value Pair
• make sure to implement check function, and to do so in a very independent manner
• keep track of a number of constraint checks, always incrementing for every check
• will be writing abscom to parse
• Graph representation
• Macro representation
• Variables are represented as nodes (vertices)
• domains as node labels
• constraints as arcs (edges) between nodes
• hypergraphs allow for special constraint nodes, or use a bubble to connect them instead – the hyperedges
• relations in intension are defined by set-bulider notation
• used when not practical/possible to list all tuples
• define types/templates of common constraints
• linear constraitns
• all-diff constraints
• at most
• TSP-constraints
• cycle-constraints
• constraints implemented
• in extension
• set of tuples (list/table)
• binary matrix (bit-matrix)
• multi-valued decision diagrams
• in intension
• constrained decision diagrams
• predicate functions