How to find all Pareto Optimal solutions in a multi objective problem

Ongoing

Zachary Teo

• May 21, 2021 02:52

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.

2

• 

  Jaromił Najman

  Gurobi Staff

  • May 26, 2021 12:30
  • Edited

  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
• 

  Zachary Teo

  • June 04, 2021 02:21

  

  

  

  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,
  Zachary

  0
• 

  Jaromił Najman

  Gurobi Staff

  • June 07, 2021 07:56

  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
• 

  Pengfei Su

  • May 09, 2022 20:51

  

  

  Hi Zachary,

  May I know how you solve this problem?

  Many thanks!

  Nick

  0

Please sign in to leave a comment.