Work-around for multi-objective optimization

[nicola-gigante]

Hi all,

the documentation notes that the UP does not support multi-objective optimization. Is that note up-to-date?

I would benefit from being able to minimize action cost and then the makespan, in a HierarchicalProblem.

If I cannot use multiple metrics, is there any modeling work-around to being able to do that?

Best,
Nicola

[miquelramirez]

Dear Nicola,

one straightforward proposition is to consider the linear combination $w_1 f_1(x) + w_2 f_2(x)$, where $w_1, w_2$ are positive reals, and $x$ is an element of your feasible set, as a surrogate for the actual objective. By doing so you are actually dealing with a parametric function in two dimensions, one for each multiplier in the objective. Each optimal solution lies on the Pareto front... but you are "guessing" one such point, which may not quite be what the human operator of the planner may actually want.

So any planner that can optimize arbitrary linear functions should be useable. TAMER does optimize each of your functions but it is not clear to me what metric expressions are well supported.

You can find about the technique above in the book by Miettinen "Nonlinear Multiobjective Optimization", Springer, 1999. I can provide more detailed bib ref later.

EDIT: added mathematical property and explanation

[arbimo]

The Aries solver itself would support the solution of @miquelramirez but this is not exposed in the UP due to two limitations (on in the UP and one in the Aries integration):

• the makespan is not interpretable as a UP numeric expression and thus cannot appear in a (goal) expression
• there are limitations in the interpretation of numeric expressions by Aries' integration (multiplications in particular are not parsed as they are only supported by the underlying solver in specific contexts)

Note that these two limitations should be reasonably easy to address but I do not have a time frame to propose :/

For such a case of lexicographic optimization however, you could work around it in by:

1. solving a first problem that minimizes action costs
2. solving a second problem that minimizes makespan under the constraint that the actions costs is equal to its optimal value

Note that for this to work, you can express your action costs through a specific state variable. For the first step, you would minimizes its value in the final state. For the second, you would add a goal condition on its value.

[nicola-gigante]

Hi @arbimo, thanks!

The documentation of the Aries UP integration states that it supports only the three metrics I mentioned above, not the minimization of values at the final state. Is that note out-of-date and it can indeed minimize values at the final state? That would help me for a lot of other issues.

[miquelramirez]

Thanks for the notes on Aries, @arbimo. That is useful information and a reminder that UP interface != backend planner interface.

For such a case of lexicographic optimization however, you could work around it in by:

solving a first problem that minimizes action costs
solving a second problem that minimizes action costs, under the constraint that the actions costs is equal to its optimal value

That method is also known as the "$\epsilon$-constraints" method, discussed too in Miettinen's book

All the best,

Miquel.

[arbimo]

Well, this method is more general as it is meant to construct pareto-optimal solutions in the case where there is no hierarchisation between several objective functions (pareto optimization). In @nicola-gigante 's case however, makespan is only used as a tie-breaker among solutions with optimal action-costs (lexicographic optimization).

@nicola-gigante yes in this case the documentation is lagging a bit behind. I did not put it forward immediately as I wanted to have it battle-tested before publicizing it. I am now confident that is correct, modulo some limitation in the kind of expressions that would be supported, such as multiplications (in these cases however, the planner should give you a clear internal error).

[nicola-gigante]

@arbimo that's awesome news! I think I have all I need now. Thanks to @miquelramirez as well for the insights.

[arbimo]

Oh by the way. As noted by @miquelramirez's reference, Inequality or equality (for the action-cost constraint of step 2.) are equivalent in the problem formulation. However, equality constraints may help the solver converge faster by strengthening the internal constraint propagation (or not, one never knows for sure...)

[miquelramirez]

Hello again,

The precise reference to the book I mentioned above is

Kaisa Miettinen. Nonlinear multiobjective optimization. International series in operations research & management science , volume 12. 1998. Springer Science+Business Media.

I mentioned the method in Chapter 3, "A Posteriori Methods," section 3.1. Note that when the optimization problem is a Linear Program, doing "proper" search on the surrogate objective (what Miettinen calls an "a posterior" method) requires solving a linearly constrained quadratic problem. Miettinen attributes the origins of this method to these references, which may be easier to access but perhaps not aligned with contemporary theory and practice in optimization

Gass S., Saaty T., The Computational Algorithm for the Parametric Objective Function,
Naval Research Logistics Quarterly 2 (1955), 39-45.

Zadeh L., Optimality and Non-Scalar- Valued Performance Criteria,
IEEE Transactions on Automatic Control 8 (1963), 59-60.

There are ways to proceed with general planning problems that cannot be efficiently captured by linear constraints. However, this discussion would be off-topic for this forum.

Good hunting,

Miquel.