5
$\begingroup$

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?
$\endgroup$

4 Answers 4

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is a great suggestion. Although, there might be a problem when I have to produce a product of $1000$ items and another one of $5000$ items. This method suggests that the product with less quantity to produce has a priority (since its ratio will be much higher) which is not necessarily true. $\endgroup$
    – Georgios
    Jan 18, 2020 at 15:31
5
$\begingroup$

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$).

$\endgroup$
3
  • $\begingroup$ I have the feeling that the suggested methodologies, create too many variables. Perhaps, my question was not clear enough. Is there no better way to formulate a model, for which when the resources are scarce to underproduce a variety of different products instead of focusing only on fully producing one or two? $\endgroup$
    – Georgios
    Jan 18, 2020 at 12:19
  • $\begingroup$ The model I suggested has one variable ($d$) more than what you already have. $\endgroup$
    – prubin
    Jan 19, 2020 at 16:13
  • $\begingroup$ Correct, to which I added that it is not well formulated. $\endgroup$
    – Georgios
    Jan 20, 2020 at 13:55
5
$\begingroup$

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.$$

$\endgroup$
5
  • $\begingroup$ I tested it with 2 products for two cases but the result is not the desired one. Note the resource has the absolute value of 100. Example 1: $\frac{55}{70} = 0.78$ and $\frac{45}{60} = 0.75$ with obj: -0.47 if $t = 1$ and Example 2: $\frac{40}{70} = 0.57$ and $\frac{60}{60} = 1.0$ with obj: -0.43 if $t = 1$. So the algorithm would have chosen the 2nd one although the 1st one would have been more optimal. $\endgroup$
    – Georgios
    Jan 17, 2020 at 16:15
  • 1
    $\begingroup$ The objective value should be nonnegative, and the solver should be choosing $t$. For Example 1, with $55/70$ and $45/60$, any value of $t \in [45/60,55/70 ]$ yields objective value $55/70-45/60 \approx 0.0357$. $\endgroup$
    – RobPratt
    Jan 17, 2020 at 17:01
  • $\begingroup$ So, in this case, I should set a constraint choosing $t$ so that the objective function is $>0$. In this case $t = 45/60$ if I got it right, setting $e_a = 55/70 - 45/60$ and $e_b = 0$ making the objective function $e_a + e_b = 55/70 - 45/60$ right? $\endgroup$
    – Georgios
    Jan 17, 2020 at 18:52
  • $\begingroup$ No, I don't think you should set $t$ at all. Let the solver find the value of $t$ that yields the best objective value. It sounds like you might have multiple objectives here: maximize production and minimize differences in ratios. $\endgroup$
    – RobPratt
    Jan 17, 2020 at 22:44
  • $\begingroup$ I am aware now that $t$ is a decision variable. I was only trying to comprehend why you get this objective value suggested from you above, e.g., how you get the value of $\approx 0.0358$. Sure I want to write a multiobjective function. A part of it has to do the following. The solver has to split the limited resources to underproduce different products instead of focusing on the production of only one product. $\endgroup$
    – Georgios
    Jan 18, 2020 at 11:42
1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Is there though another way to write the objective function without trying to linearize it? Maybe formulate complete in another way. $\endgroup$
    – Georgios
    Jan 17, 2020 at 19:02
  • $\begingroup$ That depends on what dependency you wish to represent (and optimize) with the objective function. Could you explain your aim further? Also, any particular reason why you'd like to know about other ways of modelling the objective function? $\endgroup$
    – dhasson
    Jan 18, 2020 at 2:33
  • $\begingroup$ The available resource can be an employee that can produce a certain number of different products. Some of the products can not get fully produced, because of the lack of employees (resource). Thus, it is better to produce a reduced amount of each product, instead of focusing on the production of only one them. It is irrelevant for me how this is formulated, so it does not have to be within the objective function. I am interested in an alternative method since with all the formulations suggested above, the solver has to produce too many variables. $\endgroup$
    – Georgios
    Jan 18, 2020 at 11:32

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.