StableSetModKSeparator Class Reference

#include <StableSetModKSeparator.hh>

List of all members.

Public Member Functions

 StableSetModKSeparator (StableSetLPSolution *solution, Graph *itsGraph)
 ~StableSetModKSeparator ()
virtual void separate ()
void applyRanking (ABA_BUFFER< double > *rank)


Detailed Description

This class realizes the separation of metric (triangle) - inequalities.

Definition at line 35 of file StableSetModKSeparator.hh.


Constructor & Destructor Documentation

StableSetModKSeparator::StableSetModKSeparator StableSetLPSolution solution,
Graph itsGraph
 

Constructor.

Parameters:
*lpSolution Pointer to the current LP-Solution to be separated.
*theGraph Pointer to the graph.

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 }

StableSetModKSeparator::~StableSetModKSeparator  ) 
 

Destructor.

Definition at line 60 of file StableSetModKSeparator.cpp.

00060                                                 {
00061 }


Member Function Documentation

void StableSetModKSeparator::applyRanking ABA_BUFFER< double > *  rank  ) 
 

Rank the inequalities.

Parameters:
*rank Pointer to the ranking of the inequalities.
Returns:
void

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(..)

void StableSetModKSeparator::separate  )  [virtual]
 

Contains the separation procedure. Overrides the pure virtual function of ABA_SEPARATOR.

Parameters:
void 
Returns:
void

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


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