Error if Algorithm shouldn't be used on a problem type

[odow]

At minimum, the MIP ones when applied to continuous problems.

See the reviewer's comment.

[odow]

Reviewer's comment is that this goes on forever:

using JuMP, HiGHS
import MultiObjectiveAlgorithms as MOA
model = Model()
@variable(model, x1 >= 0)
@variable(model, 0 <= x2 <= 3)
@objective(model, Min, [3x1 + x2, -x1 - 2x2])
@constraint(model, 3x1 - x2 <= 6)
set_optimizer(model, () -> MOA.Optimizer(HiGHS.Optimizer))
set_attribute(model, MOA.Algorithm(), MOA.DominguezRios())
optimize!(model)

[odow]

I wrote in the review:

We are still debating whether a better approach is to throw an error, but detecting ``discreteness'' in JuMP is surprisingly nuanced. Moreover, KirlikSayin is in theory similarly restricted to discrete problems, but it finds a representative set on the same problem (related to your point below).

Maybe we just need to modify DominguezRios so that it returns a representative set even if the problem is continuous. I don't know what code changes that would entail though. I think KirlikSayin should work for LP problems; it effectively uses tolerance of 1.

[odow]

The other thing is what defines a MIP. Do we need just some binary/integer variables? Or all? Do we also need integer data? What about other types of integrality like SOS1/SOS2? Or what if only some variables are integer, but the constraints imply that the others are also integer?

[odow]

With logging, it's now apparent what's going on:

julia> using JuMP, HiGHS

julia> import MultiObjectiveAlgorithms as MOA

julia> model = Model()
A JuMP Model
├ solver: none
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

julia> @variable(model, x1 >= 0)
x1

julia> @variable(model, 0 <= x2 <= 3)
x2

julia> @objective(model, Min, [3x1 + x2, -x1 - 2x2])
2-element Vector{AffExpr}:
 3 x1 + x2
 -x1 - 2 x2

julia> @constraint(model, 3x1 - x2 <= 6)
3 x1 - x2 ≤ 6

julia> set_optimizer(model, () -> MOA.Optimizer(HiGHS.Optimizer))

julia> set_attribute(model, MOA.Algorithm(), MOA.DominguezRios())

julia> optimize!(model)
----------------------------------------------
        MultiObjectiveAlgorithms.jl
----------------------------------------------
Algorithm: DominguezRios
----------------------------------------------
solve #     Obj. 1       Obj. 2       Time    
----------------------------------------------
    1    0.00000e+00  0.00000e+00  5.78701e-02
    2    1.20000e+01 -9.00000e+00  5.84750e-02
    3    1.20000e+01 -9.00000e+00  5.88272e-02
    4    0.00000e+00  0.00000e+00  5.94151e-02
    5    3.62791e+00 -6.20930e+00  9.75890e-02
    6    7.29924e+00 -7.43308e+00  9.82380e-02
    7    1.89218e+00 -3.78437e+00  9.88381e-02
    8    8.81318e+00 -7.93773e+00  9.94220e-02
    9    1.23543e+00 -2.47086e+00  1.00002e-01
   10    9.63747e+00 -8.21249e+00  1.00563e-01
   11    5.58924e+00 -6.86308e+00  1.01106e-01
   12    2.61807e+00 -5.23615e+00  1.01689e-01
   13    7.82586e+00 -7.60862e+00  1.02230e-01
   14    9.75000e+00 -8.25000e+00  1.02773e-01
   15    8.91589e-01 -1.78318e+00  1.03352e-01
   16    9.75000e+00 -8.25000e+00  1.03888e-01
   17    2.25442e+00 -4.50883e+00  1.04463e-01
   18    9.75000e+00 -8.25000e+00  1.05003e-01
   19    4.80405e+00 -6.60135e+00  1.05549e-01
   20    9.75000e+00 -8.25000e+00  1.06088e-01
   21    9.01802e+00 -8.00601e+00  1.06616e-01
   22    9.75000e+00 -8.25000e+00  1.07166e-01
   23    7.50000e-01 -1.50000e+00  1.07750e-01
   24    9.75000e+00 -8.25000e+00  1.08290e-01
   25    4.37522e+00 -6.45841e+00  1.08832e-01
   26    9.75000e+00 -8.25000e+00  1.09373e-01
   27    7.50000e-01 -1.50000e+00  1.09950e-01
   28    9.75000e+00 -8.25000e+00  1.10489e-01
   29    7.50000e-01 -1.50000e+00  1.11072e-01
   30    9.75000e+00 -8.25000e+00  1.11613e-01
   31    7.50000e-01 -1.50000e+00  1.12193e-01
   32    9.75000e+00 -8.25000e+00  1.12732e-01
   33    7.50000e-01 -1.50000e+00  1.13308e-01
   34    9.75000e+00 -8.25000e+00  1.13845e-01
   35    7.50000e-01 -1.50000e+00  1.14423e-01
   36    9.75000e+00 -8.25000e+00  1.14962e-01
   37    7.50000e-01 -1.50000e+00  1.15539e-01

[kofgokhan]

KS and TV both use epsilon constraint scalarization. When they find a point they partition the solution space into region and use the upper vertex .-1 as the right hand side. The reason for that is that, yes, the data is integer as well so the objective values will be integer and .-1 is safe. So if the data is not integer, using .-1 may result in a representative set rather than the whole front.

If we solve an LP with KS or TV, we will get a representative set because the epsilon constraint scalarization will return a nondominated point indepedently of problem type.

So DominguezRios uses weighted tchebychev scalarization. It introduces objective weights depending on the region we are exploring w = scale ./ max.(1, B.u - yI. So even if we subtract 1 the objective gradient will not change. Instead, we can partition the search space using Y .- 1. When I do that, the algorithm terminates but this -1 may not work on every problem. Also, Unlike KS and TV, DominguezRios will not find integer points for LP this way (this should not be that important but it means for this problem DR will also not find the extreme point of the pareto front and Dichotomy, KS and TV all do).

Can we do something like this?:

variables = MOI.get(model.inner, MOI.ListOfVariableIndices())
integrality_constraints = MOI.get(
    model.inner, 
    MOI.ListOfConstraintIndices{MOI.VariableIndex, MOI.Integer}()
)
binary_constraints = MOI.get(
    model.inner, 
    MOI.ListOfConstraintIndices{MOI.VariableIndex, MOI.ZeroOne}()
)
integrality_constraint_functions = [MOI.get(model.inner, MOI.ConstraintFunction(), ci) 
    for ci in integrality_constraints]
binary_constraint_functions = [MOI.get(model.inner, MOI.ConstraintFunction(), ci) 
    for ci in binary_constraints]
if any((vi ∉ integrality_constraint_functions) && (vi ∉ binary_constraint_functions) 
    for vi in variables)
    error("All variables must be integer or binary.")
end

[kofgokhan]

Alterantively, I added somethings so we don't keep searching similar boxes:

B_prevs = Vector{_DominguezRiosBox}(undef, 3)
iter = 0
while any(!isempty(l) for l in L)
    iter += 1
    if (ret = _check_premature_termination(model, start_time)) !== nothing
        status = ret
        break
    end
    @info [length(Li) for Li in L]
    i, k = _select_next_box(L, k)
    B = L[k][i]
    if iter > n
        if (B_prevs[k].l ≈ B.l) && (B_prevs[k].u ≈ B.u)
            @info "B and B_prev are the same!"
            deleteat!(L[k], i)
            continue
        end
    end
    B_prevs[k] = B
    ...
end
...

[xgandibleux]

The information provided with MOA (article, documentation) on algorithms are clear and explicit.

In my opinion, the correct use of a given algorithm depends on and is the responsibility of the user. Of course, we could lock everything down... even the solver to be called. But I don't think that's what we should do, nor even that it's the right thing to do.

Indeed, it leaves open the possibility for a user to use an algorithm outside the general framework/assumptions for which it was designed if, for example, the specific problem they are dealing with allows it (thanks to e.g. a property—such as, for example, the total unimodularity of the constraint matrix—which could allow the correct use of an algorithm in a specific context).

[xgandibleux]

The log looks great and is useful for tracking the algorithm's activity.

However, a silent mode, like the one that exists for the MIP solver, specific to this tracing, would be appropriate in certain circumstances (for example, to avoid being penalized by the display time for algorithms calling MOA as a subroutine).

Can we add such an optional parameter (set to true by default) to enable/disable this tracing?

[xgandibleux]

The other thing is what defines a MIP. Do we need just some binary/integer variables? Or all? Do we also need integer data? What about other types of integrality like SOS1/SOS2? Or what if only some variables are integer, but the constraints imply that the others are also integer?

Interesting questions, which are somewhere related to the pre-processing.

Preprocessing in MOP has been discussed for a very long time (i.e. the detection/explotation of integrality for improving bounds known since the 90s in the two phase method or the shaving procedure for fixing variables) and remains an active area of investigations (e.g. Exact Objective Space Contraction for the Preprocessing of Multi-objective Integer Programs, https://arxiv.org/abs/2512.01535).

One could imagine go ahead in implementing pre-processing steps that, based on a JuMP model, identify information about the formulation and activate a MOA algorithm under specific conditions, making it more effective.

That is why I believe that, currently, there is no need to further restrict the conditions of applicability of the existing algorithms.

[odow]

Can we add such an optional parameter (set to true by default) to enable/disable this tracing?

It already respects JuMP.set_silent(model). The default is printing turned on.

[odow]

Alternatively, I added somethings so we don't keep searching similar boxes:

I think I'd prefer to do something like that. The cycling in objective space means we're not excluding already solved boxes.

[odow]

Can we do something like this?

Sure. But that's a pretty blunt tool. In theory the algorithm works for models like this, but detecting is hard:

model = Model()
@variable(model, x, Int)
@variable(model, y)
@constraint(model, y == 2 * x + 1)

I think instead of throwing an error we just make sure the algorithm is correct in the integer case and always has a finite termination in the LP case.

[kofgokhan]

What would you say to defining different logging schemes for different algorithms? For instance, for TV, KS and DR, we could also log the regions being searched in every iteration, chosen objective for the scalarization, etc. For sandwiching, we can keep track of the approximation error, objective gradient at iterations, etc.

[odow]

Open to more logging. I went with simple to start. We could have some more verbose debug logging

[odow]

I'm mindful that the basic logging should be simple. We want to communicate to users that something is happening, but not necessarily overload them with lots of information