00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00015
00016
00017
00018
00020
00021 #include "OddCyclesSeparator.hh"
00022 #include "Graph.hh"
00023 #include "OddCycleConstraint.hh"
00024 #include "ShortestPathCalculator.hh"
00025 #include "StableSetLPSolution.hh"
00026 #include "StableSetMaster.hh"
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 OddCyclesSeparator::OddCyclesSeparator(ABA_MASTER *master,
00039 StableSetLPSolution *solution,
00040 Graph *theGraph, bool flag):
00041 ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 300),
00042 master_(master),
00043 itsGraph(theGraph),
00044 lpSolution(solution),
00045 lifting(flag)
00046 {
00047 }
00048
00049
00050
00051
00052
00053 OddCyclesSeparator::~OddCyclesSeparator ()
00054 {
00055 for(int i=cycles.size()-1; i>=0; i--) {
00056 delete [] cycles[i];
00057 }
00058 }
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075 void OddCyclesSeparator::separate() {
00076
00077
00078
00079
00080
00081
00082 int i, j, k, l, m;
00083 int numberOfNodes = lpSolution->nVarCon();
00084
00085 int numberOfNonBinaryNodes = 0;
00086
00087 vector<int> index(numberOfNodes);
00088
00089
00090
00091 vector<int> indexOfNonBinaryNode(numberOfNodes);
00092
00093
00094
00095 int node;
00096 int element;
00097 int size;
00098
00099 int sizeOfList;
00100
00101 int adjazensListSmall[numberOfNodes * (numberOfNodes - 1)];
00102 int *adjazensPointer;
00103
00104
00105 int *adjazensList;
00106
00107 long numberOfEdges = 0;
00108
00109 double *weight = new double[numberOfNodes * (numberOfNodes - 1)];
00110 double *solutionValue = lpSolution->zVal();
00111 double *edgeWeight;
00112
00113 double eps = master_->machineEps();
00114
00115
00116
00117
00118
00119
00120
00121 for (i=0; i<numberOfNodes; i++) {
00122 if ((solutionValue[i] > eps)
00123 && (solutionValue[i] < (1 - eps))
00124 ) {
00125 index[i] = numberOfNonBinaryNodes;
00126 indexOfNonBinaryNode[numberOfNonBinaryNodes] = i;
00127 numberOfNonBinaryNodes++;
00128 }
00129 else {
00130 index[i] = -1;
00131 }
00132 }
00133
00134
00135 adjazensPointer = new int[2*numberOfNonBinaryNodes+1];
00136 adjazensPointer[0] = 0;
00137
00138 for (i=0; i<numberOfNonBinaryNodes; i++) {
00139 node = indexOfNonBinaryNode[i];
00140 size = itsGraph->adjacentListSize(node);
00141 sizeOfList = 0;
00142 for (j=0; j<size; j++) {
00143 element = itsGraph->adjacentListElement(node, j);
00144 if (index[element] != -1) {
00145 adjazensListSmall[numberOfEdges] = index[element];
00146 weight[numberOfEdges++] = 0.5 * (1 - solutionValue[node] -
00147 solutionValue[indexOfNonBinaryNode[index[element]]]);
00148 sizeOfList++;
00149 }
00150 }
00151 if (sizeOfList == 0) {
00152
00153 index.erase(index.begin() + indexOfNonBinaryNode[i]);
00154 indexOfNonBinaryNode.erase(indexOfNonBinaryNode.begin() + i);
00155 numberOfNonBinaryNodes--;
00156 i--;
00157 continue;
00158 }
00159 if (i < (numberOfNonBinaryNodes - 1)) {
00160 adjazensPointer[i+1] = adjazensPointer[i] + sizeOfList;
00161 }
00162 }
00163
00164
00165
00166
00167 adjazensList = new int[2*numberOfEdges];
00168 edgeWeight = new double[2*numberOfEdges];
00169
00170
00171 for (i=0; i < numberOfNonBinaryNodes; i++) {
00172 adjazensPointer[i + numberOfNonBinaryNodes] =
00173 adjazensPointer[i] + numberOfEdges;
00174 }
00175 adjazensPointer[2*numberOfNonBinaryNodes] = numberOfEdges*2;
00176
00177
00178 for (i=0; i < numberOfEdges; i++ ) {
00179 adjazensList[i] = numberOfNonBinaryNodes + adjazensListSmall[i];
00180 adjazensList[i + numberOfEdges] = adjazensListSmall[i];
00181
00182 edgeWeight[i] = weight[i] + eps * 100;
00183 edgeWeight[i + numberOfEdges] = edgeWeight[i];
00184 }
00185
00186
00187 index.clear();
00188
00189
00190
00191
00192
00193 int predNode[2*numberOfNonBinaryNodes];
00194
00195 int currentNode;
00196 int smallGraphNode;
00197
00198 int completeGraphNode;
00199
00200 int oddCycle[numberOfNonBinaryNodes];
00201
00202 int start = ((StableSetMaster *)master_)->getRandomNumber(
00203 numberOfNonBinaryNodes);
00204 double shortestPathValue;
00205
00206 double tolerance = ((StableSetMaster *)master_)->m_minAbsViolationCycle;
00207 bool inOddCycle[numberOfNonBinaryNodes];
00208
00209
00210 int marked[numberOfNonBinaryNodes];
00211 int marker;
00212 bool found;
00213 double weightOfCycle;
00214 OddCycleConstraint *oddCycleConstr;
00215
00216
00217
00218 ShortestPathCalculator* shortestPath =
00219 new ShortestPathCalculator(2*numberOfNonBinaryNodes,
00220 2*numberOfEdges,
00221 adjazensPointer,
00222 adjazensList,
00223 edgeWeight,
00224 0.5,
00225 eps);
00226
00227
00228
00229
00230
00231 for (i=0; i<numberOfNonBinaryNodes; i++) {
00232 inOddCycle[i] = false;
00233 marked[i] = -1;
00234 }
00235
00236 j = start;
00237 for (i=j; i<j+numberOfNonBinaryNodes; i++) {
00238 start = i % numberOfNonBinaryNodes;
00239
00240
00241 if (inOddCycle[start] == true) {
00242 continue;
00243 }
00244
00245 shortestPathValue = shortestPath->calculateShortestPath(
00246 start, start + numberOfNonBinaryNodes, predNode);
00247
00248
00249 if (shortestPathValue > 0.5 - eps) {
00250 continue;
00251 }
00252
00253
00254 currentNode = start + numberOfNonBinaryNodes;
00255 size = 0;
00256 weightOfCycle = 0;
00257 while (currentNode != start) {
00258 node = predNode[currentNode];
00259 currentNode = node;
00260 smallGraphNode = currentNode % numberOfNonBinaryNodes;
00261
00262 if (marked[smallGraphNode] != -1) {
00263 weightOfCycle = 0;
00264 marker = marked[smallGraphNode];
00265
00266 for (k=0; k<marker; k++) {
00267 marked[oddCycle[k]] = -1;
00268 }
00269 for ( ; k<size; k++) {
00270 node = oddCycle[k];
00271 oddCycle[k - marker] = node;
00272 completeGraphNode = indexOfNonBinaryNode[node];
00273 weightOfCycle += solutionValue[completeGraphNode];
00274 }
00275
00276 size -= marker;
00277 break;
00278 }
00279 else {
00280 oddCycle[size] = smallGraphNode;
00281 marked[smallGraphNode] = size;
00282 completeGraphNode = indexOfNonBinaryNode[smallGraphNode];
00283 weightOfCycle += solutionValue[completeGraphNode];
00284 size++;
00285 }
00286 }
00287
00288 if (weightOfCycle < 0.5*(size-1) + tolerance) {
00289 for(k=0; k<size-1; k++) {
00290 marked[oddCycle[k]] = -1;
00291 }
00292 continue;
00293 }
00294
00295 found = true;
00296 while (found) {
00297
00298 for (k=0; k<size-1; k++) {
00299 node = oddCycle[k];
00300
00301
00302 found = false;
00303 l = k+1;
00304 while (l<size && !found && (l+1)%size!=k) {
00305
00306 if (!(1 & (l-k))) {
00307 element = oddCycle[l];
00308 m = adjazensPointer[node];
00309
00310 while (m<adjazensPointer[node+1] && !found) {
00311 if (adjazensListSmall[m] == element) {
00312
00313 found = true;
00314 weightOfCycle = 0;
00315
00316 for (m=0; m<k; m++) {
00317 marked[oddCycle[m]] = -1;
00318 }
00319 for ( ; m<=l; m++) {
00320 node = oddCycle[m];
00321 oddCycle[m-k] = node;
00322 completeGraphNode =
00323 indexOfNonBinaryNode[node];
00324 weightOfCycle +=
00325 solutionValue[completeGraphNode];
00326 }
00327 for ( ; m<size; m++) {
00328 marked[oddCycle[m]] = -1;
00329 }
00330 size = l - k + 1;
00331 break;
00332
00333 }
00334 m++;
00335 }
00336 if (found) {
00337 break;
00338 }
00339 if (weightOfCycle < 0.5*(size-1) + tolerance) {
00340 break;
00341 }
00342 }
00343 l++;
00344 }
00345 if (weightOfCycle < 0.5*(size-1) + tolerance) {
00346 break;
00347 }
00348 if (found) {
00349 break;
00350 }
00351 }
00352 if (weightOfCycle < 0.5*(size-1) + tolerance) {
00353 break;
00354 }
00355 }
00356
00357
00358
00359
00360 if (size == 3) {
00361 for(k=0; k<3; k++) {
00362
00363 marked[oddCycle[k]] = -1;
00364
00365 inOddCycle[oddCycle[k]] = true;
00366
00367 completeGraphNode = indexOfNonBinaryNode[oddCycle[k]];
00368
00369 clique.push_back(completeGraphNode);
00370 }
00371 }
00372 else {
00373
00374
00375
00376
00377 if(lifting) {
00378
00379 int *aCycle = new int[size+1];
00380
00381 aCycle[0] = size+1;
00382
00383
00384 for(k=0; k<size; k++) {
00385
00386 marked[oddCycle[k]] = -1;
00387
00388 inOddCycle[oddCycle[k]] = true;
00389 completeGraphNode = indexOfNonBinaryNode[oddCycle[k]];
00390 aCycle[k+1] = completeGraphNode;
00391
00392 }
00393 cycles.push_back(aCycle);
00394 }
00395 else {
00396
00397
00398
00399
00400 for(k=0; k<size; k++) {
00401
00402 marked[oddCycle[k]] = -1;
00403 inOddCycle[oddCycle[k]] = true;
00404 completeGraphNode = indexOfNonBinaryNode[oddCycle[k]];
00405 oddCycle[k] = completeGraphNode;
00406 }
00407 oddCycleConstr = new OddCycleConstraint(master_, size, oddCycle,
00408 itsGraph);
00409 cutFound(oddCycleConstr);
00410
00411 }
00412 }
00413 }
00414
00415
00416
00417 delete shortestPath;
00418 delete [] adjazensPointer;
00419 delete [] adjazensList;
00420 delete [] edgeWeight;
00421 delete [] weight;
00422
00423 }
00424
00425
00426
00427
00428
00429 int OddCyclesSeparator::getSizeOfClique() const {
00430 return clique.size();
00431 }
00432
00433
00434
00435
00436
00437 int OddCyclesSeparator::getCliqueElement(int i) const {
00438 return clique[i];
00439 }
00440
00441
00442
00443
00444
00445 int OddCyclesSeparator::getNumberOfOddCycles() const {
00446 return cycles.size();
00447 }
00448
00449
00450
00451
00452
00453 int *OddCyclesSeparator::getOddCycle(int i) {
00454 return cycles[i];
00455 }
00456
00457
00458