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
Connected Subgraph Generation
-
- User
- Posts: 108
- Joined: 7 years ago
Re: Connected Subgraph Generation
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
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