#include <StableSetMaster.hh>
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 |
Definition at line 46 of file StableSetMaster.hh.
|
Constructor.
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
|
|
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 }
|
|
Get pool for the clique constraints.
Definition at line 211 of file StableSetMaster.cpp. Referenced by StableSetSub::separate(), and StableSetModKSeparator::separate().
|
|
Get pool for the cycle constraints.
Definition at line 203 of file StableSetMaster.cpp. Referenced by StableSetSub::separate().
|
|
Initialize the root of the branch-and-bound tree.
Definition at line 194 of file StableSetMaster.cpp. 00194 { 00195 return new StableSetSub(this, itsGraph, maxCliques, theProjection, 00196 theStatistics); 00197 }
|
|
Get number of nodes which have been FIXED to value 1 in the preprocessing phase.
Definition at line 271 of file StableSetMaster.cpp.
|
|
Get pool for the general constraints.
Definition at line 227 of file StableSetMaster.cpp.
|
|
Get a random number.
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 }
|
|
Get name of the small graph.
Definition at line 304 of file StableSetMaster.cpp.
|
|
Get currently best solution.
Definition at line 238 of file StableSetMaster.cpp. Referenced by ImprovementHeuristic::improve().
|
|
Output statistics at the end of the program.
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()
|
|
Print CPU time.
Definition at line 279 of file StableSetMaster.cpp. 00279 { 00280 out() << "Current time:" << myCPUTimer->seconds(); 00281 out() << ":" << myCPUTimer->centiSeconds() % 100 << endl; 00282 }
|
|
Store a node which has been fixed.
Definition at line 248 of file StableSetMaster.cpp.
|
|
Get pool for the rank constraints.
Definition at line 219 of file StableSetMaster.cpp.
|
|
Sort the vector of the fixed nodes.
Definition at line 258 of file StableSetMaster.cpp. 00258 { 00259 if (!fixedInStableSet.empty()) { 00260 sort(fixedInStableSet.begin(), fixedInStableSet.end()); 00261 } 00262 }
|
|
Start CPU-timer.
Definition at line 288 of file StableSetMaster.cpp.
|
|
Stop CPU-timer.
Definition at line 296 of file StableSetMaster.cpp.
|
|
Parameter managed by file .myparameters: Separate the cliques randomly or not. Definition at line 238 of file StableSetMaster.hh. Referenced by output(). |
|
Parameter managed by file .myparameters: Use edge projection or not. Definition at line 244 of file StableSetMaster.hh. Referenced by output(). |
|
Parameter managed by file .myparameters: Use local cut separation or not. Definition at line 256 of file StableSetMaster.hh. Referenced by output(). |
|
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(). |
|
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(). |
|
Parameter managed by file .myparameters: Absolute value which every cycle constraint must violate to be added. Definition at line 214 of file StableSetMaster.hh. |
|
Parameter managed by file .myparameters: Separate with mod-k or not. Definition at line 250 of file StableSetMaster.hh. Referenced by output(). |
|
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(). |
|
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(). |
|
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(). |
|
Parameter managed by file .myparameters: Time limit for the improvement heuristic. Definition at line 202 of file StableSetMaster.hh. Referenced by ImprovementHeuristic::improve(). |
|
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(). |