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 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. 603
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? 946