Dip-All  0.91.0
VRP_CVRPsep.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 VRP_CVRPSEP_INCLUDED
14 #define VRP_CVRPSEP_INCLUDED
15 
16 //---
17 //--- Interface class to CVRPSEP (separation routines for CVRP)
18 //--- Note: all CVRSEP arrays start counting from 1 (not 0)
19 //--- for n customers, consider n+1 the depot node
20 //---
21 
22 // --------------------------------------------------------------------- //
23 #include "cnstrmgr.h"
24 #include "capsep.h"
25 
26 // --------------------------------------------------------------------- //
27 #include "VRP_GSECCut.h"
28 #include "VRP_Instance.h"
29 
30 // --------------------------------------------------------------------- //
31 // --------------------------------------------------------------------- //
33 public:
34  int nEdges;
35  double * EdgeX;
36  int * EdgeTail;
37  int * EdgeHead;
38 
39 public:
41  nEdges (0),
42  EdgeX (0),
43  EdgeTail(0),
44  EdgeHead(0)
45  {};
46 
47  void clear(){
51  }
52 
53  void init(const int n){
54  nEdges = n;
55  if(nEdges > 0){
56  clear(); //TODO: doing this each time is inefficient
57  EdgeX = new double[nEdges+1];
58  EdgeTail = new int[nEdges+1];
59  EdgeHead = new int[nEdges+1];
60  CoinAssertHint(EdgeX && EdgeTail && EdgeHead, "Error: Out of Memory");
61  EdgeX[0] = 0.0;
62  EdgeTail[0] = 0;
63  EdgeHead[0] = 0;
64  }
65  }
66 
68  {
69  clear();
70  };
71 };
72 
73 
74 
75 // --------------------------------------------------------------------- //
76 // --------------------------------------------------------------------- //
77 class VRP_CVRPsep {
78 public:
79  const VRP_Instance * m_vrp; //ptr to vrp instance
80  CVRPsep_LPSol m_lpSol; //storage of current lp solution
81  CnstrMgrPointer m_newCuts; //my new CVRPsep cuts
82  CnstrMgrPointer m_oldCuts; //my old CVRPsep cuts
83 
84 
85 public:
86  VRP_CVRPsep(const int maxCuts = 500) :
87  m_vrp (0),
88  m_lpSol (),
89  m_newCuts (),
90  m_oldCuts ()
91  {
92  CMGR_CreateCMgr(&m_newCuts, maxCuts);
93  CMGR_CreateCMgr(&m_oldCuts, 10*maxCuts);
94  }
96  CMGR_FreeMemCMgr(&m_newCuts);
97  CMGR_FreeMemCMgr(&m_oldCuts);
98  }
99 
100 public:
101 
103  void init(const VRP_Instance * vrp) {
104  m_vrp = vrp;
105  //TODO: could alloc cuts here and send in param for size
106  }
107 
108 
109  void buildLpSol(const double * x,
110  const int nNzs,
111  const double etol = 1.0e-8){
112  int e;
113  int ind = 1;
114  int nEdges = m_vrp->m_graphLib.n_edges;
115  int nVerts = m_vrp->m_graphLib.n_vertices;
116 
117  //---
118  //--- free old memory, open new memory of size nszs
119  //--- TODO: would be more efficient if we did not
120  //--- do this every time - just create lpsol
121  //--- vecs of max size (nEdges) and don't
122  //--- bother clearing
123  //---
124  m_lpSol.init(nNzs);//allocates nNsz+1
125  for(e = 0; e < nEdges; e++){
126  if(x[e] > etol){
127  pair<int,int> uv = UtilBothEndsU(e);
128 
129  //---
130  //--- CVRPSEP convention:
131  //--- 1.) edgelist is 1 to NoOfEdges
132  //????????? nodes start from - so does ours...
133  //--- 2.) depot is numbered nCustomers+1=nVerts
134  //---
135  m_lpSol.EdgeX[ind] = x[e];
136  m_lpSol.EdgeTail[ind]
137  = uv.second == 0 ? nVerts : uv.second;
138  m_lpSol.EdgeHead[ind]
139  = uv.first == 0 ? nVerts : uv.first;
140 #if 0
141  printf("XLP[%d,%d -> %d,%d] = %g\n",
142  uv.first, uv.second,
143  m_lpSol.EdgeTail[ind],
144  m_lpSol.EdgeHead[ind], x[e]);
145  UTIL_DEBUG(m_appParam.Log, 5,
146  (*m_osLog) << "XLP[" << uv.first << "," << uv.second;
147  (*m_osLog) << " -> " << m_lpSol.EdgeTail[ind] << ",";
148  (*m_osLog) << m_lpSol.EdgeHead[ind] << "]";
149  (*m_osLog) << " = " << x[e] << endl;
150  );
151 #endif
152  assert(ind <= nNzs);
153  ind++;
154  }
155  }
156  }
157 
158 
159 
160  int sepCapacityCuts(const int maxCuts = 500){
161 
162  const UtilGraphLib & graphLib = m_vrp->m_graphLib;
163  const int nVerts = graphLib.n_vertices;
164  const int * demand = graphLib.vertex_wt;
165  const int capacity = graphLib.capacity;
166 
167  //---
168  //--- check to make sure m_newCuts is big enough for max size
169  //---
170  //CMGR_ExpandCMgr(m_newCuts, maxCuts);//??
171 
172  char IntegerAndFeasible;
173  double MaxViolation;
174 
175  m_newCuts->Size = 0; //need to do?
176  CAPSEP_SeparateCapCuts(nVerts - 1,
177  const_cast<int*>(demand),
178  capacity,
179  m_lpSol.nEdges,
181  m_lpSol.EdgeHead,
182  m_lpSol.EdgeX,
183  m_oldCuts,
184  maxCuts,
185  0.001, //EpsForIntegrality
186  &IntegerAndFeasible,
187  &MaxViolation,
188  m_newCuts);
189 #if 0
190  printf("Found %d capacity cuts. MaxViolation=%g\n",
191  m_newCuts->Size, MaxViolation);
192 #endif
193  return m_newCuts->Size;
194  }
195 
196 
197  void createVrpCuts(DecompCutList & newCuts){
198  int i, j;
199  const UtilGraphLib & graphLib = m_vrp->m_graphLib;
200  const int nVerts = graphLib.n_vertices;
201  const int * demand = graphLib.vertex_wt;
202  const int capacity = graphLib.capacity;
203 
204 
205  for(i = 0; i < m_newCuts->Size; i++){
206  CnstrPointer CP = m_newCuts->CPL[i];
207 
208  switch(CP->CType){
209  case CMGR_CT_CAP:
210  {
211  dynamic_bitset<> inS(nVerts);
212  for(j = 1; j <= CP->IntListSize; j++){
213  if(CP->IntList[j] == nVerts)//depot
214  inS.set(0);
215  else
216  inS.set(CP->IntList[j]);
217  }
218  VRP_GSECCut * cut = new VRP_GSECCut(inS, demand, capacity);
219  //cut->print();
220  //double lb = cut->getLowerBound();
221  double ub = cut->getUpperBound();
222  //printf("CUT lb=%g ub=%g\n", lb, ub);
223  //printf("CVRPSEP RHS=%g\n", CP->RHS);
224  assert(UtilIsZero(CP->RHS - ub));
225  newCuts.push_back(cut);
226  }
227  break;
228  default:
229  CoinAssert(0);
230  }
231  }
232 
233  //---
234  //--- move new cuts into old cut pool
235  //---
236  //--- NOTE: if the framework decides that some cut sould not
237  //--- be entered (exceeds max number per pass or something)
238  //--- then we don't really want this to go into old cuts yet
239  //---
240  for(i = 0; i < m_newCuts->Size; i++)
241  CMGR_MoveCnstr(m_newCuts, m_oldCuts, i, 0);
242  //cout << "After Move m_newCuts size = " << m_newCuts->Size << endl;
243  //cout << "After Move m_oldCuts size = " << m_oldCuts->Size << endl;
244  }
245 };
246 
247 #endif
void buildLpSol(const double *x, const int nNzs, const double etol=1.0e-8)
Definition: VRP_CVRPsep.h:109
std::list< DecompCut * > DecompCutList
Definition: Decomp.h:55
bool UtilIsZero(const double x, const double etol=1.0e-8)
Definition: UtilMacros.h:272
double getUpperBound() const
Definition: DecompCut.h:51
pair< int, int > UtilBothEndsU(const int index)
void init(const int n)
Definition: VRP_CVRPsep.h:53
void init(const VRP_Instance *vrp)
Definition: VRP_CVRPsep.h:103
#define UTIL_DELARR(x)
Definition: UtilMacros.h:29
VRP_CVRPsep(const int maxCuts=500)
Definition: VRP_CVRPsep.h:86
#define CoinAssertHint(expression, hint)
Definition: CoinError.hpp:180
int sepCapacityCuts(const int maxCuts=500)
Definition: VRP_CVRPsep.h:160
void clear()
Definition: VRP_CVRPsep.h:47
int * EdgeHead
Definition: VRP_CVRPsep.h:37
int * EdgeTail
Definition: VRP_CVRPsep.h:36
UtilGraphLib m_graphLib
Data for an instance from VRPLIB.
Definition: VRP_Instance.h:29
CVRPsep_LPSol m_lpSol
Definition: VRP_CVRPsep.h:80
CnstrMgrPointer m_oldCuts
Definition: VRP_CVRPsep.h:82
#define UTIL_DEBUG(param, level, x)
Definition: UtilMacros.h:34
double * EdgeX
Definition: VRP_CVRPsep.h:35
const VRP_Instance * m_vrp
Definition: VRP_CVRPsep.h:79
int * vertex_wt
Definition: UtilGraphLib.h:61
void createVrpCuts(DecompCutList &newCuts)
Definition: VRP_CVRPsep.h:197
#define CoinAssert(expression)
Definition: CoinError.hpp:179
CnstrMgrPointer m_newCuts
Definition: VRP_CVRPsep.h:81