1
$\begingroup$

I would like to know if there are methods that can gurantee to find all pareto-optimal solutions of a multi-objective optimization problem.

I found some possible approaches but I don't know if they can in fact find all Pareto-optimal solutions:

Do you know these methods and can you tell me if they can find all Pareto-optimal solutions? If not, do you know any method that is capable to do so? I am asking for exact methods (so no heuristic or local optimization approach).

Edit: I am asking for methods for any multiobjective optimization problem (n goals, continious or mixed-integer problems, convex or non-convex).

Reminder: Can nobody tell me a little bit more about multiobjective optimization problems? Do you know any methods for solving them exactly?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ What type of type of multi objective optimisation problem do you want solve? Is it continuous or discrete, convex or not, bi-objective or multi objective? It’s important to know before recommending a method. $\endgroup$
    – Sune
    Jul 8 at 19:16
  • $\begingroup$ @Sune: Thanks Sune for your comment. Actually I am looking for a methods for any multiobjective optimization problem. Is there a method that can solve problems with n objectives that are non-convex and mixed-integer? If not, what properties does the problem need to have in order to be solvable $\endgroup$
    – PeterBe
    Jul 9 at 13:38
  • $\begingroup$ @PeterBe, as far as I know, the $\epsilon$-constraint algorithm can solve MIP and MINLP. But I am not aware of if it can guarantee to find all Pareto-optimal solutions. $\endgroup$
    – A.Omidi
    Jul 11 at 5:26
  • $\begingroup$ @A.Omidi: Thanks for the comment Omidi. I am also not sure, this is why I asked the question and hope that someone can tell me a little bit more about this topic. $\endgroup$
    – PeterBe
    Jul 11 at 9:49

2 Answers 2

Reset to default
2
+50
$\begingroup$

Whether a particular method is capable of generating all efficient solutions is often a question of what structure the MOOP (multi objective optimisation problem) has.

In addition, you ask for methods that can generate all Pareto optimal solutions. In the single objective case, this is equivalent to asking for all alternative optimal solutions. Often what algorithms generate is a so-called minimal complete set of Pareto optimal solutions, which is a subset of Pareto optimal solutions such that there is exactly one solution for each non-dominated outcome vector. In linear and mixed integer linear MOOPs you also need to figure out how you want to represent the set of non-dominated outcomes and their corresponding pre-images: using extreme points, faces/facets, or both.

If the problem is a convex MOOP (convex objectives and convex feasible set) then for every Pareto optimal solution, $x$, there exists a weight vector for which $x$ is optimal to the weighted sum problem. And furthermore, if $x$ is optimal to the weighted sum problem for some weight vector, then it is Pareto optimal. Hence algorithms based on weighted sum scalarizations are in principle capable of generating all Pareto optimal solutions. However, there might very well exist multiple optimal solutions to a weighted sum problem, so you might need to tickle your single objective solver in order to get all the alternatives (they are all Pareto optimal). For the bi objective case the algorithm by Cohon usually works well. Especially if the problem is also linear. If you have a higher dimensional linear problem I usually resort to versions of Bensons algorithm. Bensons algorithm provides both a face and an extreme point representation.

For combinatorial MOOPs, usually ranking based methods are used when all Pareto optimal solutions must be generated. These methods often rely on solving weighted sums and then ranking solutions for a given weight. Standard references include the “two-phase papers” by Ulungu and Teghem. From a practical perspective, some type of $\varepsilon$-constraint based method is usually difficult to beat (for two objectives) both with respect to computation time and implementation time.

Through the last couple of years branch and bound methods for combinatorial MOOPs (with more than two objectives) have shown some potential. You can look at papers by N. Forget, S. Paragh, or K. Klamroth (among others).

For non-convex continuous MOOPs I do not know much. I would look for papers from e.g. G. Eichfelder.

Concluding I would like to stress that asking for an algorithm that is good for any type of problem, is like asking for the perfect tool for building a house. The tool depends on the task at hand!

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks a lot Sune for your answer. I have 2 follow up questions.1) What do you mean by "Often what algorithms generate is a so-called minimal complete set of Pareto optimal solutions, which is a subset of Pareto optimal solutions such that there is exactly one solution for each non-dominated outcome vector. " --> What is a non-dominated outcome vector and which algorithms can generate them? 2) What about the Box-method by Hamacher et al., 2007? You mentioned that for convex problems you can use the Dichotomic approach by Cohon et al, 1979, or the ε-constraint by Chankong et al, 1983 $\endgroup$
    – PeterBe
    Jul 13 at 15:05
  • $\begingroup$ @PeterBe A non-dominated outcome vector is the image in objective space of a Pareto optimal solution. That is, if $f:\mathcal{X}\rightarrow\mathbb{R}^p$ is the objective function(s), $\mathcal{X}$ is the set of feasible solutions, and $\hat{x}\in\mathcal{X}$ is a Pareto optimal solution, then the point $\hat{y}=f(\hat{x})$ is a non-dominated outcome vector/point. $\endgroup$
    – Sune
    Jul 13 at 18:53
  • $\begingroup$ The box method by Hamacher et al. is intuitively pleasing and elegant. It requires the solution of a lexicografic optimisation problem in each iteration, which might be expensive. As I recall, the method is only exact if the set of non-dominated outcome vectors is discrete (I might be wrong though) $\endgroup$
    – Sune
    Jul 13 at 18:57
1
$\begingroup$

I would like to add the following resources that were mentioned by Gurobi experts and would be useful:

These extreme points are non-dominated points on the Pareto front. It is possible to compute all of these points and reconstruct the whole Pareto front from them. This idea is presented in the paper by Özpeynirci & Koksalan.

  1. O. Ozpeynirci and M. Koksalan. “An Exact Algorithm for Finding Extreme Sup- ported Nondominated Points of Multiobjective Mixed Integer Programs”. In: Management Science 56.12 (2010), pages 2302–2315.
  1. M. Ehrgott. Multicriteria optimization. Volume 491. Lecture notes in economics and mathematical systems. Springer Science & Business Media, 2005.
Improve this answer
$\endgroup$
2
  • $\begingroup$ @Thanks Omidi for your answer. Do you know if these methods can find all pareto-optimal solutions for every multiobjective optimization problem (linear/nonlinear, convex/non-convex etc.) $\endgroup$
    – PeterBe
    Jul 11 at 14:48
  • $\begingroup$ @PeterBe, you're welcome. Actually I am not digging into the paper to read in details, but as it commented it can find all pareto optimal solution. It would be worth to read. 🙏 $\endgroup$
    – A.Omidi
    Jul 11 at 16:07

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.