不可分离凸背包问题的拉格朗日分解和区域分割方法

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

A Lagrangian Decomposition and Domain Cut Algorithm for Nonseparable Convex Knapsack Problems

In this paper, we present an exact algorithm for solving nonseparable convex knapsack problems with linear constraints and bounded integer variables. The method is of branch-and-bound framework that combines the Lagrangian decomposition with a domain cut sheme. For each subproblem, the Lagrangian decomposition is used to produce an upper bound of the objective function together with a feasible solution and an infeasible solution. The lower bound is determined by the feasible solutions generated during the dual search. The domain cut scheme is adopted to partition the integer domain, thus reducing the duality gap. The algorithm finds an optimal solution in a finite number of iterations. Computational results are reported.