VRP_CVRPsep.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef VRP_CVRPSEP_INCLUDED
00014 #define VRP_CVRPSEP_INCLUDED
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include "cnstrmgr.h"
00024 #include "capsep.h"
00025
00026
00027 #include "VRP_GSECCut.h"
00028 #include "VRP_Instance.h"
00029
00030
00031
00032 class CVRPsep_LPSol {
00033 public:
00034 int nEdges;
00035 double * EdgeX;
00036 int * EdgeTail;
00037 int * EdgeHead;
00038
00039 public:
00040 CVRPsep_LPSol() :
00041 nEdges (0),
00042 EdgeX (0),
00043 EdgeTail(0),
00044 EdgeHead(0)
00045 {};
00046
00047 void clear(){
00048 UTIL_DELARR(EdgeX);
00049 UTIL_DELARR(EdgeTail);
00050 UTIL_DELARR(EdgeHead);
00051 }
00052
00053 void init(const int n){
00054 nEdges = n;
00055 if(nEdges > 0){
00056 clear();
00057 EdgeX = new double[nEdges+1];
00058 EdgeTail = new int[nEdges+1];
00059 EdgeHead = new int[nEdges+1];
00060 CoinAssertHint(EdgeX && EdgeTail && EdgeHead, "Error: Out of Memory");
00061 EdgeX[0] = 0.0;
00062 EdgeTail[0] = 0;
00063 EdgeHead[0] = 0;
00064 }
00065 }
00066
00067 ~CVRPsep_LPSol()
00068 {
00069 clear();
00070 };
00071 };
00072
00073
00074
00075
00076
00077 class VRP_CVRPsep {
00078 public:
00079 const VRP_Instance * m_vrp;
00080 CVRPsep_LPSol m_lpSol;
00081 CnstrMgrPointer m_newCuts;
00082 CnstrMgrPointer m_oldCuts;
00083
00084
00085 public:
00086 VRP_CVRPsep(const int maxCuts = 500) :
00087 m_vrp (0),
00088 m_lpSol (),
00089 m_newCuts (),
00090 m_oldCuts ()
00091 {
00092 CMGR_CreateCMgr(&m_newCuts, maxCuts);
00093 CMGR_CreateCMgr(&m_oldCuts, 10*maxCuts);
00094 }
00095 ~VRP_CVRPsep() {
00096 CMGR_FreeMemCMgr(&m_newCuts);
00097 CMGR_FreeMemCMgr(&m_oldCuts);
00098 }
00099
00100 public:
00101
00103 void init(const VRP_Instance * vrp) {
00104 m_vrp = vrp;
00105
00106 }
00107
00108
00109 void buildLpSol(const double * x,
00110 const int nNzs,
00111 const double etol = 1.0e-8){
00112 int e;
00113 int ind = 1;
00114 int nEdges = m_vrp->m_graphLib.n_edges;
00115 int nVerts = m_vrp->m_graphLib.n_vertices;
00116
00117
00118
00119
00120
00121
00122
00123
00124 m_lpSol.init(nNzs);
00125 for(e = 0; e < nEdges; e++){
00126 if(x[e] > etol){
00127 pair<int,int> uv = UtilBothEndsU(e);
00128
00129
00130
00131
00132
00133
00134
00135 m_lpSol.EdgeX[ind] = x[e];
00136 m_lpSol.EdgeTail[ind]
00137 = uv.second == 0 ? nVerts : uv.second;
00138 m_lpSol.EdgeHead[ind]
00139 = uv.first == 0 ? nVerts : uv.first;
00140 #if 0
00141 printf("XLP[%d,%d -> %d,%d] = %g\n",
00142 uv.first, uv.second,
00143 m_lpSol.EdgeTail[ind],
00144 m_lpSol.EdgeHead[ind], x[e]);
00145 UTIL_DEBUG(m_appParam.Log, 5,
00146 (*m_osLog) << "XLP[" << uv.first << "," << uv.second;
00147 (*m_osLog) << " -> " << m_lpSol.EdgeTail[ind] << ",";
00148 (*m_osLog) << m_lpSol.EdgeHead[ind] << "]";
00149 (*m_osLog) << " = " << x[e] << endl;
00150 );
00151 #endif
00152 assert(ind <= nNzs);
00153 ind++;
00154 }
00155 }
00156 }
00157
00158
00159
00160 int sepCapacityCuts(const int maxCuts = 500){
00161
00162 const UtilGraphLib & graphLib = m_vrp->m_graphLib;
00163 const int nVerts = graphLib.n_vertices;
00164 const int * demand = graphLib.vertex_wt;
00165 const int capacity = graphLib.capacity;
00166
00167
00168
00169
00170
00171
00172 char IntegerAndFeasible;
00173 double MaxViolation;
00174
00175 m_newCuts->Size = 0;
00176 CAPSEP_SeparateCapCuts(nVerts - 1,
00177 const_cast<int*>(demand),
00178 capacity,
00179 m_lpSol.nEdges,
00180 m_lpSol.EdgeTail,
00181 m_lpSol.EdgeHead,
00182 m_lpSol.EdgeX,
00183 m_oldCuts,
00184 maxCuts,
00185 0.001,
00186 &IntegerAndFeasible,
00187 &MaxViolation,
00188 m_newCuts);
00189 #if 0
00190 printf("Found %d capacity cuts. MaxViolation=%g\n",
00191 m_newCuts->Size, MaxViolation);
00192 #endif
00193 return m_newCuts->Size;
00194 }
00195
00196
00197 void createVrpCuts(DecompCutList & newCuts){
00198 int i, j;
00199 const UtilGraphLib & graphLib = m_vrp->m_graphLib;
00200 const int nVerts = graphLib.n_vertices;
00201 const int * demand = graphLib.vertex_wt;
00202 const int capacity = graphLib.capacity;
00203
00204
00205 for(i = 0; i < m_newCuts->Size; i++){
00206 CnstrPointer CP = m_newCuts->CPL[i];
00207
00208 switch(CP->CType){
00209 case CMGR_CT_CAP:
00210 {
00211 dynamic_bitset<> inS(nVerts);
00212 for(j = 1; j <= CP->IntListSize; j++){
00213 if(CP->IntList[j] == nVerts)
00214 inS.set(0);
00215 else
00216 inS.set(CP->IntList[j]);
00217 }
00218 VRP_GSECCut * cut = new VRP_GSECCut(inS, demand, capacity);
00219
00220
00221 double ub = cut->getUpperBound();
00222
00223
00224 assert(UtilIsZero(CP->RHS - ub));
00225 newCuts.push_back(cut);
00226 }
00227 break;
00228 default:
00229 CoinAssert(0);
00230 }
00231 }
00232
00233
00234
00235
00236
00237
00238
00239
00240 for(i = 0; i < m_newCuts->Size; i++)
00241 CMGR_MoveCnstr(m_newCuts, m_oldCuts, i, 0);
00242
00243
00244 }
00245 };
00246
00247 #endif