I have the following question, and I need to write it as an integer programming problem:

A manager of a company wants to by presents to his 100 employers. He can buy the presents from two different suppliers:

  1. Every present costs 110\$. For any present above 500, the manager would have to pay 5\$ extra for insurance (for example, for 502 presents, there will be 10\$ extra for insurance).
  2. Every present costs 120$. For any present above 300, there is a discount of 30% (each present above 300 costs 84\$).

I need to find how many presents he should buy from each supplier, in order to spend the minimal amount of money.

I defined:

$x_1, x_2$ - The number of presents to buy from each supplier.

$z_1$ - Indicator which represents whether or not $x_1 \ge501$

$z_2$ - Indicator which represents whether or not $x_2 \ge301$

I know how to represents the indicators using linear functions, but I don't know how to find a linear objective function.

My best suggestion is:

$$ 110x_1+5z_1(x_1-500)+120x_2-36z_2(x_2-300) $$

However, this is not a linear function, because I multiply the decision variables.

How can I turn it into a linear function?

  • $\begingroup$ How do you represents the indicators using linear functions? $\endgroup$ – user1543037 Nov 15 '20 at 7:41

You can multiply variables in ILP with https://blog.adamfurmanek.pl/2015/08/29/ilp-part-2/ and https://blog.adamfurmanek.pl/2015/09/26/ilp-part-6/ and https://blog.adamfurmanek.pl/2015/10/03/ilp-part-7/

You don't need multiplication, though. Your objective function is effectively:

$ \min(500, x_1) \cdot 110 + \max(x_1 - 500, 0) \cdot 115 + \min(300, x_2) \cdot 120 + \max(x_2 - 300, 0) \cdot 84 $

You can represent max/min functions as comparison + absolute value, as explained in https://blog.adamfurmanek.pl/2015/09/19/ilp-part-5/

  • $\begingroup$ I can transfer each max into a variable $M$, and than claim that $M\ge max$, and that it's greater than both of the max arguments, but I can't transfer the min in to $m \le min$, since it will add optimal solutions $\endgroup$ – Daniel Nov 15 '20 at 14:38
  • $\begingroup$ Sorry, I don't get what you're talking about. Just calculate $m_1 = \min(500, x_1)$ and use it in calculations. No need to another variable which would be even lower. $\endgroup$ – user1543037 Nov 15 '20 at 17:02
  • $\begingroup$ Since min and max are not linear functions, we learned that we should add a new decision variable, $M=max(a,b)$, and if it's possible, to change this constraint to $M \ge a$ and $M \ge b$, and similar thing for $m = min(a,b)$. But those things are possible only if they don't change the optimal value. $\endgroup$ – Daniel Nov 15 '20 at 19:13
  • $\begingroup$ I gave you links how to implement min and max using linear functions. $\endgroup$ – user1543037 Nov 16 '20 at 7:34

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.