• Gurobi Staff

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ł

• Permanently deleted user

Hi 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

• Gurobi Staff

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ł