0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ How do you represents the indicators using linear functions? $\endgroup$
    – user1543037
    Nov 15, 2020 at 7:41
  • 1
    $\begingroup$ Since there are only 100 employees, the conditions for $>300$ or $>500$ are irrelevant, aren’t they? Just buy all 100 from supplier 1, who is cheaper. $\endgroup$
    – Emil Jeřábek
    Apr 14, 2021 at 13:01

1 Answer 1

Reset to default
0
$\begingroup$

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/

Improve this answer
$\endgroup$
4
  • $\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, 2020 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, 2020 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, 2020 at 19:13
  • $\begingroup$ I gave you links how to implement min and max using linear functions. $\endgroup$
    – user1543037
    Nov 16, 2020 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.