00001
00002
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
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 }