Simple question on undirected graphs

Problems with syntax of GAMS
Post Reply
bissi
User
User
Posts: 3
Joined: 6 years ago

Simple question on undirected graphs

Post by bissi »

So I have my standard SETS, PARAMETERS, EQUATIONS defined. I have a set "I" of nodes, aliased with "J". I have an edge set, EDGE(I,J), but I want my graph to be undirected. So I defined my edges in this way:

edge('s1',j)$i_nodes(j)= yes;
edge(j,'s1')$i_nodes(j)= yes;

This is part of the graph, but you should get an idea. I define an edge between nodes x and y, and then rewrite to get an edge between y and x.
Now when I have my equations defined, with a variable Y(I,J), I can run into problems that Y(I,J) is not same as Y(J,I). So I create an extra equation:

undir_1(i,j)$(edge(i,j))..
y(i,j)=e=y(j,i) ;

This seems really stupid to me. What is the way out?
cladelpino
User
User
Posts: 108
Joined: 7 years ago

Re: Simple question on undirected graphs

Post by cladelpino »

A small example, based on the approach of defining edges only between a "lower order" node and a "higher order" node.

Code: Select all

set i nodes /s1*s10/;
alias(i,j);
set candedge(i,i),edge(i,i),i_nodes(i),connected(i);
binary variable y;
variable z;


candedge(i,j)$(ord(i)<ord(j))=yes;

i_nodes(i)=yes$(uniform(0,1)>0.5);

*Some redundancy is needed if you don't know the location of 's1' in the node set:
*In order to put to test this approach, I use 's5' instead.
edge(i,j)$(candedge(i,j) and sameas(i,'s5') and i_nodes(j))= yes;
edge(j,i)$(candedge(j,i) and sameas(i,'s5') and i_nodes(j))= yes;

connected(i)=yes$(sum(j$(edge(i,j) or edge(j,i)),1)>0);

*Example Constraint: choose at least one incident edge
*Although you have a smaller set of variables, some redundancy is needed
equation atmostoneedge,fobj;
fobj.. z=e=sum((i,j)$edge(i,j),y(i,j));
atmostoneedge(i)$connected(i).. sum(j$edge(i,j),y(i,j))+sum(j$edge(j,i),y(j,i))=g=1;

display candedge,i_nodes,edge;

model graph /all/
solve graph using mip minizing z
bissi
User
User
Posts: 3
Joined: 6 years ago

Re: Simple question on undirected graphs

Post by bissi »

cladelpino,

Thanks for replying. I do have lower and higher order nodes in my code too. But that does not guarantee y(i,j)=y(j,i) without an extra equation.
However, even in your code you need an extra equation. To make things more precise, here is my small code:
objS..
zS =e= sum(edge(i,j)$(ord(j) gt ord(i)), d(i,j)*u(i,j));

cut(i,j)$(edge(i,j))..
u(i,j) + trial(i,j) =g= x(j) - x(i);

undir_2(i,j)$(edge(i,j))..
u(i,j) =e= u(j,i) ;

The equation undir_2 is the one I do not like.
cladelpino
User
User
Posts: 108
Joined: 7 years ago

Re: Simple question on undirected graphs

Post by cladelpino »

Dear bissi, I guess I'm not following you.
bissi wrote:But that does not guarantee u(i,j)=u(j,i) without an extra equation.


In the approach suggested by me, the variable is actually defined only once for each possible edge in the graph. No need to "guarantee u(i,j)=u(j,i)", because u(j,i) shouldn't exist when ord(j)>ord(i).

In order to force its non-existence, it needs to never appear in the model. Both the objective function and the "cut" constraint you quoted will work in a straightforward way since they are basically using the "edge set", which can be properly defined.

If you send me a complete small -working- example, I can adapt it to the approach proposed. You can look at the y variable in the example I sent, and you will notice it is only defined for edges where i<j.

Best regards
Claudio
bissi
User
User
Posts: 3
Joined: 6 years ago

Re: Simple question on undirected graphs

Post by bissi »

Dear Claudio,

I tried following your code but could not get it to work for my case. Attached is my GAMS code with the extra constraints undir_1 and undir_2. These are the two constraints which I find stupid but cannot get rid of. Let me know what you think. Thank you!
Attachments
dummy_trial_6.gms
(5.55 KiB) Downloaded 282 times
cladelpino
User
User
Posts: 108
Joined: 7 years ago

Re: Simple question on undirected graphs

Post by cladelpino »

Check out this example, I think it can accomodate what I saw in your code.

Code: Select all

set i nodes /i1*i10/;
alias(i,j);

set someSetOfNodes(i),otherSetOfNodes(i);

someSetOfNodes(i)=YES$(uniform(0,1)<0.5);
otherSetOfNodes(i)=YES$(uniform(0,1)<0.5);

set edges(i,j),aTypeOfEdge(i,j),anotherTypeOfEdge(i,j);

*connect some arbitrary nodes to a set of other nodes, distingushing between these two sets.

aTypeOfEdge(i,j)$(ord(i)<ord(j) and sameas(i,'i3') and someSetOfNodes(j))=YES;
aTypeOfEdge(i,j)$(ord(i)<ord(j) and sameas(j,'i3') and someSetOfNodes(i))=YES;
anotherTypeOfEdge(i,j)$(ord(i)<ord(j) and sameas(i,'i5') and otherSetOfNodes(j))=YES;
anotherTypeOfEdge(i,j)$(ord(i)<ord(j) and sameas(j,'i5') and otherSetOfNodes(i))=YES;

edges(i,j)$(aTypeOfEdge(i,j) or anotherTypeOfEdge(i,j))=YES;

parameter someParameter,otherParameter;

someParameter(edges)$(aTypeofEdge(edges))=1;
otherParameter(edges)$(anotherTypeOfEdge(edges))=10;

parameter weight;
weight(edges)=uniform(-1,1);
binary variable  y;
variable z;
equation fobj;

fobj.. sum(edges,weight(edges)*y(edges))=e=z;

equation aConstraintOverASetOfNodes;

aConstraintOverASetOfNodes(someSetOfNodes)..

sum(i,y(i,someSetOfNodes)$edges(i,someSetOfNodes)+y(someSetOfNodes,i)$edges(someSetOfNodes,i))=g=1;

equation aConstraintOverASetOfEdges;

aConstraintOverASetOfEdges(edges)$(anotherTypeOfEdge(edges))..  y(edges)=e=1;

model aModel /all/
solve aModel using mip maximizing z;
display weight;
Good Luck!!
Post Reply