  This paper develops a polyhedral approach to the design, analysis, and
computation of dynamic allocation indices for scheduling binary-action
(engage/rest) Markovian stochastic projects which can change state when rested
(restless bandits (RBs)), based on partial conservation laws (PCLs). This
extends previous work by the author [J. Ni\~no-Mora. Restless bandits, partial
conservation laws and indexability. Adv. Appl. Probab., vol. 33, 76-98, 2001],
where PCLs were shown to imply optimality of index policies with a postulated
structure under admissible linear objectives, and they were deployed to obtain
sufficient conditions for the existence of Whittle's index and an
adaptive-greedy index algorithm. The contributions include: (i) we develop the
polyhedral foundation of the PCL framework, based on structural and algorithmic
properties of a polytope associated with an accessible set system
($\mathcal{F}$-extended polymatroid); (ii) we present new indices for RBs,
motivated by an admission control model, which extend Whittle's and have a
significantly increased scope; (iii) we deploy PCLs to obtain both sufficient
conditions for the existence of the new indices (PCL-indexability) and a
reformulated adaptive-greedy index algorithm; (iv) we interpret
PCL-indexability in terms of the economic law of diminishing marginal returns
and characterize the index as an optimal marginal cost rate; (v) we carry out a
PCL-indexability analysis of the motivating admission control model, which
gives, under mild conditions, a new index characterization of optimal threshold
policies; and (vi) we apply the latter to present new heuristic index policies
for two hard queueing control problems: admission control and routing to
parallel queues; and scheduling a multiclass make-to-stock queue with lost
sales, both under state-dependent holding cost rates and birth-death dynamics.
