Results 1 to 4 of 4

Math Help - Integer programming: converting to binary

  1. #1
    Member
    Joined
    Jun 2006
    Posts
    93

    Integer programming: converting to binary

    Maximize 2X1 + 5X2
    subject to X1 + X2 <= 15
    -X1 + X2 <= 2
    X1 - X2 >= 2
    X1 + X2 >= 2
    X1, X2 >= 0 and integer

    I am supposed to convert the model to binary. I'm thinking of using a Xij format, though I am not really sure how to constrain it. Any ideas? Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello pakman
    Quote Originally Posted by pakman View Post
    Maximize 2X1 + 5X2 (1)
    subject to X1 + X2 <= 15 (2)
    -X1 + X2 <= 2 (3)
    X1 - X2 >= 2 (4)
    X1 + X2 >= 2 (5)
    X1, X2 >= 0 and integer (6)

    I am supposed to convert the model to binary. I'm thinking of using a Xij format, though I am not really sure how to constrain it. Any ideas? Thank you.
    This would appear to be a fairly straightforward exercise in Linear Programming. Using the numbering above:

    (3) becomes X1 - X2 >= -2 which is redundant since (4) is a stronger condition.

    (6) and (4) imply X1 >= 2 which renders (5) redundant also.

    So we are left with (2), (4) and (6). Plotting these on a graph, and considering the gradient of the line 2X1 + 5X2 = k, gives the maximum value 48 at (9,6).

    I don't understand the need for binary.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2006
    Posts
    93
    The issue wasn't solving the LP, it was converting it to binary, which is what the problem asked to do.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by pakman View Post
    Maximize 2X1 + 5X2
    subject to X1 + X2 <= 15
    -X1 + X2 <= 2
    X1 - X2 >= 2
    X1 + X2 >= 2
    X1, X2 >= 0 and integer

    I am supposed to convert the model to binary. I'm thinking of using a Xij format, though I am not really sure how to constrain it. Any ideas? Thank you.
    Since X_1 + X_2 \leq 15 and X_i \geq 0 and integer, we know  0 \leq X_i \leq 15. So we can write

    X_1 = a + 2 b + 4c + 8d
    X_2 = e + 2f + 4g + 8h

    where a, b, ..., h are binary variables (0 or 1). Making these substitutions for X_1 and X_2 in the original problem converts it to a problem in which all the variables are either 0 or 1, i.e. a binary problem.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary Integer Programming Problem
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: August 14th 2011, 04:57 PM
  2. Binary Integer Proof?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 05:22 AM
  3. Replies: 0
    Last Post: September 26th 2010, 04:33 PM
  4. Binary quadratic programming
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: August 7th 2009, 10:47 AM
  5. Binary Quadratic Programming
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: November 14th 2007, 09:36 PM

Search Tags


/mathhelpforum @mathhelpforum