00001 // $Id: TSP_SubtourCut.hpp,v 1.9 2004/08/10 03:43:15 magh Exp $ 00002 00003 /*------------------------------------------------------------------------- 00004 Author: Matthew Galati (magh@lehigh.edu) 00005 00006 (c) Copyright 2004 Lehigh University. All Rights Reserved. 00007 00008 This software is licensed under the Common Public License. Please see 00009 accompanying file for terms. 00010 ---------------------------------------------------------------------------*/ 00011 00012 #ifndef TSP_SUBTOUR_CUT_INCLUDED 00013 #define TSP_SUBTOUR_CUT_INCLUDED 00014 00015 /*---------------------------------------------------------------------- 00016 TSP_SubtourCut: TSP subtour elimination constraint 00017 00018 (i) ACROSS: sum{e in delta(S)} x_e >= 2 00019 (ii) SIDE : sum{e in E(S)} x_e <= |S| - 1 00020 ---------------------------------------------------------------------- */ 00021 00022 #include "Decomp.h" 00023 #include "DecompCut.h" 00024 #include "UtilMacros.h" 00025 00026 #include <vector> 00027 using namespace std; 00028 00029 /*---------------------------------------------------------------------------*/ 00030 class TSP_SubtourCut : public DecompCut { 00031 public: 00032 enum storageType {VECTOR, BITSET, BOTH}; 00033 enum cutType {ACROSS, SIDE}; 00034 00035 private: 00036 vector<int> m_S; 00037 vector<bool> m_inS; 00038 cutType m_type; 00039 storageType m_storage; 00040 int m_nverts; 00041 00042 public: 00043 //these (pure virutal) methods are inherited from DecompCut 00044 virtual void expandCutToRow(CoinPackedVector * row); 00045 virtual void setBounds(); 00046 00047 //these (virutal) methods are inherited from DecompCut 00048 virtual void print(ostream * os = &cout) const; 00049 virtual bool isSame(const DecompCut * cut) const; 00050 00051 public: 00052 void init(); 00053 void setCutType(); 00054 void create_bitset(); 00055 void create_vector(); 00056 00057 public: 00058 TSP_SubtourCut(const vector<bool> & inS, 00059 const cutType type = ACROSS){ 00060 m_inS = inS; 00061 m_storage = BITSET; 00062 m_nverts = static_cast<int>(m_inS.size()); 00063 m_type = type; 00064 setBounds(); 00065 init(); 00066 }; 00067 00068 TSP_SubtourCut(const vector<bool> & inS, 00069 const vector<int> & S, 00070 const cutType type){ 00071 m_inS = inS; 00072 m_S = S; 00073 m_storage = BOTH; 00074 m_nverts = static_cast<int>(m_inS.size()); 00075 m_type = type; 00076 setBounds(); 00077 init(); 00078 }; 00079 00080 TSP_SubtourCut(const vector<bool> & inS, 00081 const vector<int> & S){ 00082 m_inS = inS; 00083 m_S = S; 00084 m_storage = BOTH; 00085 m_nverts = static_cast<int>(m_inS.size()); 00086 setCutType(); 00087 setBounds(); 00088 init(); 00089 }; 00090 00091 virtual ~TSP_SubtourCut() {} 00092 }; 00093 00094 00095 00096 00097 00098 00099 00100 #endif