A hybrid method for solving nonlinear knapsack problems (Q1123129)

The following type of a nonlinear integer programming problem is considered: Minimize \(f(x):=f_ 1(x_ 1)+...+f_ n(x_ n)\), subject to \(g(x):=g_ 1(x_ 1)+...+g_ n(x_ n)\leq b\), \(x_ i\in N_ i:=\{0,1,...,u_ i\}\) for \(i=1,...,n\), where \(b=(b_ 1,...,b_ m)^ T\) and \(g_ i(x_ i)=(h_{1i}(x_ i),...,h_{mi}(x_ i))^ T\) and \(h_{ij}(x_ j)\in {\mathbb{N}}\) for \(x_ i\in N_ i\) and all i,j. By means of a subgradient algorithm a surrogate problem is determined. This problem is solved by dynamic programming, the data of which are used as bounds for the final branch-and-bound procedure to solve the original problem. Numerical results are also reported.