Algorithm interfaces

IncidenceGraphInterface(
    model;
    include_inequality = false,
    include_active_inequalities = false,
    tolerance = 0.0,
)

A bipartite incidence graph of JuMP constraints and variables.

This is the primary data type accepted by the algorithms implemented in the remainder of this module. This type can be instantiated with a JuMP model or a tuple of (graph, con_node_map, var_node_map), as returned by get_bipartite_incidence_graph. If a model is provided, optional arguments are the same as those provided to get_bipartite_incidence_graph.

Note that the fields of this struct are private, and may change behavior in a future release without warning.

Example using only equality constraints

using JuMP
import MathProgIncidence
m = Model()
@variable(m, v[1:3] >= 0)
@constraint(m, eq_1, v[1] + v[3]^2 == 1.0)
@NLconstraint(m, eq_2, v[1]*v[2]^1.5 == 2.0)
graph = MathProgIncidence.IncidenceGraphInterface(m)

Example including active inequality constraints

using JuMP
import Ipopt
import MathProgIncidence
m = Model(Ipopt.Optimizer)
@variable(m, v[1:3] >= 0)
@NLconstraint(m, eq_1, v[1]*v[2]^1.5 == 2.0)
@constraint(m, ineq_1, v[1] + v[2] + v[3] >= 7)
@objective(m, Min, v[1]^2 + 2*v[2]^2 + 3*v[3]^2)
optimize!(m)
graph = MathProgIncidence.IncidenceGraphInterface(
    m, include_active_inequalities = true, tolerance = 1e-6
)

get_adjacent(
    igraph::IncidenceGraphInterface,
    constraint::JuMP.ConstriantRef,
)::Vector{JuMP.VariableRef}

Return the variables adjacent to a constraint in an incidence graph.

get_adjacent(
    igraph::IncidenceGraphInterface,
    variable::JuMP.VariableRef,
)::Vector{JuMP.ConstraintRef}

Return the constraints adjacent to a variable in an incidence graph.

Example

julia> using JuMP

julia> import MathProgIncidence

julia> m = Model();

julia> @variable(m, v[1:3]);

julia> @constraint(m, eq_1, v[1] + v[3] == 1);

julia> @NLconstraint(m, eq_2, v[1]*v[2]^3 == 2);

julia> igraph = MathProgIncidence.IncidenceGraphInterface(m);

julia> adj_cons = MathProgIncidence.get_adjacent(igraph, v[1]);

julia> display(adj_cons)
2-element Vector{ConstraintRef}:
 eq_1 : v[1] + v[3] = 1.0
 v[1] * v[2] ^ 3.0 - 2.0 = 0

maximum_matching(igraph::IncidenceGraphInterface)::Dict

Compute a maximum matching of variables and constraints in the incidence graph.

The returned Dict maps JuMP ConstraintRefs to their matched VariableRefs.

Example

julia> using JuMP

julia> import MathProgIncidence

julia> m = Model();

julia> @variable(m, v[1:3]);

julia> @constraint(m, eq_1, v[1] + v[3] == 1);

julia> @NLconstraint(m, eq_2, v[1]*v[2]^3 == 2);

julia> igraph = MathProgIncidence.IncidenceGraphInterface(m);

julia> matching = MathProgIncidence.maximum_matching(igraph);

julia> display(matching)
Dict{ConstraintRef, VariableRef} with 2 entries:
  v[1] * v[2] ^ 3.0 - 2.0 = 0 => v[2]
  eq_1 : v[1] + v[3] = 1.0 => v[1]

dulmage_mendelsohn(igraph::IncidenceGraphInterface)

Return the Dulmage-Mendelsohn partition of variables and constraints in an incidence graph.

The returned type is a Tuple of two NamedTuples, (con_dmp, var_dmp). These NamedTuples have the following fields:

con_dmp:

• underconstrained – The constraints matched with variables that can possibly be unmatched in a maximum cardinality matching
• square – The constraints that cannot possibly be unmatched in a maximum matching
• overconstrained – The constraints that are matched, but can possibly be unmatched in a maximum matching
• unmatched – The constraints that are not matched in the maximum matching that was found

var_dmp:

• unmatched – The variables that are not matched in the maximum matching that was found
• underconstrained – The variables that can possibly be unmatched in a maximum matching
• square – The variables that cannot possibly be unmatched in a maximum matching
• overconstrained – The variables matched with constraints that can possibly be unmatched in a maximum cardinality matching

The Dulmage-Mendelsohn partition groups nodes in a bipartite graph into three unique subsets. In the application to constraints and variables, these may be thought of as:

• the "overconstrained subsystem", which has more constraints than variables,
• the "underconstrained subsystem", which has more variables than constraints,
• and the "square subsystem", which has the same number of variables as constraints

In the NamedTuples returned by this function, the constraints in the overconstrained subsystem are split into overconstrained and unmatched, while the variables in the underconstrained subsystem are split into underconstrained and unmatched. This is because it is useful to explicitly check whether there are any unmatched variables and constraints, and also useful to recover the maximum matching by zip-ing corresponding variables and constraints.

Example

julia> using JuMP

julia> import MathProgIncidence

julia> m = Model();

julia> @variable(m, v[1:4]);

julia> @constraint(m, eq_1, v[1] + v[3] == 1);

julia> @NLconstraint(m, eq_2, v[1]*v[2]^3 == 2);

julia> @constraint(m, eq_3, v[4]^2 == 3);

julia> igraph = MathProgIncidence.IncidenceGraphInterface(m);

julia> con_dmp, var_dmp = MathProgIncidence.dulmage_mendelsohn(igraph);

julia> # Assert that there are no unmatched constraints

julia> @assert isempty(con_dmp.unmatched);

julia> display(var_dmp.unmatched)
1-element Vector{VariableRef}:
 v[3]

julia> display(var_dmp.underconstrained)
2-element Vector{VariableRef}:
 v[1]
 v[2]

julia> display(con_dmp.underconstrained)
2-element Vector{ConstraintRef}:
 eq_1 : v[1] + v[3] = 1.0
 v[1] * v[2] ^ 3.0 - 2.0 = 0
 
julia> display(var_dmp.square)
1-element Vector{VariableRef}:
 v[4]

julia> display(con_dmp.square)
1-element Vector{ConstraintRef}:
 eq_3 : v[4]² = 3.0

julia> # As there are no unmatched constraints, the overconstrained subsystem is empty

connected_components(igraph::IncidenceGraphInterface)

Return the connected components of a bipartite incidence graph of constraints and variables.

The connected components are returned as two vector-of-vectors, containing the variables in each connected component and the constraints in each connected component. Note that the input graph is undirected, so there is no distinction between strongly and weakly connected components.

Example

julia> using JuMP

julia> import MathProgIncidence

julia> m = Model();

julia> @variable(m, x[1:2] >= 0);

julia> @constraint(m, eq1, x[1] == 1);

julia> @constraint(m, eq2, x[2]^2 == 2);

julia> igraph = MathProgIncidence.IncidenceGraphInterface(m);

julia> con_comps, var_comps = MathProgIncidence.connected_components(igraph);

julia> con_comps
2-element Vector{Vector{ConstraintRef}}:
 [eq1 : x[1] = 1]
 [eq2 : x[2]² = 2]

julia> var_comps
2-element Vector{Vector{VariableRef}}:
 [x[1]]
 [x[2]]

connected_components(constraints, variables)

Return the connected components of a bipartite incidence graph of constraints and variables.

The method that accepts constraints and variables directly is convenient for working with the output of the Dulmage-Mendelsohn partition. It is often used to decompose and help debug the over and under-constrained subsystems.

Example

julia> using JuMP

julia> import MathProgIncidence

julia> m = Model();

julia> @variable(m, x[1:4] >= 0);

julia> @constraint(m, eq1, x[1] + x[3] == 7);

julia> @constraint(m, eq2, x[2]^2 + x[4]^2 == 1);

julia> igraph = MathProgIncidence.IncidenceGraphInterface(m);

julia> con_dmp, var_dmp = MathProgIncidence.dulmage_mendelsohn(igraph);

julia> uc_con = con_dmp.underconstrained;

julia> uc_var = [var_dmp.unmatched..., var_dmp.underconstrained...];

julia> con_comps, var_comps = MathProgIncidence.connected_components(uc_con, uc_var);

julia> con_comps
2-element Vector{Vector{ConstraintRef}}:
 [eq1 : x[1] + x[3] = 7]
 [eq2 : x[2]² + x[4]² = 1]

julia> var_comps
2-element Vector{Vector{VariableRef}}:
 [x[3], x[1]]
 [x[4], x[2]]