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!

$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

examples of modeling

• can have temporal csp

• graph or map coloring – requires 4

• resource allocation – airline trip planning, list coloring

• product configuration – allowed components and what they require/forbid

• logic puzzles

Constraint types

• algebraic constraints

• constraitns of bounded difference

• coloring

• mutual exclusion

• difference constraints

• arbitrary constraints, must be made explicit

Databases

• Join in DB is a CSP

• View materialization is a CSP

Interactive systems

• data-flow

• spreadsheets

• graphical layout systems and animation

• graphical user interfaces

Molecular biologiy

• threading and similar

solutions found by

• detecting components

• NC

• normalize constraints

• NC, AC, other forms of AC

• Search

• Verification

• Solution, Node Vists, Constraint Checks, CPU Time

when implementing AC1, terminate if domain wipe-out occurs

worst case complexity is seldom reached

remember, AC may discover a solution to a CSP, or may find an inconsistent problem (by domain annhilation)

AC3

• for $i \gets 1$ to $n$, do $NC(i)$

• $Q \gets \{(i, j) | (i, j) \in arcs, i \neq j\}$

• while $Q$ is non-empty:

  • select and delete any arc $(k, m) \in Q$

  • if $\mathsc{Revise}(k, m)$ then $Q \gets Q \cup \{(i, k) | (i, k) \in arcs(G), i \neq k, i \neq m\}$

• Check for domain wipe-out!

Remember to deal with Node Consistency – and don't include it in the check count

see lecture 8 notes

AC3 is not only more powerful

$2e + a[2e - n]$

AC3 is $O(a^2 (2e + a(2e - n))) = O(a^3e) = O(a^3n^2)$

AC4 is even more efficient, but requires special bookkeeping, is $O(a^2n^2)$

Variant of AC-3 called AC-2001, but requires cubic space, has yet another variant, AC-3.1$^{m}$, requires different bookkeeping

AC4

• generate m, s, and counter

  • m and s have as many rows as there are VVPs in the problem, m is set to true, s to empty list

  • m is for alive

  • s is for a list of all VVPs that support a given VVP

  • given a vvp, provide a number of supports provided by a given variable

• prepare data structures

  • for every constraint all tuples:

    • when allowed, update s

      • increment counter

• Then process all constraints

  • if counter is 0, remove from domain, and update $m$

  • since $x$ is removed, then for everything such that it was a support, decrement the counter

AC3 tends to be a bit better than AC4

soundness – can trust

complete – will always find a solution if exists

more efficient AC variants are useful for use during search

but when enforcing AC during search, you must be able to keep track of what was removed

remember properties are not the same as the algorithms! there may be many algorithms to implement each property!

most consistency methods are local initially

• node/arc remove inconsistent values

• path removes inconsistent tuples

  • used when you have positive tables of supports

• they get closer to the solution

• reduce the size of the problem

• are cheap (polynomial time)

• choice of consistency properties helps to reduce time to solution

Variables $V_i$, $i \in [1, n]$

Domains $D_i = \{V_{i1}, v_{i2}, \ldots, v_{iMi}\}$

Constraint between $V_i$ and $V_j$ : $C_{i,j}$

Constraint graph $G$

Arcs of $G$: $\mathrm{Arc}(G)$

Instantiation order is static or dynamic

lang primitives are from lisp

Data structures

• $v$ is a 1 by $n$ array to store assignments, $v_0$ is the root, backtracking to this indicates insolvability, $v_i$ is the assignment to the $i$th variable

• $domain$ is the original domain

• $current-domain$ is the current domain, must be updated on back-tracking

• check is as before

Generic form

• takes n, status

• set consistent to true

• status to unknown

• $i \gets 1$

• while the status is unknown

  • if consistent

    • $i \gets \mathrm{label}(i, consistent)$

    • else $i \gets \mathrm{unlabel}(i, consistent)$

  • if $i > n$

    • set status to solution

    • else if $i = 0$, set status to impossible

label and unlabel functions are provided by the backtrack algorithm

label is forward move, unlabel is backward move

For BT

• label

  • when $v_i$ is assigned a value from the $current-domain_i$, we perform back-checking against past variables

  • if back-checking succeeds

  • return $i + 1$

  • else, remove assigned value from current-domain[i], assign next value, etc

  • if no value exists, set consistent to false

  • function

    • takes i, consistent

    • set consistent to false

    • for v[i] in each element of the current domain while not consistent

      • set consistent to true

      • for h from 1 to i - 1 and while consistent

        • set consistent to check(i, h)

      • if not consistent

        • then remove i from current-domain

    • if consistent, return i+1, otherwise i

• unlabel

  • current level is set to $i - 1$

  • for future variables $j$, reset the current-domain

  • if the domain of $h$ is not empty, set consistent to true

  • Function

    • takes i, consistent

    • set h to i - 1

    • set current-domain[i] to domain[i]

    • remove v[h] from current-domain[h]

    • set consistent to current-domain[h] not-equal empty-set

    • return h

• label does the actual instantiation

Cheeseman 1991

Order parameter

Probability solution exists for random problems is almost 1

there's a critical value whereby, after it, probability is almost 0

around the critical value, the probability is around 0.5

cost of solving drops sharply as it gets further to the right of the critical value, but high as it goes to it

around .5 probability is high cost of solving, no matter the algorithm, this is referred to as a phase transition

conjecture regarding the characterization of NP complete problems

applies to detecting/implementing arc-consistency

random graphs are almost always easy to to color – conjecture from famous paper

• graph coloring is a reduction operator

• friends are vertices with the same neighborhood

• this is the degree

For CSPs, it's either density or tightness

currently effects the way of expirement conduct – try and deal with the hardest problems

but be careful not to focus exclusively on the redior around the critical value

Run on random CSPs – given statistical analysis

Vary params $\langle n, a, t, p \rangle$

• $n$ – number of variables

• $a$ – domain size$

• $t$ – tightness $\frac{|\mathrm{forbidden tuples}|}{|\mathrm{all tuples}|}$

• $p$ – proportion of constraints $p = \frac{e}{e_{max} - e_{min}}$, also $\frac{2e}{n(n-1)}$

• $t$ and $p$ will be between 0 and 1

• Can have issue with uniformity, difficulty (phase transition), solvability

• empirical studies can be done simply by varying one of the parameters

• do it (Model B):

  1. generate $n$ nodes

  2. generate a list of $\frac{n(n-1)}{2}$ tuples of all combinations of 2 nodes.

  3. choose e elements from the above list as constraints to go between the $n$ nodes

  4. if the graph is not connected, throw away, go back to step 4, otherwise proceed

  5. generate a list of $a^2$ tuples of all combinations of 2 values

  6. For each constraint, choose randomly a number of tuples from the list to gparantee tightness $t$ for the constraint.

• Model B instances may be flawed, but it's rare

keep track of path – an array of the instantiations thus far and to be created

remember what unlevel does – actually performs backtracking

many different ways to order variables

when doing value-ordering, use lexicographic ordering!

eventually, variable ordering heuristics must be broken with lexicographic ordering

Kondrak and Van Beek, IJCAI 95

Dechter 5, 6

most backtracking algorithms are evaluated empirically

performance depends heavily on problem instance

is therefore average case analysis

representativesness of the test problems

CSP in NP complete – always possible to construct examples where BJ/CBJ are worse than BT

comparison criteria are different

paper gives theroretical approach

• states by number of nodes visited

• number of constraint checks

BT, CBJ perform the same amount of consistency checks

bm reduced consistency checked

MD does not affect number of nodes visited

FC-CBJ may visit more nodes than CBJ

proves correctness of BJ/CBJ

determines partial order between algos

proves BJ, CBJ are correct

proves FC never visits more nodes than BJ

Improves BMJ and BM-CBJ to perform even fewer consistency checks

provides framework for characterizing future BT algorithms

BT extends partial solutions – solutions consistent with a set of uninstantiated values if it can be consistently extend to the variables – that is, create a new partial solution extended by one variable s.t. it's still consistent

Dead end – when all values of current variables are rejected

lower level are closer to the root

higher levels are closer to the fringe

2 BT algos are equiv if on every csp they generate the same tree and perform the same consistency checks

Lemma 1: If BJ bactkracs to variable x_h from a dead end at x_i, then (a_i \ldots a_h) is not a valid partial solution

sufficient conditions

• BT visits a node if parent is consistent

• BT visits a node if its parent is consistent with all variables

• CBJ vists a node if its parent is consistent with all sets of variables

• FC vists a node if it is consistent and its parent is consistent with all variables

Necessary Conditions

• BT visits a node only if parent is consistent

• BT visits a node only if its parent is consistent with all variables

• CBJ vists a node only if its parent is consistent with all sets of variables

• FC vists a node only if it is consistent and its parent is consistent with all variables

BT visits all nodes FC visits

BJ vistis all nodes CBJ visits

CBJ and FC are not comparable.

FC will visit no more nodes than BJ

BT and BM are equivalent, as are BJ and BMJ

proof of correctness – termination, soundness, completeness

extends for seeking all solutions

BM hybrids should be fixed, by changing MBL to an $n \times m$ array, creating BM2, BMJ2 and BM-CBJ2

assumptions

• finite domains

• binary constraints

Chapter 6, Tsang is req'd reading

Dual viewpoint heuristics for binary constraint satisfaction problems is recommended reading

IN BT, some orders have fewer backtracks

in lookahead, some ordering detect failure earlier

variable ordering is often the most constrained variable

value ordering is often the most promising value first

using dynamic ordering in lookahead algos often removes the need for intelligent backtracking

Regin and Bessier show that CBJ and similar isn't needed – but not so sure

Select values that don't cause constraint violation – do the most promising value first, avoiding constraint violation

Discover constraint violation quickly – select variables that don't delay discovery of constraint violation, go with the most constrained variable first

Notation: For a given future variable $V_i$, the assignment $V_i \gets x$ partitions the domain of the future variable $V_j$, a set of values consistent with with the assignment of size $\mathrm{Left}(V_j | V_i \gets x)$ and a set of values inconsistent of size $\mathrm{Lost}(V_j | V_i \gets x)$

Value selection of Lost and Left

Value Ordering to quickly find a solution

• min-conflict – orders values according to the conflicts in which they are involved with the future variables – most popular (Minton), $Cost(V_i \gets x) = \sum_{V_j \neq i} \mathrm{Lost}(V_j | V_i \gets x)$

• Cruciality – (Keng and Yu, 1989) $Cruciality(V_i \gets x) = \sum_{V_j \neq i} Lost(V_j | V_i\gets x) / |D_{V_j}$

• promise – most powerful (Geelen, 1992) $Promise(V_i \gets x) = \prod_{V_j \neq i} Left(V_j | V_i \gets x)$, the number of assignments that can be done such that no constraint on $V_i$ is broken.

• Others are defined

Promise

• recognizes domain wipe-out

• product discriminates better than sum

• semantics of promise gives an upper bound on number of solutions

FFP name is contested

• goal is to recognize dead-ends asap to save search effort

• choose ordering that reduces branching factor

• Early ones

  • LD

  • maximal degree

  • minimal ratio of domain size over degree

  • promise for variables

  • Br\'elaz heuristic

  • weighted degree (Boussemart et al, ECAI 2004)

  • graph-based

    • minimal width

    • induced with ordering w*

    • maximal cardinality ordering

    • minimal bandwidth ordering

  • remember to exploit domino effect, especially under dinamic var ordering

  • always state how you are breaking ties – generally lexicographically

  • is often cheap and effective

  • in most cases, suitable for both static and dynamic ordering

• Promise for variables – Sum of the promises of the values, minimize the number of assignments that can be done such that no constraint on $V_i$ is broken. Has upper bound on the number of solutions

Least Domain

Max Domain

Domain/Degree

Promise is based on what has the most promise given the current state

Br\'elaz heuristic – originally used for graph coloring

Remember, variable ordering heuristics are cheap and effective

generally suitable for static and dynamic ordering

graph-based heuristics aren't often used anymore

Br\'elaz

• originally designed for coloring

• assigns most constrained nodes first

• arrange vars in decreasing order of degrees

• color a vertex with maximal degree with color 1

• choose a vertex with a maximal saturation degree (number of different colors to which is it adjacent)

  • if thete's an equality, choose any vertex of maximal degree in uncolored

• color chosen vertex, with lowest numbered color

• if all vertices are colored, stop, otherwise, choose another vertex and continue

wdeg

• All counstraints assigned a weight, initially 1

• every time a constraint is broken, during propagation with look-ahead (constraint causing domain wipe-out), weight is increased

• the weight of an un-assigned variable is defined as the sum of the weights of the constraints that apply to the variable

• the variable with the largest weight is chosen for instantiation

• weights are not reinitialied at back-track

• refined with dom/wdeg

• inspired by breakout heuristic in local search

• However, there mart be places where dom/deg is more efficient than dom/wdeg

• A decay function may help improve this

Graph heuristics

• ordering by elimination or instantiation

• minimal width

  • given an ordering, the width of a node is the number of its parents

  • then the ordering's width is the largest width of any of the nodes

  • sum of degrees is always equal to the number of edges

  • take minimum of the orders, by width – this is the width of the graph

  • this can reduce chance of backtracking, can help to find minimum width ordering

  • Algo:

    • remove all nodes not connected to any others

    • $k \gets 0$

    • while no nodes left in the graph

      • $k \gets 1$

      • while there are nodes not connected to more than k others

        • remove such nodes from graph, along with any edges connected to them

    • return $k$

    • minimal width ordering of the nodes is obtained by taking the nodes in the reverse order that they were removed

• Inducted Width Ordering

  • What happens when you reconnect neighbors of what you remove to each other

From Workday, SaaS company for HR management

work has primarily been in Data Analysis and optimization

go from techniques and technologies to money

Could be a Linear Program

• Measures, Items (index sets)

• indices i, m

• variables Quantity, 0 to N

• model sets, limit, value, weight

• maximize value and quanitity

• but must be withinn weight

big thing is assigning resources in a data center

truck scheduling

• many truck loads that a company has to move

  • origin and destination specified

  • and time windows at origin and destination

• many drivers, many trucks

• some time horizon

• DOT rules

• operational rules

  • returning to base

  • equipment preventative maintenance

• Taking a run at the whole thing is probably too much

  • run a rout model to pick loads that go togethr

  • schedule loads – the big thing for SCPs

  • drivers pick the sets of loads they prefer

modeling

• discrete time forms an integer domain

  • can be clumpy

• use start time of the task as the domain

• constraints like before and after are relatively straightforward

• duration of driving/time windows are prety easy to express

• small disruptions are normally readily repaired by freeing up parts of the model and letting it re-solve

• time windows tend to be pretty large

• isn't always a notion of an optimal schedule

• side constraints can be pretty easy to represent

  • work rules aren't always easy

  • drivers may have odd drive/sleep patterns

  • side resource use is tolerable

Robustness for many things has to be dealt with, but how that's done is very differennt

And remember how important interface is – they're both important, and very, very different

And even more important is understanding what's going on within the problem domain

good large software is built on top of amazing small software

GAC – Generalized Arc Consistency, for non-binary CSPs

• Operates on table constraints, by supports or by no-goods

• $\pi_A(R)$ gives a new relation with only values of A

  • May be a Set, or a Bag

finite csps are linear in space, quadratic time when dealing with all-diff constrants

Sometimes, all diff may become many constraints that together are equivalent, but not always

GAC4 handles n-ary constraints

• has good pruning power

• but is very expensive – $\frac{d!}{(d-p)!}$

value is consistent if other values exist for all other values such that the values and the give simulatenously satisfy the problem

a constraint is consistent if all values for all variables arec oconsistent

csp is arc-consistent if all constraints are consistent

csp is diff-arc-consistent iff all all-diff constraints are arc-consistent

value graphs are bipartite

• vertices are $X_C$, $\cup_{x \in X_C}(D_x)$

• edges $(x_i, a)$ iff $a \in D_x$

Space is $\mathcal{O}(nd)$

Matching a subset of edges in G with no vertex in common

max matching is the bigges possible

matching covers a set $X$ – every vertex in $X$ is an endpoint for an edge in matching

$M$ that covers $X_C$ is a max matching.

If every edge in $GV(C)$ is in a matching that covers $X_C$, $C$ is consistent.

CSP is diff-arc-consistent iff, for every all-diff $C \in \mathcal{C}$, for every edge $GV(C)$ belongs to a matching that covers $X_C$ in $GV(C)$

Build graph, compute max matching, if size of max matching is smaller than $X_C$, return false, otherwise remove edges from G given the max matching and return true

• use Maximal Flow in Bipartite graph

• Or Hopcroft/Karp algo

Then we have an all-dif constraint, value graph and a maximum covering

• remove edges that aren't in a matching covering

given a Matching M

• matching edge is an edge in M

• free edge is an edge not in M

• matched vertex is incident to a matching edge

• free vertex is otherwise

• alternating path (cycle) – a path (cycle) whose edges are alternatively matching and free

  • flip colors on even alternating path – gives another matching of same size

  • flip colors on alternating cycle – another matching

• length of path – number of edges in path

• vital edge belongs to every maximum matching

An edge belongs to some of but not all maximum matching iff for an arbitrary maximum matching $m$ , it belongs to either an even alternating cycle or an even alternating path tha begins at a free vertex

Edges to remove shouldn't be in all matchings, even alternating paths starting at a free vertex and an even alternating cycle.

every directed cycle in $G_0$ corresponds to an even alternating cycle of $G$

every directed simple path starting at a free vertex corresponds to an even alternating path of $G$ starting at a free vertex

make black point one way, red the other

allows for all-diff and other global constraints

connections

• constraint databases and constraint logic programming

• query processing and solving csps

shared

• constrant dbs (deductive BD, Datalog) and constraint logic programming share representation

• relational databases and constraint satisfaction share computations

Constraint databases use LP – Prolog for DB, Datalog

Prolog was a bit of a failed expiriment

CLP(R,F) is prolog with CSP techniques for either reals or finite domains

Relations

• binary relations – given $D_a$ and $D_b$, a set of any 2-tuples $\langle x, y \rangle$ with $x \in D_a$ and $y \in D_b$, this defines a relation $R_{ab}$ $R_{ab} = {(x, y)} \subseteq D_a \times D_b$

• Function – a binary relation such that there is at most one tuple $\langle x, ? \rangle \in R_ab$. $D_a$ is the domain, $D_b$ is the co-domain.

• $k$-ary relations – are relations on $k$ elements

representation

• 2-dimensional binary array, though k-dimension works

• tables

• linked-lists of pairs

• hash-maps of sets

• many other options

Terms

• table, relation – constraint

• arity of relation – arity of variable

• attribute – variable

• value of attribute – value of var

• domain of attribute – domain of variable

• tuple in table – tuple in constraint/allowed by constraint/consistent with constraint

Relational algebra

• intersection

  • input two relations of same scope

  • output a new, more restrictive relation with the same scope made of tuples in all the input relations simultaneously

  • logical and

• union

  • input 2 rel of same socope

  • less restrictive relation with same scope of tuples that are in any input relation

  • logical or

• difference – same as set theory

• selection

• projection

• join

• composition (from CSP)

Selection and projection are unary operators

Selection

• Input – a relation $R$ and a predicate o attributes of $R$

• Output a relation $R^\prime$ with the same scope as $R$ but having only a subset of the tuples in $R$

• Row selection

• $\sigma_{p}(R)$

Projection

• Input – a relation $R$ and a subset $s$ of the scope

• Output – a relation $R^\prime$ of scope $s$ with the tuples rewritten such that positions not in $s$ are removed

• column elimination, in CSP set semantics, in DB bag

• $\pi_{\{x_1, x_2\}}(R)$

Join (natural join)

• Input – $R$ and $R^\prime$

• Output a relation $R^{\prime\prime}$ whose scope is the union of $R$ and $R^\prime$ and tuples satisfy both

  • if they have no common attribute, cartesian product

  • if they have an attribute in common, compute all possibilities

• Computes all solutions to a csp

• $R \bowtie R^\prime$

Composition of two relations

• Input – two binary relations $R_{ab}$ and $R_{bc}$ with 1 var in common

• Output – a new induced relation $R_{ac}$ to be combined by intersection to a pre-existsing relation between them

• bit matrix op is matrix multiplication

• Generalization as constraint synthesis

• Produces induced relations a/k/a indirect, inferred, implicit

Given $V_1$ and $V_2$ and $C_1$ and $C_2$ between them, how do $C_1 \cap C_2$ and $C_1 \bowtie C_2$ relate? – They'll be the same in this situation

Given $V_1$, $V_2$, $V_3$, $C_{V_1, V_2}$ and $C_{V_2, V_3}$, write the induced $C_{V_1, V_3}$ in relational algebra. – $C_{V_1, V_3} = \pi_{V1, V3}(C_{V_1, V_2} \bowtie C_{V_2, V_3}) = C_{V_1, V_2} \circ C_{V_2, V_3}$

Given $V_1, V_2, V_3$, $C_{V_1, V_2}, C_{V_2, V_3}, C_{V_1, V_3}$, $C^{\prime}_{V_1, V_3} = (C_{V_1, V_2} \circ C_{V_2, V_3}) \cap C_{V_1, V_3}$

Natural join – synthesized constraint

left/right join – synth constraint with some inconsistent tuples

Differences

• number of relations

  • db have few

  • csp have many

• size of relations

  • dbs have high-arity

  • csps are mostly binary

• bounds of relations

  • dbs are very tight

  • csps are loose

• size of domains

  • db large

  • csp small

• type of domain

  • almost always finite, but csp may be continuous

• number of solutions sought

  • dbs looking for almost all

  • csp only looks for one in general

• cost-model

  • DB is I/O, memory

  • CSP is computational

consistency helps to reduce possible search-space

A path of length $m$ is consistent iff for any value $x \in D_{V0}$ and for any value $y \in D_{Vm}$ that are consistent, there exists a sequence of values in the domains of the variables $V_1, V_2, \ldots, V_{m - 1}$ such that all constraints between them (along the path, not across) are satisfied

A CSP is path consistent if any path of any length is consistent

However, by Mackworth AIJ77, only paths of length 2 are necessary, $\mathcal{O}(n^3)$

algo looks at every vertex as a mid-point $k$, and makes $i$ and $j$ together consistent given $j$,

• and $R_{ij} \gets R_{ij} \cap (R_{ik} \cdot R_{kj})$

• Closure algorithm. $k$ is outer loop

• Until fixed point

  • for k from 1 to n

    • for i from 1 to n

      • for j from 1 to n

        • $R_{ij} \gets R_{ij}^{O} \cap (R_{ik} \cdot R_{kj})$

• Algo

  • $Y^n \gets R$

  • Until $Y^n = Y^0$

    • For k from 1 to n

      • For i from 1 to n

        • For j from 1 to n

          • See slide for equation

  • $Y \gets Y^n$

Difference between k consistent and strong k consistency

PC1 terminates, is sound and complete for discrete CSPs - $\mathcal{O}(a^5n^5)$

In a complete graph, if every path of length 2 is consistent, the network is path consistent

• PC1 has two operations, composition and intersection

• proof is done by induction

Mohr and Henderson also developed PC-2, 3

and Han, Lee created PC4

PC5 from Singh uses support bookkeeping from AC6

PC8 uses domains, not constraints, 2001 improves on PC8, but isn't tested

PC is rarely used except for certain types of constraints

monotonic constraints – ordering based

completion allows you to use paths of length 2.

Strong PC will ensure both PC and AC

AC first, then if no inconsistency, PC (likely PC2)

Go from weaker first to stronger – making later steps likely cheaper

But PC is often unused – except some situations make it much more likely to find a solution

PC is also called 3 consistency

Local Consistencies

• AC

• GAC

• Path Consistency – modifies binary constraints, requirecs completed graph

• Partial Path Consistency – triangulates graph, modifies binary relations

Global consistency properties

• Consistency in general – it has a solution

• minimality – constraints are as tight as possible, on binary constraints, elimination of a tupple eliminates a solution, every tuple is a member of at least one solution, idealized form of path consistency, garutys consistency, important in interactive product configuration – NP complete in general, Gottlob, 2011

  • determining whether or not a CSP is minimal is NP complete

  • Finding a solution of a minimal CSP is still NP complete

  • occasionally called globally consistent

• decomposability

  • CSP is decomposable if for any combination of assignments to any number of variables that is consistent given the constraints can be extended to a complete solution

  • guaranties back-track free search

  • strongly $n$-consistent

there are some islands of tractability

• tree structure – AC ensures tractability

• convex constraints – path consistency ensures minimality and decomposability

minimality doesn't guaranty bt-free search

decomposability ensures no back tracking

PC approximates minimality

when constraints are convex, PPC on triangulated graph guarantees minimality and decomposability

when $\circ$ distributes over $\cap$, then PC1 guarantees that a CSP is minimal and decomposable, and that the outer loop can be removed

but this doesn't always hold

constraints of bounded difference ad temporal reasoning

• vars,

• constraints of the form $a \leq Y -X \leq B$, $Y - X = [a, b] = I$

• composition and intersection from slides

Remember, once decomposability is enforced, search is guaranteed backtrack free

When constraints are convex, use of PPC ensures minimality and decomposability, but triangles must be done in PEO

When composition distributes over intersection

• PC1 generalizes Floyd-Warshall (all-pairs shortest path)

• PC-1 generalizes Warshall (transitive closure)

Don't confuse properties with algorithms

Local consistency

• remove inconsistent values (node, arc)

• remove tuples (path consistency)

• get closer to solution

• reduce size of problem

• are cheap

Aim for global consistency, but it's hard

Sometimes (given certain types of constraints or graphs), local consistency guarantees lobal consistency

• distributivity in PC, row-convex constraints, special networks

Systematic/constructive search is all we've talked about

Starts at a solution that's not correct, try to repair

General method:

• for each variable, choose a value

• check if solution

  • You're done. Lucky.

  • pick a value that broke a constraint and change it (using min-conflict)

Local search is in worst case, $\mathcal{O}(d^n)$

States laid on a surface

quality/cost is height

optimum state maximizes solution quality while minimising cost

move around from state to state to find a local optimum

Gradient descent – will only ever find a local optimum

State is a complete assignment of values to variables

how do you move – CSP uses min-conflict

eval function rates the quality of a state, generally in number of broken constraints

Try

• Start w/ full but arbitrary assignment of aues

• reduce inconsistencies by local repairs

• repeat until

  • A solution is found (a global minimum)

  • The current solution cannot be repaired (local minimum)

  • You've gone through max tries (running out of patience)

Local repair for decision, local optimzation for optimization

Greedy types are hill climbing, local beam

Local beam

• start in parallel with a number of different points

• choose among those another number of best moves

• remove those without promise

• and repeat as necessary

Stochastic methods

• break out, helps to avoid getting stuck in a local minimum

• when stuck in a local minimum, walk randomly, pick a random variable, change to a random value

• tabu search

  • keep a list of tabu positions (those that aren't good), but only a certain number

  • when a new state is visited, added to tabu, and farthest back forgotten

  • if no better, go to the next state not tabu

  • repeat until a global minimum is found

• sometimes you may randomly ignore a heuristic

Local search problems

• get stuck in a local optimum

• start having can have issues with plateaus (flat local maxima) (be ready to move to a state with the same quality)

• ridges can go from side to side with minimal progress

when stuck, do random walk

Simulated annealing

• When stuck in a local minimum, allow steps towards less good neighbors to escape the ocal maximum

• be more random at the start, be less random as you go

• Start at a random state, start countdown and loop until over

  • pick a neighbor at random

  • $d$ = quality of neighbor - quality of current state

  • if $d > 0$

    • then move to neighbor and restart

    • otherwise, move to a neighbor with a transition probability $p<1$

• Transition probability proportional to $e^{\frac{d}{t}}$

  • $d$ is negative

  • $t$ is countdown

  • As time passes, you're less and less likely to move towards bad neighbors

But all forms of local search are:

• non-exhaustive

• non-systematic

• liable to get stuck in a local optimum

• non-deterministic – outcome depends on where you start

• heavy-tailed – longer you go, less likely you are to find a solution

Is often somewhat probabalistic

starts from a complete assignment, and moves to a new assignment that's better

Very greedy approach, but can be parameterized very easily

Tends to be very greedy, but only allows improvements

others can be better, and allow forr random walks/steps – stochastic algorithms

stochastic algorithms are not deterministic!

Tabu search moves to a state that may be worse, provided it's not in a list of previous states

break-out modifies weight of objective function

simulated annealing involves countdowns and loops, controled by quality of neighbor and the time, but when significantly restricted,, it is guaranteed to find an optimum

Have issues

• non-systematic and non-exhaustive

• have issues getting stuck in local optima

• non-deterministic!!

• generally the probability of improving a solution gets smaller, but never actually dies out – heavy-tailed

So, when you hit a point where it seems improvability drops

• keep the most promising solution

• and start someplace else

• Random restart

Luby restart profile

• uses a crazy geometric law to decide how/when/where to restart

CSPs represented by networks

• for bCSPs, graph

  • constraint graph

  • microstructure

  • co-microstructure

• for general CSPs

  • hypergraph

  • dual – allowed tuples connected to each other when shared variables match

  • primal graph – vertices in graph are original variables, are variables in a constraint are a clique

Incidence graph – Variables are one type of node, constraints another, edges connect variables to the constraints, is bipartite

domain minimality – constraints over arity 1, Gottlob 2011

however, even if domain minimality and constraint minimality hold, solving is still NP complete

global inverse consistency – where given a value at 1 var, you can extend it to $n - 1$ assignments

bounded number of backtrack search

bounded backtrack depth search

limited discrepency search

credit-based backtrack search

randomized backtrack search