qap.cc

#include<scil/scil.h>
#include<scil/core/monomial.h>

#include<iostream>
#include<string>


using std::cout;
using std::endl;
using std::ifstream;
using std::cerr;


#define INPATH ""


using namespace SCIL;


void  readcoeff(char* infile, double**& matrix1, double**& matrix2, int& size) {
   std::string path(INPATH);
   path += infile;
   ifstream file(path.c_str());
   if(file.fail()) {
      cerr << "in path " << path << endl;
      cerr<<"is no "<< infile<< endl;
      exit(1);
   }
   char buf[1024];
   while(file.peek() != '#')
      file.getline(buf, 1024);

   char c;
   file >> c;
   file >> size;
   matrix1 = new double*[size];
   for(int i=0; i<size; i++) {
      matrix1[i] = new double[size];
      for(int j=0; j<size; j++) {
         file >>matrix1[i][j];
      }
   }
   matrix2 = new double*[size];
   for(int i=0; i<size; i++) {
      matrix2[i] = new double[size];
      for(int j=0; j<size; j++) {
         file >>matrix2[i][j];
      }
   }
}


int main(int argc, char ** argv) {
   if(argc != 2) {
      cerr<< "wrong number of input parameters!"<< endl;
      return 1;
   }

   double **matrix1=NULL;
   double **matrix2=NULL;
   int size;

   //read the coefficients from file
   readcoeff(argv[1], matrix1, matrix2, size);

   //create ILP and add binary variables
   ILP_Problem IP(Optsense_Min);
   var **variablen= new var*[size];
   for(int i=0; i<size; i++) {
      variablen[i] = new var[size];
      for(int j=0; j<size; j++) {
         variablen[i][j] = IP.add_binary_variable(0);
      }
   }

   //create objective function
   for(int i=0; i<size; i++) {
      for(int j=0; j<size; j++) {
         for(int k=0; k<size; k++) {
            for(int l=0; l<size; l++) {
               if(((i!=k) && (j!=l)) || ((i==k) && (j==l))) {
                  if( matrix1[i][k] != 0. && matrix2[j][l] != 0. )
                     IP.add_polynomial(variablen[i][j]*variablen[k][l]*(matrix1[i][k]*matrix2[j][l]));
               }
            }
         }
      }
   }


   //add basic constraints necessary for QAP
   row r;
   for(int i=0; i<size; i++) {
      r=0;
      for(int j=0; j<size; j++) {
         r+=variablen[i][j];
      }
      IP.add_basic_constraint(r==1,Static);
   }
   for(int i=0; i<size; i++) {
      r=0;
      for(int j=0; j<size; j++) {
         r+=variablen[j][i];
      }
      IP.add_basic_constraint(r==1,Static);
   };
   IP.set_qrType(SQK2_SQK3);

   IP.optimize();

   //print solution
   for(int i=0; i<size; i++) {
      for(int j=0; j<size; j++) {
         cout<<IP.get_solution(variablen[i][j]);
      }
      cout << endl;
   };

   for(int i=0; i<size; i++){
      delete[] variablen[i];
      delete[] matrix1[i];
      delete[] matrix2[i];
   }
   delete[] variablen;
   delete[] matrix1;
   delete[] matrix2;
}

---