Before I ask my question let me give you an overview of the basic problem I am trying to solve:
1.) a set of 2000+ nodes + node A & B
2.) With 20+ different connected graphs made up of a sub set of the given set node (~200 per graph + A + B) with about ~1000 edges in each graph
Find the minimum set of nodes such that all the graphs remain connected such that there is a path from A to B. Which on average should only take 10 nodes per graph
My naive implementation in JuMP was something like this:
@variable(model, node_switch[i=1:2000],Bin) @expression(model, node_switched_capacity[i=1:2000], node_capacity[i]*node_switch[i])
Then I go on to build the embedded flow sub problems using
node_switched_capacity for each of the graphs. This will solve for 1 graph but just does not scale past maybe 5 graphs.
It is clear to me that I need to change this to a Column Generation problem.
The question I have is this is I generate columns that are essentially small sub sets of nodes how can I translate that into a node_capacity_expresion?