In this paper, we introduce a technique to enhance the computational efficiency of solution algorithms for high-dimensional discrete simulation-based optimization problems. The technique is based on innovative adaptive partitioning strategies that partition the feasible region using solutions that has already been simulated as well as prior knowledge of the problem of interesting. We integrate the proposed strategies with the Empirical Stochastic Branch-and-Bound framework proposed by Xu and Nelson (2013). This combination leads to a general-purpose discrete simulation-based optimization algorithm that is both globally convergent and has good small sample (finite-time) performance. The proposed general-purpose discrete simulation-based optimization algorithm is validated on a synthetic discrete simulation-based optimization problem and is then used to address a real-world car-sharing fleet assignment problem. Experiment results show that the proposed strategy can increase the algorithm efficiency significantly.
翻译:在本文中,我们引入了一种提高高维离散模拟优化问题解决方案算法计算效率的技术,该技术基于创新的适应性分割战略,利用已经模拟的解决方案以及先前对有趣问题的了解,将可行区域分割开来;我们将拟议战略与许和纳尔逊(2013年)提出的“EmpiricalStochastic 分支和组合框架”相结合;这一组合导致一种通用的离散模拟优化算法,既全球趋同,又具有极小的样本(定期)性能;拟议的普通用途离散模拟优化算法,根据合成离散模拟优化问题加以验证,然后用于解决真实世界汽车共享车队分配问题;实验结果表明,拟议的战略可以大大提高算法效率。