Relaxations for the dynamic knapsack problem with stochastic item sizes

Optimization;Stochastic knapsack;Optimal policy;Dynamic programming;Bound/policy gap

Blado, Daniel E. ; Toriello, Alejandro Industrial and Systems Engineering Ahmed, Shabbir Dey, Santanu Foley, Robert Vempala, Santosh ; Toriello, Alejandro

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Optimization;    Stochastic knapsack;    Optimal policy;    Dynamic programming;    Bound/policy gap;   

Others  :  https://smartech.gatech.edu/bitstream/1853/60199/1/BLADO-DISSERTATION-2018.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We propose a new semi-infinite relaxation based on an affine value function approximation, and show that an existing pseudo-polynomial relaxation corresponds to a non-parametric value function approximation. We compare both theoretically to other relaxations from the literature and also perform a computational study. Our first main empirical conclusion is that our new relaxation, a Multiple Choice Knapsack (MCK) bound, provides tight bounds over a variety of different instances and becomes tighter as the number of items increases. Motivated by these empirical results, we then provide an asymptotic analysis of MCK by comparing it to a greedy policy. Subject to certain technical conditions, we show the MCK bound is asymptotically tight under two distinct but related regimes: a fixed infinite sequence of items under increasing capacity, and where capacity and the number of items increase at their own separate respective rates. The distributions tested in the initial computational study are consistent with such findings, and these results allow us to shift the focus towards stochastic knapsack instances that have a smaller number of items available, i.e. when the bound/policy gap starts to become a cause for concern. We then examine a new relaxation that builds upon the value function approximation that led to MCK. This bound is based on a quadratic value function approximation which introduces the notion of diminishing returns by encoding interactions between remaining items. We compare the bound to previous bounds in literature, including the best known pseudopolynomial bound, and contrast their corresponding policies with two natural greedy policies. Our main conclusion here is that the quadratic bound is theoretically more efficient than the pseudopolyomial bound yet empirically comparable to it in both value and running time. Lastly, we develop a finitely terminating general algorithm that solves the dynamic knapsack problem under integer sizes and capacity within an arbitrary numerical tolerance. The algorithm follows the same value function approximation approach as the MCK and quadratic bounds, whereby, in the spirit of cutting plane algorithms, we successively improve upon a changing value function approximation through both column and constraint generation. We provide theoretical closed form solutions for the zero capacity case as well as an extensive computational study for the general capacitated case. Our most recent main conclusion is that the algorithm is able to significantly reduce the gap when the initial bounds or heuristic policies perform rather poorly; in other words, the algorithm performs best when we need it to the most.