Hello,

I have a graph G=(V,E) in GAMS, and I am trying to generate all connected subgraphs of G, possibly by using dynamic sets.

Any idea on solving this issue is greatly appreciated.

Thanks,

Amin

This problem of course admits a MIP formulation, but you cannot easily (of the top of my head) limit it to generate only one subgraph per run. Of course this may not be a problem for you (since you are trying to enumerate them all). Something along the lines of…

set node nodes;

set edge(node,node) /…/;

alias(node,i);

binary variable x indicates if the node is chosen for the subgraph;

equation isconnected;

isconnected(node)… sum(i$(edge(node,i) or edge(i,node)),x(i)) =g= x(node);

equation sizeDef;

sizeDef… sum(node,x(node))=e=size;

model subg /all/;

solve subg using MIP maximizing size;

then repeat adding cuts…

Best

Claudio