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