DepBound.cpp 5.86 KB
Newer Older
1
2
#include <iostream>

EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
3
4
#include "DepBound.h"

5
6
using namespace std;

7
DepBound::DepBound(const AlgOptions & options) {
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
8
  verbosity = options.asInt("verbosity", 0);
9
  //  firstlimit = options.asInt("firstlimit", 0); 
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
10
  instance = nullptr; 
11
  mode = options.asString("mode", "normal"); 
12
  outputInteger=options.isPresent("outint");
13
  shareKey = options.asString("share", "");
14
  bVersion = options.isPresent("bversion");
15
  integerSolution = false; 
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
16
17
18
19
}

void DepBound::clear() {
  env.end();
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
20
  env=IloEnv(); 
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
21
22
23
  isRemoved.clear();
}

24
void DepBound::init(Instance& ins) {
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
25
26
27
  if(instance) clear();
  instance = &ins; 
  
28
  nbWorkerTypes = instance->nbWorkerTypes;
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
29
30
31
32
33
34
35
36
37
  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); 

EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
38
39
40
41
42
  if(verbosity >= 3) {
    cerr << "DepBound: writing constraints." << endl;
    cerr << "          task assignment constraints. "<< endl; 
  }
  
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
43
  // Each task is performed on only one resource
44
  for(int i = 0; i < nbTasks; i++) {
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
45
46
47
48
49
50
51
    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;
  }

EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
52
  if(verbosity >= 3)
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
53
    cerr << "          Global load constraint." << endl;
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
54
  
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
55
    //Global load constraint
56
  for(int j = 0; j < nbWorkerTypes; j++) {
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
57
    IloExpr e(env);
58
    for(int i = 0; i < nbTasks; i++) {
59
60
61
62
63
64
      if(instance->isValidType(j, i)) {
	e += wType[i][j] * instance->execType(j, i);
      }
      else {
	idc.add(wType[i][j] == 0); 
      }
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
65
66
67
68
69
    }
    idc.add(e / instance->nbWorkers[j] <= load);
    e.end();
  }

EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
70
71
72
  if(verbosity >= 3)
    cerr << "          Computing ending time expressions." <<endl;
  
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
73
  execTime = IloExprArray(env, nbTasks); 
74
  for(int i = 0; i < nbTasks; i++){ 
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
75
    execTime[i] = IloExpr(env);
76
    for(int j = 0; j < nbWorkerTypes; j++) 
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
77
78
      if(instance->isValidType(j, i)) 
	execTime[i] += wType[i][j] * instance->execType(j, i);
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
79
80
  }

EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
81
82
83
  if(verbosity >= 3)
    cerr << "          Dependency constraints." << endl;
  
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
84
  // Dependencies 
85
  for(int i = 0; i < nbTasks; i++) {
86
    for(auto prec : instance->dependencies[i]) {
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
87
88
89
90
      idc.add(startTime[i] >= startTime[prec] + execTime[prec]);
    }
    idc.add(load >= startTime[i] + execTime[i]);
  }
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
91
92
93
94

  if(verbosity >= 3)
    cerr << "          Done." << endl; 
  
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
95
96
97
98
99
100
  // Objective function & params
  objective = IloMinimize(env, load);
  idc.add(objective);
  idcCplex = IloCplex(idc);
  if(verbosity < 5) 
    idcCplex.setOut(env.getNullStream());
101
102
103
104
105
  if(mode == "concurrent") {
    if(verbosity >= 4)
      cout << "DepBound: setting concurrent mode." << endl; 
    idcCplex.setParam(IloCplex::RootAlg, IloCplex::Concurrent); 
  }
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
106
107
}

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

117
118
  integerSolution = true; 
  
119
120
121
122
  double result = idcCplex.getBestObjValue();
  return result; 
  
}
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
123
124
125
126
127
128
129

double DepBound::compute () {
  double result = 0; 
  
  if(verbosity >= 6) 
    cout << "Going for solve..." << endl; 
  IloBool b = idcCplex.solve();
130
  if(verbosity >= 5) {
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
131
132
    cout << "solve status: " << b << " " << idcCplex.getStatus() << " " << idcCplex.getCplexStatus() << endl;
  }
133

EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
134
135
136
137
  result = idcCplex.getObjValue();
  return result; 
}

138
void DepBound::finalize() {
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
139
  if(!shareKey.empty()) {
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
    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; 
    }
    
  }
}

162
// To be called after a compute() call
163
vector<int> DepBound::getAllocTasks() {
164
165
166
167
  
  vector<int> result(nbTasks, -1); 
  
  for(int i = 0; i < nbTasks; i++) {
168
169
    if(isRemoved[i]) continue; 
    double val = idcCplex.getValue(wType[i][0]);
170
171
172
173
174
175
    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);
176
      }
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
      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]);
	}
    }
202
  }
203
  
204
205
206
207
  return result; 
}


EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
208
void DepBound::removeTask(int taskID) {
209
  if(verbosity >= 6) 
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
210
211
212
213
214
    cout << "Removing task " << taskID << endl; 
  isRemoved[taskID] = true; 
  onlyOnce[taskID].setBounds(0, 0);
}
void DepBound::restoreTask(int taskID) {
215
  if(verbosity >= 6) 
EYRAUD-DUBOIS Lionel's avatar
EYRAUD-DUBOIS Lionel committed
216
217
218
219
220
221
    cout << "Restoring task " << taskID << endl; 
  assert(isRemoved[taskID]);
  isRemoved[taskID] = false; 
  onlyOnce[taskID].setBounds(1, 1); 
}