Very nice new tutorial. Being interested in model building for these things, I typed up a quick tutorial of using acsets (attributed C-sets, a data structure from applied category theory, but in practice something akin to an in-memory relational database with additional equations on paths possible) for generating this type of model. They are exported from the Catlab.jl package. The full script is here https://jump.dev/JuMP.jl/dev/tutorials/getting_started/sum_if/ with acsets (github.com)
The data structure which powers this is this acset whose schema is in the screenshot below (produced by to_graphviz). The ovals are finite Sets (edges and verticies), and the arrows are Functions. The dots are “attributes” which map to Julia types, in this case Int for the demand, and JuMP.VariableRef for the flows. The arrows between finite sets are indexed so that reverse lookup is fast.
In the code I used some convenience functions for acsets that are “graph-like”, such as inedges but they are just wrappers for the generic way to do inverse lookup on arrows, see the source at: Catlab.jl/src/graphs/BasicGraphs.jl at main · AlgebraicJulia/Catlab.jl (github.com)
@present SchDemandGraph <: SchGraph begin
Demand::AttrType
Flows::AttrType
d::Attr(V,Demand)
x::Attr(E,Flows)
end
to_graphviz(SchDemandGraph)
@abstract_acset_type AbstractDemandGraph <: AbstractGraph
@acset_type DemandGraph(SchDemandGraph, index=[:src,:tgt]) <: AbstractDemandGraph
acs_graph = @acset DemandGraph{Int,JuMP.VariableRef} begin
V=length(nodes)
E=length(edges)
src=first.(edges)
tgt=last.(edges)
d=demand.(nodes)
end
model = JuMP.Model()
acs_graph[:, :x] = @variable(model, flows[e in Catlab.edges(acs_graph)] >= 0)
@constraint(
model,
[n in Catlab.vertices(acs_graph)],
sum(acs_graph[inedges(acs_graph, n), :x]) -
sum(acs_graph[outedges(acs_graph, n), :x]) == acs_graph[n, :d]
)
Benchmarking results are basically the same as expected. I think that acsets open up interesting possibilities for very expressive model building and fusing data + the LP/MIP model, so it was fun to write out this small example.
