# Integer programming with indicators

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? • How do you represents the indicators using linear functions? Nov 15, 2020 at 7:41 • 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. Apr 14, 2021 at 13:01 • What makes a proper solution hard is that it is so easy to solve in your head. You but everything from 1 until you reach the point where 2 is cheaper. At that point you switch to buying everything from 2. 2 is cheaper for 446 presents. Dec 5, 2022 at 18:48 ## 1 Answer 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/ • 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 Nov 15, 2020 at 14:38 • 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. Nov 15, 2020 at 17:02 • 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. Nov 15, 2020 at 19:13
• I gave you links how to implement min and max using linear functions. Nov 16, 2020 at 7:34