00001 #include<scil/scil.h>
00002 #include<LEDA/graph.h>
00003
00004 #define K 16
00005 #define N 20
00006 #define KK 256
00007 #define P 0.55
00008
00009 using namespace SCIL;
00010 using namespace LEDA;
00011
00012 int main() {
00013
00014 graph G;
00015 node L[N];
00016 node R[KK];
00017 var V[N+KK];
00018 node_map<int> NM(G);
00019 ILP_Problem IP(Optsense_Min);
00020
00021 for(int i=0; i<N; i++) {
00022 L[i]=G.new_node();
00023 NM[L[i]]=i;
00024 }
00025 for(int i=0; i<KK; i++) {
00026 R[i]=G.new_node();
00027 NM[R[i]]=i+N;
00028 }
00029
00030 random_source RS;
00031 double d;
00032 for(int i=0; i<N; i++) for(int j=0; j<KK; j++) {
00033 RS>>d;
00034 if(d<=P) G.new_edge(L[i],R[j]);
00035 };
00036
00037
00038 for(int i=0; i<N; i++) V[i]=IP.add_variable(1,0,1,Vartype_Integer);
00039 for(int i=N; i<N+KK; i++) V[i]=IP.add_variable(0,0,1, Vartype_Integer);
00040
00041 edge e;
00042 forall_edges(e, G)
00043 IP.add_basic_constraint((row) V[NM[source(e)]]>=V[NM[target(e)]]);
00044
00045 row r;
00046 for(int i=N; i<N+KK; i++) r+=V[i];
00047 IP.add_basic_constraint(r==K);
00048
00049 IP.optimize();
00050
00051 return 0;
00052 }
