From: <qua...@us...> - 2009-04-20 08:41:28
|
Revision: 194 http://rmol.svn.sourceforge.net/rmol/?rev=194&view=rev Author: quannaus Date: 2009-04-20 08:41:24 +0000 (Mon, 20 Apr 2009) Log Message: ----------- Implemented the optimal bid-price vector computation within the Monte-Carlo algorithm. Modified Paths: -------------- trunk/rmol/rmol/RMOL_Service.hpp trunk/rmol/rmol/bom/BucketHolder.cpp trunk/rmol/rmol/bom/BucketHolder.hpp trunk/rmol/rmol/bom/MCOptimiser.cpp trunk/rmol/rmol/bom/MCOptimiser.hpp trunk/rmol/rmol/command/Optimiser.cpp trunk/rmol/rmol/command/Optimiser.hpp trunk/rmol/rmol/service/RMOL_Service.cpp trunk/rmol/test/OptimiseTestSuite.cpp Added Paths: ----------- trunk/rmol/test/samples/ trunk/rmol/test/samples/sample1.csv trunk/rmol/test/samples/sample2.csv trunk/rmol/test/samples/sample3.csv trunk/rmol/test/samples/sample4.csv Removed Paths: ------------- trunk/rmol/test/sample1.csv trunk/rmol/test/sample2.csv trunk/rmol/test/sample3.csv trunk/rmol/test/sample4.csv Property Changed: ---------------- trunk/rmol/ trunk/rmol/config/ Property changes on: trunk/rmol ___________________________________________________________________ Modified: svn:ignore - autom4te.cache INSTALL Makefile Makefile.in aclocal.m4 config.log config.status configure libtool rmol-config rmol-html-doc-0.*.0.tar.bz2 rmol-html-doc-0.*.0.tar.gz rmol.pc rmol.m4 rmol.spec config.guess config.h config.h.in config.sub configure.log rmol-0.*.0.tar.bz2 rmol-0.*.0.tar.gz stamp-h1 + autom4te.cache INSTALL Makefile Makefile.in aclocal.m4 config.log config.status configure libtool rmol-config rmol-html-doc-0.*.0.tar.bz2 rmol-html-doc-0.*.0.tar.gz rmol.pc rmol.m4 rmol.spec config.guess config.h config.h.in config.sub configure.log rmol-0.*.0.tar.bz2 rmol-0.*.0.tar.gz stamp-h1 mytest Property changes on: trunk/rmol/config ___________________________________________________________________ Modified: svn:ignore - config.guess config.sub depcomp install-sh ltmain.sh mdate-sh missing texinfo.tex codeset.m4 gettext.m4 glibc21.m4 iconv.m4 intdiv0.m4 intmax.m4 inttypes-pri.m4 inttypes.m4 inttypes_h.m4 isc-posix.m4 lcmessage.m4 lib-ld.m4 lib-link.m4 lib-prefix.m4 longdouble.m4 longlong.m4 mkinstalldirs nls.m4 po.m4 printf-posix.m4 progtest.m4 signed.m4 size_max.m4 stdint_h.m4 uintmax_t.m4 ulonglong.m4 wchar_t.m4 wint_t.m4 xsize.m4 + config.guess config.sub depcomp install-sh ltmain.sh mdate-sh missing texinfo.tex codeset.m4 gettext.m4 glibc21.m4 iconv.m4 intdiv0.m4 intmax.m4 inttypes-pri.m4 inttypes.m4 inttypes_h.m4 isc-posix.m4 lcmessage.m4 lib-ld.m4 lib-link.m4 lib-prefix.m4 longdouble.m4 longlong.m4 mkinstalldirs nls.m4 po.m4 printf-posix.m4 progtest.m4 signed.m4 size_max.m4 stdint_h.m4 uintmax_t.m4 ulonglong.m4 wchar_t.m4 wint_t.m4 xsize.m4 libtool.m4 lt~obsolete.m4 ltsugar.m4 ltversion.m4 ltoptions.m4 Modified: trunk/rmol/rmol/RMOL_Service.hpp =================================================================== --- trunk/rmol/rmol/RMOL_Service.hpp 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/rmol/RMOL_Service.hpp 2009-04-20 08:41:24 UTC (rev 194) @@ -36,6 +36,7 @@ /** Single resource optimization that uses Monte-Carlo algorithm and returns a vector of cumulated booking limits. */ void optimalOptimisationByMCIntegration (const int K, + BidPriceVector_T&, BookingLimitVector_T&); /** Single resource optimization using dynamic programming. */ @@ -57,14 +58,14 @@ /** Single resource optimization that uses EMSR-a heuristic and returns a vector of cumulated booking limits. */ - void heuristicOptimisationByEmsrA (BookingLimitVector_T&); + void heuristicOptimisationByEmsrA (BidPriceVector_T&, BookingLimitVector_T&); /** Single resource optimization using EMSR-b heuristic. */ void heuristicOptimisationByEmsrB (); /** Single resource optimization that uses EMSR-b heuristic and returns a vector of cumulated booking limits. */ - void heuristicOptimisationByEmsrB (BookingLimitVector_T&); + void heuristicOptimisationByEmsrB (BidPriceVector_T&, BookingLimitVector_T&); private: /** Default Constructors. */ Modified: trunk/rmol/rmol/bom/BucketHolder.cpp =================================================================== --- trunk/rmol/rmol/bom/BucketHolder.cpp 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/rmol/bom/BucketHolder.cpp 2009-04-20 08:41:24 UTC (rev 194) @@ -151,6 +151,22 @@ } // ////////////////////////////////////////////////////////////////////// + const double BucketHolder::getPreviousCumulatedProtection () const { + // Get the cumulated protection of the previous bucket. If the + // current bucket is the first one, the function returns 0.0 + if (_itCurrentBucket == _bucketList.begin()) { + return 0.0; + } else { + BucketList_T::iterator itPreviousBucket = _itCurrentBucket; + --itPreviousBucket; + Bucket* lPreviousBucket_ptr = *itPreviousBucket; + const double oPreviousCumulatedProtection = + lPreviousBucket_ptr->getCumulatedProtection(); + return oPreviousCumulatedProtection; + } + } + + // ////////////////////////////////////////////////////////////////////// void BucketHolder::calculateMeanDemandAndOptimalRevenue () { _totalMeanDemand = 0.0; _optimalRevenue = 0.0; Modified: trunk/rmol/rmol/bom/BucketHolder.hpp =================================================================== --- trunk/rmol/rmol/bom/BucketHolder.hpp 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/rmol/bom/BucketHolder.hpp 2009-04-20 08:41:24 UTC (rev 194) @@ -43,6 +43,10 @@ /** Get the size of list of buckets/classes. */ const short getSize () const; + /** Get the cumulated protection of the previous bucket. If the + current bucket is the first one, the function returns 0.0. */ + const double getPreviousCumulatedProtection () const; + /** Fill up the vector of cumulated booking limits. */ void fillup (BookingLimitVector_T&) const; Modified: trunk/rmol/rmol/bom/MCOptimiser.cpp =================================================================== --- trunk/rmol/rmol/bom/MCOptimiser.cpp 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/rmol/bom/MCOptimiser.cpp 2009-04-20 08:41:24 UTC (rev 194) @@ -21,9 +21,10 @@ // ////////////////////////////////////////////////////////////////////// void MCOptimiser:: optimalOptimisationByMCIntegration(const int K, - const ResourceCapacity_T iCabinCapacity, - BucketHolder& ioBucketHolder, - PartialSumHolderHolder& ioPSHolderHolder){ + const ResourceCapacity_T iCabinCapacity, + BucketHolder& ioBucketHolder, + PartialSumHolderHolder& ioPSHolderHolder, + BidPriceVector_T& ioBidPriceVector){ // Retrieve the BucketHolder // BucketHolder& ioBucketHolder = ioResource.getBucketHolder(); @@ -55,8 +56,9 @@ ioPSHolderHolder.iterate(); int Kj = K; int lj = 0; - for (short j=1 ; j <= nbOfClasses - 1; - j++, ioBucketHolder.iterate(), ioPSHolderHolder.iterate()) { + const int cabinCapacityInt = static_cast<int> (iCabinCapacity); + for (short j = 1 ; j <= nbOfClasses - 1; + ++j, ioBucketHolder.iterate(), ioPSHolderHolder.iterate()) { /** Retrieve Bucket(j) (current) and Bucket(j+1) (next). */ Bucket& currentBucket = ioBucketHolder.getCurrentBucket(); Bucket& nextBucket = ioBucketHolder.getNextBucket(); @@ -83,9 +85,9 @@ VariateList_T aVariateList; PartialSumHolder& previousPartialSumList = - ioPSHolderHolder.getPreviousPartialSumHolder(); + ioPSHolderHolder.getPreviousPartialSumHolder(); PartialSumHolder& currentPartialSumList = - ioPSHolderHolder.getCurrentPartialSumHolder(); + ioPSHolderHolder.getCurrentPartialSumHolder(); currentPartialSumList.initSize (Kj); for (int k=1; k <= Kj; k++) { const double djk = gaussianDemandGenerator.generateVariate(); @@ -142,9 +144,6 @@ /** Consistency check. */ assert (lj >= 1 && lj < Kj); - /** Update Kj for the next loop. */ - Kj = Kj - lj; - /** The optimal protection is defined as: y(j) = 1/2 [S(j,lj) + S(j, lj+1)] @@ -161,6 +160,37 @@ // Set the cumulated protection for Bucket(j) (j ranging from 1 to n-1) currentBucket.setCumulatedProtection (yj); + /** Compute the Bid-Price (Opportunity Cost) at index x + (capacity) for x between y(j-1) et y(j). This OC can be + proven to be equal to p(j)*Proba(D1+...+Dk>=x | D1 > y1, + D1+D2 > y2, ..., D1+...+D(k-1) > y(k-1)). */ + + // Get the previous cumulated protection y(j-1). + const double yjm1 = ioBucketHolder.getPreviousCumulatedProtection (); + const int yjm1int = static_cast<int> (yjm1); + const int yjint = static_cast<int> (yj); + int currentIndex = 0; + double currentPartialSum = + currentPartialSumList.getPartialSum (currentIndex); + int x = 0; + + for (x = yjm1int + 1; x <= yjint && x <= cabinCapacityInt; ++x) { + while (currentPartialSum < x) { + ++currentIndex; + if (currentIndex < Kj) { + currentPartialSum = + currentPartialSumList.getPartialSum (currentIndex); + } else { + currentPartialSum = x; + } + } + const double bidPriceAtX = pj * (Kj - currentIndex) / Kj; + ioBidPriceVector.push_back (bidPriceAtX); + } + + /** Update Kj for the next loop. */ + Kj = Kj - lj; + /** S'(j,k) = S(j,k). <br>The previousPartialSumList (S') now becomes equal to the currentPartialSumList (S) (by iteration on ioPSHolderHolder). */ @@ -170,6 +200,61 @@ Bucket& currentBucket = ioBucketHolder.getCurrentBucket(); currentBucket.setCumulatedProtection (iCabinCapacity); + /** Compute the Bid-Price (Opportunity Cost) at index x + (capacity) for x between y(n-1) et cabin capacity. This OC can be + proven to be equal to p(n)*Proba(D1+...+Dn>=x | D1 > y1, + D1+D2 > y2, ..., D1+...+D(n-1) > y(n-1)). */ + + // Get the previous cumulated protection y(n-1). + const double ynm1 = ioBucketHolder.getPreviousCumulatedProtection (); + + if (ynm1 < iCabinCapacity) { + // STEP 1. + const FldDistributionParameters& aDistribParams = + currentBucket.getDistributionParameters(); + const Gaussian gaussianDemandGenerator (aDistribParams); + + VariateList_T aVariateList; + + PartialSumHolder& previousPartialSumList = + ioPSHolderHolder.getPreviousPartialSumHolder(); + PartialSumHolder& currentPartialSumList = + ioPSHolderHolder.getCurrentPartialSumHolder(); + currentPartialSumList.initSize (Kj); + + for (int k = 1; k <= Kj; ++k) { + const double djk = gaussianDemandGenerator.generateVariate(); + aVariateList.push_back (djk); + + const double spjm1lpk = + previousPartialSumList.getPartialSum (lj + k - 1); + const double sjk = spjm1lpk + djk; + currentPartialSumList.addPartialSum (sjk); + } + + // STEP 2. + currentPartialSumList.sort (); + + const int ynm1int = static_cast<int> (ynm1); + const double pn = currentBucket.getAverageYield(); + int currentIndex = 0; + double currentPartialSum = + currentPartialSumList.getPartialSum (currentIndex); + for (int x = ynm1int + 1; x <= cabinCapacityInt; ++x) { + while (currentPartialSum < x) { + ++currentIndex; + if (currentIndex < Kj) { + currentPartialSum = + currentPartialSumList.getPartialSum (currentIndex); + } else { + currentPartialSum = x; + } + } + const double bidPriceAtX = pn * (Kj - currentIndex) / Kj; + ioBidPriceVector.push_back (bidPriceAtX); + } + } + /** Re-calculate the values (protections, bkg limits and cumulated booking limits, the optimal revenue. Modified: trunk/rmol/rmol/bom/MCOptimiser.hpp =================================================================== --- trunk/rmol/rmol/bom/MCOptimiser.hpp 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/rmol/bom/MCOptimiser.hpp 2009-04-20 08:41:24 UTC (rev 194) @@ -31,9 +31,10 @@ overbooking. */ static void optimalOptimisationByMCIntegration (const int K, - const ResourceCapacity_T, - BucketHolder&, - PartialSumHolderHolder&); + const ResourceCapacity_T, + BucketHolder&, + PartialSumHolderHolder&, + BidPriceVector_T&); }; } #endif // __RMOL_BOM_MCUTILS_HPP Modified: trunk/rmol/rmol/command/Optimiser.cpp =================================================================== --- trunk/rmol/rmol/command/Optimiser.cpp 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/rmol/command/Optimiser.cpp 2009-04-20 08:41:24 UTC (rev 194) @@ -26,8 +26,9 @@ // ////////////////////////////////////////////////////////////////////// void Optimiser:: optimalOptimisationByMCIntegration (const int K, - const ResourceCapacity_T iCabinCapacity, - BucketHolder& ioBucketHolder) { + const ResourceCapacity_T iCabinCapacity, + BucketHolder& ioBucketHolder, + BidPriceVector_T& ioBidPriceVector) { // Retrieve the BucketHolder // BucketHolder& ioBucketHolder = ioResource.getBucketHolder(); @@ -44,7 +45,7 @@ Note that n-1 corresponds to the size of the parameter list, i.e., n corresponds to the number of classes/buckets. */ - for (short j=0 ; j <= nbOfClasses - 1; j++) { + for (short j = 0 ; j <= nbOfClasses; ++j) { PartialSumHolder& aPartialSumList = FacPartialSumHolder::instance().create (); @@ -54,8 +55,9 @@ // Call the class performing the actual algorithm MCOptimiser::optimalOptimisationByMCIntegration (K, iCabinCapacity, - ioBucketHolder, - aPartialSumHolderHolder); + ioBucketHolder, + aPartialSumHolderHolder, + ioBidPriceVector); } // ////////////////////////////////////////////////////////////////////// Modified: trunk/rmol/rmol/command/Optimiser.hpp =================================================================== --- trunk/rmol/rmol/command/Optimiser.hpp 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/rmol/command/Optimiser.hpp 2009-04-20 08:41:24 UTC (rev 194) @@ -31,8 +31,9 @@ overbooking. */ static void optimalOptimisationByMCIntegration (const int K, - const ResourceCapacity_T, - BucketHolder&); + const ResourceCapacity_T, + BucketHolder&, + BidPriceVector_T&); /** Dynamic Programming. Modified: trunk/rmol/rmol/service/RMOL_Service.cpp =================================================================== --- trunk/rmol/rmol/service/RMOL_Service.cpp 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/rmol/service/RMOL_Service.cpp 2009-04-20 08:41:24 UTC (rev 194) @@ -82,17 +82,30 @@ const double iCapacity = _rmolServiceContext->getCapacity(); BucketHolder* ioBucketHolder_ptr = _rmolServiceContext->getBucketHolder(); assert (ioBucketHolder_ptr != NULL); + BidPriceVector_T lBidPriceVector; Optimiser::optimalOptimisationByMCIntegration (K, iCapacity, - *ioBucketHolder_ptr); + *ioBucketHolder_ptr, + lBidPriceVector); // DEBUG RMOL_LOG_DEBUG (ioBucketHolder_ptr->display()); + /* + std::cout << "Bid-Price Vector (BPV): "; + unsigned int size = lBidPriceVector.size(); + + for (unsigned int i = 0; i < size; ++i) { + const double bidPrice = lBidPriceVector.at(i); + std::cout << std::fixed << std::setprecision (2) << bidPrice << " "; + } + std::cout << std::endl; + */ } // ////////////////////////////////////////////////////////////////////// void RMOL_Service:: optimalOptimisationByMCIntegration(const int K, + BidPriceVector_T& ioBidPriceVector, BookingLimitVector_T& ioBookingLimitVector){ assert (_rmolServiceContext != NULL); @@ -101,7 +114,8 @@ assert (ioBucketHolder_ptr != NULL); Optimiser::optimalOptimisationByMCIntegration (K, iCapacity, - *ioBucketHolder_ptr); + *ioBucketHolder_ptr, + ioBidPriceVector); // Fill up booking vector ioBucketHolder_ptr->fillup (ioBookingLimitVector); @@ -152,7 +166,7 @@ RMOL_LOG_DEBUG (ioBucketHolder_ptr->display()); // std::cout << "Bid-Price Vector (BPV): "; - unsigned int size = lBidPriceVector.size(); + // unsigned int size = lBidPriceVector.size(); // for (unsigned int i = 0; i < size; ++i) { // const double bidPrice = lBidPriceVector.at(i); @@ -198,7 +212,8 @@ // ////////////////////////////////////////////////////////////////////// void RMOL_Service:: - heuristicOptimisationByEmsrA (BookingLimitVector_T& ioBookingLimitVector) { + heuristicOptimisationByEmsrA (BidPriceVector_T& ioBidPriceVector, + BookingLimitVector_T& ioBookingLimitVector) { assert (_rmolServiceContext != NULL); const double iCapacity = _rmolServiceContext->getCapacity(); BucketHolder* ioBucketHolder_ptr = _rmolServiceContext->getBucketHolder(); @@ -225,7 +240,8 @@ // ////////////////////////////////////////////////////////////////////// void RMOL_Service:: - heuristicOptimisationByEmsrB (BookingLimitVector_T& ioBookingLimitVector) { + heuristicOptimisationByEmsrB (BidPriceVector_T& ioBidPriceVector, + BookingLimitVector_T& ioBookingLimitVector) { assert (_rmolServiceContext != NULL); const double iCapacity = _rmolServiceContext->getCapacity(); BucketHolder* ioBucketHolder_ptr = _rmolServiceContext->getBucketHolder(); Modified: trunk/rmol/test/OptimiseTestSuite.cpp =================================================================== --- trunk/rmol/test/OptimiseTestSuite.cpp 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/test/OptimiseTestSuite.cpp 2009-04-20 08:41:24 UTC (rev 194) @@ -24,11 +24,11 @@ const short METHOD_FLAG = 0; // Cabin Capacity (it must be greater then 100 here) - const double cabinCapacity = 500.0; + const double cabinCapacity = 100.0; // Input file name - const std::string inputFileName ("class.csv"); - const bool hasInputFile = false; + const std::string inputFileName ("samples/sample2.csv"); + const bool hasInputFile = true; // Set the log parameters std::ofstream logOutputFile; Deleted: trunk/rmol/test/sample1.csv =================================================================== --- trunk/rmol/test/sample1.csv 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/test/sample1.csv 2009-04-20 08:41:24 UTC (rev 194) @@ -1,4 +0,0 @@ -price; mean; standard deviation; -100; 20; 9; -70; 45; 12; -42; 80; 16; Deleted: trunk/rmol/test/sample2.csv =================================================================== --- trunk/rmol/test/sample2.csv 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/test/sample2.csv 2009-04-20 08:41:24 UTC (rev 194) @@ -1,6 +0,0 @@ -../../rmol/service/RMOL_Service.cpp:90: 500Class; Price; Mean; Std Dev; Protection; Cum. Protection; Cum. Bkg Limit; -1; 100([2.22507e-308, 100]), upper yield = 100.00; , mean = 20.00; , std_dev = 9.00; , protection = 15.23; , cumulative protection = 15.23; , booking limit = 0.00, cumulative booking limit = 500.00 -2; 70([2.22507e-308, 70]), upper yield = 70.00; , mean = 45.00; , std_dev = 12.00; , protection = 50.57; , cumulative protection = 65.80; , booking limit = 0.00, cumulative booking limit = 484.77 -3; 42([2.22507e-308, 42]), upper yield = 42.00; , mean = 0.00; , std_dev = 0.00; , protection = 434.20; , cumulative protection = 500.00; , booking limit = 0.00, cumulative booking limit = 434.20 -Cabin Capacity = 500; Total Mean Demand = 65; Demand Factor = 0.13; Optimal Revenue = 23299.5 - Deleted: trunk/rmol/test/sample3.csv =================================================================== --- trunk/rmol/test/sample3.csv 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/test/sample3.csv 2009-04-20 08:41:24 UTC (rev 194) @@ -1,5 +0,0 @@ -price; mean; standard deviation; -1050; 17.3; 5.8; -950; 45.1; 15.0; -699; 39.6; 13.2; -520; 34.0; 11.3; Deleted: trunk/rmol/test/sample4.csv =================================================================== --- trunk/rmol/test/sample4.csv 2009-04-02 18:55:23 UTC (rev 193) +++ trunk/rmol/test/sample4.csv 2009-04-20 08:41:24 UTC (rev 194) @@ -1,4 +0,0 @@ -price; mean; standard deviation; -1295; 0; 1; -1250; 8; 2.82843; -1205; 4; 2.82843; Copied: trunk/rmol/test/samples/sample1.csv (from rev 193, trunk/rmol/test/sample1.csv) =================================================================== --- trunk/rmol/test/samples/sample1.csv (rev 0) +++ trunk/rmol/test/samples/sample1.csv 2009-04-20 08:41:24 UTC (rev 194) @@ -0,0 +1,4 @@ +price; mean; standard deviation; +100; 20; 9; +70; 45; 12; +42; 80; 16; Copied: trunk/rmol/test/samples/sample2.csv (from rev 193, trunk/rmol/test/sample2.csv) =================================================================== --- trunk/rmol/test/samples/sample2.csv (rev 0) +++ trunk/rmol/test/samples/sample2.csv 2009-04-20 08:41:24 UTC (rev 194) @@ -0,0 +1,5 @@ +price; mean; standard deviation; +1050; 17.3; 5.8; +567; 45.1; 15.0; +534; 39.6; 13.2; +520; 34.0; 11.3; Copied: trunk/rmol/test/samples/sample3.csv (from rev 193, trunk/rmol/test/sample3.csv) =================================================================== --- trunk/rmol/test/samples/sample3.csv (rev 0) +++ trunk/rmol/test/samples/sample3.csv 2009-04-20 08:41:24 UTC (rev 194) @@ -0,0 +1,5 @@ +price; mean; standard deviation; +1050; 17.3; 5.8; +950; 45.1; 15.0; +699; 39.6; 13.2; +520; 34.0; 11.3; Copied: trunk/rmol/test/samples/sample4.csv (from rev 193, trunk/rmol/test/sample4.csv) =================================================================== --- trunk/rmol/test/samples/sample4.csv (rev 0) +++ trunk/rmol/test/samples/sample4.csv 2009-04-20 08:41:24 UTC (rev 194) @@ -0,0 +1,4 @@ +price; mean; standard deviation; +1295; 0; 1; +1250; 8; 2.82843; +1205; 4; 2.82843; This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |