00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00016
00017
00018
00019
00021
00022 #include "StableSetMaster.hh"
00023 #include "abacus/nonduplpool.h"
00024 #include "Clique.hh"
00025 #include "CliqueConstraint.hh"
00026 #include "EdgeProjection.hh"
00027 #include "Graph.hh"
00028 #include "Node.hh"
00029 #include "Preprocessing.hh"
00030 #include "StableSetStatistics.hh"
00031 #include "StableSetSub.hh"
00032
00033
00034 #include <cstdlib>
00035 #include <string>
00036
00037 #include <iostream>
00038
00039
00040 extern "C"
00041 {
00042 #include <stdio.h>
00043 #include <string.h>
00044 }
00045
00046
00047 #ifdef ABACUS_MATH_CPP
00048 #include <math.h>
00049 #else
00050 extern "C"
00051 {
00052 #include <math.h>
00053 }
00054 #endif
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087 StableSetMaster::StableSetMaster(const char *problemName,
00088 const char *theInequalitiesFileName,
00089 const char *theSmallGraphName):
00090 ABA_MASTER(problemName, true, false, ABA_OPTSENSE::Max)
00091 {
00092
00093
00094
00095
00096
00097 if (problemName == 0) {
00098 err() << "StableSetMASTER::StableSetMASTER(): ";
00099 err() << "problem name is missing." << endl;
00100 exit(Fatal);
00101 }
00102
00103 char *fileName;
00104 if ((problemName[0] == '/')
00105 || ((strlen(problemName) > 1
00106 && (problemName[0] == '.')
00107 && (problemName[1] == '/')))
00108 ){
00109 fileName = new char[strlen(problemName) +1];
00110
00111 sprintf( fileName, "%s", problemName );
00112 }
00113 else {
00114
00115 const char *stableSetLib = getenv("StableSetLIB_DIR");
00116 if (stableSetLib == 0) {
00117 err() << "StableSetMASTER::StableSetMASTER(): environment ";
00118 err() << "variable StableSetLIB_DIR not found." << endl;
00119 exit(Fatal);
00120 }
00121
00122 fileName = new char[strlen(stableSetLib) + strlen(problemName) + 2];
00123
00124 #ifdef ABAUS_VISUAL_CPP
00125 sprintf(fileName, "%s\\%s", stableSetLib, problemName);
00126 #else
00127 sprintf(fileName, "%s/%s", stableSetLib, problemName);
00128 #endif
00129 }
00130
00131
00132
00133
00134
00135 if (theInequalitiesFileName == 0) {
00136 err() << "StableSetMASTER::StableSetMASTER(): ";
00137 err() << "inequalities file name is missing." << endl;
00138 exit(Fatal);
00139 }
00140
00141 char *inequalitiesFileName = new char[strlen(theInequalitiesFileName) + 1];
00142 sprintf(inequalitiesFileName, "%s", theInequalitiesFileName);
00143
00144 ofstream out(inequalitiesFileName);
00145 out.close();
00146
00147
00148 sprintf(smallGraphName, "%s", theSmallGraphName);
00149
00150
00151
00152
00153 readStableSetInputData(fileName, inequalitiesFileName);
00154
00155
00156
00157
00158 theStatistics = new StableSetStatistics;
00159
00160
00161 delete [] fileName;
00162 delete [] inequalitiesFileName;
00163
00164 }
00165
00166
00167
00168
00169
00170 StableSetMaster::~StableSetMaster() {
00171
00172 if (itsGraph->numberOfNodes() != 0) {
00173 delete theProjection;
00174 delete cycleCutPool_;
00175 delete cliqueCutPool_;
00176 delete rankCutPool_;
00177 delete generalCutPool_;
00178 }
00179 delete myCPUTimer;
00180 delete itsGraph;
00181 delete maxCliques;
00182 delete theStatistics;
00183 }
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194 ABA_SUB *StableSetMaster::firstSub() {
00195 return new StableSetSub(this, itsGraph, maxCliques, theProjection,
00196 theStatistics);
00197 }
00198
00199
00200
00201
00202
00203 ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *StableSetMaster::cycleCutPool() {
00204 return cycleCutPool_;
00205 }
00206
00207
00208
00209
00210
00211 ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *StableSetMaster::cliqueCutPool(){
00212 return cliqueCutPool_;
00213 }
00214
00215
00216
00217
00218
00219 ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *StableSetMaster::rankCutPool() {
00220 return rankCutPool_;
00221 }
00222
00223
00224
00225
00226
00227 ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *StableSetMaster::generalCutPool()
00228 {
00229 return generalCutPool_;
00230 }
00231
00232
00233
00234
00235
00236
00237
00238 vector<int> *StableSetMaster::getSolution() {
00239 return &bestSolution;
00240 }
00241
00242
00243
00244
00245
00246
00247
00248 void StableSetMaster::pushFixedNode(int node) {
00249 fixedInStableSet.push_back(node);
00250 }
00251
00252
00253
00254
00255
00256
00257
00258 void StableSetMaster::sortFixedNodes() {
00259 if (!fixedInStableSet.empty()) {
00260 sort(fixedInStableSet.begin(), fixedInStableSet.end());
00261 }
00262 }
00263
00264
00265
00266
00267
00268
00269
00270
00271 int StableSetMaster::fixedNodesToOne() const{
00272 return fixedInStableSet.size();
00273 }
00274
00275
00276
00277
00278
00279 void StableSetMaster::printTime() {
00280 out() << "Current time:" << myCPUTimer->seconds();
00281 out() << ":" << myCPUTimer->centiSeconds() % 100 << endl;
00282 }
00283
00284
00285
00286
00287
00288 void StableSetMaster::startTimer() {
00289 myCPUTimer->start();
00290 }
00291
00292
00293
00294
00295
00296 void StableSetMaster::stopTimer() {
00297 myCPUTimer->stop();
00298 }
00299
00300
00301
00302
00303
00304 char *StableSetMaster::getSmallGraphName() {
00305 return smallGraphName;
00306 }
00307
00308
00309
00310
00311
00312
00313
00314 int StableSetMaster::getRandomNumber(int bound) const {
00315 int aNumber = rand();
00316 double d = (double(aNumber)/RAND_MAX);
00317
00318 return (int)(d*bound);
00319 }
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330 void StableSetMaster::output() {
00331
00332
00333 myCPUTimer->stop();
00334
00335
00336
00337
00338 out() << "\n\nStatistics on preprocessing:\n";
00339 itsGraph->printStatistic();
00340
00341
00342
00343
00344
00345 out() << "\n\nStatistics on generated cuts:\n";
00346 out() << " Number of generated edge inequalities\t\t: ";
00347 out() << theStatistics->getEdgeInequalitiesCut() << endl;
00348 out() << " Number of generated odd cycles\t\t: ";
00349 if (m_oddCycleSeparation) {
00350 out() << theStatistics->getOddCyclesCut() << endl;
00351 out() << " Number of lifted odd circles\t\t: ";
00352 out() << theStatistics->getLiftedOddCyclesCut() << endl;
00353 }
00354 else {
00355 out() << "off" << endl;
00356 }
00357 out() << " Number of generated cliques\t\t\t: ";
00358 if (m_CliqueHeuristicsSeparation) {
00359 out() << theStatistics->getCliqueHeuristicsCut() << endl;
00360 }
00361 else {
00362 out() << "off" << endl;
00363 }
00364 if (m_maxCliqueSeparation) {
00365 out() << " Number of generated cliques (exact)\t\t: ";
00366 out() << theStatistics->getExactCliquesCut() << endl;
00367 }
00368
00369 out() << " Number of generated rank inequalities\t\t: ";
00370 if (m_EdgeProjection) {
00371 out() << theStatistics->getEdgeProjectionCut() << endl;
00372 }
00373 else {
00374 out() << "off" << endl;
00375 }
00376 out() << " Number of generated mod-k cuts\t\t: ";
00377 if (m_ModKCutsSeparation) {
00378 out() << theStatistics->getModKCut() << endl;
00379 }
00380 else {
00381 out() << "off" << endl;
00382 }
00383 out() << " Number of generated local cuts\t\t: ";
00384 if (m_LocalCutSeparation) {
00385 out() << theStatistics->getLocalCutCut() << endl;
00386 }
00387 else {
00388 out() << "off" << endl;
00389 }
00390 out() << " Number of cuts from pool separation\t\t: ";
00391 if (m_PoolSeparation) {
00392 out() << theStatistics->getPoolSeparationCut()
00393 + theStatistics->getMaxCliquesMemoryCut() << endl;
00394 }
00395 else {
00396 out() << "off" << endl;
00397 }
00398 out() << " Number of generated large rank cuts\t\t: ";
00399 out() << theStatistics->getLargeCut() << endl;
00400
00401
00402
00403
00404 out() << "\nStatistics on heuristics:";
00405 out() << "\n Number of solutions found by rounding heuristic\t: ";
00406 out() << theStatistics->getRoundedSolutions();
00407 out() << "\n Number of solutions found by the improvment heuristic\t: ";
00408 out() << theStatistics->getImprovedSolutions();
00409 out() << "\n Solution was found by\t\t\t\t\t: ";
00410 out() << theStatistics->solutionWasFoundBy();
00411
00412
00413
00414
00415 out() << "\n\nStatistics on Branch and Cut tree:";
00416 out() << "\n Number of generated subproblems\t: " << nSub();
00417 out() << "\n Number of solved LPs\t\t\t: " << nLp();
00418 out() << "\n Correct Dual Bound\t: " << theStatistics->getDualBound();
00419 out() << "\n Alpha\t\t: ";
00420 out() << bestSolution.size() + fixedInStableSet.size();
00421 out() << "\n Alpha in root\t: ";
00422 out() << theStatistics->getAlphaRoot();
00423 out() << "\n CPU Time\t: ";
00424 out() << myCPUTimer->seconds() << ":";
00425 out() << myCPUTimer->centiSeconds() % 100 << endl;
00426 out() << endl;
00427
00428
00429
00430
00431 if (m_showBestStableSet) {
00432 if (bestSolution.empty()) {
00433 out() << "No Stable Set found!" << endl;
00434 return;
00435 }
00436
00437 out() << "(Maximum) Stable Set:\t";
00438
00439 if (!fixedInStableSet.empty()) {
00440 int cnt_one = 0;
00441 int cnt_two = 0;
00442 int node_one = fixedInStableSet[cnt_one];
00443 int node_two = itsGraph->translateNode(bestSolution[cnt_two]);
00444 while (true) {
00445 if (node_one < node_two) {
00446 out() << node_one << " ";
00447 cnt_one++;
00448 if (cnt_one < fixedInStableSet.size()) {
00449 node_one = fixedInStableSet[cnt_one];
00450 }
00451 else {
00452 for (int i=cnt_two; i<bestSolution.size(); i++) {
00453 out() << itsGraph->translateNode(bestSolution[i]) << " ";
00454 }
00455 break;
00456 }
00457 }
00458 else {
00459 out() << node_two << " ";
00460 cnt_two++;
00461 if (cnt_two < bestSolution.size()) {
00462 node_two = itsGraph->translateNode(bestSolution[cnt_two]);
00463 }
00464 else {
00465 for (int i=cnt_one; i<fixedInStableSet.size(); i++) {
00466 out() << fixedInStableSet[i] << " ";
00467 }
00468 break;
00469 }
00470 }
00471 }
00472 }
00473 else {
00474 for (int i=0; i<bestSolution.size(); i++) {
00475 out() << bestSolution[i] << " ";
00476 }
00477 out() << endl;
00478 }
00479 }
00480
00481
00482 }
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498 void StableSetMaster::readStableSetInputData(const char *fileName,
00499 char *inequalitiesFileName) {
00500
00501 int i;
00502 int numberOfNodes;
00503 int numberOfEdges;
00504 const int MAX_CHAR_PER_LINE = 1024;
00505 const int MAX_CHAR_PER_FILE_NAME = 256;
00506 char lineBuf[MAX_CHAR_PER_LINE +1];
00507 char weightFileName[MAX_CHAR_PER_FILE_NAME +1];
00508 bool numberOfNodesFound = false;
00509 bool numberOfEdgesFound = false;
00510 bool weightsFound = false;
00511 bool edgeSectionFound = false;
00512 bool noWeights = false;
00513
00514
00515
00516 FILE *stableSetFile = fopen(fileName, "r");
00517 if (stableSetFile == NULL) {
00518 err() << "StableSetMASTER::readStableSetInputData(): ";
00519 err() << "stableSetLIB file " << fileName;
00520 err() << " could not be opened." << endl;
00521 exit(Fatal);
00522 }
00523
00524
00525
00526
00527 while (fgets(lineBuf, MAX_CHAR_PER_LINE, stableSetFile)) {
00528
00529 if (strncmp( lineBuf, "NNODES", strlen("NNODES") ) == 0) {
00530
00531 if (sscanf( lineBuf, "NNODES : %d", &numberOfNodes ) != 1) {
00532 err() << "StableSetMASTER::readStableSetInputData(): ";
00533 err() << "Error when reading numer of nodes (NNODES) of ";
00534 err() << "problem." << endl;
00535 exit(Fatal);
00536 }
00537 numberOfNodesFound = true;
00538 }
00539 else {
00540 if (strncmp(lineBuf, "NEDGES", strlen("NEDGES")) == 0) {
00541
00542 if (sscanf( lineBuf, "NEDGES : %d", &numberOfEdges ) != 1) {
00543 err() << "StableSetMASTER::readStableSetInputData(): ";
00544 err() << "Error when reading numer of edges (NEDGES) ";
00545 err() << "of problem." << endl;
00546 exit(Fatal);
00547 }
00548 numberOfEdgesFound = true;
00549 }
00550 else {
00551 if (strncmp(lineBuf, "WEIGHTS", strlen("WEIGHTS")) == 0) {
00552
00553 if (strncmp(lineBuf, "WEIGHTS : NO",
00554 strlen("WEIGHTS : NO")) == 0) {
00555 noWeights = true;
00556 weightsFound = true;
00557 }
00558 else {
00559
00560 if (sscanf(lineBuf, "WEIGHTS : %s",
00561 &weightFileName) != 1) {
00562 err() << "StableSetMASTER::";
00563 err() << "readStableSetInputData(): ";
00564 err() << "Error when reading name of weight file.";
00565 err() << endl;
00566 exit(Fatal);
00567 }
00568 weightsFound = true;
00569 }
00570 }
00571 else {
00572 if (strncmp(lineBuf, "EDGE_SECTION",
00573 strlen("EDGE_SECTION")) == 0) {
00574 edgeSectionFound = true;
00575
00576 break;
00577 }
00578 }
00579 }
00580 }
00581 }
00582
00583
00584 if (!numberOfNodesFound) {
00585 err() << "StableSetMASTER::readStableSetInputData(): ";
00586 err() << "Keyword NNODES could not be found in file ";
00587 err() << fileName << "." << endl;
00588 exit( Fatal );
00589 }
00590
00591 if (!numberOfEdgesFound) {
00592 err() << "StableSetMASTER::readStableSetInputData(): ";
00593 err() << "Keyword NEDGES could not be found in file ";
00594 err() << fileName << "." << endl;
00595 exit( Fatal );
00596 }
00597
00598 if (!weightsFound) {
00599 err() << "StableSetMASTER::readStableSetInputData(): ";
00600 err() << "Keyword WEIGHTS could not be found in file ";
00601 err() << fileName << "." << endl;
00602 exit( Fatal );
00603 }
00604
00605 if (!edgeSectionFound) {
00606 err() << "StableSetMASTER::readStableSetInputData(): ";
00607 err() << "Keyword EDGE_SECTION could not be found in file ";
00608 err() << fileName << "." << endl;
00609 exit( Fatal );
00610 }
00611
00612
00613
00614
00615 itsGraph = new Graph(this, numberOfNodes, numberOfEdges, !noWeights,
00616 inequalitiesFileName);
00617
00618
00619 for (i=0; i<numberOfEdges; i++) {
00620 static int rightNode;
00621 static int leftNode;
00622 if (fscanf(stableSetFile, "%d %d",&rightNode, &leftNode) != 2) {
00623 err() << "StableSetMASTER::readStableSetInputData(): ";
00624 err() << "Error in edge line " << i+1 << " while reading ";
00625 err() << "EDGE_SECTION." << endl;
00626 exit(Fatal);
00627 }
00628 itsGraph->pushAdjacentNodes(rightNode, leftNode);
00629
00630 }
00631 itsGraph->sortAdjacentList();
00632
00633
00634 if (fclose(stableSetFile)) {
00635 err() << "StableSetMASTER::readStableSetInputData(): ";
00636 err() << "Error in closing file " << fileName << "." << endl;
00637 exit(Fatal);
00638 }
00639
00640
00641 if (!noWeights) {
00642 bool weightsSectionFound = false;
00643 double weight;
00644
00645 const char *stableSetLib = getenv("StableSetLIB_DIR");
00646 if (stableSetLib == 0) {
00647 err() << "StableSetMASTER::readStableSetInputData(): ";
00648 err() << "Environment variable StableSetLIB_DIR not found.";
00649 err() << endl;
00650 exit(Fatal);
00651 }
00652
00653 char weightFile[strlen(stableSetLib) + strlen(weightFileName) +2];
00654
00655 #ifdef ABAUS_VISUAL_CPP
00656 sprintf(weightFile, "%s\\%s", stableSetLib, weightFileName);
00657 #else
00658 sprintf(weightFile, "%s/%s", stableSetLib, weightFileName);
00659 #endif
00660
00661
00662 FILE *stableSetWeightFile = fopen(weightFile, "r");
00663 if (stableSetWeightFile == NULL) {
00664 err() << "StableSetMASTER::readStableSetInputData(): ";
00665 err() << "StableSetLIB file " << weightFile;
00666 err() << " could not be opened." << endl;
00667 exit(Fatal);
00668 }
00669
00670
00671
00672 while (fgets(lineBuf, MAX_CHAR_PER_LINE, stableSetWeightFile)) {
00673
00674 if (strncmp(lineBuf, "WEIGHTS_SECTION",
00675 strlen("WEIGHTS_SECTION")) == 0) {
00676 weightsSectionFound = true;
00677 break;
00678 }
00679 }
00680
00681 if (!weightsSectionFound) {
00682 err() << "StableSetMASTER::readStableSetInputData(): ";
00683 err() << "Keyword WEIGHTS_SECTION could not be found in file ";
00684 err() << weightFile << "." << endl;
00685 exit(Fatal);
00686 }
00687
00688
00689 for (i=0; i<numberOfNodes; i++) {
00690 if( fscanf(stableSetWeightFile, "%lf", &weight) == 1) {
00691 itsGraph->pushWeight(i, weight);
00692 }
00693 else {
00694 err() << "StableSetMASTER::readStableSetInputData(): ";
00695 err() << "Error in weight line " << i+1;
00696 err() << " while reading WEIGHTS_SECTION." << endl;
00697 exit(Fatal);
00698 }
00699 }
00700
00701
00702 if (fclose(stableSetWeightFile)) {
00703 err() << "StableSetMASTER::readStableSetInputData(): ";
00704 err() << "Error in closing file " << weightFile << "." << endl;
00705 exit(Fatal);
00706 }
00707
00708
00709 delete stableSetLib;
00710 }
00711
00712
00713
00714
00715 maxCliques = new Clique(this, itsGraph, numberOfEdges);
00716
00717
00718
00719
00720 }
00721
00722
00723
00724
00725
00726
00727
00728
00729
00730
00731 void StableSetMaster::initializeOptimization() {
00732
00733 int i, j;
00734
00735
00736 out() << "A Maximum Stable Set Solver." << endl;
00737 out() << "Copyright (c) Universitaet Heidelberg." << endl << endl;
00738 out() << "Program Version: 1.0 " << endl;
00739 out() << "Last update: Fri Apr 07 2006" << endl << endl;
00740
00741
00742 myCPUTimer = new ABA_CPUTIMER(this);
00743 myCPUTimer->start(0);
00744
00745 itsGraph->initializeTranslator();
00746
00747 if (itsGraph->numberOfNodes() < 100
00748 && (itsGraph->getDensity() < .2 || itsGraph->getDensity() > .8)
00749 ) {
00750
00751 Preprocessing *thePreprocessing;
00752 thePreprocessing = new Preprocessing(this, itsGraph, theStatistics);
00753 thePreprocessing->preprocessing();
00754
00755
00756 delete thePreprocessing;
00757 }
00758
00759
00760
00761
00762
00763 int size = itsGraph->numberOfNodes();
00764 if (size) {
00765 vector< vector<int> > adjacentList(size);
00766 for (int i=0; i<size; i++) {
00767 adjacentList[i] = (*itsGraph->getAdjacentList(i));
00768 }
00769
00770
00771
00772 theProjection = new EdgeProjection(&adjacentList);
00773 }
00774 else {
00775 theStatistics->setDualBound(fixedInStableSet.size());
00776 }
00777
00778 int numberOfNodes = itsGraph->numberOfNodes();
00779 int numberOfEdges = itsGraph->numberOfEdges();
00780
00781
00782 if (numberOfNodes == 0) {
00783
00784 primalBound(fixedInStableSet.size());
00785 dualBound(fixedInStableSet.size());
00786
00787 ABA_BUFFER<ABA_VARIABLE *> variables(this, 0);
00788 ABA_BUFFER<ABA_CONSTRAINT *> edgeConstraints(this, 0);
00789
00790 initializePools(edgeConstraints, variables, 1, 0);
00791
00792 return;
00793 }
00794
00795
00796
00797
00798
00799
00800
00801 ABA_BUFFER<ABA_VARIABLE *> variables(this, numberOfNodes);
00802
00803
00804 if (itsGraph->weighted()) {
00805 for (i=0; i<numberOfNodes; i++) {
00806 variables.push(new Node(this, i, itsGraph->weight(i)));
00807 }
00808 }
00809 else {
00810 static double DISPLACE = 0.0000000001;
00811 static int MAX_DISPLAYS_MULT = (int) 100;
00812 int factor;
00813 for (i=0; i<numberOfNodes; i++) {
00814 factor = getRandomNumber(MAX_DISPLAYS_MULT);
00815 variables.push(new Node(this, i, 1 + DISPLACE * factor));
00816 }
00817 }
00818
00819
00820
00821 ABA_BUFFER<ABA_CONSTRAINT *> cliqueConstraints(this, numberOfEdges);
00822 vector<int> theNodes(itsGraph->numberOfNodes());
00823 vector<int> adjacentNodes;
00824 vector<int> clique(2);
00825 int index;
00826 int node;
00827 int vertex;
00828 int begin;
00829 int numberOfCliques = 0;
00830
00831
00832 for (i=0; i<itsGraph->numberOfNodes(); i++) {
00833 theNodes[i] = i;
00834 }
00835
00836 ofstream fout(itsGraph->getFileName(), ios::app);
00837 fout << "* Clique covering:" << endl;
00838 fout.close();
00839
00840 while (!theNodes.empty()) {
00841 clique[0] = theNodes.back();
00842 theNodes.pop_back();
00843
00844 adjacentNodes = (*itsGraph->getAdjacentList(clique[0]));
00845
00846 index = getRandomNumber(adjacentNodes.size());
00847 clique[1] = adjacentNodes[index];
00848 adjacentNodes.erase(adjacentNodes.begin() + index);
00849
00850 for (i=adjacentNodes.size()-1; i>=0; i--) {
00851 node = adjacentNodes[i];
00852 size = clique.size();
00853 begin = 0;
00854 if (!itsGraph->isMemberOfAdjacentList(clique[1], begin, node)) {
00855 adjacentNodes.erase(adjacentNodes.begin() + i);
00856 }
00857 }
00858
00859 while (!adjacentNodes.empty()) {
00860 index = getRandomNumber(adjacentNodes.size());
00861 vertex = adjacentNodes[index];
00862 adjacentNodes.erase(adjacentNodes.begin() + index);
00863 clique.push_back(vertex);
00864
00865
00866 for (i=adjacentNodes.size()-1; i>=0; i--) {
00867 node = adjacentNodes[i];
00868 begin = 0;
00869 if (!itsGraph->isMemberOfAdjacentList(vertex, begin, node)) {
00870 adjacentNodes.erase(adjacentNodes.begin() + i);
00871 }
00872 }
00873 }
00874
00875
00876
00877
00878 sort(clique.begin(), clique.end());
00879
00880 for (i=clique.size()-1; i>=0; i--) {
00881 j = 0;
00882 while (j<theNodes.size()) {
00883 if (clique[i] <= theNodes[j]) {
00884 break;
00885 }
00886 j++;
00887 }
00888 if (j == theNodes.size()) {
00889 continue;
00890 }
00891 if (clique[i] == theNodes[j]) {
00892 theNodes.erase(theNodes.begin() + j);
00893 }
00894 }
00895
00896 cliqueConstraints.push(new CliqueConstraint(this, &clique, itsGraph));
00897 numberOfCliques++;
00898
00899 clique.clear();
00900 clique.resize(2);
00901
00902 }
00903
00904
00905 cliqueConstraints.realloc(numberOfCliques);
00906
00907
00908
00909
00910
00911
00912
00913
00914 initializePools(cliqueConstraints, variables, numberOfNodes, 0);
00915
00916
00917
00918
00919
00920
00921
00922
00923 cycleCutPool_ = numberOfEdges < 100
00924 ? new ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE>(
00925 this, numberOfEdges*numberOfEdges, true)
00926 : new ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE>(
00927 this, 25000, true);
00928
00929
00930
00931
00932
00933
00934
00935 cliqueCutPool_ = numberOfEdges < 100
00936 ? new ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE>(
00937 this, numberOfEdges*numberOfEdges, false)
00938 : new ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE>(
00939 this, 15000, false);
00940
00941
00942
00943
00944
00945
00946
00947 rankCutPool_ = numberOfEdges < 100
00948 ? new ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE>(
00949 this, numberOfEdges*numberOfEdges, false)
00950 : new ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE>(
00951 this, 15000, false);
00952
00953
00954
00955
00956
00957
00958 generalCutPool_ = numberOfEdges < 100
00959 ? new ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE>(
00960 this, numberOfEdges*numberOfEdges, true)
00961 : new ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE>(
00962 this, 5000, true);
00963
00964
00965
00966
00967
00968 primalBound(0);
00969
00970
00971 }
00972
00973
00974
00975
00976
00977
00978
00979
00980 void StableSetMaster::initializeParameters() {
00981
00982 int status;
00983
00984
00985
00986
00987
00988 readParameters(".myparameters");
00989
00990 status = getParameter("ShowBestStableSet", m_showBestStableSet);
00991 if (status) {
00992 err() << "StableSetMASTER::initializeParameters(): ";
00993 err() << "Parameter \"ShowBestStableSet\" could not be found ";
00994 err() << "in configuration file \".myparameters.\"" << endl;
00995 exit(Fatal);
00996 }
00997
00998 status = getParameter("TimeLimitImprovementHeuristic",
00999 m_timeLimitForImprovementHeuristic);
01000 if (status) {
01001 err() << "StableSetMASTER::initializeParameters(): ";
01002 err() << "Parameter \"TimeLimitImprovementHeuristic\" could not";
01003 err() << " be found ";
01004 err() << "in configuration file \".myparameters.\"" << endl;
01005 exit(Fatal);
01006 }
01007
01008 status = getParameter("TimeLimit", m_timeLimitForMaxCliqueSep);
01009 if (status) {
01010 err() << "StableSetMASTER::initializeParameters(): ";
01011 err() << "Parameter \"TimeLimit\" could not be found ";
01012 err() << "in configuration file \".myparameters.\"" << endl;
01013 exit(Fatal);
01014 }
01015
01016 status = getParameter("MinimumViolationOfOddCycle", m_minAbsViolationCycle);
01017 if (status) {
01018 err() << "StableSetMASTER::initializeParameters(): ";
01019 err() << "Parameter \"MinimumViolationOfOddCycle\" could not be found ";
01020 err() << "in configuration file \".myparameters.\"" << endl;
01021 exit(Fatal);
01022 }
01023
01024 status = getParameter("MinimumViolationOfClique", m_minAbsViolationClique);
01025 if (status) {
01026 err() << "StableSetMASTER::initializeParameters(): ";
01027 err() << "Parameter \"MinimumViolationOfClique\" could not be found ";
01028 err() << "in configuration file \".myparameters.\"" << endl;
01029 exit(Fatal);
01030 }
01031
01032 status = getParameter("PoolSeparation", m_PoolSeparation);
01033 if (status) {
01034 err() << "StableSetMASTER::initializeParameters(): ";
01035 err() << "Parameter \"PoolSeparation\" could not be found ";
01036 err() << "in configuration file \".myparameters.\"" << endl;
01037 exit(Fatal);
01038 }
01039
01040
01041 status = getParameter("OddCycleSeparation", m_oddCycleSeparation);
01042 if (status) {
01043 err() << "StableSetMASTER::initializeParameters(): ";
01044 err() << "Parameter \"oddCycleSeparation\" could not be found ";
01045 err() << "in configuration file \".myparameters.\"" << endl;
01046 exit(Fatal);
01047 }
01048
01049 status = getParameter("CliqueHeuristicsSeparation", m_CliqueHeuristicsSeparation);
01050 if (status) {
01051 err() << "StableSetMASTER::initializeParameters(): ";
01052 err() << "Parameter \"CliqueHeuristicsSeparation\" could not be found ";
01053 err() << "in configuration file \".myparameters.\"" << endl;
01054 exit(Fatal);
01055 }
01056
01057 status = getParameter("EdgeProjection", m_EdgeProjection);
01058 if (status) {
01059 err() << "StableSetMASTER::initializeParameters(): ";
01060 err() << "Parameter \"EdgeProjection\" could not be found ";
01061 err() << "in configuration file \".myparameters.\"" << endl;
01062 exit(Fatal);
01063 }
01064
01065 status = getParameter("ModKCutsSeparation", m_ModKCutsSeparation);
01066 if (status) {
01067 err() << "StableSetMASTER::initializeParameters(): ";
01068 err() << "Parameter \"ModKCutsSeparation\" could not be found ";
01069 err() << "in configuration file \".myparameters.\"" << endl;
01070 exit(Fatal);
01071 }
01072
01073
01074 status = getParameter("LocalCutSeparation", m_LocalCutSeparation);
01075 if (status) {
01076 err() << "StableSetMASTER::initializeParameters(): ";
01077 err() << "Parameter \"LocalCutSeparation\" could not be found ";
01078 err() << "in configuration file \".myparameters.\"" << endl;
01079 exit(Fatal);
01080 }
01081
01082 status = getParameter("MaxCliqueSeparation", m_maxCliqueSeparation);
01083 if (status) {
01084 err() << "StableSetMASTER::initializeParameters(): ";
01085 err() << "Parameter \"MaxCliqueSeparation\" could not be found ";
01086 err() << "in configuration file \".myparameters.\"" << endl;
01087 exit(Fatal);
01088 }
01089
01090 }
01091
01092