Dip-All  0.91.0
TSP_SubtourCut.h
Go to the documentation of this file.
1 // $Id: TSP_SubtourCut.hpp,v 1.9 2004/08/10 03:43:15 magh Exp $
2 
3 /*-------------------------------------------------------------------------
4  Author: Matthew Galati (magh@lehigh.edu)
5 
6  (c) Copyright 2004 Lehigh University. All Rights Reserved.
7 
8  This software is licensed under the Common Public License. Please see
9  accompanying file for terms.
10  ---------------------------------------------------------------------------*/
11 
12 #ifndef TSP_SUBTOUR_CUT_INCLUDED
13 #define TSP_SUBTOUR_CUT_INCLUDED
14 
15 /*----------------------------------------------------------------------
16  TSP_SubtourCut: TSP subtour elimination constraint
17 
18  (i) ACROSS: sum{e in delta(S)} x_e >= 2
19  (ii) SIDE : sum{e in E(S)} x_e <= |S| - 1
20  ---------------------------------------------------------------------- */
21 
22 #include "Decomp.h"
23 #include "DecompCut.h"
24 #include "UtilMacros.h"
25 
26 #include <vector>
27 using namespace std;
28 
29 /*---------------------------------------------------------------------------*/
30 class TSP_SubtourCut : public DecompCut {
31 public:
32  enum storageType {VECTOR, BITSET, BOTH};
33  enum cutType {ACROSS, SIDE};
34 
35 private:
36  vector<int> m_S;
37  vector<bool> m_inS;
40  int m_nverts;
41 
42 public:
43  //these (pure virutal) methods are inherited from DecompCut
44  virtual void expandCutToRow(CoinPackedVector * row);
45  virtual void setBounds();
46 
47  //these (virutal) methods are inherited from DecompCut
48  virtual void print(ostream * os = &cout) const;
49  virtual bool isSame(const DecompCut * cut) const;
50 
51 public:
52  void init();
53  void setCutType();
54  void create_bitset();
55  void create_vector();
56 
57 public:
58  TSP_SubtourCut(const vector<bool> & inS,
59  const cutType type = ACROSS){
60  m_inS = inS;
61  m_storage = BITSET;
62  m_nverts = static_cast<int>(m_inS.size());
63  m_type = type;
64  setBounds();
65  init();
66  };
67 
68  TSP_SubtourCut(const vector<bool> & inS,
69  const vector<int> & S,
70  const cutType type){
71  m_inS = inS;
72  m_S = S;
73  m_storage = BOTH;
74  m_nverts = static_cast<int>(m_inS.size());
75  m_type = type;
76  setBounds();
77  init();
78  };
79 
80  TSP_SubtourCut(const vector<bool> & inS,
81  const vector<int> & S){
82  m_inS = inS;
83  m_S = S;
84  m_storage = BOTH;
85  m_nverts = static_cast<int>(m_inS.size());
86  setCutType();
87  setBounds();
88  init();
89  };
90 
91  virtual ~TSP_SubtourCut() {}
92 };
93 
94 
95 
96 
97 
98 
99 
100 #endif
storageType m_storage
TSP_SubtourCut(const vector< bool > &inS, const cutType type=ACROSS)
virtual ~TSP_SubtourCut()
Sparse Vector.
TSP_SubtourCut(const vector< bool > &inS, const vector< int > &S)
vector< int > m_S
vector< bool > m_inS
TSP_SubtourCut(const vector< bool > &inS, const vector< int > &S, const cutType type)