C:/Programme/home/Administrator/CD/stableSetCode/StableSetModKSeparator.cpp

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : StableSetModKSeparator.cpp
00004 //  Description      : Mod-k separation.
00005 //  Author           : Hanna Seitz, Steffen Rebennack
00006 //  Email            : Hanna.Seitz@informatik.uni-heidelberg.de;
00007 //                     srebenac@ix.urz.uni-heidelberg.de;
00008 //                     steffen.rebennack@web.de
00009 //  Copyright        : University of Heidelberg
00010 //  Created on       : Thu Apr 06 11:00:09 2006
00011 //  Last modified by : -
00012 //  Last modified on : -
00013 //  Update count     : 0
00014 //
00016 //
00017 //  Date        Name            Changes/Extensions
00018 //  ----        ----            ------------------
00019 //
00021 
00022 #include <abacus/constraint.h>
00023 #include <abacus/variable.h>
00024 #include "abacus/row.h"
00025 
00026 #include "StableSetModKSeparator.hh"
00027 #include "GeneralConstraint.hh"
00028 #include "Graph.hh"
00029 #include "ModkSeparator.hh"
00030 #include "StableSetLPSolution.hh"
00031 #include "StableSetMaster.hh"
00032 
00033 #include <vector>
00034 
00035 using namespace std;
00036 
00037 
00038 
00039 // -----------------------------------------------------------------------------
00040 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00041 // -----------------------------------------------------------------------------
00042 
00043 
00044 // -----------------------------------------------------------------------------
00045 // C o n s t r u c t o r
00046 // -----------------------------------------------------------------------------
00047 StableSetModKSeparator::StableSetModKSeparator(StableSetLPSolution *solution,
00048                                                Graph *theGraph):
00049     ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 10000),
00050     lpSolution(solution),
00051     itsGraph(theGraph)
00052 {
00053     nVariables = theGraph->numberOfNodes();
00054 }
00055 
00056 
00057 // -----------------------------------------------------------------------------
00058 // D e s t r u c t o r
00059 // -----------------------------------------------------------------------------
00060 StableSetModKSeparator::~StableSetModKSeparator() {
00061 }
00062 
00063 
00064 // -----------------------------------------------------------------------------
00065 // s e p a r a t e
00066 //
00067 // Separate mod-2, mod-3, mod-5 and mod-7 cuts. Use as input the clique
00068 // constraints which have slack 0 and eliminate all nodes of that clique
00069 // which have LP value 0.
00070 // -----------------------------------------------------------------------------
00071 void StableSetModKSeparator::separate() {
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()
00276 
00277 
00278 // -----------------------------------------------------------------------------
00279 // a p p l y R a n k i n g
00280 // -----------------------------------------------------------------------------
00281 void StableSetModKSeparator::applyRanking(ABA_BUFFER<double> *rank) {
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(..)
00340 
00341 

Generated on Fri Apr 28 15:49:59 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO