Incidence graph

get_bipartite_incidence_graph(
    model,
    include_inequality = false,
    include_active_inequalities = false,
    tolerance = 0.0,
)

Return the bipartite incidence graph of (scalar) variables and constraints in the JuMP model.

Arguments

• model::JuMP.Model: Model whose incidence graph is constructed
• include_inequality::Bool: Whether all inequality constraints should be included in the graph
• include_active_inequalities::Bool: Whether only active inequality constraints should be included in the graph. Constraint activity is determined using the most recent solution. include_active_inequalities and include_inequality are mutually exclusive.
• tolerance::Float64: Tolerance for deciding whether an inequality constraint is active

Returns

This function returns a tuple (graph, con_node_map, var_node_map)

• graph – a tuple (A, B, E) where A and B contain the integer nodes in the bipartite sets for constraints and variables and E contains edges in the form of tuples of integers (a, b), where a is in A and b is in B.
• con_node_map – a Dict mapping JuMP ConstraintRefs to nodes
• var_node_map – a Dict mapping JuMP VariableRefs to nodes

The constraints in the graph are all the (by default, equality) constraints in the model, and the variables are those that participate in these constraints (not all variables in the model).

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]^2 == 1.0);

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

julia> graph, con_node_map, var_node_map = MathProgIncidence.get_bipartite_incidence_graph(m);

julia> A, B, E = graph;

julia> M = length(A);

julia> N = length(B);

julia> imat = zeros(M, N);

julia> for (a, b) in E
           imat[a, b-M] = 1.0;
       end

julia> display(imat)
2×3 Matrix{Float64}:
 1.0  1.0  0.0
 0.0  1.0  1.0

Convention

The returned graph follows a convention where, for a JuMP model with N constraints and M variables, the first N nodes are constraints and nodes N+1 through N+M are variables. Nodes are always contiguous integers starting at 1.

Methods

Methods are implemented that accept a JuMP Model, a vector of ConstraintRefs, and vectors of ConstraintRefs and VariableRefs. If variables are provided, then only these variables participate in the graph, regardless of which variables participate in the constraints.