StableSetMaster Class Reference

#include <StableSetMaster.hh>

List of all members.

Public Member Functions

 StableSetMaster (const char *problemName, const char *theInequalitiesFileName, const char *theSmallGraphName)
virtual ~StableSetMaster ()
virtual ABA_SUB * firstSub ()
ABA_NONDUPLPOOL< ABA_CONSTRAINT,
ABA_VARIABLE > * 
cycleCutPool ()
ABA_NONDUPLPOOL< ABA_CONSTRAINT,
ABA_VARIABLE > * 
cliqueCutPool ()
ABA_NONDUPLPOOL< ABA_CONSTRAINT,
ABA_VARIABLE > * 
rankCutPool ()
ABA_NONDUPLPOOL< ABA_CONSTRAINT,
ABA_VARIABLE > * 
generalCutPool ()
vector< int > * getSolution ()
void pushFixedNode (int node)
void sortFixedNodes ()
int fixedNodesToOne () const
void printTime ()
void startTimer ()
void stopTimer ()
char * getSmallGraphName ()
int getRandomNumber (int bound) const
virtual void output ()

Public Attributes

double m_timeLimitForImprovementHeuristic
double m_timeLimitForMaxCliqueSep
double m_minAbsViolationCycle
double m_minAbsViolationClique
bool m_PoolSeparation
bool m_oddCycleSeparation
bool m_CliqueHeuristicsSeparation
bool m_EdgeProjection
bool m_ModKCutsSeparation
bool m_LocalCutSeparation
bool m_maxCliqueSeparation
bool m_showBestStableSet


Detailed Description

The class StableSetMaster is derived from the abstract class ABA_MASTER. Its main purpose is:

Definition at line 46 of file StableSetMaster.hh.


Constructor & Destructor Documentation

StableSetMaster::StableSetMaster const char *  problemName,
const char *  theInequalitiesFileName,
const char *  theSmallGraphName
 

Constructor.

Parameters:
*problemName Pointer to the name of the optimization problem instance.
*theInequalitiesFileName Pointer to the name of the file where all generated cuts are stored.
*theSmallGraphName Store the name of a small graph. This is used by the rank inequality separation.

Definition at line 87 of file StableSetMaster.cpp.

00089                                                                :
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

StableSetMaster::~StableSetMaster  )  [virtual]
 

Destructor.

Definition at line 170 of file StableSetMaster.cpp.

References Graph::numberOfNodes().

00170                                   {
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 }


Member Function Documentation

ABA_NONDUPLPOOL< ABA_CONSTRAINT, ABA_VARIABLE > * StableSetMaster::cliqueCutPool  ) 
 

Get pool for the clique constraints.

Parameters:
void 
Returns:
Pointer to the cut pool forthe clique constraints.

Definition at line 211 of file StableSetMaster.cpp.

Referenced by StableSetSub::separate(), and StableSetModKSeparator::separate().

00211                                                                              {
00212     return cliqueCutPool_;
00213 }

ABA_NONDUPLPOOL< ABA_CONSTRAINT, ABA_VARIABLE > * StableSetMaster::cycleCutPool  ) 
 

Get pool for the cycle constraints.

Parameters:
void 
Returns:
Pointer to the cut pool for the cycle constraints.

Definition at line 203 of file StableSetMaster.cpp.

Referenced by StableSetSub::separate().

00203                                                                              {
00204     return cycleCutPool_;
00205 }

ABA_SUB * StableSetMaster::firstSub  )  [virtual]
 

Initialize the root of the branch-and-bound tree.

Parameters:
void 
Returns:
Pointer to the root node of the enumeration tree.

Definition at line 194 of file StableSetMaster.cpp.

00194                                    {
00195     return new StableSetSub(this, itsGraph, maxCliques, theProjection,
00196                             theStatistics);
00197 }

int StableSetMaster::fixedNodesToOne  )  const
 

Get number of nodes which have been FIXED to value 1 in the preprocessing phase.

Parameters:
void 
Returns:
Number of fixed nodes to value 1.

Definition at line 271 of file StableSetMaster.cpp.

00271                                           {
00272     return fixedInStableSet.size();
00273 }

ABA_NONDUPLPOOL< ABA_CONSTRAINT, ABA_VARIABLE > * StableSetMaster::generalCutPool  ) 
 

Get pool for the general constraints.

Parameters:
void 
Returns:
Pointer to the cut pool for the local cuts.

Definition at line 227 of file StableSetMaster.cpp.

00228 {
00229     return generalCutPool_;
00230 }

int StableSetMaster::getRandomNumber int  bound  )  const
 

Get a random number.

Parameters:
bound Upper bound for the random number.
Returns:
Random number y with property: y integer and 0 <= y < bound.

Definition at line 314 of file StableSetMaster.cpp.

00314                                                     {
00315     int    aNumber = rand();
00316     double d       = (double(aNumber)/RAND_MAX);
00317 
00318     return (int)(d*bound);
00319 }

char * StableSetMaster::getSmallGraphName  ) 
 

Get name of the small graph.

Parameters:
void 
Returns:
void

Definition at line 304 of file StableSetMaster.cpp.

00304                                          {
00305     return smallGraphName;
00306 }

vector< int > * StableSetMaster::getSolution  ) 
 

Get currently best solution.

Parameters:
void 
Returns:
Pointer to a vector storing the best solution found.

Definition at line 238 of file StableSetMaster.cpp.

Referenced by ImprovementHeuristic::improve().

00238                                           {
00239     return &bestSolution;
00240 }

void StableSetMaster::output  )  [virtual]
 

Output statistics at the end of the program.

Parameters:
void 
Returns:
void

Definition at line 330 of file StableSetMaster.cpp.

References StableSetStatistics::getAlphaRoot(), StableSetStatistics::getCliqueHeuristicsCut(), StableSetStatistics::getDualBound(), StableSetStatistics::getEdgeInequalitiesCut(), StableSetStatistics::getEdgeProjectionCut(), StableSetStatistics::getExactCliquesCut(), StableSetStatistics::getImprovedSolutions(), StableSetStatistics::getLargeCut(), StableSetStatistics::getLiftedOddCyclesCut(), StableSetStatistics::getLocalCutCut(), StableSetStatistics::getMaxCliquesMemoryCut(), StableSetStatistics::getModKCut(), StableSetStatistics::getOddCyclesCut(), StableSetStatistics::getPoolSeparationCut(), StableSetStatistics::getRoundedSolutions(), m_CliqueHeuristicsSeparation, m_EdgeProjection, m_LocalCutSeparation, m_maxCliqueSeparation, m_ModKCutsSeparation, m_oddCycleSeparation, m_PoolSeparation, m_showBestStableSet, Graph::printStatistic(), StableSetStatistics::solutionWasFoundBy(), and Graph::translateNode().

00330                              {
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()

void StableSetMaster::printTime  ) 
 

Print CPU time.

Parameters:
void 
Returns:
void

Definition at line 279 of file StableSetMaster.cpp.

00279                                 {
00280     out() << "Current time:" << myCPUTimer->seconds();
00281     out() << ":" << myCPUTimer->centiSeconds() % 100 << endl;
00282 }

void StableSetMaster::pushFixedNode int  node  ) 
 

Store a node which has been fixed.

Parameters:
node Index of a node.
Returns:
void

Definition at line 248 of file StableSetMaster.cpp.

00248                                             {
00249      fixedInStableSet.push_back(node);
00250 }

ABA_NONDUPLPOOL< ABA_CONSTRAINT, ABA_VARIABLE > * StableSetMaster::rankCutPool  ) 
 

Get pool for the rank constraints.

Parameters:
void 
Returns:
Pointer to the cut pool for the rank cuts.

Definition at line 219 of file StableSetMaster.cpp.

00219                                                                             {
00220     return rankCutPool_;
00221 }

void StableSetMaster::sortFixedNodes  ) 
 

Sort the vector of the fixed nodes.

Parameters:
void 
Returns:
void

Definition at line 258 of file StableSetMaster.cpp.

00258                                      {
00259     if (!fixedInStableSet.empty()) {
00260         sort(fixedInStableSet.begin(), fixedInStableSet.end());
00261     }
00262 }

void StableSetMaster::startTimer  ) 
 

Start CPU-timer.

Parameters:
void 
Returns:
void

Definition at line 288 of file StableSetMaster.cpp.

00288                                  {
00289     myCPUTimer->start();
00290 }

void StableSetMaster::stopTimer  ) 
 

Stop CPU-timer.

Parameters:
void 
Returns:
void

Definition at line 296 of file StableSetMaster.cpp.

00296                                 {
00297     myCPUTimer->stop();
00298 }


Member Data Documentation

bool StableSetMaster::m_CliqueHeuristicsSeparation
 

Parameter managed by file .myparameters: Separate the cliques randomly or not.

Definition at line 238 of file StableSetMaster.hh.

Referenced by output().

bool StableSetMaster::m_EdgeProjection
 

Parameter managed by file .myparameters: Use edge projection or not.

Definition at line 244 of file StableSetMaster.hh.

Referenced by output().

bool StableSetMaster::m_LocalCutSeparation
 

Parameter managed by file .myparameters: Use local cut separation or not.

Definition at line 256 of file StableSetMaster.hh.

Referenced by output().

bool StableSetMaster::m_maxCliqueSeparation
 

Parameter managed by file .myparameters: If exact max clique separation is vished the value is true.

Definition at line 262 of file StableSetMaster.hh.

Referenced by output().

double StableSetMaster::m_minAbsViolationClique
 

Parameter managed by file .myparameters: Absolute value which every clique constraint must violate to be added.

Definition at line 220 of file StableSetMaster.hh.

Referenced by MaxCliquesSeparator::separate().

double StableSetMaster::m_minAbsViolationCycle
 

Parameter managed by file .myparameters: Absolute value which every cycle constraint must violate to be added.

Definition at line 214 of file StableSetMaster.hh.

bool StableSetMaster::m_ModKCutsSeparation
 

Parameter managed by file .myparameters: Separate with mod-k or not.

Definition at line 250 of file StableSetMaster.hh.

Referenced by output().

bool StableSetMaster::m_oddCycleSeparation
 

Parameter managed by file .myparameters: If pool separation is wished the value is true.

Definition at line 232 of file StableSetMaster.hh.

Referenced by output().

bool StableSetMaster::m_PoolSeparation
 

Parameter managed by file .myparameters: If odd cycle separation is vished the value is true.

Definition at line 226 of file StableSetMaster.hh.

Referenced by output().

bool StableSetMaster::m_showBestStableSet
 

Parameter managed by file .myparameters: If this flag is true than an optimal stable set is printed.

Definition at line 268 of file StableSetMaster.hh.

Referenced by output().

double StableSetMaster::m_timeLimitForImprovementHeuristic
 

Parameter managed by file .myparameters: Time limit for the improvement heuristic.

Definition at line 202 of file StableSetMaster.hh.

Referenced by ImprovementHeuristic::improve().

double StableSetMaster::m_timeLimitForMaxCliqueSep
 

Parameter managed by file .myparameters: Time limit for the exact max clique separation.

Definition at line 208 of file StableSetMaster.hh.

Referenced by MaxCliquesSeparator::separate().


The documentation for this class was generated from the following files:
Generated on Fri Apr 28 15:50:01 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO