//*********************************************************************************************
//      SUBROTINA PARA SOLUCAO DO SUB-PROBLEMA DE BENDERS'
//      SUB-PROBLEMA DUAL MONTADO SOBRE O QAP
//*********************************************************************************************
double solve_slave(int n, int *d, double **x, double *v, double *u, double *r, double *alfa);
double solve_slave(int n, int *d, double **x, double *v, double *u, double *r, double *alfa){

int i, j, k, l, n2, n3;
double sup;

n2 = n*n;
n3 = n2*n;
sup = 0.0;
// complementary slackness
for(k=1;k<=n;k++){
    for(l=(k+1);l<=n;l++){
      alfa[(k-1)*n+l] = 0.0;
            for(j=1;j<=n;j++){
	            for(i=1;i<=n;i++){
		    alfa[(k-1)*n+l]+= (d[(k-1)*n3+(i-1)*n2+(l-1)*n+j]+d[(l-1)*n3+(j-1)*n2+(k-1)*n+i])*x[k][i]*x[l][j];
		    }
	    }
      sup+= alfa[(k-1)*n+l];	    
    }
}


// construindo ambiente de programacao matematica
IloEnv env;
IloModel mod(env);
IloNumVarArray vcpx(env, n3+1, 0, +IloInfinity, ILOFLOAT);
IloNumVarArray ucpx(env, n3+1, 0, +IloInfinity, ILOFLOAT);
IloNumVarArray rcpx(env, n3+1, 0, +IloInfinity, ILOFLOAT);

IloExpr expr0(env);
for(k=1;k<=n;k++){
    for(l=(k+1);l<=n;l++){
      for(j=1;j<=n;j++){
        expr0-= vcpx[(k-1)*n2+(l-1)*n+j];
      }
      for(i=1;i<=n;i++){
        expr0-= ucpx[(k-1)*n2+(l-1)*n+i];
      }
    }
    for(i=1;i<=n;i++){
      for(j=1;j<=n;j++){
        if(i!=j)expr0-= rcpx[(k-1)*n2+(i-1)*n+j];
      }
    }
}

mod.add(IloMaximize(env,expr0));

// introduzindo restricoes duais

for(k=1;k<=n;k++){
  for(l=(k+1);l<=n;l++){
    for(i=1;i<=n;i++){
      for(j=1;j<=n;j++){
        if(i!=j){
        IloExpr expr5(env);
	expr5 += alfa[(k-1)*n+l];
        expr5 -= vcpx[(k-1)*n2+(l-1)*n+j];
	expr5 -= ucpx[(k-1)*n2+(l-1)*n+i];
        expr5 -= rcpx[(k-1)*n2+(i-1)*n+j];
	expr5 -= rcpx[(l-1)*n2+(j-1)*n+i];
	mod.add(-IloInfinity<=expr5<=(d[(k-1)*n3+(i-1)*n2+(l-1)*n+j]+d[(l-1)*n3+(j-1)*n2+(k-1)*n+i]));
        }
      }
    }
  }
}


// zerando preços onde x[k][i] = 1

for(k=1;k<=n;k++){
    for(i=1;i<=n;i++){
       if(x[k][i] > 0.1) {
           IloExpr expr6(env);
	   for(l=1; l<=n; l++){
	   expr6+= vcpx[(l-1)*n2+(k-1)*n+i];
	   }
	   mod.add(0<=expr6<=0);
           IloExpr expr7(env);
	   for(l=1; l<=n; l++){
	   expr7+= ucpx[(k-1)*n2+(l-1)*n+i];
	   }
	   mod.add(0<=expr7<=0);
           IloExpr expr8(env);
	   for(j=1; j<=n; j++){
	   expr8+= rcpx[(k-1)*n2+(i-1)*n+j];
	   }
	   mod.add(0<=expr8<=0);
       }
    }
}
 
IloCplex cplex(mod);
cplex.setParam(IloCplex::MIPDisplay,0);
cplex.setRootAlgorithm(IloCplex::Network);
//cplex.exportModel("spdualqap.lp");
cplex.solve();

for(k=1;k<=n;k++){
 for(l=(k+1);l<=n;l++){
  for(j=1;j<=n;j++){
   v[(k-1)*n2+(l-1)*n+j] = (double)cplex.getValue(vcpx[(k-1)*n2+(l-1)*n+j]);
  }
 }
}

for(k=1;k<=n;k++){
 for(l=(k+1);l<=n;l++){
  for(i=1;i<=n;i++){
   u[(k-1)*n2+(l-1)*n+i] = (double)cplex.getValue(ucpx[(k-1)*n2+(l-1)*n+i]);
  }
 }
}

for(k=1;k<=n;k++){
 for(i=1;i<=n;i++){
  for(j=1;j<=n;j++){
   if(i!=j)r[(k-1)*n2+(i-1)*n+j] = (double)cplex.getValue(rcpx[(k-1)*n2+(i-1)*n+j]);
  }
 }
}

env.end();
return sup;
}// eof

