symmetric_connectivity

The problem is defined as follows: Given a set of nodes $V$ and symmetric power requirements $p(u,v)$, $(u,v)\in V\times V$, find a power assignment

r:

V \rightarrow R_+

minimizing $\sum_{v \in V} r(v)$ subject to the constraint that the graph $(V,B(r))$ is connected.

First, we compute the cost of the minimum spanning tree heuristic. Than, we set-up the integer programm. We have a variable for every edge of the tree supposed to be the incidencevector of the spanning tree we compute (stored in VM) and edges for the radius of a node.

    double ComputeBroadcast(graph& G, edge_array<double>& Cost, list<edge>& T, 
                          GraphWin& GW) {
      list<edge> MST=MIN_SPANNING_TREE(G, Cost);
      node_array<double> MSTC(G,0);
      edge e;
      forall(e,MST) {
        MSTC[source(e)]=leda_max(MSTC[source(e)], Cost[e]);
        MSTC[target(e)]=leda_max(MSTC[target(e)], Cost[e]);
      };
      node u; double mstc=0;
      forall_nodes(u, G) mstc+=MSTC[u]*MSTC[u];
      //cout<<mstc<<" cost of mst\n";
      ILP_Problem IP(Optsense_Min);
      edge f; e=nil;
      var_map<edge> VM;
      var_map<edge> VMy;
      var_map<edge> VMz;
      forall_edges(e,G) { 
        VM[e]=IP.add_variable(-0.1, 0, 1, Vartype_Integer);
        VMy[e]=IP.add_variable(Cost[e]*Cost[e], 0, 1, Vartype_Integer);    
        VMz[e]=IP.add_variable(Cost[e]*Cost[e], 0, 1, Vartype_Integer);
      }
      forall_edges(e,G) {
        row r1;
        forall_out_edges(f,source(e)) if(Cost[f]>=Cost[e]-0.001) r1+=VMy[f];
        forall_in_edges(f, source(e)) if(Cost[f]>=Cost[e]-0.001) r1+=VMz[f];
        IP.add_basic_constraint(r1 >= VM[e]);
        row r2;
        forall_out_edges(f,target(e)) if(Cost[f]>=Cost[e]-0.001) r2+=VMy[f];
        forall_in_edges(f, target(e)) if(Cost[f]>=Cost[e]-0.001) r2+=VMz[f];
        IP.add_basic_constraint(r2 >= VM[e]);
      }    
      forall_nodes(u, G) {
        row r;
        forall_out_edges(e, u) r+=VMy[e];
        forall_in_edges(e, u) r+=VMz[e];
        IP.add_basic_constraint(r==1);
      };
      IP.add_sym_constraint(new SpanTree(G,VM));
      //IP.add_sym_constraint(new Broadcast(G, VM, VMy, VMz, GW, Cost));
      //IP.add_sym_constraint(new disjunctive());
      IP.optimize();
      double optc=0;
      forall_edges(e, G) {
        if(IP.get_solution(VM[e])>0.5) { 
          T.append(e);
        };
      }
      forall_nodes(u, G) MSTC[u]=0;
      forall(e,T) {
        MSTC[source(e)]=leda_max(MSTC[source(e)], Cost[e]);
        MSTC[target(e)]=leda_max(MSTC[target(e)], Cost[e]);
      };
      forall_nodes(u, G) optc+=MSTC[u]*MSTC[u];
      cout<<"Number of nodes "<<G.number_of_nodes()<<endl;
      cout<<"Cost of mst "<<mstc<<"\n";
      cout<<"Cost of optimal solution "<<optc<<"\n";
      cout<<"Save "<<(mstc-optc)/mstc*100<<"\n";
      return (mstc-optc)/mstc*100;
    } // END_COMPUTE_BROADCAST

---