Most efficient way to solve multiple objectives

Answered

Fabio David

• February 20, 2022 02:55

Hi

I'm trying to solve a MILP with multiple objectives. For example, suppose I want to min x then min y and finally min z.

I would like to know which is the most efficient way to solve it. Should I create hierarchical objectives with setObjectiveN() or simply create a single objective like x*1000000 + y*1000 + z?  The latter seems to be faster in my tests, is that right? But I am afraid of having numerical issues.

Thanks in advance,
Fabio David

0

• 

  Jaromił Najman

  Gurobi Staff

  • February 21, 2022 13:06
  • Edited

  Hi Fabio,

  It is hard to say which approach is best and it highly depends on your application. The blended approach is easier to solve. However, it may be hard to find suiting objective weights to truly achieve the results one expects.The hierarchical approach is often better suited. Unfortunately, it gets harder to solve with each additional objective. This is because each solved objective is added as a constraint to the model such that it get worse (up to some specified tolerance). You can find more details in Working With Multiple Objectives.

  Short answer: You should definitely try both approaches if you are unsure. If you have good objective weights for the blending approach and are satisfied with the results, then go for it. Otherwise, stick to the hierarchical approach.

  But I am afraid of having numerical issues.

  Numerical issues most often arise from the model's constraints and not from the multiple objectives. Thus, as long as your model is well-scaled overall, you should not run into numerical issues when working with multiple objectives.

  Best regards, 
  Jaromił

   

  0
• 

  Fabio David

  • February 23, 2022 22:41

  

  

  

  Hi Jaromil/Gurobi staff,

  Thanks for your explanation.

  After running some tests, the blended approach seems to be much faster than the hierarquical method, at least in my application.

  The problem now is the order of magnitude of the weight I need to apply. As explained in my last message, I need to minimize x, y and z, in that order. I imagined that the obvious approach would be the hierarquical method. But it sometimes takes too long, so I decided to try blended method. However, "x" can be as big as 3 digits, "y" 3 digits too and "z" 4 digits! So the weights I used were wx=10000000(10e7), wy=10000(10e4) and wz=1.

  The documentation say weights shouldnt be larger than 10e6! When I compared the results between hierarquical and blended approaches, sometimes I got some differences in results of variable z. 

  Any suggestions? Should I set some different tolerance?

  Thanks in advance.

  Best regards,
  Fabio

  -1
• 

  Jaromił Najman

  Gurobi Staff

  • February 24, 2022 08:51

  Hi Fabio,

  The documentation say weights shouldnt be larger than 10e6!

  This is correct. However, if the rest of your problem is well-scaled and only your objective has some very big values, Gurobi often can deal with it. Please note that this does not mean that this should be done every time. It means that for specific cases, such as this one, large objective coefficients may work without numerical issues.

  When I compared the results between hierarquical and blended approaches, sometimes I got some differences in results of variable z. 

  This is expected. When you solve for \(x\) first in the hierarchical approach, Gurobi adds a constraint to the model when solving for \(y\) and \(z\), which makes sure that the \(x\) value does not deteriorate too much (up to some given tolerance). The same happens for \(y\). This limits the possible values for \(z\). In the blended approach, it might be possible that \(z\) can be chosen a bit higher and the objective is still optimal up to some defined MIPGap. How large are the differences in \(z\)? Are they really meaningful?

  Any suggestions? Should I set some different tolerance?

  I don't think that tightening tolerances is the right way to deal with the issue. How much slower is the hierarchical approach for your model? Did you experiment with some parameters to try to speed up the hierarchical approach? You can find the most important parameters in our MIP documentation. You could also try Gurobi's automatic tuning tool to try to improve the performance of the hierarchical approach.

  Note that for multiobjective problems, there often is no "best" solution. It always depends on the decision maker (in this case that's you) to define a good balance between the different objectives. One way to deal with the blended approach is to solve the problem multiple times with different weight and analyze the solutions. You can then choose the best solution based on whatever you find to be most important for your specific application.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.