00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00015
00016
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
00048
00049
00050 struct NodesAndDegree {
00051 int inode;
00052 double degree;
00053 };
00054
00055
00056
00057
00058
00059 bool operator<(const NodesAndDegree &a, const NodesAndDegree &b) {
00060 return a.degree > b.degree;
00061 }
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
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
00096
00097
00098
00099
00100
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
00117
00118 StableSetSub::~StableSetSub() {
00119 }
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135 bool StableSetSub::feasible() {
00136
00137 bool feasible;
00138
00139
00140
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
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
00169
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
00184 vertex = adjacentList[j];
00185 clique[0] = i;
00186 clique[1] = vertex;
00187 adjacentList.erase(adjacentList.begin() + j);
00188
00189
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
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 }
00211
00212
00213
00214 sort(clique.begin(), clique.end());
00215 cliqueConstr = new CliqueConstraint(master_, &clique, itsGraph);
00216 constraint.push(cliqueConstr);
00217 newCuts++;
00218
00219
00220 clique.clear();
00221 clique.resize(2);
00222 adjacentList = (*itsGraph->getAdjacentList(i));
00223
00224 if (newCuts == MAX_NUM) {
00225 break;
00226 }
00227 }
00228 }
00229 if (newCuts == MAX_NUM) {
00230 break;
00231 }
00232 }
00233
00234 fout.close();
00235
00236 if (newCuts) {
00237
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
00246 master_->out() << "\tEdge inequalities:\t" << num << endl;
00247
00248
00249 theStatistics->edgeInequalitiesCut(num);
00250
00251 return false;
00252 }
00253 else {
00254 master_->out() << "\tAll edge inequalities are valid" << endl;
00255 }
00256 }
00257
00258
00259
00260
00261
00262 feasible = integerFeasible();
00263
00264
00265 if (feasible) {
00266
00267
00268
00269
00270 if (lp_->value() >= (master_->primalBound() + .5)) {
00271
00272 int i;
00273 int numberOfNodes = itsGraph->numberOfNodes();
00274 double OneMinusEps = 1.0 - master_->machineEps();
00275 vector<int> *bestSolution = stableSetMaster()->getSolution();
00276 bestSolution->clear();
00277
00278 for (i=0; i<numberOfNodes; i++) {
00279
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
00298
00299 master_->primalBound((int)lp_->value());
00300 theStatistics->solutionFound(0);
00301 }
00302 }
00303
00304 return feasible;
00305
00306 }
00307
00308
00309
00310
00311
00312
00313
00314
00315
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
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338 int StableSetSub::improve(double &primalValue) {
00339
00340 int status = 0;
00341 double value;
00342
00343 LowerBoundHeuristic *roundingHeuristic;
00344 roundingHeuristic = new LowerBoundHeuristic(master_, itsGraph,
00345 theStatistics),
00346
00347 status = roundingHeuristic->computeSolution(value, xVal_, level());
00348
00349
00350 delete roundingHeuristic;
00351
00352 if (!itsGraph->weighted()) {
00353
00354 ImprovementHeuristic *improveHeuristic;
00355 improveHeuristic = new ImprovementHeuristic(master_, itsGraph,
00356 theStatistics);
00357
00358
00359 status = (improveHeuristic->improve(value) || status);
00360
00361
00362 delete improveHeuristic;
00363 }
00364
00365 if (status) {
00366 primalValue = value;
00367 }
00368
00369 return status;
00370 }
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393 int StableSetSub::separate() {
00394
00395 int i, j, k;
00396 int numberOfGeneratedCuts = 0;
00397 int newCuts = 0;
00398 int num;
00399 int number = -1;
00400 int numPrevious;
00401 int error;
00402 static int largeCutCnt = 0;
00403
00404
00405 static int MIN_NUMBER_OF_CUTS = (int) itsGraph->numberOfNodes() / 10;
00406 static double EPS = 0.000001;
00407
00408
00409
00410 StableSetLPSolution *currentLPSolution;
00411 currentLPSolution = new StableSetLPSolution(master_, this,
00412 itsGraph->numberOfNodes(),
00413 xVal_);
00414
00415
00416
00417
00418
00419
00420 if (violatedEdge) {
00421 violatedEdge = false;
00422
00423
00424
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
00433 CliqueHeuristicsSeparator *cliqueHeuristicsSep;
00434 cliqueHeuristicsSep = new CliqueHeuristicsSeparator(
00435 currentLPSolution,
00436 itsGraph);
00437
00438 cliqueHeuristicsSep->separate();
00439
00440
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
00451 master_->out() << "\tCliques:\t\t" << num << endl;
00452
00453
00454 theStatistics->cliqueHeuristicsCut(num);
00455
00456
00457 delete cliqueHeuristicsSep;
00458 delete currentLPSolution;
00459 }
00460
00461
00462
00463
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
00474
00475
00476
00477 theStatistics->poolSeparationCut(number);
00478 }
00479
00480
00481 return newCuts;
00482 }
00483
00484
00485
00486
00487
00488
00489 if (stableSetMaster()->m_oddCycleSeparation) {
00490
00491 ofstream fout(itsGraph->getFileName(), ios::app);
00492 fout << "\n* Odd Cycles:" << endl;
00493
00494
00495 OddCyclesSeparator *oddCyclesSep;
00496 oddCyclesSep = new OddCyclesSeparator(master_, currentLPSolution,
00497 itsGraph, false);
00498
00499 oddCyclesSep->separate();
00500
00501 fout.close();
00502
00503
00504
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
00515 master_->out() << "\tOdd cycles:\t\t" << num << endl;
00516
00517
00518 theStatistics->oddCyclesCut(num);
00519
00520
00521
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
00533 master_->out() << "\tLifted odd cycles:\t" << num << endl;
00534
00535
00536 theStatistics->liftedOddCyclesCut(num);
00537 }
00538
00539
00540 delete oddCyclesSep;
00541 }
00542
00543
00544
00545
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
00554 CliqueHeuristicsSeparator *cliqueHeuristicsSep;
00555 cliqueHeuristicsSep = new CliqueHeuristicsSeparator(
00556 currentLPSolution,
00557 itsGraph);
00558
00559 cliqueHeuristicsSep->separate();
00560
00561
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
00572 master_->out() << "\tCliques:\t\t" << num << endl;
00573
00574
00575 theStatistics->cliqueHeuristicsCut(num);
00576
00577
00578 delete cliqueHeuristicsSep;
00579 }
00580
00581 if (newCuts >= MIN_NUMBER_OF_CUTS) {
00582
00583 delete currentLPSolution;
00584
00585 return numberOfGeneratedCuts;
00586 }
00587
00588
00589
00590
00591
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
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
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
00624 RankConstraint *rankConstr;
00625
00626 ABA_BUFFER< ABA_CONSTRAINT* > constraint(master_,
00627 inequalities->size());
00628
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 }
00636
00637
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 }
00646
00647
00648 master_->out() << "\tEdge projection:\t" << num << endl;
00649
00650
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 }
00662 }
00663 if (newCuts >= MIN_NUMBER_OF_CUTS) {
00664
00665 delete currentLPSolution;
00666
00667 return numberOfGeneratedCuts;
00668 }
00669
00670
00671
00672
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
00686 theStatistics->poolSeparationCut(numberOfGeneratedCuts);
00687 }
00688 if (newCuts > 0) {
00689
00690 delete currentLPSolution;
00691
00692 return numberOfGeneratedCuts;
00693 }
00694
00695
00696
00697
00698 if (stableSetMaster()->m_ModKCutsSeparation) {
00699
00700 static int MAX_GEN_NR = 100000;
00701
00702
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
00708
00709 for (int i=0; i<keepInPool->size();i++) {
00710 (*keepInPool)[i] = false;
00711 }
00712
00713 StableSetModKSeparator *stableSetModKSeparator;
00714 stableSetModKSeparator = new StableSetModKSeparator(currentLPSolution,
00715 itsGraph);
00716
00717
00718 stableSetModKSeparator->separate();
00719
00720
00721
00722
00723
00724 numPrevious = stableSetMaster()->generalCutPool()->number();
00725 number = addCons(stableSetModKSeparator->cutBuffer(),
00726 stableSetMaster()->generalCutPool());
00727 number = stableSetMaster()->generalCutPool()->number();
00728 number -= numPrevious;
00729 num = number >= 0 ? number : num;
00730 numberOfGeneratedCuts += num;
00731 newCuts += num;
00732
00733
00734 theStatistics->modKCut(num);
00735
00736
00737 delete rank;
00738 delete keepInPool;
00739 delete stableSetModKSeparator;
00740 }
00741 if (newCuts != 0) {
00742
00743 delete currentLPSolution;
00744
00745 return numberOfGeneratedCuts;
00746 }
00747
00748
00749
00750
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
00759 LocalCutSeparator *localCuts;
00760 localCuts = new LocalCutSeparator(master_, currentLPSolution, itsGraph);
00761
00762
00763 localCuts->separate();
00764
00765
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
00776 master_->out() << "\tLocal cut:\t" << num << endl;
00777
00778
00779 theStatistics->localCutCut(1);
00780
00781
00782 delete localCuts;
00783 }
00784 if (newCuts != 0) {
00785
00786 delete currentLPSolution;
00787
00788 return numberOfGeneratedCuts;
00789 }
00790
00791
00792
00793
00794
00795 if (stableSetMaster()->m_maxCliqueSeparation) {
00796
00797
00798 vector<int*> cliques;
00799
00800
00801 num = maxCliques->checkMaxCliques(&cliques, xVal_);
00802
00803
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
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
00821 cliqueConstr = new CliqueConstraint(master_, &nodesOfClique,
00822 itsGraph);
00823 constraint.push(cliqueConstr);
00824
00825
00826 nodesOfClique.clear();
00827 }
00828
00829
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
00841 master_->out() << "\tMaximal cliques from memory:\t" << num << endl;
00842
00843
00844 theStatistics->maxCliquesMemoryCut(num);
00845
00846 }
00847 }
00848
00849
00850
00851
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
00862 MaxCliquesSeparator *maxCliquesSep;
00863 maxCliquesSep = new MaxCliquesSeparator(master_, currentLPSolution,
00864 itsGraph, maxCliques);
00865
00866 maxCliquesSep->separate();
00867
00868
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
00877 master_->out() << "\tExact cliques:\t" << num << endl;
00878
00879
00880 theStatistics->exactCliquesCut(num);
00881
00882
00883 delete maxCliquesSep;
00884 }
00885
00886
00887
00888
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
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
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
00925 RankConstraint *rankConstr;
00926 rankConstr = new RankConstraint(master_, (*inequalities)[0],
00927 (*rhs)[0], true, itsGraph);
00928 constraint.push(rankConstr);
00929
00930
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
00940 theStatistics->largeCutCut(1);
00941 }
00942 }
00943
00944
00945 delete currentLPSolution;
00946
00947
00948 return numberOfGeneratedCuts;
00949
00950 }
00951
00952
00953
00954
00955
00956
00957
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
00975 theStatistics->setDualBound(lp()->value());
00976
00977 theStatistics->setAlphaRoot((int) master_->primalBound());
00978
00979 master_->tailOffNLp(2);
00980 master_->tailOffPercent(0.01);
00981 }
00982
00983
00984
00985
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
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 }
01032
01033
01034 sort(storeNodes.begin(), storeNodes.end());
01035
01036
01037
01038
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
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
01068 poolPointer = stableSetMaster()->cliqueCutPool();
01069
01070 nConstraints = poolPointer->number();
01071
01072 for (i=0; i<nConstraints; i++){
01073
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
01083 itsWeight = 0;
01084 numberOfVariablesInConstr = constrPointer->genRow(actVar(), *row);
01085
01086
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
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
01124 poolPointer = stableSetMaster()->rankCutPool();
01125
01126 nConstraints = poolPointer->number();
01127
01128 for (i=0; i<nConstraints; i++){
01129
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
01139 itsWeight = 0;
01140 numberOfVariablesInConstr = constrPointer->genRow(actVar(), *row);
01141
01142
01143
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
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
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
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
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 }
01232
01233
01234 if (chiBar > alpha) {
01235 cout << "Branching was wrong!" << endl;
01236 exit(master_->Fatal);
01237 }
01238
01239
01240
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
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
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
01274 newBranchRule = new StableSetBranchRule(master_, node, &L);
01275
01276 rules.push(newBranchRule);
01277
01278 L.clear();
01279
01280 }
01281
01282
01283 delete row;
01284
01285 return 0;
01286
01287 }
01288
01289
01290
01291
01292
01293
01294
01295
01296 void StableSetSub::setVertex(int vertex, bool lowerOrUpperBound) {
01297
01298 int status;
01299 bool newValue;
01300
01301
01302
01303
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
01325
01326
01327
01328
01329
01330
01331
01332
01333
01334
01335
01336
01337 int StableSetSub::increaseToMaximalClique(OddCyclesSeparator *oddCyclesSep) {
01338
01339 int i, j, k;
01340 int min;
01341 int index;
01342 int size = oddCyclesSep->getSizeOfClique();
01343 int node;
01344 int begin[3];
01345
01346 bool found;
01347 bool newNode;
01348 bool fixed;
01349 vector<int> clique(3);
01350 vector<int> adjazentNodes;
01351 ABA_BUFFER<ABA_CONSTRAINT*> constraint(master_, (int)size/3);
01352 CliqueConstraint *cliqueConstr;
01353
01354
01355
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
01364 clique[2] = node;
01365
01366 sort(clique.begin(), clique.end());
01367
01368
01369 for (j=0; j<3; j++) {
01370 begin[j] = 0;
01371 }
01372
01373
01374
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
01385
01386
01387 for (j=0; j<min; j++) {
01388
01389 node = itsGraph->adjacentListElement(clique[index], j);
01390
01391
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
01403
01404
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
01422
01423 while (!adjazentNodes.empty()) {
01424
01425
01426 clique.push_back(adjazentNodes.back());
01427
01428 adjazentNodes.erase(adjazentNodes.end() -1);
01429 k = 0;
01430
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 }
01440
01441
01442 sort(clique.begin(), clique.end());
01443
01444
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
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 }
01468
01469
01470
01471
01472
01473
01474
01475
01476 StableSetMaster *StableSetSub::stableSetMaster() {
01477 return (StableSetMaster *) master_;
01478 }
01479