Constraint programming problem with conditional constraints and some unknown indicator variables
I have an interesting little problem that I believe can be formulated in terms of optimization or constraint programming. I have a few dozen variables $a$, $b$, $c$ ... and a set of constraints that establish relations between them, such as $a < b$. Some of these constraints are "turned on" by binary indicator variables: $b < c\:|\:(ind_x = True)$. We know the value of some of these binary variables, but not all of them. The goal here is to solve the system such that we can quickly answer questions about the relations between pairs of non-binary variables ("What is the relation between $a$ and $c$?"). 946
Answers could be:
* $a < c$
* $a = c$
* $ a > c$
* the relationship between $a$ and $c$ cannot be determined with the information available.
My first instinct was to formulate this as a constraint satisfaction problem. I defined the domain of each non-binary variable to be the set of positive nonzero integers, encoded conditional constraints as $b * ind_x < c$ (always true if the indicator is 0, and if the indicator is 1, only true if $b<c$), and provided unconditional constraints ($ a<b$) as-is. Then I would take one of the feasible solutions, for example:
PROBLEM:
a < b
b < c
a < d
SOLUTION:
a = 0
b = 1
c = 2
d = 1
This works great for answering some questions -- for example, if we ask for the relation between $a$ and $c$, we can conclude from $a=0$ and $c=1$ that $a < c$.
But if we ask for the relationship between $b$ and $d$, the fact that $b = d = 1$ is misleading, because the following is also a viable solution:
a = 0
b = 1
c = 2
d = 99
In fact, the relationship between $b$ and $d$ is impossible to determine given the available information. We could iterate over all the feasible solutions of this CSP, and check the relationship between $b$ and $d$ in each one, but this is too slow. We could also try adding constraint $b < d$ and solving for feasibility, then doing the same for $b > d$, etc., but this seems cumbersome as well.
Is there a more elegant way to formulate this problem that I am not aware of? Any ideas or suggestions would be much appreciated. Thank you! 603