MIP for similar production percentages in production planning

Question

As a task, I want to produce three products $x,y,z$ in different quantities $a,b,c>0$ respectively.

It is not always possible to produce the full amount of each product, because of a lack of resources.

Now I want to set an objective keeping the percentage between $a^*/a$, $b^*/b$ and $c^*/c$ as similar as possible with $a^*,b^*,c^*$ being the decision variables for the actual amount of produced numbers.

Moreover the following attributes have to hold:

1. $a^* \leq a,b^*\leq b,c^*\leq c$
2. $a^* + b^* + c^* \leq |\rm resources|$.

My thoughts on this:

• I thought that by maximizing the sum of $a^*/a$, $b^*/b$ and $c^*/c$ would have the wanted effect which is not the case.
• A way to do so would be to write an objective in the following way: $$\min\ \left|\frac{a^*}{a}-\frac{b^*}{b}\right| + \left|\frac{b^*}{b}-\frac{c^*}{c}\right| + \left|\frac{a^*}{a}-\frac{c^*}{c}\right| $$ which is not linear and perhaps not the best way to formulate.
• Is there a better objective function without having to linearize the upper part?

Answer 1

Based on your comments, I have an alternative suggestion. You had tried maximizing the sum of $a^*/a$, $b^*/b$, and $c^*/c$. Maybe instead maximize the minimum of these, which you can do linearly by introducing a new variable $z$ to be maximized, with additional constraints: \begin{align} z&\le a^*/a\\ z&\le b^*/b\\ z&\le c^*/c \end{align} This approach will not necessarily make the ratios similar, but it will try to prevent any of them from being small.

Answer 2

Here's one option: \begin{align}\min&\quad d\\\mathrm{s.t.}&\quad-d\le\frac{a^{*}}{a}-\frac{b^{*}}{b}\le d\\ &\quad-d\le\frac{a^*}a-\frac{c^*}c\le d\\ &\quad-d\le\frac{b^*}b-\frac{c^*}c\le d\\ &\quad R_\min\le a^*+b^*+c^*\le R_\max\\ &\quad0\le a^*\le a\\ &\quad0\le b^*\le b\\ &\quad0\le c^*\le c\\ &\quad d\ge0\end{align} where $R_\min$ and $R_\max$ are respectively the minimum and maximum acceptable resource expenditures (both parameters). This is basically working with the absolute differences of the ratios. Forcing the decision maker to use at least some minimal amount of resources avoids the trivial solution (do nothing) being optimal, a risk Rob Pratt pointed out. An alternative to using $R_{min}$ is to change the lower bounds of the three starred variables from $0$ to some multiple of their respective upper bounds (e.g., $\lambda a\le a^*\le a$ where $\lambda(a+b+c)\le R_\max$).

Answer 3

You could let decision variable $t$ represent the desired common percentage, and penalize the absolute differences by minimizing $$\left|\frac{a^*}{a}-t\right|+\left|\frac{b^*}{b}-t\right|+\left|\frac{c^*}{c}-t\right|,$$ which you can linearize by minimizing $e_a + e_b + e_c$ subject to \begin{align} -e_a \le \frac{a^*}{a}-t &\le e_a\\ -e_b \le \frac{b^*}{b}-t &\le e_b\\ -e_c \le \frac{c^*}{c}-t &\le e_c \end{align} and your other constraints.

Without some constraint that forces production, an optimal solution will be $$a^*=b^*=c^*=t=e_a=e_b=e_c=0.$$

Answer 4

You could try this: Adding three auxiliary variables for the absolute values of the difference of the percentages: $s_{ab}, s_{bc}$ and $s_{ac}$. Adding additional constraints to the model:

\begin{align}s_{ab}&\geq\frac{a^*}a - \frac{b^*}b\\s_{ab}&\geq\frac{b^*}b - \frac{a^*}a\\s_{bc}&\geq\frac{b^*}b - \frac{c^*}c\\s_{bc}&\geq\frac{c^*}c - \frac{b^*}b\\s_{ac}&\geq\frac{c^*}c - \frac{a^*}a\\s_{ac}&\geq\frac{a^*}a - \frac{c^*}c\end{align}

With the following objective function: $$\min s_{ab}+s_{bc} + s_{ca},$$ which yields a linear objective function and constraints, and minimizing it drives more similar value of the fractions $\frac{a^*}a, \frac{b^*}b, \frac{c^*}c$.