Dip-All  0.91.0
VRP_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 VRP_CONCORDE_INCLUDED
14 #define VRP_CONCORDE_INCLUDED
15 
16 //---
17 //--- Interface class to Concorde (TSP solver)
18 //---
19 
20 // --------------------------------------------------------------------- //
21 #include "VRP_ConcordeI.h"
22 
23 // --------------------------------------------------------------------- //
24 #define VRP_CONCORDE_DEBUG 0
25 #define VRP_CONCORDE_SOLVER_TINY 1
26 //#define VRP_CONCORDE_SOLVER_TINY 0
27 
28 // --------------------------------------------------------------------- //
29 // --------------------------------------------------------------------- //
31  public:
32  int m_nEdges;
33  int m_nVerts;
34  int * m_edgeList;
35  int * m_edgeValue;
36 
37  //index on complete graph to index on complete graph minus d-to-d edges
38  //int * m_edgeMapCtoN;
39  //index on complete graph minus d-to-d edges to index on complete graph
40  //int * m_edgeMapNtoC;
41 
42  public:
44  m_nEdges (0),
45  m_nVerts (0),
46  m_edgeList (0),
47  m_edgeValue (0)
48  //m_edgeMapCtoN(0),
49  //m_edgeMapNtoC(0)
50 {};
51 
52  void clear(){
53  m_nEdges = 0;
54  m_nVerts = 0;
57  //UTIL_DELARR(m_edgeMapCtoN);
58  //UTIL_DELARR(m_edgeMapNtoC);
59  }
60 
61  void setEdgeValue(const double * edgeValue){
62 
63  }
64 
65  void init(const int nVerts,
66  const int nEdges){
67  m_nVerts = nVerts;
68  m_nEdges = nEdges;
69  if(nEdges > 0){
70  m_edgeList = new int[2 * m_nEdges];
71  m_edgeValue = new int[ m_nEdges];
72  //m_edgeMapCtoN = new int[ m_nEdges];
73  //m_edgeMapNtoC = new int[ m_nEdges];
74  //UtilFillN(m_edgeMapCtoN, m_nEdges, -1);
75  //UtilFillN(m_edgeMapNtoC, m_nEdges, -1);
77  //m_edgeMapCtoN && m_edgeMapNtoC,
78  "Error: Out of Memory");
79  }
80  }
81 
83  clear();
84  };
85 };
86 
87 // --------------------------------------------------------------------- //
88 // --------------------------------------------------------------------- //
89 class VRP_Concorde {
90  public:
91  const VRP_Instance * m_vrp; //ptr to vrp instance
92  ConcordeGraph m_cgExpand; //complete graph expanded
93  int * m_CCoptTour; //store optimal tour out of concorde
94  double m_CCoptVal; //store optimal obj out of concorde
95  //tmp storage of doubles (sz = num of original edges)
96  double * tmpDblNOrigE;
97  //tmp storage of doubles (sz = num of original edges)
98  int * tmpIntNOrigE;
99 
100  public:
102  m_vrp (0),
103  m_cgExpand ( ) ,
104  m_CCoptTour (0),
105  m_CCoptVal ( ) ,
106  tmpDblNOrigE( ) ,
107  tmpIntNOrigE( ) {}
108 
113  }
114 
115  public:
116 
118  void init(const VRP_Instance * vrp) {
119  m_vrp = vrp;
121  m_CCoptTour = new int[m_cgExpand.m_nVerts];
122  CoinAssertHint(m_CCoptTour, "Error: Out of Memory");
123 
124  const UtilGraphLib & graphLib = m_vrp->m_graphLib;
125  tmpDblNOrigE = new double[graphLib.n_edges];
126  tmpIntNOrigE = new int [graphLib.n_edges];
128  "Error: Out of Memory");
129  }
130 
131 
133  //---
134  //--- To represent a VRP graph as a TSP instance we need to
135  //--- create (nRoutes-1) additional dummy depots and their
136  //--- associated customer edges.
137  //---
138  //--- Original VRP graph has depot=0 and n_vertices-1 customers
139  //--- depot => 0
140  //--- C => {1,..,n_vertices-1}
141  //--- Now, we will shift the customers back to index:
142  //--- C => {0,..,n_vertices-2}
143  //--- and make the depot indices
144  //--- depot => n_vertices-1, .... n_vertices - 1 + nRoutes
145  //---
146  //--- We do not want or need edges between dummy depots. But, it
147  //--- actually makes the accounting easier to have them. So, we will
148  //--- include them and treat this like a complete graph but make the
149  //--- edge weights on depot-depot edges high (or just fix to 0).
150  //---
151  //--- NOTE: changed to remove depot-to-depot edges, now using
152  //--- a mapping for the book-keeping
153  //---
154  int i, j, edgeIndex;
155  const UtilGraphLib & graphLib = m_vrp->m_graphLib;
156  const int nRoutes = m_vrp->m_numRoutes;
157  int nCustomers = graphLib.n_vertices - 1;
158  int nVerts = nCustomers + nRoutes;
159  int nEdges = UtilNumEdgesU(nVerts);
160  int * edgeList = NULL;
161  //int * edgeMapCtoN = NULL;
162  //int * edgeMapNtoC = NULL;
163 
164  //---
165  //--- Assumption: a complete undirected graph,
166  //--- (i,j) = (j,i), i!=j (setup for i>j)
167  //--- Loop thru edges: i: 1 -> n-1, j: 0 -> i-1
168  //--- Number of edges: m = (n^2 - n)/2 - (nR^2 - nR)/2
169  //---
170  m_cgExpand.init(nVerts, nEdges);
171  edgeIndex = 0;
172  //edgeIndexC = 0;
173  edgeList = m_cgExpand.m_edgeList;
174  //edgeMapCtoN = m_cgExpand.m_edgeMapCtoN;
175  //edgeMapNtoC = m_cgExpand.m_edgeMapNtoC;
176  for(i = 1; i < nVerts; i++){
177  for(j = 0; j < i; j++){
178  //printf("(i=%d, j=%d) edgeIndexC:%d edgeIndex:%d",
179  // i,j,edgeIndexC,edgeIndex);
180  //if(i >= nCustomers && j >= nCustomers)
181  // printf(" --> depot edge");
182  //printf("\n");
183  //edgeMapCtoN[edgeIndexC] = edgeIndex;
184  //edgeMapNtoC[edgeIndex ] = edgeIndexC;
185  //exclude depot-to-depot edges
186  //if(i < nCustomers || j < nCustomers){
187  edgeList[2*edgeIndex ] = i;
188  edgeList[2*edgeIndex+1] = j;
189  CoinAssert(edgeIndex < nEdges);
190  edgeIndex++;
191  //}
192  //edgeIndexC++;
193  }
194  }
195  //TODO: or, open up less, except for m_edgeMapCtoN?
196  // m_cgExpand.m_nEdges = edgeIndex;
197  //assert(m_cgExpand.m_nEdges ==
198  // (UtilNumEdgesU(nVerts) - UtilNumEdgesU(nRoutes)));
199  }
200 
201  void setExpandedCost(const double * origGraphCost){
202  //---
203  //--- origGraphCost contains the costs based on original graph
204  //---
205  //--- Original VRP graph has depot=0 and n_vertices-1 customers
206  //--- depot => 0
207  //--- C => {1,..,n_vertices-1}
208  //---
209  const UtilGraphLib & graphLib = m_vrp->m_graphLib;
210  const int nOrigEdges = graphLib.n_edges;
211  const int nOrigVerts = graphLib.n_vertices;
212  const int nRoutes = m_vrp->m_numRoutes;
213  const int nEdges = m_cgExpand.m_nEdges;
214  const int nCustomers = nOrigVerts - 1;
215  double * origGraphCostDbl = tmpDblNOrigE;
216  int * origGraphCostInt = tmpIntNOrigE;
217  int * edgeValue = m_cgExpand.m_edgeValue;
218  int i;
219  //---
220  //--- offset the orig (reduced costs) costs so all positive
221  //---
222 #if VRP_CONCORDE_DEBUG > 0
223  for(i = 0; i < nOrigEdges; i++){
224  printf("origGraphCost[%d -> %s]: %10.5f\n",
225  i, UtilEdgeToStr(i).c_str(), origGraphCost[i]);
226  }
227 #endif
228  const double * minElement = min_element(origGraphCost,
229  origGraphCost + nOrigEdges);
230  const double offset = min(0.0, *minElement);
231 #if VRP_CONCORDE_DEBUG > 0
232  printf("minElement = %10.5f offset = %10.5f\n", *minElement, -offset);
233 #endif
234  memcpy(origGraphCostDbl, origGraphCost, nOrigEdges * sizeof(double));
235  if(offset < 0.0){
236  UtilAddOffsetArr(nOrigEdges, -offset, origGraphCostDbl);
237  }
238 
239  //---
240  //--- scale to integers (do something very simple)
241  //--- just multiply by 1.0e4 and then round
242  //--- this should avoid any kind of overflow and
243  //--- give accuracy at the 4th decimal place which should be
244  //--- sufficient
245  //--- NOTE: epsilon=1.0e-6, 1.0e-4 causes overflow issues
246  //---
247  //int scaleFactor =
248  UtilScaleDblToIntArr(nOrigEdges,
249  origGraphCostDbl,
250  origGraphCostInt, 1.0e-3);
251  //UtilScaleDblToIntArrCC(nOrigEdges,
252  // origGraphCostDbl,
253  // origGraphCostInt);
254 #if VRP_CONCORDE_DEBUG > 0
255  //printf("scaleFactor = %d\n", scaleFactor);
256  for(i = 0; i < nOrigEdges; i++){
257  printf("origGraphCost[%d]: %10.5f -> %10d\n",
258  i,
259  origGraphCostDbl[i],
260  origGraphCostInt[i]);
261  //CoinAssert(origGraphCostInt[i] < bigCost);
262  }
263 #endif
264 
265  //---
266  //--- find max edge length for "bigM" on depot-to-depot edges
267  //--- check for integer overflow
268  //---
269  int bigCost = 0;
270  double bigCostDbl = 0.0;
271  int maxEdgeLen = *max_element(origGraphCostInt,
272  origGraphCostInt+nOrigEdges);
273  bigCostDbl = ((double)maxEdgeLen+1.0) * (double)m_cgExpand.m_nVerts;
274  if((256*bigCostDbl) > (double)CCutil_MAXINT) {
275  printf("WARNING: Large edge lengths!!!!\n");
276  bigCost = CCutil_MAXINT / 256;
277  }
278  else
279  bigCost = (maxEdgeLen+1) * m_cgExpand.m_nVerts;
280 
281  while(maxEdgeLen > bigCost){
282  printf("maxEdgeLen=%d > bigCost=%d !!! SCALE BY 10\n",
283  maxEdgeLen, bigCost);
284  //scale by 10
285  for(i = 0; i < nOrigEdges; i++){
286  origGraphCostInt[i] /= 10;//and int will trunc it
287  }
288  maxEdgeLen /= 10;
289  }
290  assert(maxEdgeLen < bigCost);
291 
292  //---
293  //--- shift the customers back to index
294  //--- C => {0,..,n_vertices-2}
295  //--- and make the depot indices
296  //--- depot => n_vertices-1, .... n_vertices - 1 + nRoutes
297  //---
298  //--- set all depot to depot costs to a big number (DON'T NEED)
299  //--- and
300  //--- duplicate the original depot to customer edges for dummies
301  //---
302  int origDepot = 0;
303  int origCost = 0;
304  int u, v, d, d1, d2, origIndex, newIndex, custIndex, depot;
305  for(u = 1; u < nOrigVerts; u++){
306  for(v = 1; v < u; v++){
307  origIndex = UtilIndexU(u,v);
308  newIndex = UtilIndexU(u-1, v-1);
309 #if VRP_CONCORDE_DEBUG > 0
310  printf("origIndex: [%d -> %s] to newIndex: [%d -> %s]\n",
311  origIndex, UtilEdgeToStr(origIndex).c_str(),
312  newIndex, UtilEdgeToStr(newIndex).c_str());
313 #endif
314  CoinAssert(origGraphCostInt[origIndex] >= 0);
315  CoinAssert(origGraphCostInt[origIndex] < bigCost);
316  edgeValue[newIndex] = origGraphCostInt[origIndex];
317  }
318  }
319  for(u = 1; u <= nCustomers; u++){
320  //get the original cost of customer to depot
321  origIndex = UtilIndexU(u, origDepot);
322  origCost = origGraphCostInt[origIndex];
323  //in the concorde graph, the customers are 0..c-1
324  custIndex = u - 1;
325  //in the concorde graph, the depots are c..c+r-1
326  for(d = 0; d < nRoutes; d++){
327  depot = nCustomers + d;
328  //get the index in the concorde graph based on complete graph
329  //newIndex = edgeMapCtoN[UtilIndexU(custIndex, depot)];
330  newIndex = UtilIndexU(custIndex, depot);
331  CoinAssert(newIndex < nEdges);
332  //CoinAssert(origGraphCostInt[origIndex] < bigCost);
333 #if VRP_CONCORDE_DEBUG > 0
334  printf("(u:%d,0) origIndex=%d origCost=%d d=%d cInd=%d nInd=%d\n",
335  u, origIndex, origCost, d,
336  UtilIndexU(custIndex, depot), newIndex);
337 #endif
338  edgeValue[newIndex] = origCost;
339  }
340  }
341  for(d1 = 1; d1 < nRoutes; d1++){
342  for(d2 = 0; d2 < d1; d2++){
343  newIndex = UtilIndexU(nCustomers + d1,
344  nCustomers + d2);
345  edgeValue[newIndex] = bigCost;//bigCost (causing overflow)
346  }
347  }
348 
349  //#if VRP_CONCORDE_DEBUG > 0
350  //for(i = 0; i < nEdges; i++){
351  //printf("newGraphCostInt[%d -> %s]: %d\n",
352  // i, UtilEdgeToStr(i).c_str(), edgeValue[i]);
353  //printf("newGraphCostInt[%d -> (%d,%d)]: %d\n",
354  // i,
355  // edgeList[2*i],
356  // edgeList[2*i+1],
357  // edgeValue[i]);
358  //}
359  //#endif
360  }
361 
362  int solveTSP(vector<int> & vrpRouteInd,
363  vector<double> & vrpRouteEls){
364 
365 
366  //---
367  //--- NOTE: using this requires linking with Cplex right now
368  //---
369  //--- int CCtsp_solve_dat (int ncount,
370  //--- CCdatagroup * indat,
371  //--- int * in_tour,
372  //--- int * out_tour,
373  //--- double * in_val,
374  //--- double * optval,
375  //--- int * success,
376  //--- int * foundtour,
377  //--- char * name,
378  //--- double * timebound,
379  //--- int * hit_timebound,
380  //--- int silent,
381  //--- CCrandstate * rstate);
382  //---
383 
384  //---
385  //--- Description:
386  //--- SOLVES the TSP over the graph specfied in the edgelist.
387  //--- - elist is an array giving the ends of the edges (in pairs)
388  //--- - elen is an array giving the weights of the edges.
389  //--- - in_tour gives a starting tour in node node node format (it can
390  //--- be NULL)
391  //--- - out_tour will return the optimal tour (it can be NULL, if it is
392  //--- not NULL then it should point to an array of length at least
393  //--- ncount.
394  //--- - in_val can be used to specify an initial upperbound (it can be
395  //--- NULL)
396  //--- - optval will return the value of the optimal tour.
397  //--- - success will be set to 1 if the run finished normally,
398  //--- and set to if the search was terminated early (by hitting
399  //--- some predefined limit)
400  //--- - foundtour will be set to 1 if a tour has been found (if success
401  //--- is 0, then it may not be the optimal tour)
402  //--- - name specifes a char string that will be used to name various
403  //--- files that are written during the branch and bound search
404  //--- (if it is NULL, then "noname" will be used - this will
405  //--- cause problems in a multithreaded program, so specify a
406  //--- distinct name in that case).
407  //--- - silent will suppress most output if set to a nonzero value.
408  //---
409  int returnCode = 0;
410  int silent = 2;
411  int success, foundtour, hit_timebound;
412 
413  CCrandstate rstate;
414  int seed = 1;
415  CCutil_sprand(seed, &rstate);
416 
417 
418  //do this once
419  int i, d1, d2;
420  const UtilGraphLib & graphLib = m_vrp->m_graphLib;
421  int nRoutes = m_vrp->m_numRoutes;
422  int nOrigVerts = graphLib.n_vertices;
423  int nCustomers = nOrigVerts - 1;
424  double upbound = DecompInf;
425  double optval = DecompInf;
426 
427  //---
428  //--- try tiny first, switch if needed... if fails
429  //--- for now, full blown solver is overkill... ?
430  //---
431  int * lower = new int[m_cgExpand.m_nEdges];
432  int * upper = new int[m_cgExpand.m_nEdges];
433  int * xsol = new int[m_cgExpand.m_nEdges];
434  for(i = 0; i < m_cgExpand.m_nEdges; i++){
435  lower[i] = 0;
436  upper[i] = 1;
437  xsol[i] = 0;
438  }
439  for(d1 = 1; d1 < nRoutes; d1++){
440  for(d2 = 0; d2 < d1; d2++){
441  upper[UtilIndexU(nCustomers + d1, nCustomers + d2)] = 0;
442  }
443  }
444  returnCode = CCtiny_bnc_msp (m_cgExpand.m_nVerts,
448  -1,//depot
449  lower,
450  upper,
451  &upbound,
453  &optval,
454  xsol,
455  1, //checkresult (make option)
456  1000); //nodelimit
457 
458  assert(returnCode != CC_TINYTSP_ERROR);
459  assert(returnCode != CC_TINYTSP_INFEASIBLE);
460  bool useFullSolver = false;
461  if(returnCode == CC_TINYTSP_SEARCHLIMITEXCEEDED){
462  printf("Search limit exceeded - let's go to full solver\n");
463  useFullSolver = true;
464  }
465 
466  delete [] lower;
467  delete [] upper;
468 
469  if(useFullSolver){
470  CCdatagroup dataGroup;
475  -1, &dataGroup);
476  char nameC[100];
477  string name = UtilStringRandom(10);
478  strcpy(nameC, name.c_str());
479 
480 #if VRP_CONCORDE_DEBUG > 0
481  printf("CONCORDE GRAPH:\n");
482  printf(" nVerts=%d nEdges=%d\n",
485  for(i = 0; i < m_cgExpand.m_nEdges; i++){
486  printf("(%4d,%4d) val:%4d\n",
487  m_cgExpand.m_edgeList[2*i],
488  m_cgExpand.m_edgeList[2*i+1],
490  }
491 #endif
492 
493  returnCode = CCtsp_solve_dat(m_cgExpand.m_nVerts,
494  &dataGroup,
495  NULL, //in_tour
496  m_CCoptTour,
497  NULL, //in_val,
498  &m_CCoptVal,
499  &success,
500  &foundtour,
501  nameC,
502  NULL, //timebound
503  &hit_timebound,
504  silent,
505  &rstate);
506  CoinAssert((success == 1) && (foundtour == 1));
507  }
508 
509 #if VRP_CONCORDE_DEBUG > 0
510  printf("Optimal Route:\n");
511 #endif
512 
513 
514  if(!useFullSolver){
515  vector<int> edgeListSol;
516  for(i = 0; i < m_cgExpand.m_nEdges; i++){
517  if(xsol[i]){
518 #if VRP_CONCORDE_DEBUG > 0
519  printf("(%d,%d) wt:%d\n",
520  m_cgExpand.m_edgeList[2*i],
521  m_cgExpand.m_edgeList[2*i+1],
523 #endif
524  edgeListSol.push_back(m_cgExpand.m_edgeList[2*i]);
525  edgeListSol.push_back(m_cgExpand.m_edgeList[2*i+1]);
526  }
527  }
528  createVrpRouteFromTspEdgeList(edgeListSol,
529  vrpRouteInd,
530  vrpRouteEls);
531  }
532  else{
535  vrpRouteInd,
536  vrpRouteEls);
537  }
538  return returnCode;
539  }
540 
541  void createVrpRouteFromTspEdgeList(vector<int> & tspEdgeList,
542  vector<int> & vrpRouteInd,
543  vector<double> & vrpRouteEls){
544 
545  int i, u, v;
546  int nVerts = m_vrp->m_graphLib.n_vertices;
547  int nCustomers = m_vrp->m_graphLib.n_vertices - 1;
548  int * depotEdges = tmpIntNOrigE;
549 
550  //---
551  //--- keep track of depot edges separate for 1-routes (els=2.0)
552  //---
553  UtilFillN(depotEdges, nVerts, 0);
554 #if VRP_CONCORDE_DEBUG > 0
555  printf("Optimal Route:\n");
556 #endif
557  for(i = 0; i < m_cgExpand.m_nVerts; i++){
558  //for(i = 0; i < tspRouteLen-1; i++){
559  u = tspEdgeList[2*i];
560  v = tspEdgeList[2*i+1];
561  u = u >= nCustomers ? 0 : u+1;
562  v = v >= nCustomers ? 0 : v+1;
563  CoinAssert((u + v) > 0);
564  if(u == 0){
565  depotEdges[v]++; //(0,v) depot edge
566  }
567  else if(v == 0){
568  depotEdges[u]++; //(u,0) depot edge
569  }
570  else{
571  vrpRouteInd.push_back(UtilIndexU(u,v));
572 #if VRP_CONCORDE_DEBUG > 0
573  printf("(%d,%d) -> %d\n", u, v, UtilIndexU(u,v));
574 #endif
575  }
576  }
577  UtilFillN(vrpRouteEls, vrpRouteInd.size(), 1.0);
578 
579  for(v = 1; v < nVerts; v++){
580  if(depotEdges[v]){
581  CoinAssert(depotEdges[v] >= 0);
582  CoinAssert(depotEdges[v] <= 2);
583  vrpRouteInd.push_back(UtilIndexU(v, 0));
584  vrpRouteEls.push_back(static_cast<double>(depotEdges[v]));
585 #if VRP_CONCORDE_DEBUG > 0
586  printf("%d D(%d,%d) -> %d\n",
587  depotEdges[v], v, 0, UtilIndexU(v,0));
588 #endif
589  }
590  }
591  }
592 
593  void createVrpRouteFromTspRoute(const int * tspRoute,
594  const int tspRouteLen,
595  vector<int> & vrpRouteInd,
596  vector<double> & vrpRouteEls){
597 
598  int i, u, v;
599  int nVerts = m_vrp->m_graphLib.n_vertices;
600  int nCustomers = m_vrp->m_graphLib.n_vertices - 1;
601  int * depotEdges = tmpIntNOrigE;
602 
603  //---
604  //--- keep track of depot edges separate for 1-routes (els=2.0)
605  //---
606  UtilFillN(depotEdges, nVerts, 0);
607 #if VRP_CONCORDE_DEBUG > 0
608  printf("Optimal Route Nodes:");
609  for(i = 0; i < tspRouteLen; i++){
610  printf("%d ", tspRoute[i]);
611  }
612  printf("\nOptimal Route Edges:\n");
613 #endif
614  for(i = 0; i < tspRouteLen-1; i++){
615  u = tspRoute[i] >= nCustomers ? 0 : tspRoute[i] +1;
616  v = tspRoute[i+1] >= nCustomers ? 0 : tspRoute[i+1]+1;
617  CoinAssert((u + v) > 0);
618  if(u == 0){
619  depotEdges[v]++; //(0,v) depot edge
620  }
621  else if(v == 0){
622  depotEdges[u]++; //(u,0) depot edge
623  }
624  else{
625  vrpRouteInd.push_back(UtilIndexU(u,v));
626  }
627 #if VRP_CONCORDE_DEBUG > 0
628  printf("(%d,%d) -> %d\n", u, v, UtilIndexU(u,v));
629 #endif
630  }
631  u = tspRoute[tspRouteLen-1] >= nCustomers ? 0
632  : tspRoute[tspRouteLen-1]+1;
633  v = tspRoute[0] >= nCustomers ? 0 : tspRoute[0] + 1;
634  CoinAssert((u + v) > 0);
635  if(u == 0){
636  depotEdges[v]++; //(0,v) depot edge
637  }
638  else if(v == 0){
639  depotEdges[u]++; //(u,0) depot edge
640  }
641  else{
642  vrpRouteInd.push_back(UtilIndexU(u,v));
643  }
644 #if VRP_CONCORDE_DEBUG > 0
645  printf("(%d,%d) -> %d\n", u, v, UtilIndexU(u,v));
646 #endif
647  UtilFillN(vrpRouteEls, vrpRouteInd.size(), 1.0);
648 
649  for(v = 1; v < nVerts; v++){
650  if(depotEdges[v]){
651  CoinAssert(depotEdges[v] >= 0);
652  CoinAssert(depotEdges[v] <= 2);
653  vrpRouteInd.push_back(UtilIndexU(v, 0));
654  vrpRouteEls.push_back(static_cast<double>(depotEdges[v]));
655 #if VRP_CONCORDE_DEBUG > 0
656  printf("%d D(%d,%d) -> %d\n",
657  depotEdges[v], v, 0, UtilIndexU(v,0));
658 #endif
659  }
660  }
661  }
662 
663  void createTSPLIBFile(const string fileName){
664  ofstream os;
665  int i, j, edgeIndex;
666  const int nVerts = m_cgExpand.m_nVerts;
667  const int * edgeValue = m_cgExpand.m_edgeValue;
668 
669  printf("Open File %s\n", fileName.c_str());
670 
671  UtilOpenFile(os, fileName);
672  os << "NAME: " << fileName << "\n"
673  << "TYPE: TSP\n"
674  << "DIMENSION: " << nVerts << "\n"
675  << "EDGE_WEIGHT_TYPE: EXPLICIT\n"
676  << "EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW\n"
677  << "EDGE_WEIGHT_SECTION\n";
678  os << " 0\n";
679  edgeIndex = 0;
680  for(i = 1; i < nVerts; i++){
681  for(j = 0; j < i; j++){
682  os << edgeValue[edgeIndex] << " ";
683  edgeIndex++;
684  }
685  os << " 0\n";
686  }
687  os << "EOF\n";
688 
689  os.close();
690  }
691 
692 
693 };
694 
695 
696 #endif
int UtilIndexU(const int i, const int j)
Definition: UtilMacros.h:134
int solveTSP(vector< int > &vrpRouteInd, vector< double > &vrpRouteEls)
Definition: VRP_Concorde.h:362
int * m_CCoptTour
Definition: VRP_Concorde.h:93
std::string UtilStringRandom(int iLength)
Definition: UtilMacros.h:385
int * m_edgeValue
Definition: VRP_Concorde.h:35
void createVrpRouteFromTspRoute(const int *tspRoute, const int tspRouteLen, vector< int > &vrpRouteInd, vector< double > &vrpRouteEls)
Definition: VRP_Concorde.h:593
#define CC_TINYTSP_INFEASIBLE
Definition: VRP_ConcordeI.h:23
int * tmpIntNOrigE
Definition: VRP_Concorde.h:98
ConcordeGraph m_cgExpand
Definition: VRP_Concorde.h:92
int * m_edgeList
Definition: VRP_Concorde.h:34
#define CC_TINYTSP_SEARCHLIMITEXCEEDED
Definition: VRP_ConcordeI.h:22
int UtilNumEdgesU(const int n)
Definition: UtilMacros.h:128
void init(const int nVerts, const int nEdges)
Definition: VRP_Concorde.h:65
#define UTIL_DELARR(x)
Definition: UtilMacros.h:29
#define CoinAssertHint(expression, hint)
Definition: CoinError.hpp:180
double m_CCoptVal
Definition: VRP_Concorde.h:94
void UtilOpenFile(ifstream &fs, const char *fileName)
Definition: UtilMacros.h:526
UtilGraphLib m_graphLib
Data for an instance from VRPLIB.
Definition: VRP_Instance.h:29
const VRP_Instance * m_vrp
Definition: VRP_Concorde.h:91
int CCtsp_solve_dat(int ncount, CCdatagroup *indat, int *in_tour, int *out_tour, double *in_val, double *optval, int *success, int *foundtour, char *name, double *timebound, int *hit_timebound, int silent, CCrandstate *rstate)
void createVrpRouteFromTspEdgeList(vector< int > &tspEdgeList, vector< int > &vrpRouteInd, vector< double > &vrpRouteEls)
Definition: VRP_Concorde.h:541
std::string UtilEdgeToStr(const int index)
Definition: UtilMacros.h:247
#define CC_TINYTSP_MINIMIZE
Definition: VRP_ConcordeI.h:20
void UtilAddOffsetArr(const int arrLen, T offset, T *arr)
Definition: UtilMacros.h:352
void UtilFillN(T *to, const int size, const T value)
Definition: UtilMacros.h:158
int CCutil_graph2dat_matrix(int ncount, int ecount, int *elist, int *elen, int defaultlen, CCdatagroup *dat)
void setEdgeValue(const double *edgeValue)
Definition: VRP_Concorde.h:61
void buildExpandedCompleteGraph()
Definition: VRP_Concorde.h:132
#define CCutil_MAXINT
Definition: VRP_ConcordeI.h:24
#define CoinAssert(expression)
Definition: CoinError.hpp:179
#define CC_TINYTSP_ERROR
Definition: VRP_ConcordeI.h:21
void CCutil_sprand(int seed, CCrandstate *r)
void init(const VRP_Instance *vrp)
Definition: VRP_Concorde.h:118
int CCtiny_bnc_msp(int ncount, int ecount, int *elist, int *elen, int depot, int *lower, int *upper, double *upperbound, int objsense, double *optval, int *xsol, int checkresult, int searchlimit)
void createTSPLIBFile(const string fileName)
Definition: VRP_Concorde.h:663
int UtilScaleDblToIntArr(const int arrLen, const double *arrDbl, int *arrInt, const double oneDbl, int *oneInt, const double epstol=UtilEpsilon)
double * tmpDblNOrigE
Definition: VRP_Concorde.h:96
void setExpandedCost(const double *origGraphCost)
Definition: VRP_Concorde.h:201