/home/coin/SVN-release/Bcp-1.2.1/Bcp/examples/MaxCut/include/MC_cut.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
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; // length of the cycle
00049    int  pos_edges; // number of edges with positive coefficient
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

Generated on Thu Jan 15 03:00:58 2009 for coin-Bcp by  doxygen 1.4.7