Skip to main content

Questions on the mechanic of the hierarchical method for multi-objective optimization

Answered

Comments

1 comment

  • Jaromił Najman
    Gurobi Staff 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\) plus some tolerance ObjNRelTol and ObjNAbsTol. The model then looks something like

    \[\begin{align}
    \max \,\,&\text{obj}_2 \\
    \text{s.t.}\,\, &\text{obj}_1 \leq \text{ov}_2 \\
    &\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

Please sign in to leave a comment.