# graphs – Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time

I have a system that consists of binary equality and inequality constraints:

``````a < b
b < c
x < y
y = z
``````

and I would like to answer questions about the system, such as “is `a` greater than `c`?” and “is `b` greater than `x`?”.
One approach would be to formulate this as an integer linear program: in the example above, the variables would have domains (0, 5) and a feasible solution might be:

``````a = 0
b = 1
c = 2
x = 0
y = 1
z = 1
``````

I could then answer “is `a` greater than `c`?” by comparing the integer values assigned to `a` and `c`.
However, I could get the wrong answer for “is `b` greater than `x`?”: the solution above suggests yes, but there exists another feasible solution

``````a = 0
b = 1
c = 2
x = 1
y = 2
z = 2
``````

in which the answer appears to be no. (The correct answer is that we cannot determine the relationship between `b` and `x`.)

Now, I could generate ALL the feasible solutions, iterate over them, and check whether `b > x` in each one — but I have to answer enough of these questions that this approach would be too slow.

Is there a more efficient and elegant way? Perhaps constraint programming is not even the right way to think about this — I considered formulating it as a directed graph-search problem instead, where directed edges represent inequality relationships, but my actual system contains conditional constraints as well. The wonderful answer that I received on a related question (https://scicomp.stackexchange.com/questions/36090/constraint-programming-problem-with-conditional-constraints-and-some-unknown-ind) directed me here. Glad for any suggestions or references to relevant papers or textbooks!

Posted on Categories Articles