/home/coin/SVN-release/OS-2.4.0/Bcp/examples/MaxCut/CG/MC_ising_cycles.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 
00004 #include "CoinSort.hpp"
00005 
00006 #include "BCP_matrix.hpp"
00007 
00008 #include "MC_cut.hpp"
00009 
00010 static inline void
00011 MC_test_ising_four_cycle(const double sum, const double minviol,
00012                          const int c0, const int c1, const int c2,const int c3,
00013                          BCP_vec<BCP_cut*>& cuts, BCP_vec<BCP_row*>& rows)
00014 {
00015   // sort c0, c1, c2
00016   int cut[4];
00017   cut[3] = c3;
00018   if (c0 < c1) {
00019     if (c0 < c2) {
00020       cut[0] = c0;
00021       if (c1 < c2) {
00022         cut[1] = c1;
00023         cut[2] = c2;
00024       } else {
00025         cut[1] = c2;
00026         cut[2] = c1;
00027       }
00028     } else {
00029       cut[0] = c2;
00030       cut[1] = c0;
00031       cut[2] = c1;
00032     }
00033   } else {
00034     if (c1 < c2) {
00035       cut[0] = c1;
00036       if (c0 < c2) {
00037         cut[1] = c0;
00038         cut[2] = c2;
00039       } else {
00040         cut[1] = c2;
00041         cut[2] = c0;
00042       }
00043     } else {
00044       cut[0] = c2;
00045       cut[1] = c1;
00046       cut[2] = c0;
00047     }
00048   }
00049       
00050   if (sum > 2 + minviol) {
00051     cuts.push_back(new MC_cycle_cut(cut, 3, 4));
00052     double row[4] = {1.0, 1.0, 1.0, -1.0};
00053     CoinSort_2(cut, cut+4, row);
00054     rows.push_back(new BCP_row(cut, cut+4, row, row+4, -BCP_DBL_MAX, 2));
00055   } else if (sum < - minviol) {
00056     std::rotate(cut, cut+3, cut+4);
00057     cuts.push_back(new MC_cycle_cut(cut, 1, 4));
00058     double row[4] = {1.0, -1.0, -1.0, -1.0};
00059     CoinSort_2(cut, cut+4, row);
00060     rows.push_back(new BCP_row(cut, cut+4, row, row+4, -BCP_DBL_MAX, 0));
00061   }
00062 }
00063 
00064 void
00065 MC_test_ising_four_cycles(const int n, const int* cycles,
00066                           const double* x, const double minviol,
00067                           BCP_vec<BCP_cut*>& cuts, BCP_vec<BCP_row*>& rows)
00068 {
00069   const int* cycle = cycles;
00070   for (int i = 0; i < n; ++i) {
00071     const int c0 = cycle[0];
00072     const int c1 = cycle[1];
00073     const int c2 = cycle[2];
00074     const int c3 = cycle[3];
00075     const double x0 = x[c0];
00076     const double x1 = x[c1];
00077     const double x2 = x[c2];
00078     const double x3 = x[c3];
00079 
00080     MC_test_ising_four_cycle(x0+x1+x2-x3, minviol, c0, c1, c2, c3, cuts, rows);
00081     MC_test_ising_four_cycle(x1+x2+x3-x0, minviol, c1, c2, c3, c0, cuts, rows);
00082     MC_test_ising_four_cycle(x2+x3+x0-x1, minviol, c2, c3, c0, c1, cuts, rows);
00083     MC_test_ising_four_cycle(x3+x0+x1-x2, minviol, c3, c0, c1, c2, cuts, rows);
00084       
00085     cycle += 4;
00086   }
00087 }
00088 
00089 //#############################################################################
00090 
00091 void
00092 MC_test_ising_triangles(const int n, const int* cycles,
00093                         const double* x, const double minviol,
00094                         BCP_vec<BCP_cut*>& cuts, BCP_vec<BCP_row*>& rows)
00095 {
00096   const int* cycle = cycles;
00097   int cut[3];
00098   for (int i = 0; i < n; ++i) {
00099     const int c0 = cycle[0];
00100     const int c1 = cycle[1];
00101     const int c2 = cycle[2];
00102     const double x0 = x[c0];
00103     const double x1 = x[c1];
00104     const double x2 = x[c2];
00105 
00106     if (x0+x1+x2 > 2 + minviol) {
00107       cuts.push_back(new MC_cycle_cut(cycle, 3, 3));
00108       double row[3] = {1.0, 1.0, 1.0};
00109       rows.push_back(new BCP_row(cycle, cycle+3, row, row+3, -BCP_DBL_MAX, 2));
00110     }
00111     if (+ x0 - x1 - x2 > minviol) {
00112       cuts.push_back(new MC_cycle_cut(cycle, 1, 3));
00113       double row[3] = {1.0, -1.0, -1.0};
00114       rows.push_back(new BCP_row(cycle, cycle+3, row, row+3, -BCP_DBL_MAX, 0));
00115     }
00116     if (- x0 + x1 - x2 > minviol) {
00117       cut[0] = c1;
00118       cut[1] = c0;
00119       cut[2] = c2;
00120       cuts.push_back(new MC_cycle_cut(cut, 1, 3));
00121       double row[3] = {-1.0, 1.0, -1.0};
00122       rows.push_back(new BCP_row(cycle, cycle+3, row, row+3, -BCP_DBL_MAX, 0));
00123     }
00124     if (- x0 - x1 + x2 > minviol) {
00125       cut[0] = c2;
00126       cut[1] = c0;
00127       cut[2] = c1;
00128       cuts.push_back(new MC_cycle_cut(cut, 1, 3));
00129       double row[3] = {-1.0, -1.0, 1.0};
00130       rows.push_back(new BCP_row(cycle, cycle+3, row, row+3, -BCP_DBL_MAX, 0));
00131     }
00132 
00133     cycle += 3;
00134   }
00135 }

Generated on Thu Sep 22 03:05:50 2011 by  doxygen 1.4.7