Optimal budget allocation policy for tabu search in stochastic simulation optimization. (February 2023)

• Record Type: Journal Article
• Authors: Yu, Chunlong; Lahrichi, Nadia; Matta, Andrea
• Is Part Of: Computers & operations research. Volume 150(2023)
• Publication Date: 2023-02
• Subjects: Metaheuristics -- Simulation optimization -- Tabu search -- Optimal computing budget allocation -- Ranking and selection; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106046
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Tabu search (TS) is a powerful method for solving combinatorial optimization problems. However, when TS is adopted for stochastic simulation optimization, the simulation noises may mislead the search direction and prevent TS from converging to high-quality solutions. This issue can be mitigated by increasing the number of simulation samples used for solution evaluation, however, real-world applications are generally constrained by a finite computing budget. Therefore, it is critical to reducing the noise effect by an efficient simulation budget allocation, i.e., splitting the total number of samples on solutions. Studies on the budget allocation problem of TS are sparse. Most of the works employ equal allocation or simple policies which are not optimal. Based on the large deviations framework, we propose a new budget allocation policy to enhance the performance of TS under stochastic settings. The proposed allocation policy, provided in closed-form formulas, is asymptotically optimal for maximizing the probability that TS performs the correct move in a single iteration. The efficiency of the proposed method is validated by solving different problems from manufacturing and healthcare scenarios, including an inventory control problem, a throughput maximization problem for the production line, and a physician scheduling problem for the radiotherapy center. The numerical results show that, with the proposed method, TS can obtain better results using the same amount of computational efforts. Highlights: Tabu search is misled by simulation noises in stochastic optimization problems. We study the budget allocation problem to mitigate the misleading effect. An asymptotically optimal budget allocation policy is proposed. The proposed policy is given in closed-form formulas and thus easy to use. The proposed policy enhances the search efficiency in real-world problems.