# Math Help - Integer programming: converting to binary

1. ## 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.

2. Hello pakman
Originally Posted by pakman
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.

3. The issue wasn't solving the LP, it was converting it to binary, which is what the problem asked to do.

4. Originally Posted by pakman
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.