I am trying to formulate the following MILP:

A company produces products A and B by processing material M through a machine. The requirements and selling price of a unit of each product are given as follows:

Product A requires 5 units of M and 2 minutes of machine time to make, and sells for £25.

Product B requires 8 units of M and 6 minutes of machine time to make, and sells for £45

The company has available 120 minutes of machine time weekly at no cost. The material M, however, must be purchased from an outside vendor. The company can purchase no more than 350 units of M per week. The price is £3/unit for the first 200 units, and £2/unit afterward. Formulate the mixed integer-linear programming problem to maximise the revenue of the company.

So far I have the following: Define $x_1$ and $x_2$ to be the number of units of A and B, respectively, to be produced and sold weekly, $x_3$ the number of units of M purchased at £3/unit and $x_4$ the number purchased at £2/unit.

The cost function to be maximized is $\max z=25x_1+45x_2-3x_3-2x_4$, subject to

$2x_1+6x_2 \leqslant 120$, (constraint on machine time),

$\quad$$\qquad$ $x_3\leqslant200$, (since after 200 units, M costs £2 instead of £3),

$\quad$$x_3+x_4\leqslant350$ (constraint on unit of M purchased per week),

and $x_1,x_2,x_3,x_4\geqslant0$.

But I am unsure how to formulate the "if-then" constraint that would make sure that if $x_3<200$ then $x_4=0$. I think I'll need to introduce a binary variable, any hints on how to go about this would be appreciated!

I also need a constraint that says that A is made from 5 units of M, and B is made from 8, but don't know how exactly. Is the constraint $5x_1+8x_2\leqslant x_3+x_4 \quad$ i.e $\quad 5x_1+8x_2-x_3-x_4\leqslant0$ sufficient?

Many thanks!


First Question

You could introduce a binary variable, as you suggest. Let $z\in\{0,1\}$--intuitively, $z=0$ if $x_3<200$. Then add the constraints

$$ x_4\leqslant 350z $$ and $$x_3\geqslant200z.$$

If $z=0$, then we must have $0\leqslant x_4\leqslant0$, that is, $x_4=0$. Also, the constraint $x_3\geqslant 200z$ becomes $x_3\geqslant0$, which was already a constraint.

If $z=1$, then we have that $x_3\geqslant200$, which, combined with your constraint $x_3\leqslant200$ implies that $x_3=200$. Also, the first constraint becomes $x_4\leqslant350$, which is already true, since you enforce the constraint that $x_3+x_4\leqslant350$.

These kinds of constraints are called big-$M$ constraints--they're very useful!

Second Question

Yes, those constraints look sufficient. You are essentially saying that you cannot produce more than the raw materials you purchased will allow.


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.