Integer programming with indicators

Question

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:

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).
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?

How do you represents the indicators using linear functions? — user1543037, Nov 15 '20 at 7:41

user1543037 · Accepted Answer · 2020-11-15 07:47:25Z

0

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/

answered Nov 15 '20 at 7:47

user1543037

3161 gold badge2 silver badges4 bronze badges

$\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

Add a comment |

1 Answer 1