UP | HOME

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