peter.cc

#include<scil/scil.h>
#include <boost/graph/adjacency_list.hpp>

#define K 16
#define N 20
#define KK 256
#define P 0.55

using namespace SCIL;
using namespace boost;

int main() {

  typedef adjacency_list< vecS, vecS, directedS > Graph;
  typedef graph_traits<Graph>::edge_descriptor edge;    
  typedef graph_traits<Graph>::vertex_descriptor vertex;        
  typedef graph_traits<Graph>::edge_iterator edge_iterator;     


  Graph G;
  var V[N+KK];
  ILP_Problem IP(Optsense_Min);

  // create vertices
  for( int i=0;i<N+KK;i++ )
    add_vertex(G);


  // Generate edges with probability P
  srand ( time(NULL) );
  double d;
  for(int i=0; i<N; i++) 
    for(int j=0; j<KK; j++) {
      d = (double)rand()/RAND_MAX;
      if(d<=P) add_edge(i,N+j,G);
  };


  // add variable
  for(int i=0; i<N; i++) V[i]=IP.add_binary_variable(1);
  for(int i=N; i<N+KK; i++) V[i]=IP.add_binary_variable(0);

  // add constraints
  edge_iterator ei,ei_end;
  for( tie(ei,ei_end) =edges(G); ei!=ei_end; ++ei )
    IP.add_basic_constraint((row) V[source(*ei,G)]>=V[target(*ei,G)]);

  row r;
  for(int i=N; i<N+KK; i++) r+=V[i];
  IP.add_basic_constraint(r==K);

  // solve
  IP.optimize();

  return 0;


  /*Graph G;
  vertex L[N];
  vertex R[KK];
  var V[N+KK];
  map<vertex,int> VM;
  ILP_Problem IP(Optsense_Min);
  
  for( int i=0;i<N;i++ ){
    L[i] = add_vertex(G);
    VM[L[i]] = i;
  }

  for( int i=0;i<KK;i++ ){
    R[i]=add_vertex(G);
    VM[R[i]]=i+N;
  }

 // initialize random seed:
  srand ( time(NULL) );

  // Generate edges with probability P
  double d;
  for(int i=0; i<N; i++) for(int j=0; j<KK; j++) {
    d = (double)rand()/RAND_MAX;
    if(d<=P) add_edge(L[i],R[j],G);
  };


  for(int i=0; i<N; i++) V[i]=IP.add_binary_variable(1);
  for(int i=N; i<N+KK; i++) V[i]=IP.add_binary_variable(0);

  edge_iterator ei,ei_end;
  for( tie(ei,ei_end) =edges(G); ei!=ei_end; ++ei )
    IP.add_basic_constraint((row) V[VM[source(*ei,G)]]>=V[VM[target(*ei,G)]]);

  row r;
  for(int i=N; i<N+KK; i++) r+=V[i];
  IP.add_basic_constraint(r==K);

  IP.optimize();

  return 0; */
}

---