Robust optimization approach for a chance-constrained binary knapsack problem

• 成果类型: Article
• 署名作者: Han, Jinil; Lee, Kyungsik; Lee, Chungmok; Choi, Ki-Seok; Park, Sungsoo
• 署名单位: Universite Catholique Louvain; Korea Advanced Institute of Science & Technology (KAIST); Seoul National University (SNU); Seoul National University (SNU); Hankuk University Foreign Studies
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0931-0
• 发表日期: 2016
• 页码: 277-296
• 关键词: exact algorithms; price

摘要

We consider a certain class of chance-constrained binary knapsack problem where each item has a normally distributed random weight that is independent of the other items. For this problem we propose an efficient pseudo-polynomial time algorithm based on the robust optimization approach for finding a solution with a theoretical bound on the probability of satisfying the knapsack constraint. Our algorithm is tested on a wide range of random instances, and the results demonstrate that it provides qualified solutions quickly. In contrast, a state-of-the-art MIP solver is only applicable for instances of the problem with a restricted number of items.