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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : StableSetSub.cpp
00004 //  Description      : The nodes of the Branchand Cut tree.
00005 //  Author           : Steffen Rebennack
00006 //  Email            : srebenac@ix.urz.uni-heidelberg.de;
00007 //                     steffen.rebennack@web.de
00008 //  Copyright        : (C) 2006 by the University of Heidelberg
00009 //  Created on       : Thu Apr 06 13:40:40 2006
00010 //  Last modified by : -
00011 //  Last modified on : - 
00012 //  Update count     : 0
00013 //
00015 //
00016 //  Date        Name            Changes/Extensions
00017 //  ----        ----            ------------------
00018 //
00020 
00021 
00022 #include "StableSetSub.hh"
00023 #include "abacus/lpsub.h"
00024 #include "abacus/row.h"
00025 #include "Clique.hh"
00026 #include "CliqueConstraint.hh"
00027 #include "CliqueHeuristicsSeparator.hh"
00028 #include "EdgeProjection.hh"
00029 #include "GeneralConstraint.hh"
00030 #include "Graph.hh"
00031 #include "ImprovementHeuristic.hh"
00032 #include "LocalCutSeparator.hh"
00033 #include "LowerBoundHeuristic.hh"
00034 #include "MaxCliquesSeparator.hh"
00035 #include "Node.hh"
00036 #include "OddCyclesSeparator.hh"
00037 #include "RankConstraint.hh"
00038 #include "StableSetBranchRule.hh"
00039 #include "StableSetLPSolution.hh"
00040 #include "StableSetMaster.hh"
00041 #include "StableSetModKSeparator.hh"
00042 #include "StableSetStatistics.hh"
00043 
00044 
00045 
00046 //
00047 // The struct NodesAndDegree is used to store a node with its degree.
00048 // It is used by the branching rule.
00049 //
00050 struct NodesAndDegree {
00051     int    inode;        // index of node
00052     double degree;       // degree of a node
00053 };// struct
00054 
00055 
00056 //
00057 // This operator is used by the sort a set of nodes according to its degree.
00058 //
00059 bool operator<(const NodesAndDegree &a, const NodesAndDegree &b) {
00060         return a.degree > b.degree;
00061 }
00062 
00063 
00064 
00065 // -----------------------------------------------------------------------------
00066 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00067 // -----------------------------------------------------------------------------
00068 
00069 
00070 // -----------------------------------------------------------------------------
00071 // C o n s t r u c t o r
00072 //
00073 // This is the constructor for the root node of the enumeration tree. Calling
00074 // the constructor of the base class ABA_SUB with the arguments:
00075 // 1.) A pointer to the corresponding master of the problem.
00076 // 2.) 10% additional memory allocated for constraints.
00077 // 3.) No additional storage for variables
00078 // 4.) 50% additional space for the nonzeros of the constraint matrix in the
00079 //     LP-solver should be allocated.
00080 // -----------------------------------------------------------------------------
00081 StableSetSub::StableSetSub(ABA_MASTER *master, Graph *theGraph,
00082                            Clique *theClique, EdgeProjection *anEdgeProjection,
00083                            StableSetStatistics *aStatistics):
00084    ABA_SUB(master, 10, 0, 50),
00085    itsGraph(theGraph),
00086    maxCliques(theClique),
00087    theEdgeProjection(anEdgeProjection),
00088    theStatistics(aStatistics),
00089    violatedEdge(false)
00090 {
00091 }
00092 
00093 
00094 // -----------------------------------------------------------------------------
00095 // C o n s t r u c t o r
00096 //
00097 // This is the constructor for a son of an existing node. The constructor of the
00098 // ABACUS class ABA_SUB takes three arguments: a pointer to the master of the
00099 // problem, a pointer to the father of the enumeration tree and the rule
00100 // defining the subspace of solution space associated with this sub porblem.
00101 // -----------------------------------------------------------------------------
00102 StableSetSub::StableSetSub(ABA_MASTER *master, ABA_SUB *father,
00103                            ABA_BRANCHRULE *branchRule, Graph *theGraph,
00104                            Clique *theClique, EdgeProjection *anEdgeProjection,
00105                            StableSetStatistics *aStatistics):
00106    ABA_SUB(master, father, branchRule),
00107    itsGraph(theGraph),
00108    maxCliques(theClique),
00109    theEdgeProjection(anEdgeProjection),
00110    theStatistics(aStatistics)
00111 {
00112 }
00113 
00114 
00115 // -----------------------------------------------------------------------------
00116 // D e s t r u c t o r
00117 // -----------------------------------------------------------------------------
00118 StableSetSub::~StableSetSub() {
00119 }
00120 
00121 
00122 // -----------------------------------------------------------------------------
00123 // f e a s i b l e
00124 //
00125 // This function redefines a pure virtual function of ABACUS. It checks for the
00126 // feasibility of a solution of the LP-relaxation. A solution indicates a 
00127 // Stable Set if all edge constraints are satisfied and all variables are 
00128 // binary. If a solution is feasible, than this function returns true. If in
00129 // addition the value of the primal bound is smaller than the value of this
00130 // feasible solution, the solution and the value of the primal bound are
00131 // updated. The update of the primal bound is done automatically by ABACUS.
00132 // As all the edge constraints are relaxed and not fixed in the cut pool, one
00133 // has to check them prior to the update of the solution.
00134 // -----------------------------------------------------------------------------
00135 bool StableSetSub::feasible() {
00136 
00137     bool feasible;  // True: the LP solution is feasible; else false.
00138 
00139     //
00140     // Check all the edge inequalities.
00141     //
00142     if (true) {
00143         static int MAX_NUM = (int) itsGraph->numberOfNodes() / 2;
00144         static double EPS = 0.000001;
00145         
00146         int newCuts = 0;
00147         int numPrevious = 0;
00148         int num = 0;
00149         int number = -1;
00150 
00151         int i, j, k;
00152         int numberOfNodes = itsGraph->numberOfNodes();
00153         vector<int> adjacentList;
00154         double * solutionVal = xVal_;
00155         vector<int> clique(2);
00156         CliqueConstraint *cliqueConstr;
00157         // Add all violated maximal cliques.
00158         ABA_BUFFER< ABA_CONSTRAINT* > constraint(master_, MAX_NUM);
00159         int size;
00160         int vertex;
00161         int node;
00162         int index;
00163         double val;
00164         int begin;
00165 
00166         violatedEdge = false;
00167 
00168         // Store all inequalities in file 'storeInequalitiesFile' that they
00169         // can be checked if they are valid.
00170         ofstream fout(itsGraph->getFileName(), ios::app);
00171         fout << "\n* Edge inequalities:" << endl;
00172 
00173         for (i=0; i<numberOfNodes; i++) {
00174             if (solutionVal[i] <= EPS) {
00175                 continue;
00176             }
00177             adjacentList = (*itsGraph->getAdjacentList(i));
00178             size = itsGraph->adjacentListSize(i);
00179             for (j=size-1; j>=0; j--) {
00180                 val = solutionVal[i] + solutionVal[adjacentList[j]];
00181 
00182                 if ( (val > (1 + EPS)) && (val < 3)) {
00183                     // Violated edge inequality found.
00184                     vertex = adjacentList[j];
00185                     clique[0] = i;
00186                     clique[1] = vertex;
00187                     adjacentList.erase(adjacentList.begin() + j);
00188                     // Lift to maximal clique.
00189                     // Update adjacentList.
00190                     for (k=adjacentList.size()-1; k>=0; k--) {
00191                         begin = 0;
00192                         if (!itsGraph->isMemberOfAdjacentList(vertex, begin, adjacentList[k])) {
00193                             adjacentList.erase(adjacentList.begin() + k);
00194                         }
00195                     }
00196 
00197                     while (!adjacentList.empty()) {
00198                         index = stableSetMaster()->getRandomNumber(adjacentList.size());
00199                         vertex = adjacentList[index];
00200                         clique.push_back(vertex);
00201                         adjacentList.erase(adjacentList.begin() + index);
00202                         // Update set 'adjacentList'
00203                         for (k=adjacentList.size()-1; k>=0; k--) {
00204                             node = adjacentList[k];
00205                             begin = 0;
00206                             if (!itsGraph->isMemberOfAdjacentList(vertex, begin, node)) {
00207                                 adjacentList.erase(adjacentList.begin() + k);
00208                             }
00209                         }
00210                     }// while
00211 
00212                     // Add this inequality.
00213                     // New constraint.
00214                     sort(clique.begin(), clique.end());
00215                     cliqueConstr = new CliqueConstraint(master_, &clique, itsGraph);
00216                     constraint.push(cliqueConstr);
00217                     newCuts++;
00218 
00219                     // Clean up
00220                     clique.clear();
00221                     clique.resize(2);
00222                     adjacentList = (*itsGraph->getAdjacentList(i));
00223 
00224                     if (newCuts == MAX_NUM) {
00225                         break;
00226                     }
00227                 }
00228             }// for
00229             if (newCuts == MAX_NUM) {
00230                 break;
00231             }
00232         }
00233 
00234         fout.close();
00235 
00236         if (newCuts) {
00237             // Add cuts to the pool.
00238             numPrevious = stableSetMaster()->cliqueCutPool()->number();
00239             number = addCons(constraint, stableSetMaster()->cliqueCutPool());
00240             number = stableSetMaster()->cliqueCutPool()->number();
00241             number -= numPrevious;
00242             num = number >= 0 ? number : num;
00243             violatedEdge = true;            
00244 
00245             // Output
00246             master_->out() << "\tEdge inequalities:\t" << num << endl;
00247 
00248             // Update statistics.
00249             theStatistics->edgeInequalitiesCut(num);
00250 
00251             return false;
00252         }
00253         else {
00254             master_->out() << "\tAll edge inequalities are valid" << endl; 
00255         }
00256     }// if
00257 
00258 
00259     // The function integerFeasible() checks if the solution of the
00260     // LP-relaxation is primally feasible. This means that all variables are
00261     // binary and all constraints of the LP relaxation are satisfied.
00262     feasible = integerFeasible();
00263 
00264     // ABACUS does not update the solution - so you do.
00265     if (feasible) {
00266         // LP solution is incedence vector of a Stable Set
00267         // If the value of the Stable Set is higher than the best known then
00268         // we update the solution. xVal_ stores the values of the variables of
00269         // the LP solution.
00270         if (lp_->value() >= (master_->primalBound() + .5)) {
00271 
00272             int i;
00273             int numberOfNodes = itsGraph->numberOfNodes();      // Problem size.
00274             double OneMinusEps = 1.0 - master_->machineEps();   // Precision.
00275             vector<int> *bestSolution = stableSetMaster()->getSolution();
00276             bestSolution->clear();
00277 
00278             for (i=0; i<numberOfNodes; i++) {
00279                 // xVal[i] == 1?
00280                 if ((xVal_[i] > OneMinusEps) && (xVal_[i] < 2)) {
00281                     bestSolution->push_back(i);
00282                 }
00283                 else {
00284                     if ((xVal_[i] > master_->machineEps())
00285                         || (xVal_[i] < -master_->machineEps())) {
00286                         master_->err() << "StableSetMASTER::update():";
00287                         master_->err() << " x is not incidence vector ";
00288                         master_->err() << "of a Stable Set " << endl;
00289                         exit(master_->Fatal);
00290                     }
00291                 }
00292             }
00293 
00294             master_->out() << "\nSolution was integer feasible with weight:\t";
00295             master_->out() << (int)lp_->value() << "." << endl;
00296 
00297             // Update lower bound (best known feasible solution)
00298             // (this is done automatically by ABACUS, too).
00299             master_->primalBound((int)lp_->value());
00300             theStatistics->solutionFound(0);
00301         }
00302     }
00303 
00304     return feasible;
00305 
00306 }// end: bool feasible()
00307 
00308 
00309 // -----------------------------------------------------------------------------
00310 // g e n e r a t e S o n
00311 //
00312 // This function redefindes a pure virtual function of the base class ABA_SUB.
00313 // While the function stableSetMaster::firstSub() initializes the root node of
00314 // the branch-and-bound tree with a problem specific subproblem, this function
00315 // generates a problem specific son of a subproblem.
00316 // -----------------------------------------------------------------------------
00317 ABA_SUB *StableSetSub::generateSon(ABA_BRANCHRULE *rule) {
00318     return new StableSetSub(master_, this, rule, itsGraph, maxCliques,
00319                             theEdgeProjection,
00320                             theStatistics);
00321 }
00322 
00323 
00324 // -----------------------------------------------------------------------------
00325 // i m p r o v e
00326 //
00327 // This is a redefinition of the pure virtual ABACUS function improve(). It is
00328 // called after every solved LP-relaxation. 
00329 // This function uses two heuristics:
00330 // ~ Construction of a stabel set via a rounding heuristics from a fractional
00331 //   LP solution. This is done by the lowerBoundHeuristic.
00332 // ~ Improve a stable set.
00333 // If one of the heuristics computes a better solution than the
00334 // best known one, this solution is stored and the lower bound is updated. In
00335 // this case the function return value 1. If no better solution is found it
00336 // will return 0.
00337 // -----------------------------------------------------------------------------
00338 int StableSetSub::improve(double &primalValue) {
00339 
00340     int status = 0;  // This stores the return value.
00341     double value;
00342 
00343     LowerBoundHeuristic *roundingHeuristic;
00344     roundingHeuristic = new LowerBoundHeuristic(master_, itsGraph,
00345                                                 theStatistics),
00346     // Call heuristic.
00347     status = roundingHeuristic->computeSolution(value, xVal_, level());
00348         
00349     // Clean up.
00350     delete roundingHeuristic;       
00351 
00352     if (!itsGraph->weighted()) {
00353         // Generate object.
00354         ImprovementHeuristic *improveHeuristic;
00355         improveHeuristic = new ImprovementHeuristic(master_, itsGraph,
00356                                                          theStatistics);
00357              
00358         // Improve current solution.
00359         status = (improveHeuristic->improve(value) || status);
00360   
00361         // Clean up.
00362         delete improveHeuristic;
00363     }
00364 
00365     if (status) {
00366        primalValue = value;
00367    }
00368    
00369    return status;
00370 }// end: int improve(..)
00371 
00372 
00373 // -----------------------------------------------------------------------------
00374 // s e p a r a t e
00375 //
00376 // This function redefines a pure virtual function of ABACUS. It separates the
00377 // following inequalities (in this order):
00378 // ~ pool separation
00379 // ~ clique separation of memory (only with exact clique separation)
00380 // ~ odd cycle separation and lifting of trinagles
00381 // ~ cliques (heuristic)
00382 // ~ edge projection
00383 // ~ mod-k cuts
00384 // ~ local cuts
00385 // ~ exact clique separation
00386 // ~ large rank inequality
00387 //
00388 // Remark: The check if all computed inequalities are valid is done
00389 //         at the end of this program in StableSetMain.
00390 // Remark: The edge inequalities are separated in the function feasible().
00391 //
00392 // -----------------------------------------------------------------------------
00393 int StableSetSub::separate() {
00394  
00395     int i, j, k;                    // Loop counter.
00396     int numberOfGeneratedCuts = 0;  // Store the number of added cuts.
00397     int newCuts = 0;
00398     int num;                        // Number of cuts.
00399     int number = -1;
00400     int numPrevious;
00401     int error;
00402     static int largeCutCnt = 0;
00403 
00404     // Parameter.
00405     static int MIN_NUMBER_OF_CUTS = (int) itsGraph->numberOfNodes() / 10;
00406     static double EPS = 0.000001;
00407  
00408  
00409     // Create LP solution instance: needed for the separation classes.
00410     StableSetLPSolution *currentLPSolution;
00411     currentLPSolution = new StableSetLPSolution(master_, this,
00412                                                 itsGraph->numberOfNodes(),
00413                                                 xVal_);
00414 
00415       
00416     
00417     //  
00418     // If the edge inequalities are not satisfied separate cliques and check pool.
00419     //
00420     if (violatedEdge) {
00421         violatedEdge = false;
00422 
00423         //
00424         // Heuristic clique separation.
00425         //
00426         if (stableSetMaster()->m_CliqueHeuristicsSeparation) {
00427 
00428                 ofstream fout(itsGraph->getFileName(), ios::app);
00429                 fout << "\n* Clique heuristics:" << endl;
00430                 fout.close();
00431 
00432                 // Create new object.
00433                 CliqueHeuristicsSeparator *cliqueHeuristicsSep;
00434                 cliqueHeuristicsSep = new CliqueHeuristicsSeparator(
00435                                                        currentLPSolution,
00436                                                        itsGraph);
00437                 // Separate.
00438                 cliqueHeuristicsSep->separate();
00439 
00440                 // Add inequalities.
00441                 numPrevious = stableSetMaster()->cliqueCutPool()->number();
00442                 number = addCons(cliqueHeuristicsSep->cutBuffer(),
00443                       stableSetMaster()->cliqueCutPool());
00444                 number = stableSetMaster()->cliqueCutPool()->number();
00445                 number -= numPrevious;
00446                 num = number >= 0 ? number : num;
00447                 newCuts += num;
00448                 numberOfGeneratedCuts =+ newCuts;
00449 
00450                 // Output.
00451                 master_->out() << "\tCliques:\t\t" << num << endl;
00452 
00453                 // Update statistics.
00454                 theStatistics->cliqueHeuristicsCut(num);
00455 
00456                 // Clean up.
00457                 delete cliqueHeuristicsSep;
00458                 delete currentLPSolution;
00459         }
00460 
00461 
00462         //
00463         // Constraint pool separation.
00464         //
00465         if (stableSetMaster()->m_PoolSeparation) {
00466 
00467                 number = constraintPoolSeparation(0,
00468                                          stableSetMaster()->cycleCutPool());
00469                 number += constraintPoolSeparation(0,
00470                                          stableSetMaster()->cliqueCutPool());
00471                 number += constraintPoolSeparation(0,
00472                                          stableSetMaster()->rankCutPool());
00473 //              number += constraintPoolSeparation(0,
00474 //                                       stableSetMaster()->generalCutPool());
00475             
00476                 // Update statistics.
00477                 theStatistics->poolSeparationCut(number);
00478         }
00479         
00480         // Return.    
00481         return newCuts;    
00482     } 
00483     
00484      
00485    
00486     //
00487     // Odd cycle separation.
00488     //
00489     if (stableSetMaster()->m_oddCycleSeparation) {
00490 
00491         ofstream fout(itsGraph->getFileName(), ios::app);
00492         fout << "\n* Odd Cycles:" << endl;
00493 
00494         // Create new object.
00495         OddCyclesSeparator *oddCyclesSep;
00496         oddCyclesSep = new OddCyclesSeparator(master_, currentLPSolution,
00497                                               itsGraph, false);
00498         // Separate.
00499         oddCyclesSep->separate();
00500 
00501         fout.close();
00502         
00503         // Add inequalities.
00504         // Add cuts to the pool.
00505         numPrevious = stableSetMaster()->cycleCutPool()->number();
00506         number = addCons(oddCyclesSep->cutBuffer(),
00507                       stableSetMaster()->cycleCutPool());
00508         number = stableSetMaster()->cycleCutPool()->number();
00509         number -= numPrevious;
00510         num = number >= 0 ? number : num;
00511         numberOfGeneratedCuts += num;
00512         newCuts += num;
00513 
00514         // Output.
00515         master_->out() << "\tOdd cycles:\t\t" << num << endl;
00516 
00517         // Update statistics.
00518         theStatistics->oddCyclesCut(num);
00519 
00520         // If the odd cycle separation found 3-cycles than they are saved
00521         // so we can increase them to max cliques.
00522         if (oddCyclesSep->getSizeOfClique() != 0) {
00523 
00524             ofstream fout(itsGraph->getFileName(), ios::app);
00525             fout << "\n* Lifted triangles:" << endl;
00526             fout.close();
00527 
00528             num = increaseToMaximalClique(oddCyclesSep);
00529             numberOfGeneratedCuts += num;
00530             newCuts += num;
00531 
00532             // Output.
00533             master_->out() << "\tLifted odd cycles:\t" << num << endl;
00534 
00535             // Update statistics.
00536             theStatistics->liftedOddCyclesCut(num);
00537         }
00538 
00539         // Clean up.
00540         delete oddCyclesSep;
00541     }
00542 
00543 
00544     //
00545     // Heuristic clique separation.
00546     //
00547     if (stableSetMaster()->m_CliqueHeuristicsSeparation) {
00548 
00549         ofstream fout(itsGraph->getFileName(), ios::app);
00550         fout << "\n* Clique heuristics:" << endl;
00551         fout.close();
00552 
00553         // Create new object.
00554         CliqueHeuristicsSeparator *cliqueHeuristicsSep;
00555         cliqueHeuristicsSep = new CliqueHeuristicsSeparator(
00556                                                 currentLPSolution,
00557                                                 itsGraph);
00558         // Separate.
00559         cliqueHeuristicsSep->separate();
00560 
00561         // Add inequalities.
00562         numPrevious = stableSetMaster()->cliqueCutPool()->number();
00563         number = addCons(cliqueHeuristicsSep->cutBuffer(),
00564                       stableSetMaster()->cliqueCutPool());
00565         number = stableSetMaster()->cliqueCutPool()->number();
00566         number -= numPrevious;
00567         num = number >= 0 ? number : num;
00568         numberOfGeneratedCuts += num;
00569         newCuts += num;
00570 
00571         // Output.
00572         master_->out() << "\tCliques:\t\t" << num << endl;
00573 
00574         // Update statistics.
00575         theStatistics->cliqueHeuristicsCut(num);
00576 
00577         // Clean up.
00578         delete cliqueHeuristicsSep;
00579     }
00580 
00581     if (newCuts >= MIN_NUMBER_OF_CUTS) {
00582         // Clean up.
00583         delete currentLPSolution;
00584         // End separation, if enough cuts are generated.
00585         return numberOfGeneratedCuts;
00586     }
00587 
00588 
00589 
00590     //
00591     // Edge projection.
00592     //
00593     if (stableSetMaster()->m_EdgeProjection) {
00594 
00595         ofstream fout(itsGraph->getFileName(), ios::app);
00596         fout << "\n* Edge projection:" << endl;
00597         fout.close();
00598 
00599         int cnt = 0;
00600         bool goon = true;
00601         while (goon) {
00602         
00603             // Separate.
00604             error = theEdgeProjection->separate(xVal_);
00605 
00606             if (error) {
00607                 master_->err() << "\nERROR:\n";
00608                 master_->err() << "StableSetSub::separate():";
00609                 master_->err() << " There was a problem with the edge";
00610                 master_->err() << " projection.\n" << endl;
00611                 master_->err() << "Program aborted." << endl;
00612                 exit(master_->Fatal);
00613             }
00614 
00615             // Get inequalities
00616             vector< vector<int>* >* inequalities = theEdgeProjection->getLHS();
00617             vector<int> *rhs = theEdgeProjection->getRHS();
00618 
00619             if (inequalities == NULL) {
00620                 num = 0;
00621             }
00622             else {
00623                 // The inequality type.
00624                 RankConstraint *rankConstr;
00625                 // Add this inequalities.
00626                 ABA_BUFFER< ABA_CONSTRAINT* > constraint(master_,
00627                                                      inequalities->size());
00628                 // Create new inequalities for ABACUS
00629                 for (i=0; i<inequalities->size(); i++) {
00630                     rankConstr = new RankConstraint(master_,
00631                                                     (*inequalities)[i],
00632                                                     (*rhs)[i],
00633                                                     itsGraph);
00634                     constraint.push(rankConstr);
00635                 }// for
00636 
00637                 // Add new inequalities to the pool.
00638                 numPrevious = stableSetMaster()->rankCutPool()->number();
00639                 number = addCons(constraint, stableSetMaster()->rankCutPool());
00640                 number = stableSetMaster()->rankCutPool()->number();
00641                 number -= numPrevious;
00642                 num = number >= 0 ? number : num;
00643                 numberOfGeneratedCuts += num;
00644                 newCuts += num;
00645             }// else
00646 
00647             // Output
00648             master_->out() << "\tEdge projection:\t" << num << endl;
00649 
00650             // Update statistics.
00651             theStatistics->edgeProjectionCut(num);
00652             
00653             cnt++;
00654             if (level() == 1 && (cnt >= 10 || newCuts >= 4*MIN_NUMBER_OF_CUTS)) {
00655                 goon = false;
00656             }
00657             if (level() != 1 && (newCuts >= MIN_NUMBER_OF_CUTS || cnt >= 5)) {
00658                 goon = false;
00659             }
00660             
00661         }// while
00662     }//  if
00663     if (newCuts >= MIN_NUMBER_OF_CUTS) {
00664         // Clean up.
00665         delete currentLPSolution;
00666         // End separation, if enough cuts are generated.
00667         return numberOfGeneratedCuts;
00668     }
00669 
00670 
00671     //
00672     // Constraint pool separation.
00673     //
00674     if (stableSetMaster()->m_PoolSeparation) {
00675 
00676         numberOfGeneratedCuts += constraintPoolSeparation(0,
00677                                          stableSetMaster()->cycleCutPool());
00678         numberOfGeneratedCuts += constraintPoolSeparation(0,
00679                                          stableSetMaster()->cliqueCutPool());
00680         numberOfGeneratedCuts += constraintPoolSeparation(0,
00681                                          stableSetMaster()->rankCutPool());
00682         numberOfGeneratedCuts += constraintPoolSeparation(0,
00683                                         stableSetMaster()->generalCutPool());
00684 
00685         // Update statistics.
00686         theStatistics->poolSeparationCut(numberOfGeneratedCuts);
00687     }
00688     if (newCuts > 0) {
00689         // Clean up.
00690         delete currentLPSolution;
00691         // End separation, if enough cuts are generated.
00692         return numberOfGeneratedCuts;
00693     }
00694 
00695     //
00696     //  Maximally violated Mod k.
00697     //
00698     if (stableSetMaster()->m_ModKCutsSeparation) {
00699 
00700         static int MAX_GEN_NR = 100000;
00701 
00702         // Vorbereitungen fuer das Ranking der separierten Constraints
00703         ABA_STANDARDPOOL<ABA_CONSTRAINT,ABA_VARIABLE> *poolPointer;
00704         poolPointer = stableSetMaster()->cliqueCutPool();
00705         ABA_BUFFER<double> *rank = new ABA_BUFFER<double>(master_, MAX_GEN_NR);
00706         ABA_BUFFER<bool> *keepInPool = new ABA_BUFFER<bool>(master_,MAX_GEN_NR);
00707         /* If (*keepInPool)[i] is true the i-th added constraint will even
00708         be stored in the pool if it is not added to the active constraints.*/
00709         for (int i=0; i<keepInPool->size();i++) {
00710             (*keepInPool)[i] = false;
00711         }
00712         // Create new object to separate the mod k cuts.
00713         StableSetModKSeparator *stableSetModKSeparator;
00714         stableSetModKSeparator = new StableSetModKSeparator(currentLPSolution,
00715                                               itsGraph);
00716 
00717         // Separate.
00718         stableSetModKSeparator->separate();
00719 
00720         // Rank the inequalities.
00721 //      stableSetModKSeparator->applyRanking(rank);
00722 
00723         // Add the cuts to the pool.
00724         numPrevious = stableSetMaster()->generalCutPool()->number();
00725         number = addCons(stableSetModKSeparator->cutBuffer(),
00726                       stableSetMaster()->generalCutPool());//, keepInPool, rank);
00727         number = stableSetMaster()->generalCutPool()->number();
00728         number -= numPrevious;
00729         num = number >= 0 ? number : num;
00730         numberOfGeneratedCuts += num;
00731         newCuts += num;
00732 
00733         // Update statistics.
00734         theStatistics->modKCut(num);
00735 
00736         // Clean up.
00737         delete rank;
00738         delete keepInPool;
00739         delete stableSetModKSeparator;
00740     }
00741     if (newCuts != 0) {
00742         // Clean up.
00743         delete currentLPSolution;
00744         // End separation, if enough cuts are generated.
00745         return numberOfGeneratedCuts;
00746     }
00747 
00748 
00749     //
00750     // Local cuts.
00751     //
00752     if (stableSetMaster()->m_LocalCutSeparation) {
00753 
00754         ofstream fout(itsGraph->getFileName(), ios::app);
00755         fout << "\n* Local Cut:" << endl;
00756         fout.close();
00757 
00758         // Create separator
00759         LocalCutSeparator *localCuts;
00760         localCuts = new LocalCutSeparator(master_, currentLPSolution, itsGraph);
00761 
00762         // Separate.
00763         localCuts->separate();
00764 
00765         // Add the cuts to the pool.
00766         numPrevious = stableSetMaster()->generalCutPool()->number();
00767         number = addCons(localCuts->cutBuffer(),
00768                       stableSetMaster()->generalCutPool());
00769         number = stableSetMaster()->generalCutPool()->number();
00770         number -= numPrevious;
00771         num = number >= 0 ? number : num;
00772         numberOfGeneratedCuts += num;
00773         newCuts += num;
00774 
00775         // Output.
00776         master_->out() << "\tLocal cut:\t" << num << endl;
00777 
00778         // Update statistics.
00779         theStatistics->localCutCut(1);
00780 
00781         // Clean up.
00782         delete localCuts;
00783     }
00784     if (newCuts != 0) {
00785         // Clean up.
00786         delete currentLPSolution;
00787         // End separation, if enough cuts are generated.
00788         return numberOfGeneratedCuts;
00789     }
00790 
00791 
00792     //
00793     // Check all computed cliques.
00794     //
00795     if (stableSetMaster()->m_maxCliqueSeparation) {
00796 
00797         // Store the cliques to be violated.
00798         vector<int*> cliques;
00799 
00800         // Check inequalities.
00801         num = maxCliques->checkMaxCliques(&cliques, xVal_);
00802 
00803         // Add new constraints.
00804         if (num != 0) {
00805 
00806             CliqueConstraint *cliqueConstr;
00807             vector<int> nodesOfClique;
00808 
00809             ofstream fout(itsGraph->getFileName(), ios::app);
00810             fout << "\n* Cliques from pool:" << endl;
00811 
00812             // Add all violated maximal cliques.
00813             ABA_BUFFER< ABA_CONSTRAINT* > constraint(master_, num);
00814 
00815             for (i=0; i<num; i++) {
00816                 nodesOfClique.resize(cliques[i][0]);
00817                 for (j=0; j<cliques[i][0]; j++) {
00818                     nodesOfClique[j] = cliques[i][j+1];
00819                 }
00820                 // New constraint.
00821                 cliqueConstr = new CliqueConstraint(master_, &nodesOfClique,//
00822                                                     itsGraph);
00823                 constraint.push(cliqueConstr);
00824 
00825                 // Clean up.
00826                 nodesOfClique.clear();
00827             }
00828 
00829             // Add cuts to the pool.
00830             numPrevious = stableSetMaster()->cliqueCutPool()->number();
00831             number = addCons(constraint, stableSetMaster()->cliqueCutPool());
00832             number = stableSetMaster()->cliqueCutPool()->number();
00833             number -= numPrevious;
00834             num = number > 0 ? number : num;
00835             numberOfGeneratedCuts += num; 
00836             newCuts += num;
00837 
00838             fout.close();
00839 
00840             // Output
00841             master_->out() << "\tMaximal cliques from memory:\t" << num << endl;
00842 
00843             // Update statistics.
00844             theStatistics->maxCliquesMemoryCut(num);
00845 
00846         }// if
00847     }
00848 
00849 
00850     //
00851     // Exact clique separation.
00852     //
00853     if ((stableSetMaster()->m_maxCliqueSeparation)
00854         && !(maxCliques->allMaximalCliquesFound())
00855        ) {
00856 
00857         ofstream fout(itsGraph->getFileName(), ios::app);
00858         fout << "\n* Exact max clique:" << endl;
00859         fout.close();
00860         
00861         // Create max clique separator.
00862         MaxCliquesSeparator *maxCliquesSep;
00863         maxCliquesSep = new MaxCliquesSeparator(master_, currentLPSolution,
00864                                                 itsGraph, maxCliques);
00865         // Separate.
00866         maxCliquesSep->separate();
00867 
00868         // Add the cuts to the pool.
00869         numPrevious = stableSetMaster()->cliqueCutPool()->number();
00870         num = addCons(maxCliquesSep->cutBuffer(),
00871                       stableSetMaster()->cliqueCutPool());
00872         num = stableSetMaster()->cliqueCutPool()->number();
00873         num -= numPrevious;
00874         numberOfGeneratedCuts += num;
00875 
00876         // Output
00877         master_->out() << "\tExact cliques:\t" << num << endl;
00878 
00879         // Update statistics.
00880         theStatistics->exactCliquesCut(num);
00881 
00882         // CLean up.
00883         delete maxCliquesSep;
00884     }
00885 
00886 
00887     //
00888     // Large rank inequality.
00889     //
00890     int MAX_NUMER_OF_LARGE_CUTS = itsGraph->numberOfNodes() / 5;
00891     if (itsGraph->numberOfNodes() > 100 && level()==1
00892         && largeCutCnt < MAX_NUMER_OF_LARGE_CUTS) {
00893         largeCutCnt++;
00894 
00895         master_->out() << "Compute large inequality." << endl;
00896 
00897         // Separate.
00898         error = theEdgeProjection->computeLargeInequality(xVal_, stableSetMaster());
00899 
00900         if (error) {
00901             master_->err() << "\nERROR:\n";
00902             master_->err() << "StableSetSub::compteLargeInequality():";
00903             master_->err() << " There was a problem with the edge";
00904             master_->err() << " projection.\n" << endl;
00905             master_->err() << "Program aborted." << endl;
00906             exit(master_->Fatal);
00907         }
00908 
00909         // Get inequalities
00910         vector< vector<int>* >* inequalities = theEdgeProjection->getLHS();
00911         vector<int> *rhs = theEdgeProjection->getRHS();
00912 
00913         ofstream fout(itsGraph->getFileName(), ios::app);
00914         fout << "\n* Large Rank Inequality:";
00915         fout.close();
00916 
00917         if (inequalities == NULL) {
00918             num = 0;
00919         }
00920         else {  
00921             
00922             ABA_BUFFER< ABA_CONSTRAINT* > constraint(master_, 1);
00923             
00924             // New constraint.
00925             RankConstraint *rankConstr;
00926             rankConstr = new RankConstraint(master_, (*inequalities)[0],//
00927                                             (*rhs)[0], true, itsGraph);
00928             constraint.push(rankConstr);
00929 
00930             // Add cuts to the pool.
00931             numPrevious = stableSetMaster()->rankCutPool()->number();
00932             number = addCons(constraint, stableSetMaster()->rankCutPool());
00933             number = stableSetMaster()->rankCutPool()->number();
00934             number -= numPrevious;
00935             num = number >= 0 ? number : num; 
00936             numberOfGeneratedCuts += num;
00937             newCuts += num;
00938 
00939             // Update statistics.
00940             theStatistics->largeCutCut(1);    
00941         }
00942     }
00943 
00944     // Clean up.
00945     delete currentLPSolution;
00946 
00947     // Return the number of computed inequalities.
00948     return numberOfGeneratedCuts;
00949 
00950 }// end: int separate()
00951 
00952 
00953 // -----------------------------------------------------------------------------
00954 // g e n e r a t e B r a n c h i n g R u l e s
00955 //
00956 // Branch according to Bals and Yu, 1986. Use a covering of inequalities from
00957 // the pool to get alpha.
00958 // -----------------------------------------------------------------------------
00959 int StableSetSub::generateBranchRules(ABA_BUFFER<ABA_BRANCHRULE*> &rules) {
00960 
00961     int i, j, k;
00962     int itsDegree;
00963     int size = itsGraph->numberOfNodes();
00964     int alpha = (int) master_->lowerBound();
00965     
00966     vector<int> freeVariables;
00967     vector<int> L;
00968 
00969     vector<NodesAndDegree> storeNodes;
00970     NodesAndDegree a;
00971     ABA_FSVARSTAT * status;
00972 
00973     if (level() == 1) {
00974         // Store dual bound.
00975         theStatistics->setDualBound(lp()->value());
00976         // Store weight of best stable set found so far.
00977         theStatistics->setAlphaRoot((int) master_->primalBound());
00978         // Change tailing off.
00979         master_->tailOffNLp(2);
00980         master_->tailOffPercent(0.01);
00981     }
00982 
00983 
00984     //
00985     // Get all nodes which are NOT fixed and calculate alpha tilde.
00986     //
00987     for (i=0; i<size; i++) {
00988         status = fsVarStat(i);
00989         if (status->status() == 0) {
00990             freeVariables.push_back(i);
00991         }
00992         else {
00993             if (status->status() == 3 || status->status() == 6) {
00994                 alpha -= 1;
00995             }
00996         }
00997     }
00998 
00999     
01000     
01001     if (freeVariables.empty()) {
01002     cout << "No free variables" << endl;
01003         return 1;
01004     }
01005 
01006     //
01007     // Calculate degree of each node and sort.
01008     //
01009     vector<int> * list;
01010     for (i=freeVariables.size()-1; i>=0; i--) {
01011         itsDegree = 0;
01012         list = itsGraph->getAdjacentList(freeVariables[i]);
01013         for (j=itsGraph->adjacentListSize(freeVariables[i])-1; j>=0; j--) {
01014             k=0;
01015             while (k<freeVariables.size()) {
01016                 if ((*list)[j] <= freeVariables[k]) {
01017                     break;
01018                 }
01019                 k++;
01020             }
01021             if (k < freeVariables.size()) {
01022                 if ((*list)[j] == freeVariables[k]) {
01023                     itsDegree++;
01024                 }
01025             }
01026         }
01027 
01028         a.inode = freeVariables[i];
01029         a.degree = itsDegree;
01030         storeNodes.push_back(a);
01031     }// for
01032 
01033     // Sort in (non-)ascending order of degree.
01034     sort(storeNodes.begin(), storeNodes.end());
01035         
01036 
01037     //
01038     //  Construct from the computed inequalities of the pool a good covering.
01039     //
01040     ABA_STANDARDPOOL<ABA_CONSTRAINT,ABA_VARIABLE> *poolPointer;
01041     int nConstraints;
01042     ABA_CONSTRAINT *constrPointer;
01043     ABA_ROW *row = new ABA_ROW(stableSetMaster(), itsGraph->numberOfNodes());
01044     vector<int> W;      
01045     double bestWeight;
01046     double itsWeight;
01047     int constrSlot;
01048     int constrType;
01049     int index;
01050     int numberOfVariablesInConstr;
01051     int chiBar = 0;
01052     int nodeToCover;
01053     
01054     //
01055     // Make it big...
01056     //
01057     while ((chiBar < alpha) && !storeNodes.empty()) {
01058         bestWeight = -1;
01059         constrSlot = -1;
01060         constrType = -1;
01061         
01062         nodeToCover = storeNodes.back().inode;
01063         storeNodes.pop_back();
01064         W.push_back(nodeToCover);
01065 
01066         
01067         // Check first the clique Cut pool.
01068         poolPointer = stableSetMaster()->cliqueCutPool();
01069         // Number of conatraints in the pool.
01070         nConstraints = poolPointer->number();
01071 
01072         for (i=0; i<nConstraints; i++){
01073             // Get next constraint.
01074             constrPointer = (ABA_CONSTRAINT *)(( poolPointer->slot(i) )->conVar());
01075             if (constrPointer == NULL) {
01076                 continue;
01077             }
01078             if (((int) constrPointer->rhs() + chiBar) > alpha ) {
01079                  continue;
01080             } 
01081             
01082             // Get information of this inequality.
01083             itsWeight = 0;    
01084             numberOfVariablesInConstr = constrPointer->genRow(actVar(), *row);
01085                 
01086             // Check if the node to cover is in that inequality.
01087             j = 0;
01088             while (j<numberOfVariablesInConstr) {
01089                 if (nodeToCover <= row->support(j)) {
01090                     break;
01091                 }
01092                 j++;
01093             }
01094             if (j==numberOfVariablesInConstr) {
01095                 row->clear();
01096                 continue;           
01097             }
01098             if (nodeToCover != row->support(j)) {
01099                 row->clear();
01100                 continue;
01101             }
01102 
01103             for (j=0; j<numberOfVariablesInConstr; j++) {
01104                 index = row->support(j);
01105                 // Check if this node is free.
01106                 for (k=0; k<storeNodes.size(); k++) {
01107                     if (storeNodes[k].inode == index) {
01108                         itsWeight++;
01109                         break;
01110                     }
01111                 }
01112             }
01113             row->clear();
01114 
01115             if (itsWeight > bestWeight) {
01116                 bestWeight = itsWeight;
01117                 constrSlot = i;
01118                 constrType = 0;
01119             }
01120             
01121         }
01122         
01123         // Check next the rank cut pool.
01124         poolPointer = stableSetMaster()->rankCutPool();
01125         // Number of conatraints in the pool.
01126         nConstraints = poolPointer->number();
01127 
01128         for (i=0; i<nConstraints; i++){
01129             // Get next constraint.
01130             constrPointer = (ABA_CONSTRAINT *)(( poolPointer->slot(i) )->conVar());
01131             if (constrPointer == NULL) {
01132                 continue;
01133             }
01134             if (((int) constrPointer->rhs() + chiBar) > alpha ) {
01135                  continue;
01136             } 
01137             
01138             // Get information of this inequality.
01139             itsWeight = 0;    
01140             numberOfVariablesInConstr = constrPointer->genRow(actVar(), *row);
01141 
01142             
01143             // Check if the node to cover is in that inequality.
01144             j = 0;
01145             while (j<numberOfVariablesInConstr) {
01146                 if (nodeToCover <= row->support(j)) {
01147                     break;
01148                 }
01149                 j++;
01150             }
01151             if (j==numberOfVariablesInConstr) {
01152                 row->clear();
01153                 continue;           
01154             }
01155             if (nodeToCover != row->support(j)) {
01156                 row->clear();
01157                 continue;
01158             }
01159             
01160             
01161 
01162 
01163             for (j=0; j<numberOfVariablesInConstr; j++) {
01164                 index = row->support(j);
01165                 // Check if this node is free.
01166                 for (k=0; k<storeNodes.size(); k++) {
01167                     if (storeNodes[k].inode==index) {
01168                         itsWeight++;
01169                         break;
01170                     }
01171                 }
01172             }
01173             row->clear();
01174             
01175             itsWeight = itsWeight / constrPointer->rhs();           
01176 
01177             if (itsWeight > bestWeight) {
01178                 bestWeight = itsWeight;
01179                 constrSlot = i;
01180                 constrType = 1;
01181             }
01182         }
01183         
01184         
01185         if (bestWeight == -1) {
01186             W.push_back(nodeToCover);
01187             chiBar += 1;
01188             break;
01189         }       
01190 
01191                 
01192         // Get this best inequality.
01193         if (constrType == 0) {
01194             poolPointer = stableSetMaster()->cliqueCutPool();   
01195         }
01196         else {
01197             poolPointer = stableSetMaster()->rankCutPool();
01198         } 
01199         constrPointer = (ABA_CONSTRAINT *)(( poolPointer->slot(constrSlot) )->conVar());
01200         
01201         numberOfVariablesInConstr = constrPointer->genRow(actVar(), *row);  
01202         for (j=0; j<numberOfVariablesInConstr; j++) {
01203         
01204             index = row->support(j);
01205             if (index == nodeToCover) {
01206                 continue;
01207             } 
01208             // Check if this node is not contained in W.
01209             k = 0;
01210             while (k<W.size()) {
01211                 if (W[k] == index) {
01212                     break;
01213                 }       
01214                 k++;
01215             }    
01216             if (k == W.size()) {
01217                 W.push_back(index);
01218                 // Delete this node of the list of free nodes.
01219                 storeNodes.size();
01220                 for (k=0; k<storeNodes.size(); k++) {
01221                     if (storeNodes[k].inode == index) {
01222                         storeNodes.erase(storeNodes.begin() + k);
01223                         break;
01224                     }
01225                 }
01226             }
01227         }
01228         row->clear();
01229         
01230         chiBar += (int) constrPointer->rhs();
01231     }// while()
01232 
01233 
01234     if (chiBar > alpha) {
01235         cout << "Branching was wrong!" << endl;
01236         exit(master_->Fatal);
01237     }
01238 
01239     //
01240     // Generate subproblems to branch on.
01241     //
01242     int node;
01243     int vertex;
01244     StableSetBranchRule *newBranchRule;
01245     int numberOfSubProblems = storeNodes.size();
01246     master_->out() << "Number of sub problems:\t" << numberOfSubProblems << endl;
01247     rules.realloc(numberOfSubProblems);
01248     
01249     
01250     for (i=numberOfSubProblems-1; i>=0; i--) {
01251         node = storeNodes[i].inode;
01252 
01253         // L is neighborhood of node i and set v_j for j > i;
01254         for (j=0; j<i; j++) {
01255             L.push_back(storeNodes[j].inode);
01256         }
01257         for (j=0; j<itsGraph->adjacentListSize(node); j++) {
01258             vertex = itsGraph->adjacentListElement(node, j);
01259             // Check if this node is already contained in the set.
01260             for (k=0; k<L.size(); k++) {
01261                 if (vertex == L[k]) {
01262                     break;
01263                 }
01264                 if (k == L.size()-1) {
01265                     L.push_back(vertex);
01266                 }
01267             }
01268             if (L.empty()) {
01269                 L.push_back(vertex);
01270             }
01271         }
01272 
01273         // Generate new sub problem.
01274         newBranchRule = new StableSetBranchRule(master_, node, &L);
01275         // Store it.
01276         rules.push(newBranchRule);
01277         //CLean up.
01278         L.clear();
01279 
01280     }
01281   
01282     // Clean up.  
01283     delete row;
01284 
01285     return 0;
01286 
01287 }// generateBranchingRules(..)
01288 
01289 
01290 // -----------------------------------------------------------------------------
01291 // s e t V e r t e x
01292 //
01293 // Set a node to a particular value. This is used when a subproblem is 
01294 // generated in the branching process.
01295 // -----------------------------------------------------------------------------
01296 void StableSetSub::setVertex(int vertex, bool lowerOrUpperBound) {
01297 
01298     int status;
01299     bool newValue;
01300 
01301     // The function 'set' is a pure virual function of ABACUS. It sets
01302     // the variable vertex to its upper bound. set() returns value 1 if a
01303     // contradiction is found and 0 otherwise.
01304     switch(lowerOrUpperBound) {
01305     case 0: 
01306             status = set(vertex, ABA_FSVARSTAT::SetToLowerBound, newValue);
01307             break;
01308 
01309     case 1: status = set(vertex, ABA_FSVARSTAT::SetToUpperBound, newValue);
01310             break;
01311     }
01312     if (status == 1) {
01313         master_->err() << "StableSetSub::setVertex(..): ";
01314         master_->err() << "Setting of variable " << vertex;
01315         master_->err() << " to value " << lowerOrUpperBound;
01316         master_->err() << " failed." << endl;
01317         exit(master_->Fatal);
01318     }
01319 }
01320 
01321 
01322 
01323 // -----------------------------------------------------------------------------
01324 // --------------- M e t h o d s  ( p r i v a t e ) ----------------------------
01325 // -----------------------------------------------------------------------------
01326 
01327 
01328 // -----------------------------------------------------------------------------
01329 // i n c r e a s e T o M a x i m a l C l i q u e
01330 //
01331 // This function increases all 3-cycles found by the odd cycle separation to
01332 // maximal cliques. To do this it first constructs the 3-cycles from the data
01333 // of the odd cycle separator and finds out all adjazent nodes to thsi cycle.
01334 // After this the algorithm adds step by step a node and updates the list of
01335 // adjazent nodes untill no more nodes are left.
01336 // -----------------------------------------------------------------------------
01337 int StableSetSub::increaseToMaximalClique(OddCyclesSeparator *oddCyclesSep) {
01338 
01339     int  i, j, k;       // Loop counter.
01340     int  min;           // Minimal size of an adjazens list.
01341     int  index;         // Index of the adjazens list with minimal size.
01342     int  size = oddCyclesSep->getSizeOfClique();
01343     int  node;          // Store a vertex.
01344     int  begin[3];      // Remember the indizes to begin the search for the
01345                         // adjazent nodes.
01346     bool found;         // Flag to show if something is found or not.
01347     bool newNode;       // The value is true if a new node is found.
01348     bool fixed;         // This is true if all variables could be fixed.
01349     vector<int> clique(3);     // Store the clique.
01350     vector<int> adjazentNodes; // List of adjazent nodes to the vector clique.
01351     ABA_BUFFER<ABA_CONSTRAINT*> constraint(master_, (int)size/3);
01352     CliqueConstraint *cliqueConstr;
01353 
01354 
01355     // Get all nodes of the cycles and construct the 3-cycles out of them.
01356     for (i=0; i<size; i++) {
01357         node = oddCyclesSep->getCliqueElement(i);
01358 
01359         if ((i+1) % 3 != 0) {
01360             clique[i % 3] = node;
01361         }
01362         else {
01363             // The clique stores now a 3-cycle.
01364             clique[2] = node;
01365 
01366             sort(clique.begin(), clique.end());
01367 
01368             // Set the indizes to zero.
01369             for (j=0; j<3; j++) {
01370                 begin[j] = 0;
01371             }
01372 
01373 
01374             // Get node with smallest size of adjazens list.
01375             min   = itsGraph->adjacentListSize(clique[0]);
01376             index = 0;
01377             for (j=1; j<3; j++) {
01378                 if (itsGraph->adjacentListSize(clique[j]) < min) {
01379                     min   = itsGraph->adjacentListSize(clique[j]);
01380                     index = j;
01381                 }
01382             }
01383 
01384             // Get all adjazent nodes to the node of the 3-cycle with the
01385             // smallest number of adjazent nodes. Store this nodes only
01386             // if they are also adjazent to the two other nodes of the 3-cycle.
01387             for (j=0; j<min; j++) {
01388                 // Get node of adjazens list.
01389                 node = itsGraph->adjacentListElement(clique[index], j);
01390 
01391                 // Check if it is not one node of the 3-cycle.
01392                 newNode = true;
01393                 for(k=0; k<3; k++) {
01394                     if ((k != index) && (node == clique[k])) {
01395                         newNode = false;
01396                         break;
01397                     }
01398                 }
01399 
01400                 if (newNode) {
01401                     found = true;
01402                     // Now we know that this node is not a member of the
01403                     // 3-cycle and so we check if it is also a neighbour of
01404                     // the two other nodes of the clique.
01405                     for(k=0; k<3; k++) {
01406                         if(k == index) {
01407                             continue;
01408                         }
01409                         if(!itsGraph->isMemberOfAdjacentList(clique[k],
01410                                                          begin[k], node)) {
01411                             found = false;
01412                             break;
01413                         }
01414                     }
01415                     if(found) {
01416                         adjazentNodes.push_back(node);
01417                     }
01418                 }
01419             }
01420 
01421             // Increase the 3-cycle to a maximal clique
01422             // -> "sequential lifting".
01423             while (!adjazentNodes.empty()) {
01424 
01425                 // Add new node: the last one of the list of adjazent nodes.
01426                 clique.push_back(adjazentNodes.back());
01427                 // Delete last element of this list.
01428                 adjazentNodes.erase(adjazentNodes.end() -1);
01429                 k = 0;
01430                 // Update adjazent list.
01431                 for (j=0; j<adjazentNodes.size(); j++) {
01432                     index = clique.back();
01433                     node  = adjazentNodes[j];
01434                     if (!itsGraph->isMemberOfAdjacentList(index, k, node)) {
01435                         adjazentNodes.erase(adjazentNodes.begin() + j);
01436                         j--;
01437                     }
01438                 }
01439             }// while
01440 
01441             // Sort the new max clique.
01442             sort(clique.begin(), clique.end());
01443 
01444             // New maximal clique found.
01445             cliqueConstr = new CliqueConstraint(master_, &clique, itsGraph);
01446             constraint.push(cliqueConstr);
01447 
01448             clique.clear();
01449             clique.resize(3);
01450         }
01451     }
01452     int num = 0;
01453     int number = -1;
01454     int numPrevious;
01455 
01456     if (constraint.number() != 0) {
01457         // add constraints to pool
01458         numPrevious = stableSetMaster()->cliqueCutPool()->number();
01459         number = addCons(constraint, stableSetMaster()->cliqueCutPool());
01460         number = stableSetMaster()->cliqueCutPool()->number();
01461         number -= numPrevious;
01462         num = number > 0 ? number : num;
01463     }
01464 
01465     return num;
01466 
01467 }// end: int increaseToMaximalClique(..)
01468 
01469 
01470 // -----------------------------------------------------------------------------
01471 // s t a b l e S e t M a s t e r
01472 //
01473 // This function returns a pointer to the corresponding object of the class
01474 // StableSetMaster.
01475 // -----------------------------------------------------------------------------
01476 StableSetMaster *StableSetSub::stableSetMaster() {
01477    return (StableSetMaster *) master_;
01478 }
01479 

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