Bridges

abstract type AbstractBridge end

An abstract type representing a bridged constraint or variable in a MathOptInterface.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:

• MathOptInterface.ConstraintDual
• MathOptInterface.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.

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.

Example

julia> MOI.Bridges.added_constraint_types(
           MOI.Bridges.Constraint.ZeroOneBridge{Float64},
       )
2-element Vector{Tuple{Type, Type}}:
 (MathOptInterface.VariableIndex, 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 repsect 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.

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

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.

abstract type AbstractFunctionConversionBridge{F,S} <: AbstractBridge end

Abstract type to support writing bridges in which the function changes but the set does not.

By convention, the transformed function is stored in the .constraint field.

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 MathOptInterface.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}}
with 0 constraint bridges
with inner model MOIU.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.Constraint.SingleBridgeOptimizer{MyNewBridge{T},OT};

This enables users to create bridged models as follows:

julia> MyNewBridgeModel{Float64}(MOI.Utilities.Model{Float64}())
MOIB.Constraint.SingleBridgeOptimizer{MyNewBridge{Float64}, MOIU.Model{Float64}}
with 0 constraint bridges
with inner model MOIU.Model{Float64}

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

Add all bridges defined in the Bridges.Constraint submodule to bridged_model. The coefficient type used is T.

FlipSignBridge{T,S1,S2,F,G}

An abstract type that simplifies the creation of other bridges.

AbstractToIntervalBridge{T<:AbstractFloat,S,F}

An abstract type that simplifies the creation of other bridges.

abstract type SetMapBridge{T,S2,S1,F,G} <: AbstractBridge end

Consider two type of sets, S1 and S2, and a linear mapping A such that the image of a set of type S1 under A is a set of type S2.

A SetMapBridge{T,S2,S1,F,G} is a bridge that maps G-in-S2 constraints into F-in-S1 by mapping the function through A.

The linear map A is described by;

• MathOptInterface.Bridges.map_set
• MathOptInterface.Bridges.map_function.

Implementing a method for these two functions is sufficient to bridge constraints. However, in order for the getters and setters of attributes such as dual solutions and starting values to work as well, a method for the following functions must be implemented:

• MathOptInterface.Bridges.inverse_map_set
• MathOptInterface.Bridges.inverse_map_function
• MathOptInterface.Bridges.adjoint_map_function
• MathOptInterface.Bridges.inverse_adjoint_map_function

See the docstrings of each function to see which feature would be missing if it was not implemented for a given bridge.

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

supports_objective_function(
    BT::Type{<:MOI.Bridges.Objective.AbstractBridge},
    F::Type{<:MOI.AbstractScalarFunction},
)::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.AbstractScalarFunction}

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.AbstractScalarFunction},
)::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.AbstractScalarFunction,
)::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.

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 MathOptInterface.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}(),
       )
MOIB.Objective.SingleBridgeOptimizer{MyNewBridge{Float64}, MOIU.Model{Float64}}
with 0 objective bridges
with inner model MOIU.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}())
MOIB.Objective.SingleBridgeOptimizer{MyNewBridge{Float64}, MOIU.Model{Float64}}
with 0 objective bridges
with inner model MOIU.Model{Float64}

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

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.

Examples

As a variable in MathOptInterface.GreaterThan is bridged into variables in MathOptInterface.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.

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}(),
       )
MOIB.Variable.SingleBridgeOptimizer{MyNewBridge{Float64}, MOIU.Model{Float64}}
with 0 variable bridges
with inner model MOIU.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}())
MOIB.Variable.SingleBridgeOptimizer{MyNewBridge{Float64}, MOIU.Model{Float64}}
with 0 variable bridges
with inner model MOIU.Model{Float64}

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.

abstract type FlipSignBridge{T,S1,S2} <: SetMapBridge{T,S2,S1} end

An abstract type that simplifies the creation of other bridges.

abstract type SetMapBridge{T,S1,S2} <: AbstractBridge end

Consider two type of sets, S1 and S2, and a linear mapping A such that the image of a set of type S1 under A is a set of type S2.

A SetMapBridge{T,S1,S2} is a bridge that substitutes constrained variables in S2 into the image through A of constrained variables in S1.

The linear map A is described by:

• MathOptInterface.Bridges.map_set
• MathOptInterface.Bridges.map_function

Implementing a method for these two functions is sufficient to bridge constrained variables. However, in order for the getters and setters of attributes such as dual solutions and starting values to work as well, a method for the following functions must be implemented:

• MathOptInterface.Bridges.inverse_map_set
• MathOptInterface.Bridges.inverse_map_function
• MathOptInterface.Bridges.adjoint_map_function
• MathOptInterface.Bridges.inverse_adjoint_map_function.

See the docstrings of each function to see which feature would be missing if it was not implemented for a given bridge.

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.

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}())
MOIB.LazyBridgeOptimizer{MOIU.Model{Float64}}
with 0 variable bridges
with 0 constraint bridges
with 0 objective bridges
with inner model MOIU.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 (e.g., within the solver package itself) or only apply in certain circumstances (e.g., 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 MathOptInterface.instantiate.

Examples

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, e.g., 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_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(s) 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: https://arxiv.org/abs/2002.03447

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.

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 is used for bridging the constraint and setting the MathOptInterface.ConstraintSet.

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 is used for getting the MathOptInterface.ConstraintSet.

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 is used for getting the MathOptInterface.ConstraintPrimal of variable bridges. For constraint bridges, this is used for bridging the constraint, setting the MathOptInterface.ConstraintFunction and MathOptInterface.ConstraintPrimalStart and modifying the function with MathOptInterface.modify.

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 MathOptInterface.VariablePrimal and MathOptInterface.VariablePrimalStart of variable bridges.

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 is used by Variable.unbridged_map and for setting the MathOptInterface.VariablePrimalStart of variable bridges and for getting the MathOptInterface.ConstraintFunction, the MathOptInterface.ConstraintPrimal and the MathOptInterface.ConstraintPrimalStart of constraint bridges.

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 is used for getting the MathOptInterface.ConstraintDual and MathOptInterface.ConstraintDualStart of constraint bridges.

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 is used for getting the MathOptInterface.ConstraintDual of variable bridges and setting the MathOptInterface.ConstraintDualStart of constraint bridges.

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},
)

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.