论文部分内容阅读
本文对线性约束不可分离凸背包问题给出了一种精确算法.该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法.利用拉格朗日分解方法可以得到每个子问题的一个可行解,一个不可行解,一个下界和一个上界.区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集,每个整数子箱子对应一个子问题.通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解.数值结果表明该算法对不可分离凸背包问题是有效的.