Solution to a system of difference constraints

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

Quote:

---

Originally Posted by WBuffet

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.

---

Then this requirement must be included in the objective function I guess. Unless of course "maximizing the number of distinct variables" means you stipulate no two variables may be equal. In that case you can do it by constraints.

To rule out that two variables x and y become equal you need to introduce one 0/1 variable z and two constraints of the form

x-y < z*M
y-x < (1-z)*M

where M is the maximum int.

When z=0 you have

x-y < 0
y-x < M

The first constraint ensures that x < y (they're not equal). The second constraint is not contraining.

When z=1 you have

x-y < M
y-x < 0

The second constraint now ensures that y < x (they're not equal). The first constraint is not constraining.

So regardless of whether z is 0 or 1, x and y can take on any value except x=y.

The above is fine when there are just two variables x and y but when there are more variables all variables must be constrained pairwise. So the number of constraints increases quadratically which becomes expensive when there are many variables.

Please DO NOT help WBuffet with this problem. This is a task from an active programming contest.

Quote:

---

Originally Posted by JaAnoOn

Please DO NOT help WBuffet with this problem. This is a task from an active programming contest.

---

What of it? That is an issue for the contest organizers to deal with, not the entire internet.

Quote:

---

Originally Posted by BioPhysEngr

What of it? That is an issue for the contest organizers to deal with, not the entire internet.

---

Be careful! I got banned from a forum partly for pursuing your point. :)

The consensus view at most forums is that you don't help "cheaters". I argue it's not up to forums to decide who's a cheater. One really cannot know.

I have a feeling this obsession with cheating stems from the practice among many universities, especially American, to allow unsupervised work to count towards grades. You can easily let others land you an A. But this cannot be solved here, it must be solved by the universities themselves.

At some forums cheater hunting even has become institutionalized. Tracking down cheaters is a main moderator task. Just visit the Oracle Java forums and watch for yourself.

I don't want that development here so I'm glad you reacted.