2
$\begingroup$

I have an optimization problem where I'd like to maximize revenue and I have separate variables for cost and revenue.

  • Building a single unit of a product takes 100 hours of labor
  • I have a list of staff, the number of hours they have available, and the cost per hour for each
  • The projected revenue of the product changes based on the total cost to build the unit
  • If cost is less than 2500, revenue = 40 * cost
  • If cost is between 2500 to 5000, revenue = 25 * cost
  • If cost is > 5000, revenue = 8 * cost
  • I want my objective function to maximize the appropriate revenue formula based on what the cost might be

I tried to use the BigM notation to determine which range the cost falls into, and then my objective function looked something like
Maximize(
is_cost_group_1 * (40 * cost) +
is_cost_group_2 * (25 * cost) +
is_cost_group_3 * (8 * cost))
but this gave me an error'ed saying the solver does not support quadratic functions.

Is this possible as a linear programming problem?

Improve this question
$\endgroup$
3
  • $\begingroup$ As stated, your cost function is discontinuous. If the cost is 2500, your revenue is 62,500. If the cost is 2499 (just slightly lower), your revenue is 99,960 (much higher). Is this intentional (and realistic), or do you want the marginal (incremental) revenue rate to be 40/25/8? $\endgroup$
    – prubin ♦
    Apr 4, 2022 at 15:44
  • $\begingroup$ While this example is just a theoretical one, the discontinuous cost function is intentional and realistic because if we can keep the cost under 2500, we can sell more units to a wider audience whereas the higher cost will target fewer customers. $\endgroup$
    – Eddie
    Apr 4, 2022 at 18:37
  • $\begingroup$ Demand being a decreasing function of price is fine, but cost is not price. If your cost is 2501 (revenue 62,525) and you pretended it was 2499 (revenue 99,960), would the extra 37,435 in revenue not cover the extra cost (and then some)? $\endgroup$
    – prubin ♦
    Apr 4, 2022 at 19:26

1 Answer 1

Reset to default
1
$\begingroup$

Given the discontinuities in the revenue function, you cannot use a linear program, but you can use a mixed-integer linear program. (If the revenue function were continuous with diseconomies of scale, you could use a linear program.)

Let $x$ be the cost variable and $y$ the revenue variable (which you will maximize). Let $M$ be an upper limit on $x$ (the maximum cost you might encounter). Introduce three binary variables $z_1,z_2,z_3$ together with the following constraints:\begin{align*} z_{1}+z_{2}+z_{3} & =1\\ x & \le2500z_{1}+5000z_{2}+Mz_{3}\\ y & \le40x\\ y & \le25x+15M(1-z_{2})\\ y & \le8x+32M(1-z_{3}). \end{align*} If $z_1=1$, your cost is up to 2500 (but no higher) and your revenue is up to 40 times the cost (and therefore will be 40 times the cost). If $z_2=1$, your cost is up to 5000 and your revenue no more than (therefore equal to) 25 times cost. If $z_3=1$, cost is up to $M$ and revenue no more than 8 times cost.

Note that break points qualify for the higher revenue value. For instance, a cost of exactly 2500 can result in revenue $40\times 2500$. To enforce strict inequality (revenue rate 40 only if cost strictly less than 2500) you need to change 2500 and 5000 in the second constraint to $2500-\epsilon$ and $5000-\epsilon$ for some small $\epsilon>0$ and then live with the discrepancy that cost $2500-\epsilon/2$ on earns revenue multiple 25 and not 40.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Great, that works if I put the cost in as a static number! However, I have an issue. The costs are variable as well which I am also trying to have the optimizer solve for. So when “x” is represented by a variable list of cost items the optimizer is telling me “Solver does not support quadratic” I believe this is because the optimizer is thinking of “Z1” (as well as Z2 and Z3) as one variable in the optimization problem and “X” as a second one that it can’t multiply those together. $\endgroup$
    – Eddie
    Apr 5, 2022 at 17:45
  • $\begingroup$ Additionally, you mention that I could use a linear program if the revenue function were continuous with diseconomies of scale. I have a second optimization to make that would fall under this category and I didn’t realize they would get solved differently. Can I share that one as well? It looks essentially like this. For X1 = 0-23.3 it is represented by -.676*X+8.24 For X2 = 23.4 to 239 it is represented by .12755*X-10.47 For X3 >239 it is represented by 20 Similar to what I mentioned above X is also a variable number made up of a subset of approximately 100 different items. $\endgroup$
    – Eddie
    Apr 5, 2022 at 17:45
  • $\begingroup$ I recommend starting a new question with the second problem, after we resolve what is going on with this problem. In my answer, I am assuming that cost $x$ is a variable. My answer does not multiply $x$ and $z_i$ together. $\endgroup$
    – prubin ♦
    Apr 5, 2022 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.