treecplexminimum-spanning-tree

Min Spanning tree with cplex-opl


I am confused with CPLEXs coding, there isn't any help on the net. Help me, please.

This is my code. I have a problem with constraint2, I don't know how to define 3 conditions before summing in constraint2. I attached the MST1 formulation picture.enter image description here

This is my code.

range i= 1..7;
range j= 1..7;
range node=1..7;
{int} v= {1,2,3,4,5,6,7};   
{int} E={{1,2},{1,4},{1,6},{2,1},{2,4},{2,3},{2,5},{3,2},{3,5},{3,7},{4,1},{4,2},
{4,5},{4,7},{5,2},{5,3},{5,4},{5,7},{6,1},{6,4},{6,7},{7,3},{7,5},{7,6}};

float Q[node][node]=[[0,5,0,6,0,7,0,0],[5,0,5,5,4],[0,5,0,0,3,0,3],
[6,5,0,0,2,2],[0,4,3,2,0,0,1],[7,0,0,2,0,0,2],[0,0,3,0,1,2,0]];

dvar boolean x[i][j];


dexpr float w= sum(i,j in E)Q[node][node]*x[i][j];
minimize w;

/*****************constraint******************/
subject to {
cons1:
sum(i,j in E)x[i][j]==6;

cons2:
forall (s in sub[v]:{s}!={v}{s}!={})sum(i,j in E(s))x[i][j]<=abs(s)-1
  ;
}

Solution

  • I posted an example in https://www.linkedin.com/pulse/tips-tricks-opl-cplex-alex-fleischer/

    minimum spanning tree

    tuple edge
        {
            key int o;
            key int d;
            int weight;
        }
    
        {edge} edges=...;
    
        {int} nodes={i.o | i in edges} union {i.d | i in edges};
    
        range r=1..-2+ftoi(pow(2,card(nodes)));
        {int} nodes2 [k in r] = {i | i in nodes: ((k div (ftoi(pow(2,(ord(nodes,i))))) mod 2) == 1)};
    
        dvar boolean x[edges];
    
        minimize sum (e in edges) x[e]*e.weight;
        subject to
        {
        sum(e in edges) x[e]==card(nodes)-1;
    
        // Subtour elimination constraints.
           
        forall(k in r)  // all subsets but empty and all
            sum(e in edges:(e.o in nodes2[k]) && (e.d in nodes2[k])) x[e]<=card(nodes2[k])-1;  
           
        }
    
        {edge} solution={e | e in edges : x[e]==1};
    
        execute
        {
        writeln("minimum spanning tree ",solution);
        }
    
    
    /*
    which gives
        minimum spanning tree  {<1 4 8> <2 3 3> <3 5 2> <4 5 8> <4 7 7> <5 6 2> <7 8 4>
             <8 9 1> <9 10 3>}
             
             */