Add Lazy{S} set

[jd-lara]

Would it be possible to expose a generic MOI attribute to expose the solver attribute setting to add constraints lazily without being a callback. Gurobi has the GRB_INT_LAZY and Xpress has the XPRSloaddelayedrows that support lazy constraints natively.

The interfaces aren't the same for the solvers but it would be possible to use MOI to have a generic interface for solvers that support it.

[odow]

@jd-lara and I discussed this over the phone. Here's a summary:

The attribute

The way to set this with Gurobi is via Gurobi.ConstraintAttribute: https://github.com/jump-dev/Gurobi.jl?tab=readme-ov-file#accessing-gurobi-specific-attributes

Making this attribute generic in MOI is difficult because it's pretty specific to Gurobi.

Delayed rows

We could conceivably have an API like MOI.add_delayed_constraint which was either the usual add_constraint+ConstraintAttribute in Gurobi, or the XPRSloaddelayedrows in Xpress. Other solvers like CPLEX may have something similar.

Open-source solvers like HiGHS don't have this.

Callback

Our current recommended way to implement this would be via a lazy constraint callback: https://jump.dev/JuMP.jl/stable/manual/callbacks/#Lazy-constraints

The downside to this is that you need to significantly refactor your model building code.

MathOptDelayedRows.Optimizer

We could also consider building some sort of MOI layer that delayed adding rows to the inner optimiser, and did a solve-add-solve loop. This would let us fake solvers that didn't natively support lazy constraints.

The massive downside to this is that the solve loop would not restart from an existing branch-and-bound tree, so it's not likely to be peformant.

As an aside: I've wanted this in the LP space for a long time to help me manage cut pools in SDDP.jl; we currently just use a heuristic to decide which cuts to keep and add between resolves.

Summary

There's clearly a need for something like this, but it isn't standardised well enough across multiple solvers to have something generic in MOI.

Step 1 is for @jd-lara to prove that Gurobi are actually doing something clever under the hood with their lazy constraints and that the reported benefits can be replicated in a benchmark. He's going to work on this as a next step.

[senhalil]

Hey @jd-lara ! just stumbled upon this while looking for something to contribute.

Other solvers like CPLEX may have something similar.

@odow Cplex does indeed have a cpxxaddlazyconstraints method and it was useful back in early 2010s when I used it last (wow time flies by!). But I suspect it is still useful since its usefulness is application dependent -- as it reduces the LP size while incurring a small verification step for each integer solution candidate and then then the integer solution needs to fixed if it violates a constraint.

If JD's verification is positive, I would be happy to help -- realistically, MathOptDelayedRows.Optimizer is more than I can chew at the moment but I think I can implement a MOI.add_delayed_constraint interface.

[odow]

Perhaps I should clarify: even if this is a performance win, I'm not convinced we should do anything about it. MOI.add_delayed_constraint is going to make the MOI API much more complicated.

[odow]

I missed the obvious way to implement this: with a MOI.Lazy{S<:MOI.AbstractSet}.

Then solvers can declare that they support MOI.Lazy. There can be a trivial bridge from the MOI.Lazy constraint to the underlying constraint.

And we can make a JuMP extension so that

@constraint(model, 2x <= 1, Lazy())

lowers to 2x in Lazy(LessThan(1.0)

[odow]

I'm making progress at this. I think it's a nice design.

using Revise
using JuMP
import Gurobi
import HiGHS

###
### The MOI set
###

struct LazyScalarSet{S<:MOI.AbstractScalarSet} <: MOI.AbstractScalarSet
    set::S
end

function MOI.Utilities.supports_shift_constant(
    ::Type{LazyScalarSet{S}},
) where {S<:MOI.AbstractScalarSet}
    return MOI.Utilities.supports_shift_constant(S)
end

function MOI.Utilities.shift_constant(set::LazyScalarSet, constant)
    return LazyScalarSet(MOI.Utilities.shift_constant(set.set, constant))
end

###
### The fallback bridges
###

struct LazyScalarSetBridge{
    T,
    F<:MOI.AbstractScalarFunction,
    S<:MOI.AbstractScalarSet,
} <:
       MOI.Bridges.Constraint.SetMapBridge{T,S,LazyScalarSet{S},F,F}
    constraint::MOI.ConstraintIndex{F,S}
end

MOI.Bridges.map_function(::Type{<:LazyScalarSetBridge}, f) = f

MOI.Bridges.inverse_map_function(::Type{<:LazyScalarSetBridge}, f) = f

MOI.Bridges.adjoint_map_function(::Type{<:LazyScalarSetBridge}, f) = f

MOI.Bridges.inverse_adjoint_map_function(::Type{<:LazyScalarSetBridge}, f) = f

function MOI.Bridges.map_set(
    ::Type{LazyScalarSetBridge{T,F,S}},
    set::LazyScalarSet{S},
) where {T,F,S}
    return set.set
end

function MOI.Bridges.inverse_map_set(
    ::Type{LazyScalarSetBridge{T,F,S}},
    set::S,
) where {T,F,S}
    return LazyScalarSet(set)
end

function MOI.supports_constraint(
    ::Type{<:LazyScalarSetBridge},
    ::Type{<:MOI.AbstractScalarFunction},
    ::Type{<:LazyScalarSet},
)
    return true
end

function MOI.Bridges.Constraint.concrete_bridge_type(
    ::Type{<:LazyScalarSetBridge{T}},
    ::Type{F},
    ::Type{LazyScalarSet{S}},
) where {T,F<:MOI.AbstractScalarFunction,S<:MOI.AbstractScalarSet}
    return LazyScalarSetBridge{T,F,S}
end

###
### The JuMP Extension
###

struct Lazy end

Base.broadcastable(::Lazy) = Ref(Lazy())

function JuMP.build_constraint(
    error_fn::Function,
    f::AbstractJuMPScalar,
    s::MOI.AbstractScalarSet,
    ::Lazy,
)
    return JuMP.build_constraint(error_fn, f, LazyScalarSet(s))
end

function JuMP.model_convert(model::AbstractModel, set::LazyScalarSet)
    return LazyScalarSet(JuMP.model_convert(model, set.set))
end

###
### Gurobi.jl
###

function MOI.supports_constraint(
    model::Gurobi.Optimizer,
    ::Type{MOI.ScalarAffineFunction{Float64}},
    ::Type{LazyScalarSet{S}},
) where {
    S<:Union{
        MOI.GreaterThan{Float64},
        MOI.EqualTo{Float64},
        MOI.LessThan{Float64},
    },
}
    return true
end

function MOI.add_constraint(
    model::Gurobi.Optimizer,
    f::MOI.ScalarAffineFunction{Float64},
    s::LazyScalarSet{S},
) where {
    S<:Union{
        MOI.GreaterThan{Float64},
        MOI.EqualTo{Float64},
        MOI.LessThan{Float64},
    },
}
    ci = MOI.add_constraint(model, f, s.set)
    MOI.set(model, Gurobi.ConstraintAttribute("Lazy"), ci, 1)
    return MOI.ConstraintIndex{typeof(f),typeof(s)}(ci.value)
end

###
### An example
###

N = 100
model = Model(Gurobi.Optimizer)
add_bridge(model, LazyScalarSetBridge)
@variable(model, x[1:N] >= 0, Int)
w, c = abs.(sin.(1:N)), abs.(cos.(1:N))
@constraint(model, w' * x <= 0.1 * N)
@objective(model, Max, c' * x)
@constraint(model, x .<= 1, Lazy())
optimize!(model)
print_active_bridges(model)
set_optimizer(model, HiGHS.Optimizer)
optimize!(model)
print_active_bridges(model)

[jd-lara]

So the bridge just add the lazy constraints directly to the model if it isn't supported natively?

[odow]

Yip

[odow]

This would let us tap in to Gurobi's native API. We'd need to build a new MOI optimizer to handle the lazy constraints in a loop if we wanted that.

[odow]

And it doesn't handle your DC/AC think where the evaluator and the constraint are different.