Online Knapsack Problem with Items Delay

Hajer Ben-Romdhane, Saoussen Krichen

2014

Abstract

We address in this paper a special case of the online knapsack problem (OKP) that considers a number of items arriving sequentially over time without any prior information about their features. As items features are not known in advance but revealed at their arrival, we allow the decision maker to delay his decision about incoming items (to select the current item or reject it) until observing the next ones. The main objective in this problem is to load the best subset of items that maximizes the expected value of the total reward without exceeding the knapsack capacity. The selection process can be stopped before observing all items if the capacity constraint is exhausted. To solve this problem, we propose an exact solution approach that decomposes the original problem dynamically and incorporates a stopping rule in order to decide whether to load or not each new incoming item. We illustrate the proposed approach by numerical experimentations and compare the obtained results for different utility functions using performance measures. We discuss thereafter the effect of the decision maker’s utility function and his readiness to take risks over the final solution.

Paper Citation

in Harvard Style

Ben-Romdhane H. and Krichen S. (2014). Online Knapsack Problem with Items Delay . In Proceedings of the 3rd International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES, ISBN 978-989-758-017-8, pages 213-220. DOI: 10.5220/0004832702130220

in Bibtex Style

@conference{icores14,
author={Hajer Ben-Romdhane and Saoussen Krichen},
title={Online Knapsack Problem with Items Delay},
booktitle={Proceedings of the 3rd International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,},
year={2014},
pages={213-220},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004832702130220},
isbn={978-989-758-017-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 3rd International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,
TI - Online Knapsack Problem with Items Delay
SN - 978-989-758-017-8
AU - Ben-Romdhane H.
AU - Krichen S.
PY - 2014
SP - 213
EP - 220
DO - 10.5220/0004832702130220