#include <MaxCliquesSeparator.hh>
Public Member Functions | |
MaxCliquesSeparator (ABA_MASTER *master, StableSetLPSolution *solution, Graph *theGraph, Clique *clique) | |
~MaxCliquesSeparator () | |
virtual void | separate () |
Definition at line 39 of file MaxCliquesSeparator.hh.
|
Constructor.
Definition at line 44 of file MaxCliquesSeparator.cpp. 00046 : 00047 ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 500), 00048 master_(master), 00049 lpSolution(solution), 00050 itsGraph(theGraph), 00051 maxCliques(clique) 00052 { 00053 }
|
|
Destructor. Definition at line 59 of file MaxCliquesSeparator.cpp.
|
|
This method provides the separation procedure itself and overrides the pure virtual function of ABA_SEPARATOR. Definition at line 73 of file MaxCliquesSeparator.cpp. References Clique::getLastMaxClique(), StableSetMaster::m_minAbsViolationClique, and StableSetMaster::m_timeLimitForMaxCliqueSep. 00073 { 00074 00075 clock_t t1 = clock(); // Get current time. 00076 00077 int i; // Loop variable. 00078 int cliqueSize; // Size of a clique. 00079 int *lastClique; // Store a clique. 00080 bool maxCliqueFound; // true if a maximal clique has been computed. 00081 bool added; // true if a clique could be added. 00082 bool fixed; // true if the variables of the clique could 00083 // be fixed. 00084 double weight; // Weight of a clique. 00085 double *solutionValue = lpSolution->zVal(); // LP solution 00086 double minViolation = stableSetMaster()->m_minAbsViolationClique; 00087 double timeLimit = stableSetMaster()->m_timeLimitForMaxCliqueSep; 00088 vector<int> nodesOfClique; // Store the nodes of a clique. 00089 CliqueConstraint *cliqueConstr; // Pointer to clique constraint. 00090 00091 00092 // Fill vector nodesOfClique with last found max clique. 00093 lastClique = maxCliques->getLastMaxClique(); 00094 if (lastClique != NULL) { 00095 cliqueSize = lastClique[0]; 00096 nodesOfClique.resize(cliqueSize); 00097 for (i=0; i<cliqueSize; i++) { 00098 nodesOfClique[i] = lastClique[i+1]; 00099 } 00100 } 00101 else { 00102 // No cliques found, yet. 00103 nodesOfClique.push_back(-1); 00104 } 00105 00106 // Produce new maximal cliques untill time limit is reached 00107 // or all cliques are computed. 00108 while ((!maxCliques->allMaximalCliquesFound()) 00109 && (timeLimit > (double)(clock() - t1)/CLOCKS_PER_SEC) 00110 ) { 00111 // Compute next maximal clique. 00112 maxCliqueFound = getNextClique(&nodesOfClique); 00113 if (!maxCliqueFound) { 00114 continue; 00115 } 00116 00117 00118 // Store this clique if it is not part of a greater one and non of 00119 // its variables could be fixed! 00120 added = maxCliques->addMaxClique(&nodesOfClique); 00121 if (!added) { 00122 continue; 00123 } 00124 00125 // This clique is a new maximal clique and therefore we 00126 // compute the weight of it. 00127 00128 weight = 0; 00129 for (i=0; i<nodesOfClique.size(); i++) { 00130 weight += solutionValue[nodesOfClique[i]]; 00131 } 00132 00133 if (weight >= 1 + minViolation) { 00134 // This clique constraint is violated. 00135 // So we have a new clique costraint to be added. 00136 cliqueConstr = new CliqueConstraint(master_, &nodesOfClique, itsGraph); 00137 cutFound(cliqueConstr); 00138 } 00139 }// end: while(..) 00140 00141 00142 } // end: void separate()
|