Add support for vector-valued objectives

[odow]

Closes #2099

Overview

The issue #2099 discussed two approaches for implementing MO in JuMP.

1. Treat multicriteria as a vector of scalar objectives and a vector of scalar senses. This would let someone write [Min, Max], [f(x), g(x)]. The main reason for this approach is that it matches what users want to do.
2. Treat multicriteria as an optimization problem with a vector-valued objective function. Users could write only Min, f(x) where f(x) is a vector. The main reason for this approach is that it matches what MathOptInterface wants.

This PR implements option 2. The strongest reason in support of option 2 is that it requires very little code to implement, suggesting that it is a natural extension of MOI.

There are also solvers, like Gurobi, that support 2, but not 1. That is, they have a single objective sense but support multiple objectives: https://www.gurobi.com/documentation/10.0/refman/c_setobjectiven.html. (You could work-around that by setting the weight of the Max objective to -1 instead of 1, but that's getting a bit finicky.)

The biggest downside is that it doesn't overcome the Min-Max issue; but I think we can work around this with user-facing cosmetic tooling in JuMP; solvers would be forced to accept a single sense.

Documentation

See https://jump.dev/JuMP.jl/previews/PR3176/manual/objective/#Set-a-vector-valued-objective

Testing it out

The MOI PR is:

• Add support for vector-valued objective functions MathOptInterface.jl#2070

The supported solvers are:

• https://github.com/odow/MOO.jl (Follow https://github.com/odow/MOO.jl#installation)
• Add support for vector-valued objective functions Gurobi.jl#497 (] add Gurobi#od/vector-optimization)

Examples to follow are:

• https://github.com/odow/MOO.jl/blob/master/test/mo_models.jl

but this explains the basic syntax. Currently you need add_bridges = false because of an issue in MOI.

function example_jump_bolp_1_min_max(f)
    model = Model(f; add_bridges = false)
    set_silent(model)
    @variable(model, x >= 0.0)
    @variable(model, y >= 0.25)
    @constraint(model, x + y >= 1.0)
    @constraint(model, 0.5 * x + y >= 0.75)
    @expression(model, obj1, 2 * x + y)
    @expression(model, obj2, -x - 3 * y)
    # We want
    #   min obj1
    #   max obj2
    # But you must pick a single sense.
    @objective(model, Min, [obj1, -obj2])
    optimize!(model)
    @test termination_status(model) == OPTIMAL
    @test result_count(model) == 3
    X = [[0.0, 1.0], [0.5, 0.5], [1.0, 0.25]]
    Y = [[1.0, 3.0], [1.5, 2.0], [2.25, 1.75]]
    for i in 1:3
        @test primal_status(model; result = i) == MOI.FEASIBLE_POINT
        @test dual_status(model; result = i) == MOI.NO_SOLUTION
        @test objective_value(model; result = i) == Y[i]
        @test value(x; result = i) == X[i][1]
        @test value(y; result = i) == X[i][2]
    end
    @test objective_bound(model) == [1.0, 1.75]
    return
end

[codecov]

Codecov Report

Base: 98.06% // Head: 98.07% // Increases project coverage by +0.00% 🎉

Coverage data is based on head (c664da7) compared to base (451740a).
Patch coverage: 100.00% of modified lines in pull request are covered.

Additional details and impacted files

@@           Coverage Diff           @@
##           master    #3176   +/-   ##
=======================================
  Coverage   98.06%   98.07%           
=======================================
  Files          34       34           
  Lines        4597     4612   +15     
=======================================
+ Hits         4508     4523   +15     
  Misses         89       89           

Impacted Files	Coverage Δ
src/objective.jl	96.66% <100.00%> (+0.58%)	⬆️
src/solution_summary.jl	97.61% <100.00%> (+0.11%)	⬆️
src/lp_sensitivity2.jl	97.79% <0.00%> (+0.02%)	⬆️

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

☔ View full report at Codecov.
📢 Do you have feedback about the report comment? Let us know in this issue.

[odow]

Picking on the main sticking points from #2099

we have chosen to handle the objectives separately. Adding an index which denote a specific objective as suggested by @odow is our preferred option because we would like in a near future to remove one objective without redefining all the model.

You can re-define the objective without rebuilding the model. This is working with MOO.jl

model = Model()
@variable(model, x >= 0.0)
@variable(model, y >= 0.25)
@constraint(model, x + y >= 1.0)
@constraint(model, 0.5 * x + y >= 0.75)
@expression(model, obj1, 2 * x + y)
@expression(model, obj2, -x - 3 * y)
# Optimize two objectives
@objective(model, Min, [obj1, -obj2])
optimize!(model)
# ... do something with solution
# Drop objective 2
@objective(model, Min, [obj1])
optimize!(model)
# ... do something with solution

a discussion about how to pass the resolution method to invoke (and possibly the required parameters) is needed.

These are just normal solver parameters

using JuMP
import HiGHS, MOO
model = JuMP.Model(() -> MOO.Optimizer(HiGHS.Optimizer))
set_optimizer_attribute(model, "algorithm", MOO.NISE())

a discussion about how to retrieve Y_N and X_E is needed as soon as the problem is not discrete. Indeed, for the MO-MILP case, Y_N may be composed of points, segments (open or closed), facets (full or not; open or closed). We have not yet stated about a protocol in the vOpt team. One option may be to return each object separately, with its proprieties, and a description of their adjacency relations.

This is tricky. For now, value(x; result = i) and objective_value(model, ; result = i) return points. Presumably, we'd need some solver-specific attributes here for the facets. For example:

Y_N = MOI.get(model, vOpt.EfficientFacets())

In writing @objective(model, Max, [dot(x, p1), dot(x, p2)]), the user cannot
(1) blend functions to minimize and to maximize in the model, and

This is still a problem.

(2) point out a function to delete without rebuilding all the model.

You can set a new objective, but we can't say "delete the 2nd objective from this vector." Would solvers benefit from the ability to do this?

[odow]

Before merging, I'd like to tag https://github.com/jump-dev/MultiObjectiveAlgorithms.jl as a public package and add a tutorial to the documentation. This would let us document both vector-valued objectives, and solvers which support multiple solutions.

[odow]

I've added a tutorial using MultiObjectiveAlgorithms. I think it's pretty cool. The ease to which we can solve multi-objective problems is going to be a nice boost to the popularity of JuMP.

I'll post a link here once CI finishes.

[odow]

Here's the tutorial: https://jump.dev/JuMP.jl/previews/PR3176/tutorials/linear/multi_objective_knapsack

[odow]

@xgandibleux: I've updated the tutorial to use vectors instead of the Item struct I had before:
https://jump.dev/JuMP.jl/previews/PR3176/tutorials/linear/multi_objective_knapsack/#Data

[xgandibleux]

Great!

[odow]

After 3+ years (#2099), this is finally ready to merge!

[blegat]

What is an "ideal point" ? Is this a technical term from the multi-objective field ?

[odow]

Yes. See https://en.wikipedia.org/wiki/Multi-objective_optimization ("ideal objective vector").

It's also plotted in the tutorial:

[blegat]

Ok, maybe write it in italic to signify its the first occurence of this technical word and maybe add a href to the wikipedia page

[odow]

Added italics. I don't think the href is useful. We don't link to other technical terms, and the docstring includes a that is, ... comment in non-jargon.

[xgandibleux]

Ideed, Ideal point is a common reference point in MOO, and I agree with Oscar, extra explanations are not required here.