Integer Programming - How to express a conditional variable whose properties change once a value has been reached.

Question

I have the following question. In an exercise they tell me:

• You have the following product B that brings $25 of profit per unit, and takes a production time of 2.1 man-hours per unit to produce.

• However, once more than 110 units have been produced, the number of man-hours required will become 3.1 man-hours for any additional units.

I am not sure how to express this within my maximisation formula paired to the constraints. I thought about splitting it into two variables, $X_{b1}$ and $X_{b2}$ where the first variable is for those units under 110 produced, and the second over.

However, when it comes to expressing it through constraints I got stuck at the following step:

• $X_{B1}$ ≤ 110 + M$w_{B}$
• 2.1$X_{B}$ + $w_{B}$ ≤ 231 (Given that 2.1*110 units is 231 and $w_{B}$ is a binary variable which indicates whether the production of B is over 110 units.)

I thought this step would help me restrict the value of B1 to under 110, but I am pretty stuck. Any help is appreciated.

P.S: The maximum number of man-hours to produce the items is 730.

Answer 1

I will assume that you want to maximize profit while keeping man-hours below a limit $H$. Let $x$ indicate the number of units of product $B$ made, up to $110$. We indicate this by forcing $0 \leq x \leq 110$. Let $y$ indicate the number of units made beyond $110$, if any, so we only need $y \geq 0$. The total number of units made is $x+y$. For example, if we made 120 units, we'd have $x=110$ and $y=10$.

Our linear program is then: we want to maximize $25(x+y)$ given that:

• $2.1x + 3.1y \leq H$
• $0 \leq x \leq 110$
• $0 \leq y$

Now, you may be worried that we can write $120 = 60 + 60$, i.e. $x=60$ and $y=60$, so that we use up more man-hours than we really need, and hence this linear program includes possibilities that are not allowed in the original problem. However, so long as $0 \leq x \leq 110$, we can raise $x$ and lower $y$ by the same amount, keeping the profit the same but using less man hours, so we still remain with $2.1x + 3.1y \leq H$, and indeed there may be room for more hours available.

Said another way, although it seems that this linear program allows for more possibilities than what you've described, any solution to this linear program can be transformed to adhere to the conditions you've described, by raising $x$ and lowering $y$ by the same amount, to a solution where $x$ is as large as it can be below $110$ and $y$ is whatever remains.

Answer 2

Or you can make it tighter by introducing a binary variable $ z$ with the constraints
$ 110(1-z) \le x \le 110z + U_x(1-z)$
$ U_x \gt 730$ is upper bound for $x$, kind of $M$

As for the constraint: $ 2.5x + 2.5*110+3.5x \le H$ where $H=730$, this can be implemented as below
$ 2.5x \le Hz +U_x(1-z)$
$ 2.5\times110+3.5x \le H (1-z) + U_xz$
when $z=0$ the constraint with $2.5x$ becomes redundant as the next constraint turns active.