C:/Programme/home/Administrator/CD/stableSetCode/StableSetMaster.cpp

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : StableSetMaster.cpp
00004 //  Description      : Master of the stable set problem. Root of the Branch
00005 //                     and Cut tree.
00006 //  Author           : Steffen Rebennack
00007 //  Email            : srebenac@ix.urz.uni-heidelberg.de;
00008 //                     steffen.rebennack@web.de
00009 //  Copyright        : (C) 2006 by the University of Heidelberg
00010 //  Created on       : Thu Apr 06 10:39:14 2006
00011 //  Last modified by : -
00012 //  Last modified on : -
00013 //  Update count     : 0
00014 //
00016 //
00017 //  Date        Name            Changes/Extensions
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>                   // rand()
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 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00060 // -----------------------------------------------------------------------------
00061 
00062 
00063 // -----------------------------------------------------------------------------
00064 // C o n s t r u c t o r
00065 //
00066 // Argument problemName is the name of the optimization problem instance. If
00067 // problemName starts with "./" then the input file with the same name is
00068 // searched in the current directory, if it strats with "/" then the absolute
00069 // path name of problem instances is taken, otherwise the input file is
00070 // searched in the directory defined by environment variable StableSetLIB_DIR.
00071 // The input file must have the special StableSetLIB format.
00072 // Argument theInequalitiesFileName is the name of the file where all generated
00073 // cuts are saved that they can be checked.
00074 //
00075 // The constructor calls first the constructor of its base class ABA_MASTER.
00076 // This constructor takes 4 arguments:
00077 // 1.) The name of the problem being solved.
00078 // 2.) With the value true cutting planes are generated with the function
00079 //     ABA_SUB::separate().
00080 // 3.) pricing
00081 // 4.) The sense of optimization.
00082 //
00083 // After the call of ABA_MASTER, the problem name and the name of the file
00084 // for all generated inequalities is read. The next step is to read the input
00085 // graph and to generate the object storing all statistic information.
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     // Read problem name.
00095     //
00096     // Check if problem name is not 0.
00097     if (problemName == 0) {
00098         err() << "StableSetMASTER::StableSetMASTER(): ";
00099         err() << "problem name is missing." << endl;
00100         exit(Fatal);
00101     }
00102     // Determine the complete file name.
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         // Copy problemName in fileName.
00111         sprintf( fileName, "%s", problemName );
00112     }
00113     else {
00114         // Find location of StableSetLIB.
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     // Read file name to store all generated cuts.
00133     //
00134     // Check if inequalities file name is not 0.
00135     if (theInequalitiesFileName == 0) {
00136         err() << "StableSetMASTER::StableSetMASTER(): ";
00137         err() << "inequalities file name is missing." << endl;
00138         exit(Fatal);
00139     }
00140     // Copy outputFileName in outputFile.
00141     char *inequalitiesFileName = new char[strlen(theInequalitiesFileName) + 1];
00142     sprintf(inequalitiesFileName, "%s", theInequalitiesFileName);
00143     // Delete contents of file
00144     ofstream out(inequalitiesFileName);
00145     out.close();
00146 
00147     // Copy small graph name.
00148     sprintf(smallGraphName, "%s", theSmallGraphName);
00149 
00150     //
00151     // Read input data.
00152     //
00153     readStableSetInputData(fileName, inequalitiesFileName);
00154 
00155     //
00156     // Generate object to store statistics.
00157     //
00158     theStatistics = new StableSetStatistics;
00159 
00160     // Clean up.
00161     delete [] fileName;
00162     delete [] inequalitiesFileName;
00163 
00164 }// end: constructor
00165 
00166 
00167 // -----------------------------------------------------------------------------
00168 // D e s t r u c t o r
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 // f i r s t S u b
00188 //
00189 // It redefines a pure virtual function of the base class ABA_MASTER. The root
00190 // of the branch-and-bound tree is initialized with an object of the type
00191 // StableSetSUB. The return value is a pointer to the root node of the
00192 // enumeration tree.
00193 // -----------------------------------------------------------------------------
00194 ABA_SUB *StableSetMaster::firstSub() {
00195     return new StableSetSub(this, itsGraph, maxCliques, theProjection,
00196                             theStatistics);
00197 }
00198 
00199 
00200 // -----------------------------------------------------------------------------
00201 // c y c l e C u t P o o l
00202 // -----------------------------------------------------------------------------
00203 ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *StableSetMaster::cycleCutPool() {
00204     return cycleCutPool_;
00205 }
00206 
00207 
00208 // -----------------------------------------------------------------------------
00209 // c l i q u e C u t P o o l
00210 // -----------------------------------------------------------------------------
00211 ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *StableSetMaster::cliqueCutPool(){
00212     return cliqueCutPool_;
00213 }
00214 
00215 
00216 // -----------------------------------------------------------------------------
00217 // r a n k C u t P o o l
00218 // -----------------------------------------------------------------------------
00219 ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *StableSetMaster::rankCutPool() {
00220     return rankCutPool_;
00221 }
00222 
00223 
00224 // -----------------------------------------------------------------------------
00225 // g e n e r a l C u t P o o l
00226 // -----------------------------------------------------------------------------
00227 ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *StableSetMaster::generalCutPool()
00228 {
00229     return generalCutPool_;
00230 }
00231 
00232 
00233 // -----------------------------------------------------------------------------
00234 // g e t S o l u t i o n
00235 //
00236 // This function is used by the improvement heuristic.
00237 // -----------------------------------------------------------------------------
00238 vector<int> *StableSetMaster::getSolution() {
00239     return &bestSolution;
00240 }
00241 
00242 
00243 // -----------------------------------------------------------------------------
00244 // p u s h F i x e d N o d e
00245 //
00246 // This function is used by the preprocessor.
00247 // -----------------------------------------------------------------------------
00248 void StableSetMaster::pushFixedNode(int node) {
00249      fixedInStableSet.push_back(node);
00250 }
00251 
00252 
00253 // -----------------------------------------------------------------------------
00254 // s o r t F i x e d N o d e s
00255 //
00256 // This function is used by the preprocessor.
00257 // -----------------------------------------------------------------------------
00258 void StableSetMaster::sortFixedNodes() {
00259     if (!fixedInStableSet.empty()) {
00260         sort(fixedInStableSet.begin(), fixedInStableSet.end());
00261     }
00262 }
00263 
00264 
00265 // -----------------------------------------------------------------------------
00266 // f i x e d N o d e s T o O n e
00267 //
00268 // This function is used to determine the stablity number if the preprocessing
00269 // phase was successful.
00270 // -----------------------------------------------------------------------------
00271 int StableSetMaster::fixedNodesToOne() const{
00272     return fixedInStableSet.size();
00273 }
00274 
00275 
00276 // -----------------------------------------------------------------------------
00277 // p r i n t T i m e
00278 // -----------------------------------------------------------------------------
00279 void StableSetMaster::printTime() {
00280     out() << "Current time:" << myCPUTimer->seconds();
00281     out() << ":" << myCPUTimer->centiSeconds() % 100 << endl;
00282 }
00283 
00284 
00285 // -----------------------------------------------------------------------------
00286 // s t a r t T i m e r
00287 // -----------------------------------------------------------------------------
00288 void StableSetMaster::startTimer() {
00289     myCPUTimer->start();
00290 }
00291 
00292 
00293 // -----------------------------------------------------------------------------
00294 // s t o p T i m e r
00295 // -----------------------------------------------------------------------------
00296 void StableSetMaster::stopTimer() {
00297     myCPUTimer->stop();
00298 }
00299 
00300 
00301 // -----------------------------------------------------------------------------
00302 // g e t S m a l l G r a p h N a m e
00303 // -----------------------------------------------------------------------------
00304 char *StableSetMaster::getSmallGraphName() {
00305     return smallGraphName;
00306 }
00307 
00308 
00309 // -----------------------------------------------------------------------------
00310 // g e t R a n d o m N u m b e r
00311 //
00312 // Get an integer random number which is non-negative and smaller than 'bound'.
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 // o u t p u t
00324 //
00325 // The function output() redefines a virtual dummy function of the base class
00326 // master to output statistics of the run and the best stable set. This function
00327 // is called at the end of the optimization after the output of the ABACUS
00328 // statistics.
00329 // -----------------------------------------------------------------------------
00330 void StableSetMaster::output() {
00331 
00332     // Stop counter.
00333     myCPUTimer->stop();
00334 
00335     //
00336     // Preprocessing.
00337     //
00338     out() << "\n\nStatistics on preprocessing:\n";
00339     itsGraph->printStatistic();
00340 
00341 
00342     //
00343     // Output statistics on constraint generation.
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     // Heuristics.
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     // Branch and Cut tree.
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     // Output best stable set.
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                     }// else
00457                 }// if
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                 }// else
00471             }// while
00472         }// if
00473         else {
00474             for (int i=0; i<bestSolution.size(); i++) {
00475                 out() << bestSolution[i]  << " ";
00476             }
00477             out() << endl;
00478         }// else
00479     }// if
00480 
00481 
00482 }// end: void output()
00483 
00484 
00485 
00486 // -----------------------------------------------------------------------------
00487 // --------------- M e t h o d s  ( p r i v a t e ) ----------------------------
00488 // -----------------------------------------------------------------------------
00489 
00490 
00491 // -----------------------------------------------------------------------------
00492 // r e a d S t a b l e S e t I n p u t D a t a
00493 //
00494 // This function reads a problem instance in StableSetLIB format and stores all
00495 // this data in the class Graph.
00496 // Argument fileName is the name of the input file
00497 // -----------------------------------------------------------------------------
00498 void StableSetMaster::readStableSetInputData(const char *fileName,
00499                                              char *inequalitiesFileName) {
00500 
00501     int i;                              // Loop counter.
00502     int numberOfNodes;                  // Store number of nodes.
00503     int numberOfEdges;                  // Store number of edges.
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     // Open input file.
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     // Check input file format and store numberOfNodes and numberOfEdges
00525     // therefor read all lines of file stableSetFile and store it in lineBuf
00526     // - but max. 1024 characters per line.
00527     while (fgets(lineBuf, MAX_CHAR_PER_LINE, stableSetFile)) {
00528         // Compare lineBuf with key word NNODES.
00529         if (strncmp( lineBuf, "NNODES", strlen("NNODES") ) == 0) {
00530             // Save number of nodes.
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                 // Save number of edges.
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                     // Is this a weighted stable set problem?
00553                     if (strncmp(lineBuf, "WEIGHTS : NO",
00554                                 strlen("WEIGHTS : NO")) == 0) {
00555                         noWeights = true;
00556                         weightsFound = true;
00557                     }
00558                     else {
00559                         // Save file name which includes all weights.
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                         // All data found -> exit while loop
00576                         break;
00577                     }
00578                 }
00579             }
00580         }
00581     }  // end: while (fgets( lineBuf, MAX_CHAR_PER_LINE, stableSetFile)) {
00582 
00583     // Have all required keywords be found in the file?
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     // Call constructor of graph.
00614     //
00615     itsGraph = new Graph(this, numberOfNodes, numberOfEdges, !noWeights,//
00616                          inequalitiesFileName);
00617         
00618     // Get all information of the graph.
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     // Close stableSetLIB file.
00634     if (fclose(stableSetFile)) {
00635         err() << "StableSetMASTER::readStableSetInputData(): ";
00636         err() << "Error in closing file " << fileName << "." << endl;
00637         exit(Fatal);
00638     }
00639 
00640     // Read coefficients.
00641     if (!noWeights) {
00642         bool   weightsSectionFound = false;
00643         double weight;  // Weight of a node.
00644         // Find location of StableSetLIB.
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         // Open file which includes all weights.
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         // Read all lines of file StableSetFile and store it in lineBuf
00671         // - but max. 1024 characters per line.
00672         while (fgets(lineBuf, MAX_CHAR_PER_LINE, stableSetWeightFile)) {
00673             // Compare 'lineBuf' with key word 'NNODES'.
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         // Read all weights.
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         // Close stableSetWeightFile file.
00702         if (fclose(stableSetWeightFile)) {
00703             err() << "StableSetMASTER::readStableSetInputData(): ";
00704             err() << "Error in closing file " << weightFile << "." << endl;
00705             exit(Fatal);
00706         }
00707 
00708         // clean up
00709         delete stableSetLib;
00710     }// if (!noWeights) {
00711 
00712     //
00713     // Initialize clique constraints.
00714     //
00715     maxCliques = new Clique(this, itsGraph, numberOfEdges);
00716 
00717     // Output information about problem instance.
00718 //    itsGraph->output();
00719 
00720 }// end: void readStableSetInputData(..)
00721 
00722 
00723 // -----------------------------------------------------------------------------
00724 // i n i t i a l i z e O p t i m i z a t i o n
00725 //
00726 // This function defines a virtual dummy function of the class ABA_MASTER. 
00727 // It starts the preprocessing phase and computes the first LP. This LP
00728 // contains a clique covering and the trivial inequalities.
00729 // After that is done, all cut pools are initialized.
00730 // -----------------------------------------------------------------------------
00731 void StableSetMaster::initializeOptimization() {
00732 
00733     int i, j;                                           // Loop counter.
00734 
00735     // Output a banner.
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     // Set timer.
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         // Call preprocessing
00751         Preprocessing *thePreprocessing;
00752         thePreprocessing = new Preprocessing(this, itsGraph, theStatistics);
00753         thePreprocessing->preprocessing();
00754        
00755         // Clean up.
00756         delete thePreprocessing; 
00757     }
00758 
00759 
00760     //
00761     // Generate new object edge projection.
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         //cout << "m_storeInequalities:\t" << m_storeInequalities << endl;
00771 
00772         theProjection = new EdgeProjection(&adjacentList);
00773     }
00774     else {
00775         theStatistics->setDualBound(fixedInStableSet.size());
00776     }
00777 
00778     int numberOfNodes = itsGraph->numberOfNodes();      // Problem size.
00779     int numberOfEdges = itsGraph->numberOfEdges();      // Number of edges.
00780 
00781     // Check if the preprocessing step was successful.
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     // Generate the variables.
00796     // Each variable in this stable set problem solver is associated with an
00797     // vertex of the undirected graph. This variables are created by using the
00798     // class NODE that is derived from the class ABA_VARIABLE. The objective
00799     // function coefficient is one in the unweighted case and otherwise the
00800     // weight itself.
00801     ABA_BUFFER<ABA_VARIABLE *> variables(this, numberOfNodes);
00802 
00803     // Add all variables with its weight.
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     // Construct clique covering.
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         }// for
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             // Update adjacent list.
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         }// while
00874 
00875         // Maximal clique found.
00876         // Delete all nodes from set theNodes.
00877         // Store the clique.
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         }// for
00895 
00896         cliqueConstraints.push(new CliqueConstraint(this, &clique, itsGraph));
00897         numberOfCliques++;
00898 
00899         clique.clear();
00900         clique.resize(2);
00901 
00902     }// while
00903 
00904 
00905     cliqueConstraints.realloc(numberOfCliques);
00906 
00907     // Initialize the pools.
00908     // The first argument inserts the constraints in the constraint pool and the
00909     // second argument inserts the variables in the variable pool. Because there
00910     // are no more variables added, the number of variables is fixed to
00911     // numerOfNodes. The last argument is the size of the pool for the
00912     // cutting planes. It is zero because we have for each type an own cutting
00913     // plane.
00914     initializePools(cliqueConstraints, variables, numberOfNodes, 0);
00915 
00916      
00917     // The cut pool for the cycle constraints. The size of the pool is fixed.
00918     // The pool is of type non_dupl which means that no equal constraints are
00919     // stored twice.
00920     //
00921     // Size is updated automatically.
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     // The cut pool for the clique constraints. The size of the pool is fixed.
00930     // The pool is of type non_dupl which means that no equal constraints are
00931     // stored twice.
00932     //
00933     // Size is fixed.
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     // The cut pool for the rank constraints. The size of the pool is dynamic.
00942     // The pool is of type non_dupl which means that no equal constraints are
00943     // stored twice.
00944     //
00945     // Size is fixed.
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     // The cut pool for the local cuts. The size of the pool is fixed.
00956     // The pool is of type non_dupl which means that no equal constraints are
00957     // stored twice.
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     // Initialize the primal bound.
00966     // In this solver there is no heuristic for finding a solution without a
00967     // fractional solution and therfore the lower bound is zero.
00968     primalBound(0);
00969 
00970 
00971 }// end: void initializeOptimization()
00972 
00973 
00974 // -----------------------------------------------------------------------------
00975 // i n i t i a l i z e P a r a m e t e r s
00976 //
00977 // This function redefines a virtual dummy function of the class ABA_MASTER. It
00978 // is called at the beginning of the optimization.
00979 // -----------------------------------------------------------------------------
00980 void StableSetMaster::initializeParameters() {
00981 
00982     int  status;
00983 
00984     // The function readParameters() reads the file .myparameters that must be
00985     // in the ABACUS parameter file format. All parameters together with their
00986     // values are added to an internal paramter table from which they can be
00987     // read with the function getParameter().
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 }// end: void initializeParameters()
01091 
01092 

Generated on Fri Apr 28 15:49:59 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO