dnatag.c

#include<scil/scil.h>

#include<LEDA/graph.h>

using namespace LEDA;
using namespace SCIL;

#define P 10
#define T 5
#define Pr 0.02

class PrimerVariable : public var_obj {
  cons* C;
  list<int> PV;

  public:

  PrimerVariable(bool* B_, cons* C_) : var_obj(1,0,1) {
    C=new cons[P];
    for(int i=0; i<P; i++) {
      C[i]=C_[i];
      if(B_[i]) PV.append(i);
    };
  };

  PrimerVariable(cons* C_) : var_obj(100,0,1) {
    C=new cons[P];
    for(int i=0; i<P; i++) {
      C[i]=C_[i];
      PV.append(i);
    };
  };

  ~PrimerVariable() {
    delete[] C;
  };

  void non_zero_entries(column& Co) {
    cout<<PV.size()<<" HIER\n";
    int i;
    forall(i, PV) {
      Co+=(column) C[i];
    }
  }

};

double Solve_Pricing(graph& G, double* C, bool* B, node_array<int> N) {
  ILP_Problem ILP(Optsense_Min);
  
  //ILP.set_silent();

  node u;
  var_map<node> VN;
  row r;
  forall_nodes(u, G) {
    if(N[u]==-1) {
      VN[u]=ILP.add_integer_variable(0,0,1);
      r+=VN[u];
    } else { 
      VN[u]=ILP.add_integer_variable(-C[N[u]],0,1);
      r-=VN[u];
    }
  }
  ILP.add_basic_constraint(r==0);  

  edge e;
  var_map<edge> VE;
  forall_edges(e, G) {
    VE[e]=ILP.add_integer_variable(0,0,0);
    ILP.add_basic_constraint((row) VE[e]>=VN[source(e)]+VN[target(e)]-1);
  }

  forall_nodes(u, G) if(G.degree(u)!=0) {
    row r1;
    forall_inout_edges(e, u) r1+=(row) VE[e];
    ILP.add_basic_constraint(r1<=1);
  }

  ILP.optimize();

  double D=0;
  forall_nodes(u, G) if(N[u]!=-1) {
    if(ILP.get_solution(VN[u])==1) {
      B[N[u]]=1;
      D+=C[N[u]];
    } else B[N[u]]=0;
  };
  cout<<D<<" SOLIUTION\n";
  return D;
};

class PrimerPricer : public sym_constraint {
  private:
    graph& G;
    cons* C;
    node_array<int>& PN;
    bool no_more_pricing;

  public:

  PrimerPricer(graph& G_, cons* C_, node_array<int>& PN_) : G(G_), C(C_), PN(PN_) {
    no_more_pricing=false;
  };

  status feasible(subproblem& s) {
    return feasible_solution;
  };

  status LP_pricing(subproblem& s) {
    if(no_more_pricing) return no_variable_found;
    cout<<"HIER\n";
    double Co[P];
    bool B[P];
    for(int i=0; i<P; i++) Co[i]=s.value(C[i])+0.001;
    double d=Solve_Pricing(G, Co, B, PN);
    //for(int i=0; i<P; i++) cout<<B[i]<<" "; cout<<endl;
    cout<<d<<"----------------- ADD AN VARIABLE"<<endl;
    if(d>1.05) { s.add_integer_variable(new PrimerVariable(B, C));
      return variable_found;
    }
    no_more_pricing=true;
    return no_variable_found;
  };
};

int main() {
  // Make Input

  node PN[P];
  node TN[T];

  graph G;
  random_source RS;
  double p;


  for(int i=0; i<P; i++) PN[i]=G.new_node();

  for(int j=0; j<T; j++) {
    TN[j]=G.new_node();
    for(int i=0; i<P; i++) {
      RS>>p;
      if(p<=Pr) G.new_edge(PN[i],TN[j]);
    }
  };
  

  // Optimize

  node_array<int> PNN(G);
  for(int i=0; i<P; i++) PNN[PN[i]]=i;
  for(int j=0; j<T; j++) PNN[TN[j]]=-1;

  ILP_Problem ILP(Optsense_Min); //, true);

  cons CS[P];
  for(int i=0; i<P; i++) CS[i]=ILP.add_basic_constraint(Greater,1);

  ILP.add_integer_variable(new PrimerVariable(CS));

  ILP.add_sym_constraint(new PrimerPricer(G, CS, PNN));
    
  ILP.optimize();

  cout<<"OPTIMIZED\n";

  return 0;

}

---