Abstract:

Chance-Constrained Multi-Choice Knapsack Problem （CCMCKP） is a class of NP-hard combinatorial optimization problems with important practical applications. However， there is a lack of research on the solution methods for this problem. The first framework for solving CCMCKP was proposed for this problem， and two solution methods were established based on this framework， including the dynamic programming-based method RA-DP and the genetic algorithm-based method RA-IGA. RA-DP is an exact method with optimality guarantee， but it can only solve small-scale problem instances within a time budget of 1 hour. In contrast， RA-IGA is an approximation method with better scalability. Simulation experimental results verify the performance of the proposed methods. On small-scale problem instances， both RA-DP and RA-IGA can find the optimal solutions. On the medium- and large-scale problem instances， RA-IGA exhibits significantly higher efficiency than RA-DP， always obtaining feasible solutions quickly within 1 hour. In future research on CCMCKP， RA-DP and RA-IGA can be considered as baseline methods， and the benchmark set considered in this work can also be used as a standard benchmark test set.

Key words: combinatorial optimization problem, Chance-Constrained Multi-Choice Knapsack Problem (CCMCKP), Genetic Algorithm (GA), dynamic programming, exact algorithm, approximation algorithm

摘要：

机会约束的多选择背包问题（CCMCKP）是一类具有重要应用价值的NP难组合优化问题，但目前还缺乏关于该问题求解方法的专门研究。为此，提出首个CCMCKP的求解框架，并基于该框架构建了两种求解方法：基于动态规划的RA-DP和基于遗传算法的RA-IGA。RA-DP是精确求解方法，具有最优性保证，但是在可接受的时间（1 h）内仅能求解小规模问题样例；相较而言，RA-IGA是近似求解方法，具有更好的可扩放性。仿真实验结果验证了所提求解方法的性能：在小规模问题样例上，RA-DP和RA-IGA都可以找到最优解；在中大规模问题样例上，RA-IGA表现出了比RA-DP显著更高的求解效率，它总是可以在给定时间（1 h）内快速获得可行解。在CCMCKP的后续研究中，RA?DP和RA-IGA可作为基准对比方法，而实验工作中所构建的测试样例集可作为该问题的标准测试集。

关键词: 组合优化问题, 机会约束的多选择背包问题, 遗传算法, 动态规划, 精确算法, 近似算法