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.


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.

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

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

  • $\begingroup$ Okay! thanks for clarifying!! $\endgroup$
    – Slim Shady
    Commented Nov 12, 2019 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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