Descent algorithms for discrete resource allocation problems
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3, 2639-2644 vol.3
- https://doi.org/10.1109/cdc.1994.411545
Abstract
We consider a class of discrete resource allocation problems, which are hard due to the combinatorial explosion of the discrete search space. In addition, if no dosed-form expressions are available for the cost function of interest, one needs to evaluate or (for stochastic environments) estimate the cost function through simulation. A new approach for such problems (which are typically encountered in discrete event systems), was proposed previously by us (1993). In this paper, we study the deterministic version of the problem and derive necessary and sufficient conditions for a globally optimal solution. A descent algorithm is also presented and it is shown that the algorithm yields a globally optimal allocation.Keywords
This publication has 7 references indexed in Scilit:
- Optimal admission control in circuit-switched multihop radio networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Marked/phantom slot algorithms for a class of scheduling problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Optimal scheduling in systems with delay-sensitive trafficPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Stochastic Comparison Algorithm for Discrete Optimization with EstimationSIAM Journal on Optimization, 2000
- Stochastic Discrete OptimizationSIAM Journal on Control and Optimization, 1992
- Stochastic Estimation of the Maximum of a Regression FunctionThe Annals of Mathematical Statistics, 1952
- A Stochastic Approximation MethodThe Annals of Mathematical Statistics, 1951