8
$\begingroup$

I have the following multiobjective optimization problem. The objectives are non-conflicting.

The Optimization Problem:

$$\underset{\large{a^{(l)}_{c,u},f^{(l)}_{c,u},z_{l,t},l\in\mathcal{L}}}{\max}\hspace{6mm}\left\{t^{(l)}_{\rm U},l=1,2,\cdots,N_{\rm L},t_{\rm L}\right\} $$

Since there is no preference (all the objectives have the same priority), I tried with the following objective.

$$\underset{\large{a^{(l)}_{c,u},f^{(l)}_{c,u},z_{l,t},l\in\mathcal{L}}}{\max}\hspace{6mm}\left\{\sum_{l=1}^{N_L}t^{(l)}_{\rm U}+t_{\rm L}\right\}$$

I am not sure if I am doing it right.

Is the single objective that I am using correct?

$\endgroup$
5
  • 1
    $\begingroup$ Are the suppliers shared? Can the costumers' demand be satisfied by more than one supplier? Your problem looks like your previous question here: or.stackexchange.com/q/1434/39 but I still can't really see the appropriate details. Could you elaborate a little more? For example why you put $t_S$ in the objective function? if you maximize all the $t_{sub i}$ as they are positive the summation of all will be automatically maximized. $\endgroup$ Commented Sep 9, 2019 at 16:42
  • $\begingroup$ @OguzToragay, thanks for your comments. The supply to users are provided in a time-slot manner. There are $N_{TS}$ time slots. At each time slot, only 3 subsystems can be active. Each subsystem has its own resources. But due to hardware and power limitations, only 3 subsystems can be active at any time slot. The reason I put $t_S$ in the objective is that, I want to be fair subsystem wise. So, the number of time slots, one subsystem will remain active depends on the total demand of that subsystem. If a subsystem has overall low demand, the subsystem can be active for less number of time slots. $\endgroup$
    – KGM
    Commented Sep 10, 2019 at 9:33
  • 1
    $\begingroup$ This is a much cleaner and clearer statement of your question. I hope someone will post a good answer and claim your bounty! $\endgroup$ Commented Sep 17, 2019 at 1:20
  • $\begingroup$ What do you mean by "the objectives are non-conflicting"? Do you mean that the overall problem can be solved by solving a problem for each subsystem independently? $\endgroup$ Commented Sep 17, 2019 at 9:51
  • $\begingroup$ @RolfvanLieshout, for example, cost minimization and quality maximization are conflicting objectives. This is not the case in this optimization. Yes, you got it right. $\endgroup$
    – KGM
    Commented Sep 17, 2019 at 15:32

1 Answer 1

5
+50
$\begingroup$

If there is a solution that maximizes all the objectives at once, then your choice of objective function is satisfying because this solution will be optimal for the weighted sum. However, from experience, the existence of such a solution is rare. There is rather a whole set of points representing possible compromises between objectives. Exploring them can be done partially by aggregating all objectives into one with a scalarizing function.

There are several ways of scalarizing multiple objectives. Here you chose to sum up all 5 objectives, so you use a weighted sum with a weight of $1$ for each objective. This means that you estimate that $1$ unit on one objective is "tradeable" for $1$ unit of any other objective. Thus, the first thing to check is that your objectives have comparable units. If these are gains that are in €, \$ or another currency, this makes sense. If, for instance, you want to optimize energy gain and a gain in €, then you need to adjust the weight so that it matches your preferences on the tradeoff between $1$ unit of energy gain and $1$ €. From you notations, the last objective, denoted by $t_L$, seems to be a bit different from the others. Make sure that trading one unit of $t_L$ for one unit on another objective is something desirable in your case.

To better illustrate the principle of tradeoffs and its limitations, suppose you have two solutions, resp. denoted by $y^1$ and $y^2$, and evaluated on two objectives such that $y^1=(12,1)$ and $y^2=(3,10)$. Suppose $f$ represents the objective sum that you proposed. Then, the two solutions are equivalent, since we have $f(y^1)=f(y^2)=13$. From $y^1$ to $y^2$, there were $9$ units on the first objective that were traded for an increase of $9$ units on objective 2. Now, suppose that you have a third solution $y^3=(6,6)$. This solution will not be optimal since $f(y^3)=12$, even if its performances on both objectives seems to be more balanced and the weight of each objective equals $1$. More than that, no combination of weights on both objectives will put $y^3$ as the optimal solution, compared to $y^1$ and $y^2$. This type of solution is called non-supported solutions, and cannot be optimal with a weighted sum, no matter the chosen weights for the objectives. Therefore, choosing the weighted sum as scalarizing function limits the scope of solutions you can reach.

If you are interested in other options, there are other scalarizing function like the Ordered Weighted Average1, or some function based on reference points2, that integrates different types of preference but are more complex than the weighted sum.

Since it is a supply/demand problem, the OWA seems to be a potential good fit, because it can be parametrized such that it represents preferences towards equitable performance across all objectives. It will come with a computational cost because it involves additional constraints and variables to keep everything linear. Otherwise, you could only maximize the minimum objective (specific case of the OWA).

To elaborate a bit more on the latter part, I am going to illustrate the $\max\min$ approach on the previous example. Suppose now that the aggregating function $f$ is simply the minimum value across all objectives. So, $f(y)=\min y$, which means that $f(y^1)=1$, $f(y^2)=2$ and $f(y^3)=6$. Therefore, the optimal solution that maximizes the newly defined $f$ function is $y^3$. This approach is useful when you want to have a solution with a fair repartition across objectives. However, practically, you will have to add an extra term to the objective function. Indeed, suppose now that there is a fourth solution $y^4=(6,7)$. Observe that $\min y^4=6=\min y^3$, but you will prefer $y^4$, because it dominates $y^3$ on all objectives. For the solver $y^3$ and $y^4$ are equivalent (because $f(y^3)=f(y^4)$), therefore it will randomly choose $y^3$ or $y^4$. In order to prevent this behavior, the function $f$ should then be defined as $f(y) = \min(y) + \epsilon \sum\limits_{i=1}^n{y_i}$, with $n$ being the number of objectives. $\epsilon$ should be small enough to just be useful when the solver needs to arbitrate between several solutions that have the same minimum value.

Now for the model, you need to add an extra variable, for example denoted by $z$, and add $n$ constraints: $z \leq y_i$ ,$i=1,\ldots,n$ with $n$ still being the number of objectives. Your objective function will then be $\max\left\{z + 0.0001\sum\limits_{i=1}^n{y_i}\right\}$. Since $z$ is lower than all objectives, it is lower or equal to the objective with the minimum value, thus maximizing it will yield the solution having the maximum minimum value.

As Larry pointed out in your other post, MultiObjective Optimization (MOO) may also be an area worth looking at. This area focuses on the nondominated solutions, which are solutions that are not worse than another one on all objectives. You can either generate the whole set of nondominated points, a subset of it or exhibit one specific point. Using a scalarizing function does the latter. Some meta-heuristics provide a subset of the nondominated solutions. And if the problem is not too large, you can try to generate the whole nondominated set (for example, see [3] and the code can be accessed here).


References

[1] Yager, R. R. (1988). On ordered weighted averaging aggregation operators in multicriteria decisionmaking. IEEE Transactions on Systems, Man, and Cybernetics. 18(1):183-190.

[2] Wierzbicki, A. P. (1980). The Use of Reference Objectives in Multiobjective Optimization. Multiple Criteria Decision Making Theory and Application. pp. 468-486.

[3] Kirlik, G., Sayın, S. (2014). A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems. European Journal of Operational Research. 232(3):479-488.

$\endgroup$
5
  • $\begingroup$ Thank you for the reply. I appreciate it. As I choose all the weights to be 1, does my solver outputs the solution $y^3$ even if the sum is lower than the solutions $y^1$ and $y^2$? In my problem, the expected values of all the objective functions are close to 1 or around 1. $\endgroup$
    – KGM
    Commented Sep 18, 2019 at 14:57
  • $\begingroup$ Solution $y^3$ is preferred to solutions $y^1$ and $y^2$. Note that I do have any preference. All the objectives have equal priority. Would you please comment a bit more on "you could only maximize the minimum objective (specific case of the OWA)." Which one is more appropriate in my case, you think? $\endgroup$
    – KGM
    Commented Sep 18, 2019 at 15:24
  • $\begingroup$ Since the value of $f(y^1)=12+1$ and $f(y^2)=3+10$ is 13 and $f(y^3)$ is 12, then $y^3$ cannot be optimal by definition (in a maximization problem) because $13>12$. $\endgroup$
    – drskd
    Commented Sep 19, 2019 at 6:19
  • $\begingroup$ I have edited the answer to elaborate a bit more on the max min approach! $\endgroup$
    – drskd
    Commented Sep 19, 2019 at 6:46
  • $\begingroup$ thanks for your very illustrative answer. It helps a lot to grasp. You mentioned that max-min ais a specific case of OWA. Any comment/example or reference for this would be highly appreciated. $\endgroup$
    – KGM
    Commented Sep 19, 2019 at 10:13

Your Answer

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