Evolutionary bi-objective optimization for the dynamic chance-constrained knapsack problem based on tail bound objectives

Simple item page
dc.contributor.authorAssimi, H.
dc.contributor.authorHarper, O.
dc.contributor.authorXie, Y.
dc.contributor.authorNeumann, A.
dc.contributor.authorNeumann, F.
dc.contributor.conference24th European Conference on Artificial Intelligence (ECAI) (29 Aug 2020 - 8 Sep 2020 : Santiago de Compostela, Spain)
dc.contributor.editorGiacomo, G.D.
dc.contributor.editorCatalá, A.
dc.contributor.editorDilkina, B.
dc.contributor.editorMilano, M.
dc.contributor.editorBarro, S.
dc.contributor.editorBugarín, A.
dc.contributor.editorLang, J.
dc.date.issued2020
dc.description.abstractReal-world combinatorial optimization problems are often stochastic and dynamic. Therefore, it is essential to make optimal and reliable decisions with a holistic approach. In this paper, we consider the dynamic chance-constrained knapsack problem where the weight of each item is stochastic, the capacity constraint changes dynamically over time, and the objective is to maximize the total profit subject to the probability that total weight exceeds the capacity. We make use of prominent tail inequalities such as Chebyshev’s inequality, and Chernoff bound to approximate the probabilistic constraint. Our key contribution is to introduce an additional objective which estimates the minimal capacity bound for a given stochastic solution that still meets the chance constraint. This objective helps to cater for dynamic changes to the stochastic problem. We apply single- and multi-objective evolutionary algorithms to the problem and show how bi-objective optimization can help to deal with dynamic chance-constrained problems.
dc.description.statementofresponsibilityHirad Assimi, Oscar Harper, Yue Xie, Aneta Neumann and Frank Neumann
dc.identifier.citationInternational Journal of Computer Research, 2020 / Giacomo, G.D., Catalá, A., Dilkina, B., Milano, M., Barro, S., Bugarín, A., Lang, J. (ed./s), vol.325, pp.307-314
dc.identifier.doi10.3233/FAIA200107
dc.identifier.isbn9781643681009
dc.identifier.issn0922-6389
dc.identifier.issn1879-8314
dc.identifier.orcidAssimi, H. [0000-0002-0548-2921]
dc.identifier.orcidXie, Y. [0000-0002-7959-4563]
dc.identifier.orcidNeumann, A. [0000-0002-0036-4782]
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttp://hdl.handle.net/2440/128270
dc.language.isoen
dc.publisherIOS Press BV
dc.publisher.placeAmsterdam, Netherlands
dc.relation.granthttp://purl.org/au-research/grants/arc/DP160102401
dc.relation.ispartofseriesFrontiers in Artificial Intelligence and Applications; 325
dc.rights© 2020 The authors and IOS Press. This article is published online with Open Access by IOS Press and distributed under the terms of the Creative Commons Attribution Non-Commercial License 4.0 (CC BY-NC 4.0).
dc.source.urihttp://ebooks.iospress.nl/doi/10.3233/FAIA325
dc.titleEvolutionary bi-objective optimization for the dynamic chance-constrained knapsack problem based on tail bound objectives
dc.typeConference paper
pubs.publication-statusPublished

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
hdl_128270.pdf
Size:
283.79 KB
Format:
Adobe Portable Document Format
Description:
Published version
Download

Collections

Computer Science publications