$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?


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}$$

  • $\begingroup$ but my variable $x_i$ can take any value between $[0,10]$ so how would adding a big M to the contraints change the linear problem into an integer problem $\endgroup$ – kardongastel Oct 21 '17 at 11:03
  • 1
    $\begingroup$ What about the variable $\delta$? That requires a MIP solver. $\endgroup$ – Erwin Kalvelagen Oct 21 '17 at 13:29

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.