Integer programming example clarification

Question

There is an explanation in my book for an integer programming example, which goes like this:

A company is considering manufacturing three types of autos: compact, midsize, and large. The resources required, and the profits yielded, by each type of car are shown in the table. \begin{array}{c|ccc|c}&&\underline{\text{Car Type}}&&\text{Available}\\\text{Resource}&\text{Compact}&\text{Midsize}&\text{Large}&\text{Resources}\\\hline \text{Steel Required}&1.5\,\,\text{tons}&3 \,\,\text{tons}&5 \,\,\text{tons}&6000\,\, \text{tons}\\\text{Labour Required}&30\,\, \text{hrs}&25 \,\,\text{hrs}&40\,\, \text{hrs}&60000 \,\,\text{hrs}\\\hline \text{Profit}\,\, ({\it£})&2000&3000&4000&\\\hline\end{array} For the production of a type of car to be economically feasible, at least $1000$ cars of that type must be produced. Formulate an IP to maximize the profit.

Solution:

Let $x_1$, $x_2$ and $x_3$ be the number of compact, midsize and large cars produced respectively.

Resource Constraints: \begin{align}1.5x_1 + 3x_2 + 5x_3&\leq 6000 \ \ \text{(Steel resource)}\\30x_1 + 25x_2 + 40x_3 &\leq 60000 \ \ \text{(Labour resource)}\end{align} If we decide to produce any cars of a given type, then it must be at least $1000$ cars of that type. \begin{align}\text{Constraint 3}:x_1 \le 0 \ \ &\text{or} \ \ x_1\ge 1000\\\text{Constraint 4}:x_2 \le 0 \ \ &\text{or} \ \ x_2\ge 1000\\\text{Constraint 5}:x_3 \le 0 \ \ &\text{or} \ \ x_3\ge 1000.\end{align}

For Constraint $3$, $x_1 \le 0 \ \ \text{or} \ \ x_1\ge 1000$ so \begin{align}\text{Either}&\quad x_1\le0\color{maroon}{+My_1}\\\text{or}&\quad-x_1\le-1000\color{maroon}{+M(1-y_1)}\\&\quad y_1=0\ \ \text{or}\ \ 1\end{align} When $y_1=0$, \begin{align}x_1&\le0\\-x_1&\le-1000+M\end{align} and when $y_1=1$, \begin{align}x_1&\le M\\-x_1&\le-1000.\end{align} The constant $M$ should not restrict the values of decision variables, so \begin{align}1.5x_1+3x_2+5x_3&\le6000\\30x_1+25x_2+40x_3&\le60000.\end{align} For $x_1$, $M\ge2000$. For $x_2$, $M\ge2000$. For $x_3$, $M\ge1200$.

I don't understand why $M_1, M_2, M_3$ are equal or bigger than $2000$, $2000$ and $1200$ respectively. From where have these numbers been deduced? I'm confused.

Answer 1

You can choose large numbers for your $M$s (big-M) (that's why they are called that), but you also want to make sure they are not very large. See the discussions here and here for the reasons.

In your example, your big-Ms just need to be bigger than the upper bound of the values that the variables can take (as @Stradivari mentioned). So, for each of $x_1, x_2, x_3$, take the $\min$ of values they can get from the resource (steel and labor) constraints and you get your big-Ms.

For example for $x_1$: $$\min\left(\frac{6000}{1.5}, \frac{60000}{30}\right)=2000 $$

Do the same for $x_2$ and $x_3$ and you get $2000$ and $1200$, respectively.