A pegging algorithm for the nonlinear resource allocation problem
A pegging algorithm for the nonlinear resource allocation problem
复制标题
DOI：
10.1016/s0305-0548(00)00089-7
复制
发表时间：
2002-04
期刊：
影响因子：
--
通讯作者：
Kurt M. Bretthauer;B. Shetty
中科院分区：
文献类型：
--
作者：
Kurt M. Bretthauer;B. Shetty
本文提出了一种求解非线性资源分配问题的新算法。非线性资源分配问题被定义为在单个凸约束和有界整数变量上的凸函数的最小化。我们首先提出了一个求解连续变量问题的钉住算法，然后将钉住方法结合到求解整数变量问题的分支定界算法中。我们比较的计算性能的钉住分支和定界算法与其他三种方法：乘子搜索分支和定界算法，动态规划，和0，1线性化方法。计算结果表明，钉住分支定界算法在求解非线性资源分配问题的方法上取得了一定的进步。范围和目的：非线性资源分配问题（即，背包问题，其中目标函数和单个约束都可以是非线性的）在各种应用中遇到，包括金融建模、抽样、生产和库存管理以及制造和计算机系统的嵌入式网络模型。尽管它的重要性，这些和其他应用程序，非线性资源分配问题在文献中得到了有限的关注。因此，我们开发的方法来解决连续和整数变量版本的问题，并报告广泛的计算测试的算法。
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. SCOPE AND PURPOSE: The nonlinear resource allocation problem (i.e., a knapsack problem where both the objective function and single constraint may be nonlinear) is encountered in a variety of applications, including financial modeling, sampling, production and inventory management, and queueing network models of manufacturing and computer systems. Despite its importance to these and other applications, the nonlinear resource allocation problem has received limited attention in the literature. Therefore, we develop methods for solving continuous and integer variable versions of the problem and report extensive computational testing of the algorithms.