The basic algorithm for adding a constraint is:
- Build a “vine” to enforce the constraint by doing a DeltaBlue-like local decision search. This vine both (a) enforces the added constraint and (b) only overrides weaker constraints.
- Building the vine may have overridden satisfiable constraints, so then build vines for all the overridden constraints.
- This process may repeatedly “flip” some constraints, but will always terminate.

QuickPlan

A SkyBlue-like algorithm which uses Degrees of Freedom rather than Known Values [Vander Zanden 95].

The incremental version of QuickPlan is faster than SkyBlue, but slower than DeltaBlue.

QuickPlan correctly handles both cycles and multiple-output constraints.

QuickPlan: Overview

The basic algorithm for adding a constraint is:
- Add the constraint to the constraint graph.
- Using degrees of freedom, find a propagation solution to the graph.
- If unsolvable sub-graphs remain, remove the weakest constraint from the graph and retry the degrees of freedom. Continue until all constraints are either enforced by the propagation solution or removed from the graph.
- Removing constraints may have removed an enforcable constraint so, starting with the strongest removed constraint, add the unenforced constraints back again using steps 2 and 3. While doing so, remove only constraints weaker than the constraint being added
- Any remaining unsolvable sub-graphs are cycles and must be solved with a cycle solver.

Hierarchical Local Propagation Constraints Scorecard

Computation model is complicated; debugging has not been completely solved.

Algorithms are moderately difficult to implement.

Algorithms are reasonably fast.

Handle conflicts, over- and under-constrained.

Does not handle cycles.

Hierarchical Local Propagation Constraint Systems

Using DeltaBlue:
- Delta TRIP [Satoshi et al.]
- Rotterdam (anaesthesia)
- Chronology Corporation.
- researchers at Hewlett-Packard Labs, Apple Computer, Data I/O, GMD (the German Computer Science Research Lab), DEC Paris Research Labs, and the Helsinki Institute of Technology

Using Skyblue:
- TBAG [Elliott 1994]
- Pika [Amador 1993] (self-explanatory simulation system)
- VB2 [Gobbetti 1993] (VR system)

Workpage #1a

Use the Hudson Algorithm (slides 16-19) to solve these constraints:
- the original constraints are:
- demand A
- change C to 32
- demand D
- change F to 52
- demand A

Workpage #1b

Use the Degrees of Freedom algorithm (slide 27) to find a propagation solution for these constraints:

Workpage #1c

The following constraint hierarchy specifies when three co-workers are available for a meeting. Use the locally-predicate-better and the least-squares-better comparators to determine when they could have a one hour meeting: (see slides 36-46)

Workpage #1d

Use DeltaBlue (slides 50-57) to make the following changes to this local propagation solution:
- add strong B = 12
- add strong C = 32
- add required A = 52
- remove strong B = 12
- remove medium B = cj

Section III: Non-Local Propagation Constraints

Cycle Example #1

are we?

we sell?

training?

Cycle Example #2

Simultaneous Linear Equation Algorithms

Gaussian elimination

Gaussian elimination augmented for over- and under-constrained systems and constraint hierarchies
- semi-symbolic
- adapted from linear equation solver used in the CLP(R) system

Semi-Symbolic Linear Equation Solver

For constraints that are linear equations.

Constraints are in one of the following sets:
- enforced
- unsatisfied
- not yet processed
- initially all constraints are in the not yet processed set

Variables are in one of the following sets:
- parametric (can take on any value)
- non-parametric (defined as a linear combination of parametric variables)
- known (have a known floating point value)
- initially all variables are in the parametric variables set

Semi-Symbolic Linear Equation Solver

Process constraints strongest to weakest. To process a constraint:
- Convert the constraint into linear normal form
- Replace known variables by their values, and nonparametric variables by their defining expressions. Simplify. The result will be a linear expression in the parametric variables.
- If the resulting equation is 0=0 the constraint is redundant with the already satisfied constraints
- If the resulting equation is 0=c for some c???0 then the constraint is unsatisfiable

Semi-Symbolic Linear Equation Solver

Otherwise the constraint adds new information.
- Solve it for one of its parametric variables, and move this variable to known variables or nonparametric variables. Replace this variable in other expressions for non-parametric variables with its value or expression.
- After all constraints have been processed, all the variables will be in known variables and parametric variables and nonparametric variables will be empty. (Note that this property follows from the presence of the very weak stays on every variable -- so that every variable will get a value in the end.)

Linear Equation Solver Example

The constraints:
- required 1.8*c = f - 32.0
- strong c = f
- very weak c = 15.0
- very weak f = 98.6

Initially all constraints are in the not yet processed set and the variables (c and f) are in the parametric variables set.

Linear Equation Solver Example

Process the strongest constraint:
- put it in normal form, and solve for one of the variables, say f:f = 1.8*c + 32.0
- move f to nonparametric variables

Process the next constraint.
- Replace nonparametric variables by their defining expressions, resulting in c = 1.8*c + 32.0
- Simplify: 0.8*c +32.0 = 0.0
- Solve for c: c = -40.0
- Move c to known variables. Substitute the new value for c in all expressions for nonparametric variables and simplify: f = -40.0

Linear Equation Solver Example

Process c=15.0 After replacing c with its value this equation becomes -40.0=15.0, which is unsatisfiable.

Process f=98.6 After replacing f with its value this equation becomes -40.0=98.6, which is unsatisfiable.

All constraints have been processed, and all variables now have known values.

Simultaneous Linear Equation Scorecard

Computation model is similar to, but slightly easier than, non-cyclic hierarchies

Algorithms are relatively straight-forward.

Performance is reasonable.

Handles cycles and, with hierarchies, conflicts, over- and under-constrained problems.

Only handles numeric constraints.

Needs to be integrated with other solvers.

Simultaneous Linear Equation Systems

CLP(?) and other Constraint Logic Programming systems

DETAIL

BERTRAND

Inequalities Example #1

are we?

we sell?

Inequalities Example #2

Inequality Algorithms

Local Propagation: Interval-based

Simultaneous: Interval or Simplex-based

Simultaneous: other linear programming algorithms (Karmarkar’s algorithm, etc.)

Local Propagation for Inequalities (1)

Current algorithm is batch

Constrained variables hold an interval (lower and upper bounds), as well as a value

Initially all variables have:
- lower bound = -?
- upper bound = ?
- value unknown

Local Propagation for Inequalities (2)

Process constraints strongest to weakest

Check whether the constraint can be satisfied given the current bounds and values for the variables it constrains. If it can be, enforce it. If it can’t be, discard it. (If it’s a required constraint, signal an error.)

Local Propagation for Inequalities (3)

When a constraint is enforced, tighten bounds on its constrained variables and determine values if possible.

This may allow other bounds to be tightened or values to be determined, rippling out to other parts of the contraint graph.

At the end, all variables should have unique values.

Example of Local Propagation for Inequalities (1)

Constraints:
- required 2*a + b = c
- required 0 ? a ? 5
- required 0 ? c ? 10
- strong b = 25
- weak b = 5
- weak c = 5

Example of Local Propagation for Inequalities (2)

process 2*a+b=c
- this constraint is satisfiable, but produces no restrictions on the bounds on a, b, or c

process 0 ? a ??5
- the bounds on a are now 0 ??a ??5

process 0 ??c ??10
- the bounds on c are now 0 ??c ??10
- we also tighten the bounds on b to -10 ??b ??10

Example of Local Propagation for Inequalities (3)

process b=25
- this constraint cannot be satisfied since 25 is outside of b’s bounds

process b=5
- this constraint can be satisfied: set b=5
- we also tighten the bounds on a to 0 ??a ??2.5
- and we tighten the bounds on c to 5 ??c ??10

process c=5
- this constraint can be satisfied: set c=5 and a=0

Bounded Linear Constraint Solver

Derived from semi-symbolic linear equation solver -- solves hierarchies of linear equality and inequality constraints

Process equations as before, but also keep track of bounds

Sound but not complete. (In other words, if it produces an answer the answer will be correct, but there are some problems it can’t solve.)

Based on the Simplex algorithm.

Simplex Algorithm Review

Well-understood; extensively used in operations research

Variables restricted to be non-negative

Maximizes or minimizes a linear expression subject to a collection of linear equality and inequality constraints

Simplex-Based Solver (1)

[currently only a design - not implemented]

Like bounded linear constraint solver, solves hierarchies of linear equality and inequality constraints

Derived from CLP(R) linear inequality solver

Unlike bounded linear constraint solver, both sound and complete

Simplex-Based Solver (2)

Solver maintains a tableau of variables involved in inequality constraints, and separately an equality tableau (like that for semi-symbolic linear equation solver)

Inequality tableau includes slack variables (which are not visible outside solver). For example, x ??y is converted to x-y+s=0.

Equality and inequality tableaux maintained in solved form

Constraints processed strongest to weakest. If a constraint can be satisfied given the current tableaux, it is entered into the tableax; otherwise it is discarded.

Differences between Simplex-Based Solver and Standard Simplex Algorithm

Variables are unrestricted in sign

Handles constraint hierarchies

Only uses Phase 1 of the traditional Two-Phase Simplex algorithm (no optimization phase)

Separate equality and inequality tableau optimizes for the fact that equality constraints are more common

Inequality Scorecard

Computation model is similar to hierarchies

Algorithms are difficult to implement.

Performance is rather slow.

Handles cycles and, with hierarchies, conflicts, over- and under-constrained problems.

Only handles numeric constraints.

Inequality Constraint Systems

CLP(?), BNR Prolog, and other Constraint Logic Programming systems

GUI Builders (but just assertion checked)

Non-Linear Numeric Constraints Example #1

Non-Linear Numeric Constraint Algorithms

Iterative
- Newton-Raphson
- Levenberg-Marquadt iteration [Press 89]
- Gleicher differential constraints

Symbolic
- Mathematica
- Maple

Non-Linear Numeric Constraints Scorecard

Computation model is similar to hierarchies

Algorithms range from moderately difficult to truely obscure.

Performance is very slow.

Handles cycles and, with hierarchies, conflicts, over- and under-constrained problems.

Only handles numeric constraints.

Can miss the solution.

Workpage #2

Which of the follow sets of constraints involve cycles?
- required 2*x + y = 7required x + y = 5
- required 2*x + y = 7required y = 5
- A circuit consisting of just a battery and a resistor. Battery's voltage and the resistance are given.
- A circuit consisting of a battery and two resistors in series. Battery's voltage and the resistances are given.
- A window layout problem. A window has two panes p1 and p2 laid out side by side. p1 is constrained to be twice as wide as p2, and the entire window width must be equal to a given number.

Workpage #2b

Solve the following hierarchy using bounded local propagation (slides 83-88):

Section IV: Other Constraints

Constraints Over Finite Domains Example #1

Constraints Over Finite Domains - Algorithms

Naive algorithm: pure generate-and-test

Generate each possible mapping of variables to values, and see if it is consistent with the constraints. Very inefficient!

Constraints Over Finite Domains - Algorithms (2)

Node-arc-path consistency algorithms from AI (CSP algorithms)

Use pruning for more efficiency:
- node consistency (for unary constraints)
- arc consistency (consistency between pairs of nodes)
- path consistency (consistency among k nodes)

CSP algorithms with hierarchies

PCSPs [Freuder 92]

Constraints Over Finite Domains Scorecard

Computation model is similar well analyzed and understood.

Algorithms are moderately difficult to implement.

Performance is quite fast.

Handles cycles and, with hierarchies or PCSP, conflicts, over- and under-constrained problems.

Only for finite domains; has limited applicability

Uses for Constraints Over Finite Domains

Planning and Scheduling

Device configuration

Perceptual labelling problems (e.g., scene labelling)

Qualitative physics

Fault diagnosis

Dynamically Changeable Constraint Sets Example #1

Dynamically Changeable Constraint Sets Example #2

are we?

we sell?

Dynamically Changeable Constraint Sets Algorithms

The only algorithm so far is a backtracking search.
- Prolog-like (depth-first), or
- breadth-first, or
- intelligent backtracking, or
- ... etc ...

Dynamically Changeable Constraint Sets Scorecard

Computation model is based on logic programming.

Algorithms are moderately difficult to implement.

Performance depends on the underlying class of constraints, but can be slow due to massive backtracking.

Handles cycles, conflicts, over- and under-constrained problems.

Higher-level constraints vs. meta-constraints.

Systems Supporting Dynamically Changeable Constraint Sets

CLP(?) and other Constraint Logic Programming systems

Kaleidoscope

Section V: Constraints In Use

Integration via ENVY/Constraints

Single algorithm is not sufficient
- The usual engineering trade-off of generality vs. efficiency applies.

ENVY/Constraints uses pluggable solvers:
- partition into disjoint
- partition into local propagation regions and cycle regions
- DeltaBlue
- cycle solvers (e.g., Gaussian elimination)

ENVY/Constraints

Framework and completions for building constraints

ClConstrainableVariable
- pre- and post- change callbacks in both immediate and delayed versions
- value and value: messages

ClConstraint
- standard constraints available as subclasses, e.g., equal, stay, linear equation, etc.
- specialized constraints can be built using blocks, methods, or objects for propagation rules.
- have extra protocol for linear and non-linear constraint solvers.

Building Interactive Graphical Applications (1)

Decide if the problem is suitable for constraints.
- Can you identify relations that should hold between the objects?
- Are these relations used in multiple directions?

Partition the problem.
- Imperative part and constraint part.

Identify the relations
- Permanent vs. Transient relations.
- Intra- vs. Inter-object relations

Building Interactive Graphical Applications (2)

Determine the class of constraints
- Local propagation
- Simultaneous a.k.a. cycles
- Linear vs. non-linear
- etc.

Identify constrainable variables
- Manipulatable attributes
- Visible (or contributing to visible) attributes

Building Interactive Graphical Applications (3)

Specify imperative - declarative interface
- Control flow:
  - Callbacks are declarative ? imperative flow.
  - value: addCn: messages are imperative ??declarative flow.
- Information flow:
  - value message is declarative ? imperative flow.
  - value: addCn: messages are imperative ??declarative flow.

Building Interactive Graphical Applications (4)

Debugging
- Use display widgets and monitors.
- Unexpected solution? Check for under- or over-constrained system. (Check under-constrained first.)

Performance Problems
- Check for excessive callbacks.
- Try lazy vs. eager solving.
- Worst case: create a new sub-solver for specialized domain.

Building Interactive Graphical Applications (5)

Issues to consider:
- Visibility: in a graphical system, constraints may not have a visible artifact; they are only visible by their effects.
- Alternate Solutions: only one solution can be seen at a time although almost all sets of constraints have multiple solutions.
- Perturbation: provides concrete values so that the graphics can be displayed

The Good, The Bad, and The Ugly

Good: ENVY/Constraints is proven for graphical editors

Bad: No constraint system works well for sequences of actions, e.g., popping up a dialog box or copying a file.

Ugly:
- Some problems are more simply done with a consistency mechanism, i.e., if you are using the library anyway, then go ahead, otherwise don’t.
- Other packages, such as the ILOG Solver, are good for scheduling problems (e.g., S.N.C.F. crews); ENVY/Constraints is not designed for such problems.

Workpage #3

Sketch a design for one of the following (using a constraint library):
- Currency converter for at least three currencies
- Dialog box layout
- PERT chart program
- Constraint-based CAD/MacDraw-type program
- Physics simulation tool

Summary

What are constraints?
- Declarative, multi-way assertions and invariants

How are constraints satisfied?

How do declarative constraints interact with imperative code?

What applications are constraints well suited for?
- Directed searching, graphical layout, user interfaces, and simulations

Integration: constraints that can be used when and where declarative relations are appropriate

Compromise: constraint solvers with the correct trade-off between power and speed

Author’s Addresses

Alan Borningborning@cs.washington.eduDepartment of Computer Science and EngineeringUniversity of WashingtonP.O. Box 352350Seattle, WA 98195-2350USA

Bjorn N. Freeman-Bensonbnfb@oti.on.caObject Technology International, Inc.R. Buckminster Fuller Laboratory201 - 506 Fort St.Victoria, BCCANADA V8W 1E6

Internet Instructions

Two Web sites supply information and source code for constraints and constraint solvers:

The newsgroup comp.constraints is another source of information.