for subsets of variables. We use capital letters for variables (e.g. X, Y and S), and lower case for values (e.g. d and di). A solution is an assignment of values to the variables satisfying the constraints. Constraint solvers typically explore partial assignments enforcing a local consistency property using either specialized or general purpose propagation algorithms. A *support* for a constraint C is a tuple that assigns a value to each variable from its domain which satisfies C. A *bounds support* is a tuple that assigns a value to each variable which is between the maximum and minimum in its domain which satisfies C. A constraint is domain consistent (DC) iff for each variable Xi, every value in the domain of Xi belongs to a support. A constraint is *bounds consistent* (BC) iff for each variable Xi, there is a bounds support for the maximum and minimum value in its domain. A CSP is *DC/BC* iff each constraint is *DC/BC*. A constraint is *monotone* iff there exists a total ordering ≺ of the domain values such that for any two values v, w if v ≺ w then v is substitutable for w in any support for C.

We also give some background on flows. A *flow network* is a weighted directed graph G = (**V, E**) where each edge e has a capacity between non-negative integers l(e) and u(e), and an integer cost w(e). A *feasible flow* in a flow network between a source
(s) and a sink (t), (**s, t**)-flow, is a function f : E → Z
+ that satisfies two conditions:
f(e) ∈ [l(e), u(e)], ∀e ∈ E and the *flow conservation* law that ensures that the amount of incoming flow should be equal to the amount of outgoing flow for all nodes except the source and the sink. The *value* of a (**s, t**)-flow is the amount of flow leaving the sink s. The *cost* of a flow f is w(f) = Pe∈E w(e)f(e). A *minimum cost flow* is a feasible flow with the minimum cost. The Ford-Fulkerson algorithm can find a feasible flow in O(φ(f)|E|) time. If w(e) ∈ Z, ∀e ∈ E, then a minimum cost feasible flow can be found using the successive shortest path algorithm in O(φ(f)**SP P**) time, where **SP P** is the complexity of finding a shortest path in the residual graph. Given a (**s, t**)-flow f in G(**V, E**), the *residual graph* Gf is the directed graph (**V, E**f ), where Ef is

$\{e$ with cost $w(e)$ and capacity $0..(u(e)-f(e))\mid e=(u,v)\in E,f(e)<u(e)\}\bigcup$
$\{e$ with cost $\ -\ w(e)$ and capacity $0..(f(e)-l(e))\mid e=(u,v)\in E,l(e)<f(e)\}$. 
There are other asymptotically faster but more complex algorithms for finding either feasible or minimum-cost flows [3].

In our flow-based encodings, a consistency check will correspond to finding a feasible or minimum cost flow. To enforce DC, we therefore need an algorithm that, given a minimum cost flow of cost w(f) and an edge e checks if an extra unit flow can be pushed (or removed) through the edge e and the cost of the resulting flow is less than or equal to a given threshold T . We use the residual graph to construct such an algorithm. Suppose we need to check if an extra unit flow can be pushed through an edge e = (**u, v**). Let e
′ = (**u, v**) be the corresponding arc in the residual graph. If w(e**) = 0**,
∀e ∈ E, then it is sufficient to compute strongly connected components (SCC) in the residual graph. An extra unit flow can be pushed through an edge e iff both ends of the edge e
′are in the same strongly connected component. If w(e) ∈ Z, ∀e ∈ E, the shortest path p between v and u in the residual graph has to be computed. The minimal cost of pushing an extra unit flow through an edge e equals w(f) + w(p) + w(e). If w(f) + w(p) + w(e) > T , then we cannot push an extra unit through e. Similarly, we can check if we can remove a unit flow through an edge.