
October 23rd, 2011, 01:51 PM
#1
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 BellmanFord 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

October 24th, 2011, 12:23 PM
#2
Re: Solution to a system of difference constraints
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
xy < z*M
yx < (1z)*M
where M is the maximum int.
When z=0 you have
xy < 0
yx < M
The first constraint ensures that x < y (they're not equal). The second constraint is not contraining.
When z=1 you have
xy < M
yx < 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.
Last edited by nuzzle; October 28th, 2011 at 07:06 PM.

October 24th, 2011, 04:28 PM
#3
Re: Solution to a system of difference constraints
Please DO NOT help WBuffet with this problem. This is a task from an active programming contest.

October 28th, 2011, 12:46 AM
#4
Re: Solution to a system of difference constraints
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.
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

October 28th, 2011, 06:35 PM
#5
Re: Solution to a system of difference constraints
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.
Last edited by nuzzle; October 28th, 2011 at 10:18 PM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
