Solution to a system of difference constraints
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Solution to a system of difference constraints

  1. #1
    Join Date
    Oct 2011
    Posts
    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 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

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Solution to a system of difference constraints

    Quote Originally Posted by WBuffet View Post
    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.
    Last edited by nuzzle; October 28th, 2011 at 07:06 PM.

  3. #3
    Join Date
    Oct 2011
    Posts
    1

    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.

  4. #4
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,006

    Re: Solution to a system of difference constraints

    Quote Originally Posted by JaAnoOn View Post
    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.

  5. #5
    Join Date
    May 2009
    Posts
    2,413

    Re: Solution to a system of difference constraints

    Quote Originally Posted by BioPhysEngr View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center