I've ran into an interesting problem. Given a set of constraints (in integers) of the two following forms :

a)
a1 = a2 + 1
a4 = a1 + 1

In which one variable is greater than another one by precisely one.

b)
a3 >= a4
a2 >= a4

In which one variable is greater or equal to another one.

I need to find a solution to the above set of constraints, but with a twist - we need to maximize the number of distinct variable values.

Finding one solution is trivial, as:

a1 = a2 + 1 <=> a1 - a2 <= 1 && a2 - a1 <= -1, which is a difference constraint, and the other type converts by simple substraction:

a4 - a3 <= 0

Then I can simply convert it to a constraint graph, run the Bellman-Ford algorithm from a source vertex, and get a solution.

The solution, however, doesn't guarantee that the number of distinct variable values is maximized.

If anybody has any idea on how to find that solution, I'll be greatly grateful.

Regards,
Warren