# Fundamentals of Constraint Processing

## Table of Contents

## 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

- generating optimal decisions
- 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

- in extension