00001
00002
00003 #ifndef _MC_CUT_H
00004 #define _MC_CUT_H
00005
00006 #include <algorithm>
00007
00008 #include "CoinHelperFunctions.hpp"
00009
00010 #include "BCP_math.hpp"
00011 #include "BCP_mempool.hpp"
00012 #include "BCP_cut.hpp"
00013
00014 class BCP_buffer;
00015 class BCP_row;
00016 class MC_problem;
00017 class MC_solution;
00018
00019
00020
00021 enum MC_cut_t {
00022 MC_cut_t__cycle,
00023 MC_cut_t__explicit_dense
00024 };
00025
00026 enum MC_EdgeOrdering {
00027 MC_MstEdgeOrderingPreferZero,
00028 MC_MstEdgeOrderingPreferOne,
00029 MC_MstEdgeOrderingPreferExtreme
00030 };
00031
00032
00033
00034 class MC_cycle_cut : public BCP_cut_algo {
00035 private:
00036 MC_cycle_cut(const MC_cycle_cut&);
00037 MC_cycle_cut& operator=(const MC_cycle_cut&);
00038 private:
00039 static BCP_MemPool memPool;
00040 public:
00041 static inline void * operator new(size_t size) {
00042 return memPool.alloc(size);
00043 }
00044 static inline void operator delete(void *p, size_t size) {
00045 memPool.free(p, size);
00046 }
00047 public:
00048 int cycle_len;
00049 int pos_edges;
00050 int* edges;
00051 public:
00052 MC_cycle_cut(const int* ei, const int pos, const int len) :
00053 BCP_cut_algo(-BCP_DBL_MAX, pos-1.0),
00054 cycle_len(len), pos_edges(pos), edges(0)
00055 {
00056 if (len > 0) {
00057 edges = new int[len];
00058 CoinDisjointCopyN(ei, len, edges);
00059 }
00060 }
00061 MC_cycle_cut(BCP_buffer& buf);
00062 ~MC_cycle_cut() {
00063 delete[] edges;
00064 }
00065
00066 void pack(BCP_buffer& buf) const;
00067 };
00068
00069
00070
00071 class MC_explicit_dense_cut : public BCP_cut_algo {
00072 private:
00073 MC_explicit_dense_cut(const MC_explicit_dense_cut&);
00074 MC_explicit_dense_cut& operator=(const MC_explicit_dense_cut&);
00075 private:
00076 static BCP_MemPool memPool;
00077 public:
00078 static inline void * operator new(size_t size) {
00079 return memPool.alloc(size);
00080 }
00081 static inline void operator delete(void *p, size_t size) {
00082 memPool.free(p, size);
00083 }
00084 public:
00085 double rhs;
00086 double * coeffs;
00087 int varnum;
00088 public:
00089 MC_explicit_dense_cut(const double ub, const int num,
00090 const double * elements) :
00091 BCP_cut_algo(-BCP_DBL_MAX, ub),
00092 rhs(ub), coeffs(new double[num]), varnum(num)
00093 {
00094 CoinDisjointCopyN(elements, num, coeffs);
00095 }
00096 MC_explicit_dense_cut(BCP_buffer& buf);
00097 ~MC_explicit_dense_cut() {
00098 delete[] coeffs;
00099 }
00100
00101 void pack(BCP_buffer& buf) const;
00102 };
00103
00104
00105
00106 inline bool
00107 MC_cycle_cut_less(const BCP_cut* bc0, const BCP_cut* bc1) {
00108 const MC_cycle_cut* c0 = dynamic_cast<const MC_cycle_cut*>(bc0);
00109 const MC_cycle_cut* c1 = dynamic_cast<const MC_cycle_cut*>(bc1);
00110 if (c0->cycle_len < c1->cycle_len)
00111 return true;
00112 if (c1->cycle_len < c0->cycle_len)
00113 return false;
00114 if (c0->pos_edges < c1->pos_edges)
00115 return true;
00116 if (c1->pos_edges < c0->pos_edges)
00117 return false;
00118 return memcmp(c0->edges, c1->edges, c0->cycle_len * sizeof(int)) < 0;
00119 }
00120
00121 inline bool
00122 MC_cycle_cut_equal(const BCP_cut* bc0, const BCP_cut* bc1) {
00123 const MC_cycle_cut* c0 = dynamic_cast<const MC_cycle_cut*>(bc0);
00124 const MC_cycle_cut* c1 = dynamic_cast<const MC_cycle_cut*>(bc1);
00125 return (c0->cycle_len == c1->cycle_len &&
00126 c0->pos_edges == c1->pos_edges &&
00127 memcmp(c0->edges, c1->edges, c0->cycle_len * sizeof(int)) == 0);
00128 }
00129
00130
00131
00132 MC_solution*
00133 MC_mst_heur(const MC_problem & mc, const double * x, const double * w,
00134 const double alpha, const double beta,
00135 const MC_EdgeOrdering edge_ordering,
00136 const int heurswitchround,
00137 const bool do_edge_switch_heur, const int struct_switch_heur);
00138
00139
00140
00141 MC_solution*
00142 MC_mst_cutgen(const MC_problem& mc, const double* x, const double* w,
00143 const double alpha, const double beta,
00144 const MC_EdgeOrdering edge_ordering,
00145 const int heurswitchround,
00146 const bool do_edge_switch_heur, const int struct_switch_heur,
00147 const double minviol, const int maxnewcuts,
00148 BCP_vec<BCP_cut*>& new_cuts, BCP_vec<BCP_row*>& new_rows);
00149
00150
00151
00152 void
00153 MC_kruskal(const MC_problem& mc, const int * edgeorder, const double* x,
00154 int * nodesign, int * edges_in_tree);
00155
00156
00157
00158 void
00159 MC_kruskal(const MC_problem& mc, const int * edgeorder, const double* x,
00160 int * nodesign, int * parentnode, int * parentedge);
00161
00162
00163
00164 void
00165 MC_generate_shortest_path_cycles(const MC_problem& mc, const double* x,
00166 const bool generate_all_cuts,
00167 const double minviol,
00168 BCP_vec<BCP_cut*>& new_cuts,
00169 BCP_vec<BCP_row*>& new_rows);
00170
00171
00172
00173 void
00174 MC_test_ising_four_cycles(const int n, const int* cycles,
00175 const double* x, const double minviol,
00176 BCP_vec<BCP_cut*>& cuts, BCP_vec<BCP_row*>& rows);
00177
00178 void
00179 MC_test_ising_triangles(const int n, const int* triangles,
00180 const double* x, const double minviol,
00181 BCP_vec<BCP_cut*>& cuts, BCP_vec<BCP_row*>& rows);
00182
00183 #endif