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 scheme. 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 adapted 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.