00001
00015 #include "OSDipBlockBearcatSolver.h"
00016 #include "OSErrorClass.h"
00017 #include "OSDataStructures.h"
00018
00019 #include <sstream>
00020 using std::ostringstream;
00021
00022
00023
00024
00025 OSDipBlockBearcatSolver::OSDipBlockBearcatSolver():
00026 m_osinstance(NULL) {
00027 std::cout << "INSIDE OSDipBlockBearcatSolver CONSTRUCTOR" << std::endl;
00028 }
00029
00030
00031 OSDipBlockBearcatSolver::OSDipBlockBearcatSolver( OSInstance *osinstance, OSOption *osoption) {
00032 std::cout << "INSIDE OSDipBlockBearcatSolver CONSTRUCTOR" << std::endl;
00033 std::cout << "whichBlock = " << m_whichBlock<< std::endl;
00034 try{
00035 m_osinstance = osinstance;
00036 m_numberOfVar = m_osinstance->getVariableNumber();
00037
00038 m_osoption = osoption;
00039
00040 m_demand = NULL;
00041 m_u = NULL;
00042 m_v = NULL;
00043 m_g = NULL;
00044 m_px = NULL;
00045 m_tx =NULL;
00046 m_varIdx = NULL;
00047
00048
00049 std::vector<SolverOption*> solverOptions;
00050 std::vector<SolverOption*>::iterator vit;
00051 std::vector<int >demand;
00052
00053
00054 solverOptions = m_osoption->getSolverOptions("Dip");
00055
00056
00057 int tmpVal;
00058
00059 for (vit = solverOptions.begin(); vit != solverOptions.end(); vit++) {
00060
00061
00062
00063
00064
00065
00066
00067 if( (*vit)->name.find("numHubs") != std::string::npos){
00068
00069 std::istringstream buffer( (*vit)->value);
00070 buffer >> m_numHubs;
00071 std::cout << "numHubs = " << m_numHubs << std::endl;
00072
00073 }else{
00074
00075 if((*vit)->name.find("numNodes") != std::string::npos){
00076
00077 std::istringstream buffer( (*vit)->value);
00078 buffer >> m_numNodes;
00079 std::cout << "numNodes = " << m_numNodes << std::endl;
00080
00081 }else{
00082 if((*vit)->name.find("totalDemand") != std::string::npos){
00083
00084 std::istringstream buffer( (*vit)->value);
00085 buffer >> m_totalDemand;
00086 std::cout << "m_totalDemand = " << m_totalDemand << std::endl;
00087
00088 }else{
00089 if((*vit)->name.find("minDemand") != std::string::npos){
00090
00091 std::istringstream buffer( (*vit)->value);
00092 buffer >> m_minDemand;
00093 std::cout << "m_minDemand = " << m_minDemand << std::endl;
00094
00095 }else{
00096 if( (*vit)->name.find("demand") != std::string::npos ){
00097
00098 std::istringstream buffer( (*vit)->value);
00099 buffer >> tmpVal;
00100 demand.push_back( tmpVal);
00101
00102
00103 }
00104 }
00105 }
00106 }
00107 }
00108
00109 }
00110
00111
00112 m_demand = new int[ m_numNodes];
00113
00114 m_varIdx = new int[ m_numNodes];
00115
00116 m_u = new double*[ m_numNodes];
00117 m_v = new double*[ m_numNodes];
00118 m_g = new double*[ m_numNodes];
00119
00120 m_px = new int*[ m_numNodes];
00121 m_tx = new int*[ m_numNodes];
00122
00123 if(m_numNodes != (int)demand.size( ) ) throw ErrorClass("inconsistent number of demand nodes");
00124 int i;
00125 for (i = 0; i < m_numNodes; i++) {
00126
00127 m_demand[ i] = demand[i];
00128 m_u[ i] = new double[ m_totalDemand + 1];
00129 m_v[ i] = new double[ m_totalDemand + 1];
00130 m_g[ i] = new double[ m_numNodes];
00131
00132 m_px[ i] = new int[ m_totalDemand + 1];
00133 m_tx[ i] = new int[ m_totalDemand + 1];
00134
00135
00136 }
00137
00138
00139 } catch (const ErrorClass& eclass) {
00140
00141 throw ErrorClass(eclass.errormsg);
00142
00143 }
00144
00145 }
00146
00147 OSDipBlockBearcatSolver::~OSDipBlockBearcatSolver(){
00148
00149 std::cout << "INSIDE ~OSDipBlockBearcatSolver()" << std::endl;
00150
00151
00152 std::vector<IndexValuePair*>::iterator vit;
00153
00154 for (vit = m_primalVals.begin(); vit != m_primalVals.end(); vit++) {
00155
00156 delete *vit;
00157 }
00158
00159
00160 int i;
00161
00162 for(i = 0; i < m_numNodes; i++){
00163
00164 delete[] m_u[i];
00165 m_u[i] = NULL;
00166
00167 delete[] m_v[i];
00168 m_v[i] = NULL;
00169
00170 delete[] m_g[i];
00171 m_g[i] = NULL;
00172
00173 delete[] m_px[i];
00174 m_px[i] = NULL;
00175
00176 delete[] m_tx[i];
00177 m_tx[i] = NULL;
00178 }
00179
00180 delete[] m_u;
00181 m_u= NULL;
00182
00183 delete[] m_v;
00184 m_v= NULL;
00185
00186 delete[] m_g;
00187 m_g= NULL;
00188
00189 delete[] m_px;
00190 m_px= NULL;
00191
00192 delete[] m_tx;
00193 m_tx= NULL;
00194
00195
00196
00197 if(m_demand != NULL) delete[] m_demand;
00198
00199 if(m_varIdx != NULL) delete[] m_varIdx;
00200
00201 }
00202
00203 void OSDipBlockBearcatSolver::solve(double *cost, std::vector<IndexValuePair*> *solIndexValPair, double *optVal){
00204
00205 try{
00206
00207 int i;
00208
00209
00210
00211 struct IndexValuePair *primalValPair;
00212
00213 std::vector<IndexValuePair*>::iterator vit;
00214
00215 for (vit = m_primalVals.begin(); vit != m_primalVals.end(); vit++) {
00216
00217 delete *vit;
00218 }
00219 m_primalVals.clear();
00220
00221
00222
00223
00224 *optVal = OSDBL_MAX;
00225
00226
00227
00228 int l ;
00229
00230 int bestl;
00231 int kountVar;
00232 double testVal;
00233
00234 for(l = m_minDemand; l <= m_totalDemand; l++){
00235
00236 testVal = qrouteCost(m_whichBlock, l, cost, &kountVar);
00237 if( testVal < *optVal){
00238 *optVal = testVal;
00239 bestl = l;
00240 }
00241
00242
00243
00244 }
00245
00246 *optVal = qrouteCost(m_whichBlock, bestl, cost, &kountVar);
00247 std::cout << "best reduced cost = " << *optVal << std::endl;
00248
00249 std::map<int, int> indexCount;
00250
00251 std::map<int, int>::iterator mit;
00252
00253
00254 for(i = 0; i < kountVar; i++){
00255
00256 if( indexCount.find( m_varIdx[ i]) == indexCount.end() ){
00257
00258 indexCount[ m_varIdx[ i]] = 1;
00259
00260 }else{
00261
00262 indexCount[ m_varIdx[ i]] += 1;
00263
00264 }
00265
00266
00267 }
00268
00269 for (mit = indexCount.begin(); mit != indexCount.end(); mit++){
00270
00271
00272
00273
00274
00275
00276 primalValPair = new IndexValuePair();
00277
00278 primalValPair->value = mit->second;
00279 primalValPair->idx = mit->first;
00280
00281
00282 m_primalVals.push_back( primalValPair);
00283 }
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304 *solIndexValPair = m_primalVals;
00305
00306
00307 } catch (const ErrorClass& eclass) {
00308
00309 throw ErrorClass(eclass.errormsg);
00310
00311 }
00312
00313 }
00314
00315
00316 void OSDipBlockBearcatSolver::solve(double *cost, std::string *osrl){
00317
00318
00319 try{
00320
00321
00322 } catch (const ErrorClass& eclass) {
00323
00324 throw ErrorClass(eclass.errormsg);
00325
00326 }
00327
00328 }
00329
00330
00331
00332 double OSDipBlockBearcatSolver::qrouteCost(const int& k, const int& l, double* c, int* kountVar){
00333
00334
00335
00336
00337 double rcost;
00338 rcost = OSDBL_MAX;
00339
00340
00341
00342
00343
00344 int startPnt = (l - 1)*(m_numNodes*m_numNodes - m_numNodes);
00345 c+= startPnt ;
00346
00347 *kountVar = 0;
00348 int bestLastNode = 0;
00349 int i;
00350 int j;
00351 int l1;
00352 int l2;
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366 for(i = m_numHubs; i < m_numNodes; i++){
00367
00368
00369 for(l1 = m_minDemand; l1 <= l; l1++){
00370
00371 m_u[i][l1] = OSDBL_MAX;
00372 m_v[i][l1] = OSDBL_MAX;
00373
00374 if(l1 == *(m_demand + i) ){
00375
00376 m_px[i][l1] = k;
00377
00378
00379 m_u[i][l1] = *(c + k*(m_numNodes - 1) + i - 1);
00380
00381
00382 }
00383 }
00384 }
00385
00386
00387
00388
00389 if(l == m_minDemand){
00390
00391 for(i = m_numHubs; i < m_numNodes; i++){
00392
00393
00394 if( m_u[i][l] + *(c + i*(m_numNodes-1) + k ) < rcost){
00395
00396 rcost = m_u[i][l] + *(c + i*(m_numNodes-1) + k );
00397
00398
00399
00400
00401
00402 bestLastNode = i;
00403 }
00404
00405 }
00406
00407
00408
00409 *(m_varIdx + (*kountVar)++) = startPnt + bestLastNode*(m_numNodes - 1) + k ;
00410 *(m_varIdx + (*kountVar)++) = startPnt + k*(m_numNodes - 1) + bestLastNode - 1;
00411
00412
00413 return rcost;
00414 }
00415
00416
00417
00418
00419
00420
00421 int lowerVal = m_minDemand + 1;
00422 for(l2 = lowerVal; l2 <= l; l2++){
00423
00424 for(i = m_numHubs; i < m_numNodes; i++) {
00425
00426
00427 if( *(m_demand + i) < l2 ){
00428
00429 for(j = m_numHubs; j < i; j++){
00430
00431
00432
00433
00434 l1 = l2 - *(m_demand + i);
00435
00436 if( m_px[j][ l1 ] != i ){
00437
00438
00439 m_g[j][i] = m_u[ j][ l1 ] + *(c + j*(m_numNodes-1) + i - 1) ;
00440
00441
00442
00443
00444 }else{
00445
00446 m_g[j][i] = m_v[ j][ l1] + *(c + j*(m_numNodes-1) + i - 1) ;
00447
00448
00449
00450 }
00451
00452
00453
00454 if(m_g[j][i] < m_u[i][l2] ){
00455
00456 m_u[i][l2] = m_g[j][i];
00457 m_px[i][l2] = j;
00458
00459 }
00460
00461
00462
00463 }
00464
00465
00466 for(j = i + 1; j < m_numNodes; j++){
00467
00468
00469
00470 l1 = l2 - *(m_demand + i);
00471
00472 if( m_px[j][ l1 ] != i ){
00473
00474
00475 m_g[j][i] = m_u[ j][ l1 ] + *(c + j*(m_numNodes-1) + i ) ;
00476
00477
00478 }else{
00479
00480 m_g[j][i] = m_v[ j][ l1] + *(c + j*(m_numNodes-1) + i ) ;
00481
00482 }
00483
00484
00485
00486 if(m_g[j][i] < m_u[i][l2] ){
00487
00488 m_u[i][l2] = m_g[j][i];
00489 m_px[i][l2] = j;
00490
00491 }
00492
00493
00494 }
00495
00496
00497
00498
00499
00500 for(j =m_numHubs; j < m_numNodes; j++){
00501
00502 if(j != i){
00503
00504 if( (m_g[j][i] < m_v[i][l2] ) && (m_px[i][l2] != j) ){
00505
00506
00507
00508 m_v[i][l2] = m_g[j][i];
00509 m_tx[i][l2] = j;
00510
00511
00512 }
00513
00514 }
00515
00516
00517 }
00518
00519
00520 if(l2 == l ){
00521
00522 if( m_u[i][l2] + *(c + i*(m_numNodes-1) + k ) < rcost){
00523
00524 rcost = m_u[i][l2] + *(c + i*(m_numNodes-1) + k );
00525
00526 bestLastNode = i;
00527 }
00528
00529 }
00530
00531
00532 }
00533
00534
00535 }
00536
00537
00538 }
00539
00540
00541
00542
00543
00544
00545 int currentNode;
00546 int successorNode;
00547 int lvalue;
00548
00549
00550
00551
00552
00553
00554
00555 *(m_varIdx + (*kountVar)++) = startPnt + bestLastNode*(m_numNodes - 1) + k ;
00556
00557
00558
00559
00560
00561 successorNode = k;
00562 currentNode = bestLastNode;
00563
00564 lvalue = l ;
00565
00566
00567 while(currentNode != k){
00568
00569
00570 if( m_px[ currentNode][ lvalue ] != successorNode){
00571
00572
00573
00574
00575 successorNode = currentNode;
00576 currentNode = m_px[ currentNode][ lvalue ];
00577
00578
00579 if(currentNode - successorNode > 0){
00580
00581 *(m_varIdx + (*kountVar)++) = startPnt + currentNode*(m_numNodes - 1) + successorNode;
00582
00583 }else{
00584
00585 *(m_varIdx + (*kountVar)++) = startPnt + currentNode*(m_numNodes - 1) + successorNode - 1 ;
00586
00587 }
00588
00589
00590 }else{
00591
00592
00593
00594 successorNode = currentNode;
00595 currentNode = m_tx[ currentNode][ lvalue ];
00596
00597 if(currentNode - successorNode > 0){
00598
00599 *(m_varIdx + (*kountVar)++) = startPnt + currentNode*(m_numNodes - 1) + successorNode;
00600
00601 }else{
00602
00603 *(m_varIdx + (*kountVar)++) = startPnt + currentNode*(m_numNodes - 1) + successorNode - 1 ;
00604
00605 }
00606
00607 }
00608
00609
00610 lvalue = lvalue - *(m_demand + successorNode);
00611
00612
00613
00614 }
00615
00616
00617
00618
00619
00620
00621
00622
00623 return rcost;
00624
00625 }
00626