Questions on the mechanic of the hierarchical method for multi-objective optimization
Answered
Hello,
I would like to know how the hierarchical method for multi-objective optimization works.
For example, I have 2 objectives here: min obj1 and min obj2. The priority for obj1 is set to 10 and the priority for obj2 is set to 5.
According to the documentation, I think the solver would first get all optimal solutions for obj1 (denoted as a set OPT1), and then filter among OPT1 to find optimal solutions for obj2. That is to say, the final optimal solution for the whole problem should be a subset of OBJ1. Therefore, under my thoughts, if OPT1 is obtained, then the optimal solution for obj2 can also be obtained and should take much less time than OPT1 (since the search space is only OPT1).
However, in real cases, when watching the output, I can see gaps of obj1 quickly close while then the gap of obj2 drops really slow. So I believe my explanation of the mechanism is definitely wrong.
So I would like to know how exactly the hierarchical method for multi-objective optimization works? If I would like to implement what I thought above, is it possible in gurobi?
Best,
Runqiu
-
Hi Runqiu,
In the hierarchical method, Gurobi first solves the given model w.r.t. to the objective with highest priority, let's call it obj\(_1\). It solves the model
\[\begin{align}
\max \,\,&\text{obj}_1 \\
\text{s.t.}\,\, &\text{constraints}
\end{align}\]up to a given MIPGap to obtain an optimal objective value ov\(_1\). Gurobi then solves the given model w.r.t. the objective with second highest priority obj\(_2\) and uses objective value ov\(_1\) to constraint the feasible set of next optimization such that obj\(_1\) cannot get worse than ov\(_1\) taking into account some tolerance tol defined by ObjNRelTol and ObjNAbsTol. The model then looks something like
\[\begin{align}
\max \,\,&\text{obj}_2 \\
\text{s.t.}\,\, &\text{obj}_1 \geq \text{ov}_1 - \text{tol} \\
&\text{constraints}
\end{align}\]This is then continued for every additional objective. As you see, Gurobi does not compute a set of optimal solutions for each objective. Note that computing all optimal solutions (up to some given tolerance) is most often not possible in an acceptable amount of time.
However, in real cases, when watching the output, I can see gaps of obj1 quickly close while then the gap of obj2 drops really slow. So I believe my explanation of the mechanism is definitely wrong.
This is expected, since the model gets harder with each solved objective. The feasible set for each subsequent objective gets smaller and depending on the overall numerics of the model and each objective the numerics of each subsequent solve may get worse.
If I would like to implement what I thought above, is it possible in gurobi?
It is theoretically possible with the use of Solution Pools. However, as mentioned above, computing the set OPT1 can take a vast amount of time and does not make this approach applicable in practice. If you are interested in computing multiple solutions on the Pareto front of your multi-objective model, you should have a look at an \(\epsilon\)-method algorithm. It works well if the number of objectives is low and there is enough literature to dive into.
Best regards,
Jaromił0 -
Permanently deleted userHi Jaromił，
Thanks for your answer. I met the same problem. you wrote below sentences in the last comments.
"If you are interested in computing multiple solutions on the Pareto front of your multi-objective model, you should have a look at an epsilon-method algorithm. It works well if the number of objectives is low and there is enough literature to dive into."
What's the mearning of "epsilon-method "here? Could you share more about it?
Regards,
David
0 -
Hi David,
You can find a lot of literature when you search for "epsilon constraint method in multi objective optimization". I found a freely available slide deck from the Purdue University which explains the \(\epsilon\)-constraint method on slide 15. Additionally, the slide deck provides good literature sources which are definitely worth reading.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
3 comments