tpp2.c

#line 2 "tpp2.lw"
#include<LEDA/graph.h>
#include<scil/scil.h>

using namespace LEDA;
using namespace SCIL;
using namespace std;

//#include"cp_cuts.h"

int** D;

class trip {
  public:
  int* C;
  int a,h;
  int H;
  int s;
  int id;
  int l;

  public:
  trip() {};

  trip(int H_, int h_, int s_, list<int>& c, int id_) {
    H=H_;
    s=s_;
    a=c.size();
    C=new int[a];
    int i, j=0;
    forall(i, c) {
      C[j]=i;
      j++;
    };
    h=h_;
    id=id_;
    l=0; j=H;
    if(c.size()!=0) {
      forall(i,c) {
        l+=D[j][i];
        j=i;
      };
      l+=D[j][H];
    };
  }

  bool home(int i) {
    return (i>=a+s) && (i<a+h+s);
  };

  int number() {
    return id;
  };

  int length() {
    return l;
  };

  int city(int i) {
    if(i<s) return -1;
    i-=s;
    if(i>=a+h) return -1;
    if(i>=a) return H;
    return C[i];
  };

  void print() const {
    cout<<s<<" start : "<<H<<" home :";
    for(int i=0; i<a; i++) cout<<C[i]<<" ";
    for(int i=0; i<h; i++) cout<<H<<" ";
  };
};

list<int>** L1, **L2, **L3, **L4;

void list_append(list<trip>& L, trip t) {
  L.append(t);
  cout<<L.size()<<" : ";
  t.print();cout<<endl;
  for(int i=t.s; i<t.s+t.a+t.h; i++) {
    L1[t.H][i].append(t.number());
  };
  for(int i=t.s+t.a; i<t.s+t.a+t.h; i++) {
    L2[t.H][i].append(t.number());
  };
  for(int i=t.s; i<t.s+t.a; i++) {
    L3[t.city(i)][i].append(t.number());
    L4[t.H][t.city(i)].append(t.number());
  };
};

void generate_trip(list<trip>& L, list<int>& T, bool* B, int U, int n, int H) {
  for(int i=0; i<n; i++) if(B[i]==false) {
    T.append(i); B[i]=true;
    for(int j=1; j<=U; j++) {
      for(int s=0; s<2*(n-1)-T.size()-j+1; s++) {
        list_append(L, trip(H, j, s, T, L.size()));
      };
    }
    list_append(L, trip(H, 0, 2*(n-1)-T.size(), T, L.size()));
    if(T.size()<U) generate_trip(L, T, B, U, n, H);
    B[i]=false; T.pop_back();
  };
};

list<trip> L;
var_map<int> VM;
int n, U;

class sc : public sym_constraint {
 public:
  status separate(subproblem& s) {
    /*
    trip t; double d;
    double D[n][2*n-2][n];

    for(int i=0; i<n; i++) for(int j=0; j<n; j++) for(int l=0; l<2*n-2; l++)
      D[i][l][j]=0;

    forall(t, L) {
      d=s.value(VM[t.number()]);
      if(d>0) {
        for(int i=t.s; i<t.s+t.a+t.h; i++) {
          D[t.H][i][t.city(i)]+=d;
        };
      };
    };

    for(int i=0; i<n; i++) {
      cout<<"\n"<<i<<" city\n";
      for(int j=0; j<n; j++) {
        cout<<"\n"<<j<<": ";
        for(int l=0; l<2*n-2; l++) {
          cout<<D[i][l][j]<<" ";
        };
      };
    };
    cout<<endl;
    */
    return no_constraint_found;
  };
};
      

int main() {
  
  ifstream is("data.txt");

  is>>n;
  is>>U;
  cout<<n<<" cities\n";
  cout<<U<<" succesive\n";

  D=new int*[n];
  for(int i=0; i<n; i++) D[i]=new int[n];

  L1=new list<int>*[n];
  L2=new list<int>*[n];
  L3=new list<int>*[n];
  L4=new list<int>*[n];

  for(int i=0; i<n; i++) {
    L1[i]=new list<int>[2*n-2];
    L2[i]=new list<int>[2*n-2];
    L3[i]=new list<int>[2*n-2];
    L4[i]=new list<int>[n];
  };

  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      is>>D[i][j];
      cout<<D[i][j]<<" ";
    }
    cout<<endl;
  }

  bool B[n];
  for(int i=0; i<n; i++) B[i]=false;
  list<int> T;
  
  for(int i=0; i<n; i++) {
    B[i]=true;
    for(int j=1; j<=U; j++) {
      list_append(L, trip(i, j, 0, T, L.size()));
    };
    generate_trip(L, T, B, U, n, i);
    cout<<L.size()<<" variables\n";
    B[i]=false;
  };

  cout<<L.size()<<" L.size()\n";

  ILP_Problem IP(Optsense_Min);

  //cp_cuts* CPC=new cp_cuts;

  cons c; 

  //var_map<int> VM;
  trip t;
  forall(t, L) {
    VM[t.number()]=IP.add_variable(t.length(), 0,1, Vartype_Integer);
  };

  cout<<L.size()<<" L.size()\n";
  int k;
  for(int i=0; i<n; i++) {
    for(int t=0; t<2*n-2; t++) {
      row r1;
      forall(k, L1[i][t]) r1+=(row) VM[k];
      c=IP.add_basic_constraint(r1==1);
      //CPC->add_sym_constraint(new cp_basic_constraint(c));
      row r2;
      forall(k, L2[i][t]) r2+=(row) VM[k];
      forall(k, L3[i][t]) r2-=(row) VM[k];
      c=IP.add_basic_constraint(r2==0);
      //CPC->add_sym_constraint(new cp_basic_constraint(c));
    }
    for(int j=0; j<n; j++) if(j!=i) {
      row r3;
      forall(k, L4[i][j]) r3+=(row) VM[k];
      c=IP.add_basic_constraint(r3 == 1);
      //CPC->add_sym_constraint(new cp_basic_constraint(c));
    };
  }

  for(int i=0; i<n; i++) {
    for(int k=0; k<n; k++) if(k!=i) {
      for(int l=0; l<2*n-4; l++) {
        row r;
        forall(t, L) {
          if((t.H==i) && (t.city(l)!=i) && (t.city(l+1)!=i)
             && (t.city(l)!=-1) && (t.city(l+1)!=-1)) 
            r+=(row) VM[t.number()];
          if((t.H==k) && ((t.city(l)==i) || (t.city(l+1)==i))
             && (t.city(l+2)!=k))
            r+=(row) VM[t.number()];
          if((t.H!=i) && (t.H!=k) && ((t.city(l)==i) || (t.city(l+1)==i))
             && (t.city(l+2)==k))
            r+=(row) VM[t.number()];
        };
        c=IP.add_basic_constraint(r<=1);
        //CPC->add_sym_constraint(new cp_basic_constraint(c));
      };
    };
  };
 
  row sr;
  forall(t, L) {
    if((t.H==0) && (t.city(0)==0)) sr+=(row) VM[t.number()];
    if((t.H==0) && (t.city(2*n-3)==0)) sr-=(row) VM[t.number()];
  };
  c=IP.add_basic_constraint(sr<=0);
  //CPC->add_sym_constraint(new cp_basic_constraint(c));

  //IP.add_sym_constraint(CPC);
  //IP.add_sym_constraint(new sc());

  IP.optimize();

  int D[n][2*n-2];
  //trip t;
  forall(t, L) {
    if(IP.get_solution(VM[t.number()])>0.01) {
      for(int i=t.s; i<t.s+t.a+t.h; i++) {
        D[t.H][i]=t.city(i);
      }
      t.print();
      cout<<"\n Solution: "<<IP.get_solution(VM[t.number()])<<endl;
      cout<<t.number()<<" number\n";
    }
  };

  for(int i=0; i<n; i++) {
    for(int j=0; j<2*n-2; j++) {
      cout<<D[i][j]<<" ";
    };
    cout<<endl;
  };

}

---