Integer-Ordered Simulation Optimization using R-SPLINE: Retrospective Search using Piecewise-Linear Interpolation and Neighborhood Enumeration. Wang, H., Pasupathy, R., & Schmeiser, B. W. *ACM TOMACS*, 23(3), 2013.

Paper doi abstract bibtex

Paper doi abstract bibtex

We consider simulation-optimization (SO) models where the decision variables are integer ordered and the objective function is defined implicitly via a simulation oracle, which for any feasible solution can be called to compute a point estimate of the objective-function value. We develop R-SPLINE—a Retrospective-search algorithm that alternates between a continuous Search using Piecewise-Linear Interpolation and a discrete Neighborhood Enumeration, to asymptotically identify a local minimum. R-SPLINE appears to be among the first few gradient-based search algorithms tailored for solving integer-ordered local SO problems. In addition to proving the almost-sure convergence of R-SPLINE?s iterates to the set of local minima, we demonstrate that the probability of R-SPLINE returning a solution outside the set of true local minima decays exponentially in a certain precise sense. R-SPLINE, with no parameter tuning, compares favorably with popular existing algorithms.

@article{2013wanpassch, author = {H. Wang and R. Pasupathy and B. W. Schmeiser}, title = {Integer-Ordered Simulation Optimization using {R-SPLINE}: Retrospective Search using Piecewise-Linear Interpolation and Neighborhood Enumeration}, journal = {ACM TOMACS}, year = {2013}, volume = {23}, number = {3}, pages = {}, doi = {10.1145/2499913.2499916}, url = {http://web.ics.purdue.edu/~pasupath/PAPERS/2013wanpassch.pdf}, keywords = {retrospective approximation, simulation optimization on integer-ordered spaces}, abstract = {We consider simulation-optimization (SO) models where the decision variables are integer ordered and the objective function is defined implicitly via a simulation oracle, which for any feasible solution can be called to compute a point estimate of the objective-function value. We develop R-SPLINE---a Retrospective-search algorithm that alternates between a continuous Search using Piecewise-Linear Interpolation and a discrete Neighborhood Enumeration, to asymptotically identify a local minimum. R-SPLINE appears to be among the first few gradient-based search algorithms tailored for solving integer-ordered local SO problems. In addition to proving the almost-sure convergence of R-SPLINE?s iterates to the set of local minima, we demonstrate that the probability of R-SPLINE returning a solution outside the set of true local minima decays exponentially in a certain precise sense. R-SPLINE, with no parameter tuning, compares favorably with popular existing algorithms.}}

Downloads: 0

{"_id":{"_str":"5342a5ef0e946d920a00232e"},"__v":1,"authorIDs":["2LsNCSfcuCHZ2bwwk","34rFneKbNhk4MTKFS","3GdCmHtparmeFqq3f","3XoF8DfqJsYFoDYhe","3vW8cvryNS2mm2jBM","4QjGv7n8jm6s54wNw","4WE9bofLYdCkqGsGd","4Y8czGNHCDwAq5yDH","4o9qwLRCQY4absaEb","4teGyL2jzd7wNLJxY","5456dd008b01c8193000000b","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":["Wang, H.","Pasupathy, R.","Schmeiser, B. W."],"bibbaseid":"wang-pasupathy-schmeiser-integerorderedsimulationoptimizationusingrsplineretrospectivesearchusingpiecewiselinearinterpolationandneighborhoodenumeration-2013","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["H."],"propositions":[],"lastnames":["Wang"],"suffixes":[]},{"firstnames":["R."],"propositions":[],"lastnames":["Pasupathy"],"suffixes":[]},{"firstnames":["B.","W."],"propositions":[],"lastnames":["Schmeiser"],"suffixes":[]}],"title":"Integer-Ordered Simulation Optimization using R-SPLINE: Retrospective Search using Piecewise-Linear Interpolation and Neighborhood Enumeration","journal":"ACM TOMACS","year":"2013","volume":"23","number":"3","pages":"","doi":"10.1145/2499913.2499916","url":"http://web.ics.purdue.edu/~pasupath/PAPERS/2013wanpassch.pdf","keywords":"retrospective approximation, simulation optimization on integer-ordered spaces","abstract":"We consider simulation-optimization (SO) models where the decision variables are integer ordered and the objective function is defined implicitly via a simulation oracle, which for any feasible solution can be called to compute a point estimate of the objective-function value. We develop R-SPLINE—a Retrospective-search algorithm that alternates between a continuous Search using Piecewise-Linear Interpolation and a discrete Neighborhood Enumeration, to asymptotically identify a local minimum. R-SPLINE appears to be among the first few gradient-based search algorithms tailored for solving integer-ordered local SO problems. In addition to proving the almost-sure convergence of R-SPLINE?s iterates to the set of local minima, we demonstrate that the probability of R-SPLINE returning a solution outside the set of true local minima decays exponentially in a certain precise sense. R-SPLINE, with no parameter tuning, compares favorably with popular existing algorithms.","bibtex":"@article{2013wanpassch,\n\tauthor = {H. Wang and R. Pasupathy and B. W. Schmeiser},\n\ttitle = {Integer-Ordered Simulation Optimization using {R-SPLINE}: Retrospective Search using Piecewise-Linear \tInterpolation and Neighborhood Enumeration},\n\tjournal = {ACM TOMACS},\n\tyear = {2013},\n\tvolume = {23},\n\tnumber = {3},\n\tpages = {},\n\tdoi = {10.1145/2499913.2499916},\n\turl = {http://web.ics.purdue.edu/~pasupath/PAPERS/2013wanpassch.pdf},\n\tkeywords = {retrospective approximation, simulation optimization on integer-ordered spaces},\n\tabstract = {We consider simulation-optimization (SO) models where the decision variables are integer ordered and the objective function is defined implicitly via a simulation oracle, which for any feasible solution can be called to compute a point estimate of the objective-function value. We develop R-SPLINE---a Retrospective-search algorithm that alternates between a continuous Search using Piecewise-Linear Interpolation and a discrete Neighborhood Enumeration, to asymptotically identify a local minimum. R-SPLINE appears to be among the first few gradient-based search algorithms tailored for solving integer-ordered local SO problems. In addition to proving the almost-sure convergence of R-SPLINE?s iterates to the set of local minima, we demonstrate that the probability of R-SPLINE returning a solution outside the set of true local minima decays exponentially in a certain precise sense. R-SPLINE, with no parameter tuning, compares favorably with popular existing algorithms.}}\n\n","author_short":["Wang, H.","Pasupathy, R.","Schmeiser, B. W."],"key":"2013wanpassch","id":"2013wanpassch","bibbaseid":"wang-pasupathy-schmeiser-integerorderedsimulationoptimizationusingrsplineretrospectivesearchusingpiecewiselinearinterpolationandneighborhoodenumeration-2013","role":"author","urls":{"Paper":"http://web.ics.purdue.edu/~pasupath/PAPERS/2013wanpassch.pdf"},"keyword":["retrospective approximation","simulation optimization on integer-ordered spaces"],"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":91,"keywords":["retrospective approximation","simulation optimization on integer-ordered spaces"],"search_terms":["integer","ordered","simulation","optimization","using","spline","retrospective","search","using","piecewise","linear","interpolation","neighborhood","enumeration","wang","pasupathy","schmeiser"],"title":"Integer-Ordered Simulation Optimization using R-SPLINE: Retrospective Search using Piecewise-Linear Interpolation and Neighborhood Enumeration","year":2013,"dataSources":["qnbhPCpdghcXAQgXA"]}