Robust optimization approach for a chance-constrained binary knapsack problem

Cited 8 time in webofscience Cited 0 time in scopus
  • Hit : 386
  • Download : 0
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.
Publisher
SPRINGER
Issue Date
2016-05
Language
English
Article Type
Article
Citation

MATHEMATICAL PROGRAMMING, v.157, no.1, pp.277 - 296

ISSN
0025-5610
DOI
10.1007/s10107-015-0931-0
URI
http://hdl.handle.net/10203/209843
Appears in Collection
IE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 8 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0