A unified method for a class of convex separable nonlinear knapsack problems
In this paper, a unified algorithm is proposed for solving a class of convex separable nonlinear knapsack problems, which are characterized by positive marginal cost (PMC) and increasing marginal losscost ratio (IMLCR). By taking advantage of these two characteristics, the proposed algorithm is applicable to the problem with equality or inequality constraints. In contrast to the methods based on KarushKuhnTucker (KKT) conditions, our approach has linear computation complexity. Numerical results are reported to demonstrate the efficacy of the proposed algorithm for different problems.
nonlinear knapsack problem convex programming separable programming singly constrained program