I have a system that consists of binary inequality constraints between variables, plus some indicator variables that can assume only two values:
a, b, c, d ⊆ ℝ
i ⊆ {true, false}
// unconditional inequality constraints
a < b
// conditional inequality constraints
i -> b < c
i -> b < d
!i -> b > c
!i -> a < d
and I would like to answer questions about the system, such as "is a greater than d?" and "is c less than d?".
One approach would be to formulate this as an integer linear program: in the example above, the non-indicator variables would have domains [0, 3], the indicator variables [0, 1] and a feasible solution might be:
i = 0 (false)
a = 0
b = 1
c = 0
d = 2
I could then answer "is a greater than d?" by comparing the integer values assigned to a and d. However, I could get the wrong answer for "is c less than d?": the solution above suggests yes, but there exists another feasible solution
i = 0 (false)
a = 0
b = 3
c = 2
d = 1
in which the answer appears to be no. (The correct answer is that we cannot determine the relationship between c and d.)
Now, I could generate ALL the feasible solutions, iterate over them, and check whether c < d
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!
Edit: After asking this question to several people (both here and elsewhere), I have received multiple suggestions to reduce these constraints to a comparability graph. To illustrate the challenges of this approach, I have added conditional constraints to my example system above. Is there a way to incorporate such constraints into a comparability graph?