Robust optimization of the 0–1 knapsack problem: Balancing risk and return in assortment optimization

Robert P. Rooderkerk and Harald J. van Heerde

European Journal of Operational Research, 2016, vol. 250, issue 3, 842-854

Abstract: Retailers face the important but challenging task of optimizing their product assortments. The challenge is to find, for every category in every store, the assortment that maximizes (expected) category profit. Adding to the complexity of this 0–1 knapsack problem, retailers should also consider the risk associated with every assortment. While every product in the assortment offers an expected return, there is also uncertainty around its expected demand and profit contribution. Therefore, retailers face the difficult task of designing a portfolio of products that balances risk and return. In this paper, we develop a robust approach to optimize retail assortments that offers this balance. Since the dimensionality of this robust 0–1 knapsack problem in practice often precludes full enumeration, we propose a novel, efficient and real-time heuristic that solves this problem. The heuristic constructs an approximation of the risk-return Efficient Frontier of assortments. We find that the robust solutions offer the retailer a considerable reduction in risk (variance), yet only imply a small reduction in expected return. The constructed approximations contain assortments that are optimal solutions to the robust assortment optimization problem. Moreover, they represent insightful visualizations of the solution space, allowing for interactivity (“what risk premium should the retailer pay?”) in real-time (matter of seconds).

Keywords: Retailing; Assortments; Risk-return; Efficient Frontier; Robust optimization; Knapsack problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715009212
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:250:y:2016:i:3:p:842-854

DOI: 10.1016/j.ejor.2015.10.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().