Results 1 to 3 of 3

Math Help - Linear Programming Question

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    1

    Linear Programming Question

    Hi Guys,

    I have a quick question regarding constraints in integer linear programming. I've never seen a constraint look something like this but I need it to complete my model.

    (X1 + X2) / 9 > 0 and integer

    Essentially meaning x1 + x2 modulo 9 needs to be 0. Would this be acceptable in linear programming because I have yet to see a constraint that divides numbers on the left side.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    Hmm. I don't know much about linear programming (I've been waiting for someone else to chime in.) However, it does seem to me that one of the first principles of it is that you are generally dealing with a convex feasible region. The modular arithmetic constraint you have there does not describe a convex region at all. Ergo, I would say you are no longer in the linear programming regime. But that's my highly inexpert opinion.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    Another way of writing the constraint, that is entirely equivalent, is that x1 + x2 = 9k (or k9, if you prefer dogs), for k in the positive integers. This is going to be a series of disconnected lines, of slope -1, in the x1-x2 plane. I don't mean the lines are continuous; I really mean that you have a series of dots that are on these lines. So that set is not only not convex, it's not connected in any way, shape, or form.

    Are there any constraints on x1 and x2? Because, the way you've written it, there are actually infinitely many points on each line. If, say, x1 and x2 must be positive, then there are finitely many points on each line. However, because there are infinitely many lines, you still have infinitely (countably) many solutions to the constraint. That would take a computer a long time to check.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. linear programming question
    Posted in the Business Math Forum
    Replies: 8
    Last Post: August 9th 2010, 05:40 AM
  2. Linear Programming question
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: February 1st 2010, 02:35 PM
  3. Linear Programming question
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 18th 2009, 06:17 AM
  4. Replies: 1
    Last Post: November 17th 2008, 04:18 AM
  5. Linear Programming Question
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 24th 2008, 06:04 PM

Search Tags


/mathhelpforum @mathhelpforum