00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00015
00016
00017
00018
00020
00021 #include "Preprocessing.hh"
00022 #include "abacus/row.h"
00023 #include "Graph.hh"
00024 #include "StableSetMaster.hh"
00025 #include "StableSetStatistics.hh"
00026
00027
00028 #include "abacus/array.h"
00029 #include "abacus/cplexif.h"
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 Preprocessing::Preprocessing(StableSetMaster *theMaster, Graph *theGraph,
00041 StableSetStatistics *theStatistics):
00042 itsMaster(theMaster),
00043 itsGraph(theGraph),
00044 itsStatistics(theStatistics)
00045 {
00046 }
00047
00048
00049
00050
00051
00052 Preprocessing::~Preprocessing() {
00053 }
00054
00055
00056
00057
00058
00059
00060
00061 void Preprocessing::preprocessing() {
00062
00063 bool fixed = true;
00064 double *sol;
00065
00066
00067
00068
00069 while (fixed) {
00070
00071
00072
00073
00074 fixed = fixVariablesClique();
00075
00076
00077
00078
00079 if (itsGraph->numberOfNodes()) {
00080 sol = solveLP();
00081 fixed = fixVariablesEdgeLP(sol) || fixed;
00082 if (!itsGraph->numberOfNodes()) {
00083 fixed = false;
00084 }
00085
00086 delete [] sol;
00087 }
00088 }
00089
00090 if (itsGraph->numberOfNodes() == 0) {
00091
00092 itsStatistics->solutionFound(3);
00093 }
00094
00095 itsMaster->sortFixedNodes();
00096
00097 }
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111 bool Preprocessing::fixVariablesClique() {
00112
00113 int i, j, k;
00114 bool fixed = false;
00115 bool isClique;
00116 int numberOfNodes = itsGraph->numberOfNodes();
00117 int node;
00118 int size;
00119 vector<int> nodesToCheck(numberOfNodes);
00120
00121 vector<int> fixNodes;
00122
00123
00124 for (i=0; i<itsGraph->numberOfNodes(); i++) {
00125 nodesToCheck[i] = i;
00126 }
00127
00128
00129
00130
00131
00132 while (nodesToCheck.size() != 0) {
00133
00134
00135 node = nodesToCheck.back();
00136 nodesToCheck.pop_back();
00137
00138
00139 size = itsGraph->adjacentListSize(node);
00140
00141 isClique = true;
00142
00143
00144 for (i=0; i<size; i++) {
00145
00146
00147
00148 if (itsGraph->weighted()
00149 && (itsGraph->weight(node)
00150 < itsGraph->weight(itsGraph->adjacentListElement(node,i)))){
00151 isClique = false;
00152 break;
00153 }
00154
00155
00156
00157
00158 for (j=i+1; j<size; j++) {
00159 k = 0;
00160 if (!itsGraph->isMemberOfAdjacentList(
00161 itsGraph->adjacentListElement(node,i),
00162 k, itsGraph->adjacentListElement(node,j))
00163 ) {
00164 i = size;
00165 isClique = false;
00166 break;
00167 }
00168 }
00169 }
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179 if (isClique) {
00180
00181 fixed = true;
00182 fixNodes.resize(size + 1);
00183 fixNodes[0] = node;
00184
00185 for (i=1; i<size + 1; i++) {
00186 fixNodes[i] = itsGraph->adjacentListElement(node, i-1);
00187
00188 k = 0;
00189 while ((k < nodesToCheck.size()) && (nodesToCheck[k] != fixNodes[i])
00190 ) {
00191 k++;
00192 }
00193 if (nodesToCheck[k] == fixNodes[i]) {
00194 nodesToCheck.erase(nodesToCheck.begin() + k);
00195 }
00196
00197 }
00198 sort(fixNodes.begin(), fixNodes.end());
00199
00200
00201 itsMaster->pushFixedNode(itsGraph->translateNode(node));
00202
00203
00204
00205 itsGraph->deleteNodesFromGraph(&fixNodes, &nodesToCheck);
00206 }
00207 }
00208
00209
00210 return (fixed && (itsGraph->numberOfNodes() != 0));
00211
00212 }
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222 double *Preprocessing::solveLP() {
00223
00224
00225
00226
00227
00228
00229 int i,j;
00230 int size;
00231 int numberOfConstraints = itsGraph->numberOfEdges();
00232 int numberOfVariables = itsGraph->numberOfNodes();
00233
00234 ABA_ROW *constraint;
00235
00236 ABA_BUFFER<int> nonZeroElementsBuf(itsMaster, 2);
00237
00238 ABA_ARRAY<int> *nonZeroElements;
00239
00240 ABA_ARRAY<double> *coefficients;
00241
00242
00243 ABA_ARRAY<double> objectiveFunctionCoefficient(itsMaster,
00244 numberOfVariables, 1);
00245
00246 ABA_ARRAY<double> lowerBound(itsMaster, numberOfVariables, 0);
00247
00248 ABA_ARRAY<double> upperBound(itsMaster, numberOfVariables, 1);
00249
00250
00251 ABA_ARRAY<ABA_ROW*> allConstraints(itsMaster, numberOfConstraints);
00252
00253
00254
00255
00256
00257
00258 int cnt = 0;
00259 int element;
00260
00261 for (i=0; i<numberOfVariables; i++) {
00262 size = itsGraph->adjacentListSize(i);
00263 for (j=0; j<size; j++) {
00264 element = itsGraph->adjacentListElement(i,j);
00265 if (element > i) {
00266 nonZeroElementsBuf.push(i);
00267 nonZeroElementsBuf.push(element);
00268 nonZeroElements = new ABA_ARRAY<int>(itsMaster,
00269 nonZeroElementsBuf);
00270 coefficients = new ABA_ARRAY<double>(itsMaster, 2, 1);
00271 nonZeroElementsBuf.clear();
00272
00273
00274 constraint = new ABA_ROW(itsMaster,
00275 2,
00276 (*nonZeroElements),
00277 (*coefficients),
00278 ABA_CSENSE::Less,
00279 1);
00280
00281 allConstraints[cnt] = constraint;
00282 cnt++;
00283
00284 delete nonZeroElements;
00285 delete coefficients;
00286
00287 }
00288 }
00289 }
00290
00291
00292
00293
00294
00295
00296 ABA_CPLEXIF lp(itsMaster);
00297 lp.initialize(ABA_OPTSENSE::Max,
00298 numberOfConstraints,
00299 numberOfConstraints,
00300 numberOfVariables,
00301 numberOfVariables,
00302 objectiveFunctionCoefficient,
00303 lowerBound,
00304 upperBound,
00305 allConstraints);
00306
00307
00308 if (!(ABA_LP::Optimal == lp.optimize(ABA_LP::Primal))) {
00309 itsMaster->err() << "ERROR in Preprocessing::solveLP()." << endl;
00310 itsMaster->err() << "LP could not be dolved to optimality." << endl;
00311 exit(itsMaster->Fatal);
00312 }
00313
00314 double *sol = new double[numberOfVariables];
00315 for (i=0; i<numberOfVariables; i++) {
00316 sol[i] = lp.xVal(i);
00317 }
00318
00319
00320 for (i=numberOfConstraints-1; i>=0; i--) {
00321 delete allConstraints[i];
00322 allConstraints[i] = NULL;
00323 }
00324
00325 return sol;
00326
00327 }
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341 bool Preprocessing::fixVariablesEdgeLP(double *sol) {
00342
00343 int i, j, k;
00344 int numberOfNodes = itsGraph->numberOfNodes();
00345 bool fixed = false;
00346 int node;
00347 bool isElement;
00348
00349
00350 vector<int> fixOne;
00351 vector<int> fixZero;
00352
00353
00354
00355
00356
00357
00358 for (i=0; i<numberOfNodes; i++) {
00359 if ((sol[i] < (1 + itsMaster->machineEps()))
00360 && (sol[i] > (1 - itsMaster->machineEps()))
00361 ) {
00362 fixOne.push_back(i);
00363
00364 for (j=0; j<itsGraph->adjacentListSize(i); j++) {
00365 node = itsGraph->adjacentListElement(i, j);
00366
00367 isElement = false;
00368 for (k=0; k<fixZero.size(); k++) {
00369 if (fixZero[k] == node) {
00370 isElement = true;
00371 break;
00372 }
00373 }
00374 if (!isElement) {
00375 fixZero.push_back(node);
00376 }
00377 }
00378 }
00379 }
00380
00381
00382
00383
00384 if (!fixOne.empty()) {
00385
00386
00387 vector<int> fixNodes(fixOne.size() + fixZero.size());
00388 int size;
00389
00390 size = fixOne.size();
00391 for (i=0; i<size; i++) {
00392 fixNodes[i] = fixOne[i];
00393
00394 itsMaster->pushFixedNode(itsGraph->translateNode(fixOne[i]));
00395 }
00396
00397 for (i=0; i<fixZero.size(); i++) {
00398 fixNodes[size + i] = fixZero[i];
00399 }
00400 sort(fixNodes.begin(), fixNodes.end());
00401
00402
00403 itsGraph->deleteNodesFromGraph(&fixNodes);
00404
00405
00406 itsGraph->fixVariablesFirstLP(fixNodes.size());
00407 fixed = true;
00408 }
00409
00410
00411 return fixed;
00412
00413 }
00414
00415
00416
00417
00418
00419
00420
00421
00422
00423