Heuristics for the General Multiple Non-linear Knapsack Problem

We propose heuristic algorithms for the multiple non-linear knapsack problem with separable non-convex profit and weight functions. First, we design a fast constructive algorithm that provides good initial solutions. Secondly, we improve the quality of these solutions through local search procedures. We compare the proposed methods with exact and heuristic algorithms for mixed integer non-linear programming problems, proving that our approach provides good-quality solutions in smaller CPU time.