Article ID: | iaor20023095 |
Country: | United Kingdom |
Volume: | 29 |
Issue: | 5 |
Start Page Number: | 505 |
End Page Number: | 527 |
Publication Date: | Apr 2002 |
Journal: | Computers and Operations Research |
Authors: | Shetty Bala, Bretthauer Kurt M. |
Keywords: | programming: branch and bound, programming: dynamic |
In this paper we present a new algorithm for solving the nonlinear resource allocation problem. The nonlinear resource allocation problem is defined as the minimization of a convex function over a single convex constraint and bounded integer variables. We first present a pegging algorithm for solving the continuous variable problem, and then incorporate the pegging method in a branch and bound algorithm for solving the integer variable problem. We compare the computational performance of the pegging branch and bound algorithm with three other methods: a multiplier search branch and bound algorithm, dynamic programming, and a 0,1 linearization method. The computational results demonstrate that the pegging branch and bound algorithm advances the state of the art in methods for solving the nonlinear resource allocation problem.