How to find all Pareto Optimal solutions in a multi objective problem
Ongoing
Hello!
I understand from https://www.gurobi.com/documentation/9.1/refman/working_with_multiple_obje.html that there are 2 ways one can work with multi-objective problems in Gurobi - Blended and Hierarchical.
And understand that using these methods, will give me a solution on the Pareto front.
However, is there a way to use Gurobi to exhaustively find all solutions on the Pareto front? I understand I can use ObjNRelTol and ObjNAbsTol to do Multiple-Objective Degradation but I do not want to find dominated solutions.
As with quite a lot multi-objective problems, my problem is not 100% defined, am not able to use weights or rankings since I am not able to determine which objective is more important and by how much. Which is why I want to list out all solutions on the Pareto front and to then be able to qualitatively determine which is the "best" solution.
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
Hi Zachary,
There is no built in feature in Gurobi to obtain the Pareto front. Obtaining the Pareto front gets very complex quickly with a rising number of objectives.
If you to compute the Pareto front, you will have to implement an own algorithm for that. For MILPs, you could have a look at
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.The algorithm described therein computes all extreme points of the Pareto front which are required to identify the whole Pareto frontier.
The notes by
M. Ehrgott. Multicriteria optimization. Volume 491. Lecture notes in economics
and mathematical systems. Springer Science & Business Media, 2005.should also be a nice starting point when you are interested in Multi-Objective Linear Problems and their Pareto frontiers.
Best regards,
Jaromił0 -
Hi Jaromił,
Thanks so much for getting back to me and for the pointing me to the right resources!
Sorry it took me awhile to process your comment and get back to you. May I ask how does computing the extreme points allow for the identification of the whole Pareto frontier? I don't quite understand how that might work.
Best Regards,
Zachary0 -
Hi Zachary,
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 mentioned in my previous message. For more insight, please refer to the notes by Ehrgott. There are also multiple well explained examples in there.
Best regards,
Jaromił0 -
Hi Zachary,
May I know how you solve this problem?
Many thanks!
Nick
0
Post is closed for comments.
Comments
5 comments