Where should this repo live

[odow]

We're going to tag a release of MOI with multi-objective support soon (https://github.com/jump-dev/MathOptInterface.jl/pull/2090), and this repo contains a collection of solvers that are similar to the purpose of https://github.com/vOptSolver/vOptGeneric.jl.

There's no point duplicating work, so should we pick one of:

1. Move this repo to jump-dev/MOO.jl
2. Move this repo to jump-dev and rename to MultiObjectiveAlgorithms.jl (to be bikeshed)
3. Replace https://github.com/vOptSolver/vOptGeneric.jl with the contents of this package
4. Move this repo to vOptSolver and call it vOpt.jl

Thoughts @mlubin @blegat @joaquimg @xgandibleux?

[xgandibleux]

Since the first public release in 2017, vOptGeneric has been patched along the years to follow the versions of JuMP (and Julia). Definitively, the version designed by Oscar is younger (and then better from that perspective) and comes with the strong knowledge of MOI. At the user level, the functionalities discussed these last weeks for modeling a MOO with JuMP fit with the expectations of the community. For me, the package vOptGeneric has no reason to be continued, and option 1) or 2) are the directions to consider (transfert/rewrite the algorithms available in vOptGeneric in the fresh code).

However, I have several questions and remarks about the implementations of the 4 algorithms in MOO.jl

1) about epsilonConstraint algorithm; this implementation in MOO.jl is relevant for sampling the outcome set (as people working in approximations or in metaheuristics are doing), but it is not the common/usual usage done by the MOO/MCDM community. The epsilon-constraint method is awaited to deliver $Y_N$ the (exact) set of nondominated points (containing all nondominated points -not a sample-, and without weakly nondominated point).

According my understanding of the code, the results returned by the lines 47-57 (file epsilonconstraint) are in general weaky nondominated, which is not valid for an epsilon-constraint method (a filter has to be applied or the generation handles this case and delete the unexpected points). Also, the value epsilon for a IP problem is (basically) set to the value 1, i.e. it eliminates each new nondominated point found (see in vOptGeneric). This implementation in MOO seems not designed for handling such a value.

Suggestion: after being corrected to avoid any weakly non dominated points into the results returned, this code may be released but not named epsilon-constraint method, I suggest something as "samplingMethod" or simply "sampling" the outcome set.

2) In the hierarchical algorithm, the weights used (line 95) are unclear for me. Is it a kind of preference that you are trying to integrate here? I don't know how to understand it and which kind of nondominated point this algorithm returns. As far as I know, such a manner to compute is not common in the community.

Suggestion: while this is not fully clarified, I would suggest to wait/postpone the release of this algorithm.

3) in the lexicographic algorithm, according the usual definition the method have to consider all the permutations of the objectives (see in vOptGeneric), i.e. p=2 => (1 , 2) and (2 , 1) p=3 => (1 , 2 , 3) and the 5 others arrangements Is it done here?

Suggestion: to modify the implementation for corresponding to fit with the definition

4) I have to come back on the NISE method before to read the code; to do.

5) I have also some comments on the terms used in the implementation of MOO.jl :

5.1) Pareto solution is commonly used in the metaheuristic community (EMO), but almost not by the LP/IP/MIP community . Moreover it refers to the solution vector x, and not to the image y in the objective space. In the code, ParetoSolution is a structure with both x and y, whereas both are respectively defined by "efficient solution" for x and "nondominated point" for y. A structure packing the two should not be named "paretoSolution", simply "pareto" could be fine.

5.2) in the code, I see "utopia" whereas it is an "ideal point" (the optimal value objective by objective separately, right?). A "utopian point" (term commonly used) is a point dominating slightly the ideal point by an epsilon value. It is not the case here, right?

[odow]

1

My goal with this has been to knock out a few quick algorithms to demonstrate we can do things and that the solver -> MOI -> JuMP interface works okay.

Let me take a look at your code in vOptGeneric instead of making something up on the spot...

2

The algorithm is similar to the one used by Gurobi and CPLEX: https://www.gurobi.com/documentation/10.0.1/refman/multiple_objectives.html

It lets you mix and match a blended and lexicographic approach.

3

No. It just goes from 1 through N and returns a single solution. We could add an option to solve all permutations. But is that useful? I have been solving some problems recently where we used the multiobjective support in LocalSolver, and it was lexicographic in the sense that we really wanted objectives 1 through N solved in that order. A different order would give meaningless solutions.

5.1

PR #13 renames to SolutionPoint.

5.2

Fixed in #12

[odow]

According my understanding of the code, the results returned by the lines 47-57 (file epsilonconstraint) are in general weaky nondominated, which is not valid for an epsilon-constraint method

Hmm. I might need some more detail here. Lines 47-57 are:

https://github.com/odow/MOO.jl/blob/78f47daa513c9f2aa3a21050174a2d2068a9e424/src/algorithms/EpsilonConstraint.jl#L47-L57

This finds the two lexicographic solutions which should be non-dominated? It doesn't just solve objective 1, leaving objective 2 free.

Also, the value epsilon for a IP problem is (basically) set to the value 1, i.e. it eliminates each new nondominated point found (see in vOptGeneric). This implementation in MOO seems not designed for handling such a value.

Added in #14

[odow]

are the directions to consider (transfert/rewrite the algorithms available in vOptGeneric in the fresh code).

I've opened #15, #16, and #17 to track these.

[odow]

For me, the package vOptGeneric has no reason to be continued, and option 1) or 2)

Okay. I'll tentatively rename this to MultiObjectiveAlgorithms.jl https://github.com/odow/MOO.jl/pull/18, and then we can move it to jump-dev.

That'd also give us more control adding it to the JuMP documentation, which would let us better document multi-objective stuff and a solver which returns multiple solutions.

[odow]

I've moved this to jump-dev.

[odow]

Given the use in https://github.com/jump-dev/JuMP.jl/pull/3176, and the related tutorial https://jump.dev/JuMP.jl/previews/PR3176/tutorials/linear/multi_objective_knapsack/, I'm pretty happy with this.

I'll move forward with registering this package unless anyone has objections/suggestions for a better name?

[odow]

Started the registration process: https://github.com/JuliaRegistries/General/pull/77484. Waiting period is three days, so still time to change if anyone has a name request before then.

[odow]

Closing because this is now a registered package!