Dip-All  0.91.0
TSP_Concorde.h
Go to the documentation of this file.
1 //===========================================================================//
2 // This file is part of the Decomp Solver Framework. //
3 // //
4 // Decomp is distributed under the Common Public License as part of the //
5 // COIN-OR repository (http://www.coin-or.org). //
6 // //
7 // Author: Matthew Galati, Lehigh University //
8 // //
9 // Copyright (C) 2002-2015, Lehigh University, Matthew Galati, and Ted Ralphs//
10 // All Rights Reserved. //
11 //===========================================================================//
12 
13 #ifndef TSP_CONCORDE_INCLUDED
14 #define TSP_CONCORDE_INCLUDED
15 
16 //---
17 //--- Interface class to Concorde (TSP solver).
18 //---
19 
20 // --------------------------------------------------------------------- //
21 extern "C"{
22 #include "TSP_ConcordeI.h"
23 }
24 
25 // --------------------------------------------------------------------- //
26 #include <vector>
27 using namespace std;
28 
29 // --------------------------------------------------------------------- //
30 #include "UtilMacros.h"
31 
32 // --------------------------------------------------------------------- //
34 public:
35  vector<int> S;
36  vector<bool> inS;
37 public:
38  void print(){
39  cout << "ConcordeSubtour: ";
40  for(int i = 0; i < static_cast<int>(inS.size()); i++){
41  if(inS[i]){
42  cout << i << " ";
43  }
44  }
45  cout << endl;
46  }
47  ConcordeSubtourCut(const int nVerts) :
48  S(),
49  inS(nVerts, false) {}
50 
52 };
53 
54 // --------------------------------------------------------------------- //
55 class TSP_Concorde {
56 public:
57  //define concorde subgraph
58  int m_nVerts;
59  vector<int> m_edgeList;
60  vector<double> m_edgeValue;
61 
62 public:
64  void clearSubGraph(){
65  m_nVerts = 0;
66  m_edgeList.clear();
67  m_edgeValue.clear();
68  }
69 
70  void buildSubGraph(const int nVerts,
71  const int nEdges,
72  const double * edgeWeight,
73  const double tol = 1.0e-6){
74 
75  int i;
76  clearSubGraph();
77  m_nVerts = nVerts;
78  m_edgeList.reserve(2*nEdges);
79  m_edgeValue.reserve(nEdges);
80  for(i = 0; i < nEdges; i++){
81  if(edgeWeight[i] <= tol)
82  continue;
83  pair<int,int> uv = UtilBothEndsU(i);
84  m_edgeValue.push_back(edgeWeight[i]);
85  m_edgeList.push_back(uv.first);
86  m_edgeList.push_back(uv.second);
87  }
88  }
89 
90  int generateCutsSubtour(vector<ConcordeSubtourCut> & subtourCuts){
91  CCtsp_lpcut_in * tsp_cuts = NULL;
92  CCtsp_lpcut_in * tsp_cut = NULL;
93  CCtsp_lpcut_in * tsp_cut_next = NULL;
94 
95  int i, c, tmp;
96  int n_subtour = 0;
97  int n_edgeList = static_cast<int>(m_edgeValue.size());
98  int retCode = CCtsp_exact_subtours(&tsp_cuts,
99  &n_subtour,
100  m_nVerts,
101  n_edgeList,
102  &m_edgeList[0],
103  &m_edgeValue[0]);
104  assert(!retCode);
105 
106  //cout << "CONCORDE found n_subtours : " << n_subtour << endl;
107 
108  tsp_cut = tsp_cuts;
109  for(c = 0; c < n_subtour; c++){
110  ConcordeSubtourCut subtourCut(m_nVerts);
111  assert(tsp_cut);
112  CC_FOREACH_NODE_IN_CLIQUE(i, tsp_cut->cliques[0], tmp){
113  subtourCut.S.push_back(i);
114  subtourCut.inS[i] = true;
115  }
116  //subtourCut.print();
117  subtourCuts.push_back(subtourCut);
118  tsp_cut = tsp_cut->next;
119  }
120 
121  for (tsp_cut = tsp_cuts; tsp_cut; tsp_cut = tsp_cut_next){
122  tsp_cut_next = tsp_cut->next;
123  CCtsp_free_lpcut_in(tsp_cut);
124  free(tsp_cut); //need UtilFree? for C style alloc/free?
125  }
126  tsp_cuts = NULL;
127  return static_cast<int>(subtourCuts.size());
128  }
129 
130 public:
132  m_nVerts (0),
133  m_edgeList (),
134  m_edgeValue()
135  {}
137  {}
138 };
139 
140 #endif
void clearSubGraph()
Definition: TSP_Concorde.h:64
void buildSubGraph(const int nVerts, const int nEdges, const double *edgeWeight, const double tol=1.0e-6)
Definition: TSP_Concorde.h:70
pair< int, int > UtilBothEndsU(const int index)
#define CC_FOREACH_NODE_IN_CLIQUE(i, c, tmp)
Definition: TSP_ConcordeI.h:47
ConcordeSubtourCut(const int nVerts)
Definition: TSP_Concorde.h:47
vector< double > m_edgeValue
Definition: TSP_Concorde.h:60
vector< int > S
Definition: TSP_Concorde.h:35
int generateCutsSubtour(vector< ConcordeSubtourCut > &subtourCuts)
Definition: TSP_Concorde.h:90
CCtsp_lpclique * cliques
Definition: TSP_ConcordeI.h:40
vector< bool > inS
Definition: TSP_Concorde.h:36
vector< int > m_edgeList
Definition: TSP_Concorde.h:59
void CCtsp_free_lpcut_in(CCtsp_lpcut_in *c)
struct CCtsp_lpcut_in * next
Definition: TSP_ConcordeI.h:43
int CCtsp_exact_subtours(CCtsp_lpcut_in **cuts, int *cutcount, int ncount, int ecount, int *elist, double *x)