#include <StableSetModKSeparator.hh>
Public Member Functions | |
StableSetModKSeparator (StableSetLPSolution *solution, Graph *itsGraph) | |
~StableSetModKSeparator () | |
virtual void | separate () |
void | applyRanking (ABA_BUFFER< double > *rank) |
Definition at line 35 of file StableSetModKSeparator.hh.
|
Constructor.
Definition at line 47 of file StableSetModKSeparator.cpp. References Graph::numberOfNodes(). 00048 : 00049 ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 10000), 00050 lpSolution(solution), 00051 itsGraph(theGraph) 00052 { 00053 nVariables = theGraph->numberOfNodes(); 00054 }
|
|
Destructor. Definition at line 60 of file StableSetModKSeparator.cpp.
|
|
Rank the inequalities.
Definition at line 281 of file StableSetModKSeparator.cpp. References StableSetLPSolution::stableSetMaster(), and StableSetLPSolution::sub(). 00281 { 00282 00283 // Nothing to do if buffer is empty. 00284 if (cutBuffer().number() == 0) { 00285 return; 00286 } 00287 00288 // 00289 // Variables. 00290 // 00291 StableSetMaster *master = lpSolution->stableSetMaster(); 00292 ABA_SUB *sub = lpSolution->sub(); 00293 ABA_CONSTRAINT *constrPointer; 00294 ABA_POOLSLOT<ABA_CONSTRAINT, ABA_VARIABLE> *constrSlot; 00295 int i, j; // Loop varibels. 00296 double slack, nNonZeroCoeffs, rankValue; 00297 00298 ABA_STANDARDPOOL<ABA_VARIABLE, ABA_CONSTRAINT> *varPool; 00299 ABA_POOLSLOT<ABA_VARIABLE, ABA_CONSTRAINT> *varSlot; 00300 varPool = master->varPool(); 00301 ABA_VARIABLE *varPointer; 00302 double constrCoeff, objectiveCoeff, scaleCoeff = 0, scaleObj = 0; 00303 00304 // 00305 // Rank the inequalities. 00306 // 00307 for (i=0; i<cutBuffer().number(); i++){ 00308 constrPointer = cutBuffer()[i]; 00309 rankValue = 0; 00310 for(j=0; j<nVariables; j++){ 00311 varPointer = (varPool->slot(j))->conVar(); 00312 objectiveCoeff = varPointer->obj(); 00313 if (objectiveCoeff > 0.999999 && objectiveCoeff < 1.000001) { 00314 objectiveCoeff = 1; 00315 } 00316 if(objectiveCoeff < -0.999999 && objectiveCoeff > -1.000001) { 00317 objectiveCoeff = -1; 00318 } 00319 constrCoeff = constrPointer->coeff(varPointer); 00320 /* Skalarprodukt berechnen */ 00321 rankValue += (objectiveCoeff * constrCoeff); 00322 /* Fuer das spaetere Normieren */ 00323 scaleCoeff += (constrCoeff * constrCoeff); 00324 scaleObj += (objectiveCoeff* objectiveCoeff); 00325 00326 } 00327 /* Normieren des Skalarproduktes */ 00328 scaleCoeff = sqrt(scaleCoeff); 00329 scaleObj = sqrt(scaleObj); 00330 rankValue = rankValue / (scaleCoeff * scaleObj); 00331 /* Kleine Winkel sind am besten. 00332 Aber fuer ABACUS je groesser, desto besser,daher */ 00333 rankValue = 1 - rankValue; 00334 rank->push(rankValue); 00335 } 00336 00337 return; 00338 00339 }// end applyRanking(..)
|
|
Contains the separation procedure. Overrides the pure virtual function of ABA_SEPARATOR.
Definition at line 71 of file StableSetModKSeparator.cpp. References StableSetMaster::cliqueCutPool(), StableSetLPSolution::stableSetMaster(), and StableSetLPSolution::sub(). 00071 { 00072 00073 // 00074 // Variables. 00075 // 00076 // Stable set master. 00077 StableSetMaster *master = lpSolution->stableSetMaster(); 00078 // Current sub problem. 00079 ABA_SUB *sub = lpSolution->sub(); 00080 // Pointer to the pool which contains the variables to be added. 00081 ABA_STANDARDPOOL<ABA_CONSTRAINT,ABA_VARIABLE> *poolPointer; 00082 poolPointer = master->cliqueCutPool(); 00083 // Number of conatraints in the pool. 00084 int nConstraints = poolPointer->number(); 00085 // Loop counter; 00086 int i, j, a; 00087 // Number of conatrsints to be added to the separator. 00088 int nSlack0Constr = 0; 00089 // Tolerance. 00090 static double eps = 0.0000001; 00091 // Store constraints to be added. 00092 // Overestimate size. 00093 int *nNonZeros = new int[nConstraints +nVariables]; 00094 int **nonZeroIndices = new int*[nConstraints +nVariables]; 00095 double **nonZeroCoeffs = new double*[nConstraints +nVariables]; 00096 double *rhs = new double[nConstraints +nVariables]; 00097 // This will contain the information of the constraints. 00098 ABA_ROW *row = new ABA_ROW(master, nVariables); 00099 // Pointer to a constraint. 00100 ABA_CONSTRAINT *constrPointer; 00101 vector<int> indexVector; 00102 int numberOfVariablesInConstr; 00103 int index; 00104 double *solutionVal = lpSolution->zVal(); 00105 // The k's which are used for the mod-k separation. 00106 int theKs[] = {2, 3, 5, 7}; 00107 int numberOfKs = 4; 00108 00109 // 00110 // Construct all inequalities for the mod-k-separator. 00111 // 00112 for (i=0; i<nConstraints; i++){ 00113 // Get next constraint. 00114 constrPointer = (ABA_CONSTRAINT *)(( poolPointer->slot(i) )->conVar()); 00115 if (constrPointer == NULL) { 00116 continue; 00117 } 00118 00119 // Select only constraints which have slack zero. 00120 if (constrPointer->slack(sub->actVar(), lpSolution->zVal()) < -eps 00121 || constrPointer->slack(sub->actVar(), lpSolution->zVal()) > +eps) { 00122 continue; 00123 } 00124 00125 // Store inequality. 00126 rhs[nSlack0Constr] = constrPointer->rhs(); // = 1; 00127 numberOfVariablesInConstr = constrPointer->genRow(sub->actVar(), *row); 00128 00129 for (j=0; j<numberOfVariablesInConstr; j++) { 00130 index = row->support(j); 00131 if (solutionVal[index] >= eps) { 00132 indexVector.push_back(index); 00133 } 00134 } 00135 if (indexVector.size() == 0) { 00136 cout << "\n\n\n\nALARM!!!\n\n\n\n" << endl; 00137 int abcd; 00138 cin >> abcd; 00139 } 00140 nNonZeros[nSlack0Constr] = indexVector.size(); 00141 nonZeroIndices[nSlack0Constr] = new int[nNonZeros[nSlack0Constr]]; 00142 nonZeroCoeffs[nSlack0Constr] = new double[nNonZeros[nSlack0Constr]]; 00143 for (j=0; j<indexVector.size(); j++) { 00144 nonZeroIndices[nSlack0Constr][j] = indexVector[j]; 00145 nonZeroCoeffs[nSlack0Constr][j] = row->coeff(j); 00146 } 00147 nSlack0Constr++; 00148 00149 // Clean up. 00150 row->clear(); 00151 indexVector.clear(); 00152 } 00153 00154 // Check the trivial inequalities. 00155 for (i=0; i<nVariables; i++) { 00156 if (solutionVal[i] <= eps) { 00157 nNonZeros[nSlack0Constr] = 1; 00158 nonZeroIndices[nSlack0Constr] = new int[1]; 00159 nonZeroIndices[nSlack0Constr][0] = i; 00160 nonZeroCoeffs[nSlack0Constr] = new double[1]; 00161 nonZeroCoeffs[nSlack0Constr][0] = -1; 00162 rhs[nSlack0Constr] = 0; 00163 nSlack0Constr++; 00164 } 00165 else { 00166 if (solutionVal[i] >= 1-eps) { 00167 nNonZeros[nSlack0Constr] = 1; 00168 nonZeroIndices[nSlack0Constr] = new int[1]; 00169 nonZeroIndices[nSlack0Constr][0] = i; 00170 nonZeroCoeffs[nSlack0Constr] = new double[1]; 00171 nonZeroCoeffs[nSlack0Constr][0] = 1; 00172 rhs[nSlack0Constr] = 1; 00173 nSlack0Constr++; 00174 } 00175 } 00176 }// for 00177 00178 00179 // 00180 // Check if there were inequalities. 00181 // 00182 if (nSlack0Constr == 0) { 00183 cout << "\n\t\tNo constraints with slack 0." << endl; 00184 00185 return; 00186 } 00187 00188 // 00189 // Call Mod-k separation routine. 00190 // 00191 00192 for (a=0; a<numberOfKs; a++) { 00193 00194 // Generate object. 00195 ModkSeparator *modkSeparator; 00196 modkSeparator = new ModkSeparator(theKs[a], nSlack0Constr, nVariables, 00197 nNonZeros, 00198 nonZeroIndices, nonZeroCoeffs, rhs, 00199 lpSolution->zVal()); 00200 // Separate. 00201 int num = modkSeparator->separate( nVariables ); 00202 00203 ofstream fout(itsGraph->getFileName(), ios::app); 00204 fout << "\n* Mod :" << theKs[a] << endl; 00205 fout.close(); 00206 00207 // Store solution in abacus. 00208 if (num) { 00209 // This array stores the information of the generated cut. 00210 int *cutInfo; //= new int[3*nVariables]; 00211 // Store the inequalities: lhs * coeff <= rhs. 00212 vector<int> lhs; 00213 vector<int> coeff; 00214 int rhsCut; 00215 int cutSize; // Number of nodes in the inequality. 00216 00217 // Get all inequalities. 00218 for (i=0; i<num; i++) { 00219 // Get next inequality from separator. 00220 cutInfo = modkSeparator->getCut(); 00221 00222 if (cutInfo == NULL || cutInfo[0] == 0) { 00223 if (cutInfo != NULL) { 00224 delete [] cutInfo; 00225 } 00226 continue; 00227 } 00228 00229 // Construct inequality. 00230 cutSize = cutInfo[0]; 00231 lhs.resize(cutSize); 00232 coeff.resize(cutSize); 00233 for (j=0; j<cutSize; j++) { 00234 lhs[j] = cutInfo[j+1]; 00235 } 00236 for (j=0; j<cutSize; j++) { 00237 coeff[j] = cutInfo[j +1 +cutSize]; 00238 } 00239 rhsCut = cutInfo[1 +cutSize +cutSize]; 00240 00241 // Generate new inequality. 00242 GeneralConstraint *generalConstr; 00243 generalConstr = new GeneralConstraint(master, &lhs, &coeff, 00244 rhsCut, itsGraph); 00245 // Add cut to buffer. 00246 cutFound(generalConstr); 00247 00248 // Clean up. 00249 delete[] cutInfo; 00250 }// for 00251 00252 }// if 00253 00254 // Output number of generated cuts. 00255 lpSolution->stableSetMaster()->out() << "\tMod " << theKs[a] << ":\t"; 00256 lpSolution->stableSetMaster()->out() << num << endl; 00257 00258 // Clean up. 00259 delete modkSeparator; 00260 00261 }// for 00262 00263 00264 // Clean up. 00265 delete row; 00266 for (i=0; i<nSlack0Constr; i++){ 00267 delete[] nonZeroIndices[i]; 00268 delete[] nonZeroCoeffs[i]; 00269 } 00270 delete[] nNonZeros; 00271 delete[] rhs; 00272 delete[] nonZeroIndices; 00273 delete[] nonZeroCoeffs; 00274 00275 }// end separate()
|