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:
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?
A small example, based on the approach of defining edges only between a “lower order” node and a “higher order” node.
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
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));
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.
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! dummy_trial_6.gms (5.55 KB)
Check out this example, I think it can accomodate what I saw in your code.
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;