5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's the upper bound for each variable given the two constraints. $\endgroup$ – Stradivari Nov 12 '19 at 15:56
  • $\begingroup$ @Stradivari okay but why exactly those numbers? just random numbers? $\endgroup$ – user6969 Nov 12 '19 at 16:18
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Okay! thanks for clarifying!! $\endgroup$ – user6969 Nov 12 '19 at 16:51

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.