Stochastically constrained ranking and selection via SCORE. Pasupathy, R., Hunter, S. R., Pujowidianto, N. A., Lee, L. H., & Chen, C. *ACM Transactions on Modeling and Computer Simulation*, 25(1):1–26, 2014.

Link Paper doi abstract bibtex

Link Paper doi abstract bibtex

Consider the context of constrained simulation optimization (SO), that is, optimization problems where the objective and constraint functions are known through dependent Monte Carlo estimators. For solving such problems on large finite spaces, we provide an easily implemented sampling framework called SCORE (Sampling Criteria for Optimization using Rate Estimators) that approximates the optimal simulation budget allocation. We develop a general theory, but like much of the existing literature on ranking and selection, our focus is on SO problems where the distribution of the simulation observations is Gaussian. We first characterize the nature of the optimal simulation budget as a bilevel optimization problem. We then show that under a certain asymptotic limit, the solution to the bilevel optimization problem becomes surprisingly tractable and is expressed through a single intuitive measure, the score. We provide an iterative SO algorithm that repeatedly estimates the score and determines how the available simulation budget should be expended across contending systems. Numerical experience with the algorithm resulting from the proposed sampling approximation is very encouraging — in numerous examples of constrained SO problems having 1,000 to 10,000 systems, the optimal allocation is identified to negligible error within a few seconds to one minute on a typical laptop computer. Corresponding times to solve the full bilevel optimization problem range from tens of minutes to several hours.

@article{2014pashunetal, Year = {2014}, Author = {R. Pasupathy and S. R. Hunter and N. A. Pujowidianto and L. H. Lee and {C.-H.} Chen}, Title = {Stochastically constrained ranking and selection via {SCORE}}, Journal = {ACM Transactions on Modeling and Computer Simulation}, shortjournal = {ACM Trans. Model. Comput. Simul.}, volume = {25}, number = {1}, articleno = {1}, pages = {1--26}, numpages = {26}, doi = {10.1145/2630066}, url_Link = {http://dx.doi.org/10.1145/2630066}, url_Paper = {http://web.ics.purdue.edu/~pasupath/PAPERS/2014pashunpujleeche.pdf}, keywords = {ranking and selection, optimal allocation, constrained simulation optimization}, abstract = {Consider the context of constrained simulation optimization (SO), that is, optimization problems where the objective and constraint functions are known through dependent Monte Carlo estimators. For solving such problems on large finite spaces, we provide an easily implemented sampling framework called SCORE (Sampling Criteria for Optimization using Rate Estimators) that approximates the optimal simulation budget allocation. We develop a general theory, but like much of the existing literature on ranking and selection, our focus is on SO problems where the distribution of the simulation observations is Gaussian. We first characterize the nature of the optimal simulation budget as a bilevel optimization problem. We then show that under a certain asymptotic limit, the solution to the bilevel optimization problem becomes surprisingly tractable and is expressed through a single intuitive measure, the score. We provide an iterative SO algorithm that repeatedly estimates the score and determines how the available simulation budget should be expended across contending systems. Numerical experience with the algorithm resulting from the proposed sampling approximation is very encouraging --- in numerous examples of constrained SO problems having 1,000 to 10,000 systems, the optimal allocation is identified to negligible error within a few seconds to one minute on a typical laptop computer. Corresponding times to solve the full bilevel optimization problem range from tens of minutes to several hours.}} %bibbase_note = {<span style="color: green">Journal version, Finalist, WSC Best Theoretical Paper Award.</span>}} %addendum = {(Journal version, \textbf{Finalist, WSC Best Theoretical Paper Award}.)}}

Downloads: 0

{"_id":{"_str":"5342a5ef0e946d920a002335"},"__v":210,"authorIDs":["2LsNCSfcuCHZ2bwwk","34rFneKbNhk4MTKFS","3GdCmHtparmeFqq3f","3XoF8DfqJsYFoDYhe","3vW8cvryNS2mm2jBM","4QjGv7n8jm6s54wNw","4WE9bofLYdCkqGsGd","4Y8czGNHCDwAq5yDH","4o9qwLRCQY4absaEb","4teGyL2jzd7wNLJxY","5456dd008b01c8193000000b","545708a08b01c81930000130","5PuuuqCvjCG9cLtzL","5de6d25fabd988de010000a8","5de6e251abd988de010001f3","5de704a645c10edf0100004c","5de7296e97054edf010000d6","5de8368c8cf0fbde01000040","5de851c68ff138de0100001e","5de8f925d5dfa2e00100000d","5de90676d5dfa2e0010000f5","5de9107dd5dfa2e0010001cc","5de95707d574c6de010000bd","5de99b3d59feb7f201000123","5dea64fdddb5e6df0100021a","5deaaf6303c11ade01000148","5ded8dc85fefb3de010000d9","5dedb465e47c43de0100001c","5dee71ac773914de010001ef","5deebb5c0ddb85de01000107","5def1e4cc5ae39f201000194","5def3576e83f7dde01000105","5deff7c414db5cdf0100016f","5df0601be4ce32df0100009e","5df1ecff78da84de01000082","5df20e7fe4cb4ede010000fd","5df42a559d2522de0100012f","5df4756c95416ade0100009f","5df4f25dfc47dbde01000133","5df53020fd245cde0100005d","5df55da3ff5784de01000147","5df5b606a0eab8de01000156","5df7ab64f3cb28df010001b4","5df81fa9d74ee7df01000168","5dfaf58bfa2bbbde010000e1","5dfb5859012925de01000066","5dfb7ea1c2820bdf01000107","5dfba59a749b8bde01000164","5dfbba9ff6f0aede01000124","5dfbfbffb371afde0100001f","5dfc6b1c4a82f3f201000004","5dfccc4f7a3608de0100009d","5dfd1b69ece35ede01000054","5dfd2a23ece35ede01000153","5dfdbb97cdf7c8de010000ef","5dfeeccf5dd8e7df01000085","5e001ed39292b5de010000a9","5e014c336afa18de0100004e","5e0181a6aa04bede01000042","5e044485705486df0100006a","5e04e4fffff612df0100002c","5e056c974b4c94de010000cb","5e05fd62e95bcdde01000022","5e0661287da1d1de0100020a","5e06d44aa0810cde01000093","5e06e1232eda19df01000042","5e075d62764d8ede0100009a","5e080c67cdee3adf01000097","5e08b0dc7dc1dcdf010000a0","5e08dfebcbe70cdf0100006a","5e096462ade67ddf01000016","5e0993db83a3f3de01000090","5e0a0cfb52fbd9de0100001e","5e0a59cace3ebce4010000df","5e0abafa27625ede0100003c","5e0bb52d94c532f301000024","5e0e587dac7d11df01000058","5e0eb12103f891de0100003a","5e1241abc196d3de0100011f","5e134506697554de01000003","5e14ed2cb46f1bdf0100001b","5e15043db46f1bdf0100017c","5e151bb588b10dde0100012b","5e161f09f67f7dde010007cf","5e177d85cf35a4de010000b9","5e192771eaca22df01000017","5e1a17149fbdddde01000024","5e1bd6e44c869ade01000001","5e1c697192587bde01000068","5e1cb74c7723aadf0100017a","5e1d0c1bfeb115df01000001","5e1d3fbc6b18c4df01000102","5e1d8fd93a6d8cde01000178","5e1db3f2d9acfbde010001eb","5e1dc7bb8d71ddde0100013c","5e1dcbbc8d71ddde01000185","5e1e1aeef6dca7f20100013c","5e1e20fdf6dca7f2010001c2","5e1e40cb407a20de01000268","5e1e575b2e41a7de0100013a","5e1e9865bedb58de01000021","5e1f259007379ade0100004b","5e1f4b899ddd0fde01000120","5e1f6ef1e8f5ddde010001bf","5e1ffff214d3c9de01000149","5e2038f302c04cde01000171","5e20a682bdda1fde0100018e","5e20b0485c2065de01000038","5e20dcf1b46c27ee01000122","5e217c6fc7842fde010000b3","5e221fab71dcf8df01000057","5e24e2250e3b0adf01000062","5e250bef2e79a1f2010000e8","5e25c8aaf299d4de01000161","5e25ef17a6f19fde01000276","5e262dba24c8a6de01000036","5e27467118178ede0100002a","5e27b689328b80de0100001a","5e27c523328b80de010000c5","5e28f86441639df301000062","5e29a547fed3e7df01000142","5e2b5bcf6366e2df0100008d","5e2d212d4e7fefde01000048","5e2e568627ce0ade01000051","5e2f89e248b7a4df010000f4","5e3022e57e0df1de01000156","5e302e8546a666df01000050","5e303c8446a666df010001d3","5e30560f57a222df0100012c","5e30cdb02a1e4bde010001d6","5e31fdc67c8d24df0100012c","5e324bfee45eb5df010000bb","5e325105e45eb5df010000f7","5e32d6ed150c84df0100006e","5e32f849c1389bde01000165","5e3443860c807ede010000d1","5e3478d6fae8b9de0100007b","5e385c05ccda85de01000180","5e38773d1f8af9e00100013b","5e388b69030bcadf01000092","5e389cc2030bcadf010001ed","5e38a43d645ed2de01000060","5e38d7b781a46ade01000001","5e3acde7f2a00cdf010001b9","5e3ad6221b85fadf01000051","5e3b0f63ba2e16df0100004a","5e3b83b3184d6ede01000073","5e3b912f184d6ede01000120","5e3c247a34cd37de0100001c","5e3c2eb034cd37de010000e7","5e3cf9fead8243de010000a6","5e3d8eee96e576de010001d1","5e3da0c7f33211df010000ec","5e3dabd9f33211df010001af","5e3dbf3d07ca74de01000102","5e3e13304cdb49de0100008d","5e3e4358018e1dde01000039","5e3f4a5377baf5df010000b6","5e3f532ccd8fe2de01000001","5e42d01be7fe39df010001a5","5e43071baefe1adf01000186","5e434e7ba37866de01000044","5e435ceda37866de010000f8","5e437511b5e412df010000c5","5e43915e639a35de010000cd","5e442947e5a34dde01000029","5e447260084293df01000128","5e448fabec14b3de010000ee","5e44b42430d0bbde0100011f","5e44d347ab9cedde01000015","5e44f43303c52dde01000046","5e44fc2f03c52dde010000ad","5e450b26501a51de0100001c","5e452d6c605639de0100005d","5e4553aca96575df01000165","5e45b9970920e8de0100007b","5e46186fb57382df010000b5","5e46b3888573d1de0100004a","5e49689916841dde010000dd","5e4a03d6cc11a8df01000061","5e4afb99332a9bde0100002c","5e4b486aa44fbbde01000111","5e4bf4df8f0677df01000199","5e4d795d08a8e5de01000194","5e4dab1de671efde010001a5","5e4dc50d682c99de010000bb","5e4e08e9cc196bde010001c3","5e4ea5b564b624de010000e1","5e4f0a6ee5389bde01000022","5e5015c0933046de010000cc","5e5027418c3a2cde01000035","5e545c8488d190df010000c0","5e556b2be11ab9df01000025","5e5603c9819fabdf01000079","5e568bddeb2916df01000115","5e574023bf9f82de010000e0","5e57cb565d5d52de0100012b","5e594017e60e02de010001c9","5e596f1e56d60ade0100018f","5e5a89cfb6725cde010000be","5e5b519474a3e7df0100012d","5e5c359d15d8f5de010000e8","5e5d77a30b73f6de010000d0","5e5dc297c64f0ede01000002","5e5dd063c64f0ede010000a8","5e5e48b0d3955dde01000174","5e5e5c6a5f9e7bee0100011e","5e5fd7f66b32b0f20100021d","5e600b0e13e3aede010001b0","5e602266c064fcde01000264","5e6271e111ac5fde010001e0","5e6579926e5f4cf30100007c","5e66a24e44d2c4de010001f6","5e66b95f4b4a62de01000121","5e6a95dd0e8744de010001aa","5e6b5628e9cf32de010000f0","5eukLewyvtHJ4WPT7","6hj49bCTP57FjutjL","82gBBwyJR2WCNWPWm","9k3X5crnHa5xJ4p7a","AjG6eiMp43eKLk2Yx","BPGmMaEX9pHFcwzrs","BSbB972EuqxRSxK4q","BWawN4hTNFAWjMjHQ","BZn4si3dP7J3H9fky","CcADyySGr39q8rimi","DWYv3xvTzwq9KAjDp","EiCaXco5a7djZngEx","Ey3dnH6u8SFBZSrRS","FCNTJyX4Y757fHDmf","FfpBpZgrPK6GzWzg8","FzE5MgxndyPuqq7uj","GSGoyxizKMrQAYfq7","GguCXKi2NxMS4tNph","KNeor84tRiAGBckxK","KQqLGaFRpAbpBskBQ","KYEFo9TJpP86AhCAr","Lshk7Ffyqph79sBSC","MaifQ9BJT2ed2dZGQ","N5tWeDGAZb5gWkkDp","NBqzAQnD3yAHrJ2xc","NFgFx8pEH8SSsBfeY","NxFbiZ5KXwcqamDsn","NzNpe39Q5DnjHYfXH","Pi7yiWLLHLXG3nQKS","QMz9YsqYMv2FxcrWR","QSqaE2cp2FrPiQW4N","QipRTRhBEJbKr5r5p","QmEqPPCm3CYaeT5sz","RLeConBCygYyJYFjZ","RPFzPgD6mGvvLYagB","RSP7HPs5tD2qvcieu","RZHiDpYi8b2SNKWvW","ReXQXH2CdCDw8CGSa","Ro9bQKrb6shDGMAdv","S6MinMfG29rqRYQA9","SPqCLTdy73wgYcnQq","SSd2xTrkAZtytoyza","SbxH6ZekW7syy7bRy","TSvwARqENambxnPrm","WMvuyWXseWigM3xmR","WPh2SBoox3kFYreuv","WTEpbvXWYyWaLP9fR","WohTL5e4xTKvafcgZ","Xeza9s8dXbXYpiXCF","XgT4w8FQ9GkEwKs4Z","XzSrze7ZA49N8pPiY","Y8f8mN4haHr8RLSHq","YyuePc45BLAbaHYSe","ZA852k8x6E2z78EKG","ZJW3AoAJebLMWuP9e","ZTLzLyaEuYkvrihhG","ZiczJGfQdyYQNodsx","akaiiw9kM3uc3g9w4","avF2hdaGEEAM98DSX","bSLBYQaQ4kKqoatFw","cKdmzfYuhRo469Bmu","cbXkRN6TDnPYEdaDq","cqdiSz7b8NGALu2r4","e5xB5BgjaDsiWNQeH","eJqK7mmamEkYP724x","fDmXj9dfDwJtywS4R","gBzw4TZeaZBiEMuny","giqfvfiFYi6bvnnYB","gjSfEPLukj5tbToTD","gwjZBg4y7YxprKrod","gyB9wdPsiWhZuZB3S","hTJtzpXBRfPtLyahg","hmidXFcMyt4C4yn94","iM2mYTcCiHBmRAkRe","iMRnJkytnZJMAAc5f","iSkAFqqy6ZM5z8rcD","ibBdNBZw79ekcSBLz","kABfYsS38CsgdWfcc","kGiCdK6hwjbt8zbpY","kLrFsm9XJzWKg94Xc","kdYcvNWv7ejC7aRke","kdxhy7dNM6Y7BsmSt","kiejYFiwMiTdLPpLi","mLG769TSC6Nx5jet3","nuLZLT2mGTSaZk8Hn","nzzoR37EXqhbC6wYS","o4GjXhX2JeFovdSwH","oPjFKW9xzDcb2aF6h","p372M7LbgPjAtHFe6","pE86fXX97JPRkRXmh","pnEa7DuEQ8Coe3Cwn","q2GhjiCM95xxsoAgZ","rJJizDq9EQ4nD8vMT","sR38HmZ7bsXuAMSmu","sYCtfEdGGjCWxezsx","t7AdsRiupiQQhetS5","tQXNeq3DmxAYj4iaG","tbirRndbLp4maBSzS","tgCg2KndQiSxduqXp","tkXbW9FMr4dBv2psC","trzPWfze2ysu27QGQ","tupoFJpu7aySR9uR4","ui4w4B9v2H2KfZ36g","uwSXdm9fgEkS8wvhv","vTPqfZG5YeBngrebd","vYnLp8Qk499SgMHX3","vaMBFQq5rkSWq8HoR","vpgPj5ZqG4QWDWBgq","wfXprfNd5cxAnbJqa","x6FX2icxtLjmxSsEM","xededTNbkQkcnyzkK","xreej3aHEdqNvyrTk","y867chrGxEuu8ZsWR","yNwK2BcFRaZ5zdKmA","yTKirEsJv57GFkDEa","zErqDaNgwPAAmXaZ9","za8HG9n7wYCafScuE"],"author_short":["Pasupathy, R.","Hunter, S. R.","Pujowidianto, N. A.","Lee, L. H.","Chen, C."],"bibbaseid":"pasupathy-hunter-pujowidianto-lee-chen-stochasticallyconstrainedrankingandselectionviascore-2014","bibdata":{"bibtype":"article","type":"article","year":"2014","author":[{"firstnames":["R."],"propositions":[],"lastnames":["Pasupathy"],"suffixes":[]},{"firstnames":["S.","R."],"propositions":[],"lastnames":["Hunter"],"suffixes":[]},{"firstnames":["N.","A."],"propositions":[],"lastnames":["Pujowidianto"],"suffixes":[]},{"firstnames":["L.","H."],"propositions":[],"lastnames":["Lee"],"suffixes":[]},{"firstnames":["C.-H."],"propositions":[],"lastnames":["Chen"],"suffixes":[]}],"title":"Stochastically constrained ranking and selection via SCORE","journal":"ACM Transactions on Modeling and Computer Simulation","shortjournal":"ACM Trans. Model. Comput. Simul.","volume":"25","number":"1","articleno":"1","pages":"1–26","numpages":"26","doi":"10.1145/2630066","url_link":"http://dx.doi.org/10.1145/2630066","url_paper":"http://web.ics.purdue.edu/~pasupath/PAPERS/2014pashunpujleeche.pdf","keywords":"ranking and selection, optimal allocation, constrained simulation optimization","abstract":"Consider the context of constrained simulation optimization (SO), that is, optimization problems where the objective and constraint functions are known through dependent Monte Carlo estimators. For solving such problems on large finite spaces, we provide an easily implemented sampling framework called SCORE (Sampling Criteria for Optimization using Rate Estimators) that approximates the optimal simulation budget allocation. We develop a general theory, but like much of the existing literature on ranking and selection, our focus is on SO problems where the distribution of the simulation observations is Gaussian. We first characterize the nature of the optimal simulation budget as a bilevel optimization problem. We then show that under a certain asymptotic limit, the solution to the bilevel optimization problem becomes surprisingly tractable and is expressed through a single intuitive measure, the score. We provide an iterative SO algorithm that repeatedly estimates the score and determines how the available simulation budget should be expended across contending systems. Numerical experience with the algorithm resulting from the proposed sampling approximation is very encouraging — in numerous examples of constrained SO problems having 1,000 to 10,000 systems, the optimal allocation is identified to negligible error within a few seconds to one minute on a typical laptop computer. Corresponding times to solve the full bilevel optimization problem range from tens of minutes to several hours.","bibtex":"@article{2014pashunetal,\n\tYear = {2014},\n\tAuthor = {R. Pasupathy and S. R. Hunter and N. A. Pujowidianto and L. H. Lee and {C.-H.} Chen},\n\tTitle = {Stochastically constrained ranking and selection via {SCORE}},\n\tJournal = {ACM Transactions on Modeling and Computer Simulation},\n\tshortjournal = {ACM Trans. Model. Comput. Simul.},\n\tvolume = {25},\n\tnumber = {1},\n\tarticleno = {1},\n\tpages = {1--26},\n\tnumpages = {26},\n\tdoi = {10.1145/2630066},\n\turl_Link = {http://dx.doi.org/10.1145/2630066},\n\turl_Paper = {http://web.ics.purdue.edu/~pasupath/PAPERS/2014pashunpujleeche.pdf},\n\tkeywords = {ranking and selection, optimal allocation, constrained simulation optimization},\n\tabstract = {Consider the context of constrained simulation optimization (SO), that is, optimization problems where the objective and constraint functions are known through dependent Monte Carlo estimators. For solving such problems on large finite spaces, we provide an easily implemented sampling framework called SCORE (Sampling Criteria for Optimization using Rate Estimators) that approximates the optimal simulation budget allocation. We develop a general theory, but like much of the existing literature on ranking and selection, our focus is on SO problems where the distribution of the simulation observations is Gaussian. We first characterize the nature of the optimal simulation budget as a bilevel optimization problem. We then show that under a certain asymptotic limit, the solution to the bilevel optimization problem becomes surprisingly tractable and is expressed through a single intuitive measure, the score. We provide an iterative SO algorithm that repeatedly estimates the score and determines how the available simulation budget should be expended across contending systems. Numerical experience with the algorithm resulting from the proposed sampling approximation is very encouraging --- in numerous examples of constrained SO problems having 1,000 to 10,000 systems, the optimal allocation is identified to negligible error within a few seconds to one minute on a typical laptop computer. Corresponding times to solve the full bilevel optimization problem range from tens of minutes to several hours.}}\n\t%bibbase_note = {<span style=\"color: green\">Journal version, Finalist, WSC Best Theoretical Paper Award.</span>}}\n\t%addendum = {(Journal version, \\textbf{Finalist, WSC Best Theoretical Paper Award}.)}}\n\n","author_short":["Pasupathy, R.","Hunter, S. R.","Pujowidianto, N. A.","Lee, L. H.","Chen, C."],"key":"2014pashunetal","id":"2014pashunetal","bibbaseid":"pasupathy-hunter-pujowidianto-lee-chen-stochasticallyconstrainedrankingandselectionviascore-2014","role":"author","urls":{" link":"http://dx.doi.org/10.1145/2630066"," paper":"http://web.ics.purdue.edu/~pasupath/PAPERS/2014pashunpujleeche.pdf"},"keyword":["ranking and selection","optimal allocation","constrained simulation optimization"],"metadata":{"authorlinks":{"pasupathy, r":"https://bibbase.org/show?bib=http://web.ics.purdue.edu/~pasupath/rpVitapublist.bib"}},"html":""},"bibtype":"article","biburl":"http://web.ics.purdue.edu/~pasupath/rpVitapublist.bib","downloads":182,"keywords":["ranking and selection","optimal allocation","constrained simulation optimization"],"search_terms":["stochastically","constrained","ranking","selection","via","score","pasupathy","hunter","pujowidianto","lee","chen"],"title":"Stochastically constrained ranking and selection via SCORE","year":2014,"dataSources":["qnbhPCpdghcXAQgXA"]}