# Sub set selection and column generation

**URL:** https://discourse.julialang.org/t/sub-set-selection-and-column-generation/20716
**Category:** Optimization (Mathematical)
**Created:** [February 12, 2019, 5:55pm UTC](https://discourse.julialang.org/t/sub-set-selection-and-column-generation/20716 "2019-02-12T17:55:23Z")
**Posts on this page:** 1
**Page:** 1

<div class="post-metadata">

### Author: ![ndinsmore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ndinsmore/32/7433_2.png) [@ndinsmore](https://discourse.julialang.org/u/ndinsmore)
#### Post date: [February 12, 2019, 5:55pm UTC](https://discourse.julialang.org/t/sub-set-selection-and-column-generation/20716/1 "2019-02-12T17:55:23Z")

</div>

Before I ask my question let me give you an overview of the basic problem I am trying to solve:  
Given:  
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:

```julia
@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?