非线性背包问题是一类特殊而重要的非线性整数规划问题，它可以定义为在有限整数集上极大化一个可分离非线性函数的约束(可分离)最优化问题.由于这类问题在经济管理，金融投资，资源分配，工业生产及计算机网络的最优化模型中有着十分广泛的应用，因此研究非线性背包问题的算法具有重要的现实意义.本文所讨论的多约束非线性背包问题可以描述如下： maxf(x)=n∑j=1fj(xj)s.t.gi(x)=n∑j=1gij(xj)≤bi，i=1，…，m，x∈X={lj≤xj≤uj，xj为整数，j=1，…，n}，其中fj，gij为定义在[lj，uj]上的单调递增函数，lj和uj为整数，分别表示整数变量xj的下界和上界，bi是常数，这里i=1，…，m，j=1，…，n. 本文根据背包问题的结构特点，提出了一种替代对偶(surrogatedual)方法和区域分割方法来解这类多约束非线性背包问题.我们用替代松弛方法把多约束问题化为单约束问题，并利用0-1线性化方法求解替代松弛问题.为得到更紧的上界，消除对偶间隙以保证算法的收敛性，我们利用割平面方法求解替代对偶问题，利用区域割技术丢掉某些整数箱子，并把剩下的区域划分为一些整数箱子的并集，以便使替代松弛问题能有效求解，使算法在有限步内收敛到最优解.算法的特色和创新之处是把替代松弛方法用于求解对偶问题并与区域分割有效结合起来解决多约束非线性背包问题.数值结果表明本文提出的方法可以较有效地求解大规模多约束非线性背包问题.此外，我们还对来自实际应用中的多约束非线性背包问题进行了大量的数值试验. 本文总共分为五章，第一章简单介绍了非线性背包问题的背景和应用，整数规划问题算法的研究现状和研究进展，并介绍了本文的主要内容.第二章简单介绍了求解非线性背包问题(单约束)的现有的算法，如：分枝定界算法，动态规划与分枝定界的混合算法，0-1线性化方法，以及拉格朗日对偶与区域割算法等.第三章介绍替代对偶理论，包括替代松弛理论以及替代对偶搜索的几种经典算法.第四章介绍我们的非线性背包问题的替代对偶和区域割算法，并给出了数值试验结果.第五章是结论部分，是对本文结果的总结以及对未来研究的展望.