Bridges

abstract type AbstractBridge end

An abstract type representing a bridged constraint or variable in a MOI.Bridges.AbstractBridgeOptimizer.

All bridges must implement:

• added_constrained_variable_types
• added_constraint_types
• MOI.get(::AbstractBridge, ::MOI.NumberOfVariables)
• MOI.get(::AbstractBridge, ::MOI.ListOfVariableIndices)
• MOI.get(::AbstractBridge, ::MOI.NumberOfConstraints)
• MOI.get(::AbstractBridge, ::MOI.ListOfConstraintIndices)

Subtypes of AbstractBridge may have additional requirements. Consult their docstrings for details.

In addition, all subtypes may optionally implement the following constraint attributes with the bridge in place of the constraint index:

• MOI.ConstraintDual
• MOI.ConstraintPrimal

added_constrained_variable_types(
    BT::Type{<:AbstractBridge},
)::Vector{Tuple{Type}}

Return a list of the types of constrained variables that bridges of concrete type BT add.

Implementation notes

• This method depends only on the type of the bridge, not the runtime value. If the bridge may add a constrained variable, the type must be included in the return vector.
• If the bridge adds a free variable via MOI.add_variable or MOI.add_variables, the return vector must include (MOI.Reals,).

Example

julia> MOI.Bridges.added_constrained_variable_types(
           MOI.Bridges.Variable.NonposToNonnegBridge{Float64},
       )
1-element Vector{Tuple{Type}}:
 (MathOptInterface.Nonnegatives,)

added_constraint_types(
    BT::Type{<:AbstractBridge},
)::Vector{Tuple{Type,Type}}

Return a list of the types of constraints that bridges of concrete type BT add.

Implementation notes

• This method depends only on the type of the bridge, not the runtime value. If the bridge may add a constraint, the type must be included in the return vector.

Example

julia> MOI.Bridges.added_constraint_types(
           MOI.Bridges.Constraint.ZeroOneBridge{Float64},
       )
2-element Vector{Tuple{Type, Type}}:
 (MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.Interval{Float64})
 (MathOptInterface.VariableIndex, MathOptInterface.Integer)

MOI.get(b::AbstractBridge, ::MOI.NumberOfVariables)::Int64

Return the number of variables created by the bridge b in the model.

See also MOI.NumberOfConstraints.

Implementation notes

• There is a default fallback, so you need only implement this if the bridge adds new variables.

MOI.get(b::AbstractBridge, ::MOI.ListOfVariableIndices)

Return the list of variables created by the bridge b.

See also MOI.ListOfVariableIndices.

Implementation notes

• There is a default fallback, so you need only implement this if the bridge adds new variables.

MOI.get(b::AbstractBridge, ::MOI.NumberOfConstraints{F,S})::Int64 where {F,S}

Return the number of constraints of the type F-in-S created by the bridge b.

See also MOI.NumberOfConstraints.

Implementation notes

• There is a default fallback, so you need only implement this for the constraint types returned by added_constraint_types.

MOI.get(b::AbstractBridge, ::MOI.ListOfConstraintIndices{F,S}) where {F,S}

Return a Vector{ConstraintIndex{F,S}} with indices of all constraints of type F-in-S created by the bride b.

See also MOI.ListOfConstraintIndices.

Implementation notes

• There is a default fallback, so you need only implement this for the constraint types returned by added_constraint_types.

needs_final_touch(bridge::AbstractBridge)::Bool

Return whether final_touch is implemented by bridge.

final_touch(bridge::AbstractBridge, model::MOI.ModelLike)::Nothing

A function that is called immediately prior to MOI.optimize! to allow bridges to modify their reformulations with respect to other variables and constraints in model.

For example, if the correctness of bridge depends on the bounds of a variable or the fact that variables are integer, then the bridge can implement final_touch to check assumptions immediately before a call to MOI.optimize!.

If you implement this method, you must also implement needs_final_touch.

bridging_cost(b::AbstractBridgeOptimizer, S::Type{<:MOI.AbstractSet}})

Return the cost of bridging variables constrained in S on creation, is_bridged(b, S) is assumed to be true.

bridging_cost(
    b::AbstractBridgeOptimizer,
    F::Type{<:MOI.AbstractFunction},
    S::Type{<:MOI.AbstractSet},
)

Return the cost of bridging F-in-S constraints.

is_bridged(b, S) is assumed to be true.

runtests(
    Bridge::Type{<:AbstractBridge},
    input_fn::Function,
    output_fn::Function;
    variable_start = 1.2,
    constraint_start = 1.2,
    eltype = Float64,
    cannot_unbridge::Bool = false,
)

Run a series of tests that check the correctness of Bridge.

input_fn and output_fn are functions such that input_fn(model) and output_fn(model) load the corresponding model into model.

Set cannot_unbridge to true if the bridge transformation is not invertible. If Bridge is a variable bridge this allows Variable.unbridged_map to returns nothing so that the tests allow errors that can be raised due to this. If Bridge is a constraint bridge this allows the getter of MOI.ConstraintFunction and MOI.ConstraintPrimalStart to throw MOI.GetAttributeNotAllowed.

Example

julia> MOI.Bridges.runtests(
           MOI.Bridges.Constraint.ZeroOneBridge,
           model -> MOI.add_constrained_variable(model, MOI.ZeroOne()),
           model -> begin
               x, _ = MOI.add_constrained_variable(model, MOI.Integer())
               MOI.add_constraint(model, 1.0 * x, MOI.Interval(0.0, 1.0))
           end,
       )
Test Summary:    | Pass  Total  Time
Bridges.runtests |   32     32  0.8s

runtests(
    Bridge::Type{<:AbstractBridge},
    input::String,
    output::String;
    variable_start = 1.2,
    constraint_start = 1.2,
    eltype = Float64,
)

Run a series of tests that check the correctness of Bridge.

input and output are models in the style of MOI.Utilities.loadfromstring!.

Example

julia> MOI.Bridges.runtests(
           MOI.Bridges.Constraint.ZeroOneBridge,
           """
           variables: x
           x in ZeroOne()
           """,
           """
           variables: x
           x in Integer()
           1.0 * x in Interval(0.0, 1.0)
           """,
       )
Test Summary:    | Pass  Total  Time
Bridges.runtests |   32     32  0.0s

abstract type AbstractBridge <: MOI.Bridges.AbstractType

Subtype of MOI.Bridges.AbstractBridge for constraint bridges.

In addition to the required implementation described in MOI.Bridges.AbstractBridge, subtypes of AbstractBridge must additionally implement:

• MOI.supports_constraint(::Type{<:AbstractBridge}, ::Type{<:MOI.AbstractFunction}, ::Type{<:MOI.AbstractSet})
• concrete_bridge_type
• bridge_constraint

SingleBridgeOptimizer{BT<:AbstractBridge}(model::MOI.ModelLike)

Return AbstractBridgeOptimizer that always bridges any objective function supported by the bridge BT.

This is in contrast with the MOI.Bridges.LazyBridgeOptimizer, which only bridges the objective function if it is supported by the bridge BT and unsupported by model.

Example

julia> struct MyNewBridge{T} <: MOI.Bridges.Constraint.AbstractBridge end

julia> bridge = MOI.Bridges.Constraint.SingleBridgeOptimizer{MyNewBridge{Float64}}(
           MOI.Utilities.Model{Float64}(),
       )
MOIB.Constraint.SingleBridgeOptimizer{MyNewBridge{Float64}, MOIU.Model{Float64}}
├ ObjectiveSense: FEASIBILITY_SENSE
├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
├ NumberOfVariables: 0
└ NumberOfConstraints: 0

Implementation notes

All bridges should simplify the creation of SingleBridgeOptimizers by defining a constant that wraps the bridge in a SingleBridgeOptimizer.

julia> const MyNewBridgeModel{T,OT<:MOI.ModelLike} =
           MOI.Bridges.Constraint.SingleBridgeOptimizer{MyNewBridge{T},OT};

This enables users to create bridged models as follows:

julia> MyNewBridgeModel{Float64}(MOI.Utilities.Model{Float64}());

MOI.supports_constraint(
    BT::Type{<:AbstractBridge},
    F::Type{<:MOI.AbstractFunction},
    S::Type{<:MOI.AbstractSet},
)::Bool

Return a Bool indicating whether the bridges of type BT support bridging F-in-S constraints.

Implementation notes

• This method depends only on the type of the inputs, not the runtime values.
• There is a default fallback, so you need only implement this method for constraint types that the bridge implements.

concrete_bridge_type(
    BT::Type{<:AbstractBridge},
    F::Type{<:MOI.AbstractFunction},
    S::Type{<:MOI.AbstractSet}
)::Type

Return the concrete type of the bridge supporting F-in-S constraints.

This function can only be called if MOI.supports_constraint(BT, F, S) is true.

Example

The SplitIntervalBridge bridges a MOI.VariableIndex-in-MOI.Interval constraint into a MOI.VariableIndex-in-MOI.GreaterThan and a MOI.VariableIndex-in-MOI.LessThan constraint.

julia> MOI.Bridges.Constraint.concrete_bridge_type(
           MOI.Bridges.Constraint.SplitIntervalBridge{Float64},
           MOI.VariableIndex,
           MOI.Interval{Float64},
       )
MathOptInterface.Bridges.Constraint.SplitIntervalBridge{Float64, MathOptInterface.VariableIndex, MathOptInterface.Interval{Float64}, MathOptInterface.GreaterThan{Float64}, MathOptInterface.LessThan{Float64}}

bridge_constraint(
    BT::Type{<:AbstractBridge},
    model::MOI.ModelLike,
    func::AbstractFunction,
    set::MOI.AbstractSet,
)::BT

Bridge the constraint func-in-set using bridge BT to model and returns a bridge object of type BT.

Implementation notes

• The bridge type BT should be a concrete type, that is, all the type parameters of the bridge must be set.

add_all_bridges(model, ::Type{T}) where {T}

Add all bridges defined in the Bridges.Constraint submodule to model.

The coefficient type used is T.

conversion_cost(
    F::Type{<:MOI.AbstractFunction},
    G::Type{<:MOI.AbstractFunction},
)::Float64

Return a Float64 returning the cost of converting any function of type G to a function of type F with convert.

This cost is used to compute MOI.Bridges.bridging_cost.

The default cost is Inf, which means that MOI.Bridges.Constraint.FunctionConversionBridge should not attempt the conversion.

abstract type AbstractBridge <: MOI.Bridges.AbstractBridge end

Subtype of MOI.Bridges.AbstractBridge for objective bridges.

In addition to the required implementation described in MOI.Bridges.AbstractBridge, subtypes of AbstractBridge must additionally implement:

• supports_objective_function
• concrete_bridge_type
• bridge_objective
• MOI.Bridges.set_objective_function_type

SingleBridgeOptimizer{BT<:AbstractBridge}(model::MOI.ModelLike)

Return AbstractBridgeOptimizer that always bridges any objective function supported by the bridge BT.

This is in contrast with the MOI.Bridges.LazyBridgeOptimizer, which only bridges the objective function if it is supported by the bridge BT and unsupported by model.

Example

julia> struct MyNewBridge{T} <: MOI.Bridges.Objective.AbstractBridge end

julia> bridge = MOI.Bridges.Objective.SingleBridgeOptimizer{MyNewBridge{Float64}}(
           MOI.Utilities.Model{Float64}(),
       );

Implementation notes

All bridges should simplify the creation of SingleBridgeOptimizers by defining a constant that wraps the bridge in a SingleBridgeOptimizer.

julia> const MyNewBridgeModel{T,OT<:MOI.ModelLike} =
           MOI.Bridges.Objective.SingleBridgeOptimizer{MyNewBridge{T},OT};

This enables users to create bridged models as follows:

julia> MyNewBridgeModel{Float64}(MOI.Utilities.Model{Float64}());

supports_objective_function(
    BT::Type{<:MOI.Bridges.Objective.AbstractBridge},
    F::Type{<:MOI.AbstractFunction},
)::Bool

Return a Bool indicating whether the bridges of type BT support bridging objective functions of type F.

Implementation notes

• This method depends only on the type of the inputs, not the runtime values.
• There is a default fallback, so you need only implement this method For objective functions that the bridge implements.

set_objective_function_type(
    BT::Type{<:Objective.AbstractBridge},
)::Type{<:MOI.AbstractFunction}

Return the type of objective function that bridges of concrete type BT set.

Implementation notes

• This method depends only on the type of the bridge, not the runtime value.

Example

julia> MOI.Bridges.set_objective_function_type(
           MOI.Bridges.Objective.FunctionizeBridge{Float64},
       )
MathOptInterface.ScalarAffineFunction{Float64}

concrete_bridge_type(
    BT::Type{<:MOI.Bridges.Objective.AbstractBridge},
    F::Type{<:MOI.AbstractFunction},
)::Type

Return the concrete type of the bridge supporting objective functions of type F.

This function can only be called if MOI.supports_objective_function(BT, F) is true.

bridge_objective(
    BT::Type{<:MOI.Bridges.Objective.AbstractBridge},
    model::MOI.ModelLike,
    func::MOI.AbstractFunction,
)::BT

Bridge the objective function func using bridge BT to model and returns a bridge object of type BT.

Implementation notes

• The bridge type BT must be a concrete type, that is, all the type parameters of the bridge must be set.

add_all_bridges(model, ::Type{T}) where {T}

Add all bridges defined in the Bridges.Objective submodule to model.

The coefficient type used is T.

abstract type AbstractBridge <: MOI.Bridges.AbstractBridge end

Subtype of MOI.Bridges.AbstractBridge for variable bridges.

In addition to the required implementation described in MOI.Bridges.AbstractBridge, subtypes of AbstractBridge must additionally implement:

• supports_constrained_variable
• concrete_bridge_type
• bridge_constrained_variable

SingleBridgeOptimizer{BT<:AbstractBridge}(model::MOI.ModelLike)

Return MOI.Bridges.AbstractBridgeOptimizer that always bridges any variables constrained on creation supported by the bridge BT.

This is in contrast with the MOI.Bridges.LazyBridgeOptimizer, which only bridges the variables constrained on creation if they are supported by the bridge BT and unsupported by model.

Example

julia> struct MyNewBridge{T} <: MOI.Bridges.Variable.AbstractBridge end

julia> bridge = MOI.Bridges.Variable.SingleBridgeOptimizer{MyNewBridge{Float64}}(
           MOI.Utilities.Model{Float64}(),
       );

Implementation notes

All bridges should simplify the creation of SingleBridgeOptimizers by defining a constant that wraps the bridge in a SingleBridgeOptimizer.

julia> const MyNewBridgeModel{T,OT<:MOI.ModelLike} =
           MOI.Bridges.Variable.SingleBridgeOptimizer{MyNewBridge{T},OT};

This enables users to create bridged models as follows:

julia> MyNewBridgeModel{Float64}(MOI.Utilities.Model{Float64}());

supports_constrained_variable(
    BT::Type{<:AbstractBridge},
    S::Type{<:MOI.AbstractSet},
)::Bool

Return a Bool indicating whether the bridges of type BT support bridging constrained variables in S. That is, it returns true if the bridge of type BT converts constrained variables of type S into a form supported by the solver.

Implementation notes

• This method depends only on the type of the bridge and set, not the runtime values.
• There is a default fallback, so you need only implement this method for sets that the bridge implements.

Example

julia> MOI.Bridges.Variable.supports_constrained_variable(
           MOI.Bridges.Variable.NonposToNonnegBridge{Float64},
           MOI.Nonpositives,
       )
true

julia> MOI.Bridges.Variable.supports_constrained_variable(
           MOI.Bridges.Variable.NonposToNonnegBridge{Float64},
           MOI.Nonnegatives,
       )
false

concrete_bridge_type(
    BT::Type{<:AbstractBridge},
    S::Type{<:MOI.AbstractSet},
)::Type

Return the concrete type of the bridge supporting variables in S constraints.

This function can only be called if MOI.supports_constrained_variable(BT, S) is true.

Example

As a variable in MOI.GreaterThan is bridged into variables in MOI.Nonnegatives by the VectorizeBridge:

julia> MOI.Bridges.Variable.concrete_bridge_type(
           MOI.Bridges.Variable.VectorizeBridge{Float64},
           MOI.GreaterThan{Float64},
       )
MathOptInterface.Bridges.Variable.VectorizeBridge{Float64, MathOptInterface.Nonnegatives}

bridge_constrained_variable(
    BT::Type{<:AbstractBridge},
    model::MOI.ModelLike,
    set::MOI.AbstractSet,
)::BT

Bridge the constrained variable in set using bridge BT to model and returns a bridge object of type BT.

Implementation notes

• The bridge type BT must be a concrete type, that is, all the type parameters of the bridge must be set.

add_all_bridges(model, ::Type{T}) where {T}

Add all bridges defined in the Bridges.Variable submodule to model.

The coefficient type used is T.

unbridged_map(
   bridge::MOI.Bridges.Variable.AbstractBridge,
    vi::MOI.VariableIndex,
)

For a bridged variable in a scalar set, return a tuple of pairs mapping the variables created by the bridge to an affine expression in terms of the bridged variable vi.

unbridged_map(
    bridge::MOI.Bridges.Variable.AbstractBridge,
    vis::Vector{MOI.VariableIndex},
)

For a bridged variable in a vector set, return a tuple of pairs mapping the variables created by the bridge to an affine expression in terms of the bridged variable vis. If this method is not implemented, it falls back to calling the following method for every variable of vis.

unbridged_map(
    bridge::MOI.Bridges.Variable.AbstractBridge,
    vi::MOI.VariableIndex,
    i::MOI.Bridges.IndexInVector,
)

For a bridged variable in a vector set, return a tuple of pairs mapping the variables created by the bridge to an affine expression in terms of the bridged variable vi corresponding to the ith variable of the vector.

If there is no way to recover the expression in terms of the bridged variable(s) vi(s), return nothing. See ZerosBridge for an example of bridge returning nothing.

abstract type AbstractBridgeOptimizer <: MOI.AbstractOptimizer end

An abstract type that implements generic functions for bridges.

Implementation notes

By convention, the inner optimizer should be stored in a model field. If not, the optimizer must implement MOI.optimize!.

bridged_variable_function(
    b::AbstractBridgeOptimizer,
    vi::MOI.VariableIndex,
)

Return a MOI.AbstractScalarFunction of variables of b.model that equals vi. That is, if the variable vi is bridged, it returns its expression in terms of the variables of b.model. Otherwise, it returns vi.

unbridged_variable_function(
    b::AbstractBridgeOptimizer,
    vi::MOI.VariableIndex,
)

Return a MOI.AbstractScalarFunction of variables of b that equals vi. That is, if the variable vi is an internal variable of b.model created by a bridge but not visible to the user, it returns its expression in terms of the variables of bridged variables. Otherwise, it returns vi.

bridged_function(b::AbstractBridgeOptimizer, value)::typeof(value)

Substitute any bridged MOI.VariableIndex in value by an equivalent expression in terms of variables of b.model.

supports_constraint_bridges(b::AbstractBridgeOptimizer)::Bool

Return a Bool indicating if b supports MOI.Bridges.Constraint.AbstractBridge.

recursive_model(b::AbstractBridgeOptimizer)

If a variable, constraint, or objective is bridged, return the context of the inner variables. For most optimizers, this should be b.model.

struct FirstBridge <: MOI.AbstractConstraintAttribute end

Returns the first bridge used to bridge the constraint.

LazyBridgeOptimizer(model::MOI.ModelLike)

The LazyBridgeOptimizer is a bridge optimizer that supports multiple bridges, and only bridges things which are not supported by the internal model.

Internally, the LazyBridgeOptimizer solves a shortest hyper-path problem to determine which bridges to use.

In general, you should use full_bridge_optimizer instead of this constructor because full_bridge_optimizer automatically adds a large number of supported bridges.

See also: add_bridge, remove_bridge, has_bridge and full_bridge_optimizer.

Example

julia> model = MOI.Bridges.LazyBridgeOptimizer(MOI.Utilities.Model{Float64}());

julia> MOI.Bridges.add_bridge(model, MOI.Bridges.Variable.FreeBridge{Float64})

julia> MOI.Bridges.has_bridge(model, MOI.Bridges.Variable.FreeBridge{Float64})
true

full_bridge_optimizer(model::MOI.ModelLike, ::Type{T}) where {T}

Returns a LazyBridgeOptimizer bridging model for every bridge defined in this package (see below for the few exceptions) and for the coefficient type T, as well as the bridges in the list returned by the ListOfNonstandardBridges attribute.

Example

julia> model = MOI.Utilities.Model{Float64}();

julia> bridged_model = MOI.Bridges.full_bridge_optimizer(model, Float64);

Exceptions

The following bridges are not added by full_bridge_optimizer, except if they are in the list returned by the ListOfNonstandardBridges attribute:

• Constraint.SOCtoNonConvexQuadBridge
• Constraint.RSOCtoNonConvexQuadBridge](@ref)
• Constraint.SOCtoPSDBridge
• If T is not a subtype of AbstractFloat, subtypes of Constraint.AbstractToIntervalBridge
  • Constraint.GreaterToIntervalBridge
  • Constraint.LessToIntervalBridge)

See the docstring of the each bridge for the reason they are not added.

ListOfNonstandardBridges{T}() <: MOI.AbstractOptimizerAttribute

Any optimizer can be wrapped in a LazyBridgeOptimizer using full_bridge_optimizer. However, by default LazyBridgeOptimizer uses a limited set of bridges that are:

1. implemented in MOI.Bridges
2. generally applicable for all optimizers.

For some optimizers however, it is useful to add additional bridges, such as those that are implemented in external packages (for example, within the solver package itself) or only apply in certain circumstances (for example, Constraint.SOCtoNonConvexQuadBridge).

Such optimizers should implement the ListOfNonstandardBridges attribute to return a vector of bridge types that are added by full_bridge_optimizer in addition to the list of default bridges.

Note that optimizers implementing ListOfNonstandardBridges may require package-specific functions or sets to be used if the non-standard bridges are not added. Therefore, you are recommended to use model = MOI.instantiate(Package.Optimizer; with_bridge_type = T) instead of model = MOI.instantiate(Package.Optimizer). See MOI.instantiate.

Example

An optimizer using a non-default bridge in MOI.Bridges

Solvers supporting MOI.ScalarQuadraticFunction can support MOI.SecondOrderCone and MOI.RotatedSecondOrderCone by defining:

function MOI.get(::MyQuadraticOptimizer, ::ListOfNonstandardBridges{Float64})
    return Type[
        MOI.Bridges.Constraint.SOCtoNonConvexQuadBridge{Float64},
        MOI.Bridges.Constraint.RSOCtoNonConvexQuadBridge{Float64},
    ]
end

An optimizer defining an internal bridge

Suppose an optimizer can exploit specific structure of a constraint, for example, it can exploit the structure of the matrix A in the linear system of equations A * x = b.

The optimizer can define the function:

struct MatrixAffineFunction{T} <: MOI.AbstractVectorFunction
    A::SomeStructuredMatrixType{T}
    b::Vector{T}
end

and then a bridge

struct MatrixAffineFunctionBridge{T} <: MOI.Constraint.AbstractBridge
    # ...
end
# ...

from VectorAffineFunction{T} to the MatrixAffineFunction. Finally, it defines:

function MOI.get(::Optimizer{T}, ::ListOfNonstandardBridges{T}) where {T}
    return Type[MatrixAffineFunctionBridge{T}]
end

add_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})

Enable the use of the bridges of type BT by b.

remove_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})

Disable the use of the bridges of type BT by b.

has_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})

Return a Bool indicating whether the bridges of type BT are used by b.

print_active_bridges([io::IO=stdout,] b::MOI.Bridges.LazyBridgeOptimizer)

Print the set of bridges that are active in the model b.

print_active_bridges(
    [io::IO=stdout,]
    b::MOI.Bridges.LazyBridgeOptimizer,
    F::Type{<:MOI.AbstractFunction}
)

Print the set of bridges required for an objective function of type F.

print_active_bridges(
    [io::IO=stdout,]
    b::MOI.Bridges.LazyBridgeOptimizer,
    F::Type{<:MOI.AbstractFunction},
    S::Type{<:MOI.AbstractSet},
)

Print the set of bridges required for a constraint of type F-in-S.

print_active_bridges(
    [io::IO=stdout,]
    b::MOI.Bridges.LazyBridgeOptimizer,
    S::Type{<:MOI.AbstractSet}
)

Print the set of bridges required for a variable constrained to set S.

print_graph([io::IO = stdout,] b::LazyBridgeOptimizer)

Print the hyper-graph containing all variable, constraint, and objective types that could be obtained by bridging the variables, constraints, and objectives that are present in the model by all the bridges added to b.

Each node in the hyper-graph corresponds to a variable, constraint, or objective type.

• Variable nodes are indicated by [ ]
• Constraint nodes are indicated by ( )
• Objective nodes are indicated by | |

The number inside each pair of brackets is an index of the node in the hyper-graph.

Note that this hyper-graph is the full list of possible transformations. When the bridged model is created, we select the shortest hyper-path from this graph, so many nodes may be un-used.

To see which nodes are used, call print_active_bridges.

For more information, see Legat, B., Dowson, O., Garcia, J., and Lubin, M. (2020). "MathOptInterface: a data structure for mathematical optimization problems." URL

debug_supports_constraint(
    b::LazyBridgeOptimizer,
    F::Type{<:MOI.AbstractFunction},
    S::Type{<:MOI.AbstractSet};
    io::IO = Base.stdout,
)

Prints to io explanations for the value of MOI.supports_constraint with the same arguments.

debug_supports(
    b::LazyBridgeOptimizer,
    ::MOI.ObjectiveFunction{F};
    io::IO = Base.stdout,
) where F

Prints to io explanations for the value of MOI.supports with the same arguments.

struct MapNotInvertible <: Exception
    message::String
end

An error thrown by inverse_map_function or inverse_adjoint_map_function indicating that the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge is not invertible.

map_set(bridge::MOI.Bridges.AbstractBridge, set)
map_set(::Type{BT}, set) where {BT}

Return the image of set through the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge.

This function is used for bridging the constraint and setting the MOI.ConstraintSet.

inverse_map_set(bridge::MOI.Bridges.AbstractBridge, set)
inverse_map_set(::Type{BT}, set) where {BT}

Return the preimage of set through the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge.

This function is used for getting the MOI.ConstraintSet.

The method can alternatively be defined on the bridge type. This legacy interface is kept for backward compatibility.

map_function(bridge::MOI.Bridges.AbstractBridge, func)
map_function(::Type{BT}, func) where {BT}

Return the image of func through the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge.

This function is used for getting the MOI.ConstraintPrimal of variable bridges. For constraint bridges, this is used for bridging the constraint, setting the MOI.ConstraintFunction and MOI.ConstraintPrimalStart and modifying the function with MOI.modify.

The default implementation of Constraint.bridge_constraint uses map_function with the bridge type so if this function is defined on the bridge type, Constraint.bridge_constraint does not need to be implemented.

map_function(::Type{BT}, func, i::IndexInVector) where {BT}

Return the scalar function at the ith index of the vector function that would be returned by map_function(BT, func) except that it may compute the ith element. This is used by bridged_function and for getting the MOI.VariablePrimal and MOI.VariablePrimalStart of variable bridges.

inverse_map_function(bridge::MOI.Bridges.AbstractBridge, func)
inverse_map_function(::Type{BT}, func) where {BT}

Return the image of func through the inverse of the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge.

This function is used by Variable.unbridged_map and for setting the MOI.VariablePrimalStart of variable bridges and for getting the MOI.ConstraintFunction, the MOI.ConstraintPrimal and the MOI.ConstraintPrimalStart of constraint bridges.

If the linear map A is not invertible, the error MapNotInvertible is thrown.

The method can alternatively be defined on the bridge type. This legacy interface is kept for backward compatibility.

adjoint_map_function(bridge::MOI.Bridges.AbstractBridge, func)
adjoint_map_function(::Type{BT}, func) where {BT}

Return the image of func through the adjoint of the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge.

This function is used for getting the MOI.ConstraintDual and MOI.ConstraintDualStart of constraint bridges.

The method can alternatively be defined on the bridge type. This legacy interface is kept for backward compatibility.

inverse_adjoint_map_function(bridge::MOI.Bridges.AbstractBridge, func)
inverse_adjoint_map_function(::Type{BT}, func) where {BT}

Return the image of func through the inverse of the adjoint of the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge.

This function is used for getting the MOI.ConstraintDual of variable bridges and setting the MOI.ConstraintDualStart of constraint bridges.

If the linear map A is not invertible, the error MapNotInvertible is thrown.

The method can alternatively be defined on the bridge type. This legacy interface is kept for backward compatibility.

Graph()

A type-stable datastructure for computing the shortest hyperpath problem.

Nodes

There are three types of nodes in the graph:

• VariableNode
• ConstraintNode
• ObjectiveNode

Add nodes to the graph using add_node.

Edges

There are two types of edges in the graph:

• Edge
• ObjectiveEdge

Add edges to the graph using add_edge.

For the ability to add a variable constrained on creation as a free variable followed by a constraint, use set_variable_constraint_node.

Optimal hyper-edges

Use bridge_index to compute the minimum-cost bridge leaving a node.

Note that bridge_index lazy runs a Bellman-Ford algorithm to compute the set of minimum cost edges. Thus, the first call to bridge_index after adding new nodes or edges will take longer than subsequent calls.

VariableNode(index::Int)

A node in Graph representing a variable constrained on creation.

ConstraintNode(index::Int)

A node in Graph representing a constraint.

ObjectiveNode(index::Int)

A node in Graph representing an objective function.

Edge(
    bridge_index::Int,
    added_variables::Vector{VariableNode},
    added_constraints::Vector{ConstraintNode},
    cost::Float64 = 1.0,
)

Return a new datastructure representing an edge in Graph that starts at a VariableNode or a ConstraintNode.

ObjectiveEdge(
    bridge_index::Int,
    added_variables::Vector{VariableNode},
    added_constraints::Vector{ConstraintNode},
)

Return a new datastructure representing an edge in Graph that starts at an ObjectiveNode.

add_node(graph::Graph, ::Type{VariableNode})::VariableNode
add_node(graph::Graph, ::Type{ConstraintNode})::ConstraintNode
add_node(graph::Graph, ::Type{ObjectiveNode})::ObjectiveNode

Add a new node to graph.

add_edge(graph::Graph, node::VariableNode, edge::Edge)::Nothing
add_edge(graph::Graph, node::ConstraintNode, edge::Edge)::Nothing
add_edge(graph::Graph, node::ObjectiveNode, edge::ObjectiveEdge)::Nothing

Add edge to graph, where edge starts at node and connects to the nodes defined in edge.

set_variable_constraint_node(
    graph::Graph,
    variable_node::VariableNode,
    constraint_node::ConstraintNode,
    cost::Int,
)

As an alternative to variable_node, add a virtual edge to graph that represents adding a free variable, followed by a constraint of type constraint_node, with bridging cost cost.

Why is this needed?

Variables can either be added as a variable constrained on creation, or as a free variable which then has a constraint added to it.

bridge_index(graph::Graph, node::VariableNode)::Int
bridge_index(graph::Graph, node::ConstraintNode)::Int
bridge_index(graph::Graph, node::ObjectiveNode)::Int

Return the optimal index of the bridge to chose from node.

is_variable_edge_best(graph::Graph, node::VariableNode)::Bool

Return a Bool indicating whether node should be added as a variable constrained on creation, or as a free variable followed by a constraint.