converting linear programming problem into integer problem

Question

$Maximise\ x_1 + x_2 + x_3$

s.t \begin{array}x x\in{T\cup{R}},\\0\leqslant x_i \leqslant 10, i = 1,2,3\\where\\T = { x \in{R^3} : (x_1 + 2x_2 + 3x_3 \leqslant 8})\\R = { x \in{R^3} : (3x_1 - 2x_2 + 4x_3 \leqslant 10})\end{array}

Could someone please explain in the example above on how to formulate the above as an integer programming question?

Answer 1

The difference between a linear program and an integer program is that the latter has an integrality constraint. In other words, there is a requirement that all variables only take on integer values.

In your example, note that the variables $x_i$ belong to the real interval $[0,10]$. In order to modify this into an integer programming problem, all we need to do is modify this constraint so that the variables take on integer values in the same interval.

So the constraint changes to: $$ x_i \in \{0,1, \dots, 10\} \quad \forall \ i \in \{1,2,3\}$$

The rest of the problem remains unchanged as the coefficients of all other constraints are integers.

Answer 2

The way I read your problem you want:

$$\begin{align} &x_1+2x_2+3x_3\le 8\\ &\text{or}\\ &3x_1-2x_2+4x_3 \le 10 \end{align}$$

This can be done by: $$\begin{align} &x_1+2x_2+3x_3\le 8 + M\delta\\ &3x_1-2x_2+4x_3 \le 10 + M (1-\delta)\\ &\delta \in \{0,1\} \end{align}$$

Good values of the big-M's can be derived:

$$\begin{align} &x_1+2x_2+3x_3\le 8 + 52\delta\\ &3x_1-2x_2+4x_3 \le 10 + 60 (1-\delta)\\ &\delta \in \{0,1\} \end{align}$$