Multi-objective optimization

Answered

Ben95

• February 17, 2021 14:58

Hi,

I have set up a multi-objective mixed integer optimization model with Gurobi. In my case, I have two objectives and 552 binary variables.

As far as I have understood, Gurobi does not support finding a Pareto front out-of-the-box, is that correct? I have therefore set up a manual brute force computation for my problem that runs in parallel with Gurobi. Gurobi is magnitudes faster of course, but so far does not provide the full set of Pareto-optimal solutions.

My plan was to use the hierarchical optimization approach combined with an absolute MIP gap in order to obtain at least the solutions that minimize objective 1 and objective 2. The optimal solution for objective 1 is found correctly. When optimizing for objective 2, Gurobi provides a solution that minimizes this objective correctly to zero, but the solution is not Pareto-optimal. That is, the solution is dominated and there exist solutions with the same objective 2 value (0 in my case), but a smaller objective 1-value than provided by Gurobi. Only if I set the absolute MIP gap to a value that just comprises the manually computed objective 2-value, is Gurobi able to find the same solution as my manual brute force approach.

Is this behavior correct/intended? Limiting degradation step by step, Gurobi finds all the solutions that lie on my manually generated Pareto front. Still, it suprises me that Gurobi provides dominated solutions when increasing the absolute MIP gap. Is there a simple explanation for this?

I am using Gurobi 9.1.0 via the Python API.

Kind regards,

Benjamin

0

• 

  Jaromił Najman

  Gurobi Staff

  • February 18, 2021 10:51
  • Edited

  Hi Benjamin,

  Is this behavior correct/intended? Limiting degradation step by step, Gurobi finds all the solutions that lie on my manually generated Pareto front. Still, it suprises me that Gurobi provides dominated solutions when increasing the absolute MIP gap. Is there a simple explanation for this?

  This behavior is intended. Gurobi allows for degradation of previous objectives up to a pre-defined gap as described in section Allowing Multiple-Objective Degradation of Working With Multiple Objectives. You can reduce the degradation by setting the relative and absolute tolerances for the specific objectives (ObjNRelTol and ObjNAbsTol).

  Best regards,
  Jaromił

  1

Please sign in to leave a comment.