#include <StableSetSub.hh>
Public Member Functions | |
StableSetSub (ABA_MASTER *master, Graph *theGraph, Clique *theClique, EdgeProjection *anEdgeProjection, StableSetStatistics *aStatistic) | |
StableSetSub (ABA_MASTER *master, ABA_SUB *father, ABA_BRANCHRULE *branchRule, Graph *theGraph, Clique *theClique, EdgeProjection *anEdgeProjection, StableSetStatistics *aStatistic) | |
virtual | ~StableSetSub () |
virtual bool | feasible () |
virtual ABA_SUB * | generateSon (ABA_BRANCHRULE *rule) |
virtual int | improve (double &primalValue) |
virtual int | separate () |
virtual int | generateBranchRules (ABA_BUFFER< ABA_BRANCHRULE * > &rules) |
void | setVertex (int vertex, bool i) |
Definition at line 48 of file StableSetSub.hh.
|
Constructor of the root node of the enumeration tree.
Definition at line 81 of file StableSetSub.cpp. Referenced by generateSon(). 00083 : 00084 ABA_SUB(master, 10, 0, 50), 00085 itsGraph(theGraph), 00086 maxCliques(theClique), 00087 theEdgeProjection(anEdgeProjection), 00088 theStatistics(aStatistics), 00089 violatedEdge(false) 00090 { 00091 }
|
|
Constructor for a son of an existing node.
Definition at line 102 of file StableSetSub.cpp. 00105 : 00106 ABA_SUB(master, father, branchRule), 00107 itsGraph(theGraph), 00108 maxCliques(theClique), 00109 theEdgeProjection(anEdgeProjection), 00110 theStatistics(aStatistics) 00111 { 00112 }
|
|
Destructor. Definition at line 118 of file StableSetSub.cpp.
|
|
Feasibility check of a LP solution.
Definition at line 135 of file StableSetSub.cpp. References Graph::adjacentListSize(), Graph::getAdjacentList(), Graph::getFileName(), Graph::isMemberOfAdjacentList(), and Graph::numberOfNodes(). 00135 { 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()
|
|
Generate all sons in this node of the tree.
Definition at line 959 of file StableSetSub.cpp. References Graph::numberOfNodes(), StableSetStatistics::setAlphaRoot(), and StableSetStatistics::setDualBound(). 00959 { 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(..)
|
|
It generates a problem specific son of a sub problem.
Definition at line 317 of file StableSetSub.cpp. References StableSetSub(). 00317 { 00318 return new StableSetSub(master_, this, rule, itsGraph, maxCliques, 00319 theEdgeProjection, 00320 theStatistics); 00321 }
|
|
Primal heuristic.
Definition at line 338 of file StableSetSub.cpp. References LowerBoundHeuristic::computeSolution(), and Graph::weighted(). 00338 { 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(..)
|
|
Separation of inequalities.
Definition at line 393 of file StableSetSub.cpp. References StableSetMaster::cliqueCutPool(), StableSetStatistics::cliqueHeuristicsCut(), StableSetMaster::cycleCutPool(), Graph::getFileName(), OddCyclesSeparator::getSizeOfClique(), StableSetStatistics::liftedOddCyclesCut(), Graph::numberOfNodes(), StableSetStatistics::oddCyclesCut(), StableSetStatistics::poolSeparationCut(), OddCyclesSeparator::separate(), and CliqueHeuristicsSeparator::separate(). 00393 { 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()
|
|
Set a vertex to a particular value.
Definition at line 1296 of file StableSetSub.cpp. 01296 { 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 }
|