DepBound.cpp

#include <iostream>

#include "DepBound.h"

using namespace std;

DepBound::DepBound(const AlgOptions & options) {
  verbosity = options.asInt("verbosity", 0);
  //  firstlimit = options.asInt("firstlimit", 0); 
  instance = nullptr; 
  mode = options.asString("mode", "normal"); 
  outputInteger=options.isPresent("outint");
  shareKey = options.asString("share", "");
  bVersion = options.isPresent("bversion");
  integerSolution = false; 
}

void DepBound::clear() {
  env.end();
  env=IloEnv(); 
  isRemoved.clear();
}

void DepBound::init(Instance& ins) {
  if(instance) clear();
  instance = &ins; 
  
  nbWorkerTypes = instance->nbWorkerTypes;
  nbTasks = instance->nbTasks;
  
  idc = IloModel(env); 
  wType = NumVarMatrix(env, nbTasks);
  isRemoved.resize(nbTasks); 
  startTime = IloNumVarArray(env, nbTasks, 0.0, IloInfinity, ILOFLOAT); 
  load = IloNumVar(env);
  onlyOnce = IloRangeArray(env, nbTasks); 

  if(verbosity >= 3) {
    cerr << "DepBound: writing constraints." << endl;
    cerr << "          task assignment constraints. "<< endl; 
  }
  
  // Each task is performed on only one resource
  for(int i = 0; i < nbTasks; i++) {
    wType[i] = IloNumVarArray(env, nbWorkerTypes, 0.0, 1.0, ILOFLOAT);
    IloRange r = (IloSum(wType[i]) == 1); 
    onlyOnce[i] = r; 
    idc.add(r);
    isRemoved[i] = false;
  }

  if(verbosity >= 3)
    cerr << "          Global load constraint." << endl;
  
    //Global load constraint
  for(int j = 0; j < nbWorkerTypes; j++) {
    IloExpr e(env);
    for(int i = 0; i < nbTasks; i++) {
      if(instance->isValidType(j, i)) {
	e += wType[i][j] * instance->execType(j, i);
      }
      else {
	idc.add(wType[i][j] == 0); 
      }
    }
    idc.add(e / instance->nbWorkers[j] <= load);
    e.end();
  }

  if(verbosity >= 3)
    cerr << "          Computing ending time expressions." <<endl;
  
  execTime = IloExprArray(env, nbTasks); 
  for(int i = 0; i < nbTasks; i++){ 
    execTime[i] = IloExpr(env);
    for(int j = 0; j < nbWorkerTypes; j++) 
      if(instance->isValidType(j, i)) 
	execTime[i] += wType[i][j] * instance->execType(j, i);
  }

  if(verbosity >= 3)
    cerr << "          Dependency constraints." << endl;
  
  // Dependencies 
  for(int i = 0; i < nbTasks; i++) {
    for(auto prec : instance->dependencies[i]) {
      idc.add(startTime[i] >= startTime[prec] + execTime[prec]);
    }
    idc.add(load >= startTime[i] + execTime[i]);
  }

  if(verbosity >= 3)
    cerr << "          Done." << endl; 
  
  // Objective function & params
  objective = IloMinimize(env, load);
  idc.add(objective);
  idcCplex = IloCplex(idc);
  if(verbosity < 5) 
    idcCplex.setOut(env.getNullStream());
  if(mode == "concurrent") {
    if(verbosity >= 4)
      cout << "DepBound: setting concurrent mode." << endl; 
    idcCplex.setParam(IloCplex::RootAlg, IloCplex::Concurrent); 
  }
}

double DepBound::tryHard(int timeLimit) {
  // Assumption: the set of active tasks has already been used 
  // in a previous compute()
  for(int i = 0; i < nbTasks; i++) 
    idc.add(IloConversion(env, wType[i], ILOBOOL));
  
  idcCplex.setParam(IloCplex::TiLim, timeLimit);
  idcCplex.solve();

  integerSolution = true; 
  
  double result = idcCplex.getBestObjValue();
  return result; 
  
}

double DepBound::compute () {
  double result = 0; 
  
  if(verbosity >= 6) 
    cout << "Going for solve..." << endl; 
  IloBool b = idcCplex.solve();
  if(verbosity >= 5) {
    cout << "solve status: " << b << " " << idcCplex.getStatus() << " " << idcCplex.getCplexStatus() << endl;
  }

  result = idcCplex.getObjValue();
  return result; 
}

void DepBound::finalize() {
  if(!shareKey.empty()) {
    instance->extraData.insert(shareKey + "[alloc]",
			       new vector<int>(getAllocTasks()) );
  }

  if(integerSolution && outputInteger) {
    vector<double> starts(nbTasks); 
    vector<double> ends(nbTasks); 
    cout << "id type start duration end "<< endl; 
    for(int i = 0; i < nbTasks; i++) {
      if(isRemoved[i]) continue; 
      double s = idcCplex.getValue(startTime[i]); 
      int type = -1; 
      for (int j = 0; j < nbWorkerTypes; j++) 
	if(idcCplex.getValue(wType[i][j]) >= 0.75)
	  type = j; 
      cout << i << " " << type << " " << s << " " << instance->execType(type, i) << " " << 
	s + instance->execType(type, i) << endl; 
    }
    
  }
}

// To be called after a compute() call
vector<int> DepBound::getAllocTasks() {
  
  vector<int> result(nbTasks, -1); 
  
  for(int i = 0; i < nbTasks; i++) {
    if(isRemoved[i]) continue; 
    double val = idcCplex.getValue(wType[i][0]);
    result[i] = 0;
    if(bVersion) {
      // Rounding from algorithms in https://arxiv.org/abs/1912.03088 
      if (instance->nbWorkerTypes > 2) {
	cerr << "B Version of HLP only works with two worker types" << endl;
	throw(1);
      }
      int largestWorkers = max(instance->nbWorkers[0], instance->nbWorkers[1]);
      int smallestWorkers = min(instance->nbWorkers[0], instance->nbWorkers[1]);
      double r = ((double)smallestWorkers)/((double)largestWorkers);
      double unsurb;
      if (r < 1) {
	unsurb = 1/(1 + sqrt((2-r)/(1-r)));
      } else {
	unsurb = 0.0;
      }
      if(idcCplex.getValue(wType[i][0]) <= unsurb) {
	result[i] = 1;
      } else if (idcCplex.getValue(wType[i][1] <= unsurb)) {
	result[i] = 0;
      } else {
	result[i] = 0;
	if(instance->execType(0, i) > instance->execType(1, i))
	  result[i] = 1;
      }
    } else {
      for(int j = 1; j < instance->nbWorkerTypes; j++) 
	if(idcCplex.getValue(wType[i][j]) > val) {
	  result[i] = j;
	  val = idcCplex.getValue(wType[i][j]);
	}
    }
  }
  
  return result; 
}


void DepBound::removeTask(int taskID) {
  if(verbosity >= 6) 
    cout << "Removing task " << taskID << endl; 
  isRemoved[taskID] = true; 
  onlyOnce[taskID].setBounds(0, 0);
}
void DepBound::restoreTask(int taskID) {
  if(verbosity >= 6) 
    cout << "Restoring task " << taskID << endl; 
  assert(isRemoved[taskID]);
  isRemoved[taskID] = false; 
  onlyOnce[taskID].setBounds(1, 1); 
}