MaxCliquesSeparator Class Reference

#include <MaxCliquesSeparator.hh>

List of all members.

Public Member Functions

 MaxCliquesSeparator (ABA_MASTER *master, StableSetLPSolution *solution, Graph *theGraph, Clique *clique)
 ~MaxCliquesSeparator ()
virtual void separate ()


Detailed Description

This class provides an exact separation procedure for max clique constraints.

Definition at line 39 of file MaxCliquesSeparator.hh.


Constructor & Destructor Documentation

MaxCliquesSeparator::MaxCliquesSeparator ABA_MASTER *  master,
StableSetLPSolution solution,
Graph theGraph,
Clique clique
 

Constructor.

Parameters:
*master Pointer to the master of the problem.
*solution Pointer to the current LP-Solution to be separated.
*theGraph Pointer to the graph of the problem instance.
*clique Pointer to the class Clique.

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 }

MaxCliquesSeparator::~MaxCliquesSeparator  ) 
 

Destructor.

Definition at line 59 of file MaxCliquesSeparator.cpp.

00059                                           {
00060 }


Member Function Documentation

void MaxCliquesSeparator::separate  )  [virtual]
 

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


The documentation for this class was generated from the following files:
Generated on Fri Apr 28 15:50:00 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO