TY - JOUR

T1 - Generalized restless bandits and the knapsack problem for perishable inventories

AU - Graczová, Darina

AU - Jacko, Peter

PY - 2014/5

Y1 - 2014/5

N2 - In this paper we introduce the Knapsack Problem for Perishable Inventories concerning the optimal dynamic allocation of a collection of products to a limited knapsack. The motivation for designing such a problem comes from retail revenue management, where different products often have an associated lifetime during which they can only be sold, and the managers can regularly select some products to be allocated to a limited promotion space which is expected to attract more customers than the standard shelves. Another motivation comes from scheduling of requests in modern multi-server data centers so that Quality-of-Service requirements given by completion deadlines are satised. Using the Lagrangian approach we derive an optimal index policy for the Whittle relaxation of the problem in which the knapsack capacity is used only on average. Assuming a certain structure of the optimal policy for the single-inventory control, we prove indexability and derive an efficient, linear-time algorithm for computing the index values. To the best of our knowledge, our paper is the first to provide indexability analysis of a restless bandit with bi-dimensional state (lifetime and inventory level). We illustrate that these index values are numerically close to the true index values when such a structure is not present. We test two index-based heuristics for the original, non-relaxed problem: (1) a conventional index rule, which prescribes to order the products according to their current index values and promote as many products as fit in the knapsack, and (2) a recently proposed index-knapsack heuristic, which employs the index values as a proxy for the price of promotion and proposes to solve a deterministic knapsack problem to select the products. By a systematic computational study we show that the performance of both heuristics is nearly-optimal, and that the index-knapsack heuristic outperforms the conventional index rule.

AB - In this paper we introduce the Knapsack Problem for Perishable Inventories concerning the optimal dynamic allocation of a collection of products to a limited knapsack. The motivation for designing such a problem comes from retail revenue management, where different products often have an associated lifetime during which they can only be sold, and the managers can regularly select some products to be allocated to a limited promotion space which is expected to attract more customers than the standard shelves. Another motivation comes from scheduling of requests in modern multi-server data centers so that Quality-of-Service requirements given by completion deadlines are satised. Using the Lagrangian approach we derive an optimal index policy for the Whittle relaxation of the problem in which the knapsack capacity is used only on average. Assuming a certain structure of the optimal policy for the single-inventory control, we prove indexability and derive an efficient, linear-time algorithm for computing the index values. To the best of our knowledge, our paper is the first to provide indexability analysis of a restless bandit with bi-dimensional state (lifetime and inventory level). We illustrate that these index values are numerically close to the true index values when such a structure is not present. We test two index-based heuristics for the original, non-relaxed problem: (1) a conventional index rule, which prescribes to order the products according to their current index values and promote as many products as fit in the knapsack, and (2) a recently proposed index-knapsack heuristic, which employs the index values as a proxy for the price of promotion and proposes to solve a deterministic knapsack problem to select the products. By a systematic computational study we show that the performance of both heuristics is nearly-optimal, and that the index-knapsack heuristic outperforms the conventional index rule.

KW - Markov decision processes

KW - resource allocation

KW - knapsack problem

KW - index policies

KW - Whittle index

KW - Lagrangian relaxation

U2 - 10.1287/opre.2014.1272

DO - 10.1287/opre.2014.1272

M3 - Journal article

VL - 62

SP - 696

EP - 711

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 3

ER -