# integer programming with indicators

Mathematics Asked on November 18, 2020

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

A manager of a company wants to give presents to his 1000 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? ## One Answer Introduce nonnegative integer decision variables $$y_1$$ and $$y_2$$ to represent "extra" presents. The problem is to minimize $$110x_1+5y_1+120x_2-36y_2$$ subject to begin{align} x_1 &le 500 + y_1 tag1 \ y_2 &le (1000-300) z_2 tag2 \ x_2 &ge 300 z_2 tag3 end{align} Constraint $$(1)$$ and the objective enforce $$y_1 = max{x_1-500, 0}$$. You don't need $$z_1$$. Constraint $$(2)$$ enforces $$y_2 > 0 implies z_2 = 1$$. Constraint $$(3)$$ enforces $$z_2 = 1 implies x_2 ge 300$$. Answered by RobPratt on November 18, 2020 ## Add your own answers! ## Related Questions ### InvariantSU(3)$subgroup for${bf 8}$in${bf 3}^* otimes {bf 3} ={bf 1} oplus {bf 8}$1 Asked on December 3, 2021 by annie-marie-cur ### Proof that a continuous function with continuous right derivatives is differentiable. 1 Asked on December 3, 2021 ### Finding the volume when a parabola is rotated about the line$y = 4$. 1 Asked on December 3, 2021 ### Differential equation, modulus signs in solution? 2 Asked on December 3, 2021 by refnom95 ### Consider the sequence where$a_1>0$,$ka_n>a_{n+1}$and$0<k<1$. Can we say it converges? 1 Asked on December 3, 2021 by oek-cafu ### In a Reflexive banach space, given a closed convex set$C$and some point$y$, there is a point in$C$, of minimal distance to$y$2 Asked on December 3, 2021 ### Ball / Urn question with a twist 1 Asked on December 3, 2021 by user109387 ### How to prove$phi'(t)1_{Omega_t}(w)$is measurable? 1 Asked on December 3, 2021 by czzzzzzz ### Using characteristic functions to determine distribution of sum of independent normal random variables. 0 Asked on December 3, 2021 by jkeg ### Radioactivity formula using differential equations? 3 Asked on December 3, 2021 by mitali-mittal ### What is the algebraic interpretation of a contracted product? 0 Asked on December 3, 2021 by james-steele ###$f:[0,1]rightarrow[0,1]$, measurable, and$int_{[0,1]}f(x)dx=yimplies m{x:f(x)>frac{y}{2}}geqfrac{y}{2}$. 1 Asked on December 3, 2021 ### Evaluating an integral with a division by$0$issue 3 Asked on December 1, 2021 ### Evaluating$sumlimits_{i=lceil frac{n}{2}rceil}^inftybinom{2i}{n}frac{1}{2^i}$1 Asked on December 1, 2021 by maxim-enis ### Lie group theory’s connection to fractional calculus? 0 Asked on December 1, 2021 ### Solution to autonomous differential equation with locally lipscitz function 1 Asked on December 1, 2021 ### Let$A,Bin M_n (mathbb R), lambdain sigma(B), alpha in sigma (B)$and$$be inner product show$=lambda||x||^2+alpha\$

0  Asked on December 1, 2021

### Is an automorphism a function or a group?

2  Asked on December 1, 2021 by josh-charleston

### Fundamental Theorem of Projective Geometry for Finite Fields

0  Asked on December 1, 2021 by am2000

### Prove a metric space is totally bounded

2  Asked on December 1, 2021

### Ask a Question

Get help from others!